Mai intai trebuie sa te autentifici.
Cod sursa(job #2247669)
Utilizator | Data | 28 septembrie 2018 21:43:58 | |
---|---|---|---|
Problema | Radix Sort | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.06 kb |
#include <bits/stdc++.h>
using namespace std;
const int kBuckets = 256;
void sort_by_bucket(function<int (int)> bucket_of_int, const vector<int>& from, vector<int>& to) {
vector<int> bucket_count(kBuckets, 0);
for (int n : from)
bucket_count[bucket_of_int(n)]++;
for (int i = 0, total = 0; i < kBuckets; i++) {
int self = bucket_count[i];
bucket_count[i] = total;
total += self;
}
for (size_t i = 0; i < from.size(); i++) {
to[bucket_count[bucket_of_int(from[i])]++] = from[i];
}
}
int main() {
#ifdef INFOARENA
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
#endif
int n, a, b, c;
cin >> n >> a >> b >> c;
vector<int> v, w;
v.push_back(b % c);
for (int i = 1; i < n; i++) {
v.push_back((1LL * a * v[i - 1] % c + b) % c);
}
w.resize(n);
for (int offset = 0; offset < 32; offset += 8) {
sort_by_bucket([offset](int x) { return (x >> offset) & 0xFF; }, v, w);
v.swap(w);
}
for (int i = 0; i < n; i += 10) {
cout << v[i] << ' ';
}
cout << '\n';
return 0;
}