Cod sursa(job #1976835)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 4 mai 2017 12:54:17
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 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 i = 1 ; i <= N ; ++i)
        Bucket[V[i] & Mask].push_back(V[i]);

    Transfer();

    for(int i = 1 ; i <= N ; ++i)
        Bucket[(V[i] >> 8) & Mask].push_back(V[i]);

    Transfer();

    for(int i = 1 ; i <= N ; ++i)
        Bucket[(V[i] >> 16) & Mask].push_back(V[i]);

    Transfer();

    for(int i = 1 ; i <= N ; ++i)
        Bucket[(V[i] >> 24) & 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;
}