Cod sursa(job #1091880)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 26 ianuarie 2014 10:16:29
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<cstdio>
#include<cstring>

using namespace std;

const int NMAX = 10000005;
const int DIGITS = 4;
const int BITS = 8;
const int RADIX = 1<<BITS;
const int MASK = RADIX-1;

int N,A,B,C;
int V[NMAX];
int T[NMAX];
int Buckets[RADIX];

void RadixSort()
{
    int i,j,k,shft;
    for(i=0,shft=0; i<DIGITS; i++,shft+=BITS)
    {
        for(j=1; j<=N; j++)
        {
            k=(V[j]>>shft)&MASK;
            Buckets[k]++;
        }
        for(j=1; j<RADIX; j++)
            Buckets[j]+=Buckets[j-1];
        for(j=N; j>=1; j--)
        {
            k=(V[j]>>shft)&MASK;
            T[Buckets[k]]=V[j];
            Buckets[k]--;
        }
        memcpy(V,T,sizeof(T));
        memset(Buckets,0,sizeof(Buckets));
    }
}

int main()
{
    int 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;

    RadixSort();

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