Pagini recente » Rating Tsveta (Tsveta) | Cod sursa (job #530815) | Cod sursa (job #2562584) | Cod sursa (job #1166491) | Cod sursa (job #2244645)
#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>
using LL = long long;
using ULL = int long long;
const std::string _problemName = "radixsort";
namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}
#define USE_FILES
#ifdef USE_FILES
#define cin fin
#define cout fout
#endif
const int RADIX_COUNT = 4;
const int RADIX = 0xFF;
const int RADIX_NR_BITS = 8;
struct RadixSorter {
void radixsort(std::vector<int>& v) {
resize(v.size());
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<int>& from, std::vector<int>& to, int radixIdx) {
for (int fromIdx = 0; fromIdx < size_; ++fromIdx) {
int radix = getRadix(from[fromIdx], radixIdx);
++buckets_[radix];
}
index_[0] = 0;
for (int bucketIdx = 1; bucketIdx < (1 << RADIX_NR_BITS); ++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);
to[index_[radix]] = value;
++index_[radix];
}
}
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<int> aux_;
int buckets_[1 << RADIX_NR_BITS];
int index_ [1 << RADIX_NR_BITS];
};
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((a * v[i - 1] + b) % c);
}
RadixSorter().radixsort(v);
for (int idx = 0; idx < v.size(); idx += 10) {
std::cout << v[idx] << ' ';
}
std::cout << '\n';
return 0;
}