Cod sursa(job #1687296)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 12 aprilie 2016 19:34:45
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e7;
const int dim = 8;

int n , a , b , c , i;
int v[nmax] , aux[nmax];
int ap[1<<dim];

void bagaradix(int p)
{
    memset(ap , 0 , sizeof(ap));

    int i;
    int mask = (1 << dim) - 1;
    for (i = 1; i <= n; ++i)
        ap[(v[i] >> p) & mask]++;

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

    for (i = mask; i ; --i) ap[i] = ap[i-1];
    ap[0] = 0;

    for (i = 1; i <= n; ++i)
        aux[++ap[(v[i] >> p) & mask]] = v[i];

    for (i = 1; i <= n; ++i)
        v[i] = aux[i];
}

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

    for (i = 0; i < 32; i += dim)
        bagaradix(i);

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

    return 0;
}