Cod sursa(job #3312747)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 29 septembrie 2025 19:46:23
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;

constexpr uint32_t H = 1 << 16;

int main() {
#ifndef LOCAL
  freopen("radixsort.in", "r", stdin);
  freopen("radixsort.out", "w", stdout);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  uint32_t N;
  int A;
  int B;
  int C;
  cin >> N >> A >> B >> C;
  vector<uint32_t> arr(N);
  arr[0] = B;
  for (uint32_t i = 1; i < N; i++) {
    arr[i] = ((int64_t)A * arr[i - 1] + B) % C;
  }
  vector<uint32_t> rra(N);
  for (int b = 0; b < 2; b++) {
    vector<uint32_t> cnt(H, 0);
    for (int i = 0; i < (int)N; ++i) {
      ++cnt[(arr[i] >> (16 * b)) & (H - 1)];
    }
    partial_sum(cnt.begin(), cnt.end(), cnt.begin());
    for (int i = N - 1; i >= 0; i--) {
      rra[--cnt[(arr[i] >> (16 * b)) & (H - 1)]] = arr[i];
    }
    arr.swap(rra);
  }
  for (uint32_t i = 0; i < N; i += 10) {
    if (i) cout << " ";
    cout << arr[i];
  }
  cout << "\n";
}