Pagini recente » Cod sursa (job #1353243) | Cod sursa (job #2041122) | Monitorul de evaluare | Cod sursa (job #866439) | Cod sursa (job #2648795)
#include <iostream>
#include <fstream>
#define LL long long
using namespace std;
const long MAXN = 1e7+1;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
LL v[MAXN], n;
void count_sort(int pow){
long long output[n];
int i, count[10] = {0};
for (i = 0; i < n; i++)
count[(v[i]/pow)%10 ]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--){
output[count[(v[i]/pow)%10 ]-1] = v[i];
count[(v[i]/pow)%10]--;
}
for (i = 0; i < n; i++)
v[i] = output[i];
}
void radix_sort(LL maxi){
for(int pow = 1;maxi/pow>0;pow*=10)
count_sort(pow);
}
LL generate_num(LL a, LL b, LL c){
LL maxi = v[0] = b;
for(int i=1;i<n;i++){
v[i] = (a*v[i-1]+b)%c;
maxi = max(maxi, v[i]);
}
return maxi;
}
int main() {
LL a, b, c;
fin>>n>>a>>b>>c;
LL maxi = generate_num(a, b, c);
radix_sort(maxi);
for(int i=0;i<n;i+=10)
fout<<v[i]<<' ';
return 0;
}