Pagini recente » Cod sursa (job #2922522) | Cod sursa (job #428255) | Cod sursa (job #2929522) | Cod sursa (job #2238027) | Cod sursa (job #2972500)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T, size_t N>
void re(array <T, N>& x);
template <class T>
void re(vt <T>& x);
template <class T>
void re(T& x) {
cin >> x;
}
template <class T, class... M>
void re(T& x, M&... args) {
re(x); re(args...);
}
template <class T>
void re(vt <T>& x) {
for(auto& it : x)
re(it);
}
template <class T, size_t N>
void re(array <T, N>& x) {
for(auto& it : x)
re(it);
}
template <class T, size_t N>
void wr(array <T, N> x);
template <class T>
void wr(vt <T> x);
template <class T>
void wr(T x) {
cout << x;
}
template <class T, class ...M> void wr(T x, M... args) {
wr(x), wr(args...);
}
template <class T>
void wr(vt <T> x) {
for(auto it : x)
wr(it, ' ');
}
template <class T, size_t N>
void wr(array <T, N> x) {
for(auto it : x)
wr(it, ' ');
}
inline void Open(const string Name) {
#ifndef ONLINE_JUDGE
(void)!freopen((Name + ".in").c_str(), "r", stdin);
(void)!freopen((Name + ".out").c_str(), "w", stdout);
#endif
}
void solve() {
const int byte = 0xFF;
function <void(int b, vt <int>&, vt <int>&)> radix;
int n, a, b, c; re(n, a, b, c);
vt <int> v{b};
for (int i = 1; i < n; ++i) {
v.emb((1LL * a * v.back() + b) % c);
}
/* knowing that the numbers are integeres we will split them into 4 buckets of a byte
the main ideea of radix sort is that after sorting the numbers by all the buckets we will get a sorted array.
The reason radix sort works is because it takes advantage of the fact that sorting by the bytes
first is equivalent to sorting by the entire key, since the relative order of elements with different bytes
will be determined by the next byte. By repeating the process for byte, radix sort ensures that the final order of elements is correct.
*/
radix = [](int x, vt <int>& a, vt <int>& b) {
vt <int> cnt(byte + 1);
for (int i = 0; i < len(a); ++i)
++cnt[byte & (a[i] >> x * 8)];
vt <int> idx(byte + 1);
for (int i = 1; i <= byte; ++i)
idx[i] = idx[i - 1] + cnt[i - 1];
for (int i = 0; i < len(a); ++i)
b[idx[byte & (a[i] >> x * 8)]++] = a[i];
};
vt <int> tmp(n);
for (int i = 0; i < 4; ++i)
if (i % 2 == 0)
radix(i, v, tmp);
else
radix(i, tmp, v);
for (int i = 0; i < n; i += 10)
wr(v[i], ' ');
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Open("radixsort");
int t = 1;
for(;t;t--) {
solve();
}
return 0;
}