Pagini recente » Cod sursa (job #2880817) | Cod sursa (job #3322540) | Cod sursa (job #3355086) | Cod sursa (job #2811524) | Cod sursa (job #3327683)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
const uint MAXVAL = (1LL << 31) - 1, BASELOG = 6, BASE = 1 << BASELOG, MVLOG = 32;
const uint MAXN = 1e7;
uint v[MAXN];
vector<uint> bkts[BASE];
uint n, a, b, c;
void read_input() {
fin >> n >> a >> b >> c;
fin.close();
}
void gen_arr() {
v[0] = b;
for (uint i = 1; i < n; ++i) {
v[i] = ((long long)a * v[i - 1] + b) % c;
}
}
/*
void qsort(vector<uint> &v, int start, int end) {
int b = start, e = end, pivot = v[(b + e) / 2];
while (v[b] < pivot) {
++b;
}
while (v[e] > pivot) {
--e;
}
while (b < e) {
v[b] ^= v[e];
v[e] ^= v[b];
v[b] ^= v[e];
do {
++b;
} while (v[b] < pivot);
do {
++e;
} while (v[e] > pivot);
}
if (start < e) {
qsort(v, start, e);
}
if (e + 1 < end) {
qsort(v, e + 1, end);
}
}
*/
void radix_sort(uint bits) {
if (bits >= MVLOG) {
return;
}
uint i, bkt;
for (i = 0; i < n; ++i) {
bkts[(v[i] >> bits) & (BASE - 1)].push_back(v[i]);
}
i = 0;
for (bkt = 0; bkt < BASE; ++bkt) {
// qsort(bkts[bkt], 0, bkts[bkt].size() - 1);
for (uint nr : bkts[bkt]) {
v[i] = nr;
// printf("v[%u] = %u\n", i, nr);
++i;
}
bkts[bkt].clear();
}
radix_sort(bits + BASELOG);
}
void print_arr() {
for (uint i = 0; i < n; i += 10) {
fout << v[i] << ' ';
}
fout << '\n';
fout.close();
}
int main() {
read_input();
gen_arr();
radix_sort(0);
print_arr();
}