Cod sursa(job #1178770)

Utilizator RathebaSerbanescu Andrei Victor Ratheba Data 27 aprilie 2014 10:55:35
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#include <cstring>

using namespace std;
#define MAX 10000001
#define DOI16 66000
int v[MAX],w[MAX],n,a,b,c,aux[DOI16],masca,shift;
void radix();
void counts(int sursa[], int destinatie[], int auxi[]);
int main()
{
    int i;
    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] = (1ll*a * v[i-1] + b) % c;
    radix();
    for(i=1; i<=n; i+=10)
        printf("%d ",v[i]);
    return 0;
}
void radix()
{
    masca=0x0000ffff; shift=0;
    counts(v,w,aux);
    memset(aux,0,66000*sizeof(int));
    masca=0xffff0000; shift=16;
    counts(w,v,aux);
}
void counts(int sursa[], int destinatie[], int auxi[])
{
    int i,index;
    for(i=1; i<=n; i++)
        aux[(sursa[i]&masca)>>shift]++;
    for(i=2; i<DOI16; i++)
        aux[i] += aux[i-1];
    for(i=n; i>=1; i--){
        index = (sursa[i]&masca)>>shift;
        destinatie[aux[index]]=sursa[i];
        aux[index]--;
    }
}