Cod sursa(job #1091876)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 26 ianuarie 2014 10:12:17
Problema Radix Sort Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

const int NMAX = 10000005;
const int DIGITS = 4;
const int BITS = 8;
const int RADIX = 1<<BITS;
const int MASK = RADIX-1;

int N,A,B,C;
int V[NMAX];
vector<int> Buckets[RADIX];

void RadixSort()
{
    int i,j,k,shft;
    vector<int>::iterator it;
    for(i=0,shft=0; i<DIGITS; i++,shft+=BITS)
    {
        for(j=1; j<=N; j++)
        {
            k=(V[j]>>shft)&MASK;
            Buckets[k].push_back(V[j]);
        }
        for(j=0,k=1; j<RADIX; j++)
        {
            for(it=Buckets[j].begin(); it!=Buckets[j].end(); it++)
                V[k++]=*it;
            Buckets[j].resize(0);
        }
    }
}

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;

    RadixSort();

    for(i=1; i<=N; i+=10)
        printf("%d ",V[i]);
    return 0;
}