Cod sursa(job #2873244)

Utilizator matthriscuMatt . matthriscu Data 18 martie 2022 22:43:51
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>

#define BYTE_SIZE 8
#define NMAX 10000000

using namespace std;

unsigned char get_nth_byte(int x, unsigned int n)
{
	return (x >> n * BYTE_SIZE) & (char)-1;
}

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

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

	vector<vector<int>> v(2, vector<int>(N));
	bool current = 0;
	v[0][0] = B;

	for (int i = 1; i < N; ++i)
		v[0][i] = (1LL * A * v[0][i - 1] + B) % C;
	
	for (int byte = 0; byte < sizeof(int); ++byte) {
		vector<int> cnt(1 << BYTE_SIZE, 0), index(1 << BYTE_SIZE);

		for (int i = 0; i < N; ++i)
			++cnt[get_nth_byte(v[current][i], byte)];

		index[0] = 0;

		for (int i = 1; i < (1 << BYTE_SIZE); ++i)
			index[i] = index[i - 1] + cnt[i - 1];

		for (int i = 0; i < N; ++i)
			v[1 - current][index[get_nth_byte(v[current][i], byte)]++] = v[current][i];

		current = 1 - current;
	}

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

	fin.close();
	fout.close();
	return 0;
}