Cod sursa(job #1824175)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 7 decembrie 2016 14:43:38
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#define N (1 << 17)
using namespace std;

int imp, n;
int frc[1000100];
int nr[11000000];
int nr2[11100010];
void sort();

int main()
{
	int a, b, c;
	ifstream in("radixsort.in");
	in >> n >> a >> b >> c;
	nr[0] = b;
	for (int i(1); i < n; i++)
		nr[i] = 1ll * (1ll * nr[i - 1] * a + b) % c;

	imp = 1;
	sort();
	imp = N;
	sort();

	ofstream out("radixsort.out");

	for (int i(0); i < n; i += 10)
		out << nr[i] << ' ';

	return 0;
}


void sort()
{
	for (int i(0); i < n; i++) {
		if ((nr[i] / imp) % N != 0)
			frc[(nr[i] / imp) % N + 1]++;
		nr2[i] = nr[i];
	}
	for (int i(1); i <= N; i++)
		frc[i] += frc[i - 1];

	for (int i(0); i < n; i++) {
		nr[frc[(nr2[i] / imp) % N]++] = nr2[i];
	}
	for (int i(0); i <= N; i++)
		frc[i] = 0;
}