Cod sursa(job #1810484)

Utilizator dranoellenTurica Leonard-Petru dranoellen Data 20 noiembrie 2016 04:14:24
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstring>
#include <cstdio>
int vec[10000009],sec[10000009],inc[257];
int main()
{
    FILE *in =fopen("radixsort.in" ,"r"), *out=fopen("radixsort.out","w");
    int a,b,c,n;
    long long x;
    fscanf(in,"%d%d%d%d",&n,&a,&b,&c);
    vec[1]=b;
    int i=2,step=0,nr;
    for(;i<=n;++i)
    {
        x=vec[i-1];
        x*=a;
        x+=b;
        x%=c;
        vec[i]=x;
    }
    for(;step<32;step+=8)
    {
        memset(inc,0,sizeof(inc));
        inc[0]=1;
        for(i=1;i<=n;++i)
            ++inc[1+((vec[i]>>step)%256)];
        for(i=1;i<256;++i)
            inc[i]=inc[i-1]+inc[i];
        for(i=1;i<=n;++i)
            nr=(vec[i]>>step)%256,
            sec[inc[nr]]=vec[i],
            ++inc[nr];
        for(i=1;i<=n;++i)
            vec[i]=sec[i];
    }
    for(i=1;i<=n;i+=10)
        fprintf(out,"%d ",vec[i]);
    return 0;
}