Cod sursa(job #2586834)

Utilizator DawlauAndrei Blahovici Dawlau Data 21 martie 2020 17:04:38
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

const int bucket = 255; // 2^8 - 1

inline int getByte(const int &no, const int &byte) {

	return ((no >> (8 * byte)) & bucket);
}

inline void byteSort(vector <int> &Arr, vector <int> &aux, const int &byte) {

	vector <int> counter(1 + bucket);
	vector <int> index(1 + bucket);

	for (int idx = 0; idx < (int)Arr.size(); ++idx)
		++counter[getByte(Arr[idx], byte)];

	for (int val = 1; val <= bucket; ++val)
		index[val] = index[val - 1] + counter[val - 1]; // cu val - 1 in loc de val algoritmul devine stable

	for (int idx = 0; idx < (int)Arr.size(); ++idx)
		aux[index[getByte(Arr[idx], byte)]++] = Arr[idx]; // functioneaza pt ca e indexat de la 0
}

inline void RadixSort(vector <int> &Arr) {

	vector <int> aux((int)Arr.size());
	for (int byte = 0; byte < 4; ++byte) // int are 4 bytes
		if(byte % 2 == 0)
			byteSort(Arr, aux, byte); // sortez dupa byte-ul byte
		else byteSort(aux, Arr, byte);
}

int main() {

	int n, a, b, c;
	fin >> n >> a >> b >> c;

	vector <int> Arr(n);

	Arr[0] = b;
	for (int idx = 1; idx < n; ++idx)
		Arr[idx] = (1LL * a * Arr[idx - 1] + b) % c;

	//sort(Arr.begin(), Arr.end());
	RadixSort(Arr);

	for (int idx = 0; idx < n; idx += 10)
		fout << Arr[idx] << ' ';
}