Cod sursa(job #1339693)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 11 februarie 2015 02:38:38
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<cstdio>
int n,a,b,c,i,j,vmax,p,nr,v[10001000],x[300],y[10001000];
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,"%d%d%d%d",&n,&a,&b,&c);
    v[1]=b;
    for(i=2;i<=n;i++){
        v[i]=int((long long)((a*v[i-1]+b)%c));
        vmax=maxim(v[i],vmax);
    }
    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];
        }
        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;
}