Pagini recente » Cod sursa (job #2939724) | Cod sursa (job #46239) | Cod sursa (job #1668765) | Cod sursa (job #376099) | Cod sursa (job #2224080)
#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 int MASK = (1 << BITS) - 1;
const int MAX_BITS = 32;
void radixSort(vector<int>& values, const int shift) {
auto buckets = vector<vector<int>>(MASK + 1);
for (const auto& v : values) {
buckets[(v >> shift) & MASK].push_back(v);
}
int i = 0;
for (auto& b : buckets) {
for (const auto& v : b) {
values[i++] = v;
}
}
}
void radixSort(vector<int>& values) {
for (int shift = 0; shift < MAX_BITS; shift += BITS) {
radixSort(values, shift);
}
}
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;
}