Cod sursa(job #3327683)

Utilizator ultra980Alex Stan ultra980 Data 4 decembrie 2025 19:22:20
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
using namespace std;

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

const uint MAXVAL = (1LL << 31) - 1, BASELOG = 6, BASE = 1 << BASELOG, MVLOG = 32;

const uint MAXN = 1e7;

uint v[MAXN];

vector<uint> bkts[BASE];

uint n, a, b, c;
void read_input() {
  fin >> n >> a >> b >> c;
  fin.close();
}

void gen_arr() {
  v[0] = b;
  for (uint i = 1; i < n; ++i) {
    v[i] = ((long long)a * v[i - 1] + b) % c;
  }
}
/*
void qsort(vector<uint> &v, int start, int end) {
  int b = start, e = end, pivot = v[(b + e) / 2];

  while (v[b] < pivot) {
    ++b;
  }

  while (v[e] > pivot) {
    --e;
  }

  while (b < e) {
    v[b] ^= v[e];
    v[e] ^= v[b];
    v[b] ^= v[e];

    do {
      ++b;
    } while (v[b] < pivot);

    do {
      ++e;
    } while (v[e] > pivot);
  }

  if (start < e) {
    qsort(v, start, e);
  }
  if (e + 1 < end) {
    qsort(v, e + 1, end);
  }
}
*/

void radix_sort(uint bits) {
  if (bits >= MVLOG) {
    return;
  }
  uint i, bkt;

  for (i = 0; i < n; ++i) {
    bkts[(v[i] >> bits) & (BASE - 1)].push_back(v[i]);
  }

  i = 0;
  for (bkt = 0; bkt < BASE; ++bkt) {
    // qsort(bkts[bkt], 0, bkts[bkt].size() - 1);
    for (uint nr : bkts[bkt]) {
      v[i] = nr;
      // printf("v[%u] = %u\n", i, nr);
      ++i;
    }
    bkts[bkt].clear();
  }
  radix_sort(bits + BASELOG);
}

void print_arr() {
  for (uint i = 0; i < n; i += 10) {
    fout << v[i] << ' ';
  }
  fout << '\n';
  fout.close();
}

int main() {
  read_input();
  gen_arr();
  radix_sort(0);
  print_arr();
}