Cod sursa(job #2037948)

Utilizator robuvedVictor Robu robuved Data 12 octombrie 2017 23:31:19
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");

typedef unsigned int uint;
uint GetByte(uint x, uint p)
{
	uint byte = (x >> (8 * p)) & 0xFF;
	return byte;
}
void SortByByte(vector<uint>& v, vector<uint>& temp, uint byte)
{
	uint count[256]{0};
	for (auto it = v.begin(); it != v.end(); it++)
	{
		count[GetByte(*it, byte)]++;
	}
	for (uint i = 1; i < 256; i++)
	{
		count[i] += count[i - 1];
	}
	for (auto it = v.rbegin(); it != v.rend(); it++)
	{
		temp[--count[GetByte(*it, byte)]] = *it;
	}
}
void RadixSort(vector<uint> & v)
{
	vector<uint> temp(v.size());
	for (uint i = 0; i < 4; i++)
	{
		if (i % 2)
			SortByByte(temp, v, i);
		else
			SortByByte(v, temp, i);
	}
}
int main()
{
	uint N, A, B, C;
	in >> N >> A >> B >> C;
	vector<uint> v(N, 0);
	v[0] = B % C;
	for (int i = 1; i < N; i++)
	{
		v[i] = (((unsigned long long)A * v[i - 1]) % C + B) % C;
	}
	RadixSort(v);
	for (int i = 0; i < N; i+= 10)
	{
		out << v[i] << ' ';
	}
}