Cod sursa(job #1404455)

Utilizator 4ONI2015oni2015 4ONI2015 Data 28 martie 2015 11:10:07
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define mask (1 << 8) - 1
using namespace std;
int v[10000005], w[10000005], n, a, b, c, i, shift, buck[mask + 5], k;
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] = (1ll * v[i - 1] * a + b) % c;
    for(shift = 0; shift < 32; shift += 8)
    {
        for(i = 1; i <= n; i++)
        {
            k = ((v[i] >> shift)&mask);
            buck[k]++;
        }
        for(i = 1; i <= n; i++)
            buck[i] += buck[i - 1];
        for(i = n; i; i--)
        {
            k = ((v[i] >> shift)&mask);
            w[buck[k]--] = v[i];
        }
        for(i = 1; i <= n; i++)
            v[i] = w[i];
        for(i = 0; i <= mask; i++)
            buck[i] = 0;
    }
    for(i = 1; i <= n; i += 10)
        printf("%d ", v[i]);
    return 0;
}