Cod sursa(job #1211981)

Utilizator vasile_pojogaPojoga Vasile vasile_pojoga Data 23 iulie 2014 16:43:16
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#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]<<' '; 
	}
}