Cod sursa(job #1446841)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 2 iunie 2015 23:15:23
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <list>
#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
typedef unsigned long long ULL;
typedef unsigned int uint;

uint v[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);
	}
}

void radixSort(uint base) {
	vector< list<uint> > buckets(base);
	uint alreadySorted = 0;
	uint p = 1;
	uint moreSorted = 0;
	do {
		moreSorted = 0;
		if (!p)
			return;
		for (uint i = alreadySorted; i < N; i++) {
			uint tmp = v[i] / p;
			if (!tmp)
				v[alreadySorted + (moreSorted++)] = v[i];
			else {
				tmp %= base;
				buckets[tmp].push_back(v[i]);
			}
		}
		alreadySorted += moreSorted;
		int curIndex = alreadySorted;
		for (auto i = buckets.begin(); i != buckets.end(); ++i)
		for (auto j = i->begin(); j != i->end(); j = i->erase(j))
			v[curIndex++] = *j;
		p *= base;
	} while (moreSorted);
}

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