Cod sursa(job #1473695)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 19 august 2015 23:59:41
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
using namespace std::placeholders;

template <typename T>
T median_3(const T& a, const T& b, const T& c){
	return (a <= b && b <= c) || (c <= b && b <= c) ? b : median_3(b, c, a); }

template <typename T>
typename T::value_type good_random_element(const T st, const T dr){
	const int nr = distance(st, dr);
	const auto it1 = st + rand()%nr, it2 = st + rand()%nr, it3 = st + rand()%nr;
	return median_3(*it1, *it2, *it3); }

template <typename T>
void my_nth_element(T& st, T& mij, T& dr){
	if(st == mij){
		return; }
	else{
		const auto pivot_val = good_random_element(st, dr);
		const auto pivot = partition(st, dr, bind(less<int>(), _1, pivot_val));
		if(mij < pivot){
			my_nth_element(st, mij, pivot); }
		else if(mij >= pivot){
			my_nth_element(pivot, mij, dr); } } }

int main(){
	srand(time(NULL));
	ifstream f("sdo.in");
	ofstream g("sdo.out");
	int n, k;
	f >> n >> k;
	vector<int> v(n);
	for(auto& x : v){
		f >> x; }
	nth_element(begin(v), begin(v)+k-1, end(v));
	g << v[k-1];
	return 0; }