Cod sursa(job #2756756)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 2 iunie 2021 19:50:12
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define uint unsigned int

using namespace std;

void radix_sort (vector<uint> &v) {
  stack<uint> stk[16];  /// baza 16
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < (int)v.size(); j++)
      stk[(v[j] >> (i << 2)) & 15].push(v[j]);

    fill(v.begin(), v.end(), 0);
    int tmp_size = 0;
    for (int j = 0; j < 16; j++) {
      int z = tmp_size + (int)stk[j].size() - 1;
      tmp_size += (int)stk[j].size();
      while (!stk[j].empty()) {
        v[z--] = stk[j].top();
        stk[j].pop();
      }
    }
  }
}

int main () {
  ifstream fin ("radixsort.in");
  ofstream fout ("radixsort.out");
  int n; fin >> n;
  long long a, b, c; fin >> a >> b >> c;
  vector<uint> v(1, (uint)b);
  for (int i = 1; i < n; i++) v.push_back((uint)((a * v.back() + b) % c));
  radix_sort(v);
  for (int i = 0; i < n; i += 10) fout << v[i] << ' ';
  fout << '\n';
  return 0;
}