Cod sursa(job #2618840)

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

int N, A, B, C;
int nums[NMAX];
int aux[NMAX], sliceStart[LMAX], cntByte[LMAX];

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++) {
		memset(cntByte, 0, sizeof(cntByte));
		for (int idx = 1; idx <= N; idx++) {
			int byteValue = getValue(nums[idx], byteIdx * 8, (byteIdx + 1) * 8);
			cntByte[byteValue]++;
		}
		sliceStart[0] = 1;
		for (int value = 1; value < LMAX; value++) {
			sliceStart[value] = sliceStart[value - 1] + cntByte[value - 1];
		}

		for (int idx = 1; idx <= N; idx++) {
			int byteValue = getValue(nums[idx], byteIdx * 8, (byteIdx + 1) * 8);
			aux[sliceStart[byteValue]++] = nums[idx];
		}

		copy(aux + 1, aux + N + 1, nums + 1);
	}

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