Cod sursa(job #2274859)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 2 noiembrie 2018 16:42:59
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
const int NMax = 10000000;
int X[NMax + 5];
int N,A,B,C;
vector <int> Bucket[256];
void Build()
{
    fin >> N >> A >> B >> C;
    X[1] = B;
    for(int i = 2; i <= N; ++i)
        X[i] = (1LL *A * X[i-1] + B) % C;
}

void Print()
{
    for(int i = 1; i <= N; i+=10)
        fout << X[i] << " ";
    fout << "\n";
}

void Radix(int p)
{
    int Shift = p*8;
    int Mask = (1<<8) - 1;
    for(int i = 1; i <= N; ++i)
    {
        Bucket[(X[i] >> Shift) & Mask].push_back(X[i]);
    }
    int k = 0;
    for(int i = 0; i <= 255; ++i)
    {
        for(int j = 0; j < (int)Bucket[i].size(); ++j)
            X[++k] = Bucket[i][j];
        Bucket[i].clear();
    }
}

int main()
{
    Build();
    for(int i = 0; i < 4; ++i)
    {
        Radix(i);
    }
    Print();
    return 0;
}