Cod sursa(job #2741736)

Utilizator avtobusAvtobus avtobus Data 18 aprilie 2021 15:02:23
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

ifstream fin {"radixsort.in"};
ofstream fout {"radixsort.out"};
// const int Nmax = 1e7+7;
void radix_sort(vi &v, short byte) {
  // byte: [0..3]
  int n = v.size();
  static vi vnew(n);
  short offset = byte*8;
  const int mask = (1<<8) - 1;
  const int BB = 257;
  static vi bucket(BB);
  fill(bucket.begin(), bucket.end(), 0);
  for(const auto &x: v) {
    bucket[((x >> offset) & mask)+1]++;
  }
  rep(i, BB-1) { bucket[i+1] += bucket[i]; }
  for(auto x: v) {
    short b = (x>>offset) & mask;
    vnew[bucket[b]++] = x;
  }
  swap(v, vnew);
}

int main(void) {
  // freopen("radixsort.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  vi v;
  int N, A, B, C;
  fin >> N >> A >> B >> C;
  v.resize(N);
  v[0] = B;
  for(int i = 1; i < N; i++) {
    v[i] = (1ll*A*v[i-1] + B) % C;
  }

  rep(byte, 4) {
    radix_sort(v, byte);
  }
  for(int i = 0; i < N; i+= 10) { fout << v[i] << " "; }
  fout << "\n";

  return 0;
}