Cod sursa(job #1509782)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 24 octombrie 2015 12:20:25
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <cstring>

#define NMAX 10000005

#define RADIX 0xFF
#define RADIX_SIZE 8
#define NR_BYTES sizeof(int)

using namespace std;

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

int n;
int v[NMAX], w[NMAX];

inline int getByte(int x, int byte)
{
	return (x >> (RADIX_SIZE * byte) & RADIX);
}

void countsort(int *a, int *b, int byte)
{
	int buckets[1 << RADIX_SIZE];
	int index[1 << RADIX_SIZE];

	memset(buckets, 0, sizeof(buckets));
	index[0] = 1;

	for (int i = 1; i <= n; ++i)
		++buckets[getByte(b[i], byte)];

	for (int i = 1; i < (1 << RADIX_SIZE); ++i)
		index[i] = index[i - 1] + buckets[i - 1];

	for (int i = 1; i <= n; ++i)
		a[index[getByte(b[i], byte)]++] = b[i];
}

void radixsort()
{
	for (int i = 0; i < NR_BYTES; ++i)
	{
		if (i & 1) countsort(v, w, i);
		else countsort(w, v, i);
	}
}
int main()
{
	int a, b, c;
	fin >> n >> a >> b >> c;

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

	radixsort();

	for (int i = 1; i <= n; i += 10)
		fout << v[i] << ' ';
	fout << '\n';
	return 0;
}