Cod sursa(job #2756803)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 2 iunie 2021 22:37:28
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 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];

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

    for (j = 1; j < base; j++)
      cnt[j] += cnt[j-1];

    for (j = n-1; j >= 0; j--) {
      z = ((v[j][pin] >> (i << 3)) & 255);
      v[--cnt[z]][pin^1] = v[j][pin];
    }
  }
}

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;
}