Pagini recente » Cod sursa (job #1404451) | Cod sursa (job #3231594) | Cod sursa (job #2908012) | Cod sursa (job #2977701) | Cod sursa (job #1227923)
#include <iostream>
using namespace std;
int n,a,b,c;
short int bucket[10000001][4];
short int B[10000001][4];
void fill_buckets(int k, int nr){
bucket[k][0] = nr % 1000;
bucket[k][1] = (nr % 1000000 - bucket[k][0]) / 1000;
bucket[k][2] = (nr % 1000000000 - bucket[k][1] * 1000 - bucket[k][0]) / 1000000;
bucket[k][3] = (nr - bucket[k][2] * 1000000 - bucket[k][1] * 1000 - bucket[k][0]) / 1000000000;
}
void create_buckets(){
int nr;
nr = b;
fill_buckets(0,nr);
for(int i = 1; i < n; i++){
nr = (int)(((long long)a * (long long)nr + (long long)b) % (long long)c);
fill_buckets(i,nr);
}
}
void counting_sort(int d){
int C[1001];
for(int i = 0; i < 1000; i++)
C[i] = 0;
for(int i = 0; i < n; i++)
C[bucket[i][d]]++;
for(int i = 1; i < 1000; i++)
C[i] += C[i - 1];
for(int i = n - 1; i >= 0; i--){
int j = bucket[i][d];
B[C[j] - 1][d] = j;
for(int k = 0; k < 4; k++)
if(k != d)
B[C[j] - 1][k] = bucket[i][k];
C[j] --;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < 4; j++)
bucket[i][j] = B[i][j];
}
void radix_sort(){
for(int i = 0; i < 4; i++){
counting_sort(i);
// cout<<i<<'\n';
}
}
int main(){
freopen("radixsort.in","r",stdin);
freopen("radixsort.out","w",stdout);
scanf("%d%d%d%d",&n,&a,&b,&c);
create_buckets();
radix_sort();
for(int i = 0; i < n; i += 10){
int nr = bucket[i][3] * 1000000000 + bucket[i][2] * 1000000 + bucket[i][1] * 1000 + bucket[i][0];
printf("%d ",nr);
}
return 0;
}