Cod sursa(job #1848865)

Utilizator PaterucAPetruc Andrei Stefan PaterucA Data 16 ianuarie 2017 19:27:38
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

ifstream inf("radixsort.in");
ofstream outf("radixsort.out");

const int N=10000010;
int v1[N], v2[N], *u, *v, n, a, b, c, mask=(1<<8)-1, shift, B[256], i;

int main()
{
    inf>>n>>a>>b>>c;
    u=v1;
    v=v2;
    u[1]=b;
    for(i=2; i<=n; i++)
        u[i]=(1LL*a*u[i-1]+b)%c;

    for(shift=0; shift<=24; shift+=8)
    {
        for(i=0; i<=mask; i++)
            B[i]=0;
        for(i=1; i<=n; i++)
        {
            b=u[i]&mask;
            B[b]++;
        }
        for(i=1; i<=mask; i++)
            B[i]+=B[i-1];
        for(i=n; i>=1; i--)
        {
            b=u[i]&mask;
            v[B[b]]=u[i];
            B[b]--;
        }
        int *aux=u;
        u=v;
        v=aux;
    }
    for(i=1; i<=n; i+=10)
        outf<<v[i]<<" ";

    return 0;
}