Cod sursa(job #3213977)

Utilizator tomaionutIDorando tomaionut Data 13 martie 2024 17:28:27
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
 
using namespace std;

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

int n, A, B, C, a[10000005], b[10000005], fr[10];

void RADIX_SORT()
{
	int r = 1e9, i, p = 1;
	while (p <= r)
	{
		for (i = 0; i <= 9; i++)
			fr[i] = 0;

		for (i = 1; i <= n; i++)
			fr[a[i] / p % 10]++;

		for (i = 1; i <= 9; i++)
			fr[i] += fr[i - 1];

		for (i = n; i >= 1; i--)
		{
			b[fr[a[i] / p % 10]] = a[i];
			fr[a[i] / p % 10]--;
		}

		for (i = 1; i <= n; i++)
			a[i] = b[i];

		p *= 10;
	}
}

int main()
{
	fin >> n >> A >> B >> C;
	a[1] = B;
	for (int i = 2; i <= n; i++)
		a[i] = (1ll * A * a[i - 1] + B) % C;
	RADIX_SORT();
	for (int i = 1; i <= n; i += 10)
		fout << a[i] << " ";

	return 0;
}