Cod sursa(job #2274874)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 2 noiembrie 2018 16:56:25
Problema Radix Sort Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 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;
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)
{
    vector <int> Bucket[256];
    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];
    }
}

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