Pagini recente » Cod sursa (job #765315) | Cod sursa (job #2321703) | Cod sursa (job #3269576) | Cod sursa (job #2027380) | Cod sursa (job #1211981)
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
void read();
void generate();
void radix(vector<int> &V, int N);
void print();
int N,A,B,C;
vector<int> V;
int main()
{
read();
generate();
radix(V,N);
print();
return 0;
}
void read()
{
ifstream fin("radixsort.in");
fin>>N>>A>>B>>C;
}
void generate()
{
V.resize(N);
V[0] = B;
for(int i=1;i<N;i++)
{
V[i] = (1LL * A * V[i-1] + B) % C;
}
}
void radix(vector<int> &V, int N)
{
deque<int> bucket[2][256];
for(int i=0;i<N;i++)
{
bucket[0][V[i]&0x000000ff].push_back(V[i]);
}
for(int i=0;i<256;i++)
{
while(!bucket[0][i].empty())
{
int val = bucket[0][i].front();
bucket[1][(val&0x0000ff00) >> 8].push_back(val);
bucket[0][i].pop_front();
}
}
for(int i=0;i<256;i++)
{
while(!bucket[1][i].empty())
{
int val = bucket[1][i].front();
bucket[0][(val&0x00ff0000) >> 16].push_back(val);
bucket[1][i].pop_front();
}
}
for(int i=0;i<256;i++)
{
while(!bucket[0][i].empty())
{
int val = bucket[0][i].front();
bucket[1][(val&0xff000000) >> 24].push_back(val);
bucket[0][i].pop_front();
}
}
int k = 0;
for(int i=0;i<256;i++)
{
while(!bucket[1][i].empty())
{
V[k++] = bucket[1][i].front();
bucket[1][i].pop_front();
}
}
}
void print()
{
ofstream fout("radixsort.out");
for(int i=0;i<N;i+=10)
{
fout<<V[i]<<' ';
}
}