Pagini recente » Cod sursa (job #2389769) | Cod sursa (job #48780) | Cod sursa (job #126906) | Cod sursa (job #1757072) | Cod sursa (job #1446871)
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
#define _submit
#ifdef _submit
#define InFile "radixsort.in"
#define OtFile "radixsort.out"
#else
#define InFile "fis.in"
#define OtFile "fis.out"
#endif
#define MAXN 10000010
//#define MAXN 11
#define BMAX 256
typedef unsigned long long ULL;
typedef unsigned int uint;
uint v[MAXN], counts[BMAX], alput[BMAX], cv[MAXN];
uint N, A, B, C;
void makeVect() {
v[0] = B;
for (uint i = 1; i < N; i++) {
ULL tmp = ULL(A)*ULL(v[i - 1]) + ULL(B);
tmp %= ULL(C);
v[i] = uint(tmp);
}
}
uint* radixSort(uint pow2) {
uint base = (1 << pow2) - 1;
uint lim = sizeof(uint)*pow2;
uint p = 0;
bool found = true;
uint *vect = cv, *vectcp = v;
do {
if (p >= 32)
break;
for (uint i = 0; i < BMAX; i++)
counts[i] = alput[i] = 0;
found = false;
for (uint i = 0; i < N; i++) {
uint tmp = vectcp[i] >> p;
if (tmp)
found = true;
tmp &= base;
counts[tmp]++;
}
for (uint i = 1; i < BMAX; i++)
counts[i] += counts[i - 1];
for (uint i = 0; i < N; i++) {
uint tmp = vectcp[i] >> p;
if (tmp)
found = true;
tmp &= base;
uint before = (tmp) ? counts[tmp - 1] : 0;
vect[before + (alput[tmp]++)] = vectcp[i];
}
uint* aux = vect;
vect = vectcp;
vectcp = aux;
p += pow2;
} while (found);
return vectcp;
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OtFile, "w", stdout));
scanf("%u%u%u%u", &N, &A, &B, &C);
makeVect();
uint* toPrint = radixSort(8);
for (uint i = 0; i < N; i += 10)// 10)
printf("%d ", toPrint[i]);
return 0;
}