Cod sursa(job #3134563)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 29 mai 2023 16:40:54
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 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> q[10];

	int max_elem = *max_element(v.begin(), v.end());
	for (int p = 1; p <= max_elem; p *= 10) {
		for (int x : v)
			q[(x / p) % 10].push_back(x);

		for (int cif = 0, index = 0; cif < 10; ++cif)
			for (int x : q[cif])
				v[index++] = x;

		for (int cif = 0; cif < 10; ++cif) {
			q[cif].clear();
			q[cif].reserve(v.size() / 10);
		}
	}
}

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);

	// #ifndef ONLINE_JUDGE
    // freopen("input.in", "r", stdin);
    // freopen("output.out", "w", stdout);
    // #endif

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

	return 0;
}