Pagini recente » Cod sursa (job #2284016) | Cod sursa (job #869628) | Cod sursa (job #1143652) | Cod sursa (job #2279470) | Cod sursa (job #2496946)
#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
) {
uint8_t bitmask = (1 << 8) - 1;
vector<uint32_t> sol(vec.size());
vector<uint32_t> cnt(bitmask + 1);
uint8_t byte_value;
uint32_t i;
for (uint8_t bit = 0; (1ULL << bit) <= max_value; bit += 8) {
fill(cnt.begin(), cnt.end(), 0);
for (i = 0; i < vec.size(); ++i) {
byte_value = (vec[i] >> bit) & bitmask;
++cnt[byte_value];
}
for (i = 1; i < cnt.size(); ++i) {
cnt[i] += cnt[i - 1];
}
for (i = vec.size() - 1; (int)i >= 0; --i) {
byte_value = (vec[i] >> bit) & bitmask;
--cnt[byte_value];
sol[cnt[byte_value]] = 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 % C;
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;
}