Cod sursa(job #2617360)

Utilizator DiagrDiana Grigore Diagr Data 21 mai 2020 15:40:27
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
int n, a, b, c;
vector<int> v(n);

void radix_offset(vector<int>& v, int i){
   int  bit = 255 << (i * 8);
   vector<int> buckets[257];
   for (auto x : v){
       int bit_offset = (x & bit) >> (i * 8);
       buckets[bit_offset].push_back(x);
   }
   v.clear();
   for (int j = 0; j <= 256; j++){
      for (int l = 0; l < buckets[j].size(); l++)
          v.push_back(buckets[j][l]);
   }
}

void radixsort(vector<int> & vc){
    int maximum = *max_element(vc.begin(), vc.end());
    int bytes = 0;
    while(maximum){
        bytes += 1;
        maximum = maximum >> 1;
    }
    if (bytes % 256 == 0)
        bytes = bytes / 8;
    else
        bytes = bytes / 8 + 1;
    for (int i = 0; i < bytes; i++)
        radix_offset(vc, i);
}


int main() {
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> a >> b >> c;
    v.push_back(b);
    for (int i = 1; i < n; i++)
        v.push_back((1LL* a * v[i - 1] + b) % c);
    radixsort(v);
    for (auto i = 0; i < v.size(); i+=10)
        cout << v[i] << " ";
    return 0;
}