Pagini recente » Cod sursa (job #1792824) | Cod sursa (job #1782876) | Cod sursa (job #1042968) | Cod sursa (job #2103891) | Cod sursa (job #2608085)
#include <bits/stdc++.h>
using namespace std;
std::string RadixSort(std::vector<int>& v)
{
const int BASE = 10;
const int valMax = *std::max_element(v.begin(), v.end());
const int valMin = *std::min_element(v.begin(), v.end());
if (valMin < 0) {
return std::string("Negative values don't work with Radix Sort");
}
std::queue<int> q[2][BASE];
for( auto & x : v )
q[0][x % BASE].push(x);
int qind = 1, put = BASE;
while(valMax >= put) {
for( int i = 0; i < BASE; ++i ) {
while( !q[1 ^ qind][i].empty() ) {
int x = q[1 ^ qind][i].front();
/// std::cerr << x / put % BASE << ' ';
q[1 ^ qind][i].pop();
q[qind][x / put % BASE].push(x);
}
}
/// std::cerr << '\n';
if( valMax / put < BASE )
break;
put *= BASE;
qind ^= 1;
}
v.clear();
for( int i = 0; i < BASE; ++i )
while( !q[qind][i].empty() )
v.push_back(q[qind][i].front()),
q[qind][i].pop();
return "";
}
int main()
{
ifstream in("radixsort.in");
ofstream out("radixsort.out");
vector<int> v;
int N, a,b,c;
in >> N >> a >> b >> c;
v.push_back(b);
for (int i = 2; i <= N; ++i) {
v.push_back((v.back() * a + b) % c);
}
RadixSort(v);
for (int i = 0; i < (int)v.size(); i += 10){
out << v[i] << ' ';
}
return 0;
}