Cod sursa(job #1117217)

Utilizator acomAndrei Comaneci acom Data 23 februarie 2014 11:55:10
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<cstdio>
using namespace std;
#define NMAX 10000005
int n,A,B,C,v[NMAX],w[NMAX],f[256],a[4]={0,8,16,24};
int main()
{
    int i,p;
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d %d%d%d",&n,&A,&B,&C);
    v[1]=B;
    for (i=2;i<=n;++i)
        v[i]=(int)(((long long)A*v[i-1]+B)%C);
    for (p=0;p<4;++p)
    {
        for (i=0;i<256;++i)
            f[i]=0;
        for (i=1;i<=n;++i)
            ++f[(v[i]>>a[p])&255];
        for (i=1;i<256;++i)
            f[i]+=f[i-1];
        for (i=n;i>0;--i)
        {
            w[f[(v[i]>>a[p])&255]]=v[i];
            --f[(v[i]>>a[p])&255];
        }
        for (i=1;i<=n;++i)
            v[i]=w[i];
    }
    for (i=1;i<=n;i+=10)
        printf("%d ",v[i]);
    printf("\n");
    return 0;
}