Cod sursa(job #3124679)

Utilizator daristyleBejan Darius-Ramon daristyle Data 29 aprilie 2023 19:55:49
Problema Radix Sort Scor 100
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 MAX_BITS = 32;
const int BITS_PER_STEP = 8;
const int BASE = (1 << BITS_PER_STEP);
const int MASK = BASE - 1;
const int NO_BUCKETS = BASE;
int w[N_MAX], v[N_MAX];
int freq[NO_BUCKETS];

void RadixSort(int w[], int v[], int n, int bits) {//LSD
	if(bits >= MAX_BITS)
		return;

	for(int i = 0; i < NO_BUCKETS; ++i)
		freq[i] = 0;
	for(int i = 0; i < n; ++i)
		++freq[(w[i] >> bits) & MASK];
	int start = 0, aux;
	for(int i = 0; i < NO_BUCKETS; ++i){
		aux = freq[i];
		freq[i] = start;
		start += aux;
	}

	for(int i = 0; i < n; ++i)
		v[freq[(w[i] >> bits) & MASK]++] = w[i];

	RadixSort(v, w, n, bits + BITS_PER_STEP);
}

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

	RadixSort(w, v, n, 0);

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

	return 0;
}