Cod sursa(job #2618838)

Utilizator radustn92Radu Stancu radustn92 Data 26 mai 2020 13:29:38
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <vector>
#include <fstream>
using namespace std;
const int NMAX = 10000505;
const int LMAX = (1 << 8);

int N, A, B, C;
int nums[NMAX];

inline int getValue(int& value, int from, int toExclusive) {
	long long temp = ((1LL << toExclusive) - 1) & value;
	return temp >> from;
}

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

	in >> N >> A >> B >> C;
	nums[1] = B;
	for (int idx = 2; idx <= N; idx++) {
		nums[idx] = (1LL * nums[idx - 1] * A + B) % C;
	}

	for (int byteIdx = 0; byteIdx < 4; byteIdx++) {
		vector<vector<int>> orderedByByte(LMAX, vector<int>());
		for (int idx = 1; idx <= N; idx++) {
			int byteValue = getValue(nums[idx], byteIdx * 8, (byteIdx + 1) * 8);
			orderedByByte[byteValue].push_back(nums[idx]);
		}

		int nextPos = 1;
		for (int value = 0; value < LMAX; value++) {
			for (auto& entry : orderedByByte[value]) {
				nums[nextPos++] = entry;
			}
		}
	}

	for (int idx = 1; idx <= N; idx += 10) {
		out << nums[idx] << " ";
	}
	out << "\n";
	return 0;
}