Cod sursa(job #2603592)

Utilizator avtobusAvtobus avtobus Data 20 aprilie 2020 14:09:55
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 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;
const int INF = 0x3f3f3f3f;

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

void radix_sort(vi &v) {
  deque<int> bucket[2][256];

  // 0x000000ff
  for(auto x: v) {
    bucket[0][x&0x000000ff].push_back(x);
  }

  // 0x0000ff00
  rep(i, 256) {
    auto &b = bucket[0][i];
    while(!b.empty()) {
      int x = b.front(); b.pop_front();
      bucket[1][(x&0x0000ff00) >> 8].push_back(x);
    }
  }

  // 0x00ff0000
  rep(i, 256) {
    auto &b = bucket[1][i];
    while(!b.empty()) {
      int x = b.front(); b.pop_front();
      bucket[0][(x&0x00ff0000) >> 16].push_back(x);
    }
  }

  // 0xff000000
  rep(i, 256) {
    auto &b = bucket[0][i];
    while(!b.empty()) {
      int x = b.front(); b.pop_front();
      bucket[1][(x&0xff000000) >> 24].push_back(x);
    }
  }

  int cnt = 0;
  rep(i, 256) {
   auto &b = bucket[1][i];
    while(!b.empty()) {
      int x = b.front(); b.pop_front();
      v[cnt++] = x;
    }
  }
}

// void write(vi &v) {
//   for(auto x: v) { cout << x << " "; }
//   cout << '\n';
// }

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

  radix_sort(v);

  rep(i, v.size()) {
    if (i % 10 == 1) {
      fout << v[i] << " ";
    }
  }
  fout << endl;

  return 0;
}