Cod sursa(job #1527574)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 18 noiembrie 2015 13:03:23
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>

#define DIM 10000010
#define PER (1<<8)-1
using namespace std;

int V[DIM], W[DIM], P[PER+1], N, A, B, C;

void radixSort ()
{
    for (int p = 0; p <= 24; p += 8)
    {
        for (int i = 0; i <= PER; i ++)
            P[i] = 0;

        for (int i = 1; i <= N; i ++)
            P[((V[i]>>p)&PER)] ++;

        for (int i = 1; i <= PER; i ++)
            P[i] += P[i-1];

        for (int i = N; i >= 1; i --)
            W[P[((V[i]>>p)&PER)]--] = V[i];

        for (int i = 1; i <= N; i ++)
            V[i] = W[i];
    }

    return;
}

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 (int i = 2; i <= N; i ++)
        V[i] = (A * 1LL * V[i-1] + B) % C;

    radixSort ();

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

    fclose (stdin );
    fclose (stdout);

    return 0;
}