Pagini recente » Cod sursa (job #2922046) | Cod sursa (job #124571) | Cod sursa (job #1837551) | Cod sursa (job #1619640) | Cod sursa (job #2057918)
#include <stdio.h>
#pragma GCC optimize "O3"
#define MAX 10000000
int v[MAX];
#define BITS 4
#define MASK 0xf
#define TINY 0xff
inline void insertion(int lef, int rig) {
for (int i = lef; i < rig; ++i) {
int t, j; for (t = v[i], j = i - 1; j >= lef; --j)
if (t < v[j]) v[j + 1] = v[j]; else break;
v[j + 1] = t;
}
}
void radix(int lef, int rig, int bit) {
int x[MASK + 1], y[MASK + 1];
y[0] = lef; for (int i = 1; i <= MASK; ++i) y[i] = 0;
for (int i = lef; i < rig; ++i) ++y[v[i] >> bit & MASK];
for (int i = 1; i <= MASK; ++i) y[i] += y[i - 1];
for (int i = 1; i <= MASK; ++i) x[i] = y[i - 1]; x[0] = lef;
for (int i = 0; i <= MASK; ++i)
for (int xi = x[i], yi = y[i]; xi < yi; ++xi) {
int t = v[xi];
for (int j = t >> bit & MASK; j != i; j = t >> bit & MASK) {
//int xj = x[j]; for (; (v[xj] >> bit & MASK) == j; ++xj); x[j] = xj + 1;
//int tmp = t; t = v[xj]; v[xj] = tmp;
int tmp = t; t = v[x[j]]; v[x[j]++] = tmp;
}
v[xi] = t;
}
if (bit <= 0) return;
for (int i = 1; i <= MASK; ++i) x[i] = y[i - 1]; x[0] = lef;
for (int i = 0; i <= MASK; ++i) {
int d = y[i] - x[i];
if (d < 2) continue;
if (d < TINY) insertion(x[i], y[i]);
else radix(x[i], y[i], bit - BITS);
}
}
int main() {
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
int n, a, b, c; scanf("%d%d%d%d", &n, &a, &b, &c);
v[0] = b; a %= c, b %= c;
for (int i = 1; i < n; ++i) v[i] = (1ULL * a * v[i - 1] + b) % c;
radix(0, n, 31 - 31 % BITS);
for (int i = 0; i < n; i += 10) printf("%d ", v[i]);
}