Cod sursa(job #2671087)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 11 noiembrie 2020 14:26:51
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

const int max_n = (int)1e8 + 5;
const int mask = (int)(1 << 8) - 1;
const int bytes = 8;
const int times = 4;

int n;

int a, b, c;

int v[max_n], counter[max_n], tmp[max_n];

int main() {
  ifstream in("radixsort.in");
  ofstream out("radixsort.out");
  in >> n >> a >> b >> c;
  v[1] = b;
  for (int i = 2; i <= n; ++i) {
    v[i] = (1LL * a * v[i - 1] + b) % c;
  }
  for (int t = 0; t < times; ++t) {
    memset(counter, 0, sizeof(counter));
    for (int i = 1; i <= n; ++i) {
      counter[((v[i] >> (t * bytes)) & mask)] += 1;
    }
    for (int i = 1; i <= mask; ++i) {
      counter[i] += counter[i - 1];
    }
    for (int i = n; i > 0; --i) {
      tmp[counter[((v[i] >> (t * bytes)) & mask)]] = v[i];
      counter[((v[i] >> (t * bytes)) & mask)] -= 1;
    }
    for (int i = 1; i <= n; ++i) {
      v[i] = tmp[i];
    }
  }
  for (int i = 1; i <= n; i += 10) {
    out << v[i] << " ";
  }
  return 0;
}