Cod sursa(job #2230544)

Utilizator stefan.botezStefan Botez stefan.botez Data 10 august 2018 15:07:21
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>

using namespace std;

const int nmax = 10000005;
const int mask = (1 << 8) - 1;

int n, a, b, c, k, bucket[mask + 5], v[nmax], output[nmax];

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] = (1LL * a * v[i - 1] + b) % c;

    for(int shift = 0; shift < 32; shift += 8)//sortam dupa cel mai nesemnificativ byte
    {
        for(int i = 1; i <= n; i++)
        {
            k = (v[i] >> shift) & mask;
            bucket[k]++;
        }

        for(int i = 1; i < mask; i++)
            bucket[i] += bucket[i - 1];

        for(int i = n; i; i--)
        {
            k = (v[i] >> shift) & mask;
            output[bucket[k]] = v[i];
            bucket[k]--;
        }

        for(int i = 1; i <= n; i++)
            v[i] = output[i];

        for(int i = 0; i < mask; i++)//resetam bcket-ul
            bucket[i] = 0;
    }

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

    return 0;
}