Cod sursa(job #1189167)

Utilizator xtreme77Patrick Sava xtreme77 Data 21 mai 2014 17:45:51
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <cstring>
const int MAX=10000100;
const int JUM=1<<16;
int v[MAX],b[MAX],bkt[JUM],mk,n,maiincolocu;
void radixsort();
void countsort(int go_to[],int from[]);
int main()
{
    int a,b,c,i;
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    for(scanf("%d%d%d%d",&n,&a,&b,&c),v[1]=b,i=2;i<=n;v[i]=(1LL*a*v[i-1]+b)%c,++i);
    for(radixsort(),i=1;i<=n;printf("%d ",v[i]),i+=10);printf("\n");
    return 0;
}
void countsort(int go_to[],int from[])
{
    for(int i=1;i<=n;++bkt[(from[i]&mk)>>maiincolocu],++i);
    for(int i=1;i<JUM;bkt[i]+=bkt[i-1],++i);
    for(int i=n;i>=1;go_to[bkt[(from[i]&mk)>>maiincolocu]--]=from[i],--i);
}
void radixsort(){
    mk = 0x0000ffff;maiincolocu=0;
    countsort(b,v);
    mk = 0xffff0000;maiincolocu=16;
    memset(bkt,0,sizeof(bkt));
    countsort(v,b);
}