Cod sursa(job #1249921)

Utilizator fhandreiAndrei Hareza fhandrei Data 27 octombrie 2014 17:33:36
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
// FMI - Grupa 135 - Semigrupa 2 - Hareza Andrei
// Include
#include <fstream>
#include <vector>
using namespace std;

// Definitii
#define pb push_back

// Constante
const int sz = 10000001;
const int base = 0xFF;

// Functii
int getDigits(int num);

// Variabile
ifstream in("radixsort.in");
ofstream out("radixsort.out");

int num;
int A, B, C;
int maxNum;

int values[sz];
vector<int> radixSort[base];

// Main
int main()
{
	in >> num >> A >> B >> C;
	values[1] = maxNum = B;
	for(int i=2 ; i<=num ; ++i)
		maxNum = max(maxNum, values[i]=((A * values[i-1] + B) % C));
	
	for(int digit=1 ; digit<=maxNum ; digit*=base)
	{
		for(int i=1 ; i<=num ; ++i)
			radixSort[(values[i]/digit)%base].pb(values[i]);
		
		int currentPos = 0;
		for(int i=0 ; i<base ; ++i)
		{
			vector<int>::iterator it, end=radixSort[i].end();
			for(it=radixSort[i].begin() ; it!=end ; ++it)
				values[++currentPos] = *it;
			radixSort[i].clear();
		}
	}
	
	for(int i=1 ; i<=num ; i+=10)
		out << values[i] << ' ';
	
	out << '\n';
	
	in.close();
	out.close();
	return 0;
}