Cod sursa(job #2222794)

Utilizator AlexDabuDabu Alexandru AlexDabu Data 18 iulie 2018 01:16:59
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>

#define NMAX 10000002

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

int n, a, b, c;
int numberList[NMAX], semiSorted[NMAX];
int largestNum = 0;

void Read(void)
{
	fin >> n >> a >> b >> c;
	numberList[1] = b % c;
	for (int i = 2; i <= n; i++)
	{
		numberList[i] = (1LL * a * numberList[i - 1] % c + b) % c;
	}
}

void RadixSort(void)
{
	for (int p = 0; p < 32; p += 8) 
	{
		int prop[256] = { 0 };
		for (int i = 1; i <= n; i++)
		{
			prop[(numberList[i] >> p) % 256]++;
		}
		for (int i = 1; i < 256; i++)
		{
			prop[i] += prop[i - 1];
		}
		for (int i = n; i >= 1; i--) 
		{
			semiSorted[prop[(numberList[i] >> p) % 256]--] = numberList[i];
		}
		for (int i = 1; i <= n; i++)
		{
			numberList[i] = semiSorted[i];
		}
	}
}

void Print(void)
{
	for (int i = 1; i <= n; i += 10)
	{
		fout << numberList[i] << ' ';
	}
}

int main(void)
{
	Read();
	RadixSort();
	Print();
	return 0;
}