Cod sursa(job #3124603)

Utilizator daristyleBejan Darius-Ramon daristyle Data 29 aprilie 2023 14:41:32
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 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 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[(v[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)
		w[freq[(w[i] >> bits) & MASK]++] = v[i];

	for(int i = 0; i < n; ++i)
		v[i] = w[i];

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

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

	RadixSort(v, n, 0);

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

	return 0;
}