Cod sursa(job #2615307)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 14 mai 2020 11:50:56
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define PLEC fin.close(); fout.close(); return 0;
using namespace std;
const string problem("radixsort");
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");
void radixsort(vector<int>& v) {
    vector<int> cnt(256), aux((int)v.size());
    for (int bit = 0; bit < 32; bit+=8) {
        for (const int& x : v)
            ++cnt[(x >> bit) & 255];
        for (int i = 1; i < 256; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = static_cast<int>(v.size()) - 1; i >= 0; --i)
            aux[--cnt[(v[i] >> bit) & 255]] = v[i];
        v = aux;
        fill(cnt.begin(), cnt.end(), 0);
    }
}
int n, a, b, c;
int main() {
    DAU
    fin >> n >> a >> b >> c;
    vector<int> v(n);
    v[0] = b;
    for (int i = 1; i < n; ++i)
        v[i] = (1LL * a * v[i - 1] + b) % c;
    radixsort(v);
    for (size_t i = 0; i < v.size(); i += 10)
        fout << v[i] << ' ';
    PLEC
}