Cod sursa(job #1250341)

Utilizator obidanDan Ganea obidan Data 28 octombrie 2014 00:13:59
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <cstdio>
using namespace std;

#define BASE  255
#define POW  8
#define NMax 10000000

int n,v[NMax],m[NMax],bucket[BASE+1];

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);

    int i,j,a,b,c;
    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] + b) % c;

    for(i = 0; i < 32; i+= POW)
    {
        for(j = 0; j <= BASE; j++)
            bucket[j] = 0;
        for(j = 1; j <= n; j++)
            ++bucket[(v[j]>>i)&BASE];
        for(j = 1; j <= BASE; j++)
            bucket[j]+=bucket[j-1];
        for(j = n; j >= 0; j--)
            m[bucket[(v[j]>>i)&BASE]--]=v[j];
        for(j = 1; j <= n; j++)
            v[j] = m[j];
    }

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