Cod sursa(job #1105897)

Utilizator proflaurianPanaete Adrian proflaurian Data 12 februarie 2014 11:09:08
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <cstdio>
#include <vector>
#define N 10000010
using namespace std;
struct nod
{
    int inf;
    nod *urm;
};
unsigned a,b,c,k,x,y;
int i,j,n,m,V[N];
nod *B[2][256],*aux;
int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
    //la fiecare grupare pe buchete mut secventa binara de 8 biti
    //din partea inferioara pe partea superioara
    x=b;k=x&255;y=(x>>8)|(k<<24);
    aux=new nod;aux->inf=y;aux->urm=B[0][k];B[0][k]=aux;
    b%=c;a%=c;
    for(i=1;i<n;i++)
    {
        x=(1LL*a*x%c+b)%c;
        k=x&255;y=(x>>8)|(k<<24);
        aux=new nod;aux->inf=y;aux->urm=B[0][k];B[0][k]=aux;
    }
    a=0;c=1;
    for(int cnt=3;cnt;cnt--)
    {
        for(i=0;i<=255;i++)
        if(B[a][i])
        for(aux=B[a][i];aux;)
        {
            B[a][i]=aux->urm;
            x=aux->inf;
            k=x&225;
            aux->inf=(x>>8)|(k<<24);
            aux->urm=B[c][k];
            B[c][k]=aux;
            aux=B[a][i];
        }
        a=1-a;c=1-c;
    }
    for(m=n-1,i=255;i>=0;i--)
        for(aux=B[a][i];aux;aux=aux->urm)
            V[m--]=aux->inf;
    for(i=0;i<n;i+=10)
        printf("%d ",V[i]);
    return 0;
}