Cod sursa(job #1370093)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 3 martie 2015 12:57:11
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream>
#include<cstdio>
using namespace std;

ifstream  fin("radixsort.in");

unsigned int k1, k2, aa, bb, cc;
unsigned int a[2][10000009], pr[256], ul[256],  nr[256];
unsigned int  n, i, cif, k, baza;
long long p, p1, x;

int main()
{
    FILE *fout;
    fout=fopen("radixsort.out","wt");
    baza=256;
    fin>>n>>aa>>bb>>cc;
    p=1;
    a[0][1]=bb;
    x=bb;
    nr[x/p%baza]++;
    for(i=2;i<=n;i++)
    {
        x=((long long)aa*x+bb)%cc;
        a[0][i]=x;
        nr[x/p%baza]++;
    }

    for(k=1;k<=4;k++)
    {
        pr[0]=1;
        ul[0]=0;
        for(i=1;i<=baza-1;i++)
        {
            pr[i]=pr[i-1]+nr[i-1];
            ul[i]=pr[i]-1;
            nr[i-1]=0;
        }
        nr[baza-1]=0;

        p1=p*baza;

        k2=k%2;
        k1=1-k2;
        for(i=1;i<=n;i++)
        {
            x=a[k1][i];
            cif=x/p%baza;
            ul[cif]++;
            a[k2][ul[cif]]=x;
            nr[x/p1%baza]++;
        }
        p=p1;
    }

    for(i=1;i<=n;i=i+10)
    {
        fprintf(fout,"%u ",a[k2][i]);
    }
    fclose(fout);
    fin.close();
    return 0;
}