Cod sursa(job #1293731)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 16 decembrie 2014 14:44:52
Problema Radix Sort Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#define D 8
#define MASK ((1<<D)-1)
#define MAXN 10000000
int nr[MASK+1], v[MAXN+1], aux[MAXN+1], n;
inline void radixSort(){
    int d, i;
    for(d=0; d<32; d+=D){
        for(i=1; i<=n; i++){
            nr[(v[i]>>d)&MASK]++;
        }
        for(i=1; i<=MASK; i++){
            nr[i]+=nr[i-1];
        }
        for(i=n; i>0; i--){
            aux[nr[(v[i]>>d)&MASK]--]=v[i];
        }
        for(i=1; i<=n; i++){
            v[i]=aux[i];
        }
        for(i=0; i<=MASK; i++){
            nr[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;
}