Cod sursa(job #1428864)

Utilizator stef93Stefan Gilca stef93 Data 5 mai 2015 10:51:47
Problema Radix Sort Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <cstring>
#include <cstdio>

using namespace std;

void sorteaza(int *vec, int *aux, int byte, int n)
{
	int count[1 << 8];
	int index[1 << 8];

	memset(count, 0, sizeof(count));

	for(int i =0 ; i < n; i++)
	{
		count[(vec[i] >> (8*byte)) & 0xff]++;
	}

	index[0] = 0;

	for(int i = 1 ; i < (1 << 8); i++)
	{
		index[i] = index[i - 1] + count[i - 1];
	}

	for(int i = 0 ;i < n ; i++)
	{
		aux[index[(vec[i] >> (8*byte)) & 0xff] ++] = vec[i];
	}
}

int vec[10000001];
int main()
{
	freopen("radixsort.in", "r", stdin);
	//ofstream out("radixsort.out");
	freopen("radixsort.out", "w", stdout);
	int n, a, b, c;
	int  *aux;

	//n >> n >> a >> b >> c;
	scanf("%d%d%d%d", &n, &a, &b, &c);
	//vec = new int[n];
	aux = new int[n];

	vec[0] = b % c;

	for(int i = 1 ; i < n; i++)
	{
		vec[i] = (1LL*a * vec[i - 1]%c + b) %c;
	}

	for(int i = 0 ; i <8; i++)
	{
		if(i % 2 == 0)
		{
			sorteaza(vec, aux, i, n);
		}
		else
		{
			sorteaza(aux, vec, i, n);
		}
	}

	for(int i = 0 ; i < n; i += 10)
	{
		printf("%d ", vec[i]);
	}
	return 0;
}