Cod sursa(job #2868402)

Utilizator Mihai7218Bratu Mihai-Alexandru Mihai7218 Data 10 martie 2022 21:53:11
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int n, a, b, c, i;
int maxvect(vector <int> v)
{
	int mx = 0;
	for (int i = 0; i < v.size(); i++)
		mx = max(mx, v[i]);
	return mx;
}
void countSort(vector <int>& v, int digit)
{
	vector <int> count(10, 0);
	vector <int> output(v.size(), 0);
	for (int i = 0; i < v.size(); i++)
		count[(v[i] / digit) % 10]++;
	for (int i = 1; i < 10; i++)
		count[i] += count[i - 1];
	for (int i = v.size() - 1; i >= 0; i--)
	{
		output[count[(v[i] / digit) % 10] - 1] = v[i];
		count[(v[i] / digit) % 10]--;
	}
	for (int i = 0; i < v.size(); i++)
		v[i] = output[i];
}
void radixSort(vector <int>& v)
{
	int m = maxvect(v);
	for (int digit = 1; (m / digit) > 0; digit *= 10)
		countSort(v, digit);
}
vector <int> v;
int main()
{
	fin >> n >> a >> b >> c; v.resize(n + 1);
	v[0] = b;
	for (i = 1; i < n; i++)
		v[i] = (a * v[i - 1] + b) % c;
	radixSort(v);
	for (i = 1; i < n; i += 10)
		fout << v[i] << " ";
	return 0;
}