Cod sursa(job #2529418)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 23 ianuarie 2020 14:18:10
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

int n, a, b, c, y;
long long e;
vector <int> v;

void sort_frecv()
{
	vector <int> d[10];
	
	for (size_t i = 0; i < v.size(); ++i)
		d[(v[i] / e) % 10].push_back(v[i]);
	
	int cnt = 0;

	for (int i = 0; i < 10; ++i)
		for (size_t j = 0; j < d[i].size(); ++j)
			v[cnt++] = d[i][j];
}

void radix_sort()
{
	e = 1;
	while (e < c)
	{
		sort_frecv();
		e *= 10;
	}
}

int main()
{
	fin >> n >> a >> b >> c;

	v.resize(n);
	v[0] = b;
	
	for (int i = 1; i < n; ++i)
		v[i] = (1LL * a * v[i - 1] + b) % c;

	radix_sort();

	for (size_t i = 0; i < n; i += 10)
		fout << v[i] << " ";

	return 0;
}