Cod sursa(job #2654322)

Utilizator raikadoCri Lu raikado Data 30 septembrie 2020 15:21:01
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <array>

using namespace std;

const uint MAXN = 10000000;
const uint USED_BITS = 31;
const uint RADIX_BITS = 11;
const uint RADIX = 1 << RADIX_BITS;

uint buf1[MAXN];
uint buf2[MAXN];
uint buckets[RADIX];

uint* radixsort(uint N, uint *vect)
{	
	uint *temp = buf2;

	for (uint step = 0; step < USED_BITS; step += RADIX_BITS) {
		for (uint i = 0; i < RADIX; ++i)
			buckets[i] = 0;

		for (uint i = 0; i < N; ++i)
			++buckets[(vect[i] >> step) & (RADIX-1)];

		for (uint i = 1; i < RADIX; ++i)
			buckets[i] += buckets[i-1];

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

		swap(vect, temp);
	}

	return 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;

	buf1[0] = B;
	for (uint i = 1; i < N; i++)
	{
		buf1[i] = (((A * buf1[i-1]) % C + B) % C);
	}

	uint* vect = radixsort(N, buf1);
	for (uint i = 0; i < N; i += 10)
		fout << vect[i] << ' ';

	return 0;
}