Pagini recente » Cod sursa (job #482829) | Cod sursa (job #2015553) | Cod sursa (job #335093) | Cod sursa (job #559618) | Cod sursa (job #1473695)
#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; }