Cod sursa(job #2644071)

Utilizator lucametehauDart Monkey lucametehau Data 23 august 2020 09:54:23
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("radixsort.in");
ofstream cout ("radixsort.out");

int n, a, b, c;

int v[10000005], tmp[10000005], cnt[65540], nr[65540];

int main() {
  cin >> 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 j = 0, msk = (1 << 16) - 1; j < 32; j += 16, msk <<= 16) {
    for(int i = 1; i <= n; i++)
      cnt[(v[i] & msk) >> j]++;
    for(int i = 1; i < (1 << 16); i++)
      cnt[i] += cnt[i - 1];
    for(int i = 1; i <= n; i++) {
      int k = ((v[i] & msk) >> j);
      nr[k]++;
      tmp[(k > 0 ? cnt[k - 1] : 0) + nr[k]] = v[i];
    }
    for(int i = 1; i <= n; i++)
      v[i] = tmp[i];
    for(int i = 0; i < (1 << 16); i++)
      cnt[i] = nr[i] = 0;
  }
  for(int i = 1; i <= n; i += 10)
    cout << v[i] << " ";
  return 0;
}