Pagini recente » Cod sursa (job #870723) | Cod sursa (job #1827924) | Cod sursa (job #65163) | Cod sursa (job #891413) | Cod sursa (job #2974059)
//https://www.infoarena.ro/problema/radixsort
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector <int> buckets[100005];
vector <int> sorted;
void radix(int n) {
int x = 100000;
for (int i = 0; i < n; ++i) {
buckets[sorted[i] % x].push_back(sorted[i]);
}
sorted.clear();
for (int j = 0; j < x; ++j) {
for (int k = 0; k < buckets[j].size(); ++k) {
sorted.push_back(buckets[j][k]);
}
buckets[j].clear();
}
for (int i = 0; i < n; ++i) {
buckets[sorted[i] / x].push_back(sorted[i]);
}
sorted.clear();
for (int j = 0; j < x; ++j) {
for (int k = 0; k < buckets[j].size(); ++k) {
sorted.push_back(buckets[j][k]);
}
buckets[j].clear();
}
}
int main()
{
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int N, A, B, C;
fin >> N >> A >> B >> C;
sorted.reserve(N);
sorted.push_back(B);
for (int i = 2; i <= N; ++i) {
sorted.push_back((1LL * A * sorted.back() + B) % C);
}
radix(N);
for (int i = 0; i < N; i += 10) {
fout << sorted[i] << " ";
}
}