Problem:
 Score: 400 points    Problem Statement  We have N integers A_1, A_2, ..., A_N .  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K -th number in that list?      Constraints   All values in input are integers.  2 \leq N \leq 2 \times 10^5  1 \leq K \leq \frac{N(N-1)}{2}  -10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)         Input  Input is given from Standard Input in the following format:  N  K  A_1  A_2  \dots  A_N       Output  Print the answer.        Sample Input 1 4 3
3 3 -4 -2      Sample Output 1 -6  There are six ways to form a pair. The products of those pairs are 9 , -12 , -6 , -12 , -6 , 8 .  Sorting those numbers in ascending order, we have -12 , -12 , -6 , -6 , 8 , 9 . The third number in this list is -6 .       Sample Input 2 10 40
5 4 3 2 -1 0 0 0 0 0      Sample Output 2 6       Sample Input 3 30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0      Sample Output 3 448283280358331064

Solution (Python):








def binary_search(*, ok, ng, func):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    import sys
    import numpy as np

    inf = 10 ** 18 + 1
    input = sys.stdin.readline

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

    A.sort()

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

    def count(x):
        """
        定数cに対して Ai*Aj<=c となる(i,j)の数え上げ
        順序制約 i<j -> 順序制約のない(i,j)からi==jの場合の個数を引いて2で割る
        iを固定して a=Ai とする
        a=0
            ax=0(<=c?),解なしまたは任意のx
        a>0
            ax<=c
            <-> x<=c/a
            <-> x<=c//a
        a<0
            ax<=c
            <-> (-a)x>=(-c)

            否定をとり,aの対候補全体=Nから引く

            (-a)x<(-c)
            <-> (-a)x<=(-c-1)
            <-> x<=(-c-1)//(-a)
        """
        cnt = 0
        if x >= 0:
            cnt += zero.size * N  
        cnt += np.searchsorted(a=A, v=x // pos, side='right').sum()  
        cnt += (N - np.searchsorted(a=A, v=(-x - 1) // (-neg), side='right')).sum()  
        cnt -= ((A * A) <= x).sum()  
        assert cnt % 2 == 0
        return cnt // 2

    ans = binary_search(
        ng=-inf,
        ok=inf,
        func=lambda x: count(x) >= K
    )

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def examA():
    C = [SI()for _ in range(3)]
    ans = C[0][0]+C[1][1]+C[2][2]
    print(ans)
    return

def examB():
    N, M = LI()
    P = [0]*N
    S = [LSI()for _ in range(M)]
    pena = 0
    ac = set()
    for p,s in S:
        p = int(p)-1
        if s=="WA":
            P[p] += 1
        else:
            if p in ac:
                continue
            ac.add(p)
            pena += P[p]

    print(len(ac),pena)
    return

def examC():
    W, H, N = LI()
    lx, rx, ly, ry = 0, W, 0, H
    A = [LI()for _ in range(N)]
    for x,y,a in A:
        if a==1:
            lx = max(lx,x)
        elif a==2:
            rx = min(rx,x)
        elif a==3:
            ly = max(ly,y)
        elif a==4:
            ry = min(ry,y)
    ans = max(0,rx-lx)*max(0,ry-ly)
    print(ans)
    return

def examD():
    N, H = LI()
    B = [0]*N
    maxa = 0
    ans = 0
    for i in range(N):
        a, B[i] = LI()
        if a>maxa:
            maxa = a
    B.sort(reverse=True)
    for b in B:
        if b<maxa:
            break
        H -= b
        ans += 1
        if H<=0:
            print(ans)
            return
    ans += -(-H//maxa)
    print(ans)
    return

def examE():
    A, B = LI()
    ans = [["
    i = 0; j = 0
    for _ in range(A-1):
        ans[i][j] = "."
        j += 2
        if j>=100:
            j = 0; i += 2
    i = 0; j = 0
    for _ in range(B-1):
        ans[99-i][j] = "
        j += 2
        if j>=100:
            j = 0; i += 2
    print(100,100)
    for v in ans:
        print("".join(map(str,v)))
    return

def examF():
    def search_1(need):
        l = 0; r = inf+1
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            cur += shakutori(neg,pos,now)
            
            if cur>=need:
                l = now
            else:
                r = now
            
        return -l
    def search_2(need):
        need *= 2
        
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            cur += shakutori_2(neg,now)
            cur += shakutori_2(pos,now)
            if cur>=need:
                r = now
            else:
                l = now
            
        return r
    def shakutori(A,B,k):
        n = len(A)
        m = len(B)
        rep = 0
        r = 0
        for l in range(n)[::-1]:
            while(r<m-1 and A[l]*B[r]<k):
                r += 1
            if (A[l]*B[r]>=k):
                rep += m-r
        return rep
    def shakutori_2(C,k):
        n = len(C)
        rep = 0
        r = n-1
        for l in range(n):
            while(r>0 and C[l]*C[r]>k):
                r -= 1
            if (C[l]*C[r]<=k):
                rep += r+1
                if r >= l:
                    rep -= 1
        return rep
    N, K = LI()
    A = LI()
    neg = []; pos = []; arr_0 = 0
    for a in A:
        if a<0:
            neg.append(-a)
        elif a==0:
            arr_0 += 1
        else:
            pos.append(a)
    neg.sort(); pos.sort()
    
    if len(neg)*len(pos)>=K:
        ans = search_1(K)
    elif len(neg)*len(pos)+arr_0*(len(neg)+len(pos))+arr_0*(arr_0-1)//2>=K:
        ans = 0
    else:
        ans = search_2(K-len(neg)*len(pos)-arr_0*(len(neg)+len(pos))-arr_0*(arr_0-1)//2)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
87940638538504699
448283280358331064
"""

Solution (Python):
import numpy as np


def get_Negative(K, pos, neg):
    K = len(pos) * len(neg) - K + 1
    l = 0
    r = 10 ** 18 + 10
    while r - l > 1:
        m = (l + r) // 2
        target = m // pos
        x = np.searchsorted(neg, target, side="right").sum()
        if x >= K:
            r = m
        else:
            l = m
    return -r


def get_Positive(K, pos, neg):
    l = 0
    r = 10 ** 18 + 10
    tmp_pos = np.arange(len(pos))
    tmp_neg = np.arange(len(neg))
    while r - l > 1:
        m = (r + l) // 2
        cnt = 0
        if len(pos) > 1:
            t1 = m // pos
            x1 = np.searchsorted(pos, t1, side="right")
            x1 = np.maximum(0, x1 - tmp_pos - 1)
            cnt += x1.sum()
        if len(neg) > 0:
            t2 = m // neg
            x2 = np.searchsorted(neg, t2, side="right")
            x2 = np.maximum(0, x2 - tmp_neg - 1)
            cnt += x2.sum()
        if cnt >= K:
            r = m
        else:
            l = m
    return r


def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)

    positive = A[A > 0]
    negative = -A[A < 0]
    positive.sort()
    negative.sort()

    Npos = len(positive)
    Nneg = len(negative)
    Nzero = N - Npos - Nneg

    P_neg = Npos * Nneg
    P_pos = 0
    if Npos:
        P_pos += Npos * (Npos - 1) // 2
    if Nneg:
        P_pos += Nneg * (Nneg - 1) // 2
    P_zero = N * (N - 1) // 2 - P_pos - P_neg

    if K <= P_neg:
        ans = get_Negative(K, positive, negative)
        return ans
    K -= P_neg
    if K <= P_zero:
        return 0
    K -= P_zero
    ans = get_Positive(K, positive, negative)
    return ans


if __name__ == "__main__":
    print(main())

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



def calc_leq_neg(m):
  ret=0
  j=0
  for i in range(len(alist_neg)):
    while j<len(alist_pos):
      if alist_neg[i]*alist_pos[j]<=m:
        ret+=len(alist_pos)-j
        break
      else:
        j+=1
  return ret

def calc_leq_pos(m):
  ret=0
  j=0
  alist_neg2=alist_neg[::-1]
  for i in range(len(alist_neg)):
    while j<len(alist_neg):
      if alist_neg[i]*alist_neg2[j]<=m:
        ret+=len(alist_neg)-j
        if alist_neg[i]<=alist_neg2[j]:
          ret-=1
        break
      else:
        j+=1
        
  j=0
  alist_pos2=alist_pos[::-1]
  for i in range(len(alist_pos)):
    while j<len(alist_pos):
      if alist_pos[i]*alist_pos2[j]<=m:
        ret+=len(alist_pos)-j
        if alist_pos[i]<=alist_pos2[j]:
          ret-=1
        break
      else:
        j+=1

  return ret//2

alist_neg,alist_pos=[],[]
num_neg,num_zero,num_pos=0,0,0
for a in alist:
  if a<0:
    num_neg+=1
    alist_neg.append(a)
  elif a>0:
    num_pos+=1
    alist_pos.append(a)
  else:
    num_zero+=1
alist_neg.sort()
alist_pos.sort()
    
num_neg_prod=num_neg*num_pos
num_pos_prod=((num_pos*(num_pos-1))//2)+((num_neg*(num_neg-1))//2)
num_zero_prod=(N*(N-1))//2-num_neg_prod-num_pos_prod


if K<=num_neg_prod:
  
  
  
  l,r=alist_neg[0]*alist_pos[-1],-1
  while l<=r:
    mid=(l+r)//2
    k1=calc_leq_neg(mid-1)
    k2=calc_leq_neg(mid)
    
    if k1<K<=k2:
      print(mid)
      break
    elif k1>=K:
      r=mid-1
    else:
      l=mid+1  
elif K<=num_neg_prod+num_zero_prod:
  print(0)
else:
  
  K-=num_neg_prod+num_zero_prod
  for i in range(len(alist_neg)):
    alist_neg[i]*=-1
  alist_neg.sort()  
  
  
  l,r=float("inf"),0
  if len(alist_neg)>=2:
    l=alist_neg[0]*alist_neg[1]
    r=alist_neg[-2]*alist_neg[-1]
  if len(alist_pos)>=2:
    l=min(l,alist_pos[0]*alist_pos[1])
    r=max(r,alist_pos[-2]*alist_pos[-1])
  
  while l<=r:
    mid=(l+r)//2
    k1=calc_leq_pos(mid-1)
    k2=calc_leq_pos(mid)
    
    if k1<K<=k2:
      print(mid)
      break
    elif k1>=K:
      r=mid-1
    else:
      l=mid+1

Solution (Python):

import sys


def main(N, K, Ap, Am):
    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)


    return

if __name__ == '__main__':
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    Ap = []
    Am = []
    
    for _ in range(N):
        t = int(next(tokens))
        if t>=0:
            Ap.append(t)
        elif t<0:
            Am.append(t)
    main(N, K, Ap, Am)

Solution (Python):
from bisect import bisect_left,bisect_right

def cntneg(X):
    cnt,r=0,posst
    for l in range(negend):
        while r<N and A[l]*A[r]>X:
            r+=1
        cnt+=poscnt-(r-posst)
    return cnt
def cntpos(X):
    cnt,r=0,N-1
    
    for l in range(posst,N):
        while l<r and A[l]*A[r]>X:
            r-=1
        cnt+=max(0,r-l)
    l=0
    for r in range(negend-1,-1,-1):
        while l<r and A[l]*A[r]>X:
            l+=1
        cnt+=max(0,r-l)
    return cnt

N,K=map(int,input().split())
A=sorted(map(int,input().split()))
negend=bisect_left(A,0);posst=bisect_right(A,0)
poscnt=N-posst;negcnt=negend;zerocnt=N-poscnt-negcnt
zeroans=zerocnt*(poscnt+negcnt)+zerocnt*(zerocnt-1)//2
posans=poscnt*(poscnt-1)//2+negcnt*(negcnt-1)//2
negans=negcnt*poscnt

if(K<=negans):
    ng,ok=-10**18,0
    while abs(ok-ng)>1:
        X=(ng+ok)//2
        if cntneg(X)>=K:
            ok=X
        else:
            ng=X
elif(K<=negans+zeroans):
    print(0)
    exit()
else:
    K-=negans+zeroans
    ng,ok=0,10**18
    while abs(ok-ng)>1:
        X=(ng+ok)//2
        if cntpos(X)>=K:
            ok=X
        else:
            ng=X
            
print(ok)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, K = lr()
A = np.array(lr()); A.sort()
neg = A[A<0]
zero = A[A==0]
pos = A[A>0]

def check(x):
    '''x以下の積がK個以上あるならTrueを返す'''
    cnt = 0  
    if x >= 0:
        cnt += len(zero) * N
    cnt += (np.searchsorted(A, x//pos, side='right')).sum()
    cnt += (N - np.searchsorted(A, (-x-1)//(-neg), side='right')).sum()
    cnt -= np.count_nonzero(A*A <= x)
    assert cnt % 2 == 0
    return (cnt//2) >= K

ok = 10**18; ng = -10**18-1
while abs(ng-ok) > 1:
    mid = (ok+ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, K = lr()
A = np.array(lr()); A.sort()
neg = A[A<0]
zero = A[A==0]
pos = A[A>0]

def check(x):
    '''x以下の積がK個以上あるならTrueを返す'''
    cnt = 0  
    if x >= 0:
        cnt += len(zero) * N
    cnt += (np.searchsorted(A, x//pos, side='right')).sum()
    cnt += (N - np.searchsorted(A, (-x-1)//(-neg), side='right')).sum()
    cnt -= np.count_nonzero(A*A <= x)
    assert cnt % 2 == 0
    return (cnt//2) >= K

ok = 10**20; ng = -10**20
while abs(ng-ok) > 1:
    mid = (ok+ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

print(ok)

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


np = 0
nA = []
zp = 0
pp = 0
pA = []


for i in A:
    if i < 0:
        np += 1
        nA.append(-i)
    elif i >0:
        pp += 1
        pA.append(i)
    else:
        zp += 1
nA=nA[::-1]



ncc = np*pp
zcc = zp*(np+pp)+(zp*(zp-1))//2
pcc = (np*(np-1))//2+(pp*(pp-1))//2


if K <= ncc:
    K = ncc-K
    
    
    minK = 0
    maxK = 10**18+1
    while maxK-minK != 1:
        x = (maxK+minK)//2
        
        count = 0
        pos = pp-1
        for i in range(np):
            while pos != -1:
                if pA[pos] > x//nA[i]:
                    pos -= 1
                else:
                    break
            count += pos+1
        if count > K:
            maxK = x
        else:
            minK = x
    print(-maxK)
elif K <= (ncc+zcc):
    print(0)

else:
    K-=(ncc+zcc)
    
    minK = 0
    maxK = 10 ** 18
    x = 0
    while maxK-minK != 1:
        x = (maxK + minK) // 2
        
        count = 0
        pos = np-1
        for i in range(np):
            while pos !=-1:
                if nA[pos] > x//nA[i]:
                    pos -=1
                else:
                    break
            count += pos+1
            if nA[i]**2<x:
                count -= 1
        pos = pp-1
        for i in range(pp):
            while pos != -1:
                if pA[pos] > x // pA[i]:
                    pos -= 1
                else:
                    break
            count += pos + 1
            if pA[i] ** 2 < x:
                count -= 1
        count = count//2
        if count >= K:
            maxK = x
        else:
            minK = x
    print(maxK)

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

plus=a[a>0]
zeros=np.sum(a==0)
minus=a[a<0]

def counter(T):
  c=0
  if T>=0:
    c+=zeros*n
  c+=np.searchsorted(a,T//plus,side='right').sum()
  c+=(n-np.searchsorted(a,(-T-1)//(-minus),side='right')).sum()
  c-=np.count_nonzero(a*a<=T)
  return c//2

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

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

Solution (Python):
import bisect
import numpy as npy
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
n0,np,nn = 0,0,0
for i in a:
  if i>0:  np += 1
  elif i == 0:  n0 += 1
  else:  nn += 1
kp = (np**2-np+nn**2-nn)//2
k0 = n0*(n-n0)+(n0**2-n0)//2
kn = nn*np
if kn < k <= kn+k0:
  print(0)
  exit()
nls = []
pls = []
for i in range(n):
  if a[i] < 0:
    nls.append(a[i])
  elif a[i] > 0:
    pls.append(a[i])
ln = len(nls)
lp = len(pls)
nls = npy.array(nls,dtype=npy.int64)
pls = npy.array(pls,dtype=npy.int64)
if k <= kn:
  l = a[0]*a[-1]-1
  r = 0
  while l+1 < r:
    m = (l+r)//2
    mls = m//nls
    tmp = npy.searchsorted(pls,mls,side="right").sum()
    if tmp > kn-k:
      l = m
    else:
      r = m
  print(l)
else:
  nls = -nls
  nls = nls[::-1]
  k -= kn+k0
  l = 0
  r = max(a[0]**2,a[-1]**2)+1
  while l+1 < r:
    m = (l+r)//2
    tmp  = npy.searchsorted(nls,m//nls,side="right").sum()
    tmp += npy.searchsorted(pls,m//pls,side="right").sum()
    tmp -= npy.searchsorted(nls**2,m,side="left")
    tmp -= npy.searchsorted(pls**2,m,side="left")
    if tmp >= 2*k:
      r = m
    else:
      l = m
  print(r)

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

ap, am, a0 = [], [], []
for i in a:
    if i > 0:
        ap.append(i)
    elif i < 0:
        am.append(i)
    else:
        a0.append(i)
lp, lm, l0 = len(ap), len(am), len(a0)
ap.sort()
am.sort(reverse=True)


if k <= lp * lm:
    start = max(ap) * min(am)
    stop = -1
    while start < stop:
        
        
        num = 0
        i = (start + stop) // 2
        j = 0
        flag = True
        for l in range(lm-1, -1, -1):
            while flag and am[l] * ap[j] > i:
                j += 1
                if j == lp:
                    flag = False
                    break
            num += lp - j
        if num < k:
            start = i + 1
        else:
            stop = i
    print(start)

elif k <= lp * lm + (lp + lm) * l0 + l0 * (l0 - 1) // 2:
    print(0)

else:
    k -= lp * lm + (lp + lm) * l0 + l0 * (l0 - 1) // 2
    start = 1
    if ap == []:
        stop = min(am) * min(am)
    elif am == []:
        stop = max(ap) * max(ap)
    else:
        stop = max([max(ap) * max(ap), min(am) * min(am)])
    while start < stop:
        
        
        num = 0
        i = (start + stop) // 2

        
        j = 0
        flag = True
        flag2 = True
        for l in range(lp-1, -1, -1):
            while flag and ap[l] * ap[j] <= i:
                if flag2 and l <= j:
                    num -= l + 1
                    flag2 = False
                j += 1
                if j == lp:
                    flag = False
            num += j

        
        j = 0
        flag = True
        flag2 = True
        for l in range(lm-1, -1, -1):
            while flag and am[l] * am[j] <= i:
                if flag2 and l <= j:
                    num -= l + 1
                    flag2 = False
                j += 1
                if j == lm:
                    flag = False
            num += j

        num //= 2
        if num < k:
            start = i + 1
        else:
            stop = i
    print(start)

Solution (Python):
f=lambda:map(int,input().split())
n,k=f()
lm,lp=[],[]
for i in f():
  if i<0: lm.append(-i)
  else: lp.append(i)
lm.sort()
lp.sort()
cm=len(lm)
cp=len(lp)
def cnt(x):
  c=0
  if x<0:
    r=cp
    for i in lm:
      while r and i*lp[r-1]>=-x: r-=1
      c+=cp-r
    return c
  r=cm
  for i in lm:
    while r and i*lm[r-1]>x: r-=1
    c+=r
    if i*i<=x: c-=1
  r=cp
  for i in lp:
    while r and i*lp[r-1]>x: r-=1
    c+=r
    if i*i<=x: c-=1
  return cm*cp+c//2
INF=10**18+1
l,r=-INF,INF
while r-l>1:
  m=l+r>>1
  if cnt(m)<k: l=m
  else: r=m
print(r)

Solution (Python):
import numpy as np
import sys
input=sys.stdin.readline
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
pos = np.sort(a[a>0])
neg = np.sort(np.abs(a[a<0]))
zero = (a==0).sum()

INF = 2*(10**18)
l = -INF
r = INF
while(r-l>1):
    mid = (l+r)//2
    cnt = 0
    if mid >= 0:
        cnt = len(pos)*len(neg)  
        cnt += (len(pos)+len(neg)) * zero 
        cnt += (zero*(zero-1))//2 
        x = np.searchsorted(pos, mid//pos, side='right').sum() 
        x += np.searchsorted(neg, mid//neg, side='right').sum() 
        x -= (pos*pos<=mid).sum()
        x -= (neg*neg<=mid).sum()
        cnt += x/2
    else:
        
        cnt = (len(neg) - np.searchsorted(neg, abs(mid)//pos + (mid%pos!=0), side='left')).sum()
    
    
    
    
    
    if cnt < k:
        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())))
pos = np.sort(a[a>0])
neg = np.sort(np.abs(a[a<0]))
zero = (a==0).sum()

INF = 2*(10**18)
l = -INF
r = INF

while(r-l>1):
    mid = (l+r)//2
    cnt = 0
    if mid >= 0:
        cnt = len(pos)*len(neg)  
        cnt += (len(pos)+len(neg)) * zero 
        cnt += (zero*(zero-1))//2 
        x = np.searchsorted(pos, mid//pos, side='right').sum() 
        x += np.searchsorted(neg, mid//neg, side='right').sum() 
        x -= (pos*pos<=mid).sum()
        x -= (neg*neg<=mid).sum()
        cnt += x/2
    else:
        
        cnt = (len(neg) - np.searchsorted(neg, abs(mid)//pos + (mid%pos!=0), side='left')).sum()
    
    
    
    
    
    if cnt < k:
        l = mid
    else:
        r = mid
print(r)

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

a.sort()

def check(t):
    j = n - 1 if t > 0 else 0
    res = 0
    f = 1

    cond = lambda x, t, f:x <= t if f * t > 0 or (t == 0 and f == -1) else x > t
    shift = lambda x, t:x-1 if t > 0 else x+1
    count = lambda x, n, f:n-x if f == 1 else x

    for ai in a:
        if f == 1 and ai > 0:
            f = -1
            j = n - 1 if t > 0 else 0
        if ai:
            while j >= 0 and j < n and cond(ai * a[j], t, f):
                j = shift(j, t)
            if t > 0:
                res += count(j+1, n, f)
            else:
                res += count(j, n, f)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2
            

m = max(max(a)**2, min(a)**2)
l = -m
r = m

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

if check(l) == k:
    print(l)
else:
    print(r)

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


A = np.array(sorted(list(map(int,input().split()))), np.int64)
posA = A[A > 0] 
negA = A[A < 0] 
z = (A==0).sum() 

left = -10**18
right = 10**18

while left+1 < right:
    num = (left+right)//2
    
    count = 0 
    
    if num >= 0:
        
        count += z*n 
    
    limit_pos = num // posA
    
    limit_idx = np.searchsorted(A, limit_pos, side='right')
    count += limit_idx.sum()

    
    limit_neg = -(-num // negA)
    
    limit_idx = n - np.searchsorted(A, limit_neg, side='left')
    count += limit_idx.sum()
    
    duplicate_cases = (A ** 2 <= num).sum()

    count -= duplicate_cases
    count //= 2

    if count >= k:
        right = num
    else:
        left = num

print(right)

Solution (Python):
import numpy as np

n, k = map(int, input().split()) 
a_list = np.array(list(map(int, input().split())))

a_list.sort()

zero_list = a_list[a_list == 0]
minus_list = a_list[a_list < 0]
plus_list = a_list[a_list > 0]

def index_count(x):
    cnt = 0
    if x >= 0:
        cnt += len(zero_list) * n
    cnt += np.searchsorted(a_list, x // plus_list, side='right').sum()
    cnt += (n - np.searchsorted(a_list, -(-x // minus_list), side='left')).sum()
    cnt -= np.count_nonzero(a_list * a_list <= x)
 
    assert cnt % 2 == 0
    return cnt // 2
 
 
left = -10**18
right = 10**18
 
while left + 1 < right:
    mid = (left + right) // 2
    a = index_count(mid)
    if a >= k:
        right = mid
    else:
        left = mid
 
print(right)

Solution (Python):
from copy import copy

def solve_negative():
    def count_less_x(x):
        ret = 0
        i = 0
        j = 0
        while i < len(negative_a):
            while j < len(positive_a) and positive_a[j] * negative_a[i] > x:
                j += 1
            ret += len(positive_a) - j
            i += 1

        return ret

    upper = -1
    lower = -1000000001*1000000001
    while upper - lower > 1:
        middle = (upper + lower) // 2
        if count_less_x(middle) >= k:
            upper = middle
        else:
            lower = middle
    return upper


def solve_positive():
    def count_less_x(x):
        ret = 0
        i = 0
        j = len(positive_a) - 1
        while i < len(positive_a):
            while j > i and positive_a[i] * positive_a[j] > x:
                j -= 1
            ret += j - i
            i += 1
            if i >= j:
                break
        i = 0
        j = len(r_negative_a) - 1
        while i < len(r_negative_a):
            while j > i and r_negative_a[i] * r_negative_a[j] > x:
                j -= 1
            ret += j - i
            i += 1
            if i >= j:
                break
        return ret
    lower = 0
    upper = 1000000001*1000000001
    while upper - lower > 1:
        middle = (upper + lower) // 2
        if count_less_x(middle) + num_mul_n + num_mul_z >= k:
            upper = middle
        else:
            lower = middle
    return upper


def solve_zero():
    return 0


def create_sign_split_a(a):
    negative = []
    positive = []
    zero = []
    for x in a:
        if x < 0:
            negative.append(x)
        elif x > 0:
            positive.append(x)
        else:
            zero.append(x)
    return negative, zero, positive


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

a.sort()

num_n = sum([(a_ < 0) for a_ in a])
num_p = sum([(a_ > 0) for a_ in a])
num_z = sum([(a_ == 0) for a_ in a])
negative_a, zero_a, positive_a = create_sign_split_a(a)
r_negative_a = copy(negative_a)
r_negative_a.reverse()

num_mul_p = num_n * (num_n - 1) // 2 + num_p * (num_p - 1) // 2
num_mul_z = num_n * num_z + num_p * num_z + num_z * (num_z - 1) // 2
num_mul_n = n * (n - 1) // 2 - num_mul_p - num_mul_z


if num_mul_n >= k:
    ans = solve_negative()
elif num_mul_n < k <= num_mul_n + num_mul_z:
    ans = solve_zero()
else:
    ans = solve_positive()
print(ans)

Solution (Python):
import numpy as np
N,K = [int(i) for i in input().split(' ')]

A = np.array([int(i) for i in input().split(' ')])

A.sort()
zero = A[A==0]
minus = A[A<0]
plus = A[A>0]

def index_count(x):
    cnt = 0
    if x >= 0:
        cnt += len(zero) * N
    cnt += np.searchsorted(A,x//plus,side='right').sum()
    cnt += (N - np.searchsorted(A,-(-x//minus),side='left')).sum()
    cnt -= np.count_nonzero(A*A <= x)

    assert cnt % 2 == 0
    return cnt //2


left = -10**18
right = 10**18

while left + 1 < right:
    mid = (left +right) //2
    a = index_count(mid)
    if a >= K:
        right = mid
    else:
        left = mid

print(right)

Solution (Python):


from bisect import bisect

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

cnt_positive = N - bisect(A, 0)
cnt_zero = A.count(0)
cnt_negative = N - cnt_positive - cnt_zero


def is_ok(mid):
    
    if mid < 0:
        cnt_under_mid = 0
        
        j = 1
        for i in range(cnt_negative):
            a = A[i]
            
            while a * A[j] > mid:
                j += 1
                if j >= N:
                    break
            
            cnt_under_mid += (N - j)

            
            if cnt_under_mid >= K:
                return True

            
            if j >= N:
                break

        return False

    

    else:
        """
        こちらではmidより大きくなる個数を全ペアの個数から引いて考える
        """
        cnt_over_mid = 0
        cnt_duplicate = 0
        r = cnt_negative-1 
        for l in range(cnt_negative):
            a = A[l]
            
            while a * A[r] <= mid:
                r -= 1
                
                if r <= -1:
                    break
            cnt_over_mid += r+1 
            
            if r >= l: cnt_duplicate += 1
            
            
            if r <= -1:
                break
        
        
        cnt_not_positive = cnt_negative + cnt_zero
        l = cnt_not_positive
        
        for r in range(N-1, cnt_not_positive-1, -1):
            a = A[r]
            while a * A[l] <= mid:
                
                l += 1
                
                if l >= N:
                    break
            
            cnt_over_mid += N-l
            
            if l <= r:
                cnt_duplicate += 1

            
            if l >= N:
                break
        
        cnt_under_mid = (N*(N-1) // 2) - ((cnt_over_mid - cnt_duplicate) // 2)
        return cnt_under_mid >= K


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

while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print(ok)