Cod sursa(job #2214959)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 20 iunie 2018 16:44:56
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
 
const int NMAX = 10000000;
int v[NMAX + 2];
int a, b, c, n, maxx;
int x[NMAX + 2];
 
int main()
{
  fin >> n >> a >> b >> c;
  v[1] = b;
  for (int i = 2; i <= n; i++) {
    v[i] = (1LL * v[i - 1] * a + b) % c;
    maxx = max(v[i], maxx);
  }
  for (int p = 0; p < 32; p += 8) {
    int f[256];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
      f[(v[i] >> p) % 256]++;
    for (int i = 1; i < 256; i++)
      f[i] = f[i] + f[i - 1];
    for (int i = n; i >= 1; i--) {
      x[f[(v[i] >> p) % 256]] = v[i];
      f[(v[i] >> p) % 256]--;
    }
    for (int i = 1; i <= n; i++)
      v[i] = x[i];
  }
  for (int i = 1; i <= n; i += 10)
    fout << v[i] << " ";
  return 0;
}