Cod sursa(job #1099707)

Utilizator andreiiiiPopa Andrei andreiiii Data 6 februarie 2014 10:35:05
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int N=10000007;

int a[2][N], ncount[1<<16], index[1<<16];

int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    int n, i, A, B, C, j, u;
    scanf("%d%d%d%d", &n, &A, &B, &C);
    a[0][1]=B;
    for(i=2;i<=n;i++) a[0][i]=(1LL*A*a[0][i-1]+B)%C;
    for(j=0, u=0;j<4;j++, u^=1)
    {
        memset(ncount, 0, sizeof(ncount));
        for(i=1;i<=n;i++)
        {
            ncount[(a[u][i]>>(16*j))&0xFFFF]++;
        }
        index[0]=1;
        for(i=1;i<(1<<16);i++) index[i]=index[i-1]+ncount[i-1];
        for(i=1;i<=n;i++)
        {
            a[u^1][index[(a[u][i]>>(16*j))&0xFFFF]++]=a[u][i];
        }
    }
    for(i=1;i<=n;i+=10) printf("%d ", a[0][i]);
}