Pagini recente » Cod sursa (job #2722689) | Cod sursa (job #2020925) | Cod sursa (job #1997222) | Cod sursa (job #2241933) | Cod sursa (job #1446821)
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <list>
#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
typedef unsigned long long ULL;
typedef unsigned int uint;
uint v[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);
}
}
void radixSort(uint base) {
vector< list<uint> > buckets(base);
uint alreadySorted = 0;
uint p = 1;
uint moreSorted = 0;
do {
if (!p)
return;
uint infirstbucket = 0;
for (uint i = alreadySorted; i < N; i++) {
uint tmp = v[i] / p;
if (!tmp)
moreSorted++;
tmp %= base;
if (!tmp)
v[alreadySorted + (infirstbucket++)] = v[i];
else
buckets[tmp].push_back(v[i]);
}
int curIndex = alreadySorted + infirstbucket;
for (auto i = buckets.begin() + 1; i != buckets.end(); ++i)
for (auto j = i->begin(); j != i->end(); j = i->erase(j))
v[curIndex++] = *j;
p *= base;
} while (moreSorted);
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OtFile, "w", stdout));
scanf("%u%u%u%u", &N, &A, &B, &C);
makeVect();
radixSort(0xFF + 1);
for (uint i = 0; i < N; i += 10)
printf("%d ", v[i]);
return 0;
}