Cod sursa(job #2900006)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 9 mai 2022 21:19:54
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>

using namespace std;

const int N = 1e7;

unsigned v[N];

void radixSort(unsigned a[], int sz) {
  unsigned* b;
  b = new unsigned[sz];
  auto getByte = [](unsigned x, int k) {
    return (x >> (k * 8)) & ((1 << 8) - 1);
  };
  for (int k = 0; k < 4; ++k) {
    int counter[256] = {0};
    for (int i = 0; i < sz; ++i)
      if (k % 2 == 0)
        ++counter[getByte(a[i], k)];
      else
        ++counter[getByte(b[i], k)];
    int index[256];
    index[0] = 0;
    for (int i = 1; i < 256; ++i)
      index[i] = index[i - 1] + counter[i - 1];
    for (int i = 0; i < sz; ++i)
      if (k % 2 == 0)
        b[index[getByte(a[i], k)]++] = a[i];
      else
        a[index[getByte(b[i], k)]++] = b[i];
  }
}

int main() {
  ifstream cin("radixsort.in");
  ofstream cout("radixsort.out");
  unsigned n, a, b, c;
  cin >> n >> a >> b >> c;
  cin.close();
  v[0] = b;
  for (int i = 1; i < n; ++i)
    v[i] = (1LL * a * v[i - 1] + b) % c;
  radixSort(v, n);
  for (int i = 0; i < n; i += 10)
    cout << v[i] << " ";
  cout.close();
  return 0;
}