Cod sursa(job #1132143)

Utilizator predator5047Butiu Alexandru Octavian predator5047 Data 2 martie 2014 18:56:17
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <numeric>
#include <algorithm>
using namespace std;

int n, v[10000009], b[10000009];

void in() {
	int A, B, C;
	ifstream fin("radixsort.in");
	fin >> n >> A >> B >> C;
	v[0] = B;	
	generate(v + 1, v + n, [=]() {
		static int prev = v[0];
		return prev = (1LL * A * prev + B) % C;
	});
	
			
}

void radix_sort() {
	int d[] = {0, 8, 16, 24};
	for(int k = 0; k < 4; ++k) {
		int a[0xFF] = { 0 };
		for(int i = 0; i < n; ++i) {
			a[v[i] >> d[k] & 0xFF]++;
		}

		partial_sum(a, a + 0xFF, a);
		for(int i = n - 1; i >= 0; --i) {
			b[--a[v[i] >> d[k] & 0xFF]] = v[i];
		}

		copy(b, b + n, v);
	}
}

int main() {
	in();

	radix_sort();
	
	ofstream fout("radixsort.out");

	for(int i = 0; i < n; i += 10) {
		fout << v[i] << " ";
	}

	return 0;
}