Pagini recente » Cod sursa (job #1285249) | Cod sursa (job #3121649) | Cod sursa (job #618580) | Monitorul de evaluare | Cod sursa (job #1755591)
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
#ifdef INFOARENA
#define TEST 0
#else
#define TEST 1
#endif
class RadixSort {
public:
RadixSort(int N, int A, int B, int C)
: N_(N), A_(A), B_(B), C_(C), already_sorted_(false) {
long long x = 0;
// Put numbers into buckets by their less significant digit
for (int i = 1; i <= N; ++i) {
x = (x * A_ + B_) % C_;
bucket_[0][x % 10].push(x); // push numbers in order
}
}
void Sort() {
int i = 1;
int source = 1, dest = 0;
do {
i *= 10;
source ^= 1;
dest ^= 1;
for (int j = 0; j < 10; ++j) {
while (!bucket_[source][j].empty()) {
// Extract one number and move it into other bucket
int x = bucket_[source][j].front();
bucket_[source][j].pop();
int r = x / i;
if (r > 0) {
bucket_[dest][r % 10].push(x);
} else {
sorted_numbers_.push_back(x);
}
}
}
} while (i != 1000000000);
}
const vector<int>& GetSortedNubmers() {
if (!already_sorted_) {
Sort();
already_sorted_ = 1;
}
return sorted_numbers_;
}
private:
int N_, A_, B_, C_;
vector<int> sorted_numbers_;
queue<int> bucket_[2][10]; // a queue for every digit
bool already_sorted_;
};
int main() {
RadixSort *instance;
if (TEST) {
instance = new RadixSort(100, 12, 38, 123);
} else {
freopen("radixsort.in","r",stdin);
freopen("radixsort.out","w",stdout);
int N, A, B, C;
scanf("%d %d %d %d", &N, &A, &B, &C);
instance = new RadixSort(N, A, B, C);
}
vector<int> nums = instance->GetSortedNubmers();
for (int i = 0; i < nums.size(); ++i) {
if (i % 10 == 0) {
printf("%d ", nums[i]);
}
}
return 0;
}