Cod sursa(job #1980100)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 12 mai 2017 12:22:11
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <queue>
using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

const int NMax = 10000005;

int N,A,B,C,Mask,k;
int V[NMax];

queue <int> Bucket[256];

void Read()
{
    fin >> N >> A >> B >> C;
}

void Transfer()
{
    k = 0;

    for(int i = 0 ; k < N ; ++i)
        if(Bucket[i].empty())   continue;
        else
        {
            while(!Bucket[i].empty())
            {
                V[++k] = Bucket[i].front();
                Bucket[i].pop();
            }
        }
}

void Solve()
{
    V[1] = B;

    for(int i = 2 ; i <= N ; ++i)
        V[i] = (1LL * A * V[i-1] + B) % C;

    Mask = 255;

    for(int p = 0 ; p < 4 ; ++p)
    {
        for(int i = 1 ; i <= N ; ++i)
            Bucket[(V[i] >> (8 * p)) & Mask].push(V[i]);

        Transfer();
    }
}

void Print()
{
    for(int i = 1 ; i <= N ; i += 10)
        fout << V[i] << " ";

    fout << "\n";
}

int main()
{
    Read();
    Solve();
    Print();

    fin.close();
    fout.close();
    return 0;
}