Cod sursa(job #1250059)

Utilizator fhandreiAndrei Hareza fhandrei Data 27 octombrie 2014 19:41:22
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
// FMI - Grupa 135 - Semigrupa 2 - Hareza Andrei
// Include
#include <fstream>
#include <cstring>
using namespace std;

// Constante
const int sz = 1001;
const int base = 0x100;
const int byte = 0xFF;

// Functii
int getDigits(int num);

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

int num;
int A, B, C;

int _values[sz], _tempValues[sz];
int *values=_values, *tempValues=_tempValues;
int counter[base];
int pos[base];

// Main
int main()
{
	in >> num >> A >> B >> C;
	values[1] = B%C;
	for(int i=2 ; i<=num ; ++i)
		values[i] = (1LL * A * values[i-1] % C + B) % C;
	
	for(int power=0 ; power!=32 ; power+=8)
	{
		memset(counter, 0, sizeof(counter));
		for(int i=1 ; i<=num ; ++i)
			++counter[(values[i]>>power)&byte];
		
		pos[0] = 1;
		for(int i=1 ; i<base ; ++i)
			pos[i] = pos[i-1] + counter[i-1];
		
		for(int i=1 ; i<=num ; ++i)
			tempValues[pos[(values[i]>>power)&byte]++] = values[i];
		swap(values, tempValues);
	}
	
	for(int i=1 ; i<=num ; i+=10)
		out << values[i] << ' ';
	
	out << '\n';
	
	in.close();
	out.close();
	return 0;
}