Cod sursa(job #1293715)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 16 decembrie 2014 14:00:53
Problema Radix Sort Scor 30
Compilator c Status done
Runda Arhiva educationala Marime 1.02 kb
#include <stdio.h>
#define D 16
#define MASK ((1<<16)-1)
#define MAXN 10000000
int lista[MASK+1], val[MAXN+1], v[MAXN+1], next[MAXN+1], n;
inline void radixSort(){
    int d, i, j, p;
    for(d=0; d<2; d++){
        for(i=1; i<=n; i++){
            val[i]=v[i];
            next[i]=lista[(v[i]>>(d*D))&MASK];
            lista[(v[i]>>(d*D))&MASK]=i;
        }
        j=n;
        for(i=MASK; i>=0; i--){
            p=lista[i];
            while(p!=0){
                v[j--]=val[p];
                p=next[p];
            }
            lista[i]=0;
        }
    }
}
int main(){
    int a, b, c, i;
    FILE *fin, *fout;
    fin=fopen("radixsort.in", "r");
    fout=fopen("radixsort.out", "w");
    fscanf(fin, "%d%d%d%d", &n, &a, &b, &c);
    v[1]=b;
    for(i=2; i<=n; i++){
        v[i]=(a*(long long)v[i-1]+b)%c;
    }
    radixSort();
    for(i=1; i<=n-10; i+=10){
        fprintf(fout, "%d ", v[i]);
    }
    fprintf(fout, "%d\n", v[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}