Cod sursa(job #1977482)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 5 mai 2017 12:25:34
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
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];

vector <int> Bucket[256];

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

void Transfer()
{
    k = 0;

    for(int i = 0 ; i <= 255 ; ++i)
        if(Bucket[i].size())
        {
            for(int j = 0 ; j < (int) Bucket[i].size() ; ++j)
                V[++k] = Bucket[i][j];

            Bucket[i].clear();
        }
}

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

    for(int i = 2 ; i <= N ; ++i)
        V[i] = (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_back(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;
}