Pagini recente » Cod sursa (job #1054874) | Diferente pentru propuneri/6-arhiva-educationala intre reviziile 16 si 5 | Cod sursa (job #2911251) | Cod sursa (job #71273) | Cod sursa (job #2001436)
#include<bits/stdc++.h>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
const int NMAX = 1e7 + 5;
const int bits = 8;
int v[NMAX],aux[NMAX],f[1<<bits],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;
}
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 <= 4 ; ++i)
countSort(i);
}
void afis()
{
for(int i = 1 ; i <= N ; i += 10)
out<<v[i]<<" ";
}
int main()
{
read();
radixSort();
afis();
return 0;
}