Language: C++

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


// nC2を求める関数
ll pair_conb(ll n) {
    return n*(n-1)/2;
}

// returns <zone,rank>
pair<int,int> calc_zone(ll prod_minus_cnt,ll prod_zero_cnt, ll K) {
    if ( K <= prod_minus_cnt) return make_pair(-1,K);
    K -= prod_minus_cnt;
    if ( K <= prod_zero_cnt) return make_pair(0,K);
    K -= prod_zero_cnt;
    return make_pair(1,K);
}

// xが小さい順から何番目か算出する。　<rank,x以上で、xに最も近い組み合わせの中に含まれる要素>
pair<ll,ll> calc_rank(const vector<ll>& A_minus,const vector<ll>& A_plus,ll x) {
    bool end = false;
    ll ans = 0;
    ll new_x = 0;
    ll dist = (1e18);
    for(auto plus_itr:A_plus) {



        // A_minusの最大値を見る
        auto m_top = A_minus[A_minus.size()-1];

        // 先頭*plus_itrよりも小さいならendフラグを立てる
        if ( (plus_itr * m_top) < x) {
            end = true;
            auto last = A_plus.end() - plus_itr;
            ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
            continue;
        }

        // 二分探索でxよりも小さい組み合わせの数を求める
        // plus_itr * A_minus[i] < x が成り立つ最大のiを出す。
        // ライブラリを使用するため A_minus[i] < x / plus_itr として計算する。
        auto itr = lower_bound(ALL(A_minus),x/plus_itr);
        ans += itr - A_minus.begin();
        // ついでにitr-1の値を保存しておく
        auto next = plus_itr*(*(itr));
        if (chmin(dist,abs(x-next) )) new_x = next;
    }
    return make_pair(ans+1,max(x,new_x));
}


// K番目がマイナスのゾーンにいた時に答えを探索する関数
ll minus_sch(const vector<ll>& A_minus,const vector<ll>& A_plus,int rank) {
    // binary search
    ll left = -1 * ll(1e9);
    ll right = -1;
    ll mid;
    while (left < right) {
        mid = (left + right)/2;
        auto cr = calc_rank(A_minus,A_plus,mid);
        ll n_rank = cr.first;
        if (n_rank == rank) {
            return cr.second;
        } else if (rank < n_rank) {
            right = mid;
        } else if (n_rank < rank) {
            left = mid + 1;
        }
    }
    return -1;
}


// K番目がプラスのゾーンにいた時に答えを探索する関数(未実装)
ll plus_sch(const vector<ll>& A_minus,const vector<ll>& A_plus,int rank) {
    exit(1);
}
int main() {
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    // マイナスの要素を格納する配列
    vector<ll> A_minus;
    // プラスの要素を格納する配列
    vector<ll> A_plus;

    REP(i,N) {
        ll a;
        cin >> a;
        if ( a > 0) A_plus.push_back(a);
        else if ( a < 0 ) A_minus.push_back(a);
    }
    ll aps = A_plus.size();
    ll ams = A_minus.size();

    // Aに含まれる0の個数。
    ll zero_cnt = N - (aps+ams);

    // 積が{+|-|0}の個数を求める
    ll prod_minus_cnt = aps*ams;
    ll prod_plus_cnt = pair_conb(aps) + pair_conb(ams);
    ll prod_zero_cnt = pair_conb(N) - pair_conb(N-zero_cnt);

    cerr << "prod_minus_cnt: " << prod_minus_cnt << endl;
    cerr << "prod_zero_cnt: " << prod_zero_cnt << endl;
    cerr << "prod_plus_cnt: " << prod_plus_cnt << endl;

    // ここでテスト、prod_* な変数の値全て足した結果がpair_conb(N)になるはず。
    cerr << "pair_conb(N): " << pair_conb(N) << endl;
    cerr << "prod sum: " << prod_minus_cnt+prod_plus_cnt+prod_zero_cnt << endl;

    auto p = calc_zone(prod_minus_cnt,prod_zero_cnt,K);
    cerr << "zone: " << p.first << " rank: " << p.second << endl;

    sort(ALL(A_minus));
    sort(ALL(A_plus));

    if ( p.first == 1) cout << plus_sch(A_minus,A_plus,p.second) << endl;
    else if (p.first == -1) cout << minus_sch(A_minus,A_plus,p.second) << endl;
    // p.first == 0 -> K番目は0なので終了
    else cout << 0 << endl;

    return 0;
}


Compiler output:
a.cc: In function 'std::pair<long long int, long long int> calc_rank(const std::vector<long long int>&, const std::vector<long long int>&, ll)':
a.cc:48:56: error: no match for 'operator-' (operand types are 'std::vector<long long int>::const_iterator' and 'long long int*')
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                           ~~~~~~~~~~~~ ^ ~~~~~~~~~
      |                                                     |    |
      |                                                     |    long long int*
      |                                                     std::vector<long long int>::const_iterator
In file included from /usr/include/c++/14/bits/stl_algobase.h:67,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_iterator.h:1148:7: note: candidate: '__gnu_cxx::__normal_iterator<_Iterator, _Container> __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator-(difference_type) const [with _Iterator = const long long int*; _Container = std::vector<long long int>; difference_type = long int]' (near match)
 1148 |       operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1148:7: note:   conversion of argument 1 would be ill-formed:
a.cc:48:58: error: invalid conversion from 'long long int*' to '__gnu_cxx::__normal_iterator<const long long int*, std::vector<long long int> >::difference_type' {aka 'long int'} [-fpermissive]
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                          ^~~~~~~~~
      |                                                          |
      |                                                          long long int*
/usr/include/c++/14/bits/stl_iterator.h:618:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  618 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:618:5: note:   template argument deduction/substitution failed:
a.cc:48:59: note:   'std::vector<long long int>::const_iterator' is not derived from 'const std::reverse_iterator<_Iterator>'
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                           ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1790:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1790 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1790:5: note:   template argument deduction/substitution failed:
a.cc:48:59: note:   'std::vector<long long int>::const_iterator' is not derived from 'const std::move_iterator<_IteratorL>'
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                           ^~~~~~~~
In file included from /usr/include/c++/14/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:127:
/usr/include/c++/14/complex:370:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const complex<_Tp>&, const complex<_Tp>&)'
  370 |     operator-(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/complex:370:5: note:   template argument deduction/substitution failed:
a.cc:48:59: note:   'std::vector<long long int>::const_iterator' is not derived from 'const std::complex<_Tp>'
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                           ^~~~~~~~
/usr/include/c++/14/complex:379:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const complex<_Tp>&, const _Tp&)'
  379 |     operator-(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/14/complex:379:5: note:   template argument deduction/substitution failed:
a.cc:48:59: note:   'std::vector<long long int>::const_iterator' is not derived from 'const std::complex<_Tp>'
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                           ^~~~~~~~
/usr/include/c++/14/complex:388:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const _Tp&, const complex<_Tp>&)'
  388 |     operator-(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/complex:388:5: note:   template argument deduction/substitution failed:
a.cc:48:59: note:   mismatched types 'const std::complex<_Tp>' and 'long long int*'
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                           ^~~~~~~~
/usr/include/c++/14/complex:465:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const complex<_Tp>&)'
  465 |     operator-(const complex<_Tp>& __x)
      |     ^~~~~~~~
/usr/include/c++/14/complex:465:5: note:   candidate expects 1 argument, 2 provided
In file included from /usr/include/c++/14/valarray:605,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:166:
/usr/include/c++/14/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const _Expr<_Dom1, typename _Dom1::value_type>&, const _Expr<_Dom2, typename _Dom2::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
a.cc:48:59: note:   'std::vector<long long int>::const_iterator' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                           ^~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const _Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
a.cc:48:59: note:   'std::vector<long long int>::const_iterator' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                           ^~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const typename _Dom::value_type&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
a.cc:48:59: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'long long int*'
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                           ^~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const _Expr<_Dom1, typename _Dom1::value_type>&, const valarray<typename _Dom::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
a.cc:48:59: note:   'std::vector<long long int>::const_iterator' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                           ^~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const valarray<typename _Dom::value_type>&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
a.cc:48:59: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'long long int*'
   48 |             ans+= ll(A_minus.size()) * ll(A_plus.end() - &plus_itr);
      |                                                           ^~~~~~~~
/usr/include/c++/14/valarray:1197:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const valarray<_Tp>&, const valarray<_