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

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A)
ok, ng = 10**18, -10**18


while ok - ng > 1:
    mid = (ok + ng) // 2
    
    s = 0
    t = 0
    for i in range(N):
        if A[i] > 0:
            
            
            
            
            
            
            
            
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= mid:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            
            
            
            
            
            
            
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= mid:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        elif mid >= 0:
            s += N
        if A[i] * A[i] <= mid:
            t += 1
    
    total = (s - t) // 2
    
    if total >= K:
        ok = mid
    else:
        ng = mid
print(ok)

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 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):
from bisect import bisect_left, bisect_right
from math import ceil

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

    al_n = []
    al_p = []
    al_n_p = []
    zero_cnt = 0
    for a in al:
        if a < 0: 
            al_n.append(a)
            al_n_p.append(-1*a)
        elif a > 0: 
            al_p.append(a)
        else: 
            zero_cnt += 1
    al_n_p = al_n_p[::-1]

    n_cnt = len(al_n)
    p_cnt = len(al_p)

    m_n_cnt = n_cnt*p_cnt
    m_p_cnt = n_cnt*(n_cnt-1)//2 + p_cnt*(p_cnt-1)//2
    m_zero_cnt = zero_cnt*(n_cnt+p_cnt) + zero_cnt*(zero_cnt-1)//2


    if k <= m_n_cnt:
        left = (-1)*(10**18)
        right = -1
        while right-left>1:
            curr_num = left + (right-left)//2
            curr_cnt = 0
            num_exist = False
            for an in al_n:
                targt_p = abs(curr_num)//abs(an)
                p_ind = bisect_right(al_p,targt_p)
                ok_p_cnt = len(al_p) - p_ind
                curr_cnt += ok_p_cnt
                if p_ind > 0 and al_p[p_ind-1]*an == curr_num:
                    num_exist = True
            
            if curr_cnt > k-1:
                right = curr_num
            elif curr_cnt < k-1:
                left = curr_num
            else:
                if num_exist:
                    print(curr_num)
                    exit()
                else:
                    left = curr_num


    elif m_n_cnt < k <= m_n_cnt+m_zero_cnt:
        print(0)
        exit()

    else:
        k = k - m_n_cnt - m_zero_cnt 
        right = (10**18)
        left = 0
        while right-left > 1:
            cnt = k
            
            
            curr_num = left + (right-left)//2
            curr_cnt = 0
            num_exist = False
            
            
            for i, an in enumerate(al_n_p):
                targt_p = abs(curr_num)//abs(an)
                ok_p_cnt = max(bisect_right(al_n_p,targt_p)-i-1, 0)
                cnt -= ok_p_cnt
            
            for i, an in enumerate(al_p):
                
                targt_p = abs(curr_num)//abs(an)
                
                ok_p_cnt = max(bisect_right(al_p,targt_p)-i-1, 0)
                cnt -= ok_p_cnt
                

            if cnt > 0:
                left = curr_num
            else:
                right = curr_num

        print(right)


if __name__ == "__main__":
    main()

Solution (Python):



from bisect import bisect_left, bisect_right

import sys

input = sys.stdin.buffer.readline

n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
minusA = bisect_left(A, 0)
mA = A[:minusA]

zeroA = bisect_right(A, 0) - bisect_left(A, 0)
plusA = n - minusA - zeroA
pA = A[-plusA:]
minus = minusA * plusA
plus = plusA * (plusA - 1) // 2 + minusA * (minusA - 1) // 2
zero = zeroA * (zeroA - 1) // 2 + (n - zeroA) * zeroA



def calc(x):
    mmA = mA[::-1]
    res = 0
    if x > 0:
        lim = plusA - 1
        for i in range(plusA):
            while lim >= 0:
                if pA[i] * pA[lim] > x:
                    lim -= 1
                else:
                    break
            res += lim + 1
            if lim >= i:
                res -= 1
        lim = minusA - 1
        mmA = mA[::-1]
        for i in range(minusA):
            while lim >= 0:
                if mmA[i] * mmA[lim] > x:
                    lim -= 1
                else:
                    break
            res += lim + 1
            if lim >= i:
                res -= 1
        res //= 2
        res += minus + zero
    elif x == 0:
        res += minus + zero
    else:
        
        
        lim = minusA - 1
        for i in range(plusA):
            while lim >= 0:
                if pA[i] * mmA[lim] <= x:
                    lim -= 1
                else:
                    break
            res += minusA - (lim + 1)
    return res


ng = -(10 ** 20)
ok = 10 ** 20
while ok - ng > 1:
    mid = (ok + ng) // 2
    if calc(mid) >= k:
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):
from bisect import bisect_right,bisect_left
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
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  
  
  if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      cnt=0
      for i in range(nn):
        if mid%an[i]!=0:
          cnt+=np-bisect_left(ap,mid//an[i]+1)
        else:
          cnt+=np-bisect_left(ap,mid//an[i])
      
      if cnt>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    
    ok=10**18
    ng=0
    
    while ok-ng>1:
      mid=(ok+ng)//2
      cnt1,cnt2=0,0
      if np>=2:
        for i in range(np):
          cnt1+=bisect_right(ap,mid//ap[i])
          if ap[i]**2<=mid:
            cnt1-=1
      if nn>=2:
        for i in range(nn):
          cnt2+=bisect_right(an,mid//an[i])
          if an[i]**2<=mid:
            cnt2-=1
      if cnt1//2+cnt2//2>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    M, P = [], [0]
    Z = 0
    for a in A:
        if a < 0: M.append(a)
        elif a == 0: Z += 1
        else: P.append(a)
    M.sort(reverse = True)
    mL, pL = len(M), len(P)

    minusT = mL * pL
    zeroT = Z * (mL + pL)

    if K <= minusT: 
        P.sort(reverse = True)
        low, high = - 10 ** 18 - 1, 0
        while high - low > 1:
            mid = (low + high) // 2
            pi = 0
            count = 0
            for i in range(mL):
                while M[i] * P[pi] <= mid: pi += 1
                count += pi
            
            if count >= K: high = mid
            else: low = mid
        print(high)

    elif K <= minusT + zeroT: 
        print(0)

    else: 
        M.append(0)
        P.sort()
        T = N * (N - 1) // 2
        low, high = 0, 10 ** 18 + 1
        while high - low > 1:
            mid = (high + low) // 2
            count = 0
            pi = pL - 1
            for i in range(pL):
                while P[i] * P[pi] >= mid:
                    pi -= 1
                count += pL - 1 - max(i, pi)
               
            mi = mL - 1
            for i in range(mL):
                while M[i] * M[mi] >= mid:
                    mi -= 1
                count += mL - 1 - max(i, mi)

            
  
            if T - count >= K: high = mid
            else: low = mid
        print(low)
   
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n,k = map(int, input().split())
a = list(map(int, input().split()))
ma = []
pa = []
zc = 0
for num in a:
    if num<0:
        ma.append(num)
    elif num>0:
        pa.append(num)
    else:
        zc += 1
mn = len(ma)*len(pa)
ma.sort()
pa.sort()
ma =ma[::-1]

def _sub(m, l1):
    lp = len(l1)
    t = lp-1
    ans = 0
    for s in range(lp):
        if t<=s:
            break
        while l1[s]*l1[t]>m and t>s+1:
            t -= 1
        if l1[s]*l1[t]>m:
            break
        ans += (t-s)
    return ans

def sub1(m):
    
    ans = 0
    ans += _sub(m, pa)
    ans += _sub(m, ma)
    return ans

def sub2(m):
    
    ans = 0
    lp = len(pa)
    lm = len(ma)
    t = 0
    for s in reversed(range(lp)):
        while pa[s]*ma[t]>m and t<lm-1:
            t += 1
        if pa[s]*ma[t]>m:
            break
        ans += lm - t
    return ans

znum = zc*(len(ma)+len(pa)) + (zc-1)*zc//2
if k>mn:
    k -= mn
    if znum>=k:
        ans = 0
    else:
        k -= znum
        l = 0
        r = 10**18+1
        while l<r-1:
            m = (l+r)//2
            v = sub1(m)
            if v>=k:
                r = m
            else:
                l = m
        ans = l+1
else:
    l = -10**18-1
    r = 0
    while l<r-1:
        m = (l+r)//2
        v = sub2(m)
        if v>=k:
            r = m
        else:
            l = m
    ans = l+1
print(ans)

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):
from sys import stdin
import numpy as np
def main():
    
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=np.array(readline().strip().split(),dtype="int64")
    
    a.sort()
    neg=a[a<0]
    neg_p=neg**2
    zero=a[a==0]
    pos=a[a>0]
    pos_p=pos**2
    l=-10**18-1
    r=10**18
    while l<r-1:
        x=(l+r)//2
        cnt=0
        if neg.size>0:
            cnt+=(a.size-np.searchsorted(a,(x+neg+1)//neg)).sum()
            cnt-=neg_p[neg_p<=x].size
        if zero.size>0:
            if x>=0:
                cnt+=(a.size-1)*zero.size
        if pos.size>0:
            cnt+=np.searchsorted(a,x//pos,side="right").sum()
            cnt-=pos_p[pos_p<=x].size

        cnt//=2
        if cnt>=k: r=x
        else: l=x

    print(r)

if __name__=="__main__":
    main()

Solution (Python):
MAX = int(10e18)


def count(arr1, arr2, target, remove_dup):
    ret = 0
    j = len(arr2)
    for i, val1 in enumerate(arr1):
        while j > 0 and val1 * arr2[j-1] > target:
            j -= 1
        ret += j
        if remove_dup and j >= (i+1):
            ret -= 1
    if remove_dup:
        ret //= 2
    return ret


def search_negative(pos, neg, K):
    neg.sort()
    pos.sort(reverse=True)
    lo = -MAX
    hi = 0
    while lo < hi:
        mid = (lo + hi) // 2
        cnt = count(pos, neg, mid, False)
        if cnt < K:
            lo = mid + 1
        else:
            hi = mid
    return lo


def search_positive(pos, neg, K):
    pos.sort()
    neg.sort(reverse=True)
    lo = 0
    hi = MAX
    while lo < hi:
        mid = (lo + hi) // 2
        cnt = count(pos, pos, mid, True) + count(neg, neg, mid, True)
        if cnt < K:
            lo = mid + 1
        else:
            hi = mid
    return lo


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    negative_nums = []
    positive_nums = []
    zeros = 0
    for a in A:
        if a < 0:
            negative_nums.append(a)
        elif a > 0:
            positive_nums.append(a)
        else:
            zeros += 1
    negative_count = len(negative_nums) * len(positive_nums)
    zero_count = zeros * (N-1) - zeros * (zeros-1) // 2
    ans = 0
    if K <= negative_count:
        ans = search_negative(positive_nums, negative_nums, K)
    elif K <= negative_count + zero_count:
        ans = 0
    else:
        ans = search_positive(positive_nums, negative_nums,
                              K - negative_count - zero_count)
    print(ans)


if __name__ == "__main__":
    main()

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

pos_cnt = N - pos_start
neg_cnt = neg_end
zero_cnt = N - (pos_cnt + neg_cnt)

neg_pairs_cnt = pos_cnt * neg_cnt
zero_pairs_cnt = zero_cnt * (pos_cnt + neg_cnt) + (zero_cnt * (zero_cnt-1) // 2)

if K <= neg_pairs_cnt:
  
  ok, ng = 0, -10**18
  while abs(ok - ng) > 1:
    X = (ok+ng) // 2
    or_higher_cnt, r = 0, pos_start
    
    for l in range(neg_end):
      while r < N and A[l] * A[r] > X:
        r += 1
      
      or_higher_cnt += pos_cnt - (r - pos_start)

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

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

else:
  K -= (neg_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(pos_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(neg_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 numpy as np

n,k = map(int,input().split())
a = list(map(int,input().split()))
a = np.array(a)
a.sort()
plus = a[a>0]
zero = np.count_nonzero(a==0)
minus = a[a<0]

low = -10**20
hi = 10**20

while hi-low > 1:
    
    item = 0
    ave = (hi+low)//2

    
    if ave >= 0:
        item += zero*n

    
    
    item += a.searchsorted(ave//plus,side='right').sum()

    
    
    item += n*len(minus)-a.searchsorted(-(-ave//minus),side='left').sum()

    
    item -= np.count_nonzero(a*a <= ave)
    
    
    if item//2 >= k:
        hi = ave
    else:
        low = ave

print(hi)

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]
z=np.count_nonzero(a==0)
m=a[a<0]
r=10**19
l=-r
while r-l>1:
    
    
    b=(l+r)//2
    c=0
    if b>=0:
        c+=z*n
    
    c+=a.searchsorted(b//p,side='right').sum()
    
    c+=n*len(m)-a.searchsorted(-(-b//m),side='left').sum()
    c-=np.count_nonzero(a*a<=b)
    if c//2>=k:
        r=b
    else:
        l=b
print(r)

Solution (Python):
import numpy as N
n,k=map(int,input().split())
A=N.array(list(map(int,input().split())))
A.sort()
p=A[A>0]
z=N.count_nonzero(A==0)
m=A[A<0]
r=10**19
l=-r
while r-l>1:
    b=(l+r)//2
    c=0
    if b>=0:
        c+=z*n
    c+=A.searchsorted(b//p,side='right').sum()
    c+=n*len(m)-A.searchsorted(-(-b//m),side='left').sum()
    c-=N.count_nonzero(A*A<=b)
    if c//2>=k:
        r=b
    else:
        l=b
print(r)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,K = LI()
    pl = []
    mi = []
    z = 0
    for x in sys.stdin.readline().split():
        x = int(x)
        if x > 0:
            pl.append(x)
        elif x < 0:
            mi.append(-x)
        else:
            z += 1
    pl.sort()
    mi.sort()

    minus = len(pl) * len(mi)
    zero = z * (len(pl) + len(mi)) + z * (z-1) // 2

    h = INF
    l = -INF-1

    while l+1 < h:
        m = (h+l)//2

        if m > 0:
            k = minus + zero
            j = len(pl)-1
            for i in range(len(pl)-1):
                if i >= j: break
                while pl[i] * pl[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
            j = len(mi)-1
            for i in range(len(mi)-1):
                if i >= j: break
                while mi[i] * mi[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
        elif m < 0:
            k = 0
            j = 0
            if len(mi) > 0:
                for i in range(len(pl)-1,-1,-1):
                    while -pl[i] * mi[j] > m:
                        j += 1
                        if j == len(mi): break
                    else:
                        k += len(mi) - j
                        continue
                    break
        else:
            k = minus + zero

        if k < K:
            l = m
        else:
            h = m

    print(h)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
import numpy as np
def main():
    
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=np.array(readline().strip().split(),dtype="int64")
    
    a.sort()
    neg=a[a<0]
    neg_p=neg**2
    zero=a[a==0]
    pos=a[a>0]
    pos_p=pos**2
    l=-10**18-1
    r=10**18
    while l<r-1:
        x=(l+r)//2
        cnt=0
        if len(neg)>0:
            cnt+=(len(a)-np.searchsorted(a,(x+neg+1)//neg)).sum()
            cnt-=len(neg_p[neg_p<=x])
        if len(zero)>0:
            if x>=0:
                cnt+=(len(a)-1)*len(zero)
        if len(pos)>0:
            cnt+=np.searchsorted(a,x//pos,side="right").sum()
            cnt-=len(pos_p[pos_p<=x])

        cnt//=2
        if cnt>=k: r=x
        else: l=x

    print(r)

if __name__=="__main__":
    main()

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


num_neg = bisect.bisect_left(A, 0)

num_zero = bisect.bisect_right(A, 0) - num_neg

num_pos = N - num_neg - num_zero

A_neg_rev = A[:num_neg] 
A_pos = A[num_neg + num_zero:] 

A_neg = A_neg_rev[::-1] 
A_pos_rev = A_pos[::-1] 


cnt_zero = num_zero * (num_pos + num_neg) + (num_zero * (num_zero - 1) // 2)

cnt_neg = num_pos * num_neg


def syakutori_pos(arr, mid):
    if len(arr) == 0:
        return 0
    cnt = 0
    l = 0
    r = len(arr) - 1
    while l < r:
        if arr[l] * arr[r] <= mid:
            cnt += r - l
            l += 1
        else:
            r -= 1
    return cnt


def syakutori_neg(arr_pos, arr_neg, mid):
    if len(arr_pos) == 0 or len(arr_neg) == 0:
        return 0
    arr = arr_neg + arr_pos
    cnt = 0
    l = 0
    r = len(arr) - 1
    while l < len(arr_neg) and r >= len(arr_neg):
        if arr[l] * arr[r] <= mid:
            cnt += r - len(arr_neg) + 1
            l += 1
        else:
            r -= 1
    return cnt


ok = 10 ** 18
ng = -ok - 1
while ng + 1 < ok:
    mid = (ok + ng) // 2
    cnt = 0
    if mid > 0:
        cnt += cnt_zero
        cnt += cnt_neg
        cnt += syakutori_pos(A_pos, mid) + syakutori_pos(A_neg, mid)
    elif mid == 0:
        cnt += cnt_zero
        cnt += cnt_neg
    else:
        cnt += syakutori_neg(A_pos_rev, A_neg_rev, mid)
    if cnt >= K:
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):

stdin = open(0)

N, K = map(int, stdin.readline().split())

A = list(map(int, stdin.read().split()))






A.sort()
zero = list(filter(lambda x: x == 0, A))
pos = list(filter(lambda x: x > 0, A))
neg = list(filter(lambda x: x < 0, A))

pos_size = len(pos)
neg_size = len(neg)
zero_size = len(zero)

neg_count = pos_size * neg_size
pos_count = pos_size * (pos_size - 1) // 2 + neg_size * (neg_size - 1) // 2
zero_count = N * (N - 1) // 2 - neg_count - pos_count

if K > neg_count and K <= neg_count + zero_count:
    print(0)
    exit(0)

def f(x):
    """x以下の積の組み合わせを数える(k番目が負の場合)"""
    count = 0
    pos_idx = None
    neg_idx = 0
    for idx, p in enumerate(pos):
        if p * neg[neg_idx] <= x:
            pos_idx = idx
            break
    
    if pos_idx is not None:
        count += pos_size - pos_idx
        
        while neg_idx < neg_size - 1:
            neg_idx += 1
            ans = None
            for i in range(pos_idx, pos_size):
                if pos[i] * neg[neg_idx] <= x:
                    ans = i
                    break
            if ans is None:
                break
            count += pos_size - ans
            pos_idx = ans
    return count

def g(x):
    """x以下の積の組み合わせを数える(k番目が正の場合)"""
    count = neg_count + zero_count
    
    l_idx = 0
    r_idx = 0
    
    for idx, p in enumerate(reversed(pos)):
        if p * pos[l_idx] <= x:
            r_idx = pos_size - idx - 1
            break
    if r_idx > 0:
        count += (r_idx + 1) - 1  
        while r_idx - l_idx > 0:
            l_idx += 1
            ans = l_idx
            
            
            for i in range(r_idx, l_idx, -1):
            
            
                if pos[i] * pos[l_idx] <= x:
                    ans = i
                    break
            
            if ans > l_idx:
                count += ans - l_idx
                r_idx = ans
            else:
                break
    
    
    r_idx = neg_size - 1
    l_idx = neg_size - 1
    for idx, n in enumerate(neg):
        if n * neg[r_idx] <= x:
            l_idx = idx
            break
    
    if l_idx < r_idx:
        count += neg_size - l_idx - 1 
        
        while r_idx - l_idx > 0:
                r_idx -= 1
                ans = r_idx
                
                for i in range(l_idx, r_idx):
                    
                    if neg[i] * neg[r_idx] <= x:
                        ans = i
                        break
                
                
                if ans < r_idx:
                    count += r_idx - ans
                    l_idx = ans
                else:
                    break
    return count


def h(x):
    return f(x) if K <= neg_count else g(x)




def main():
    l = -1 * 10 ** 18
    r = 10 ** 18
    if K <= neg_count:
        r = 0
        h = f
    else:
        l = 0
        h = g

    while l + 1 < r:
        mid = (l + r) // 2
        count = h(mid)
        
        if count >= K:
            r = mid
        else:
            l = mid
    print(r)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N,K = MI()
A = LI()
minus,zero,plus = [], [], []
for i in A:
    if i<0:
        minus.append(i)
    elif i==0:
        zero.append(i)
    else:
        plus.append(i)
m = len(minus)
p = len(plus)
z = len(zero)
minus.sort()
plus.sort()

def count_lower_negpos(v): 
    if not minus or not plus:
        return 0
    m_idx = 0
    p_idx = 0
    ans = 0
    while True:
        val = minus[m_idx]*plus[p_idx]
        if val < v:
            ans += p - p_idx
            m_idx += 1
            if m_idx>m-1:
                break
        else:
            p_idx += 1
            if p_idx>p-1:
                break
    return ans

def count_lower_pospos(v): 
    if not plus:
        return 0
    left = 0
    right = p-1
    ans = 0
    while True:
        val = plus[left]*plus[right]
        if val < v:
            ans += right - left
            left += 1
            if left>=right:
                break
        else:
            right -= 1
            if left>=right:
                break
    return ans

def count_lower_negneg(v): 
    if not minus:
        return 0
    left = 0
    right = m-1
    ans = 0
    while True:
        val = minus[left]*minus[right]
        if val < v:
            ans += right - left
            right -= 1
            if left>=right:
                break
        else:
            left += 1
            if left>=right:
                break
    return ans


if K <= m*p: 
    l = -10**18-5
    r = 0
    while l+1<r:
        x = (l+r)//2
        if count_lower_negpos(x) < K:
            l = x
        else:
            r = x
    print(l)


elif K <= m*p+z*(m+p)+z*(z-1)//2: 
    print(0)

else: 
    K = K - (m*p+z*(m+p)+z*(z-1)//2)
    l = 0
    r = 10**18+5
    while l+1<r:
        x = (l+r)//2
        if count_lower_pospos(x)+count_lower_negneg(x) < K:
            l = x
        else:
            r = x
    print(l)

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):
from bisect import bisect_left, bisect_right

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

pos_start = bisect_right(a, 0)
neg_end = bisect_left(a, 0)

pos_cnt = n - pos_start
neg_cnt = neg_end

pairs_cnt = n * (n - 1) // 2
pos_pairs_cnt = pos_cnt * (pos_cnt - 1) // 2 + neg_cnt * (neg_cnt - 1) // 2
neg_pairs_cnt = pos_cnt * neg_cnt

if k <= neg_pairs_cnt:
    high = 0
    low = -10 ** 18
    while abs(high - low) > 1:
        mid = (high + low) // 2
        cnt = 0
        r = pos_start
        for l in range(neg_end):
            while r < n and mid < a[r] * a[l]:
                r += 1
            cnt += pos_cnt - (r - pos_start)

        if cnt >= k:
            high = mid
        else:
            low = mid

    print(high)

elif pairs_cnt - pos_pairs_cnt < k:
    k -= (pairs_cnt - pos_pairs_cnt)
    high = 10 ** 18
    low = 0
    while abs(high - low) > 1:
        mid = (high + low) // 2
        cnt = 0
        r = n - 1
        for l in range(pos_start, n):
            while l < r and mid < a[r] * a[l]:
                r -= 1
            cnt += max(0, r - l)
        
        l = 0
        for r in range(neg_end-1, -1, -1):
            while l < r and mid < a[r] * a[l]:
                l += 1
            cnt += max(0, r - l)

        if cnt >= k:
            high = mid
        else:
            low = mid

    print(high)

else:
    print(0)

Solution (Python):
from bisect import bisect_left, bisect_right

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

pos_start = bisect_right(a, 0)
neg_end = bisect_left(a, 0)

pos_cnt = n - pos_start
neg_cnt = neg_end

pairs_cnt = n * (n - 1) // 2
pos_pairs_cnt = pos_cnt * (pos_cnt - 1) // 2 + neg_cnt * (neg_cnt - 1) // 2
neg_pairs_cnt = pos_cnt * neg_cnt

if k <= neg_pairs_cnt:
    high = 0
    low = -10 ** 18
    while abs(high - low) > 1:
        mid = (high + low) // 2
        cnt = 0
        r = pos_start
        for l in range(neg_end):
            while r < n and mid < a[r] * a[l]:
                r += 1
            cnt += pos_cnt - (r - pos_start)

        if cnt >= k:
            high = mid
        else:
            low = mid

    print(high)

elif pairs_cnt - pos_pairs_cnt < k:
    k -= (pairs_cnt - pos_pairs_cnt)
    high = 10 ** 18
    low = 0
    while abs(high - low) > 1:
        mid = (high + low) // 2
        cnt = 0
        r = n - 1
        for l in range(pos_start, n):
            while l < r and mid < a[r] * a[l]:
                r -= 1
            cnt += max(0, r - l)
        
        l = 0
        for r in range(neg_end-1, -1, -1):
            while l < r and mid < a[r] * a[l]:
                l += 1
            cnt += max(0, r - l)

        if cnt >= k:
            high = mid
        else:
            low = mid

    print(high)

else:
    print(0)