Cod sursa(job #2609426)

Utilizator AlexNicuNicu Alexandru AlexNicu Data 2 mai 2020 17:06:41
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>

using namespace std;
int v[2][10000005], nr[65536], poz[65536];
ifstream cin ( "radixsort.in" );
ofstream cout ( "radixsort.out" );
int main() {
  int n, a, b, c, i, p, k, j, cif;
  cin >> n >> a >> b >> c;
  v[0][0] = b;
  for( i = 1; i < n; i++ ) {
    v[0][i] = ( 1LL * a * v[0][i - 1] + b ) % c;
  }
  p = 1;
  a = 1 << 16;
  for (k = 0; k < 2; k++) {
    int ic = k & 1;
    int ia = 1 - ic;
    int nsh = k * 16;
    for (j = 0; j < a; j++) {
      nr[j] = 0;
    }
    for (i = 0; i < n; i++) {
      nr[(v[ic][i] >> nsh) & (a - 1)]++;
    }
    poz[0] = 0;
    for (j = 1; j < a; j++) {
      poz[j] = poz[j-1] + nr[j-1];
    }
    for (i = 0; i < n; i++) {
      cif = (v[ic][i] >> nsh) & (a - 1);
      v[ia][poz[cif]++] = v[ic][i];
    }
  }
  for ( i = 0; i < n; i += 10 )
    cout << v[0][i] << " ";
  return 0;
}