Cod sursa(job #2349531)

Utilizator lucametehauDart Monkey lucametehau Data 20 februarie 2019 15:53:26
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

using namespace std;

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

int n, a, b, c;

const int DIM = (1 << 16);

int v[10000005], tmp[10000005], f[DIM + 4], poz[DIM + 4];

int get(int x, int b) {
  return ((x >> (b * 16)) & (DIM - 1));
}

void sort(int a[], int b[], int c) {
  for(int i = 0; i < DIM; i++)
    f[i] = 0;
  for(int i = 1; i <= n; i++)
    f[get(a[i], c)]++;
  poz[0] = 0;
  for(int i = 1; i < DIM; i++)
    poz[i] = poz[i - 1] + f[i - 1];
  for(int i = 1; i <= n; i++)
    b[++poz[get(a[i], c)]] = a[i];
}

int main() {
  cin >> n >> a >> b >> c;
  v[1] = b % c;
  for(int i = 2; i <= n; i++) {
    v[i] = 1LL * v[i - 1] * a % c + b;
    if(v[i] >= c)
      v[i] -= c;
  }
  for(int i = 0; i < 11; i++) {
    if(i & 1)
      sort(tmp, v, i);
    else
      sort(v, tmp, i);
  }
  for(int i = 1; i <= n; i += 10)
    cout << v[i] << " ";
  return 0;
}