Cod sursa(job #2485002)

Utilizator remus88Neatu Remus Mihai remus88 Data 31 octombrie 2019 21:11:10
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
#include <iostream>

void countingSort(std::vector<int>& arr, int power, int base) {
	std::vector<int> count(base);

	for (auto x : arr) {
		++count[(x / power) % base];
	}
	
	for (int i = 1; i < base; ++i) {
		count[i] += count[i - 1];
	}

	std::vector<int> output(arr.size());

	for (int i = arr.size() - 1; i >= 0; --i) {
		output[count[(arr[i] / power) % 10] - 1] = arr[i];
		--count[(arr[i] / power) % 10];
	}

	for (int i = 0; i < arr.size(); ++i) {
		arr[i] = output[i];
	}
}

void radixSort(std::vector<int>& arr, int base) {
	int maxn = arr[0];
	for (auto x : arr) {
		if (maxn < x) {
			maxn = x;
		}
	}

	for (int power = 1; power <= maxn; power *= 10) {
		countingSort(arr, power, base);
	}
}

int main() {
	std::ifstream in("radixsort.in");
	std::ofstream out("radixsort.out");

	int n, a, b, c;
	in >> n >> a >> b >> c;

	std::vector<int> arr;
	arr.push_back(b);
	
	for (int i = 1; i < n; ++i) {
		arr.push_back(1LL * (a * arr[i - 1] + b) % c);
	}

	radixSort(arr, 10);

	for (int i = 0; i < n; i += 10) {
		out << arr[i] << ' ';
	}

	return 0;
}