Cod sursa(job #1183442)

Utilizator howsiweiHow Si Wei howsiwei Data 9 mai 2014 08:36:58
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

void radixsortaux(vector<int> & a, vector<int> & b, int nbitshift)
{
	const int log2nbuck = 16;
	const int nbuck = 1<<log2nbuck;
	int n = a.size();
	vector<int> cnt(nbuck+1);
	for (int i = 0; i < n; i++) {
		int tmp = (a[i] >> nbitshift) & (nbuck-1);
		cnt[tmp+1]++;
	}
	for (int i = 1; i < nbuck; i++) {
		cnt[i] += cnt[i-1];
	}
	for (int i = 0; i < n; i++) {
		int tmp = (a[i] >> nbitshift) & (nbuck-1);
		b[cnt[tmp]] = a[i];
		cnt[tmp]++;
	}
}

void radixsort(vector<int> & a)
{
	vector<int> b(a.size());
	radixsortaux(a, b, 0);
	radixsortaux(b, a, 16);
}

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] = ((long long)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;
}