Cod sursa(job #1446869)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 3 iunie 2015 00:52:57
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
#define _submit
#ifdef _submit
#define InFile "radixsort.in"
#define OtFile "radixsort.out"
#else
#define InFile "fis.in"
#define OtFile "fis.out"
#endif

#define MAXN 10000010
//#define MAXN 11
#define BMAX 256
typedef unsigned long long ULL;
typedef unsigned int uint;

uint v[MAXN], counts[BMAX], alput[BMAX], cv[MAXN];
uint N, A, B, C;

void makeVect() {
	v[0] = B;
	for (uint i = 1; i < N; i++) {
		ULL tmp = ULL(A)*ULL(v[i - 1]) + ULL(B);
		tmp %= ULL(C);
		v[i] = uint(tmp);
	}
}

uint* radixSort(uint pow2) {
	uint base = (1 << pow2) - 1;
	uint p = 0;
	bool found = true;
	uint *vect = cv, *vectcp = v;
	do {
		for (uint i = 0; i < BMAX; i++)
			counts[i] = alput[i] = 0;
		found = false;
		for (uint i = 0; i < N; i++) {
			uint tmp = vectcp[i] >> p;
			if (tmp)
				found = true;
			tmp &= base;
			counts[tmp]++;
		}
		for (uint i = 1; i < BMAX; i++)
			counts[i] += counts[i - 1];
		for (uint i = 0; i < N; i++) {
			uint tmp = vectcp[i] >> p;
			if (tmp)
				found = true;
			tmp &= base;
			uint before = (tmp) ? counts[tmp - 1] : 0;
			vect[before + (alput[tmp]++)] = vectcp[i];
		}
		uint* aux = vect;
		vect = vectcp;
		vectcp = aux;
		p += pow2;
	} while (found);
	return vectcp;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OtFile, "w", stdout));
	scanf("%u%u%u%u", &N, &A, &B, &C);
	makeVect();
	uint* toPrint = radixSort(8);
	for (uint i = 0; i < N; i += 10)// 10)
		printf("%d ", toPrint[i]);
	return 0;
}