Pagini recente » Cod sursa (job #2203887) | Cod sursa (job #1932090) | Cod sursa (job #1348838) | Cod sursa (job #1018775) | Cod sursa (job #2225040)
#include <bits/stdc++.h>
using namespace std;
int v[10000001];
int orderedArray[10000001];
int countingSort [1 << 16];
void sortBucket (int v[], int n, int bucketSize, int whichBucket) {
unsigned int mask = static_cast<unsigned int>((1 << bucketSize) - 1);
mask <<= (whichBucket * bucketSize);
for (int i = 0; i < (1 << bucketSize); ++i) {
countingSort[i] = 0;
}
for (int i = 1; i <= n; ++i) {
long long currentPosition = v[i] & mask;
currentPosition >>= (whichBucket * bucketSize);
countingSort[currentPosition] += 1;
}
mask >>= (whichBucket * bucketSize);
for (int i = 1; i <= mask; ++i) {
countingSort[i] += countingSort[i - 1];
}
for (int i = n; i >= 1; --i) {
long long currentPosition = v[i] & mask;
currentPosition >>= (whichBucket * bucketSize);
orderedArray[countingSort[currentPosition]] = v[i];
countingSort[currentPosition] -= 1;
}
for (int i = 1; i <= n; ++i) {
v[i] = orderedArray[i];
}
}
int main() {
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
int n, a, b, c;
fin >> n >> a >> b >> c;
v[1] = b;
for (int i = 2; i <= n; ++i) {
int newValue = static_cast<int>((1LL * a * v[i - 1] + b) % c);
v[i] = newValue;
}
for (int i = 0; i < 2; ++i) {
sortBucket(v, n, 8, i);
}
for (int i = 1; i <= n; i += 10) {
fout << v[i] << ' ';
}
return 0;
}