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

def main():
    N, K =  [int(i) for i in input().split()]
    A =  sorted(list(map(int, input().split())))

    nega_end = bisect_left(A, 0)
    posi_start = bisect_right(A, 0)

    posi_cnt = N - posi_start
    nega_cnt = nega_end
    zero_cnt = N - (posi_cnt + nega_cnt)

    nega_pairs_cnt = posi_cnt * nega_cnt
    zero_pairs_cnt = zero_cnt * (posi_cnt + nega_cnt) + (zero_cnt * (zero_cnt-1) // 2)

    if K <= nega_pairs_cnt:
        ok, ng = 0, -10 ** 18

        while abs(ok - ng) > 1:

            X = (ok + ng) // 2
            or_higher_cnt, r = 0, posi_start

            for l in range(nega_end):
                while (r < N) and (A[l] * A[r] > X):
                    r += 1
                or_higher_cnt += posi_cnt - (r - posi_start)

            if or_higher_cnt >= K:
                ok = X
            else:
                ng = X
            
        print(ok)

    elif nega_pairs_cnt < K <= nega_pairs_cnt + zero_pairs_cnt:
        print(0)
        return
    else:
        K -= (nega_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(posi_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(nega_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)
if __name__ == "__main__":
    main()

Solution (Python):



import numpy as np
n, k = map(int,input().split())
a = np.array(list(map(int,input().split())))
a.sort()
posi = a[a>0]
zero = a[a==0]
nega = a[a<0]


l = -10**18-1
r = 10**18+1
while r-l > 1:
    mid = (r+l)//2
    cnt = 0
    if mid >= 0:
        cnt += len(zero)*n

    
    

    cnt += a.searchsorted(mid//posi, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//nega), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt //= 2
    
    
    
    
    
    
    
    
    if cnt >= k:
        r = mid
    else:
        l = mid
print(r)

Solution (Python):
import sys
import bisect
iuput=sys.stdin.readline
n,k=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
s=bisect.bisect_left(A,0,lo=0,hi=len(A))
t=bisect.bisect_right(A,0,lo=0,hi=len(A))
An=A[0:s]
Ap=A[t:n]
if k<=s*(n-t):
  
  ng=-10**19
  ok=1
  while ok-ng!=1:
    
    mid=(ok+ng)//2
    c=0
    j=0
    for i in range(s):
      if j<n-t:
        while An[i]*Ap[j]>mid:
          j=j+1
          if j==n-t:
            break
      if An[i]*Ap[-1]>mid:
        j=n-t
      c=c+(n-t-j)
    if c<k:
      ng=mid
    else:
      ok=mid
  print(ok)
elif k<=n*(n-1)//2-((n-t)*(n-t-1)//2)-s*(s-1)//2:
  print(0)
else:
  k=n*(n-1)//2-k+1
  Ann=[0]*s
  for i in range(s):
    Ann[i]=An[i]*-1
  Ann=Ann[::-1]
  App=[0]*(n-t)
  for i in range(n-t):
    App[i]=Ap[i]*-1
  App=App[::-1]
  ng=-10**19
  ok=1
  while ok-ng!=1:
    
    mid=(ok+ng)//2
    c=0
    j=0
    for i in range(s):
      if j<s:
        while An[i]*Ann[j]>mid:
          j=j+1
          if j==s:
            break
      if An[i]*Ann[-1]>mid:
        j=s
      c=c+(s-j)
    cc=0
    for i in range(s):
      if An[i]*A[i]*-1<=mid:
        cc=cc+1
    j=0
    for i in range(n-t):
      if j<n-t:
        while App[i]*Ap[j]>mid:
          j=j+1
          if j==n-t:
            break
      if App[i]*Ap[-1]>mid:
        j=n-t
      c=c+(n-t-j)
    for i in range(n-t):
      if Ap[i]*Ap[i]*-1<=mid:
        cc=cc+1
    c=(c-cc)//2
    if c<k:
      ng=mid
    else:
      ok=mid
  print(-1*ok)

Solution (Python):
import numpy as np

def count_pair(x):
    cnt = 0
    cnt += (n-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        cnt += len(A_zero)*n
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt

n, k = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < k:
        l = c
    else:
        r = c
print(l)

Solution (Python):
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = np.sort(A)

G = A[A > 0]
Z = A[A == 0]
L = A[A < 0]

l, r = 10**18, -10**18

while l-r > 1:
  
  m = (l+r) // 2

  
  Pk = np.searchsorted(A, m//G, side="right").sum()

  
  Nk = (N - np.searchsorted(A, (-m-1)//(-L), side="right")).sum()

  
  duplicate = np.count_nonzero(A*A <= m)

  
  Zk = 0
  if m >= 0:
    Zk += len(Z) * N

  
  k = Pk + Nk + Zk - duplicate
  
  
  k //= 2

  
  if k >= K:
    l = m
  else:
    r = m

print(l)

Solution (Python):
from bisect import *
from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = []
Am = []
for a in A:
    if a >= 0:
        Ap.append(a)
    elif a < 0:
        Am.append(a)
p = len(Ap)
m = len(Am)
Ap.sort()
Am.sort(reverse=True)
U = 10 ** 18
L = - 10 ** 18
while U - L > 1:
    mid = (U+L)//2
    cnt = 0
    if mid >= 0:
        cnt += p*m
        i = p
        t = 0
        for a in Ap:
            while i and Ap[i-1] * a > mid:
                i -= 1
            t += i
            if a*a <= mid:
                t -= 1
        cnt += t//2
        i = m
        t = 0
        for a in Am:
            while i and Am[i-1] * a > mid:
                i -= 1
            t += i
            if a*a <= mid:
                t -= 1
        cnt += t//2
    else:
        i = m
        for a in Ap:
            while i and Am[i-1] * a <= mid:
                i -= 1
            cnt += m - i   
    if cnt < K:
        L = mid
    else:
        U = mid
print(U)

Solution (Python):
'''たのん「決め打ち2分探索」
各ペアの積を順番に並べたときのK番目の値を愚直に計算すると、
積の計算にO(N^2)、それらの値をソートするのにO(N^2logN)かかってしまう。
そこで考え方を変え、勝手に決めた値XがK番目の値になるかどうかを
判定することを考えてみます。
勝手に決めた値Xよりも積が小さくなるペアの個数を数え、
それがK個以上であればK番目の値はXより小さく、
K個未満であればK番目の値はXより大きいことが分かります。
1回の判定にかかる計算量は、2数の積の片方を決めたとき
もう片方として取ってこられる個数をしゃくとり法によって求めると
トータルO(N)、2分探索によって求めると1要素あたりの計算量がO(logN)なので
トータルO(NlogN)となります。
また判定を行う回数は、制約より0<=|Ai|<=10^9なので、
初期値として0と10^18+1を与えれば十分で、
判定の回数は高々log(10^18)回程度だと分かります。
今回の制約は-10^9<=Ai<=10^9より、
小さい方からK番目の要素の値が負になるか、それとも0になるか、
それとも正になるかで場合分けをして考える必要があります。
まずK番目の要素の値が負になる場合、2数の積の組み合わせとしては、
(負の数)x(正の数)のみがあり得ます。
このときは、負の数からある要素を取ってきたときもう片方として
正の数から取ってこられる個数を求めればよいです。
ただし以下の実装では負数のマイナスを取って計算しているため
2数の積の大小が逆転し、(負の数)x(正の数)の小さいほうからK番目の数は、
(負の数の絶対値)x(正の数)の小さいほうから
(負の数の個数-K)番目の数(=大きいほうからK番目の数)に相当します。
次にK番目の要素の値が正になる場合、2数の積の組み合わせとしては、
(負の数)x(負の数)と(正の数)x(正の数)の2つがあり得ます。
このときは、負の数からある要素を取ってきたとき
もう片方として負の数から取ってこられる個数と、
正の数からある要素を取ってきたとき、もう片方として正の数から
取ってこられる個数をそれぞれ求めて足し合わせればよいです。
ただし、同じ要素を2回選ぶ場合が含まれてしまっていることと、
そして各ペアが2回数えられることに注意し、個数を修正する必要があります。
'''

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
for i in range(n): 
 if arr[i]<0:
   nc+=1
 elif arr[i]==0:
   zc+=1
 else:
   pc+=1
ncc=nc*pc 
zcc=zc*(nc+pc)+(zc*(zc-1))//2 
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2 
if k<=ncc: 
 arr1=[]
 arr2=[]
 for i in range(n): 
   if arr[i]<0:
     arr1.append(-arr[i])
   elif arr[i]>0:
     arr2.append(arr[i])
 arr1=arr1[::-1]
 c1=len(arr1)
 c2=len(arr2)
 l=0
 r=10**18+1
 k=ncc-k 
 while r-l!=1:
   mid=(l+r)//2
   cnt=0
   pos=c2-1
   for i in range(c1): 
     while pos!=-1:
       if arr2[pos]>mid//arr1[i]:
         pos-=1
       else:
         break        
     cnt+=pos+1
   if cnt>k: 
     r=mid
   else: 
     l=mid
 print(-r) 
elif k<=(ncc+zcc): 
 print(0)
else: 
 arr1=[]
 arr2=[]
 for i in range(n): 
   if arr[i]<0:
     arr1.append(-arr[i])
   elif arr[i]>0:
     arr2.append(arr[i])
 arr1=arr1[::-1]
 c1=len(arr1)
 c2=len(arr2)
 l=0
 r=10**18+1
 k-=(ncc+zcc) 
 while r-l!=1:
   mid=(l+r)//2
   cnt1=0
   pos1=c1-1
   for i in range(c1): 
     tmp=0
     while pos1!=-1:
       if arr1[pos1]>mid//arr1[i]:
         pos1-=1
       else:
         break
     tmp+=pos1+1
     if arr1[i]**2<mid: 
       tmp-=1
     cnt1+=tmp
   cnt1=cnt1//2 
   cnt2=0
   pos2=c2-1
   for i in range(c2): 
     tmp=0
     while pos2!=-1:
       if arr2[pos2]>mid//arr2[i]:
         pos2-=1
       else:
         break
     tmp+=pos2+1
     if arr2[i]**2<mid:
       tmp-=1 
     cnt2+=tmp
   cnt2=cnt2//2 
   cnt=cnt1+cnt2
   if cnt>=k: 
     r=mid
   else: 
     l=mid
 print(r)

Solution (Python):
import numpy as np

def check(mid):
  cnt=0
  if mid>=0:
    cnt+=len(zero)*N
  cnt+=np.searchsorted(A, mid//pos, side="right").sum()
  cnt+=(N-np.searchsorted(A, (-mid-1)//(-neg), side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  return cnt//2

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

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

high=10**18
low=-10**18
while low+1<high:
  mid=(high+low)//2
  if check(mid)>=K:
    high=mid
  else:
    low=mid
print(high)

Solution (Python):
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

def comb(n, k):
	p, q = 1, 1
	for i in range(1, k+1):
		p = p * (n-i+1)
		q = q * i
	return p // q

def binsearch(l, r, f):
	while r - l > 1:
		c = (r + l) // 2
		if f(c):
			r = c
		else:
			l = c
	return r

N, K = rl()
A = rl()

pos = 0
neg = 0
zero = 0
Ap = []
An = []
for a in A:
	if a > 0:
		pos += 1
		Ap.append(a)
	elif a < 0:
		neg += 1
		An.append(a)
	else:
		zero += 1
Ap.sort()
An.sort()
n_pos = comb(pos, 2) + comb(neg, 2)
n_neg = pos * neg
n_zero = zero*(N-zero) + comb(zero, 2)

def num_gt(A, x):
	j = len(A) - 1
	cnt = 0
	for i in range(len(A)):
		while i < j and A[i] * A[j] > x:
			j -= 1
		if i >= j:
			break
		cnt += max(j - i, 0)
	return cnt

def num_gt2(A, B, x):
	j = len(B) - 1
	cnt = 0
	for i in reversed(range(len(A))):
		while j >= 0 and A[i] * B[j] > x:
			j -= 1
		if j < 0:
			break
		cnt += max(j+1, 0)
	return cnt

def check_plus(x):
	cnt = n_neg + n_zero
	cnt += num_gt(Ap, x)
	cnt += num_gt(list(reversed(An)), x)
	return cnt >= K

def check_minus(x):
	cnt = num_gt2(Ap, An, x)
	return cnt >= K

ans = 0
if K <= n_neg:
	l = An[0] * Ap[-1] - 1
	r = 0
	ans = binsearch(l, r, check_minus)
elif K <= n_neg + n_zero:
	ans = 0
else:
	l = 0
	r = 1
	if len(Ap) >= 2:
		r = max(r, Ap[-1] * Ap[-2]) + 1
	if len(An) >= 2:
		r = max(r, An[0] * An[1]) + 1
	ans = binsearch(l, r, check_plus)
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
np,nn=len(ap),len(an)
def fminus(x):
  j=0
  cnt=0
  for i in range(np):
    cnt+=j
    while j<nn and an[j]*ap[i]>=x:
      j+=1
      cnt+=1
  return cnt
def fplus(x,length,lis):
  r=length-1
  cnt=0
  for l in range(length):
    while lis[r]*lis[l]>x:
      if r==l:
        break
      r-=1
    if r==l:
      break
    elif lis[r]*lis[l]<=x:
      cnt+=r-l
  return cnt
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  
  
  if k<=np*nn:
    an.sort(reverse=True)
    ap.sort()
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      if fminus(mid)>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    an.sort()
    ap.sort()
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    
    ok=10**18
    ng=0
    
    while ok-ng>1:
      mid=(ok+ng)//2
      if fplus(mid,nn,an)+fplus(mid,np,ap)>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

Solution (Python):
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n, k = MI()

a = np.array(sorted([int(i) for i in input().split()]))

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


l = -10 ** 18 - 1
r = 10 ** 18 + 1
while r - l > 1:
    mid = (r + l) // 2
    cnt = 0
    if mid >= 0:
        cnt += len(zero) * n
 
    cnt += a.searchsorted(mid // pos, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid // neg), side="left")).sum()
    cnt -= np.count_nonzero(a * a <= mid)
    cnt //= 2
    if cnt >= k:
        r = mid
    else:
        l = mid

print(r)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def solve_negative():
        ok = -1
        ng = -(10 ** 18)
        a_neg_desc = a_neg[::-1]
        a_pos_desc = a_pos[::-1]

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            pidx = 0
            count = 0
            for elem_neg in a_neg_desc:
                while pidx < pos_cnt:
                    elem_pos = a_pos_desc[pidx]
                    prod = elem_neg * elem_pos
                    if prod > mid:
                        break
                    else:
                        pidx += 1
                count += pidx
            if count >= k:
                ok = mid
            else:
                ng = mid

        print(ok)

    def solve_positive():
        kp = k - (prod_neg_cnt + prod_zer_cnt)
        ok = 10 ** 18
        ng = 0
        a_neg_desc = a_neg[::-1]
        a_pos_desc = a_pos[::-1]

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            pidx = 0
            nidx = 0
            count = 0
            for i, elem_pos1 in enumerate(a_pos_desc):
                while pidx < pos_cnt:
                    elem_pos2 = a_pos[pidx]
                    prod = elem_pos1 * elem_pos2
                    if prod > mid:
                        break
                    else:
                        pidx += 1
                count += min(pidx, pos_cnt - (i + 1))

            for i, elem_neg1 in enumerate(a_neg):
                while nidx < neg_cnt:
                    elem_neg2 = a_neg_desc[nidx]
                    prod = elem_neg1 * elem_neg2
                    if prod > mid:
                        break
                    else:
                        nidx += 1
                count += min(nidx, neg_cnt - (i + 1))

            if count >= kp:
                ok = mid
            else:
                ng = mid

        print(ok)

    import bisect
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    neg_cnt = bisect.bisect_left(a, 0)
    zer_cnt = bisect.bisect_left(a, 1) - neg_cnt
    pos_cnt = n - (neg_cnt + zer_cnt)

    prod_neg_cnt = neg_cnt * pos_cnt
    prod_pos_cnt = (neg_cnt * (neg_cnt - 1) + pos_cnt * (pos_cnt - 1)) // 2
    prod_zer_cnt = ((n * (n - 1)) // 2) - (prod_neg_cnt + prod_pos_cnt)

    a_neg = a[:neg_cnt]
    a_pos = a[(n - pos_cnt):]

    if k <= prod_neg_cnt:
        solve_negative()
    elif k <= (prod_neg_cnt + prod_zer_cnt):
        print(0)
    else:
        solve_positive()


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, k = map(int, readline().split())
a = np.array(list(map(int, readline().split())), np.int64)
a = np.sort(a)
z = a[a == 0]
p = a[a > 0]
m = a[a < 0]


def check(mid):
    cnt = 0
    
    if mid >= 0:
        cnt += len(z) * n
    cnt += np.searchsorted(a, mid // p, side='right').sum()
    cnt += (n - np.searchsorted(a, (-mid - 1) // (-m), side='right')).sum()
    cnt -= np.count_nonzero(a * a <= mid)
    return cnt // 2


left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    mid = (left + right) // 2
    if check(mid) >= k:
        right = mid
    else:
        left = mid
print(right)

Solution (Python):
n, k = map(int, input().split())
nums = list(map(int, input().split()))

neg_nums = []
pos_nums = []
nums.sort()
for num in nums:
    if num < 0:
        neg_nums.append(num)
    else:
        pos_nums.append(num)
l = -1231232132131232112213
r = 12312321321312312312


def cost_k(m):
    cur_k = 0
    l_pos, r_pos = 0, len(pos_nums) - 1
    while l_pos < r_pos:
        if pos_nums[l_pos] * pos_nums[r_pos] <= m:
            cur_k += r_pos - l_pos
            l_pos += 1
        else:
            r_pos -= 1
    l_neg, r_neg = 0, len(neg_nums) - 1
    while l_neg < r_neg:
        if neg_nums[l_neg] * neg_nums[r_neg] <= m:
            cur_k += r_neg - l_neg
            r_neg -= 1
        else:
            l_neg += 1
    l_pos, l_neg = 0, 0
    while l_pos < len(pos_nums) and l_neg < len(neg_nums):
        if neg_nums[l_neg] * pos_nums[l_pos] <= m:
            cur_k += len(pos_nums) - l_pos
            l_neg += 1
        else:
            l_pos += 1
    return cur_k


while r - l > 1:
    m = (r + l) // 2
    
    
    
    cur_k = cost_k(m)
    if cur_k < k:
        l = m
    else:
        r = m
print(r)

Solution (Python):
import sys
readline=sys.stdin.readline

import numpy as np

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

nega_list=A[A<0]
posi_list=A[A>0]
zero_num=A[A==0].size

nega_list=np.sort(nega_list)
posi_list=np.sort(posi_list)

nega_cnt=nega_list.size * posi_list.size
posi_cnt=((posi_list.size * posi_list.size-1) // 2) + ((nega_list.size * nega_list.size-1) // 2)

zero_cnt=(zero_num * (zero_num-1)) // 2 + zero_num * (nega_list.size + posi_list.size)


if K <= nega_cnt:
  
  
  
  def isOkNega(x):
    return np.searchsorted(nega_list,x//posi_list,side="right").sum() >= K
    
  ok=0
  ng=-10**18-1
  while (ok-ng)>1:
    mid=(ok+ng)//2
    if isOkNega(mid):
      ok=mid
    else:
      ng=mid
  print(ok)
  
elif K <= nega_cnt+zero_cnt:
  
  print(0)
  
else:  
  
  K-=(nega_cnt+zero_cnt)
  
  
  
  nega_list = np.flipud(nega_list * (-1))
  
  
  self_nega=nega_list * nega_list
  self_posi=posi_list * posi_list
  
  def isOkPosi(x):
    
    nega_all = np.searchsorted(nega_list, x // nega_list, side = "right")
    
    
    nega_cnt = nega_all.sum() - self_nega[self_nega <= x].size
    
    
    nega_cnt //= 2
    
    
    posi_all = np.searchsorted(posi_list, x // posi_list, side = "right")
    posi_cnt = posi_all.sum() - self_posi[self_posi <= x].size
    posi_cnt //= 2
        
    return nega_cnt + posi_cnt >= K
  
  ok=10**18+1
  ng=0
  while abs(ok-ng)>1:
    mid=abs(ok+ng)//2
    if isOkPosi(mid):
      ok=mid
    else:
      ng=mid
  print(ok)

Solution (Python):
import sys
readline=sys.stdin.readline

import numpy as np

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

nega_list=A[A<0]
posi_list=A[A>0]
zero_num=A[A==0].size





nega_list=np.sort(nega_list)
posi_list=np.sort(posi_list)

nega_cnt=nega_list.size * posi_list.size
posi_cnt=((posi_list.size * posi_list.size-1) // 2) + ((nega_list.size * nega_list.size-1) // 2)

zero_cnt=(zero_num * (zero_num-1)) // 2 + zero_num * (nega_list.size + posi_list.size)







if K <= nega_cnt:
  
  
  
  def isOkNega(x):
    return np.searchsorted(nega_list,x//posi_list,side="right").sum() >= K
    
  ok=0
  ng=-10**18-1
  while (ok-ng)>1:
    mid=(ok+ng)//2
    if isOkNega(mid):
      ok=mid
    else:
      ng=mid
  print(ok)
  
elif K <= nega_cnt+zero_cnt:
  
  print(0)
  
else:  
  
  K-=(nega_cnt+zero_cnt)
  
  
  
  nega_list = np.flipud(nega_list * (-1))
  
  
  self_nega=nega_list * nega_list
  self_posi=posi_list * posi_list
  
  def isOkPosi(x):
    
    
    nega_all = np.searchsorted(nega_list, x // nega_list, side = "right")
    
    
    
    nega_cnt = nega_all.sum() - self_nega[self_nega <= x].size
    
    
    
    nega_cnt //= 2
    
    
    posi_all = np.searchsorted(posi_list, x // posi_list, side = "right")
    
    
    posi_cnt = posi_all.sum() - self_posi[self_posi <= x].size
    
    posi_cnt //= 2
        
    return nega_cnt + posi_cnt >= K
  
  ok=10**18+1
  ng=0
  while abs(ok-ng)>1:
    mid=abs(ok+ng)//2
    if isOkPosi(mid):
      ok=mid
    else:
      ng=mid
  print(ok)

Solution (Python):
import numpy as np

n, k = [int(i) for i in input().split()]
a = np.array(sorted([int(i) for i in input().split()]))
posi = a[a > 0]
zero = a[a == 0]
nega = a[a < 0]


l = -10 ** 18 - 1
r = 10 ** 18 + 1
while r - l > 1:
    mid = (r + l) // 2
    cnt = 0
    if mid >= 0:
        cnt += len(zero) * n

    cnt += a.searchsorted(mid // posi, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid // nega), side="left")).sum()
    cnt -= np.count_nonzero(a * a <= mid)
    cnt //= 2
    if cnt >= k:
        r = mid
    else:
        l = mid
print(r)

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

A = sorted(A)

B = []
C = []
D = []

for i in range(len(A)):
  if A[i] < 0:
    B.append(A[i])
  elif A[i] == 0:
    C.append(A[i])
  else:
    D.append(A[i])

b = len(B)
c = len(C)
d = len(D)

def f(n):
  if n < 0:
    i = 0
    j = 0
    k = 0
    while i < b and j < d:
      if B[i]*D[j] > n:
        j += 1
      else:
        i += 1
        k += d-j
    return k
  
  elif n == 0:
    return (c*(c-1))//2 + b*c + b*d + c*d
  
  else:
    i = 0
    j = b-1
    k = 0
    while i < b and j > -1:
      if B[i]*B[j] > n:
        i += 1
        k += j+1
      else:
        j -= 1
    
    k = b**2-k
    
    i = 0
    j = d-1
    while i < d and j > -1:
      if D[i]*D[j] <= n:
        i += 1
        k += j+1
      else:
        j -= 1
        
    l = 0   
    for i in range(b):
      if B[i]**2 <= n:
        l += 1
        
    for i in range(d):
      if D[i]**2 <= n:
        l += 1
        
    return (k-l)//2 + (c*(c-1))//2 + b*c + b*d + c*d
  
l = - 10**18
h = 10**18

while l+1 < h:
  m = (l+h)//2
  if f(m) >= K:
    h = m
  else:
    l = m

print(h)

Solution (Python):
import numpy as np
n,k = map(int,input().split())
a = np.array(list(map(int,input().split())))
a.sort()
posi = a[a>0]
zero = a[a==0]
nega = a[a<0]

def cnt(x):
    c = 0
    if x >= 0:
        c += len(zero)*n
    c += np.searchsorted(a, x // posi, side = 'right').sum()
    c += (n-np.searchsorted(a, (- x - 1) // (-nega), side = 'right')).sum()
    c -= np.count_nonzero(a * a <= x)
    return c // 2

l = - 10 ** 18
r = 10 ** 18
while l + 1 < r:
    m = (l + r) // 2
    if cnt(m) < k:
        l = m
    else:
        r = m
print(r)

Solution (Python):
import bisect

n,k = map(int,input().split())
A = sorted([int(i) for i in input().split()])

inm = bisect.bisect_left(A,0)
inp = bisect.bisect_right(A,0)
mi = [-x for x in A[:inm]]
mi = mi[::-1]
pl = A[inp:]
zero = inp-inm
numm = inm
nump = n-inp

def shaku(x,l):
    count = 0
    ma = len(l)
    ri = ma-1
    for i in range(ma):
        while ri >= 0 and l[ri]*l[i] > x:
            ri -= 1
        count += max(ri-i,0)
        
    return count 

def search(x):
    count = 0
    if x >= 0:
        count += zero*(n-zero)+numm*nump+(zero*(zero-1))//2
        count += shaku(x,pl)
        count += shaku(x,mi)
            
        return count
    else:
        ri = 0
        for i in pl[::-1]:
            while ri < numm and i*mi[ri] < -x:
                ri += 1
            count += numm-ri
        return count

left = -10**18-1
right = 10**18+1
while right > left+1:
    mid = (left+right)//2
    a = search(mid)
    
    if a >= k:
        right = mid
    else:
        left = mid
print(right)

Solution (Python):
import bisect

n,k = map(int,input().split())
A = sorted([int(i) for i in input().split()])


zero = A.count(0)
inm = bisect.bisect_left(A,0)
inp = bisect.bisect_right(A,0)
mi = [-x for x in A[:inm]]
mi = mi[::-1]
pl = A[inp:]
numm = inm
nump = n-inp

def shaku(x,l):
    count = 0
    if len(l) <= 1:
        return 0
    ri = len(l)-1
    for i in range(len(l)):
        while ri >= 0 and l[ri]*l[i] > x:
            ri -= 1
        
        count += max(ri-i,0)
        
    return count 

def search(x):
    count = 0
    if x >= 0:
        count += zero*(n-zero)+numm*nump+(zero*(zero-1))//2
        count += shaku(x,pl)
        count += shaku(x,mi)
            
        return count
    else:
        ri = 0
        
        for i in pl[::-1]:
            while ri < numm and i*mi[ri] < -x:
                ri += 1
            count += numm-ri
        return count

left = -10**18-1
right = 10**18+1
while right > left+1:
    mid = (left+right)//2
    a = search(mid)
    
    if a >= k:
        right = mid
    else:
        left = mid
print(right)

Solution (Python):
import bisect

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

zero = A.count(0)
inm = bisect.bisect_left(A,0)
inp = bisect.bisect_right(A,0)
mi = [-x for x in A[:inm]]
mi = mi[::-1]
pl = A[inp:]
numm = inm
nump = n-inp

def shaku(x,l):
    count = 0
    if len(l) <= 1:
        return 0
    ri = len(l)-1
    for i in range(len(l)):
        while ri >= 0 and l[ri]*l[i] > x:
            ri -= 1
        
        count += max(ri-i,0)
        
    return count 

def search(x):
    count = 0
    if x >= 0:
        count += zero*(n-zero)+numm*nump+(zero*(zero-1))//2
        count += shaku(x,pl)
        count += shaku(x,mi)
            
        return count
    else:
        ri = 0
        
        for i in pl[::-1]:
            while ri < numm and i*mi[ri] < -x:
                ri += 1
            count += numm-ri
        return count

left = -10**18-1
right = 10**18+1
while right > left+1:
    mid = (left+right)//2
    a = search(mid)
    
    if a >= k:
        right = mid
    else:
        left = mid
print(right)

Solution (Python):
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
N=[];Z=[];P=[]
for i in range(n):
  if a[i]<0:
    N.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    P.append(a[i])

if k<=len(N)*len(P):
  for i in range(len(N)):
    N[i]*=-1
  N.sort()
  P.sort()
  Nr=list(reversed(N))
  L=0;R=10**18+1
  while R-L>1:
    x=(L+R)//2
    ct=0
    ct2=0
    for j in range(len(Nr)):
      if ct2!=len(P):
        while Nr[j]*P[ct2]<x:
          ct2+=1
          if ct2==len(P):
            break
      ct+=len(P)-ct2
    if ct<k:
      R=x
    else:
      L=x
  print(-L)

elif k<=len(N)*len(P)+(len(Z)*(len(Z)-1))//2+len(Z)*(len(N)+len(P)):
  print(0)

else:
  y=len(N)*len(P)+(len(Z)*(len(Z)-1))//2+len(Z)*(len(N)+len(P))
  for i in range(len(N)):
    N[i]*=-1
  N.sort()
  P.sort()
  L=0;R=10**18+1
  Nr=list(reversed(N))
  Pr=list(reversed(P))
  while R-L>1:
    x=(L+R)//2
    ct=0
    ct2=0
    for j in range(len(Nr)):
      if ct2!=len(N):
        while Nr[j]*N[ct2]<=x:
          ct2+=1
          if ct2==len(N):
            break
      ct+=min(ct2,len(N)-1-j)
    ct3=0
    for j in range(len(Pr)):
      if ct3!=len(P):
        while Pr[j]*P[ct3]<=x:
          ct3+=1
          if ct3==len(P):
            break
      ct+=min(ct3,len(P)-1-j)
    if ct<k-y:
      L=x
    else:
      R=x
  print(R)

Solution (Python):
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)


def main():
  n, k = map(int, input().split())
  A = np.array(input().split(), np.int64)
  
  A = np.sort(A)
  
  zero = A[A == 0]
  pos = A[A>0]
  neg = A[A<0]
  
  def F(x):
    cnt_tpl = 0
    
    if x>= 0:
      cnt_tpl += len(zero)*n
    
    cnt_tpl += np.searchsorted(A, x//pos, side='right').sum()
    cnt_tpl += (n - np.searchsorted(A, (-x-1)//(-neg), 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:
    mid = (left+right)//2
    if F(mid) >= k:
      right = mid
    else:
      left = mid
  print(right)
  
if __name__ == '__main__':
  main()