Cod sursa(job #2012782)

Utilizator CammieCamelia Lazar Cammie Data 19 august 2017 17:01:35
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

#define BITS 16
#define MASK ((1 << BITS) - 1)
#define NIL -1
#define NMAX 100000002

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

int v[NMAX], w[NMAX], nexxt[NMAX];
int head[1 << BITS], N;

void radixPass(int *a, int *b, int bits) {
  for (int i = 0; i <= MASK; i++) {
    head[i] = NIL;
  }
  for (int i = 0; i < N; i++) {
    int listNo = (a[i] >> bits) & MASK;
    nexxt[i] = head[listNo];
    head[listNo] = i;
  }
  int pos = N - 1;
  for (int i = MASK; i >= 0; i--) {
    int l = head[i];
    while (l != NIL) {
      b[pos--] = a[l];
      l = nexxt[l];
    }
  }
}

int main(void) {

    int A, B, C;
    fin >> N >> A >> B >> C;
    v[0] = B;

  for (int i = 1; i < N; i++) {
        v[i] = (A * v[i - 1] + B) % C;
  }

  radixPass(v, w, 0);
 // radixPass(w, v, 16);

  for (int i = 0; i < N; i+= 10) {
    //assert(v[i] >= v[i - 1]);
    fout << w[i] << " ";
  }
}