Cod sursa(job #2462629)

Utilizator preda.andreiPreda Andrei preda.andrei Data 27 septembrie 2019 17:49:06
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

void Sort(vector<int> &vec)
{
    constexpr int kBase = 256;
    vector<queue<int>> buckets1(kBase);
    vector<queue<int>> buckets2(kBase);
    vector<queue<int>> *curr = &buckets1;
    vector<queue<int>> *next = &buckets2;

    for (const auto &num : vec) {
        (*curr)[num % kBase].push(num);
    }

    int power = kBase;
    for (int i = 0; i < 3; i += 1) {
        for (auto &b : *curr) {
            while (!b.empty()) {
                (*next)[b.front() / power % kBase].push(b.front());
                b.pop();
            }
        }
        swap(curr, next);
        power *= kBase;
    }

    int index = 0;
    for (auto &b : *curr) {
        while (!b.empty()) {
            vec[index] = b.front();
            index += 1;
            b.pop();
        }
    }
}

int main()
{
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");

    int n, a, b, c;
    fin >> n >> a >> b >> c;

    vector<int> vec(n);
    vec[0] = b;

    for (int i = 1; i < n; i += 1) {
        vec[i] = (1LL * vec[i - 1] * a + b) % c;
    }

    Sort(vec);

    for (int i = 0; i < n; i += 10) {
        fout << vec[i] << " ";
    }
    fout << "\n";

    return 0;
}