Cod sursa(job #1695931)

Utilizator lflorin29Florin Laiu lflorin29 Data 28 aprilie 2016 00:14:35
Problema Radix Sort Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;
using lint = long long int;

constexpr static int using_mask = 255;
array<vector<int>, using_mask + 1>Bucket;

int main() {
    ifstream cin("radixsort.in");
    ofstream cout("radixsort.out");

    int N, A, B, C; cin >> N >> A >> B >> C;
    vector<int>V(N, B);
    for(int i = 0; i < N - 1; ++i)
        V[i + 1] = (static_cast<lint>(A) * V[i] + B) % C;

    for(int Shift = 0; Shift < 32; Shift += 8) {
        for(auto itr : V)
            Bucket[(itr >> Shift) & using_mask].emplace_back(itr);
        for(int i = 0, cnt = 0; i <= using_mask; ++i)
            for(auto& itr : Bucket[i])
                V[cnt++] = itr;

        for(int i = 0; i <= 255; ++i)
            Bucket[i].clear();
    }

    for(int i = 0; i < N; i += 10)
       cout << V[i] << ' ';
    return 0;
}