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):
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
 
negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)
 
positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)
 
negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

if K <= negative_pairs_cnt:
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)
 
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X
 
    print(ok)

elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

else:
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0
 
        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)
 
        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1
 
            or_higher_cnt += max(0, r - l)
 
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X
 
    print(ok)

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

pos = []
neg = []
zero = 0
for a in A:
    if a > 0:
        pos.append(a)
    elif a == 0:
        zero += 1
    else:
        neg.append(a)
        
len_pos = len(pos)
len_neg = len(neg)

cnt_pos = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
cnt_neg = len_pos * len_neg
cnt_zero = zero * (zero - 1) // 2 + zero * (len_pos + len_neg)


if K <= cnt_neg:
    pos.sort()
    neg.sort()
    ok = 10 ** 19
    ng = -10 ** 19
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        pos_i, neg_i = len_pos - 1, len_neg - 1
        cnt = 0
        while pos_i >= 0 and neg_i >= 0:
            if pos[pos_i] * neg[neg_i] <= mid:
                cnt += neg_i + 1
                pos_i -= 1
            else:
                if neg_i:
                    neg_i -= 1
                else:
                    pos_i -= 1
        if cnt >= K:
            ok = mid
        else:
            ng = mid
    print(ok)

elif K <= cnt_neg + cnt_zero:
    print(0)
    
else:
    K -= cnt_neg + cnt_zero
    pos.sort()
    neg = [abs(n) for n in neg]
    neg.sort()

    ok = 10 ** 19
    ng = -10 ** 19
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        left, right = 0, len_pos - 1
        cnt = 0
        while left <= len_pos - 1 and right >= 0:
            if pos[left] * pos[right] <= mid:
                cnt += right + 1
                if left <= right:
                    cnt -= 1
                left += 1
            else:
                if right:
                    right -= 1
                else:
                    left += 1

        left, right = 0, len_neg - 1
        while left <= len_neg - 1 and right >= 0:
            if neg[left] * neg[right] <= mid:
                cnt += right + 1
                if left <= right:
                    cnt -= 1
                left += 1
            else:
                if right:
                    right -= 1
                else:
                    left += 1
        cnt //= 2
        
        if cnt >= K:
            ok = mid
        else:
            ng = mid
    print(ok)

Solution (Python):
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

an = []
az = []
ap = []

for i in range(n):
    if a[i] < 0:
        an.append(a[i])
    elif a[i] == 0:
        az.append(a[i])
    else:
        ap.append(a[i])

an = sorted(an)
ap = sorted(ap)

an_rev = sorted(an, reverse=True)


def count(x):
    cnt = 0
    if x < 0:
        r = 0
        for t in ap:
            while r < len(an) and t*an[r] <= x:
                r += 1
            cnt += r
    elif x == 0:
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    else:
        r = 0
        for t in ap[::-1]:
            while r < len(ap) and t*ap[r] <= x:
                r += 1
            cnt += r
            if t*t <= x:
                cnt -= 1
        r = 0
        for t in an:
            while r < len(an) and t*an_rev[r] <= x:
                r += 1
            cnt += r
            if t*t <= x:
                cnt -= 1
        cnt //= 2
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    return cnt


bottom = -10**18-1
top = 10**18+1

while top - bottom > 1:
    mid = (top + bottom) // 2
    if count(mid) >= k:
        top = mid
    else:
        bottom = mid

print(top)

Solution (Python):
from bisect import *
n, k = map(int, input().split())
a = list(map(int, input().split()))

posi = 0
nega = 0
zero = 0
p = []
m = []

for i in range(n):
    if a[i] > 0:
        p.append(a[i])
        posi += 1
    elif a[i] < 0:
        nega += 1
        m.append(-a[i])
    else:
        zero += 1

p.sort()
m.sort()

if k <= posi*nega:
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)-1, -1, -1):
            count -= nega-bisect_left(m, (mid-1)//p[i]+1)
            if count <= 0:
                break
        if count <= 0:
            l = mid
        else:
            r = mid
        

    print(-l)

elif k <= posi*nega+zero*(zero-1)//2+zero*(posi+nega):
    print(0)

else:
    k -= posi*nega+zero*(zero-1)//2+zero*(posi+nega)
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)):
            count -= max(bisect_right(p, (mid)//p[i])-i-1, 0)
            if count < 0:
                
                break
        for i in range(len(m)):
            count -= max(bisect_right(m, (mid)//m[i])-i-1, 0)
            if count < 0:
                
                break

        if count > 0:
            l = mid
        else:
            r = mid
    print(r)

Solution (Python):

import numpy as np
N,K=map(int,input().split())
A=np.array(list(map(int,input().split())))
A.sort()
G=A[A>0]
Z=A[A==0]
L=A[A<0]

ok=10**18+1
ng=-10**18-1



while ok-ng>1:
  mid = (ng+ok)//2
  
  
  
  cg=np.searchsorted(A,mid//G,side="right").sum()
  
  
  cl=(N-np.searchsorted(A,(-mid-1)//(-L),side="right")).sum()
  
  
  d = np.count_nonzero(A*A <= mid)
  
  
  z=0
  if mid>=0:
    z += len(Z)*N
  
  c=cg+cl+z-d
  
  
  c //=2
  
  
  if c>=K:
    ok=mid
  else:
    ng=mid
    
print(ok)

Solution (Python):
import bisect, sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

pl = []
mi = []
ze = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(-x)
    else:
        ze += 1

p, m = len(pl), len(mi)
res1 = p * m
res2 = (p + m) * ze + ze * (ze - 1) // 2


if res1 >= k:
    pl.sort(reverse=True)
    mi.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = p * m
        tmp = 0
        for i in range(p):
            while tmp < m and pl[i] * mi[tmp] < x:
                tmp += 1
            cnt -= tmp
        if cnt < k:
            r = x
        else:
            l = x
    print(-l)


elif res1 + res2 >= k:
    print(0)


else:
    k = k - res1 - res2
    pl.sort(reverse=True)
    pl2 = pl[::-1]
    mi.sort(reverse=True)
    mi2 = mi[::-1]
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = 0
        tmp = 0
        for i in range(p):
            if pl[i] ** 2 <= x:
                cnt -= 1
            while tmp < p and pl[i] * pl2[tmp] <= x:
                tmp += 1
            cnt += tmp
        tmp = 0
        for i in range(m):
            if mi[i] ** 2 <= x:
                cnt -= 1
            while tmp < m and mi[i] * mi2[tmp] <= x:
                tmp += 1
            cnt += tmp

        cnt //= 2
        if cnt < k:
            l = x
        else:
            r = x
    print(r)

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

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

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

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

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


def count(x):
  cnt = 0
  
  if x >= 0:
    cnt += zeros*n 
  
  
  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

while r-l>1:
  mid = (r+l)//2
  
  if count(mid) >= k:
    r = mid
  else:
    l = mid
print(r)

Solution (Python):
import sys
n,k=map(int,input().split())
alist=list(map(int,input().split()))

posilist=[]
negalist=[]
zeronum=0

for a in alist:
    if a == 0:
        zeronum+=1
    elif a > 0:
        posilist.append(a)
    else:
        negalist.append(-a)
posilist.sort()
negalist.sort()

posinum=len(posilist)
neganum=len(negalist)

def shakutori(x,alist,blist,flag):
    sum=0
    alen=len(alist)
    blen=len(blist)

    a=0
    b=blen-1

    while a <= alen-1 and b >= 0:
        if flag and a == b:
            return sum
        if alist[a]*blist[b] <= x:
            if flag:
            	sum+= (b+1)-(a+1)
            else:
            	sum+= (b+1)
            a += 1
        else:
            b -=1
    return sum

if k <= posinum*neganum:
    k=posinum*neganum+1-k
    pnflag=False
elif k > n*(n-1)/2-posinum*(posinum-1)/2-neganum*(neganum-1)/2:
    k=k-(n*(n-1)/2-posinum*(posinum-1)/2-neganum*(neganum-1)/2)
    pnflag=True
else:
    print(0)
    sys.exit()

llim=0
ulim=10**19+1


while True:
    mid=(llim+ulim)//2
    if pnflag:
        d1=shakutori(mid,posilist,posilist,True)+shakutori(mid,negalist,negalist,True)
        d2=shakutori(mid+1,posilist,posilist,True)+shakutori(mid+1,negalist,negalist,True)
    else:
        d1=shakutori(mid,posilist,negalist,False)
        d2=shakutori(mid+1,posilist,negalist,False)
    if d1 < k <= d2:
        if pnflag:
            print(mid+1)
        else:
            print(-(mid+1))
        sys.exit()
    elif k <= d1:
        ulim = mid
    else:
        llim = mid

Solution (Python):


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)

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

Solution (Python):
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):
    
    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
        
        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:
    
    print(0)
else:
    
    print(binary_search(-10**20,5,False))

Solution (Python):
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)  
n_0 = bisect_right(a, 0) - n_m  
n_p = n - n_m - n_0  

nn_m = n_m * n_p  
nn_0 = n_0 * (n - n_0) + n_0 * (n_0 - 1) // 2  
nn_p = n * (n - 1) // 2 - nn_m - nn_0  

if k <= nn_m:
    

    def check_minus(x):
        

        

        
        
        
        
        
        
        
        

        
        
        
        
        
        
        
        
        
        

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

        return cnt >= k

    
    lb = -10**18  
    ub = -1  
    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:
    
    ans = 0
else:
    
    a_p = a[n_m + n_0:]
    a_m = [-a[i] for i in reversed(range(n_m))]

    def check_plus(x):
        
        def func(b):
            
            
            
            
            

            
            
            

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

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

    
    lb = 0  
    ub = 10**18 + 1  
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_plus(mid):
            ub = mid
        else:
            lb = mid
    ans = ub
print(ans)

Solution (Python):






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






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






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


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


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


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


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





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

Solution (Python):

import sys

sysread = sys.stdin.readline
read = sys.stdin.read


sys.setrecursionlimit(10**7)



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

Solution (Python):
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)



if K <= negative_pairs_cnt:
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2

        or_higher_cnt = 0
        r = positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)


elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)


else:
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0

        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)

        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1

            or_higher_cnt += max(0, r - l)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

Solution (Python):
"""
ブチギレチューニングタイム
"""


import sys
from bisect import bisect_left, bisect_right 



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
            
            while ind < len(L_negative):
                if L_negative[ind] <= target:
                    ind += 1
                else:
                    break
            cnt += ind
        
        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
                
                
                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
                
                
                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
        
        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 = L_negative[0] * L_positive[-1] - 1
        
        
        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)]
        
        
        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
        
        
        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__":
    
    
    main()
    


"""
ローカル環境だと 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
爆速！
"""

Solution (Python):


def solve_m(S, T, K):
    def count(x):
        ret, ti = 0, 0
        for s in S:
            
            while ti < len(T) and s * T[ti] > x:
                ti += 1
            if ti == len(T):
                break
            ret += len(T) - ti
        return ret
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid) < K:
            left = mid
        else:
            right = mid
    return right

def solve(S, mS, K):
    def count(x, T):
        ret, j = 0, len(T) - 1
        for i, t in enumerate(T):
            while j >= 0 and t * T[j] > x:
                j -= 1
            if j == -1:
                break
            ret += j + 1 - (1 if i <= j else 0)
        return ret // 2
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid, S) + count(mid, mS) < K:
            left = mid
        else:
            right = mid
    return right

def main():
    N, K = list(map(int, input().split()))
    A = sorted(map(int, input().split()), reverse=True)
    B = {-1:[], 0:[], 1:[]}
    for a in A:
        if a == 0:
            B[0].append(0)
        else:
            B[a//abs(a)].append(a)
    m = len(B[-1]) * len(B[1])
    z = len(B[0]) * (N-len(B[0])) + len(B[0]) * (len(B[0])-1) // 2
    if K <= m:
        print(solve_m(B[1], B[-1], K))
    elif K <= m + z:
        print(0)
    else:
        print(solve(sorted(B[1]), B[-1], K - m - z))


if __name__ == '__main__':
    main()