Cod sursa(job #2607415)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 29 aprilie 2020 18:36:53
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;

void RSort(vector <int> & v)
{
    vector <vector <int>> buff(1 << 16);
    int mask = (1 << 16) - 1;

    for (auto i : v)
        buff[i & mask].push_back(i);
    
    v.clear();
    for (auto & vec : buff) {
        for (auto i : vec)
            v.push_back(i);
        vec.clear();
    }

    for (auto i : v)
        buff[i >> 16].push_back(i);
    
    v.clear();
    for (auto & vec : buff) {
        for (auto i : vec)
            v.push_back(i);
        vec.clear();
    }
}

int main()
{
    ifstream in("radixsort.in");
    ofstream out("radixsort.out");
    
    int n, a, b, c;
    in >> n >> a >> b >> c;
    
    vector <int> ans(n);
    ans[0] = b;
    for (int i = 1; i < n; i++)
        ans[i] = (1LL * ans[i - 1] * a + b) % c;

    RSort(ans);

    for (int i = 0; i < n; i += 10)
        out << ans[i] << ' ';
    
    out << '\n';
    return 0;
}