Pagini recente » Cod sursa (job #1146386) | Cod sursa (job #281858) | Cod sursa (job #2548835) | Cod sursa (job #3199719) | Cod sursa (job #2496885)
#include <fstream>
#include <vector>
using namespace std;
char const in_file[] = "radixsort.in";
char const out_file[] = "radixsort.out";
ifstream Read(in_file);
ofstream Write(out_file);
void RadixSort(
vector<uint32_t> &vec,
uint32_t const max_value
) {
vector<uint32_t> sol(vec.size());
vector<uint32_t> cnt(10);
uint32_t digit;
uint32_t i;
for (uint64_t pow = 1; pow <= max_value; pow *= 10) {
fill(cnt.begin(), cnt.end(), 0);
for (i = 0; i < vec.size(); ++i) {
++cnt[(vec[i] / pow) % 10];
}
for (i = 1; i < 10; ++i) {
cnt[i] += cnt[i - 1];
}
for (i = vec.size() - 1; (int)i >= 0; --i) {
digit = (vec[i] / pow) % 10;
--cnt[digit];
sol[cnt[digit]] = vec[i];
}
vec = sol;
}
for (i = 0 ; i < sol.size(); i += 10) {
Write << sol[i] << ' ';
}
}
void Solve() {
uint32_t n;
uint32_t A;
uint32_t B;
uint32_t C;
Read >> n;
Read >> A;
Read >> B;
Read >> C;
vector<uint32_t> vec(n);
uint32_t max_value = 0;
vec[0] = B;
for (uint32_t i = 1; i < n; ++i) {
vec[i] = (1ULL * vec[i - 1] * A + B) % C;
max_value = max(max_value, vec[i]);
}
RadixSort(vec, max_value);
}
int main() {
Solve();
Read.close();
Write.close();
return 0;
}