Pagini recente » Cod sursa (job #1497638) | Cod sursa (job #1479097) | Monitorul de evaluare | Cod sursa (job #2278376) | Cod sursa (job #1240355)
#include <algorithm>
#include <fstream>
#include <iterator>
#include <cstdint>
using namespace std;
typedef uint32_t uint_t;
const uint_t BASE = 256;
inline uint_t number_of_digits(uint_t n) {
uint_t i;
for (i = 0; n; ++i, n /= BASE);
return i;
}
inline uint_t get_digit(uint_t n, uint_t d) {
for (; d > 0; --d, n /= BASE);
return n % BASE;
}
void counting_sort(
vector<uint_t>& v,
const uint_t digit,
vector<uint_t>& counter,
vector<uint_t>& storage) {
fill(counter.begin(), counter.end(), 0);
for (auto& x : v) {
++counter[ get_digit(x, digit) ];
}
partial_sum(counter.begin(), counter.end(), counter.begin());
for (auto i = v.rbegin(); i != v.rend(); i++) {
storage[ --counter[ get_digit(*i, digit) ] ] = *i;
}
copy(storage.begin(), storage.end(), v.begin());
}
int main() {
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
uint_t n, a, b, c;
fin >> n >> a >> b >> c;
vector<uint_t> v(n);
v[0] = b % c;
for (uint_t i = 1; i < n; ++i) {
v[i] = ((static_cast<uint64_t>(a) * v[i-1]) % c + b) % c;
}
vector<uint_t> counter(BASE);
vector<uint_t> temp_storage(v.size());
for (uint_t digit = 0; digit < number_of_digits(c); ++digit)
counting_sort(v, digit, counter, temp_storage);
for (uint_t i = 0; i < v.size(); i += 10)
fout << v[i] << ' ';
fout << endl;
fout.close();
fin.close();
return 0;
}