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
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


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

    return cnt // 2


N, K, *A = map(int, read().split())
A = np.array(A)
A.sort()

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

r = 10**18
l = -r

while r - l > 1:
    m = (r + l) // 2
    if count(m) >= K:
        r = m
    else:
        l = m

print(r)

Solution (Python):
from sys import stdin
import numpy as np

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = np.sort(np.array([int(x) for x in stdin.readline().rstrip().split()]))
MINUS = A[A<0]
ZERO = A[A==0]
PLUS = A[A>0]

def solve(x):
    count_tpl = 0
    if x >= 0:
        count_tpl += len(ZERO) * N
    count_tpl += np.searchsorted(A, x // PLUS, side='right').sum()
    count_tpl += (N - np.searchsorted(A, (-x-1)//(-MINUS), side='right')).sum()
    count_tpl -= np.count_nonzero(A * A <= x)
    assert count_tpl % 2 == 0
    return count_tpl // 2

left = -10**18
right = 10**18
while left + 1 < right:
    x = (left + right) // 2
    if solve(x) >= K:
        right = x
    else:
        left = x
print(right)

Solution (Python):
def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.readline

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

    minus = []
    plus = []
    zero = 0
    for a in A:
        if a > 0:
            plus.append(a)
        elif a < 0:
            minus.append(-a)
        else:
            zero += 1
    plus.sort()
    minus.sort()
    plus_num = len(plus)
    minus_num = len(minus)
    if plus_num * minus_num < K <= (N*(N-1))//2 - (plus_num*(plus_num-1))//2 - (minus_num*(minus_num-1))//2:
        print(0)
        exit()
    if plus_num * minus_num >= K:
        ng = 0
        ok = -10**18-1
        mid = (ng+ok)//2
        while ng - ok > 1:
            cnt = 0
            j = 0
            for a in reversed(minus):
                while True:
                    if j == plus_num:
                        break
                    if a * plus[j] < -mid:
                        j += 1
                    else:
                        break
                
                cnt += plus_num - j
            
            if cnt < K:
                ok = mid
            else:
                ng = mid
            mid = (ok+ng)//2
        print(ng)
    else:
        K -= (N*(N-1))//2 - (plus_num*(plus_num-1))//2 - (minus_num*(minus_num-1))//2
        ng = 10**18+1
        ok = 0
        mid = (ok+ng)//2
        while ng - ok > 1:
            cnt = 0
            j = plus_num-1
            for a in plus:
                while True:
                    if j == -1:
                        break
                    if a * plus[j] > mid:
                        j -= 1
                    else:
                        break
                cnt += j+1
            for a in plus:
                if a**2 <= mid:
                    cnt -= 1
                else:
                    break
            j = minus_num-1
            for a in minus:
                while True:
                    if j == -1:
                        break
                    if a * minus[j] > mid:
                        j -= 1
                    else:
                        break
                cnt += j+1
            for a in minus:
                if a**2 <= mid:
                    cnt -= 1
                else:
                    break
            
            assert cnt%2 == 0
            cnt //= 2
            if cnt < K:
                ok = mid
            else:
                ng = mid
            mid = (ok+ng)//2
        print(ng)


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left, bisect_right

def main():
    n, k = [int(s) for s in input().strip().split()]
    A = [int(s) for s in input().strip().split()]
    
    P = sorted(a for a in A if a > 0)
    N = sorted(a for a in A if a < 0)
    pp, nn = len(P), len(N)
    negpair = pp * nn
    pospair = pp * (pp - 1) // 2 + nn * (nn - 1) // 2

    if negpair < k <= n * (n - 1) // 2 - pospair:
        print(0)
        return
    
    if k <= negpair:
        lo, hi = -(10 ** 18), -1
        while lo < hi:
            x = (lo + hi) // 2

            j = 0
            cnt = 0
            for i in range(pp):
                while j < nn and P[i] * N[j] <= x:
                    j += 1
                cnt += j

            if cnt >= k:
                hi = x
            else:
                lo = x + 1
        print(lo)
    
    else:
        class Helper:
            def __getitem__(self, x):
                j = pp - 1
                cnt = 0
                for i in range(pp):
                    while j > i and P[i] * P[j] > x:
                        j -= 1
                    cnt += max(j - i, 0)
                j = nn - 1
                for i in range(nn):
                    while j > i and N[i] * N[j] <= x:
                        j -= 1
                    cnt += nn - 1 - max(i, j)
                return cnt
        
        x = bisect_left(Helper(), k - (n * (n - 1) // 2 - pospair), lo=1, hi=10 ** 18)
        print(x)


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

zero = np.count_nonzero(a == 0)
positive = a[a > 0] 
negative = a[a < 0]

def count(x): 
  ans = 0
  if x >= 0: 
    ans += n * zero
  ans += np.searchsorted(a, x // positive, side="right").sum() 
  ans += n * len(negative) - np.searchsorted(a, -(-x // negative), side="left").sum() 
  ans -= np.count_nonzero(a * a <= x) 
  return ans // 2

ok = 10**18
ng = -ok - 1
while ok - ng > 1: 
  cen = (ok + ng) // 2
  if count(cen) >= k:
    ok = cen
  else:
    ng = cen
print(ok)

Solution (Python):
import numpy as np
stdin = open(0)
 
N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().split(), np.int64)
 
 
A = np.sort(A)
zero = A[A == 0]
pos = A[A > 0]
neg = A[A < 0]
 
 
def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    
    if x >= 0:
        cnt_tpl += len(zero) * N
    
    cnt_tpl += np.searchsorted(A, x // pos, side='right').sum()
    
    cnt_tpl += (N - np.searchsorted(A, (-x - 1) // (-neg), side='right')).sum()
    
    cnt_tpl -= np.count_nonzero(A * A <= x)
    assert cnt_tpl % 2 == 0
    return cnt_tpl // 2
 
 
left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x
 
 
print(right)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mA, nA, zc = [], [], 0
dd = []
for a in A:
    if a<0:
        mA.append(a)
    elif a>0:
        nA.append(a)
    else:
        zc += 1
    dd.append(a*a)


lnA = len(nA)
lmA = len(mA)

def F(idx):
    j = lnA-1
    r = 0
    for a in nA:
        while j >= 0:
            if nA[j]*a <= idx:
                break
            j -= 1
        r += j+1
    if idx >= 0:

        r += 2*(zc*N) - zc*zc

    j = 0
    for a in mA[::-1]:
        while j < lmA:
            if mA[j]*a <= idx:
                break
            j += 1
        r += lmA-j
    j = 0
    for a in mA:
        while j < lnA:
            if nA[j]*a <= idx:
                break
            j += 1
        r += 2*(lnA-j)

    for a in dd:
        if a <= idx:
            r-=1
    return r//2


mx, mn = 2*10**18, -2*10**18
idx = (mx + mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        idx, mn = (idx + mx)//2, idx
        continue
    idx, mx = (idx + mn)//2, idx
print(idx+1)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
minus = [-x for x in a if x < 0]
plus = [x for x in a if x >= 0]

minus.sort()
plus.sort()

def solve(x):
    ans = 0
    if x < 0:
        x = -x
        r = 0
        for mi in minus[::-1]:
            while r < len(plus) and plus[r]* mi < x:
                r += 1
            ans += len(plus) - r
        return ans

    r = 0
    for l in minus[::-1]:
        if l * l <= x:ans -= 1
        while r < len(minus) and minus[r]*l <= x:
            r += 1
        ans += r
    r = 0
    for l in plus[::-1]:
        if l * l <= x: ans -= 1
        while r < len(plus) and plus[r] * l <= x:
            r += 1
        ans += r

    ans //= 2
    ans += len(minus)*len(plus)
    return ans

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

print(high)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
minus = [-x for x in a if x < 0]
plus = [x for x in a if x >= 0]

minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        x = -x
        r = 0
        for num in minus[::-1]:
            while r < len(plus) and plus[r] * num < x:
                r += 1
            ans += len(plus) -  r
        return ans

    r = 0
    for num in minus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(minus) and minus[r] * num <= x:
            r += 1
        ans += r
    r = 0
    for num in plus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(plus) and plus[r] * num <= x:
            r += 1
        ans += r
    ans //= 2
    ans += len(minus) * len(plus)
    return ans

bottom = 0
top = 2*(10**18) + 2


while top - bottom > 1:
    mid = (top + bottom) // 2
    if cnt(mid - 10**18-1) < k:
        bottom = mid
    else:
        top = mid

print(int(top - 10**18-1))

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

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

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

p.sort()
m.sort()

ng, ok = -(10 ** 18)-1, 10 ** 18+1
while ok - ng > 1 :
  mid = (ok + ng) // 2
  s = 0 
  if mid < 0 :
    j = 0
    for i in range(len(m) - 1, -1, -1) :
      while j < len(p) and m[i] * p[j] < -mid :
        j += 1
      s += len(p) - j
      
  else :
    j = len(p) - 1
    for i in range(len(p)) :
      while j >= 0 and p[i] * p[j] > mid :
        j -= 1
      s += max(0, j - i)
      
    j = len(m) - 1
    for i in range(len(m)) :
      while j >= 0 and m[i] * m[j] > mid :
        j -= 1
      s += max(0, j - i)
      
    s += (len(p) + len(m)) * zero + len(p) * len(m) + zero * (zero - 1) // 2

  if s < K :
    ng = mid
  else :
    ok = mid
    
print(ok)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

plus = minus = zero = 0
ps = []
ms = []
for i in a:
    if i == 0:
        zero += 1
    elif i > 0:
        plus += 1
        ps.append(i)
    else:
        minus += 1
        ms.append(-i)

ps.sort()
ms.sort()

def check(m):
    if m == 0:
        return plus*minus + zero*(zero-1)//2 + zero*(plus+minus) >= k
    elif m > 0:
        tmp = plus*minus + zero*(zero-1)//2 + zero*(plus+minus)
        for l in [ps, ms]:
            X = len(l)
            cur = X-1
            for i in range(X):
                while cur >= 0 and l[i]*l[cur] > m:
                    cur -= 1
                if cur <= i:
                    break
                tmp += cur-i
        return tmp >= k
    else:
        tmp = 0
        cur = 0
        for i in reversed(range(plus)):
            while cur < minus and ms[cur]*ps[i] < -m:
                cur += 1
            tmp += minus-cur
        return tmp >= k

left = -10**20
right = 10**20

while right-left>1:
    mid = (right+left)//2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)

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

Solution (Python):

import sys

def wantA(m):

    ind = len(Pl)
    ret = 0

    for i in Mi:

        while ind > 0 and Pl[ind-1] * i > m:
            ind -= 1

        ret += ind

    return ret

def wantB(m):

    ans = 0
    ret = 0

    ind = len(Pl)

    for i in Pl:

        while ind > 0 and Pl[ind-1] * i > m:
            ind -= 1

        ret += ind

        if i ** 2 <= m:
            ret -= 1

    ans += ret // 2

    ret = 0

    ind = len(Mi)

    for i in Mi:

        while ind > 0 and Mi[ind-1] * i > m:
            ind -= 1

        ret += ind

        if i ** 2 <= m:
            ret -= 1

    ans += ret // 2

    return ans
   


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

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

Mi = []
znum = 0
Pl = []

for i in A:

    if i < 0:
        Mi.append(-1 * i)
    elif i == 0:
        znum += 1
    else:
        Pl.append(i)

Mi.sort()
Pl.sort()

if len(Mi) * len(Pl) >= K:

    
    K = len(Mi) * len(Pl) - K + 1

    l = Mi[0] * Pl[0] - 1
    r = Mi[-1] * Pl[-1]

    while r - l != 1:

        m = (r + l) // 2

        num = wantA(m)

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

    print (-1 * r)
    sys.exit()


K -= len(Mi) * len(Pl)

K -= znum * (len(Pl) + len(Mi) ) + znum * (znum-1) // 2

if K <= 0:
    print (0)
    sys.exit()





l = 0
r = 10 ** 18 + 1

while r - l != 1:

    m = (r + l) // 2

    num = wantB(m)

    

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

print (r)

Solution (Python):


import numpy

n,k=map(int,input().split())
arr=list(map(int,input().split()))
nc=0
zc=0
pc=0
for i in range(n):
  if arr[i]<0:
    nc+=1
  elif arr[i]==0:
    zc+=1
  else:
    pc+=1
ncc=nc*pc
zcc=zc*(nc+pc)+(zc*(zc-1))//2
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
if ncc<k<=(ncc+zcc):
  print(0)
else:
  arr=numpy.array(arr,dtype=int)
  ms=numpy.msort(numpy.abs(arr[arr<0]))
  ps=numpy.msort(arr[arr>0])
  if k<=ncc:
    k=ncc-k
    l=0
    r=10**18+1
    while r-l!=1:
      mid=(l+r)//2
      cnt=numpy.searchsorted(ps,mid//ms,side='right')
      if cnt.sum()>k:
        r=mid
      else:
        l=mid
    print(-r)
  elif k<=(ncc+zcc):
    print(0)
  else:
    l=0
    r=10**18+1
    k-=(ncc+zcc)
    while r-l!=1:
      mid=(l+r)//2
      cnt1=numpy.searchsorted(ps,mid//ps,side='right')
      dup1=ps**2<=mid
      cnt2=numpy.searchsorted(ms,mid//ms,side='right')
      dup2=ms**2<=mid
      if (cnt1.sum()-dup1.sum()+cnt2.sum()-dup2.sum())//2>=k:
        r=mid
      else:
        l=mid
    print(r)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus, zero, minus = [], [], []
for x in a:
	if x > 0:
		plus.append(x)
	elif x == 0:
		zero.append(x)
	else:
		minus.append(x)
m, z, p = len(minus), len(zero), len(plus)
mm, zz, pp = m * p, z * (m + p) + (z * (z - 1)) // 2, (m * (m-1)) // 2 + (p * (p-1)) // 2
plus.sort()
plus2 = plus[::-1]
minus.sort()
minus2 = minus[::-1]


if mm + zz >= k and mm < k:
	print(0)
elif mm >= k:
	ok, ng = -10**19, 0
	while ng-ok > 1:
		x = (ng+ok)//2
		res = 0
		l = 0
		for c in plus:
			if l == m:
				res += m
			elif minus[l] * c >= x:
				res += l
			else:
				while minus[l] * c < x:
					l += 1
					if l == m:
						break
				res += l
		if res < k:
			ok = x
		else:
			ng = x
	print(ng-1)
else:
	ok, ng = 0, 10**19
	while ng-ok > 1:
		x = (ng+ok)//2
		lm, lp = 0, 0
		res = 0
		for c in minus:
			if c*c < x:
				res -= 1
			if lm == m:
				res += m
			elif minus2[lm] * c >= x:
				res += lm
			else:
				while minus2[lm] * c < x:
					lm += 1
					if lm == m:
						break
				res += lm
		for c in plus2:
			if c*c < x:
				res -= 1
			if lp == p:
				res += p
			elif plus[lp] * c >= x:
				res += lp
			else:
				while plus[lp] * c < x:
					lp += 1
					if lp == p:
						break
				res += lp
		res //= 2
		res += zz + mm
		
		if res < k:
			ok = x
		else:
			ng = x
	print(ng-1)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): 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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**18+1
    n,k=MI()
    aa=LI()
    pp=[]
    mm=[]
    zero=0
    for a in aa:
        if a>0:pp.append(a)
        elif a<0:mm.append(a)
        else:zero+=1
    pp.sort()
    mm.sort()
    cm=len(mm)*len(pp)
    cz=zero*(zero-1)//2+zero*(n-zero)

    def ok1(c):
        i=0
        cnt=0
        for m in mm:
            while i<len(pp) and m*pp[i]>=c:i+=1
            if i==len(pp):break
            cnt+=len(pp)-i
        return cnt<k

    def ok2(c):
        cnt=0
        j=len(mm)-1
        for i,m in enumerate(mm):
            while j>i and m*mm[j]>=c:j-=1
            if i>=j:break
            cnt+=j-i
        j=len(pp)-1
        for i,p in enumerate(pp):
            while j>i and p*pp[j]>=c:j-=1
            if i>=j:break
            cnt+=j-i
        return cnt<k

    
    if k<=cm:
        l=-inf
        r=inf
        while l+1<r:
            c=(l+r)//2
            if ok1(c):l=c
            else:r=c
    
    elif k<=cm+cz:
        print(0)
        exit()
    
    else:
        mm.reverse()
        k-=cm+cz
        l=-inf
        r=inf
        while l+1<r:
            c=(l+r)//2
            if ok2(c):l=c
            else:r=c
    print(l)

main()

Solution (Python):
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
n,k=map(int,input().split())
a=np.sort(np.array(list((map(int,input().split())))))
q=len(a[a==0])
d=a[a<0]
e=a[a>0]
l,r=10**18,-10**18
while l-r>1:
    t=(l+r)//2
    p=0
    if t>=0:
        p+=q*n
    p+=np.searchsorted(a,t//e,side="right").sum()+(n-np.searchsorted(a,(-t-1)//(-d),side="right")).sum()
    p-=np.count_nonzero(a*a<=t)
    p//=2
    if p>=k:
        l=t
    else:
        r=t
print(l)

Solution (Python):
import sys
import numpy as np


TEST_INPUT = [
    """
    4 3
    3 3 -4 -2
    """,
    """
    10 40
    5 4 3 2 -1 0 0 0 0 0
    """,
    """
    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
    """
]
ANSWER = [
    "-6",
    "6",
    "448283280358331064"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


def query(a, n, a_arr_p, a_arr_n, n_zeros, k):

    

    if a >= 0:
        
        res = len(a_arr_p) * len(a_arr_n)
        
        res += n_zeros * (n - n_zeros) + n_zeros * (n_zeros - 1) // 2
        
        res_pp = np.searchsorted(a_arr_p, a // a_arr_p, side="right").sum()
        res_pp -= (a_arr_p * a_arr_p <= a).sum()
        res += res_pp // 2
        
        res_nn = np.searchsorted(a_arr_n, a // a_arr_n, side="right").sum()
        res_nn -= (a_arr_n * a_arr_n <= a).sum()
        res += res_nn // 2
    else:
        
        res = len(a_arr_p) * len(a_arr_n) - np.searchsorted(a_arr_n, (a_arr_p - a - 1) // a_arr_p, side="left").sum()
    
    if res < k:
        return True
    else:
        return False


def solve(n, k, a_list):

    left = - 10 ** 18 - 1
    right = 10 ** 18 + 1
    center = 0

    a_arr = np.array(a_list)

    a_arr_p = a_arr[a_arr > 0]
    a_arr_n = - a_arr[a_arr < 0]
    n_zeros = (a_arr == 0).sum()
    a_arr_p.sort()
    a_arr_n.sort()

    while right > left + 1:
        if query(center, n, a_arr_p, a_arr_n, n_zeros, k):
            left, center = center, (center + right) // 2
        else:
            center, right = (left + center) // 2, center

    return right


def input_and_solve(ih):
    n, k = map(int, ih.input().split())
    a_list = list(map(int, ih.input().split()))
    res = solve(n, k, a_list)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        
        assert str(res) == str(ans)


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

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

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

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

p.sort()
m.sort()

ng, ok = -(10 ** 18)-1, 10 ** 18+1
while ok - ng > 1 :
  mid = (ok + ng) // 2
  s = 0 
  if mid < 0 :
    j = 0
    for i in range(len(m) - 1, -1, -1) :
      while j < len(p) and m[i] * p[j] < -mid :
        j += 1
      s += len(p) - j
      
  else :
    j = len(p) - 1
    for i in range(len(p)) :
      while j >= 0 and p[i] * p[j] > mid :
        j -= 1
      s += max(0, j - i)
      
    j = len(m) - 1
    for i in range(len(m)) :
      while j >= 0 and m[i] * m[j] > mid :
        j -= 1
      s += max(0, j - i)
      
    s += (len(p) + len(m)) * zero + len(p) * len(m) + zero * (zero - 1) // 2

  if s < K :
    ng = mid
  else :
    ok = mid
    
print(ok)

Solution (Python):
def solve():
    from bisect import bisect_left, bisect_right

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

    As.sort()
    negAs = [-A for A in As[::-1]]
    A2s = [A*A for A in As]
    A2s.sort()

    pstvBs = []
    numB0= 0
    ngtvBs = []
    for A in As:
        if A > 0:
            pstvBs.append(A)
        elif A == 0:
            numB0 += 1
        else:
            ngtvBs.append(A)

    def isOK(x):
        if x >= 0:
            dire = 1
        else:
            dire = -1
        num = 0
        
        iA = 0
        for B in pstvBs[::-dire]:
            key = x//B
            while iA < N and As[iA] <= key:
                iA += 1
            num += iA
        
        if x >= 0:
            num += N*numB0
        
        iA = 0
        for B in ngtvBs[::dire]:
            key = x//(-B)
            while iA < N and negAs[iA] <= key:
                iA += 1
            num += iA
        i = bisect_right(A2s, x)
        num -= i
        num //= 2
        return num >= K

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

    print(ok)


solve()

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

A0 = []
A1 = []

F = [0,0,0]
for i in range(n):
    if A[i] > 0:
        F[0] += 1
        A0.append(A[i])
    elif A[i] == 0:
        F[1] += 1
    else:
        F[2] += 1
        A1.append(A[i])
G = [F[2]*(F[2]-1)//2 + F[0]*(F[0]-1)//2,
 (F[0]+F[2]) * F[1] + F[1]*(F[1]-1)//2,
  F[2] * F[0]]

g = 2
if G[2] < k and G[2]+G[1] >= k:
    k -= G[2]
    g = 1
if G[2]+G[1] < k:
    k -= G[2]+G[1]
    g = 0
if g==2:
    k = n*(n-1)//2 + 1 - k  
    k -= G[0]+G[1]  
    
k -= 1 




if g==1:
    print(0)
elif g==0:
    A = A0[:]
    B = [-i for i in A1]
    B.sort()
    le = -1
    ri = 10**18+2
    m = (le+ri) // 2
    while ri-le > 1:
        ans = 0
        if len(A) > 0:
            j0 = len(A)-1
            for i in range(len(A)):
                while j0 > i and A[i]*A[j0] >= m:
                    j0 -= 1
                ans += j0-i
                j0 = max(i+1,j0)
        if len(B) > 0:
            j1 = len(B)-1
            for i in range(len(B)):
                while j1 > i and B[i]*B[j1] >= m:
                    j1 -= 1
                ans += j1-i
                j1 = max(i+1,j1)
        
        if ans > k:
            ri = m
        else:
            le = m
        m = (le+ri)//2
    print(le)
else:
    
    A = A0[:]
    B = [-i for i in A1]
    B.sort()
    

    le = -1
    ri = 10**18+2
    m = (le+ri) // 2
    while ri-le > 1:
        ans = 0
        if len(A) > 0:
            j0 = len(B)-1
            for i in range(len(A)):
                
                while j0 >= 0 and A[i]*B[j0] >= m:
                    
                    j0 -= 1
                ans += j0+1
                
        
        if ans > k:
            ri = m
        else:
            le = m
        m = (le+ri)//2
    print(-le)

Solution (Python):



import sys
readline = sys.stdin.readline
read = sys.stdin.read





def solve():
    from bisect import bisect_right, bisect_left
    
    n,k,*a = map(int,read().split())
    a.sort()
    
    
    
    
    
    
    l = bisect_left(a,0)
    r = bisect_right(a,0,lo = l)
    
    a_neg = [-i for i in a[:l][::-1]]
    a_pos = a[r:]
    
    if k <= l*(n-r): 
        def check(x): 
            res = (n-r)*l
            L = n-r
            v = 0
            for i in a_neg[::-1]:
                V = (x+i-1)//i
                while v < L and a_pos[v] < V:
                    v += 1
                res -= v
            return res >= k
    
        ok = 0
        ng = 10**18
        while ng-ok > 1:
            mid = (ok+ng)//2
            if check(mid): ok = mid
            else: ng = mid
    
        print(-ok)
    
    elif k <= n*(n-1)//2 - l*(l-1)//2 - (n-r)*(n-r-1)//2:
        print(0)
    
    else:
        k -= n*(n-1)//2 - l*(l-1)//2 - (n-r)*(n-r-1)//2
    
        def check(x): 
            res = 0
            vn = l-1
            for i,ai in enumerate(a_neg):
                X = x//ai
                while vn and a_neg[vn] > X:
                    vn -= 1            
                
                if vn+1 > i+1: res += vn+1-i-1

            vp = n-r-1
            for i,ai in enumerate(a_pos):
                X = x//ai
                while vp and a_pos[vp] > X:
                    vp -= 1            
                
                if vp+1 > i+1: res += vp+1-i-1
            return res >= k
        
        ng = 0
        ok = 10**18
        while ok-ng > 1:
            mid = (ok+ng)//2
            if check(mid): ok = mid
            else: ng = mid
    
        print(ok)


solve()

Solution (Python):
import numpy as np

N, K = map(int, input().split())
A = np.sort(np.array(input().split(),np.int64))
z = A[A == 0]
p = A[A > 0]
n = A[A < 0]

def count_func(x):
    cnt = 0
    if x >= 0:
        cnt += len(z) * N
    cnt += np.searchsorted(A, x // p, side='right').sum()
    cnt += (N - np.searchsorted(A, (-x - 1) // (-n), side='right')).sum()
    cnt -= np.count_nonzero(A * A <= x)
    assert cnt % 2 == 0
    return cnt // 2

l = -10 ** 18
r = 10 ** 18
while l + 1 < r:
    x = (l + r) // 2
    if count_func(x) >= K:
        r = x
    else:
        l = x

print(r)

Solution (Python):
from bisect import bisect_right, bisect_left

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

t0 = bisect_left(A,0)
t1 = bisect_right(A,0)
pos = A[t1:]
neg = [-v for v in reversed(A[:t0])]
zeros = t1-t0
offset_negative = len(pos)*len(neg)
offset_zero = zeros*(N-zeros) + zeros*(zeros-1)//2
offset = offset_zero + offset_negative

def bisect2(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

def count1(l,n):
    j = len(l)
    cnt = 0
    for i,a in enumerate(l):
        v = n//a
        while j > i and l[j-1] > v:
            j -= 1
        if j <= i:
            break
        else:
            cnt += j-i-1
    return cnt

def count2(l1,l2,n):
    j = len(l2)
    cnt = 0
    for i,a in enumerate(l1):
        v = n//a
        while j > 0 and l2[j-1] > v:
            j -= 1
        cnt += j
    return cnt


def cnt(n):
    if n > 0:
        cnt = count1(pos,n-1) + count1(neg,n-1) + offset
    else:
        cnt = offset_negative - count2(pos,neg,-n)
    return cnt


if offset_negative < K <= offset:
    print(0)
else:
    temp = max(abs(a) for a in A)**2
    print(bisect2(temp, -temp, lambda n: cnt(n) <= K-1))