Cod sursa(job #1490271)

Utilizator raducostacheRadu Costache raducostache Data 23 septembrie 2015 08:35:13
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<cstdio>
int i,j,vmax,p,nr,v[10001000],x[300],y[10001000];
long long n,a,b,c,d;
FILE *f,*g;
int maxim(int a,int b){
    if(a>b)
        return a;
    return b;
}
int main(){
    f=fopen("radixsort.in","r");
    g=fopen("radixsort.out","w");
    fscanf(f,"%lld%lld%lld%lld",&n,&a,&b,&c);
    v[1]=b;
    for(i=2;i<=n;i++){
         d=(a*v[i-1]+b)%c;
         v[i]=d;
         vmax=maxim(vmax,v[i]);
    }
    while(vmax){
        nr++;
        vmax/=256;
    }
    p=0;
    while(nr--){
        for(i=0;i<=255;i++){
            x[i]=0;
        }
        for(i=1;i<=n;i++){
            x[ ( v[i] >> p ) & 255 ]++;
        }
        for(i=1;i<=255;i++){
            x[i]+=x[i-1];
        }
        for(i=n;i>=1;i--){
            y[ x[ ( v[i] >> p ) & 255 ]  ]=v[i];
            x[ ( v[i] >> p ) & 255 ]--;
        }
        for(i=1;i<=n;i++){
            v[i]=y[i];
        }
        p+=8;
    }
    for(i=1;i<=n;i+=10){
        fprintf(g,"%d ",v[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}