Cod sursa(job #1295406)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 19 decembrie 2014 13:56:11
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <cstring>

#define Bmask 8
#define Nmax 10000000 + 10

using namespace std;

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

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

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

    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];

    ap[0] = 0;

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

    for (i = 1; i <= N; ++i)
        v[i] = aux[i];
}

int main()
{
    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] = (A * v[i-1] + B) % C;

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

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

    return 0;
}