Pagini recente » Cod sursa (job #2333734) | Cod sursa (job #3256158) | Cod sursa (job #2377625) | Cod sursa (job #3004295) | Cod sursa (job #2244673)
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <chrono>
#include <memory>
#include <cstring>
using LL = long long;
using ULL = int long long;
const std::string _problemName = "radixsort";
#define USE_FILES
#ifdef USE_FILES
namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}
#define cin fin
#define cout fout
#endif
template <
typename T,
typename Enable = void
>
class RadixSorter {};
template <typename T>
class RadixSorter<T, typename std::enable_if<sizeof(T) % 2 == 0>::type> {
static const int RADIX = 0xFF;
static const int RADIX_NR_BITS = 8;
static const int RADIX_COUNT = sizeof(T);
static const int RADIX_VALUES_COUNT = (1 << RADIX_NR_BITS);
public:
void radixsort(std::vector<T>& v) {
resize(v.size());
// assert RADIX_COUNT % 2 == 0
for (int idx = 0; idx < RADIX_COUNT; ++idx) {
if (idx % 2 == 0) {
countsort(v, aux_, idx);
}
else {
countsort(aux_, v, idx);
}
}
}
private:
void countsort(const std::vector<T>& from, std::vector<T>& to, int radixIdx) {
memset(buckets_, 0, sizeof(buckets_));
for (int fromIdx = 0; fromIdx < size_; ++fromIdx) {
int value = from[fromIdx];
int radix = getRadix(value, radixIdx);
++buckets_[radix];
}
index_[0] = 0;
for (int bucketIdx = 1; bucketIdx < RADIX_VALUES_COUNT; ++bucketIdx) {
index_[bucketIdx] = index_[bucketIdx - 1] + buckets_[bucketIdx - 1];
}
for (int fromIdx = 0; fromIdx < size_; ++fromIdx) {
int value = from[fromIdx];
int radix = getRadix(value, radixIdx);
int& index = index_[radix];
to[index] = value;
++index;
}
}
int getRadix(int value, int radixIdx) {
return (value >> (RADIX_NR_BITS * radixIdx)) & RADIX;
}
void resize(int n) {
size_ = n;
if (aux_.size() < n) {
aux_.resize(n);
}
}
private:
int size_;
std::vector<T> aux_;
int buckets_[RADIX_VALUES_COUNT];
int index_ [RADIX_VALUES_COUNT];
};
int main() {
int n, a, b, c;
std::cin >> n >> a >> b >> c;
std::vector<int> v;
v.reserve(n);
v.push_back(b);
for (int i = 1; i < n; ++i) {
v.push_back((1LL * a * v[i - 1] + b) % c);
}
RadixSorter<int>().radixsort(v);
// RadixSorter<char, char> sorter;
// std::vector<char> vc;
// sorter.radixsort(vc);
for (int idx = 0; idx < v.size(); idx += 10) {
std::cout << v[idx] << ' ';
}
std::cout << '\n';
return 0;
}