Cod sursa(job #3350665)

Utilizator Alex_at_gameIustin-Alexandru Frateanu Alex_at_game Data 11 aprilie 2026 18:04:56
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(v) begin(v), end(v)
#define al(v, l, r) begin(v) + l, begin(v) + r + 1
#define sz(v) (int)v.size()
#define pb push_back
#define pob pop_back
#define fs first
#define sd second

constexpr int inf = 2e9;
constexpr ll infll = 4e18;

struct Radix {
    int n;
    vector<int> a;
    static constexpr int B = 65536;

    Radix(): n(0) {
    }

    void insert(int x) {
        a.pb(x);
        n++;
    }

    void sort() {
        vector<int> fr(B, 0), tmp(n);
        for (int x : a) {
            fr[x & (B - 1)]++;
        }

        for (int i = 1; i < B; ++i) {
            fr[i] += fr[i - 1];
        }

        for (int i = n - 1; i >= 0; --i) {
            tmp[--fr[a[i] & (B - 1)]] = a[i];
        }

        fill(all(fr), 0);
        for (int x : tmp) {
            fr[x >> 16]++;
        }

        for (int i = 1; i < B; ++i) {
            fr[i] += fr[i - 1];
        }

        for (int i = n - 1; i >= 0; --i) {
            a[--fr[tmp[i] >> 16]] = tmp[i];
        }
    }
} r;

int n, a, b, c, x;
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);

    cin >> n >> a >> b >> c;
    x = b;
    r.insert(x);

    for (int i = 1; i < n; ++i) {
        x = (1ll * a * x + b) % c;
        r.insert(x);
    }

    r.sort();
    for (int i = 0; i < n; i += 10) {
        cout << r.a[i] << " \n"[i + 10 >= n];
    }
}