Mai intai trebuie sa te autentifici.
Cod sursa(job #1490271)
Utilizator | 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;
}