Mai intai trebuie sa te autentifici.
Cod sursa(job #1552267)
Utilizator | Data | 17 decembrie 2015 17:07:00 | |
---|---|---|---|
Problema | Radix Sort | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.97 kb |
#include <bits/stdc++.h>
using namespace std;
const int mask = (1<<8)-1;
int v[10000005];
int va[10000005];
int q[mask+5];
int main()
{
int i,n,A,B,C,mm,c,cnt,m;
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
scanf("%d %d %d %d",&n,&A,&B,&C);
v[1] = B%C;
for(i = 2;i <= n;i++){
v[i] = (1LL*A*v[i-1]+B)%C;
}
for(int shift = 0;shift < 32;shift += 8){
for(i = 1;i <= n;i++){
int k = (v[i]>>shift)&mask;
q[k]++;
}
for(i = 1;i <= mask;i++){
q[i] += q[i-1];
}
for(i = n;i >= 1;i--){
int k = (v[i]>>shift)&mask;
va[q[k]] = v[i];
q[k]--;
}
for(i = 1;i <= n;i++){
v[i] = va[i];
}
for(i = 0;i < mask;i++){
q[i] = 0;
}
}
for(i = 1;i <= n;i += 10){
printf("%d ",v[i]);
}
return 0;
}