Problem:


Score: 400 points

Problem Statement

We have N integers A_1, A_2, ..., A_N.

There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \frac{N(N-1)}{2}

-10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 3
3 3 -4 -2

Sample Output 1

-6

There are six ways to form a pair. The products of those pairs are 9, -12, -6, -12, -6, 8.

Sorting those numbers in ascending order, we have -12, -12, -6, -6, 8, 9. The third number in this list is -6.

Sample Input 2

10 40
5 4 3 2 -1 0 0 0 0 0

Sample Output 2

6

Sample Input 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

Sample Output 3

448283280358331064



Sample input:
4 3
3 3 -4 -2


Sample output:
-6

Submission status: Accepted

Solution code:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
a = np.array(a,dtype="int64")
a_minus = a[a<0]
a_plus = a[a>0]
a_zero = a[a==0]
#print(a_plus)
l = - 10**19
r = 10**19


while r - l > 1:
  mid = (l+r)//2
  # mid以下の個数を調べる
  cnt = 0
  # 正の数の組み合わせでmid以下の個数を調べる
  cnt += a.searchsorted(mid//a_plus, side="right").sum()
  # 負の数で同様
  cnt += (n - a.searchsorted((-mid-1)//(-a_minus), side="right")).sum()
  # 同じ数の組み合わせ(差し引くよう)
  cnt -= np.count_nonzero(a*a<=mid)
  # ゼロも同様(mid>=0のときのみ)
  cnt += len(a_zero)*n if mid >= 0 else 0
  
  # 重複を割る
  cnt //= 2
  
  if cnt >= k:
    r = mid
  else:
    l = mid
  
print(r)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
N, K = [int(_) for _ in input().split()]
A = np.array(sorted([int(_) for _ in input().split()]))


@njit
def solve(N, K, A):
    lb = -10**18 - 1
    rb = 10**18 + 1

    def check(x):
        #x以下の積がK個以上ある
        cnt = 0
        for i, a in enumerate(A):
            #区間i2∈[0,i) でA[i]*A[i2]<=xとなるようなi2の個数
            l = 0
            r = i
            if a > 0:
                l = -1
                r = np.searchsorted(A, x // a, side='right')
            elif a < 0:
                l = np.searchsorted(A, 0 - x // (-a), side='left')
                r = N + 1
            elif x < 0:
                r = 0
            l = min(max(l, 0), i)
            r = max(min(r, i), 0)
            cnt += r - l
        return cnt >= K

    # Min x for check(x) == True
    while rb - lb > 1:
        mid = (rb + lb) // 2
        if check(mid):
            rb = mid
        else:
            lb = mid
    print(rb)


solve(N, K, A)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def is_ok_m(x):
        cnt = 0
        for P in plus:
            t = x // P
            cnt += bisect_right(minus, t)
        return cnt >= k

    def is_ok_p(x):
        cnt = 0
        for i, P in enumerate(plus):
            t = x // P
            idx = bisect_right(plus, t)
            if i < idx:
                idx -= 1
            cnt += idx

        for i, M in enumerate(minus):
            t = x // M
            idx = bisect_right(minus, t)
            if i < idx:
                idx -= 1
            cnt += idx
        cnt //= 2
        return cnt >= k

    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    minus, plus = [], []
    z = 0
    for a in A:
        if a < 0:
            minus.append(a)
        elif a > 0:
            plus.append(a)
        else:
            z += 1
    m, p = len(minus), len(plus)

    m_cnt = m * p
    z_cnt = m * z + p * z + ((z - 1) * z) // 2
    if k <= m_cnt:
        minus.sort()
        ng, ok = -10 ** 18 - 1, -1
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok_m(mid):
                ok = mid
            else:
                ng = mid
        res = ok
    elif k <= m_cnt + z_cnt:
        res = 0
    else:
        k -= m_cnt + z_cnt
        plus.sort()
        minus = [num * -1 for num in minus]
        minus.sort()
        ng, ok = -1, 10 ** 18
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok_p(mid):
                ok = mid
            else:
                ng = mid
        res = ok
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
A = sorted(list(map(int, input().split()))) # ソートしておく

minus_right = bisect_left(A, 0)
plus_left = bisect_right(A, 0)

# Aにおける正、負、zeroの要素数
plus_cnt = N - plus_left
minus_cnt = minus_right
zero_cnt = N - (plus_cnt + minus_cnt)

# ペアの積が負の組み合わせ
minus_pairs_cnt = plus_cnt * minus_cnt
# 正*zero、負*zero、zero*zero(0を2つ選択する組合せ)
zero_pairs_cnt = plus_cnt * zero_cnt + minus_cnt * zero_cnt + zero_cnt * (zero_cnt - 1) // (2 * 1)

if K <= minus_pairs_cnt:
  # 積のK番目が負の場合
  
  # 二分探索
  low = -10 ** 18 # 積の最小(-10**9 * 10**9)
  high = 0 # 積の最大
  ans = 0
  while abs(high - low) > 1:
    mid = (low + high) // 2
    cnt = 0
    
    r = plus_left # 正の要素を小さい順に検索
    for l in range(minus_right):
      # 負の要素を小さい順に検索する
      # lを固定してrを増やしていき、A[l]*A[r]がmidよりも小さくなれば
      # rよりも右は全てA[l]*A[r]がmidよりも小さくなるので、その数をカウントする
      
      while r < N and A[l]*A[r] > mid:
        r += 1
      cnt += plus_cnt - (r - plus_left)
    if cnt >= K:
      high = mid # cnt==Kを満たしても2分探索が完了していない場合は継続
    else:
      low = mid
    
  print(high) # cnt==Kの場合highに値が入るので最後にcnt==Kを満たしたhighを出力
elif K <= minus_pairs_cnt + zero_pairs_cnt:
  # 積のK番目が0の場合
  # minus_pairs_cnt < K <= minus_pairs_cnt + zero_pairs_cnt の場合
  print(0)
else:
  # 積のK番目が正の場合
  # minus_pairs_cnt + zero_pairs_cnt < K の場合
  
  # 二分探索
  low = 0 # 積の最小
  high = 10 ** 18 # 積の最大(10**9 * 10**9)
  ans = 0
  
  while abs(high - low) > 1:
    mid = (low + high) // 2
    cnt = 0
    
    # 正*正の場合
    r = N-1
    for l in range(plus_left, N):
      # 小さい方(l)を固定し、大きい方(r)を減らしていき、
      # A[l]*A[r]がmidよりも小さくなれば
      # lとrの間は全てA[l]*A[r]がmidよりも小さくなるので、その数をカウントする
      
      while r < N and A[l]*A[r] > mid and l < r:
        r -= 1
      cnt += max(0, r - l)
      
    # 負*負の場合
    l = 0
    for r in range(minus_right - 1, -1, -1):
      # 大きい方(r)を固定し、小さい方(l)を増やしていき、
      # A[l]*A[r]がmidよりも小さくなれば
      # lとrの間は全てA[l]*A[r]がmidよりも小さくなるので、その数をカウントする
      
      while l < N and A [l]*A[r] > mid and l < r:
        l += 1
      cnt += max(0, r - l)
    if minus_pairs_cnt + zero_pairs_cnt + cnt >= K:
      high = mid
    else:
      low = mid
      
  print(high) # cnt==Kの場合highに値が入るので最後にcnt==Kを満たしたhighを出力

Submission status: Accepted

Solution code:
import sys
import numpy as np

N, K = map(int, sys.stdin.readline().rstrip().split())
A = np.array(sys.stdin.readline().rstrip().split(), np.int64)

# A をソートし、負／ゼロ／正　に分ける
A = np.sort(A)
zero = A[A == 0]
pos = A[A > 0]
neg = A[A < 0]


def f2(x):
    """
    積が x 以下になるペアの個数を返す

    - (i,j) と (j,i), (i,i) の重複を許して後で調整
    - A = [a_0, a_1, a_2, ... ,a_n-1] で、
         負 ～ 0 ～ 正 まで混ざった状態で
         target k と掛け合わせて x 以下になる場所 (index) を探す
    -           \__-5_-1__0_0_...__1___2
      a_0   = -5|  25  5  0 0 ... -5 -10
      a_1   = -1|   5  1  0 0 ... -1  -2
      a_2   =  0|   0  0  0 0 ...  0   0
      a_3   =  0|   0  0  0 0 ...  0   0
      a_4   =  1|  -5 -1  0 0 ...  1   2
      .....     |
      a_n-1 =  2| -10 -2  0 0 ...  2   4
    """

    cnt_tpl = 0

    # k < 0 の掛け合わせ -> 右から
    B = A.copy()
    B = -B
    B.sort()
    cnt_tpl += np.searchsorted(B, x // (-neg), side='right').sum()

    # a_2, a_3, k = 0 なら そのペアはすべて 0 (x//0になるので別扱い)
    if x >= 0:
        cnt_tpl += len(zero) * N

    # k > 0 の掛け合わせ -> 左から何番目まで, x 以下にできるか？
    cnt_tpl += np.searchsorted(A, x // pos, side='right').sum()

    # (i, i) で x 以下になったものがあれば、削除する
    cnt_tpl -= np.count_nonzero(A * A <= x)

    assert cnt_tpl % 2 == 0
    return cnt_tpl // 2


# 二分探索
left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f2(x) >= K:
        right = x
    else:
        left = x


print(right)

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            vars()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


def bis(K, A, B, t):
    # K 番目に小さい <=> x 未満の数が K 個未満であるような最大の x
    if t==1:
        ok = 0
        ng = 10**18+1
        while ok + 1 < ng:
            c = ok+ng>>1
            cnt = 0
            idx_B = len(B)-1
            for a in A:
                while idx_B >= 0 and a * B[idx_B] >= c:
                    idx_B -= 1
                cnt += idx_B + 1
            if cnt < K:
                ok = c
            else:
                ng = c
    else:
        ok = 0
        ng = 10**18+1
        while ok + 1 < ng:
            c = ok+ng>>1
            cnt = 0
            idx_A = len(A)-1
            idx_B = len(B)-1
            for a in A:
                while idx_A >= 0 and a * A[idx_A] >= c:
                    idx_A -= 1
                cnt += idx_A + 1
                if a*a < c:
                    cnt -= 1
            for b in B:
                while idx_B >= 0 and b * B[idx_B] >= c:
                    idx_B -= 1
                cnt += idx_B + 1
                if b*b < c:
                    cnt -= 1
            cnt >>= 1
            if cnt < K:
                ok = c
            else:
                ng = c
    return ok

numba_compile([
    [bis, "i8(i8,i8[:],i8[:],i8)"],
])

import numpy as np
def main():
    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    cnt_m = cnt_0 = cnt_p = 0
    for a in A:
        if a < 0:
            cnt_m += 1
        elif a == 0:
            cnt_0 += 1
        else:
            cnt_p += 1
    cnt2_m = cnt_m * cnt_p
    cnt2_0 = cnt_0 * N - cnt_0 * (cnt_0 + 1) // 2
    cnt2_p = cnt_p * (cnt_p - 1) // 2 + cnt_m * (cnt_m - 1) // 2
    assert cnt2_m + cnt2_0 + cnt2_p == N * (N - 1) // 2

    if K <= cnt2_m:
        # 絶対値が cnt2_m - K + 1 番目に小さい
        X = np.array([-a for a in A[::-1] if a<0], dtype=np.int64)
        Y = np.array([a for a in A if a>0], dtype=np.int64)
        ans = -bis(cnt2_m-K+1, X, Y, 1)
    elif K <= cnt2_m + cnt2_0:
        ans = 0
    else:
        X = np.array([-a for a in A[::-1] if a<0], dtype=np.int64)
        Y = np.array([a for a in A if a>0], dtype=np.int64)
        ans = bis(K-cnt2_m-cnt2_0, X, Y, 2)
    print(ans)

main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
# A.sort()
P = []
M = []
z = 0
for a in A:
    if a==0:z += 1
    elif a>0:P.append(a)
    else: M.append(a)
P.sort()
M.sort()
def helper(n):
    if n < 0:
        res = 0
        p = 0
        for m in range(len(M)):
            while p < len(P) and P[p]*M[m] > n:
                p += 1
            res += len(P)-p
    elif n ==0:
        res = len(P)*len(M) + z*(N-z) + z*(z-1)//2
    else:
        res = len(P)*len(M) + z*(N-z) + z*(z-1)//2
        pr = len(P)-1
        for pl in range(len(P)):
            while pr > pl and P[pl]*P[pr] > n:
                pr-=1
            res += max(0,pr-pl)
        ml = 0
        for mr in range(len(M)-1,-1,-1):
            while mr >ml and M[ml]*M[mr] > n:
                ml += 1
            res += max(0,mr-ml)
    return res

l = -10**18
r = 10**18
while True:
    num = (l+r)//2
    if helper(num) < K:
        l = num
    else:
        r = num
    if r-l <=1:
        print(r)
        break

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

n,k = map(int, input().split())
al = list(map(int, input().split()))
negal = []
posil = []
zero_cnt = 0
for a in al:
    if a > 0:
        posil.append(a)
    elif a == 0:
        zero_cnt += 1
    else:
        negal.append(abs(a))

negal.sort()
posil.sort()
nega_comb = len(negal)*len(posil)
zero_comb = zero_cnt*(zero_cnt-1)//2 + (len(negal)+len(posil))*zero_cnt

# ans = positive
if nega_comb+zero_comb < k:
    ng, ok = 0,10**18+1
    while abs(ok-ng) > 1:
        mid = (ok+ng) // 2
        cnt = nega_comb+zero_comb
        for i,nega in enumerate(negal):
            thre = mid//nega
            c_cnt = bisect_right(negal, thre)
            c_cnt -= (i+1)
            c_cnt = max(c_cnt,0)
            cnt += c_cnt
        for i,posi in enumerate(posil):
            thre = mid//posi
            c_cnt = bisect_right(posil, thre)
            c_cnt -= (i+1)
            c_cnt = max(c_cnt,0)
            cnt += c_cnt
        if k <= cnt:
            ok = mid
        else:
            ng = mid
    print(ok)

elif nega_comb < k:
    print(0)

# ans = negative
else:
    ng, ok = (10**18+1)*(-1), 0
    while abs(ok-ng) > 1:
        mid = (ok+ng) // 2
        cnt = 0
        for i,nega in enumerate(negal):
            thre = ((-1)*mid-1)//nega + 1
            c_cnt = len(posil) - bisect_left(posil, thre)
            cnt += c_cnt
        if k <= cnt:
            ok = mid
        else:
            ng = mid
    print(ok)

Submission status: Accepted

Solution code:
def main(N, K, A):
  cp = 0
  cn = 0
  cz = 0
  An = []
  Anp = []
  Ap = []
  for a in A:
    cp += a > 0
    cn += a < 0
    cz += a == 0
    if a > 0:
      Ap.append(a)
    if a < 0:
      An.append(a)
      Anp.append(-a)
  Anp = sorted(Anp)
	
  if K <= cn * cp:
    # negative 
    #print(K)
    
    ok = -10**20  # There are <= K pairs <= ok
    ng = 0
    # x, count

    while ok + 1 < ng:
      x = (ok + ng) //2
      count = 0
      i_an = -1
      for i, a in enumerate(Ap): # a: increasing -> x // a increasing
        while i_an + 1 < len(An) and An[i_an + 1]* a <= x:
          i_an += 1

        count += i_an + 1
        #print(x, a, count)
      #print(x, count)
      if count < K:
        ok = x
      else:
        ng = x
    return ng
  elif K <= cn * cp + cz * (cp + cn) + (cz - 1 )* cz //2:
    
    return 0
  else:
    # positive
    #print(K)
    K -=  cn * cp + cz * (cp + cn) + (cz - 1 )* cz //2
    #print(K)
    ok = 0
    ng = 10**20  # There are <= K pairs <= ok
    # x, count

    while ok + 1 < ng:
      x = (ok + ng) //2
      count = 0
      for Aa in [Ap, Anp]:
        i_ap = -1
        for i, a in zip(range(len(Aa)-1, -1, -1), Aa[::-1]):
          # a: decreasing -> x // a increasing
          while i_ap+1 < len(Aa) and Aa[i_ap+1] * a <= x:
            i_ap += 1
          count += i_ap + 1
          count -= i <= i_ap
          #print(x, a, count, i, i_ap, Aa)
      count //= 2
      #print(x, count)
      if count < K:
        ok = x
      else:
        ng = x
    return ng

N, K = map(int, input().split())
A = sorted(map(int, input().split()))
print(main(N,K,A))
#pairs = []
#for i in range(len(A)):
#  for j in range(i + 1, len(A)):
#    pairs.append(A[i]*A[j])
#pairs.sort()
#for K, p in zip(range(1, N*(N+1)//2+1), pairs):
#  
#  result = main(N, K, A)
#  if result != p:
#    print(K, p, result)
#print('done')

Submission status: Accepted

Solution code:

N, K = map(int, input().split())
X = list(map(int, input().split()))

neg = sorted(-v for v in X if v < 0)
pos = sorted(v for v in X if v > 0)
nonneg = sorted(v for v in X if v >= 0)

cnt_neg = len(neg)
cnt_pos = len(pos)

pair_pos = cnt_pos * (cnt_pos - 1) // 2 + cnt_neg * (cnt_neg - 1) // 2
pair_neg = cnt_pos * cnt_neg
pair_zro = N * (N - 1) // 2 - pair_pos - pair_neg

if pair_neg >= K:
    # Negative
    ub = 10 ** 18 + 1
    lb = 0
    while ub - lb > 1:
        mid = (ub + lb) // 2

        # Count
        cnt = 0
        j = 0
        for v in reversed(neg):
            while j < cnt_pos and v * pos[j] < mid:
                j += 1
            cnt += cnt_pos - j

        if cnt < K:
            ub = mid
        else:
            lb = mid

    print(-lb)
elif pair_neg + pair_zro >= K:
    print(0)
else:
    # Non-negative
    ub = 10 ** 18 + 1
    lb = 0
    while ub - lb > 1:
        mid = (ub + lb) // 2
        cnt = 0

        # Negative count
        j = 0
        for v in reversed(neg):
            if v ** 2 <= mid:
                cnt -= 1
            while j < cnt_neg and v * neg[j] < mid:
                j += 1
            cnt += j

        # Positive count
        j = 0
        for v in reversed(pos):
            if v ** 2 <= mid:
                cnt -= 1
            while j < cnt_pos and v * pos[j] < mid:
                j += 1
            cnt += j

        # Remove duplicate
        cnt //= 2

        if cnt + pair_neg + pair_zro < K:
            lb = mid
        else:
            ub = mid

    print(lb)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

P = []
M = []
z = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        z += 1

P.sort()
M.sort()

def f(n): #積がn以下になるペアはいくつあるか
    if n < 0:
        res = 0
        p = 0
        for m in range(len(M)):
            while p < len(P) and P[p]*M[m] > n:
                p += 1
            res += len(P)-p
    elif n == 0:
        res = len(P)*len(M)+z*(N-z)+z*(z-1)//2
    else:
        res = len(P)*len(M)+z*(N-z)+z*(z-1)//2
        pr = len(P)-1
        for pl in range(len(P)):
            while pr > pl and P[pl]*P[pr] > n:
                pr -= 1
            res += max(0, pr-pl)
        ml = 0
        for mr in range(len(M)-1, -1, -1):
            while mr > ml and M[ml]*M[mr] > n:
                ml += 1
            res += max(0, mr-ml)
    return res

l = -10**18
r = 10**18
while True:
    num = (l+r)//2
    if f(num) < K:
        l = num
    else:
        r = num
    if r-l <= 1:
        print(r)
        break

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N, K = LI()
    A = LI()

    P = sorted([ai for ai in A if ai > 0])
    Pm = sorted([-ai for ai in A if ai > 0])
    M = sorted([ai for ai in A if ai < 0])
    Mp = sorted([- ai for ai in A if ai < 0])
    zero = [ai for ai in A if ai == 0]

    zero_len = len(P) * len(zero) + len(M) * len(zero) + len(zero) * (len(zero) - 1) // 2

    if K <= len(P) * len(M):
        left = - 10 ** 18 - 1
        right = 0
        ans = right
        while right - left != 1:
            tmp = 0
            mid = (left + right) // 2
            for mi in M:
                tmp += bisect_right(Pm, - mid // mi)

            if tmp >= K:
                ans = min(ans, mid)
                right = mid
            else:
                left = mid
        print(ans)
    elif K <= len(P) * len(M) + zero_len:
        print(0)
    else:
        diff = len(P) * len(M) + zero_len
        left = 0
        right = 10 ** 18 + 1
        ans = right
        while right - left != 1:
            tmp = 0
            mid = (left + right) // 2
            for pi in P:
                tmp += bisect_right(P, mid // pi)
                tmp -= 1 if mid // pi >= pi else 0
            for mpi in Mp:
                tmp += bisect_right(Mp, mid // mpi)
                tmp -= 1 if mid // mpi >= mpi else 0
            tmp //= 2
            if tmp + diff >= K:
                ans = min(ans, mid)
                right = mid
            else:
                left = mid
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import *

def binary_search_int(ok, ng, test):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ng

def get_count1(k, A):
    """ K番目の要素が正の場合 """
    l, r = 0, len(A)-1
    res = 0
    while l < r:
        if A[l]*A[r] > k:
            r -= 1
            continue
        res += r-l
        l += 1
    return res

def get_count2(k, B, C):
    """ K番目の要素が負の場合 """
    l, r = 0, len(C)-1
    res = 0
    while True:
        if l > len(B)-1 or r < 0:
            break
        if B[l]*C[r] < -k:
            l += 1
            continue
        res += len(B)-l
        r -= 1
    return res

def test1(k):
    return get_count1(k, B) + get_count1(k, C) + count_negative < K

def test2(k):
    return get_count2(k, B, C) < K



N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

at_zero = bisect_left(A,0)
B = A[:at_zero]
B = list(map(lambda x: -x, B))
B = list(reversed(B))   # 負の要素
C = A[at_zero:]         # 正の要素
count_positive = (len(B)*(len(B)-1)//2 + len(C)*(len(C)-1)//2)
count_negative = N*(N-1)//2 - count_positive
if K > count_negative:
    print(binary_search_int(-1, 10**18+1, test1))
else:
    print(binary_search_int(-10**18, 1, test2))

Submission status: Accepted

Solution code:
"""
2つの数字の積xに対して、x未満となる組み合わせの数がk未満となる
最大のxを二分探索で求める。
"""

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

inf = int(1e18) + 1
l = -inf
r = inf

while l + 1 < r:
    c = (l + r) // 2
    cnt = 0
    for i in range(n):
        if a[i] < 0:
            _l = i
            _r = n
            while _l + 1 < _r:
                _c = (_l + _r) // 2
                if a[i] * a[_c] >= c:
                    _l = _c
                else:
                    _r = _c
            if _r != n:
                cnt += (n - _r)
        else:
            _l = i
            _r = n
            while _l + 1 < _r:
                _c = (_l + _r) // 2
                if a[i] * a[_c] < c:
                    _l = _c
                else:
                    _r = _c
            if _l != i:
                cnt += _l - i
    if cnt < k:
        l = c
    else:
        r = c

print(l)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit


@njit
def main(I):
    N,K=I[0],I[1]
    A = I[2:]
    A.sort()
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

I=np.array([int(_) for _ in open(0).read().split()],dtype=int)
print(main(I))

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()


@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def find_x_miman(pos, i, neg, x):
    if len(neg) == 0:
        return 0
    if neg[0] * pos[i] >= x:
        return 0
    ok = 0
    ng = len(neg)
    while ok + 1 < ng:
        m = (ng + ok) // 2
        if neg[m] * pos[i] < x:
            ok = m
        else:
            ng = m
    return ok + 1

def find_x_miman_from_right(arr, i, x):
    if not (i + 1  < len(arr)):
        return 0
    if arr[i] * arr[i+1] >= x:
        return 0

    ok = i + 1
    ng = len(arr)
    while ok + 1 < ng:
        m = (ng + ok) // 2
        if arr[m] * arr[i] < x:
            ok = m
        else:
            ng = m
    return ok - i

def main():
    N, K = LI()
    A = LI()
    A = sorted(A)
    pos = [a for a in A if a > 0]
    neg = [a for a in A if a < 0]
    rev_neg = [abs(a) for a in neg][::-1]
    n_zero = N - len(neg) - len(pos)
    l = -10**18 - 1 # K未満
    r = 10**18 + 1

    def count_miman(x):
        # return count of mul less than x
        cnt = 0
        if x < 0:
            for i in range(len(pos)):
                cnt += find_x_miman(pos, i, neg, x)
        else: # x > 0
            if x > 0:
                cnt += n_zero * (len(neg) + len(pos)) + (n_zero * (n_zero - 1)) // 2
            for i in range(len(pos)):
                cnt += find_x_miman_from_right(pos, i, x)
            for i in range(len(rev_neg)):
                cnt += find_x_miman_from_right(rev_neg, i, x)
            cnt += len(pos) * len(neg)
        return cnt

    # x未満がK個未満あるような最大のx
    while l + 1 < r:
        m = (l + r) // 2
        mimcount = count_miman(m)
        if mimcount < K:
            l = m
        else:
            r = m
    print(l)

main()

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())

l_pos = sorted(v for v in A if v > 0)
l_neg = sorted(-v for v in A if v < 0)

cnt_pos = len(l_pos)
cnt_neg = len(l_neg)

pair_pos = cnt_pos * (cnt_pos - 1) // 2 + cnt_neg * (cnt_neg - 1) // 2
pair_neg = cnt_pos * cnt_neg
pair_zro = N * (N - 1) // 2 - pair_pos - pair_neg


def solve_neg(n):
    ub = 10 ** 18 + 1
    lb = 0
    while ub - lb > 1:
        mid = (ub + lb) // 2
        
        # Count
        n_pos = len(l_pos)
        cnt = 0
        j = 0
        for v in reversed(l_neg):
            while j < n_pos and v * l_pos[j] < mid:
                j += 1
            cnt += n_pos - j

        if cnt < n:
            ub = mid
        else:
            lb = mid

    return -lb


def solve_pos(n):
    lb = 0
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        cnt = 0
        mid = (ub + lb) // 2

        # Negative count
        n_neg = len(l_neg)
        j = 0
        for v in reversed(l_neg):
            if v ** 2 <= mid:
                cnt -= 1
            while j < n_neg and v * l_neg[j] < mid:
                j += 1
            cnt += j

        # Positive count
        n_pos = len(l_pos)
        j = 0
        for v in reversed(l_pos):
            if v ** 2 <= mid:
                cnt -= 1
            while j < n_pos and v * l_pos[j] < mid:
                j += 1
            cnt += j

        # Remove duplicated counts
        cnt //= 2

        if cnt < n:
            lb = mid
        else:
            ub = mid
            
    return lb


if K <= pair_neg:
    ans = solve_neg(K)
elif K <= pair_neg + pair_zro:
    ans = 0
else:
    ans = solve_pos(K - pair_neg - pair_zro)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
m,p=[],[]
for a in A:
    if a<0:
        m.append(a)
    elif a>0:
        p.append(a)
M,P=len(m),len(p)
Z=N-M-P
m.sort()
p.sort()
if M*P<K<=N*(N-1)//2-M*(M-1)//2-P*(P-1)//2:
    print(0)
elif K<=M*P:
    l,r=-10**18-1,0
    while l+1<r:
        t=(l+r)//2
        x=0
        mi=0
        for pi in range(P):
            while mi<M and m[mi]*p[pi]<=t:
                mi+=1
            x+=mi
        if K<=x:
            r=t
        else:
            l=t
    print(r)
else:
    l,r=0,10**18+1
    K-=M*P+Z*(Z-1)//2+Z*(M+P)
    m.reverse()
    while l+1<r:
        t=(l+r)//2
        x=0
        mi,pi=0,0
        for mj in range(M-1,-1,-1):
            while mi<M and m[mi]*m[mj]<=t:
                mi+=1
            x+=mi-(1 if mj<mi else 0)
        for pj in range(P-1,-1,-1):
            while pi<P and p[pi]*p[pj]<=t:
                pi+=1
            x+=pi-(1 if pj<pi else 0)
        if K<=x//2:
            r=t
        else:
            l=t
    print(r)