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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7

    n,k=MI()
    lis=LI()
    p,z,m=0,0,0
    plus=[]
    minus=[]
    for i in range(n):
        if lis[i]>0:
            p+=1
            plus.append(lis[i])
        elif lis[i]==0:
            z+=1
        else:
            m+=1
            minus.append(lis[i])
    plus.sort()
    minus.sort()
    
    
    
    resm=p*m
    resz=z*p+z*m+p*m+z*(z-1)//2
    if k<=resm:
        left=-10**18-1
        right=-1
        while left+1<right:
            x=(left+right)//2
            i=0
            ans=0
            j=0
            while i<p:
                while j<m:
                    if plus[i]*minus[j]<=x:
                        if j==m-1:
                            ans+=m
                            i+=1
                            break
                        j+=1
                    else:
                        i+=1
                        ans+=j
                        break
            
            if ans>=k:
                right=x
            else:
                left=x
        print(right)
    
    elif k<=resz:
        print(0)
        sys.exit()
    else:
        k=k-resz
        
        left=0
        right=10**18
        square=[]
        for i in range(p):
            square.append(plus[i]**2)
        for i in range(m):
            minus[i]*=(-1)
            square.append(minus[i]**2)
        square.sort()
        plus.sort()
        minus.sort()
        plus2=sorted(plus,reverse=True)  
        minus2=sorted(minus,reverse=True)
        while left+1<right:
            x=(left+right)//2
            i=0
            ans=0
            j=0
            zure=bisect_right(square,x)-1
            while i<p:
                while j<p:
                    if plus2[i]*plus[j]<=x:
                        if j==p-1:
                            ans+=p
                            i+=1
                            break
                        j+=1
                    else:
                        i+=1
                        ans+=j
                        break
            i=0
            j=0
            while i<m:
                while j<m:
                    if minus2[i]*minus[j]<=x:
                        if j==m-1:
                            ans+=m
                            i+=1
                            break
                        j+=1
                    else:
                        i+=1
                        ans+=j
                        break
            
            if (ans-zure)//2>=k:
                right=x
            else:
                left=x
        print(right)
            
if __name__=="__main__":
    main()

Solution (Python):
import decimal


def solve_gutyoku(N, K, A):
    A_combinations = []
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            A_combinations.append(A[i] * A[j])
    ans = sorted(A_combinations)[K-1]
    return ans


def solve(N, K, A):
    for i, a in enumerate(A):
        if a >= 0:
            break
    for j, a in enumerate(A):
        if a > 0:
            break
    A_hu = A[:i]
    A_0 = A[i:j]
    A_sei = A[j:]
    n_hu = len(A_hu)*len(A_sei)
    n_0 = len(A_0)*(len(A)-1) - len(A_0)*(len(A_0)-1)//2
    n_sei = (len(A_sei) - 1) * len(A_sei) // 2 + \
        (len(A_hu) - 1) * len(A_hu) // 2
    if K > n_hu and K <= n_hu + n_0:
        return 0
    elif K <= n_hu:
        left, right = int(-1 * 1e18), 0
        while right - left > 1:
            piv = (left + right) // 2
            cnt = 0
            i = 0
            for a in A_sei:
                while i < len(A_hu) and A_hu[i] * a <= piv:
                    i += 1
                cnt += i
            if cnt >= K:
                right = piv
            else:
                left = piv
        return right
    else:
        A_hu = [-1 * a for a in A_hu[::-1]]
        K -= n_hu + n_0
        left, right = 0, int(1e18) + 1
        while right - left > 1:
            piv = (left + right) // 2
            cnt = 0
            i = 0
            for a in A_sei[::-1]:
                while i < len(A_sei) and A_sei[i] * a <= piv:
                    i += 1
                cnt += i - (a * a <= piv)
            i = 0
            for a in A_hu[::-1]:
                while i < len(A_hu) and A_hu[i] * a <= piv:
                    i += 1
                cnt += i - (a * a <= piv)
            cnt = cnt // 2
            if cnt >= K:
                right = piv
            else:
                left = piv
        return right


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    ans = solve(N, K, A)
    print(ans)



main()

Solution (Python):
N,K=map(int,input().split())
A=sorted(map(int,input().split()))
x=0
r=10**18+1
l=-(10**18)
while l+1<r:
    x=(l+r)//2
    k=0
    for a in A:
        if a<0:
            ll,rr=-1,N
            while ll+1<rr:
                c=(rr+ll)//2
                if x>a*A[c]:
                    rr=c
                else:
                    ll=c
            k+=N-rr
        else:
            ll,rr=-1,N
            while ll+1<rr:
                c=(rr+ll)//2
                if x>a*A[c]:
                    ll=c
                else:
                    rr=c
            k+=rr
        if x>a**2:
            k-=1
    k//=2
    if k<K:
        l=x
    else:
        r=x
print(l)

Solution (Python):
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]

l = - 10**19
r = 10**19


while r - l > 1:
  mid = (l+r)//2
  
  cnt = 0
  
  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)
  
  cnt += len(a_zero)*n if mid >= 0 else 0
  
  
  cnt //= 2
  
  if cnt >= k:
    r = mid
  else:
    l = mid
  
print(r)

Solution (Python):
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):
        
        cnt = 0
        for i, a in enumerate(A):
            
            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

    
    while rb - lb > 1:
        mid = (rb + lb) // 2
        if check(mid):
            rb = mid
        else:
            lb = mid
    print(rb)


solve(N, K, A)

Solution (Python):
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()

Solution (Python):

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)


plus_cnt = N - plus_left
minus_cnt = minus_right
zero_cnt = N - (plus_cnt + minus_cnt)


minus_pairs_cnt = plus_cnt * minus_cnt

zero_pairs_cnt = plus_cnt * zero_cnt + minus_cnt * zero_cnt + zero_cnt * (zero_cnt - 1) // (2 * 1)

if K <= minus_pairs_cnt:
  
  
  
  low = -10 ** 18 
  high = 0 
  ans = 0
  while abs(high - low) > 1:
    mid = (low + high) // 2
    cnt = 0
    
    r = plus_left 
    for l in range(minus_right):
      
      
      
      
      while r < N and A[l]*A[r] > mid:
        r += 1
      cnt += plus_cnt - (r - plus_left)
    if cnt >= K:
      high = mid 
    else:
      low = mid
    
  print(high) 
elif K <= minus_pairs_cnt + zero_pairs_cnt:
  
  
  print(0)
else:
  
  
  
  
  low = 0 
  high = 10 ** 18 
  ans = 0
  
  while abs(high - low) > 1:
    mid = (low + high) // 2
    cnt = 0
    
    
    r = N-1
    for l in range(plus_left, N):
      
      
      
      
      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):
      
      
      
      
      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)

Solution (Python):
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
am=[]
ap=[]
zc=0
for i in a:
  if i<0:
    am.append(i)
  elif i>0:
    ap.append(i)
  else:
    zc+=1
am.sort()
ap.sort()

def count(n,m,p,z):
  mx=-10**20
  lm=len(m)
  lp=len(p)
  if n==0:
    if z or (lm and lp):
      return (lm*lp+(lm+lp)*z+(z*(z-1))//2,0 if z else m[-1]*p[0])
    else:
      return (0,0)
  elif n<0:
    r=0
    j=0
    for i in m:
      while j<len(p) and i*p[j]>n:
        j+=1
      if j<len(p) and mx<i*p[j]:
         mx=i*p[j]
      r+=len(p)-j
    return (r,mx)
  else:
    if z or (lm and lp):
      mx=0 if z else m[-1]*p[0]
    r=lm*lp+(lm+lp)*z+(z*(z-1))//2
    j=lp-1
    for i in range(lp):
      while j>i and p[i]*p[j]>n:
        j-=1
      if j>i and p[i]*p[j]>mx:
        mx=p[i]*p[j]
      r+=j-i
      if i==j:
        break
    j=lm-1
    for i in range(lm):
      while j>i and m[i]*m[j]<=n:
        j-=1
      if i>j:
        j=i
      if j<lm-1 and m[i]*m[j+1]>mx:
        mx=m[i]*m[j+1]
      r+=lm-j-1
    return (r,mx)

r=10**18
t=0
s=set()

while True:
  ret=count(t,am,ap,zc)
  
  
  if ret[0]<k:
    s.add(t)
    t+=r
    r=(r+1)//2
  elif ret[0]==k:
    print(ret[1])
    break
  else:
    if t in s:
      print(ret[1])
      break
    s.add(t)
    t-=r
    r=(r+1)//2

Solution (Python):
import sys
from itertools import count

def f(plus, minus, zero, val):
    t = 0
    if val > 0:
        t += len(plus) * len(minus) + zero * (len(plus) + len(minus)) + zero * (zero - 1) // 2
        
        if len(plus) >= 2:
            right_index = len(plus) -1
            for left_index, left in enumerate(plus):
                while left_index < right_index and left * plus[right_index] > val:
                    right_index -= 1
                t += max(0, right_index - left_index)
                
        if len(minus) >= 2:
            left_index = 0
            for right_index, right in zip(count(len(minus) - 1, -1), reversed(minus)):
                while left_index < right_index and minus[left_index] * right > val:
                    left_index += 1
                t += max(0, right_index - left_index)
                
    elif val < 0:
        if plus:
            plus_index = 0
            for m in minus:
                while plus_index < len(plus) and plus[plus_index] * m > val:
                    plus_index += 1
                t += len(plus) - plus_index
                
    else:
        t += len(plus) * len(minus) + zero * (len(plus) + len(minus)) + zero * (zero - 1) // 2
        
    
    return t


def resolve(in_):
    N, K = map(int, in_.readline().split())
    plus = []
    minus = []
    zero = 0
    for a in map(int, in_.readline().split()):
        if a > 0:
            plus.append(a)
        elif a < 0:
            minus.append(a)
        else:
            zero += 1

    plus.sort()
    minus.sort()

    ng = -(10 ** 18) - 1
    ok = 10 ** 18
    while ok - ng > 1:
        mid = (ok + ng) // 2
        

        if f(plus, minus, zero, mid) >= K:
            ok = mid
        else:
            ng = mid

    
    return ok


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
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 = 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

    
    B = A.copy()
    B = -B
    B.sort()
    cnt_tpl += np.searchsorted(B, x // (-neg), side='right').sum()

    
    if x >= 0:
        cnt_tpl += len(zero) * N

    
    cnt_tpl += np.searchsorted(A, x // pos, side='right').sum()

    
    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)

Solution (Python):
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):
    
    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:
        
        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()

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))

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

Solution (Python):
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


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)


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)

Solution (Python):
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:
    
    
    
    ok = -10**20  
    ng = 0
    

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

        count += i_an + 1
        
      
      if count < K:
        ok = x
      else:
        ng = x
    return ng
  elif K <= cn * cp + cz * (cp + cn) + (cz - 1 )* cz //2:
    
    return 0
  else:
    
    
    K -=  cn * cp + cz * (cp + cn) + (cz - 1 )* cz //2
    
    ok = 0
    ng = 10**20  
    

    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]):
          
          while i_ap+1 < len(Aa) and Aa[i_ap+1] * a <= x:
            i_ap += 1
          count += i_ap + 1
          count -= i <= i_ap
          
      count //= 2
      
      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))

Solution (Python):

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:
    
    ub = 10 ** 18 + 1
    lb = 0
    while ub - lb > 1:
        mid = (ub + lb) // 2

        
        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:
    
    ub = 10 ** 18 + 1
    lb = 0
    while ub - lb > 1:
        mid = (ub + lb) // 2
        cnt = 0

        
        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

        
        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

        
        cnt //= 2

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

    print(lb)

Solution (Python):
def abc155_d():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    from bisect import bisect_left, bisect_right
    lower = -10**18
    upper = 10**18
    while upper - lower > 1:
        x = (upper + lower) // 2
        cnt = 0
        for i in range(n-1):
            a = A[i]
            if a < 0:
                idx = bisect_left(A, (x+a+1)//a)
                cnt += n - max(idx, i+1)
            elif a > 0:
                idx = bisect_right(A, x//a)
                cnt += max(0, idx - i - 1)
            else:  
                if x >= 0:
                    cnt += n - i - 1
            if cnt >= k: break
        if cnt >= k: upper = x
        else: lower = x
    print(upper)

if __name__ == '__main__':
    abc155_d()

Solution (Python):
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): 
    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

Solution (Python):

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()

Solution (Python):
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))

Solution (Python):
"""
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)