Cod sursa(job #1364880)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 27 februarie 2015 21:09:35
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#include <vector>

#define MASK 255 /// 8 biti
#define Lim 256

using namespace std;
vector<int> v;
long long N,A,B,C;

void Read()
{
    scanf("%lld%lld%lld%lld",&N,&A,&B,&C);
    v.resize(N+1);
    v[1] = B;
    for(int i = 2; i <= N; ++i)
        v[i] = ( (A*v[i-1]) % C + B) % C;
}

void Radix_Sort(int k)
{
    vector<int> bucket[Lim];
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        bucket[ ((*it)>>k) & MASK ].push_back(*it);
    int pz = 0;
    for(int i = 0; i <= 255; ++i)
        for(vector<int>::iterator it = bucket[i].begin(); it != bucket[i].end(); ++it)
            v[pz++] = *it;
}

void Solve()
{
    for(int i = 0; i <= 32; i+=8)
        Radix_Sort(i);
}

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

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

    Read();
    Solve();
    Print();

    return 0;
}