Pagini recente » Cod sursa (job #1626271) | Cod sursa (job #2102787) | Cod sursa (job #154084) | Cod sursa (job #432613) | Cod sursa (job #2057941)
#include <stdio.h>
#pragma GCC optimize("O3")
#define MAX 10000000
int v[MAX];
int n, i, a, b, t;
#define BITS 3
#define MASK 0x7
#define TINY 0xf
void insertion(int lef, int rig) {
for (a = lef; a < rig; ++a) {
for (t = v[a], b = a - 1; b >= lef; --b)
if (t < v[b]) v[b + 1] = v[b]; else break;
v[b + 1] = t;
}
}
void radix(int lef, int rig, char bit) {
int x[MASK + 1], y[MASK + 1];
y[0] = lef; for (i = 1; i <= MASK; ++i) y[i] = 0;
for (i = lef; i < rig; ++i) ++y[v[i] >> bit & MASK];
for (i = 1; i <= MASK; ++i) y[i] += y[i - 1];
for (i = 1; i <= MASK; ++i) x[i] = y[i - 1]; x[0] = lef;
for (a = 0; a <= MASK; ++a)
for (; x[a] < y[a]; ++x[a])
for (b = v[x[a]] >> bit & MASK; b != a; b = v[x[a]] >> bit & MASK) {
t = v[x[a]]; v[x[a]] = v[x[b]]; v[x[b]++] = t; }
if (bit <= 0) return;
for (i = 1; i <= MASK; ++i) x[i] = y[i - 1]; x[0] = lef;
for (int w = 0; w <= MASK; ++w) {
if (y[w] - x[w] < 2) continue;
if (y[w] - x[w] < TINY) insertion(x[w], y[w]);
else radix(x[w], y[w], bit - BITS);
}
}
int main() {
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
scanf("%d%d%d%d", &n, &a, &v[0], &b);
for (i = 1; i < n; ++i) v[i] = (1ULL * a * v[i - 1] + v[0]) % b;
radix(0, n, 31 - 31 % BITS);
for (i = 0; i < n; i += 10) printf("%d ", v[i]);
}