Cod sursa(job #1189470)

Utilizator timicsIoana Tamas timics Data 22 mai 2014 21:36:44
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
int N,A,B,C,MOD=255,v[10000100],s[100000100],r[256],sr[257],nr[256];

int main() {
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);

    //freopen("input.txt","r",stdin);

    scanf("%d%d%d%d",&N,&A,&B,&C);
    v[0] = B;
    for(int i=1;i<N;++i) {
         v[i] = (1LL*A * v[i-1] + B) % C;
    }

    for(int i=0;i<4;++i) {
        for(int j=0;j<256;++j) {
            r[j]=0;
            nr[j]=0;
        }
        for(int j=0;j<N;++j) {
            ++r[((v[j]&MOD)>>(8*i))];
        }

        sr[0]=0;

        for(int j=1;j<=256;++j) {
            sr[j] = sr[j-1]+r[j-1];
        }

        for(int j=0;j<N;++j) {
            int b = ((v[j]&MOD)>>(8*i));
            s[nr[b]+sr[b]]= v[j];
            ++nr[b];
        }

        for(int j=0;j<N;++j) {
            v[j] = s[j];
        }

        if(i==2) {
            MOD = MOD<<7;
            MOD -= (1<<23);
            continue;
        }
        MOD = MOD<<8;
    }

    for(int i=0;i<N;i+=10) {
        printf("%d ",v[i]);
    }
    return 0;
}