Cod sursa(job #1204810)

Utilizator DenisacheDenis Ehorovici Denisache Data 4 iulie 2014 02:12:30
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX_N 10000005
int v[MAX_N],N,i,a,b,c;
#define key(x) ((x>>(byte*8))&(0xFF))
void CS(int A[],int B[],int byte)
{
    int counter[1<<8],index[1<<8];
    memset(counter,0,sizeof(counter));
    for (register int i=1;i<=N;i++) ++counter[key(A[i])];
    index[0]=1;
    for (register int i=1;i<(1<<8);i++) index[i]=index[i-1]+counter[i-1];
    for (register int i=1;i<=N;i++) B[index[key(A[i])]++]=A[i];
}
int main()
{
    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]=(a*v[i-1]+b)%c;
    int *temp=new int[N+5];
    for (i=0;i<4;i++)
    {
        if (i&1) CS(temp,v,i);
        else CS(v,temp,i);
    }
    for (i=1;i<=N;i+=10) printf("%d ",v[i]);
    return 0;
}