Cod sursa(job #1389127)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 16 martie 2015 00:26:21
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <iostream>

using namespace std;

vector<unsigned> radix_sort(vector<unsigned> data,unsigned lim) {
	cout << lim << endl;
	queue<unsigned> buckets[10];
	unsigned p = 1;
	for(size_t i = 0; i <= lim; ++i) {
		for(const auto &val:data){
			buckets[(val/p)%10].push(val);
		}

		data.clear();

		for(size_t i = 0; i < 10; ++i) {
			while(!buckets[i].empty()) {
				data.push_back(buckets[i].front());
				buckets[i].pop();
			}
		}
		p*=10;
	}

	return move(data);
}

int main() {
	ifstream in("radixsort.in");

	unsigned n,a,b,c;

	in >> n >> a >> b >> c;

	vector<unsigned> data(n);
	data[0] = b;

	for(size_t i = 1; i < n; ++i) {
		data[i] = (a*data[i-1] + b)%c;
	}


	data = radix_sort(move(data),ceil(log(c)/log(10)));

	ofstream out("radixsort.out");

	for(size_t i = 0; i < n; i += 10) {
		out << data[i] << ' ';
	}
}