Cod sursa(job #3124606)

Utilizator daristyleBejan Darius-Ramon daristyle Data 29 aprilie 2023 14:43:19
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

const int N_MAX = 1e7;
const int BIT_MAX = 30;
int v[N_MAX];

void RadixSort(int v[], int begin, int end, int bit) {//MSD
	if(end <= begin || bit < 0)
		return;

	int b = begin, e = end;
	while(b < end && (v[b] & (1 << bit)) == 0)
		++b;
	while(e > begin && (v[e] & (1 << bit)) > 0)
		--e;
	while(b <= e){
		int aux = v[b];
		v[b] = v[e];
		v[e] = aux;
		do
			++b;
		while(b < end && (v[b] & (1 << bit)) == 0);
		do
			--e;
		while(e > begin && (v[e] & (1 << bit)) > 0);
	}

	b = begin;
	while(b <= end && (v[b] & (1 << bit)) == 0)
		++b;

	RadixSort(v, begin, b - 1, bit - 1);
	RadixSort(v, b, end, bit - 1);
}

int main() {
	int n, b, c;
	long long a;
	fin >> n >> a >> b >> c;
	v[0] = b;
	a %= c;
	b %= c;
	for(int i = 1; i < n; ++i)
		v[i] = ((long long) a * v[i - 1] + b) % c;

	RadixSort(v, 0, n - 1, BIT_MAX);

	for(int i = 0; i < n; ++i)
		fout << v[i] << ' ';
	fout.put('\n');

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