Cod sursa(job #1380117)

Utilizator geniucosOncescu Costin geniucos Data 6 martie 2015 22:06:11
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

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

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

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

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

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

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

    memcpy (aux, a, sizeof(a));

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