Cod sursa(job #2756766)

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

using namespace std;

uint v[maxn][2];
int cnt[64], pref_cnt[64];  /// baza 64 <=> 6 biti

void radix_sort (int n, int &pin) {
  int i, j, z, nsh;
  for (i = 0; i < 5; i++, pin ^= 1) {  /// fac exact 5 parcurgeri
    fill(cnt, cnt+64, 0);
    fill(pref_cnt, pref_cnt+64, 0);

    nsh = i * 6;
    for (j = 0; j < n; j++)
      cnt[(v[j][pin] >> nsh) & 63]++;
    for (pref_cnt[0] = cnt[0], j = 1; j < 64; j++)
      pref_cnt[j] = cnt[j] + pref_cnt[j-1];

    for (j = 0; j < n; j++) {
      z = ((v[j][pin] >> nsh) & 63);
      v[pref_cnt[z] - cnt[z]][pin^1] = v[j][pin];
      cnt[z]--;
    }
  }
  pin ^= 1;
}

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