Cod sursa(job #2452999)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 2 septembrie 2019 01:34:22
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <vector>
#include <fstream>

using std::vector;
std::ifstream fin("radixsort.in");
std::ofstream fout("radixsort.out");

int main() {
    int n, a, b, c;
    fin >> n >> a >> b >> c;

    vector<uint32_t> v(n); v[0] = b;
    for (int i = 1; i < n; i++)
        v[i] = (1LL * a * v[i - 1] + b) % c;

    vector<uint32_t> w(n);
    for (int it = 0; it < 32; it += 8) {
        swap(v, w);
        vector<int> frq(257);

        for (int i = 0; i < n; i++)
            frq[((w[i] >> it) & 255) + 1]++;
        for (int i = 1; i <= 256; i++)
            frq[i] += frq[i - 1];
        for (int i = 0; i < n; i++)
            v[frq[(w[i] >> it) & 255]++] = w[i];
    }

    for (int i = 0; i < n; i += 10)
        fout << v[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}