Cod sursa(job #1612196)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 februarie 2016 19:05:26
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 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> sz = {}, poz = {};
		for(int i = 0; i < n; ++i){
			++sz[(v[i]>>niv)&255]; }

		poz[0] = 0;
		for(int i = 1; i < 256; ++i){
			poz[i] = poz[i-1] + sz[i-1]; }

		for(int i = 0; i < n; ++i){
			tmp[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; }