Pagini recente » Cod sursa (job #216675) | Cod sursa (job #1085315) | Cod sursa (job #3250671) | Cod sursa (job #2751093) | Cod sursa (job #2549401)
// Stefan
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("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);
vector < int > aux((int) v.size());
for (int buck = 0; buck <= 31; buck += 8) {
for (auto &x : v) frecv[(x >> buck) & 255] += 1;
for (int i = 1; i <= 255; ++ i) frecv[i] += frecv[i - 1];
fill(aux.begin(), aux.end(), 0);
for (int i = (int) v.size() - 1; i >= 0; -- i) {
aux[-- frecv[(v[i] >> buck) & 255]] = v[i];
}
v = aux;
fill(frecv.begin(), frecv.end(), 0);
}
}
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;
fin >> 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) fout << v[i] << ' ';
fout << '\n';
}