Cod sursa(job #2190154)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 29 martie 2018 21:20:23
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <array>
#include <queue>

std::ifstream f("radixsort.in");
std::ofstream g("radixsort.out");

int N, A, B, C;

std::array<int, 10000005> nums;

void Generate()
{
	nums[0] = B;

	for (int i = 1; i < N; ++i) {
		nums[i] = (A * nums[i - 1] + B) % C;
	}
}

void Sort()
{
	constexpr int radix  = 10;
	constexpr int digits = 10;

	int i, j, factor;

	std::queue<int> q[radix];

	for (i = 0, factor = 1; i < digits; ++i, factor *= radix) {
		for (j = 0; j < N; ++j) {
			q[(nums[j] / factor) % radix].emplace(nums[j]);
		}
		
		int k = 0;

		for (int l = 0; l < radix; ++l) 
			while (!q[l].empty()) {
				nums[k] = q[l].front();
				q[l].pop();
				++k;
			}
			
	}
}

void Print()
{
	for (int i = 0; i < N; i = i + 10) {
		g << nums[i] << ' ';
	}
}

int main(int, char *[])
{
	f >> N >> A >> B >> C;
	
	Generate();
	Sort();
	Print();

	return 0;
}