Cod sursa(job #2778612)

Utilizator radu.z5Zamfirescu Radu Ioan radu.z5 Data 1 octombrie 2021 20:42:14
Problema Radix Sort Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#include <inttypes.h>

using namespace std;

#define FULL_BYTE (uint32_t) 0x000000ff

void radixsort(vector<uint32_t> &v) {
	size_t n = v.size();
	uint32_t *bucket = new uint32_t[n];
	uint32_t count[FULL_BYTE + 1];

	size_t i, j;
	for (i = 0; i <= FULL_BYTE; i++)
		count[i] = 0;

	for (j = 0; j < 32; j += 8) {
		for (i = 0; i < n; i++) {
			uint32_t key = (v[i] >> j) & FULL_BYTE;
			count[key]++;
		}

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

		// se face parcurgerea de la dreapta la stanga, ca sa pun in bucket mai
		// intai numerele mai mari (dpdv al octetului curent) pe indici mai
		// mari
		for (long k = n - 1; k >= 0; --k) {
			uint32_t key = (v[k] >> j) & FULL_BYTE;
			// iar aici daca se intampla sa fie un numar w cu aceeasi cheie, va
			// fi pus pe o pozitie mai mica; cel pus inaintea lui w era mai in
			// dreapta in vector, deci mai mare dpdv al octetilor mai putini
			// semnificativi decat cel de la pasul curent
			bucket[--count[key]] = v[k];
		}

		for (i = 0; i <= FULL_BYTE; i++)
			count[i] = 0;

		for (i = 0; i < n; i++)
			v[i] = bucket[i];
	}
	delete[] bucket;
}

int main(void) {
	ifstream in("radixsort.in");
	ofstream out("radixsort.out");

	uint32_t n, a, b, c, i;
	in >> n >> a >> b >> c;
	vector<uint32_t> v(n);

	v[0] = b;
	for (i = 1; i < n; i++)
		v[i] = (uint32_t) ((1UL * a * v[i - 1] + b * 1UL) % c);

	radixsort(v);

	for (i = 0; i < n; i += 10)
		out << v[i] << ' ';

	in.close();
	out.close();
	return 0;
}