Cod sursa(job #2654144)

Utilizator raikadoCri Lu raikado Data 29 septembrie 2020 21:31:04
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>

using namespace std;

void radixsort(vector<uint> &vect)
{
	vector<uint> temp(vect.size());
	vector<uint> buckets(256);

	for (uint round = 0, step = 0; round < sizeof(uint); round++, step += 8) {
		for (uint i = 0; i != buckets.size(); i++)
			buckets[i] = 0;

		for (auto v : vect) {
			buckets[(v >> step) & 255]++;
		}

		for (uint i = 1; i != buckets.size(); i++)
			buckets[i] += buckets[i-1];

		for (int i = vect.size()-1; i != -1; i--)
		{
			uint b = (vect[i] >> step) & 255;
			temp[--buckets[b]] = vect[i];
		}

		temp.swap(vect);
	}

}


int main(int argc, char const *argv[])
{
	ifstream fin("radixsort.in");
	ofstream fout("radixsort.out");

	unsigned long long N, A, B, C;
	fin >> N >> A >> B >> C;

	vector<uint> v;
	v.reserve(N);
	v.push_back(B);
	for (uint i = 1; i != N; i++)
	{
		v.push_back((((A * v[i-1]) % C + B) % C));
	}

	radixsort(v);
	for (uint i = 0; i != N; i += 10)
		fout << v[i] << ' ';

	return 0;
}