Cod sursa(job #1183438)

Utilizator howsiweiHow Si Wei howsiwei Data 9 mai 2014 07:23:41
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

void radixsort(vector<int> & a)
{
	const int nbuck = 1<<16;
	int n = a.size();
	for (int k = 0; k < 2; k++) {
		vector<vector<int> > b(nbuck);
		for (int i = 0; i < n; i++) {
			int tmp = a[i];
			for (int j = 0; j < k; j++) {
				tmp /= nbuck;
			}
			tmp %= nbuck;
			b[tmp].push_back(a[i]);
		}
		for (int i = 0, idx = 0; i < nbuck; i++) {
			for (vector<int>::iterator it = b[i].begin(); it != b[i].end(); ++it) {
				a[idx] = *it;
				idx++;
			}
		}
	}
}

int main()
{
	freopen("radixsort.in", "r", stdin);
	freopen("radixsort.out", "w", stdout);
	int n;
	cin >> n;
	int x, y, z;
	cin >> x >> y >> z;
	vector<int> a(n);
	a[0] = y;
	for (int i = 1; i < n; i++) {
		a[i] = (x*a[i-1]+y)%z;
	}
	radixsort(a);
	// sort(a.begin(), a.end());
	for (int i = 0; i < n; i += 10) {
		printf("%d%s", a[i], i+10 < n ? " " : "\n");
	}
	return 0;
}