Cod sursa(job #1679608)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 8 aprilie 2016 08:57:31
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<cstdio>
#define MASK 255
int n,a,b,c,i,j,vmax,p,nr,v[10001000],x[10001000],y[300];
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] = ( a * v[ i - 1 ] + b ) % c;
        vmax = maxim( vmax , v[i] );
    }
    while( vmax ){
        nr++;
        vmax /= 256;
    }
    p = 0;
    while(nr--){
        for(i=0;i<=260;i++){
            y[i] = 0;
        }
        for(i=1;i<=n;i++){
            y[ ( v[i] >> p ) & MASK ]++;
        }
        for(i=1;i<=260;i++){
            y[i] += y[ i - 1 ];
        }
        for(i=n;i>=1;i--){
            x[ y[ (v[i] >> p) & MASK ] -- ] = v[i];
        }
        for(i=1;i<=n;i++){
            v[i] = x[i];
            x[i] = 0;
        }
        p += 8;
    }
    for(i=1;i<=n;i+=10){
        fprintf(g,"%d ",v[i]);
    }

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