Cod sursa(job #1612179)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 februarie 2016 19:00:17
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;

void do_sort(vector<int>& v){
	const int n = v.size();
	vector<int> tmp(n);

	for(int niv = 0; niv < 32; niv += 8){
		array<int, 256> nr_el = {}, cur_poz = {};
		for(int i = 0; i < v.size(); ++i){
			++nr_el[(v[i]>>niv)&255]; }
		cur_poz[0] = 0;
		for(int i = 1; i < 256; ++i){
			cur_poz[i] = cur_poz[i-1] + nr_el[i-1]; }

		for(int i = 0; i < n; ++i){
			tmp[cur_poz[(v[i]>>niv)&255]++] = v[i]; }
		swap(tmp, v); } }


int main(){
	ifstream f("radixsort.in");
	ofstream g("radixsort.out");

	int n;
	long long a, b, c;
	f >> n >> a >> b >> c;

	vector<int> v(n);

	long long cur = b;
	for(int i = 0; i < n; ++i){
		v[i] = cur;
		cur = (a * cur + b) % c; }

	do_sort(v);

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

	return 0; }