Cod sursa(job #2970839)

Utilizator smunteanuMunteanu Stefan Catalin smunteanu Data 25 ianuarie 2023 23:00:17
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;

void solve() {
  
  size_t n, a, b, c;
  cin >> n >> a >> b >> c;

  array<vector<unsigned>, 512> s;

  for (size_t i = 0, x = b; i < n; i++) {
    s[x & 0xff].push_back(static_cast<unsigned>(x));
    x = (a * x + b) % c;
  }

  for (unsigned i = 1; i < 4; i++) {
    array<vector<unsigned>, 512> p = move(s);
    for (const vector<unsigned>& v : p) {
      for (unsigned x : v) {
        s[(x & (0xff << (i * 8))) >> (i * 8)].push_back(x);
      }
    }
  }
  

  vector<unsigned> v;
  for (vector<unsigned>& p : s) {
    for (unsigned x : p) v.push_back(x);
    p.clear();
  }
  for (size_t i = 0; i < n; i += 10) cout << v[i] << ' ';


}

int main() {

  #ifdef LOCAL
  freopen("file.in", "r", stdin);
  #else
  freopen("radixsort.in", "r", stdin);
  freopen("radixsort.out", "w", stdout);
  #endif

  ios_base::sync_with_stdio(false), cin.tie(NULL);

  solve();
}