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:
N,K=map(int,input().split())
A=list(map(int,input().split()))
mi=[]
pu=[]
ze=[]
lp=0
lz=0
lm=0
for i in A:
    if i>0:
        pu.append(i)
        lp+=1
    elif i==0:
        ze.append(i)
        lz+=1
    else:
        mi.append(-i)
        lm+=1
P=lp*(lp-1)//2+lm*(lm-1)//2
Z=lz*(lp+lm)+lz*(lz-1)//2
M=lp*lm
mi.sort()
pu.sort()
if K<=M:
    l=0
    r=10**18
    K=M-K
    while r-l!=1:
        a=(l+r)//2
        numa=0
        pos=lp-1
        for i in range(lm):
            while pos!=-1:
                if pu[pos]>a//mi[i]:
                    pos-=1
                else:
                    break
            numa+=pos+1
        if numa>K:
            r=a
        else:
            l=a
    print(-r)
elif K<=M+Z:
    print(0)
else:
    k=K-M-Z
    l=0
    r=10**18
    while r-l!=1:
        a=(l+r)//2
        cnt1=0
        cnt2=0
        pos1=lm-1
        pos2=lp-1
        for i in range(lm):
            tmp=0
            while pos1!=-1:
                if mi[pos1]>a//mi[i]:
                    pos1-=1
                else:
                    break
            tmp+=pos1+1
            if mi[i]**2<a:
                tmp-=1
            cnt1+=tmp
        for i in range(lp):
            tmp=0
            while pos2!=-1:
                if pu[pos2]>a//pu[i]:
                    pos2-=1
                else:
                    break
            tmp+=pos2+1
            if pu[i]**2<a:
                tmp-=1
            cnt2+=tmp
        numa=(cnt1+cnt2)//2
        if numa>=k:
            r=a
        else:
            l=a
    print(r)

Submission status: Accepted

Solution code:
import numpy as np
n,k = map(int,input().split())
a = np.array(list(map(int,input().split())))
a.sort()

p = a[a>0]
zeros = np.count_nonzero(a==0)
m = a[a<0]

#数xが何番目に大きい積か計算。複数ある場合は最大値
def count(x):
  cnt = 0
  #0以上だったらまず0の個数を足す
  if x >= 0:
    cnt += zeros*n #同じ要素の２じょうはあとで除くのでここでは気にせずかける
  #プラス部分のカウント
  #x//pはpをかけてもxを超えない数
  cnt += a.searchsorted(x//p,side='right').sum()
  #マイナス部分のカウント
  #マイナスは書けると大小が逆転する
  cnt += n*len(m) - a.searchsorted(-(-x//m),side='left').sum()
  #二乗を引く
  cnt -= np.count_nonzero(a*a<=x)
  return cnt//2

#十分に大きい範囲
l,r = -10**19,10**19
#r==lになるまで
while r-l>1:
  mid = (r+l)//2
  #真ん中がk以上だったらrを小さくして再挑戦
  if count(mid) >= k:
    r = mid
  else:
    l = mid
print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(x):
    cnt = 0
    if x < 0:
        j = p-1
        for i in range(m)[::-1]:
            while j >= 0 and plus[j]*minus[i] <= x:
                j -= 1
            cnt += p - j - 1
    else:
        j = 0
        for i in range(m)[::-1]:
            while j < m and minus[j]*minus[i] > x:
                j += 1
            cnt += max(0,i-j)
        j = p-1
        for i in range(p):
            while j >= 0 and plus[j]*plus[i] > x:
                j -= 1
            cnt += max(0,j-i)
        cnt += zero*(zero-1)//2 + m*p + zero*(m+p)
    
    return cnt >= k

n,k = LI()
a = LI()
a.sort()
minus = [x for x in a if x < 0]
plus = [x for x in a if x > 0]
m,p = len(minus),len(plus)
zero = bl(a,1) - br(a,-1)
ok,ng = 10**18,-10**18-1

while ok - ng > 1:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
N,K,*A = map(int, open(0).read().split())
Ap = []
An = []
Az = []
for c in A:
  if c>0:
    Ap.append(c)
  elif c<0:
    An.append(c)
  else:
    Az.append(c)
l = -10**20
r = 10**20
Ap.sort(reverse=True)
An.sort()
while l+1<r:
  s = (l+r)//2
  cnt = 0
  j = len(Ap)-1
  for i in range(len(Ap)):
    while j>-1 and Ap[i]*Ap[j]<s:
      j -= 1
    cnt += len(Ap)-1-j
  for i in range(len(Ap)):
    if Ap[i]*Ap[i]<s:
      cnt -= 1
  j = len(An)-1
  for i in range(len(An)):
    while j>-1 and An[i]*An[j]<s:
      j -= 1
    cnt += len(An)-1-j
  for i in range(len(An)):
    if An[i]*An[i]<s:
      cnt -= 1
  cnt //= 2
  if s>0:
    cnt += len(Az)*(len(Az)-1)//2 + len(Az)*(len(Ap)+len(An)) + len(Ap)*len(An)
  else:
    j = 0
    for i in range(len(Ap)-1,-1,-1):
      while j<len(An) and Ap[i]*An[j]<s:
        j += 1
      cnt += j
  if cnt>=K:
    r = s
  else:
    l = s
print(l)

Submission status: Accepted

Solution code:
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
negative_number_cnt = 0
positive_number_cnt = 0
negative_number = []
positive_number = []
zero_cnt = 0
a.sort()
def binary_search(left, right,positive):
    if right - left <= 1:
        return right
    middle = (right + left) // 2
    if is_can(middle,positive):
        return binary_search(left, middle,positive)
    else:
        return binary_search(middle, right,positive)
def is_can(x,positive):
    #xよりも小さい値がk個あるかどうか？
    if positive:
        count = than_less_zero
        #正＊正
        r = len(positive_number)-1
        for l in range(len(positive_number)):
            while l < r and positive_number[l] * positive_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #負*負
        r = len(negative_number)-1
        for l in range(len(negative_number)):
            while l < r and r_negative_number[l] * r_negative_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #print("target:{} count:{}".format(x,count))
        if count >= k:
            return True
        else:
            return False
    else:
        count = 0
        l,r = 0,0
        for l in range(len(negative_number)):
            while r < len(positive_number) and positive_number[r] * negative_number[l] > x:
                r += 1
            count += len(positive_number) - r
        if count >= k:
            return True
        else:
            return False



for i in range(n):
    if a[i] > 0:
        positive_number_cnt += 1
        positive_number.append(a[i])
    elif a[i] < 0:
        negative_number_cnt += 1
        negative_number.append(a[i])
    else:
        zero_cnt += 1
than_less_zero = ( negative_number_cnt * positive_number_cnt ) + (zero_cnt * (zero_cnt-1)//2) + zero_cnt * (n-zero_cnt)
r_negative_number = [negative_number[i] for i in range(len(negative_number)-1,-1,-1)]

if than_less_zero < k:
    #答えが正になる
    print(binary_search(0,10**20,True))
elif ( negative_number_cnt * positive_number_cnt ) < k:
    #答えが0になる
    print(0)
else:
    #答えが負になる
    print(binary_search(-10**20,5,False))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

n_m = bisect_left(a, 0)  # a[i] < 0 の数
n_0 = bisect_right(a, 0) - n_m  # a[i] = 0 の数
n_p = n - n_m - n_0  # a[i] > 0 の数

nn_m = n_m * n_p  # 積が負になるペア数
nn_0 = n_0 * (n - n_0) + n_0 * (n_0 - 1) // 2  # 積が0になるペア数
nn_p = n * (n - 1) // 2 - nn_m - nn_0  # 積が正になるペア数

if k <= nn_m:
    # k番目の値は負

    def check_minus(x):
        # k番目の値がx(<0)以下

        # a[i] * a[j] <= x

        # a[i]   * a[j] <= x  : a[j] >= abs(x) / abs(a[i])
        # a[i+1] * a[j] <= x  : a[j] >= abs(x) / abs(a[i+1])
        #     a[i]  <=     a[i+1] < 0
        # abs(a[i]) >= abs(a[i+1])
        # a: [-------00000+++++++]
        #     i             jjjjj
        #      i             jjjj
        #       i              jj

        # a[i] * a[j] <= -7
        # n_m = 4
        # n_0 = 3
        # a = [-5, -3, -2, -1, 0, 0, 0, 1, 2, 3, 4, 5]
        #       i                          j (j  j  j)
        #           i                         j (j  j)
        #               i                        j
        #                   i                          j
        # a[i] * a[j] = -5
        #  -2  *   4  = -6

        cnt = 0
        j = n_m + n_0
        for i in range(n_m):
            while j < n and a[i] * a[j] > x:
                j += 1
            # a[i] * a[j] <= x
            # [j, n)
            cnt += n - j

        return cnt >= k

    # a[i] * a[j] <= x
    lb = -10**18  # False
    ub = -1  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_minus(mid):
            ub = mid
        else:
            lb = mid
    ans = ub
elif k <= nn_m + nn_0:
    # k番目の値は0
    ans = 0
else:
    # k番目の値は正
    a_p = a[n_m + n_0:]
    a_m = [-a[i] for i in reversed(range(n_m))]

    def check_plus(x):
        # k番目の値がx(>=0)以下
        def func(b):
            # b [++++++++++++++]
            #    ijjjjjjjjjjj
            #     ijjjjjjjj
            #      ijjjj
            #       ij

            # b[i] * b[j] <= x
            # b[i]   * b[j] <= x : b[j]  <= x / b[i]
            # b[i+1] * b[j] <= x : b[j]  <= x / b[i+1]

            c = 0
            j = len(b) - 1
            for i in range(len(b)):
                if i >= j:
                    break
                # i < j
                while i < j and b[i] * b[j] > x:
                    j -= 1
                # b[i] * b[j] <= x
                # (i, j]
                c += j - i
            return c

        cnt = nn_m + nn_0
        cnt += func(a_p)
        cnt += func(a_m)
        return cnt >= k

    # a[i] * a[j] <= x
    lb = 0  # False
    ub = 10**18 + 1  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_plus(mid):
            ub = mid
        else:
            lb = mid
    ans = ub
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache
from bisect import bisect


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,K = inputIL()
A = inputIL()

A.sort()

s = bisect(A,-1)
t = bisect(A,0)

M = A[:s]
Z = A[s:t]
P = A[t:]
M_rev = [i*(-1) for i in M[::-1]]

m = len(M)
z = len(Z)
p = len(P)

n_Z = z*(m+p) + z*(z-1)//2
n_P = p*(p-1)//2 + m*(m-1)//2
n_M = p * m

def count(n):
  ret = 0
  t = 0
  for i in P:
    while t<len(M) and M[t]*i<=n:
      t += 1
    ret += t
  return ret


def count_p(n):
  ret = 0
  t = len(P)-1
  for i in P:
    while t>=0 and P[t]*i>n:
      t -= 1
    ret += t+1
    if i*i <= n:
      ret -= 1
  t = len(M_rev)-1   
  for i in M_rev:
    while t>=0 and M_rev[t]*i>n:
      t -= 1
    ret += t+1
    if i*i <= n:
      ret -= 1
  return ret//2

if n_M < K <= n_M+n_Z:
  print(0)
  exit()
  
if n_M >= K:
  l = -10**18
  r = -1
  while True:
    c = (l+r)//2
    if count(c) < K and count(c+1) >=K:
      break
    if count(c) >= K:
      r = c
    else:
      l = c+1
  print(c+1)
  exit()
  
else:
  K = K-(n_M+n_Z)
  l = 1
  r = 10**18
  while True:
    c = (l+r)//2
    if count_p(c) < K and count_p(c+1) >=K:
      break
    if count_p(c) >= K:
      r = c
    else:
      l = c+1
  print(c+1)
  exit()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
#import bisect# lower_bound etc
import numpy as np
def run():
    N, K, *A = list(map(int, read().split()))
    B = [a for a in A if a>0]
    C = [a for a in A if a<0]
    C_abs = [-c for c in C]
    O = A.count(0)
    B = np.array(sorted(B), dtype= np.int64)
    C = np.array(sorted(C), dtype = np.int64)
    C_abs = np.array(sorted(C_abs), dtype = np.int64)
    n_neg = len(B) * len(C)
    n_0 = O * (O - 1) // 2 + O * (len(B) + len(C))

    def find(x):
        ret = 0
        if x < 0:
            ret += np.searchsorted(C, x//B, side='right').sum()

        elif x == 0:
            ret += n_0 + n_neg
        else:
            ret += n_neg + n_0
            b_count = (B ** 2 <= x).sum()
            c_count = (C ** 2 <= x).sum()
            ret += (np.searchsorted(B, x//B, side='right').sum() - b_count) // 2

            ret += (np.searchsorted(C_abs, x//C_abs, side='right').sum() - c_count) // 2
        return ret

    high = 10 ** 18
    low = -high
    current = 0
    while high - low > 1:
        tmp = find(current)
        if tmp < K:
            low = current
        else:
            high = current

        current = (low + high) // 2

    print(high)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
"""
ブチギレチューニングタイム
"""
#!/usr/bin/env python3

import sys
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).



def main():
    def input(): return sys.stdin.readline().rstrip()
    def mi():    return map(int, input().split())
    def lmi():   return list(map(int, input().split()))


    def is_ok(pivot, k, L_positive, L_negative):
        cnt = 0
        ind = 0
        for positive_num in L_positive:
            target = pivot // positive_num
            # O(nlgn) -> O(2 * n) = O(n) に落ちている！
            while ind < len(L_negative):
                if L_negative[ind] <= target:
                    ind += 1
                else:
                    break
            cnt += ind
        # print(f"A pivot {pivot} cnt {cnt} k {k}")
        return cnt >= k


    def is_ok_handle_duplicate(pivot, k, L_positive, L_negative):
        pos_cnt = 0
        ind = len(L_positive)
        if len(L_positive) >= 2:
            for num in L_positive:
                target = pivot // num
                # target 以下の個数を求める
                # O(nlgn) -> O(2 * n) = O(n) に落ちている！
                while ind > 0:
                    if L_positive[ind - 1] > target:
                        ind -= 1
                    else:
                        break
                pos_cnt += ind
                if num ** 2 <= pivot:
                    pos_cnt -= 1
            pos_cnt //= 2
        neg_cnt = 0
        ind = len(L_negative)
        if len(L_negative) >= 2:
            for num in L_negative:
                target = pivot // num
                # target 以下の個数を求める
                # O(nlgn) -> O(2 * n) = O(n) に落ちている！
                while ind > 0:
                    if L_negative[ind - 1] > target:
                        ind -= 1
                    else:
                        break
                neg_cnt += ind
                if num ** 2 <= pivot:
                    neg_cnt -= 1
            neg_cnt //= 2
        cnt = pos_cnt + neg_cnt
        # print(f"B pivot {pivot} cnt {cnt} k {k}")
        return cnt >= k


    n, k = mi()
    L = lmi()
    L.sort()
    l_z = bisect_left(L, 0)
    r_z = bisect_right(L, 0)
    L_negative, L_zero, L_positive = L[:l_z], L[l_z:r_z], L[r_z:]

    num_pairs_negative = len(L_negative) * len(L_positive)
    num_pairs_zero = len(L_zero) * (len(L_zero) -1) // 2 + len(L_zero) * (n - len(L_zero))
    
    if k <= num_pairs_negative:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        # left = - 10 ** 18 - 1
        # 定数倍高速化
        left = L_negative[0] * L_positive[-1] - 1
        # right = 0
        # 定数倍高速化
        right = L_negative[-1] * L_positive[0] + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= num_pairs_negative + num_pairs_zero:
        print(0)
    else:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        k -= (num_pairs_negative + num_pairs_zero)
        L_negative = [- elm for elm in reversed(L_negative)]
        # left = 0
        # 定数倍高速化
        if L_negative and L_positive:
            left = min(L_negative[0] ** 2, L_positive[0] ** 2) - 1
        elif L_negative:
            left = L_negative[0] ** 2 - 1
        else:
            left = L_positive[0] ** 2 - 1
        # right = 10 ** 18 + 1
        # 定数倍高速化
        if L_negative and L_positive:
            right = max(L_negative[-1] ** 2, L_positive[-1] ** 2) + 1
        elif L_negative:
            right = L_negative[-1] ** 2 + 1
        else:
            right = L_positive[-1] ** 2 + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok_handle_duplicate(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    

if __name__ == "__main__":
    # import time
    # s = time.time()
    main()
    # print(f"elapsed {time.time() - s} sec" )


"""
ローカル環境だと PyPy くんが 1.0 秒くらいで通るケースたちがことごとく TLE なのですが...

トータルで O(60 * nlgn) -> O(60 * n) にしたところ... (lg(10^18) ~ 60)
cat sub1_02.in | pypy3 d.py
> elapsed 1.211238145828247 sec -> elapsed 0.307081937789917 sec
cat sub1_03.in | pypy3 d.py
> elapsed 1.6172709465026855 sec -> elapsed 0.41311001777648926 sec
cat sub1_04.in | pypy3 d.py
> elapsed 0.9529299736022949 sec -> elapsed 0.1954030990600586 sec
cat sub1_08.in | pypy3 d.py
> elapsed 0.7351880073547363 sec -> elapsed 0.19420194625854492 sec
爆速！
"""

Submission status: Accepted

Solution code:
# https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-02-16abc-155#toc3
# https://atcoder.jp/contests/abc155/submissions/10152895
# 写経


# 条件を満たす要素を抽出
# ndarray[条件式]

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


def main():
    import sys
    import numpy as np

    inf = 10 ** 18 + 1
    input = sys.stdin.readline

    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)

    A.sort()

    zero = A[A == 0]
    pos = A[A > 0]
    neg = A[A < 0]

    def count(x):
        """
        定数cに対して Ai*Aj<=c となる(i,j)の数え上げ
        順序制約 i<j -> 順序制約のない(i,j)からi==jの場合の個数を引いて2で割る
        iを固定して a=Ai とする
        a=0
            ax=0(<=c?),解なしまたは任意のx
        a>0
            ax<=c
            <-> x<=c/a
            <-> x<=c//a
        a<0
            ax<=c
            <-> (-a)x>=(-c)

            否定をとり,aの対候補全体=Nから引く

            (-a)x<(-c)
            <-> (-a)x<=(-c-1)
            <-> x<=(-c-1)//(-a)
        """
        cnt = 0
        if x >= 0:
            cnt += zero.size * N  # (a:=0)*v<=x
        cnt += np.searchsorted(a=A, v=x // pos, side='right').sum()  # (a:>0)*v<=x
        cnt += (N - np.searchsorted(a=A, v=(-x - 1) // (-neg), side='right')).sum()  # (a:<0)*v<=x
        cnt -= ((A * A) <= x).sum()  # i==j
        assert cnt % 2 == 0
        return cnt // 2

    ans = binary_search(
        ng=-inf,
        ok=inf,
        func=lambda x: count(x) >= K
    )

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def examA():
    C = [SI()for _ in range(3)]
    ans = C[0][0]+C[1][1]+C[2][2]
    print(ans)
    return

def examB():
    N, M = LI()
    P = [0]*N
    S = [LSI()for _ in range(M)]
    pena = 0
    ac = set()
    for p,s in S:
        p = int(p)-1
        if s=="WA":
            P[p] += 1
        else:
            if p in ac:
                continue
            ac.add(p)
            pena += P[p]

    print(len(ac),pena)
    return

def examC():
    W, H, N = LI()
    lx, rx, ly, ry = 0, W, 0, H
    A = [LI()for _ in range(N)]
    for x,y,a in A:
        if a==1:
            lx = max(lx,x)
        elif a==2:
            rx = min(rx,x)
        elif a==3:
            ly = max(ly,y)
        elif a==4:
            ry = min(ry,y)
    ans = max(0,rx-lx)*max(0,ry-ly)
    print(ans)
    return

def examD():
    N, H = LI()
    B = [0]*N
    maxa = 0
    ans = 0
    for i in range(N):
        a, B[i] = LI()
        if a>maxa:
            maxa = a
    B.sort(reverse=True)
    for b in B:
        if b<maxa:
            break
        H -= b
        ans += 1
        if H<=0:
            print(ans)
            return
    ans += -(-H//maxa)
    print(ans)
    return

def examE():
    A, B = LI()
    ans = [["#"]*100 for _ in range(50)] + [["."]*100 for _ in range(50)]
    i = 0; j = 0
    for _ in range(A-1):
        ans[i][j] = "."
        j += 2
        if j>=100:
            j = 0; i += 2
    i = 0; j = 0
    for _ in range(B-1):
        ans[99-i][j] = "#"
        j += 2
        if j>=100:
            j = 0; i += 2
    print(100,100)
    for v in ans:
        print("".join(map(str,v)))
    return

def examF():
    def search_1(need):
        l = 0; r = inf+1
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            cur += shakutori(neg,pos,now)
            #print(cur,now)
            if cur>=need:
                l = now
            else:
                r = now
            #print(cur)
        return -l
    def search_2(need):
        need *= 2
        #print(need)
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            cur += shakutori_2(neg,now)
            cur += shakutori_2(pos,now)
            if cur>=need:
                r = now
            else:
                l = now
            #print(cur,now)
        return r
    def shakutori(A,B,k):
        n = len(A)
        m = len(B)
        rep = 0
        r = 0
        for l in range(n)[::-1]:
            while(r<m-1 and A[l]*B[r]<k):
                r += 1
            if (A[l]*B[r]>=k):
                rep += m-r
        return rep
    def shakutori_2(C,k):
        n = len(C)
        rep = 0
        r = n-1
        for l in range(n):
            while(r>0 and C[l]*C[r]>k):
                r -= 1
            if (C[l]*C[r]<=k):
                rep += r+1
                if r >= l:
                    rep -= 1
        return rep
    N, K = LI()
    A = LI()
    neg = []; pos = []; arr_0 = 0
    for a in A:
        if a<0:
            neg.append(-a)
        elif a==0:
            arr_0 += 1
        else:
            pos.append(a)
    neg.sort(); pos.sort()
    #print(pos)
    if len(neg)*len(pos)>=K:
        ans = search_1(K)
    elif len(neg)*len(pos)+arr_0*(len(neg)+len(pos))+arr_0*(arr_0-1)//2>=K:
        ans = 0
    else:
        ans = search_2(K-len(neg)*len(pos)-arr_0*(len(neg)+len(pos))-arr_0*(arr_0-1)//2)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
87940638538504699
448283280358331064
"""

Submission status: Accepted

Solution code:
import numpy as np


def get_Negative(K, pos, neg):
    K = len(pos) * len(neg) - K + 1
    l = 0
    r = 10 ** 18 + 10
    while r - l > 1:
        m = (l + r) // 2
        target = m // pos
        x = np.searchsorted(neg, target, side="right").sum()
        if x >= K:
            r = m
        else:
            l = m
    return -r


def get_Positive(K, pos, neg):
    l = 0
    r = 10 ** 18 + 10
    tmp_pos = np.arange(len(pos))
    tmp_neg = np.arange(len(neg))
    while r - l > 1:
        m = (r + l) // 2
        cnt = 0
        if len(pos) > 1:
            t1 = m // pos
            x1 = np.searchsorted(pos, t1, side="right")
            x1 = np.maximum(0, x1 - tmp_pos - 1)
            cnt += x1.sum()
        if len(neg) > 0:
            t2 = m // neg
            x2 = np.searchsorted(neg, t2, side="right")
            x2 = np.maximum(0, x2 - tmp_neg - 1)
            cnt += x2.sum()
        if cnt >= K:
            r = m
        else:
            l = m
    return r


def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)

    positive = A[A > 0]
    negative = -A[A < 0]
    positive.sort()
    negative.sort()

    Npos = len(positive)
    Nneg = len(negative)
    Nzero = N - Npos - Nneg

    P_neg = Npos * Nneg
    P_pos = 0
    if Npos:
        P_pos += Npos * (Npos - 1) // 2
    if Nneg:
        P_pos += Nneg * (Nneg - 1) // 2
    P_zero = N * (N - 1) // 2 - P_pos - P_neg

    if K <= P_neg:
        ans = get_Negative(K, positive, negative)
        return ans
    K -= P_neg
    if K <= P_zero:
        return 0
    K -= P_zero
    ans = get_Positive(K, positive, negative)
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
alist=list(map(int,input().split()))
#alist.sort()
#print(alist)

def calc_leq_neg(m):
  ret=0
  j=0
  for i in range(len(alist_neg)):
    while j<len(alist_pos):
      if alist_neg[i]*alist_pos[j]<=m:
        ret+=len(alist_pos)-j
        break
      else:
        j+=1
  return ret

def calc_leq_pos(m):
  ret=0
  j=0
  alist_neg2=alist_neg[::-1]
  for i in range(len(alist_neg)):
    while j<len(alist_neg):
      if alist_neg[i]*alist_neg2[j]<=m:
        ret+=len(alist_neg)-j
        if alist_neg[i]<=alist_neg2[j]:
          ret-=1
        break
      else:
        j+=1
        
  j=0
  alist_pos2=alist_pos[::-1]
  for i in range(len(alist_pos)):
    while j<len(alist_pos):
      if alist_pos[i]*alist_pos2[j]<=m:
        ret+=len(alist_pos)-j
        if alist_pos[i]<=alist_pos2[j]:
          ret-=1
        break
      else:
        j+=1

  return ret//2

alist_neg,alist_pos=[],[]
num_neg,num_zero,num_pos=0,0,0
for a in alist:
  if a<0:
    num_neg+=1
    alist_neg.append(a)
  elif a>0:
    num_pos+=1
    alist_pos.append(a)
  else:
    num_zero+=1
alist_neg.sort()
alist_pos.sort()
    
num_neg_prod=num_neg*num_pos
num_pos_prod=((num_pos*(num_pos-1))//2)+((num_neg*(num_neg-1))//2)
num_zero_prod=(N*(N-1))//2-num_neg_prod-num_pos_prod
#print(num_neg_prod,num_zero_prod,num_pos_prod)

if K<=num_neg_prod:
  #neg
  #print(alist_neg)
  #print(alist_pos)
  l,r=alist_neg[0]*alist_pos[-1],-1
  while l<=r:
    mid=(l+r)//2
    k1=calc_leq_neg(mid-1)
    k2=calc_leq_neg(mid)
    #print(mid,k1,k2)
    if k1<K<=k2:
      print(mid)
      break
    elif k1>=K:
      r=mid-1
    else:
      l=mid+1  
elif K<=num_neg_prod+num_zero_prod:
  print(0)
else:
  #pos
  K-=num_neg_prod+num_zero_prod
  for i in range(len(alist_neg)):
    alist_neg[i]*=-1
  alist_neg.sort()  
  #print(alist_neg)
  #print(alist_pos)
  l,r=float("inf"),0
  if len(alist_neg)>=2:
    l=alist_neg[0]*alist_neg[1]
    r=alist_neg[-2]*alist_neg[-1]
  if len(alist_pos)>=2:
    l=min(l,alist_pos[0]*alist_pos[1])
    r=max(r,alist_pos[-2]*alist_pos[-1])
  #print(K,l,r)
  while l<=r:
    mid=(l+r)//2
    k1=calc_leq_pos(mid-1)
    k2=calc_leq_pos(mid)
    #print(mid,k1,k2)
    if k1<K<=k2:
      print(mid)
      break
    elif k1>=K:
      r=mid-1
    else:
      l=mid+1

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right

def cntneg(X):
    cnt,r=0,posst
    for l in range(negend):
        while r<N and A[l]*A[r]>X:
            r+=1
        cnt+=poscnt-(r-posst)
    return cnt
def cntpos(X):
    cnt,r=0,N-1
    #正のペアの数
    for l in range(posst,N):
        while l<r and A[l]*A[r]>X:
            r-=1
        cnt+=max(0,r-l)
    l=0
    for r in range(negend-1,-1,-1):
        while l<r and A[l]*A[r]>X:
            l+=1
        cnt+=max(0,r-l)
    return cnt

N,K=map(int,input().split())
A=sorted(map(int,input().split()))
negend=bisect_left(A,0);posst=bisect_right(A,0)
poscnt=N-posst;negcnt=negend;zerocnt=N-poscnt-negcnt
zeroans=zerocnt*(poscnt+negcnt)+zerocnt*(zerocnt-1)//2
posans=poscnt*(poscnt-1)//2+negcnt*(negcnt-1)//2
negans=negcnt*poscnt

if(K<=negans):
    ng,ok=-10**18,0
    while abs(ok-ng)>1:
        X=(ng+ok)//2
        if cntneg(X)>=K:
            ok=X
        else:
            ng=X
elif(K<=negans+zeroans):
    print(0)
    exit()
else:
    K-=negans+zeroans
    ng,ok=0,10**18
    while abs(ok-ng)>1:
        X=(ng+ok)//2
        if cntpos(X)>=K:
            ok=X
        else:
            ng=X
            
print(ok)