TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Pairs

問題

D – Pairs
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
const ll INF = 1LL << 60;
// const int INF = 1001001001;

ll N, K;
vector<ll> A;

bool f(ll mid) {
  ll cnt = 0;
  rep(i, N) {
    if(0 <= A[i]) {
      int l = -1;
      int r = N;
      while(l + 1 < r) {
        int border = (l + r) / 2;
        if(A[border] * A[i] < mid) {
          l = border;
        } else {
          r = border;
        }
      }
      cnt += r;
    } else {
      int l = -1;
      int r = N;
      while(l + 1 < r) {
        int border = (l + r) / 2;
        if(A[border] * A[i] < mid) {
          r = border;
        } else {
          l = border;
        }
      }
      cnt += N - r;
    }
    if(A[i] * A[i] < mid) {
      cnt--;
    }
  }
  cnt /= 2;
  return cnt < K;
}

int main() {
  cin >> N >> K;

  A.resize(N);
  rep(i, N) { cin >> A[i]; }

  sort(A.begin(), A.end());

  ll l = -INF;
  ll r = INF;

  while(l + 1 < r) {
    ll mid = (l + r) / 2;
    bool flg = f(mid);
    if(flg) {
      l = mid;
    } else {
      r = mid;
    }
  }

  cout << l << endl;
  return 0;
}