Cod sursa(job #1778134)

Utilizator BLz0rDospra Cristian BLz0r Data 13 octombrie 2016 15:26:11
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 10000002
#define Buckets 256

#ifdef INFOARENA
ifstream fin("radix.in");
ofstream fout("radix.out");
#else
#define fin cin
#define fout cout
#endif

int GetVal(int x, int bucket) {

	int st = 8 * bucket;
	int dr = st + 8 - 1;

	int nr = 0;
	for (int i = st, j = 0; i <= dr; ++i, ++j)
		if (x & (1 << i))
			nr ^= (1 << j);

	return nr;
}

vector<int> RadixSort(vector<int> V, int N, int step) {

	if (!step)
		return V;

	vector<int> SolV, Radix[Buckets];

	for (int i = 0; i < N; ++i)
		Radix[GetVal(V[i], step)].push_back(V[i]);

	for (int i = 0; i < Buckets; ++i)
		SolV.insert(SolV.end(), Radix[i].begin(), Radix[i].end());

	for (int i = 0; i < Buckets; ++i)
		if (Radix[i].size())
			RadixSort(Radix[i], Radix[i].size(), step - 1);

	return SolV;
}

vector<int> V, Sol;

int main(){

	int N, A, B, C;

	fin >> N >> A >> B >> C;

	V.resize(N);

	V[0] = B;

	for (int i = 1; i < N; ++i)
		V[i] = (1LL * V[i - 1] * A + B) % C;

#ifndef INFOARENA
	sort(V.begin(), V.end());
	for (int i = 0; i < N; ++i)
		fout << V[i] << " ";
	fout << "\n";
#endif

	Sol = RadixSort(V, N, 4);

	vector<int> ::iterator it;

	for (int i = 0; i < N; i += 10)
		fout << Sol[i] << " ";

	return 0;
}