Cod sursa(job #1117077)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 23 februarie 2014 00:29:06
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<cstdio>
int n,a,b,c,v[10000100],x[10000100],fr[1000],i,j,q=255,w[4]={0,8,16,24};
FILE *f,*g;
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)(1LL*a*v[i-1]+b)%c);
    }
    for(i=0;i<=3;i++){
        for(j=0;j<=255;j++){
            fr[j]=0;
        }
        for(j=1;j<=n;j++){
            fr[(v[j]>>w[i])&q]++;
        }
        for(j=0;j<=255;j++){
            fr[j]+=fr[j-1];
        }
        for(j=n;j>=1;j--){
            x[fr[(v[j]>>w[i])&q]]=v[j];
            fr[(v[j]>>w[i])&q]--;
        }
        for(j=1;j<=n;j++){
            v[j]=x[j];
        }
    }
    for(i=1;i<=n;i+=10){
        fprintf(g,"%d ",x[i]);
    }






    fclose(f);
    fclose(g);
    return 0;
}