Cod sursa(job #2562967)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 29 februarie 2020 20:46:43
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <vector>
using namespace std;
vector<int> v, aux;
vector<vector<int>> buckets;
const int MASK = 255;

void radix(int N, int step) {
  for (int i = 1; i <= N; ++i)
    buckets[ (v[i] >> (8*step)) & MASK].emplace_back(v[i]);
  int pz = 1;
  for (int i = 0; i <= MASK; ++i) {
    for (auto jt: buckets[i])
      v[pz++] = jt;
    buckets[i].clear();
    buckets[i].shrink_to_fit();
  }
}

int main()
{
  freopen("radixsort.in", "r", stdin);
  freopen("radixsort.out", "w", stdout);
  int N, A, B, C;
  scanf("%d%d%d%d", &N, &A, &B, &C);
  v.resize(N + 1);
  buckets.resize(MASK + 1);
  v[1] = B;
  for (int i = 2; i <= N; ++i) 
    v[i] = ((long long)A * ((long long)v[i - 1]) + (long long)B) % C;
  for (int i = 0; i < 4; ++i)
    radix(N, i);
  for (int i = 1; i <= N; i += 10)
    printf("%d ", v[i]);
  printf("\n");
  return 0;
}