Cod sursa(job #2742282)

Utilizator muiepulicimatacutactu muiepulici Data 20 aprilie 2021 18:08:16
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>

#define BITS 4
#define BUCKETS (1 << BITS)
#define MASK ((1 << BITS) - 1)

void CountingSort(int* v, int n, int byte, int* temp) {
	int i;
	int count[BUCKETS] = { 0 };

	for (i = 0; i < n; ++i)
		++count[(v[i] >> (byte * BITS)) & MASK];

	for (i = 1; i < BUCKETS; ++i)
		count[i] += count[i - 1];

	for (i = n - 1; i >= 0; --i)
		temp[--count[(v[i] >> (byte * BITS)) & MASK]] = v[i];
}

void RadixSort(int* v, int n) {
	int i;
	int max = 0;

	for (i = 0; i < n; ++i) {
		if (v[i] > max)
			max = v[i];
	}

	int* temp = new int[n];

	for (i = 0; i < 8; ++i) {
		if (i % 2 == 0)
			CountingSort(v, n, i, temp);
		else
			CountingSort(temp, n, i, v);
	}

	delete[] temp;
}

int v[10000001];

int main() {
	std::ifstream fin("radixsort.in");
	std::ofstream fout("radixsort.out");

	int N, A, B, C;
	fin >> N >> A >> B >> C;

	fin.close();

	v[0] = B;

	int i;

	for (i = 1; i < N; ++i)
		v[i] = (1LL * A * v[i - 1] + B) % C;

	RadixSort(v, N);

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

	fout.close();

	return 0;
}