Cod sursa(job #2855692)

Utilizator cristia_razvanCristia Razvan cristia_razvan Data 22 februarie 2022 19:40:03
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define dbg(i) (cout<<#i<<" = "<<(i)<<'\n')

using ll = long long;
using ui = unsigned int;


const string fn = "radixsort";

ifstream fin(fn + ".in");
ofstream fout(fn + ".out");


int n, A, B, C;
int a[10000001], b[10000001];
int fr[256];
int main() {

	fin >> n;
	fin >> A >> B >> C;
	a[1] = B;
	for (int i = 2; i <= n; ++i)
		a[i] = (1LL * A * a[i - 1] + B) % C;
	for (int i = 0; i < 32; i += 8) {
		for (int j = 1; j <= n; ++j) {
			fr[(a[j] >> i) & 255]++;
		}
		for (int j = 1; j <= 255; ++j)
			fr[j] += fr[j - 1];
		///
		for (int j = 1; j <= n; ++j)
			b[fr[a[j]]--] = a[j];
		/// sau de la coada
		for (int j = 1; j <= n; ++j)
			a[j] = b[j];
		for (int j = 0; j < 256; ++j)
			fr[j] = 0;
	}

	for (int i = 1; i <= n; i += 10)
		fout << a[i] << " ";

	fin.close();
	fout.close();
	return 0;
}