Cod sursa(job #2637231)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 21 iulie 2020 22:47:04
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>

using namespace std;

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

const int N = 10000000, MOD = (1 << 16);
int n, a, b, c, v[N + 5], aux[N + 5], freq[MOD + 5], p, i;

int main(){
  fin >> n >> a >> b >> c;
  v[1] = b;
  for (i = 2; i <= n; i ++)
    v[i] = ((long long)v[i - 1] * a + b) % c;
  for (p = 0; p < 32; p += 8) {
    for (i = 0; i < MOD; i ++)
      freq[i] = 0;
    for (i = 1; i <= n; i ++)
      freq[(v[i] >> p) % MOD] ++;
    for (i = 1; i < MOD; i ++)
      freq[i] += freq[i - 1];
    for (i = n; i > 0; i --)
      aux[freq[(v[i] >> p) % MOD]] = v[i], freq[(v[i] >> p) % MOD] --;
    for (i = 1; i <= n; i ++)
      v[i] = aux[i];
  }
  for (i = 1; i <= n; i += 10)
    fout << v[i] << ' ';
  return 0;
}