Cod sursa(job #1205701)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 7 iulie 2014 19:06:00
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
using namespace std;
void read(int& n, int& a, int& b, int& c)
{
	ifstream fin("radixsort.in");
	fin >> n >> a >> b >> c;
	fin.close();
}
void write(const vector<int>& v)
{
	ofstream fout("radixsort.out");
	for (int i = 0; i < v.size(); i += 10)
		fout << v[i] << ' ';
	fout << '\n';
	fout.close();
}
void count_sort(vector<int>& v, const int& mask, const int& rshift)
{
	const int kMaxValues = (1 << 8);
	int count[kMaxValues];
	fill(count, count+kMaxValues, 0);

	//Count how many elements belong to the bucket
	for (int i = 0; i < v.size(); ++i)
		++count[(v[i] & mask) >> rshift];
	//Count how many elements belong to buckets <= to this one
	for (int i = 1; i < kMaxValues; ++i)
		count[i] += count[i - 1];

	//So count of something retains the position where it should be inserted
	vector<int> a(v.size());
    for (int i = v.size() - 1; i >= 0; --i)
		a[--count[(v[i] & mask) >> rshift]] = v[i];
	v.swap(a);
}
void radix_sort(vector<int>& v)
{
	const int kIntChunks = 4;
	const int kByteSize = 8;
	int mask = 0;
	for (int i = 1; i <= kIntChunks; ++i)
	{
		mask = (1 << (i * kByteSize)) - mask - 1;
		count_sort(v, mask, (i - 1) * kByteSize);
	}
}
int main()
{
	int n = 0, a = 0, b = 0, c = 1;
	read(n, a, b, c);

	vector<int> v;
	v.push_back(b);
	for (int i = 1; i < n; ++i)
		v.push_back((1LL * a * v[i-1] + b) % c);

	radix_sort(v);

	write(v);
	return 0;
}