Pagini recente » Cod sursa (job #1832624) | Cod sursa (job #684396) | Cod sursa (job #1332324) | Cod sursa (job #1082576) | Cod sursa (job #2675367)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
typedef long long ll;
ll a, b, c;
int n;
void radixSort(vector<int> &v, int elMax = -1, int basePow = 8)
{
int base = 1 << basePow;
int mask = base - 1;
vector<int> aux(v.size()), cnt(base), start(base);
if(elMax == -1)
elMax = *max_element(v.begin(), v.end());
int sh = 0;
int i = 0;
while((elMax >> sh) > 0)
{
vector<int> &currArr = (i % 2 == 0) ? v : aux;
vector<int> &nextArr = (i % 2 == 1) ? v : aux;
cnt.assign(base, 0);
for(int x : currArr)
cnt[(x >> sh) & mask]++;
start[0] = 0;
for(int i = 1; i < base; i++)
start[i] = start[i-1] + cnt[i-1];
for(int x : currArr)
{
int coef = (x >> sh) & mask;
nextArr[start[coef]++] = x;
}
sh += basePow;
i++;
}
if(i % 2 == 1)
v = aux;
}
int main()
{
fin >> n >> a >> b >> c;
vector<int> v(n);
int elMax = b;
v[0] = b;
for(int i = 1; i < n; i++)
{
v[i] = (a * v[i-1] + b) % c;
elMax = max(elMax, v[i]);
}
radixSort(v, elMax);
for(int i = 0; i < n; i += 10)
fout << v[i] << ' ';
return 0;
}