Cod sursa(job #2778174)

Utilizator radu.z5Zamfirescu Radu Ioan radu.z5 Data 29 septembrie 2021 19:06:10
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <algorithm>
#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();
    vector<uint32_t> bucket(n);
	vector<uint32_t> count(FULL_BYTE + 1, 0);
	size_t i, j;

	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];
		}

		fill(count.begin(), count.end(), 0);
		for (i = 0; i < n; i++)
			v[i] = bucket[i];
	}
}

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;
}