Pagini recente » Cod sursa (job #2761709) | Cod sursa (job #3253126) | Cod sursa (job #3167309) | Cod sursa (job #1212560) | Cod sursa (job #2549363)
// Stefan
#include <vector>
#include <fstream>
using namespace std;
ifstream cin("radixsort.in");
ofstream cout("radixsort.out");
void minSort(vector < int > &v) {
for (int i = 0; i < (int) v.size(); ++ i) {
for (int j = i + 1; j < (int) v.size(); ++ j) {
if (v[i] > v[j]) swap(v[i], v[j]);
}
}
}
void bubSort(vector < int > &v) {
bool sorted = false;
while (not sorted) {
sorted = true;
for (int i = 1; i < (int) v.size(); ++ i) {
if (v[i] < v[i - 1]) {
swap(v[i], v[i - 1]);
sorted = false;
}
}
}
}
void cntSort(vector < int > &v, int maxVal) {
vector < int > frecv(maxVal + 1);
for (auto x : v) {
++ frecv[x];
}
int index = 0;
for (int i = 0; i <= maxVal; ++ i) {
for (int j = 1; j <= frecv[i]; ++ j) {
v[index ++] = i;
}
}
}
void radixSort(vector < int > &v) {
vector < vector < int > > buckets(256);
for (int buck = 0; buck <= 31; buck += 8) {
for (auto &x : v) {
buckets[(x >> buck) & 255].push_back(x);
}
int index = 0;
for (auto &x : buckets) {
for (auto y : x) {
v[index ++] = y;
}
x.clear();
}
}
}
void radixSort2(vector < int > &v) {
vector < int > frecv(256);
for (int buck = 0; buck <= 31; buck += 8) {
for (auto &x : v) frecv[(x >> buck) & 255] += 1;
for (int i = 1; i < 256; ++ i) frecv[i] += frecv[i - 1];
vector < int > aux((int) v.size());
for (int i = (int) v.size() - 1; i >= 0; -- i) {
aux[frecv[(v[i] >> buck) & 255] -- - 1] = v[i];
}
v = aux;
}
}
int main() {
/* vector < int > v = {-3, 3, 2, 234, 13, 33, 8475, 784, 258, 18, 25, 2, 1, 29857}; */
/* vector < int > v = {-1, 13, -19234, -5, -29, 3, 2, 234, 33, 8475, 784, 258, 18, 25, 2, 1, 29857}; */
/* vector < int > v = {}; */
int n, a, b, c;
cin >> n >> a >> b >> c;
vector < int > v(n);
v[0] = b;
for (int i = 1; i < n; ++ i) {
v[i] = (1ll * a * v[i - 1] + b) % c;
}
/* minSort(v); */
/* bubSort(v); */
/* cntSort(v, 30000); */
radixSort2(v);
for (int i = 0; i < (int) v.size(); i += 10) cout << v[i] << ' ';
cout << '\n';
}