Cod sursa(job #1380176)

Utilizator firutibogdanFiruti Bogdan-Cristian firutibogdan Data 6 martie 2015 22:43:44
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<cstdio>
#define bmax 256
using namespace std;
 
ifstream  fin("radixsort.in");
 
unsigned int k1, k2, aa, bb, cc;
unsigned int a[2][10000009], pr[bmax], ul[bmax],  nr[bmax];
unsigned int  n, i, cif, k, baza, *t1, *t2, *aux, baza1;
long long p, p1, x;
 
int main()
{
    FILE *fout;
    fout=fopen("radixsort.out","wt");
    baza=bmax;
    baza1=baza-1;
    fin>>n>>aa>>bb>>cc;
    p=0;
    t1=a[0];
    t1[1]=bb;
    x=bb;
    nr[(x>>p)&baza1]++;
    for(i=2;i<=n;i++)
    {
        x=((long long)aa*x+bb)%cc;
        t1[i]=x;
        nr[(x>>p)&baza1]++;
    }
    t2=a[1];
    for(k=1;k<=4;k++)
    {
        pr[0]=1;
        ul[0]=0;
        for(i=1;i<=baza1;i++)
        {
            pr[i]=pr[i-1]+nr[i-1];
            ul[i]=pr[i]-1;
            nr[i-1]=0;
        }
        nr[baza1]=0;
 
        p1=p+8;
 
        for(i=1;i<=n;i++)
        {
            x=t1[i];
            cif=(x>>p)&baza1;
            ul[cif]++;
            t2[ul[cif]]=x;
            nr[(x>>p1)&baza1]++;
        }
        p=p1;
 
        aux=t1;
        t1=t2;
        t2=aux;
    }
 
    for(i=1;i<=n;i=i+10)
    {
        fprintf(fout,"%u ",t1[i]);
    }
    fclose(fout);
    fin.close();
    return 0;
}