Cod sursa(job #3203444)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 13 februarie 2024 17:56:42
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 666013;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

const int nmax = 1e7;
ll n, a, b, c;
int v[nmax + 5]{ 0 };
vector<int> w[10];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	fin >> n >> a >> b >> c;
	v[1] = b;
	for (int i = 2; i <= n; ++i) {
		v[i] = (a * v[i - 1] + b) % c;
	}
	ll p = 1;
	while (true) {
		for (int i = 1; i <= n; ++i) {
			w[(v[i] / p) % 10].push_back(v[i]);
		}
		if (w[0].size() == n) {
			w[0].clear();
			break;
		}
		int k = 0;
		for (int i = 0; i < 10; ++i) {
			for (auto& x : w[i]) {
				v[++k] = x;
			}
			w[i].clear();
		}
		p *= 10;
	}
	for (int i = 1; i <= n; i += 10) {
		fout << v[i] << sp;
	}
	fout << nl;
}