Cod sursa(job #3134571)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 29 mai 2023 17:07:46
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

void radixsort(vector<int> &v) {
	vector<int> nr(10), pos(10);
	vector<int> aux(v.size());

	for (int p = 1, even = 0; p <= 1e9; p *= 10, even ^= 1) {
		fill(nr.begin(), nr.end(), 0);

		if (even)
			for (int x : aux)
				++nr[(x / p) % 10];
		else
			for (int x : v)
				++nr[(x / p) % 10];

		pos[0] = 0;
		for (int cif = 1; cif < 10; ++cif)
			nr[cif] += nr[cif - 1], pos[cif] = nr[cif - 1];

		if (even)
			for (int x : aux)
				v[pos[(x / p) % 10]++] = x;
		else
			for (int x : v)
				aux[pos[(x / p) % 10]++] = x;
	}
}

void solve()
{
	int n, a, b, c;
	cin >> n >> a >> b >> c;

	vector<int> v(n);

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

	radixsort(v);

	for (int i = 0; i < n; i += 10)
		cout << v[i] << ' ';
	cout << '\n';
}

int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);

	int t = 1;
	// cin >> t;
	while(t--)
		solve();

	return 0;
}