Cod sursa(job #2654181)

Utilizator raikadoCri Lu raikado Data 29 septembrie 2020 23:30:35
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
	
#include <array>
	
 
	
using namespace std;
	
 
	
const int MAXN = 10000000;
	
 
	
// array<uint, MAXN> vect;
	
// array<uint, MAXN> temp;
	
uint buf1[MAXN];
	
uint buf2[MAXN];
	
 
	
uint* radixsort(uint N, uint *vect)
	
{	
	
	array<uint, 256> buckets;
	
	uint *temp = buf2;
	
 
	
	for (uint round = 0, step = 0; round < sizeof(uint); round++, step += 8) {
	
		buckets.fill(0);
	
 
	
		for (uint i = 0; i < N; i++)
	
			buckets[(vect[i] >> step) & 255]++;
	
 
	
		for (uint i = 1; i < buckets.size(); i++)
	
			buckets[i] += buckets[i-1];
	
 
	
		for (int i = N-1; i != -1; i--)
	
		{
	
			uint b = (vect[i] >> step) & 255;
	
			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;
	
}