Pagini recente » Cod sursa (job #2209270) | Cod sursa (job #2251926) | Cod sursa (job #2286227) | Cod sursa (job #1072963) | Cod sursa (job #2205690)
#include <bits/stdc++.h>
using namespace std;
const int MAX=10000005;
const int bits=8,size=1<<bits,mask=size-1;
int N,A,B,C;
int v[MAX],aux[MAX];
void read();
void print();
int getMask(int,int);
void countSort(int[],int[],int);
void radixSort();
int main(){
read();
radixSort();
print();
return 0;
}
void read(){
ifstream f("radixsort.in");
f>>N>>A>>B>>C;
v[0]=B;
for(int i=1;i<N;++i)
v[i]=(1LL*A*v[i-1]+B)%C;}
void print(){
ofstream g("radixsort.out");
for(int i=0;i<N;i+=10)
g<<v[i]<<" ";
g<<"\n";}
int getMask(int x,int offset){
return (x>>offset)&mask;}
void countSort(int source[],int destination[],int offset){
int cnt[size],indx[size];
memset(cnt,0,sizeof cnt);
for(int i=0;i<N;++i)
++cnt[getMask(source[i],offset)];
indx[0]=0;
for(int i=1;i<size;++i)
indx[i]=cnt[i-1]+indx[i-1];
for(int i=0;i<N;++i)
destination[indx[getMask(source[i],offset)]++] = source[i];
}
void radixSort(){
for (int i=0;i*bits<32;++i)
if (i&1)
countSort(aux,v,i*bits);
else
countSort(v,aux,i*bits);}