Pagini recente » Cod sursa (job #456052) | Cod sursa (job #2561666) | Cod sursa (job #709750) | Cod sursa (job #241874) | Cod sursa (job #2001443)
#include<bits/stdc++.h>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
const int NMAX = 1e7 + 5;
const int bits = 16;
int v[NMAX],aux[NMAX],f[1<<bits + 5],N,A,B,C;
void read()
{
in>>N>>A>>B>>C;
v[1] = B;
for(int i = 2 ; i <= N ; ++i)
v[i] = (1LL*A*v[i-1] + 1LL*B)%C;
}
int get_bucket(int num,int nr)
{
return ((((1 << bits) - 1) << (bits*(nr-1))) & num) >> (bits*(nr-1));
}
void countSort(int bucket)
{
for(int i = 0 ; i < 1 << bits ; ++i)
f[i] = 0;
for(int i = 1 ; i <= N ; ++i)
f[get_bucket(v[i],bucket)] ++;
for(int i = 1 ; i < 1 << bits ; ++i)
f[i] += f[i-1];
for(int i = N ; i > 0 ; --i){
aux[f[get_bucket(v[i],bucket)]] = v[i];
f[get_bucket(v[i],bucket)] --;
}
for(int i = 1 ; i <= N ; ++i)
v[i] = aux[i];
}
void radixSort()
{
for(int i = 1 ; i <= 2 ; ++i)
countSort(i);
}
void afis()
{
for(int i = 1 ; i <= N ; i += 10)
out<<v[i]<<" ";
}
int main()
{
read();
radixSort();
afis();
return 0;
}