Pagini recente » Cod sursa (job #1189053) | Cod sursa (job #1882060) | Cod sursa (job #1866851) | Cod sursa (job #1699711) | Cod sursa (job #2057831)
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize "O3"
ifstream fi("radixsort.in");
ofstream fo("radixsort.out");
#define BUFMAX 11000000
int bufcnt = BUFMAX - 1; char buf[BUFMAX];
inline void write(int x) {
buf[bufcnt--] = ' ';
do buf[bufcnt--] = x % 10 + '0', x /= 10; while (x);
}
inline void flush() { fo.write(buf + bufcnt + 1, BUFMAX - bufcnt - 2); }
#define MAX 10000000
int v[MAX];
#define BITS 8
#define RANK 4
#define MASK 0xff
int x[RANK][MASK + 1], y[RANK][MASK + 1];
inline void radix(int lef, int rig, int bit) {
int r = bit / BITS;
memset(y[r], 0, sizeof y[r]); y[r][0] = lef;
for (int i = lef; i < rig; i++) y[r][v[i] >> bit & MASK]++;
for (int i = 1; i <= MASK; i++) y[r][i] += y[r][i - 1];
for (int i = 1; i <= MASK; i++) x[r][i] = y[r][i - 1]; x[r][0] = lef;
for (int i = 0; i <= MASK; i++)
for (int xi = x[r][i], yi = y[r][i]; xi < yi; xi++) {
int t = v[xi];
for (int j = t >> bit & MASK; j != i; j = t >> bit & MASK) {
int xj = x[r][j]; for (; (v[xj] >> bit & MASK) == j; xj++); x[r][j] = xj + 1;
int tmp = t; t = v[xj]; v[xj] = tmp;
}
v[xi] = t;
}
if (bit <= 0) return;
for (int i = 1; i <= MASK; i++) x[r][i] = y[r][i - 1]; x[r][0] = lef;
for (int i = 0; i <= MASK; i++)
if (y[r][i] - x[r][i] > 1) radix(x[r][i], y[r][i], bit - BITS);
}
int main() {
int n, b, c; unsigned long long a; fi >> n >> a >> b >> c;
v[0] = b; a %= c, b %= c;
for (int i = 1; i < n; i++) {
unsigned long long t = a * v[i - 1] + b;
int thi = t >> 32, tlo = t; int aux;
asm("divl %4" : "=a"(aux), "=d"(v[i]) : "0"(tlo), "1"(thi), "r"(c));
}
radix(0, n, 24);
for (int i = n - 1 - (n - 1) % 10; i >= 0; i -= 10) write(v[i]); flush();
}