Pagini recente » arena | Istoria paginii runda/oni_2010_ziua2 | arena | Istoria paginii runda/tema_asd | Cod sursa (job #2669014)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
const int BASE = 256;
int count[BASE]{};
ll n, a, b, c;
scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
int *v = new int[n];
int *container = new int[n];
v[0] = b;
for (int i = 1; i < n; i++) {
v[i] = ll(a * v[i-1] + b) % c;
}
auto dig = [] (int val, int sh) {
return (val >> (sh * 8)) & (BASE -1);
};
for (int sh = 0; sh < 4; sh++) {
memset(count, 0, sizeof(count));
for (int i = 0; i < n; i++) {
count[dig(v[i], sh)]++;
}
int pref = 0;
for (int i = 0; i < BASE; i++) {
int tmp = count[i];
count[i] = pref;
pref += tmp;
}
for (int i = 0; i < n; i++) {
container[count[dig(v[i], sh)]++] = v[i];
}
int* tmp = container;
container = v;
v = tmp;
}
for (int i = 0; i < n; i += 10) {
printf("%d ", v[i]);
}
puts("");
}