Cod sursa(job #1092198)

Utilizator andrettiAndretti Naiden andretti Data 26 ianuarie 2014 18:28:25
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define maxn 10000005
#define mask ((1<<8)-1)
using namespace std;

int N,A,B,C;
int v[maxn],bucket[mask+10],a[maxn];

void read(){
    scanf("%d%d%d%d",&N,&A,&B,&C);
}
void gen()
{
    v[1]=B;
    for(int i=2;i<=N;i++)
     v[i]=((1LL*A*v[i-1])%C+1LL*B)%C;
}

void radix_sort()
{
    int step,shift;
    for(step=1,shift=0;step<=4;step++,shift+=8)
    {
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=N;i++) bucket[(v[i]>>shift)&mask]++;
        for(int i=1;i<=mask;i++) bucket[i]+=bucket[i-1];
        for(int i=N;i;i--) a[bucket[(v[i]>>shift)&mask]--]=v[i];
        memcpy(v,a,sizeof(v));
    }
}

void print()
{
    for(int i=1;i<=N;i+=10)
      printf("%d ",v[i]);
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);

    read();
    gen();
    radix_sort();
    print();

    fclose(stdin);
    fclose(stdout);
    return 0;
}