Cod sursa(job #2410070)

Utilizator LucaSeriSeritan Luca LucaSeri Data 19 aprilie 2019 18:20:48
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

int getByte(int x, int i) {
	return (x>>(8*i))&0xffff;
}

const int MAXN = 1e7 + 10;
queue< int > radix[65536];
int v[MAXN];

int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);
	#else
		freopen("radixsort.in", "r", stdin);
		freopen("radixsort.out", "w", stdout);
	#endif

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	int n, a, b, c;
	cin >> n >> a >> b >> c;

	v[1] = b;
	for(int i = 2; i <= n; ++i) {
		v[i] = (1ll*a*v[i-1] + 1ll*b) % c;
	}

	for(int i = 0; i < 2; ++i) {
		for(int j = 1; j <= n; ++j) {
			radix[getByte(v[j], i)].push(v[j]);
		}

		int ind = 0;
		for(int j = 0; j < 65536; ++j) {
			while(radix[j].size()) {
				v[++ind] = radix[j].front();
				radix[j].pop();
			}
		}


		assert(ind == n);
	}

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