Pagini recente » Cod sursa (job #3286700) | Cod sursa (job #1176845) | Arhiva de probleme | Cod sursa (job #3283011) | Cod sursa (job #2224077)
#include <fstream>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
const string IN_FILE = "radixsort.in";
const string OUT_FILE = "radixsort.out";
const int BITS = 8;
const unsigned MASK = (1 << BITS) - 1;
const int MAX_BITS = 32;
void radixSort(vector<int>& values, const unsigned mask, const int shift) {
if (int(values.size()) <= 1 || shift < 0) return;
auto buckets = vector<vector<int>>(MASK + 1);
for (const auto& v : values) {
buckets[(v & mask) >> shift].push_back(v);
}
int i = 0;
for (auto& b : buckets) {
radixSort(b, mask >> BITS, shift - BITS);
for (const auto& v : b) {
values[i++] = v;
}
}
}
void radixSort(vector<int>& values) {
radixSort(values, MASK << (MAX_BITS - BITS), MAX_BITS - BITS);
}
vector<int> generateInput() {
ifstream in(IN_FILE);
int n, a, b, c;
in >> n >> a >> b >> c;
in.close();
auto values = vector<int>(n);
values[0] = b;
for (int i = 1; i < n; i++) {
values[i] = (1LL * a * values[i - 1] + b) % c;
}
return values;
}
void writeOutput(const vector<int>& values) {
ofstream out(OUT_FILE);
for (int i = 0; i < int(values.size()); i += 10) {
out << values[i] << (i + 10 < int(values.size()) ? " " : "\n");
}
out.close();
}
int main() {
auto values = generateInput();
radixSort(values);
writeOutput(values);
return 0;
}