Cod sursa(job #1100764)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 7 februarie 2014 14:18:29
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
const int  X=0xff;
int n, a, b, c, i, j, k, v[2][10000010], x[256], y[256], nr, N, K;
int main(){
    f>>n>>a>>b>>c;
    v[0][1]=b;
    for(i=2; i<=n; i++)
        v[0][i]=(a*v[0][i-1]+b)%c;
    k=0;
    K=1;
    for(j=0; j<4; j++)
    {
        N=8*j;
        memset(x, 0, sizeof(x));
        for(i=1; i<=n; i++)
            x[ ( v[k][i]>>N )&X ]++;
        y[0]=1;
        for(i=1; i<256; i++)
            y[i]=y[i-1]+x[i-1];
        for(i=1; i<=n; i++)
        {
            nr=( ( v[k][i]>>N )&X );
            v[K][ y[nr] ]=v[k][i];
            y[nr]++;
        }
        k=K;
        K=(K^1);
    }
    for(i=1; i<=n; i+=10)
        g<<v[0][i]<<' ';
    g<<"\n";
    return 0;
}