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):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import bisect
    mod=10**9+7
    N,K=MI()
    A=LI()
    pos=[]
    zero=[]
    nega=[]
    for i in range(N):
        if A[i]>0:
            pos.append(A[i])
        elif A[i]==0:
            zero.append(A[i])
        else:
            nega.append(A[i]*-1)
            
    np=len(pos)
    nz=len(zero)
    nn=len(nega)
    
    pos.sort()
    zero.sort()
    nega.sort()
    
    inf=10**18 + 1
    
    
    
    if K<=np * nn:
        
        
        
        
        
        def ch(x):
            cnt=0
            for p in pos:
                t=(x+p-1)//p
                num=bisect.bisect_left(nega,t)
                cnt+=nn-num
            return cnt>=K
                
        
        ok=0
        ng=inf
        while ng-ok>1:
            x=(ok+ng)//2
            if ch(x):
                ok=x
            else:
                ng=x
        
        print(ok*-1)
        
    elif K<= np*nn + nz*(N-nz) + (nz*(nz-1))//2:
        print(0)
        
    else:
        
        
        
        
        K2=(N*(N-1))//2 - K + 1
        
        
        def ch(x):
            cnt=0
            for p in pos:
                t=(x+p-1)//p
                num=bisect.bisect_left(pos,t)
                rem=np-num
                if t<=p:
                    rem-=1
                cnt+=rem
                
            for ne in nega:
                t=(x+ne-1)//ne
                num=bisect.bisect_left(nega,t)
                rem=nn-num
                if t<=ne:
                    rem-=1
                cnt+=rem
                
            cnt=cnt//2
            
            return cnt>=K2
                
        
        ok=0
        ng=inf
        while ng-ok>1:
            x=(ok+ng)//2
            if ch(x):
                ok=x
            else:
                ng=x
        
        print(ok)
        
        
        

main()

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
Aminus=[]
Aplus=[]
negative=0
positive=0
posinega=0
for i in range(N):
    if A[i]>0:
        positive+=1
        Aplus.append(A[i])
    elif A[i]<0:
        negative+=1
        Aminus.append(A[i])
    else:
        posinega+=1
Aplus.sort()
Aminus.sort()
PLUS=positive*positive+negative*negative
MINUS=2*positive*negative
ZERO=N*N-PLUS-MINUS

PLUS=(PLUS-(N-posinega))//2
MINUS=MINUS//2
ZERO=(ZERO-posinega)//2
if K<=MINUS:
    
    low=min(A)*max(A)
    high=0
    while(high-low>1):
        mid=(high+low)//2
        '''
        A[i]*A[j]<lowとなる(i<j)の組み合わせはK個未満である
        A[i]*A[j]<highとなる(i<j)の組み合わせはK個以上である
        tmpはA[i]*A[j]<midとなる(i<j)の組み合わせである
        '''
        tmp=0
        for i in range(positive):
            low0=-1
            high0=negative
            while(high0-low0>1):
                mid0=(high0+low0)//2
                '''
                Aplus[i]*Aminus[j]はjについて単調増加である。
                Aplus[i]*Aminus[low0]<mid<=Aplus[i]*Aminus[high0]を常に満たす必要がある
                '''
                if Aplus[i]*Aminus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
        if tmp<K:
            low=mid
        else:
            high=mid
    print(low)
elif K<=MINUS+ZERO:
    print(0)
else:
    K-=MINUS+ZERO
    
    low=0
    high=max(min(A)**2,max(A)**2)
    Aminus=Aminus[::-1]
    while(high-low>1):
        mid=(high+low)//2
        '''
        A[i]*A[j]<lowとなる(i<j)の組み合わせはK個未満である
        A[i]*A[j]<highとなる(i<j)の組み合わせはK個以上である
        tmpはA[i]*A[j]<midとなる(i<j)の組み合わせである
        '''
        tmp=0
        for i in range(positive):
            low0=-1
            high0=positive
            while(high0-low0>1):
                mid0=(high0+low0)//2
                '''
                Aplus[i]*Aplus[j]はjについて単調増加である。
                Aplus[i]*Aplus[low0]<mid<=Aplus[i]*Aplus[high0]を常に満たす必要がある
                '''
                if Aplus[i]*Aplus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
            if Aplus[i]*Aplus[i]<mid:
                tmp-=1
        for i in range(negative):
            low0=-1
            high0=negative
            while(high0-low0>1):
                mid0=(high0+low0)//2
                if Aminus[i]*Aminus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
            if Aminus[i]*Aminus[i]<mid:
                tmp-=1
        tmp=tmp//2
        if tmp<K:
            low=mid
        else:
            high=mid
    print(low)

Solution (Python):
def General_Binary_Increase_Search(L,R,cond,Integer=True,ep=1/(1<<20)):
    """条件式が単調増加であるとき,一般的な二部探索を行う.
    L:解の下限
    R:解の上限
    cond:条件(1変数関数,広義単調減少 or 広義単調減少を満たす)
    Integer:解を整数に制限するか?
    ep:Integer=Falseのとき,解の許容する誤差
    """
    if not(cond(R)):
        return False

    if Integer:
        R+=1
        while R-L>1:
            C=L+(R-L)//2
            if cond(C):
                R=C
            else:
                L=C
        return R
    else:
        while (R-L)>=ep:
            C=L+(R-L)/2
            if cond(C):
                R=C
            else:
                L=C
        return R

def f(R):
    I=0
    S=0
    for a in Pos:
        if I<Negative:
            while a*Neg[I]<=R:
                I+=1
                if I==Negative:
                    break

        S+=I
    return S

def g(R):
    S=0

    I=Positive
    for a in Pos:
        if I>0:
            while a*Pos[I-1]>R:
                I-=1
                if I==0:
                    break
        S+=I
        if a*a<=R:
            S-=1

    J=0
    for b in Neg:
        if J<Negative:
            while b*Neg[-(J+1)]<=R:
                J+=1
                if J==Negative:
                    break
        S+=J
        if b*b<=R:
            S-=1

    return S>>1

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

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

Pos=[a for a in A if a>0]
Neg=[a for a in A if a<0]

Positive=Zero=Negative=0
for a in A:
    if a>0:
        Positive+=1
    elif a==0:
        Zero+=1
    else:
        Negative+=1

Pos_Count=(Positive*(Positive-1))//2+(Negative*(Negative-1))//2
Neg_Count=Positive*Negative
Zero_Count=(N*(N-1))//2-(Pos_Count+Neg_Count)

H=max(A,key=lambda a:abs(a))
H=H*H+1

if Neg_Count+1<=K<=Neg_Count+Zero_Count: 
    Ans=0
elif K<=Neg_Count: 
    Ans=General_Binary_Increase_Search(-H,0,lambda x:f(x)>=K)
else: 
    Ans=General_Binary_Increase_Search(0,H,lambda x:g(x)>=K-(Neg_Count+Zero_Count))

print(Ans)

Solution (Python):
from numpy import *
N,K = map(int,input().split())
A = array(sorted(list(map(int,input().split()))))
nega = A[A<0]
zera = A[A==0]
posa = A[0<A]

def cnt(x):
  y = 0
  if x>=0:
    y+=N*len(zera)
  y+=searchsorted(A,x//posa,side="right").sum()
  y+=N*len(nega)-searchsorted(A,-(-x//nega)).sum() 
  y-=len(A[A*A<=x])
  return y//2

r = 10**18
l = -r-1

while r-l>1:
  c=(r+l)//2
  if K<=cnt(c):
    r=c
  else:
    l=c

print(r)

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

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    minus, plus, zero = [], [], 0
    for i in range(n):
        if a[i] < 0:
            minus.append(a[i])
        elif a[i] > 0:
            plus.append(a[i])
        else:
            zero += 1
    
    minus_count = len(minus) * len(plus)
    zero_count = zero * (zero - 1) // 2 + zero * (len(minus) + len(plus))

    minus.sort()
    plus.sort()

    if k <= minus_count:
        l, r = -int(1e18), 0
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            border = 0
            for v in minus:
                while border < len(plus) and v * plus[border] > value:
                    border += 1 
                count += len(plus) - border

            if count >= k:
                r = value
            else:
                l = value

        ans = r

    elif k <= zero_count + minus_count:
        ans = 0
        
    else:
        l, r = 0, int(1e18)
        count_default = minus_count + zero_count
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            
            border = 0
            for v in minus:
                while border < len(minus) and v * minus[-border-1] <= value:
                    border += 1
                count += border
                if border > 0 and v >= minus[-border]:
                    count -= 1
            
            border = 0
            for v in plus:
                while border < len(plus) and v * plus[-border-1] > value:
                    border += 1
                count += len(plus) - border
                if border < len(plus) and v <= plus[-border-1]:
                    count -= 1

            count //= 2
            count += count_default

            if count >= k:
                r = value
            else:
                l = value
        ans = r
        
    print(ans)

    
if __name__ == "__main__":
    main()

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
posi = []
nega = []
zero = []
for i in range(n):
    if a[i] < 0:
        nega.append(a[i] * -1)
    elif a[i] > 0:
        posi.append(a[i])
    else:
        zero.append(a[i])
zero = len(zero)
posi.sort()
nega.sort()
lp, ln = len(posi), len(nega)
if k <= lp * ln:
    l, r = 0, 10 ** 18
    while r - l > 1:
        m = (l + r) // 2
        cnt = lp * ln
        cur = 0
        for i in range(ln)[::-1]:
            while cur < lp and posi[cur] < (m + nega[i] - 1) // nega[i]:
                cur += 1
            cnt -= cur
        if cnt >= k:
            l = m
        else:
            r = m
    print(-1 * l)
elif k <= n * (n - 1) // 2 - (lp * (lp - 1) // 2) - (ln * (ln - 1) // 2):
    print(0)
else:
    k -= n * (n - 1) // 2 - (lp * (lp - 1) // 2) - (ln * (ln - 1) // 2)
    l, r = 0, 10 ** 18
    while r - l > 1:
        m = (l + r) // 2
        cnt = 0
        cur = ln - 1
        for i in range(ln):
            while cur and nega[cur] > m // nega[i]:
                cur -= 1
            if cur > i:
                cnt += cur - i
        cur2 = lp - 1
        for i in range(lp):
            while cur2 and posi[cur2] > m // posi[i]:
                cur2 -= 1
            if cur2 > i:
                cnt += cur2 - i
        if cnt >= k:
            r = m
        else:
            l = m
    print(r)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
plus = []
minus = []
zero = 0
for i in range(n):
    if a[i] < 0:
        minus.append(-a[i])
    elif a[i] > 0:
        plus.append(a[i])
    else:
        zero += 1
plus.sort()
minus.sort()
p = len(plus)
m = len(minus)
am = p*m
ap = p*(p-1)//2 + m*(m-1)//2
az = n*(n-1)//2 - am - ap


def binary_search_func(ok, ng, f):
    while(abs(ok - ng) > 1):
        med = (ok + ng) // 2
        if(f(med) == True):
            ok = med
        else:
            ng = med
    return ok

if k <= am:
    def c(x):
        res = p*m
        v = 0
        for i in minus[::-1]:
            kk = (x+i-1)//i
            
            while v < p and plus[v] < kk:
                v += 1
            res -= v
        return res >= k

    ok = 0
    ng = 10**18
    ans = -(binary_search_func(ok, ng, c))
    
elif k <= am + az:
    ans = 0

else:
    k -= am + az
    def c(x):
        res = 0
        vm = m-1
        for i,ai in enumerate(minus):
            kkm = x//ai
            while vm and minus[vm] > kkm:
                vm -= 1
            if vm > i:
                res += vm - i
        vp = p-1
        for i,ai in enumerate(plus):
            kkp = x//ai
            while vp and plus[vp] > kkp:
                vp -= 1
            if vp > i:
                res += vp - i
        return res >= k
    
    ok = 10**18
    ng = 0
    ans = binary_search_func(ok, ng, c)

print(ans)

Solution (Python):
N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = max(A[0]**2,A[-1]**2)
ok1 = inf
ng1 = -inf
while (abs(ok1 - ng1) > 1):
    arg = (ok1 + ng1) // 2
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] == 0:
            if arg > 0:
                ans += N
        elif A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    if K>ans:
        ng1 = arg
    else:
        ok1 = arg
print(ng1)

Solution (Python):
import bisect

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

def count(t):
    c = 0
    for x in a:
        if x == 0:
            c += len(a) - 1 if t >= 0 else 0
        elif x > 0:
            c += bisect.bisect_left(a, (t // x) + 1) - (x * x <= t)
        else:
            c += len(a) - bisect.bisect_left(a, -(t // -x)) - (x * x <= t)
    return c

lo = -1000000000000000001
hi = 1000000000000000001
while hi - lo > 1:
    mid = (lo + hi) // 2
    if count(mid) < k * 2:
        lo = mid
    else:
        hi = mid
print(hi)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
def main():
    N, K = MI()
    A = LI()
    A.sort()
    def is_ok(arg):
        
        cnt = 0
        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            elif a < 0:
                aa = -((-arg) // a)
                cnt += N - bisect.bisect_left(A, aa)
                if aa <= a:
                    cnt -= 1
            else:
                aa = arg // a
                cnt += bisect.bisect_right(A, aa)
                if aa >= a:
                    cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    cnt_neg = bisect.bisect_left(A, 0)
    cnt_pos = N - bisect.bisect_right(A, 0)
    cnt_zer = N - cnt_pos - cnt_neg

    if K <= cnt_neg * cnt_pos:
        ng = - 10 ** 18 - 10
        ok = 1
        ans = meguru_bisect(ng, ok)
        print(ans)
    elif K <= cnt_neg * cnt_pos + cnt_zer * (N - 1) - cnt_zer * (cnt_zer - 1) // 2:
        print(0)
    else:
        ng = -1
        ok = 10 ** 18 + 10
        ans = meguru_bisect(ng, ok)
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

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

a = np.array(a)
a.sort()

nega = a[a<0]
zero = a[a==0]
posi = 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=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((mid+1)//(H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

Solution (Python):
N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid-1)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

Solution (Python):

def main():
    from bisect import bisect_left, bisect_right

    N, K = map(int, input().split())
    A = sorted([int(x) for x in input().split()])

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

    postive_cnt = N - postive_start
    negative_cnt = negative_end
    zero_cnt = N - postive_cnt - negative_cnt

    negative_pairs_cnt = postive_cnt * negative_cnt
    zero_pairs_cnt = (zero_cnt * (postive_cnt + negative_cnt)
                      + (zero_cnt * (zero_cnt - 1) // 2))
    
    
    if K <= negative_pairs_cnt:
        
        ok, ng = 0, -10 ** 19
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            or_higher_cnt, right = 0, postive_start
            for left in range(negative_end):
                while right < N and A[left] * A[right] > mid:
                    right += 1
                or_higher_cnt += postive_cnt - (right - postive_start)
            if or_higher_cnt >= K:
                ok = mid
            else:
                ng = mid
        print(ok)
    
    elif K <= negative_pairs_cnt + zero_pairs_cnt:
        print(0)
    
    else:
        
        K -= negative_pairs_cnt + zero_pairs_cnt
        ok, ng = 10 ** 19, 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            
            or_higher_cnt, right = 0, N - 1
            for left in range(postive_start, N):
                while right < N and A[left] * A[right] > mid and left < right:
                    right -= 1
                or_higher_cnt += max(0, right - left)
            
            left = 0
            for right in range(negative_end - 1, -1, -1):
                while left < N and A[left] * A[right] > mid and left < right:
                    left += 1
                or_higher_cnt += max(0, right - left)

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


if __name__ == '__main__':
    main()

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

minus = 0
for i in range(n):
    if A[i] < 0:
        minus += 1
zplus = n - minus

B = []
C = []
for i in range(n):
    if A[i] < 0:
        C.append(A[i])
    else:
        B.append(A[i])
B.sort(reverse=True)
C.sort()


if k <= minus * zplus:
    ok = 1
    ng = -10**20
    m = (ok+ng) // 2
    while abs(ng-ok) > 1:
        co = 0
        j = len(C)-1
        for i in range(len(B)):
            while j >= 0 and B[i]*C[j] > m:
                j -= 1
            co += j+1
        
        if co >= k:
            ok = m
            
        else:
            ng = m
            
        m = (ok+ng) // 2
    print(ok)
else:
    k -= minus * zplus
    ok = 10**20
    ng = -1
    m = (ok+ng) // 2
    while abs(ng-ok) > 1:
        co = 0
        j = len(C)-1
        for i in range(len(C)):
            while j > i and C[i]*C[j] <= m:
                j -= 1
            co += len(C)-1-j
            j = max(j, i+1)
        j = len(B)-1
        for i in range(len(B)):
            while j > i and B[i]*B[j] <= m:
                j -= 1
            co += len(B)-1-j
            j = max(j, i+1)

        if co >= k:
            ok = m
            
        else:
            ng = m
            
        m = (ok+ng) // 2
    print(ok)

Solution (Python):
N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid-1)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

Solution (Python):

import bisect
import sys
def input(): return sys.stdin.readline().rstrip()
 
 
def is_ok(arg, sei, hu, k):
    
    count = 0
    for index, NN in enumerate(sei, 1):
        if NN==0:
            count+=len(sei)-index
        else:
            if NN**2 >= arg:
                break
            count += bisect.bisect_right(sei, ((arg)//NN))-index  
    for index, NN in enumerate(hu, 1):
        if NN**2 >= arg:
            break
        count += bisect.bisect_right(hu, ((arg)//NN))-index  
    return count >= k
 
 
def meguru_bisect(ng, ok, sei, hu, k):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, sei, hu, k):
            ok = mid
        else:
            ng = mid
    return ok
 
 
def is_ok2(arg, sei, hu, k):
    
    count = 0
    hulen=len(sei)
    for NN in hu:
        count += hulen-bisect.bisect_right(sei, ((-arg)-1)//NN)
    return count >= k
 
def meguru_bisect2(ng, ok, sei, hu, k):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok2(mid, sei, hu, k):
            ok = mid
        else:
            ng = mid
    return ok
 
def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    sei = []
    hu = []
    for AA in A:
        if AA >= 0:
            sei.append(AA)
        else:
            hu.append(-AA)
    sei.sort()
    hu.sort()
    seinum = len(sei)
    hunum = len(hu)
    if seinum*hunum < k:
        ans=meguru_bisect(-1, 10**18, sei, hu, k-seinum*hunum)
    else:
        ans=meguru_bisect2(-1*10**18, 0, sei, hu, k)
    print(ans)
 
if __name__ == '__main__':
    main()

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("YES") if fl else print("NO")
import collections
import math
import itertools
import heapq as hq
def isok1(x,ls1,ls2,cnt=0):
    
    l1,l2=0,0
    while l1<len(ls1) and l2<len(ls2):
        if ls1[l1]*ls2[l2] <= x:
            cnt+=len(ls2) -l2
            l1+=1
        else:
            l2+=1
    return cnt<k
def isok2(x,ls1,ls2,cnt=0):
    
    l,r=0,0
    tmp=0
    while r<len(ls1) and l<len(ls1):
        if ls1[-l-1]*ls1[r] <=x:
            tmp+=len(ls1)-r
            l+=1
        else:
            r+=1
    for i in range(len(ls1)):
        if ls1[i]**2 <=x:tmp-=1
    cnt+=tmp//2
    l,r=0,0
    tmp=0
    while r<len(ls2) and l<len(ls2):
        
        if ls2[-l-1]*ls2[r] <=x:
            tmp+=len(ls2)-r
            
            l+=1
        else:
            r+=1
    for i in range(len(ls2)):
        if ls2[i]**2 <=x:tmp-=1
    cnt+=tmp//2
    
    return cnt<k



n,k = ma()
A = lma()
pA = [a for a in A if a>0]
mA = [a for a in A if a<0]
pn = len(mA)*(len(mA)-1)//2 +len(pA)*(len(pA)-1)//2
mn = len(pA) *len(mA)
z = n*(n-1)//2 -pn -mn
if k<=mn:
    f=True
    pA.sort()
    mA.sort()
elif k>mn+z:
    f=False
    pA.sort(reverse=True)
    mA.sort()
else:
    print(0)
    exit()

ok = -10**18-2
ng = 10**18+2
x = (ok+ng)//2

while ng-ok>1:
    if f:
        if isok1(x,mA,pA):
            ok = x
        else:
            ng=x
        x = (ok+ng)//2
    else:
        if isok2(x,mA,pA,cnt=mn+z):
            ok = x
        else:
            ng=x
        x = (ok+ng)//2
print(ng)

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

Solution (Python):
n, k = map(int, input().split())
alst = list(map(int, input().split()))
plus = []
zero = []
minus = []
for a in alst:
    if a > 0:
        plus.append(a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(-1 * a)
p = len(plus)
z = len(zero)
m = len(minus)
p_cnt = p * (p - 1) // 2 + m * (m - 1) // 2
z_cnt = p * z + m * z + z * (z - 1) // 2
m_cnt = p * m
minus.sort()
plus.sort()
if m_cnt >= k: 
    l = 0
    r = 10 ** 20
    while r - l > 1:
        num = (r + l) // 2
        p_pos = p - 1
        cnt = 0
        for m_pos in range(m):
            while minus[m_pos] * plus[p_pos] >= num and p_pos >= 0:
                p_pos -= 1
            cnt += p - p_pos - 1
        if cnt >= k:
            l = num
        else:
            r = num
    ans = l * -1
elif m_cnt + z_cnt >= k: 
    ans = 0

else: 
    k -= (z_cnt + m_cnt)
    l = 0
    r = 10 ** 20
    while r - l > 1:
        num = (r + l) // 2
        m_r = m - 1
        cnt = 0
        cnt_sub = 0
        for m_l in range(m):
            while minus[m_l] * minus[m_r] > num and m_r >= 0:
                m_r -= 1
            cnt += m_r + 1
            if minus[m_l] * minus[m_l] <= num:
                cnt -= 1
        p_r = p - 1
        for p_l in range(p):
            while plus[p_l] * plus[p_r] > num and p_r >= 0:
                p_r -= 1
            cnt += p_r + 1
            if plus[p_l] * plus[p_l] <= num:
                cnt -= 1
        cnt //= 2
        if cnt >= k:
            r = num
        else:
            l = num
    ans = r
print(ans)

Solution (Python):
from bisect import bisect_left,bisect_right


def func(mn,zn,pn,am,ap,x):
    cnt=0
    if x>0:
        cnt+=mn*pn
        cnt+=(zn*(n-1+n-zn))//2
        cnt1=0
        for y in ap:
            cnt1+=bisect_left(ap,(x+y-1)//y)
            if y**2<x:cnt1-=1
        for y in am:
            cnt1+=bisect_left(am,(x+y-1)//y)
            if y**2<x:cnt1-=1
        cnt+=cnt1//2
    elif x<0:
        x=abs(x)
        for y in ap:
            cnt+=mn-bisect_right(am,x//y)
    elif x==0:
        cnt+=mn*pn
    return cnt<k
def main(n,k,a):
    a.sort()
    
    mn=bisect_left(a,0)
    
    zn=bisect_right(a,0)-mn
    
    pn=n-mn-zn
    am=a[:mn]
    am=[-x for x in am[::-1]]
    ap=a[mn+zn:]
    if k<=mn*pn:
        l,r=a[0]*a[-1]-1,0
    elif k<=mn*pn+zn*(n-zn)+(zn*(zn-1))//2:
        print(0)
        exit()
    else:
        l,r=0,max(a[0]*a[1],a[-1]*a[-2])+1
    while r-l>1:
        x=(l+r)//2
        if func(mn,zn,pn,am,ap,x):
            l,r=x,r
        else:
            l,r=l,x
    print(l)

    """
    b=[]
    for i in range(n-1):
        for j in range(i+1,n):
            b.append(a[i]*a[j])
    b.sort()
    print(b[k-1])
    """
if __name__=='__main__':
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    main(n,k,a)