Cod sursa(job #3312744)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 29 septembrie 2025 19:28:10
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 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<vector<uint16_t>> bck(H);
  for (int b = 0; b < 2; ++b) {
    for (uint32_t i = 0; i < N; ++i) {
      bck[(arr[i] >> (b * 0xff)) & (H - 1)].push_back(arr[i]);
    }
    int i = 0;
    for (auto& e : bck) {
      copy(e.begin(), e.end(), arr.begin() + i);
      i += e.size();
      e.clear();
    }
  }
  for (uint32_t i = 0; i < N; i += 10) {
    if (i) {
      cout << " ";
    }
    cout << arr[i];
  }
  cout << endl;
  return 0;
}