Cod sursa(job #1135607)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 8 martie 2014 02:28:15
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<cstdio>
#define mask (1<<8)-1
#define NMax 10000005
using namespace std;

int ind[260],V[NMax],aux[NMax];

int main ()
{
    int N,A,B,C,shift,i;
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&N,&A,&B,&C);
    V[1]=B;
    for (i=2; i<=N; i++)
        V[i]=(1LL*A*V[i-1]+B)%C;
    for (shift=0; shift<32; shift+=8)
    {
        for (i=0; i<=mask; i++)
            ind[i]=0;
        for (i=1; i<=N; i++)
            ind[(V[i]>>shift)&mask]++;
        for (i=1; i<=mask; i++)
            ind[i]+=ind[i-1];
        for (i=N; i; i--)
            aux[ind[(V[i]>>shift)&mask]--]=V[i];
        for (i=1; i<=N; i++)
            V[i]=aux[i];
    }
    for (i=1; i<=N; i+=10)
        printf("%d ",V[i]);
    return 0;
}