Cod sursa(job #1452553)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 21 iunie 2015 12:30:45
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int Bmask = 8;
const int Nmax = 10000010;

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

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 ; --i)
        ap[i] = ap[i-1];

    for (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;
}