Cod sursa(job #1380114)

Utilizator geniucosOncescu Costin geniucos Data 6 martie 2015 22:04:26
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<cstdio>
#include<algorithm>

using namespace std;

int N, A, B, C, a[10000009], aux[10000009], cnt[300], ap[300];
                  10000011

void S (int left, int right)
{
    int msk = 0;

    for (int i=left; i<=right; i++)
        msk |= 1<<i;

    for (int i=0; i <= 256; i++)
        cnt[i] = 0;

    for (int i=1; i<=N; i++)
    {
        aux[i] = a[i];
        cnt[(a[i] & msk) >> left] ++;
    }

    ap[0] = 0;
    for (int i=1; i <= 256; i++)
        cnt[i] += cnt[i-1], ap[i] = 0;

    for (int i=1; i<=N; i++)
    {
        int type = (aux[i] & msk) >> left;

        ap[type] ++;

        if (type)
            a[cnt[type - 1] + ap[type]] = aux[i];
        else
            a[ap[type]] = aux[i];
    }
}

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

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

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

S (0, 7);
S (8, 15);
S (16, 23);
S (24, 31);

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

return 0;
}