Cod sursa(job #2756771)

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

using namespace std;

uint v[maxn][2];
int cnt[base], pref_cnt[base];

void radix_sort (int n, int &pin) {
  int i, j, z;
  for (i = 0; i < 4; i++, pin ^= 1) {
    for (j = 0; j < n; j++)
      cnt[(v[j][pin] >> (i << 3)) & 255]++;
    for (pref_cnt[0] = cnt[0], j = 1; j < base; j++)
      pref_cnt[j] = cnt[j] + pref_cnt[j-1];

    for (j = 0; j < n; j++) {
      z = ((v[j][pin] >> (i << 3)) & 255);
      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] = (uint)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;
}