Mai intai trebuie sa te autentifici.
Cod sursa(job #2013649)
Utilizator | Data | 21 august 2017 23:03:54 | |
---|---|---|---|
Problema | Radix Sort | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.02 kb |
#include <bits/stdc++.h>
using namespace std;
#define LMAX 10000005
/// Aleg baza 256
#define bits 8
int v[LMAX],aux[LMAX],Max=0;
inline int GetBucket(int x,int poz){
return ((((1<<bits)-1)<<(bits*(poz-1)))&x)>>(bits*(poz-1));
}
inline void CountSort(int *v,int n,int poz){
int count[1<<bits]={0};
for(int i=1;i<=n;++i)
++count[GetBucket(v[i],poz)];
for(int i=1;i<(1<<bits);++i)
count[i]+=count[i-1];
for(int i=n;i;--i)
aux[count[GetBucket(v[i],poz)]--]=v[i];
for(int i=1;i<=n;++i)
v[i]=aux[i];
}
inline void RadixSort(int *v,int n){
for(int i=1;i<=4;++i)
CountSort(v,n,i);
}
int main(){
freopen("radixsort.in","r",stdin);
freopen("radixsort.out","w",stdout);
int n,a,b,c;
scanf("%d %d %d %d",&n,&a,&b,&c);
for(int i=1;i<=n;++i){
v[i]=(a*v[i-1]+b)%c;
if(v[i]>Max) Max=v[i];
}
RadixSort(v,n);
for(int i=1;i<=n;i+=10)
printf("%d ",v[i]);
fclose(stdin);fclose(stdout);
return 0;
}