Cod sursa(job #1576460)

Utilizator cristina_borzaCristina Borza cristina_borza Data 22 ianuarie 2016 14:50:15
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <cstdio>

using namespace std;

const int Nmax = 10000000 + 10;
const int Bmask = 8;

int n , a , b , c , i;
int v[Nmax] , aux[Nmax] , ap[1<<Bmask];

void radixXx(int p)
{
    int i , mask = (1 << Bmask) - 1;
    memset(ap , 0 , sizeof(ap));

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

    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]&(mask<<p))>>p]] = 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 += Bmask)
        radixXx(i);

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

    return 0;
}