Cod sursa(job #1779916)

Utilizator BLz0rDospra Cristian BLz0r Data 15 octombrie 2016 18:10:00
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 10000002
#define Buckets 256

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

void RadixSort(vector<int> &V){

    int Mask = Buckets - 1;
    int N = V.size();

    vector<int> Cnt, Sol;
    Cnt.resize(Buckets);
    Sol.resize(V.size());

    for (int i = 0; i < 32; i += 8) {
        fill(Cnt.begin(), Cnt.end(), 0);

        for (int j = 0; j < N; ++j)
            Cnt[(V[j] >> i) & Mask]++;

        for (int j = 1; j < Buckets; ++j)
            Cnt[j] += Cnt[j-1];

        for (int j = N-1; j >= 0; --j)
            Sol[--Cnt[(V[j] >> i) & Mask]] = V[j];

        copy(Sol.begin(), Sol.end(), V.begin());
    }
}

int main(){

    vector<int> V;

    int N, A, B, C;

    fin >> N >> A >> B >> C;

    V.resize(N);

    V[0] = B;

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

    RadixSort(V);

    for (int i = 0; i < N; i += 10)
        fout << V[i] << " ";

    return 0;
}