Cod sursa(job #1414148)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 2 aprilie 2015 13:25:09
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <cstring>

#define Bmask 16
#define Nmax 10000010

using namespace std;

int N , A , B , C , i;
int v[Nmax] , aux[Nmax] , ap[(1<<Bmask)];

void Radixx(int p)
{
    int i , mask = (1 << Bmask) - 1;

    memset(ap , 0 , sizeof(ap));

    for (i = 1; i <= N; ++i)
        ap[(v[i] & (mask << p)) >> p]++;

    for (i = 1; i <= mask; ++i)
        ap[i] += ap[i-1];

    for (i = mask; i >= 1; --i)
        ap[i] = ap[i-1];

    for (ap[0] = 0 , i = 1; i <= N; ++i)
        aux[++ap[(v[i] & (mask << p)) >> p]] = v[i];

    memcpy(v , aux , sizeof(aux));
}

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

    scanf("%d %d %d %d", &N, &A, &B, &C);

    for (v[1] = B , i = 2; i <= N; ++i)
     v[i] = (1LL * A * v[i-1] + B) % C;

    for (i = 0; i < 32; i += Bmask)
        Radixx(i);

    for (i = 1; i <= N; i += 10)
        printf("%d ", v[i]);

    return 0;
}