Cod sursa(job #2602284)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 16 aprilie 2020 16:14:38
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;

ifstream cin("radixsort.in");
ofstream cout("radixsort.out");

const int NMAX = 10000000;
const int BYTE = (1 << 8);

int N, A, B, C;
int v[NMAX + 2], aux[NMAX + 2];
int count[BYTE + 2];

int main()
{
	cin >> N >> A >> B >> C;

	v[1] = B;
	for(int i = 2; i <= N; i++)
		v[i] = (1LL * A * v[i - 1] + B) % C;

	for(int i = 0; i < 4; i++)
	{
		for(int j = 0; j < BYTE; j++)
			count[j] = 0;
		
		for(int j = 1; j <= N; j++)
			count[(v[j] >> (i << 3)) & (BYTE - 1)]++;

		for(int j = 1; j < BYTE; j++)
			count[j] += count[j - 1];
		
		for(int j = N; j >= 1; j--)
			aux[count[(v[j] >> (i << 3)) & (BYTE - 1)]--] = v[j];
		
		for(int j = 1; j <= N; j++)
			v[j] = aux[j];
	}

	for(int i = 1; i <= N; i += 10)
		cout << v[i] << ' ';

	return 0;
}