Submission #2384454

---

Source Code Expand

// Many Medians

#define NODEBUG

#include<utility>
#include<type_traits>
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
#include<cassert>

using namespace std;

using X_type = int32_t;

template<typename T, typename Iter>
pair<T,T> sub(Iter first,Iter last, size_t n)
{
        static_assert(is_base_of<random_access_iterator_tag, typename iterator_traits<Iter>::iterator_category>::value,
                        "ランダムアクセス反復子じゃない");

        vector<T> tmp(first,last);
        assert(n==tmp.size());
        assert(n%2==0);

        typename vector<T>::iterator mid;

        mid = tmp.begin()+(n/2)-1;
        nth_element(tmp.begin(), mid, tmp.end());
        T min_cand = *mid;

        mid = tmp.begin()+(n/2);
        nth_element(tmp.begin(), mid, tmp.end());
        T max_cand = *mid;

        return {min_cand,max_cand};
}

int main(){
        size_t N;
        cin >> N;
        assert(N%2==0);

        vector<X_type> X;
        X.reserve(N);
        copy_n(istream_iterator<X_type>{cin}, N, back_inserter(X));

        auto p = sub<X_type>(X.begin(), X.end(), N);
        transform(X.begin(), X.end(), ostream_iterator<X_type>{cout,"\n"},
                        [p](X_type x){ return x<p.second ? p.second : p.first; });

        cout.flush();
        return 0;
}

Submission Info

Judge Result