Cod sursa(job #3201878)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 10 februarie 2024 06:42:22
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int sz = 1 << 8;
const int mask = sz - 1;

vector<int> v;
int n, a, b, c;

void radix()
{
    vector<int> aux(n);
    for (int i = 0; i < 32; i += 8)
    {
        vector<int> cnt(sz, 0);

        for (auto it : v)
            ++cnt[(it >> i) & mask];

        for (int j = 1; j < sz; ++j)
            cnt[j] += cnt[j - 1];

        for (int j = n - 1; j >= 0; --j)
            aux[--cnt[(v[j] >> i) & mask]] = v[j];

        v = aux;
    }
}

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

    v.reserve(n);
    v.push_back(b);

    for (int i = 1; i < n; ++i)
        v.push_back((1LL * v.back() * a + b) % c);

    radix();

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

    return 0;
}