Pagini recente » Cod sursa (job #1070035) | Cod sursa (job #2269158) | Istoria paginii runda/oni_2012_ziua1_clasele_xi-xii | Cod sursa (job #1035191) | Cod sursa (job #1243507)
#include<fstream>
#include<deque>
using namespace std;
ifstream fi("radixsort.in");
ofstream fo("radixsort.out");
const int MAX_N = 10000007;
int i,n,a,b,c;
int v[MAX_N];
void radix_sort(int v[MAX_N], int n){
deque <int> bucket[2][256];
int i;
for(i=1;i<=n;i++)
bucket[0][v[i]&((1<<8)-1)].push_back(v[i]);
for(i=0;i<256;i++)
while(!bucket[0][i].empty())
{
int &ref=bucket[0][i].front();
bucket[1][ref&((1<<16)-1)>>8].push_back(ref);
bucket[0][i].pop_front();
}
for(i=0;i<256;i++)
while(!bucket[1][i].empty())
{
int &ref=bucket[1][i].front();
bucket[0][ref&((1<<24)-1)>>16].push_back(ref);
bucket[1][i].pop_front();
}
for(i=0;i<256;i++)
while(!bucket[0][i].empty())
{
int &ref=bucket[0][i].front();
bucket[1][ref&(1LL<<32-1)>>24].push_back(ref);
bucket[0][i].pop_front();
}
int nr=0;
for(i=0;i<256;i++)
while(!bucket[1][i].empty())
{
v[++nr]=bucket[1][i].front();
bucket[1][i].pop_front();
}
}
int main(){
fi>>n>>a>>b>>c;
v[1]=b;
for(i=2;i<=n;i++)
v[i]=(a*v[i-1]+b)%c;
radix_sort(v,n);
for(i=1;i<=n;i+=10)
fo<<v[i]<<' ';
fi.close();
fo.close();
return 0;
}