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

from bisect import bisect

DEBUG = False


def bisect_f(f, lo, hi):
    if DEBUG:
        assert f(lo) and not f(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if f(mid):
            lo = mid
        else:
            hi = mid
        if DEBUG:
            assert f(lo) and not f(hi)
    if DEBUG:
        assert hi - lo == 1
        assert f(lo) and not f(hi)
    return lo


N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
neg = []
zero = []
pos = []
for x in A:
    if x < 0:
        neg.append(x)
    elif x == 0:
        zero.append(x)
    else:
        assert x > 0
        pos.append(x)

revAbsNeg = [-x for x in reversed(neg)]  
posSq = [x ** 2 for x in pos]
negSq = [x ** 2 for x in revAbsNeg]

pos = np.array(pos, dtype=np.int64)
revAbsNeg = np.array(revAbsNeg, dtype=np.int64)


def countDistinctPairsLessThan(arr, prod):
    
    

    N = arr.shape[0]
    assert arr.shape == (N,)
    count3 = np.sum(
        np.minimum(np.arange(N), np.searchsorted(arr, (prod - 1) // arr, side="right"))
    )

    if DEBUG:
        count = 0
        for i, x in enumerate(arr):
            count += bisect(arr, (prod - 1) // x, 0, i)

        count2 = 0
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                if arr[i] * arr[j] < prod:
                    count2 += 1

        print(count, count2, count3)
        assert count == count2 == count3
    return count3


def countPairsLessThanOrEqual(arr1, arr2, prod):
    
    
    
    if len(arr1) > len(arr2):
        arr1, arr2 = arr2, arr1

    count3 = np.sum(np.searchsorted(arr2, prod // arr1, side="right"))

    if DEBUG:
        count = 0
        for x in arr1:
            count += bisect(arr2, prod // x)
        count2 = 0
        for x in arr1:
            for y in arr2:
                if x * y <= prod:
                    count2 += 1
        assert count == count2 == count3
    return count3


def getIndex(prod):
    
    count = 0
    if prod < 0:
        
        count += len(pos) * len(neg)
        count -= countPairsLessThanOrEqual(pos, revAbsNeg, -prod)
    elif prod >= 0:
        
        count += len(pos) * len(neg)
        if prod > 0:
            
            count += len(zero) * len(neg)
            count += (len(zero) * (len(zero) - 1)) // 2
            count += len(zero) * len(pos)
            
            count += countDistinctPairsLessThan(pos, prod)
            
            count += countDistinctPairsLessThan(revAbsNeg, prod)

    if DEBUG:
        count2 = 0
        for i in range(N):
            for j in range(i + 1, N):
                if A[i] * A[j] < prod:
                    count2 += 1
        assert count == count2
    return count


def solve(K):
    lo = -10 ** 18
    hi = 10 ** 18 + 1
    if DEBUG:
        assert getIndex(lo) <= K < getIndex(hi)
    prod = bisect_f(lambda prod: getIndex(prod) <= K, lo, hi)
    if DEBUG:
        assert getIndex(prod) <= K < getIndex(prod + 1)
    return prod


if DEBUG:
    for k in range((N * (N - 1)) // 2):
        print("k", k, solve(k))

print(solve(K - 1))

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

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

def main():
    N, K = map(int,input().split())
    A = np.sort(np.array(list(map(int, 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 // n), side='left')).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)
    
if __name__ == '__main__':
    main()

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

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=-A_neg[::-1]
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
p = []
z = []
m = []
for i in range(n):
    if a[i] > 0:
        p.append(a[i])
    elif a[i] == 0:
        z.append(a[i])
    else:
        m.append(a[i])
nb1 = -10**18-1
nb2 = 10**18+1
p1 = len(p)
z1 = len(z)
m1 = len(m)


def sytr(x,p,z,m,p1,z1,m1):
    ans = 0
    ans2 = 0
    ans3 = -10**18
    if x > 0:
        m.sort(reverse=True)
        p.sort()
        ans += p1*m1 + (p1+m1)*z1 + (z1-1)*z1//2
        ans2 += ans
        now = 0
        
        now1 = p1-1
        now2 = 0
        now3 = p1-1
        if p1 > 1:
            while now < now1:
                if p[now]*p[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,p[now]*p[now1])
                    ans += now1-now
                    now += 1
            while now2 < now3:
                if p[now2]*p[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3 - now2
                    now2 += 1
        if m1 > 1:
            now = 0
            now1 = m1-1
            now2 = 0
            now3 = m1-1
            while now < now1:
                if m[now]*m[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,m[now]*m[now1])
                    ans += now1 - now
                    now += 1
            while now2 < now3:
                if m[now2]*m[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3 - now2
                    now2 += 1
    elif x == 0:
        p.sort()
        m.sort()
        if p1 > 0 and m1 > 0:
            ans3 = p[0]*m[m1-1]
        if z1 > 0:
            ans3 = 0
        ans += p1*m1+1
        ans2 += (p1+m1)*z1 + ans - 1
        if z1 > 1:
            ans2 += z1*(z1-1)//2
    else:
        p.sort(reverse=True)
        m.sort()
        now = 0
        now1 = m1-1
        now2 = 0
        now3 = m1-1
        if p1 > 0 and m1 > 0:
            while now < p1 and now1 >= 0:
                if p[now]*m[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,p[now]*m[now1])
                    ans += now1+1
                    now += 1
            while now2 < p1 and now3 >= 0:
                if p[now2]*m[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3+1
                    now2 += 1
    return [ans,ans2,ans3]
while nb1 + 1 < nb2:
    
    x = (nb1+nb2)//2
    
    if max(sytr(x,p,z,m,p1,z1,m1)[0],sytr(x,p,z,m,p1,z1,m1)[1]) < k:
        nb1 = x
    elif min(sytr(x,p,z,m,p1,z1,m1)[0],sytr(x,p,z,m,p1,z1,m1)[1]) > k:
        nb2 = x
    else:
        if abs(sytr(x,p,z,m,p1,z1,m1)[1]-sytr(x,p,z,m,p1,z1,m1)[0]) == 0:
            x = sytr(x,p,z,m,p1,z1,m1)[2]
            break
        else:
            break
print(x)

Solution (Python):
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline

import numpy as np

n, k = map(int, input().split())
A = np.array(input().split(), np.int64)
A = np.sort(A)

P = A[A>0]
Z = A[A==0]
N = A[A<0]



def ok(x):
    
    cnt = 0
    
    cnt += np.searchsorted(A, x//P, side='right').sum()
    
    cnt += (n-np.searchsorted(A, (-x-1)//(-N), side='right')).sum()
    if x >= 0:
        cnt += len(Z)*n
    cnt -= np.count_nonzero(A*A <= x)
    cnt = cnt//2
    if cnt >= k:
        return True
    else:
        return False

l = -10**18-1
r = 10**18+1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(r)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = map(int, input().split())

    neg, pos, zero = list(), list(), 0
    for a in A:
        if a < 0: neg.append(a)
        elif a > 0: pos.append(a)
        else: zero += 1
    neg.sort()
    pos.sort()

    
    def calc(x):
        result = 0
        if x < 0:
            
            i, j = len(pos)-1, len(neg)-1
            while i >= 0:
                while j >= 0 and pos[i]*neg[j] >= x: j -= 1
                if j < 0: break
                result += j + 1
                i -= 1
        elif x == 0:
            result += len(neg) * len(pos) 
        else:
            
            i, j = 0, len(pos)-1
            while i < len(pos):
                while j >= 0 and pos[i]*pos[j] >= x: j -= 1
                if j < 0: break
                result += j + 1
                if pos[i]*pos[i] < x: result -= 1 
                i += 1
            
            i, j = len(neg)-1, 0
            while i >= 0:
                while j < len(neg) and neg[i]*neg[j] >= x: j += 1
                if j >= len(neg): break
                result += len(neg) - j
                if neg[i]*neg[i] < x: result -= 1 
                i -= 1
            result //= 2 
            result += len(neg) * len(pos) 
            result += (len(neg) + len(pos)) * zero + (zero)*(zero-1)//2 
        return result
    
    
    l, over = -10**18, 10**18+1
    while over - l > 1:
        m = (l+over)//2
        if calc(m) < K: l = m
        else: over = m
    print(l)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = map(int, input().split())

    neg, pos, zero = list(), list(), 0
    for a in A:
        if a < 0: neg.append(a)
        elif a > 0: pos.append(a)
        else: zero += 1
    neg.sort()
    pos.sort()

    
    def calc(x):
        result = 0
        if x < 0:
            
            i, j = len(pos)-1, len(neg)-1
            while i >= 0:
                while j >= 0 and pos[i]*neg[j] >= x: j -= 1
                if j < 0: break
                result += j + 1
                i -= 1
        elif x == 0:
            result += len(neg) * len(pos) 
        else:
            
            i, j = 0, len(pos)-1
            while i < len(pos):
                while j >= 0 and pos[i]*pos[j] >= x: j -= 1
                if j < 0: break
                result += j + 1
                if pos[i]*pos[i] < x: result -= 1 
                i += 1
            
            i, j = len(neg)-1, 0
            while i >= 0:
                while j < len(neg) and neg[i]*neg[j] >= x: j += 1
                if j >= len(neg): break
                result += len(neg) - j
                if neg[i]*neg[i] < x: result -= 1 
                i -= 1
            result //= 2 
            result += len(neg) * len(pos) 
            result += (len(neg) + len(pos)) * zero + (zero)*(zero-1)//2 
        return result
    
    
    l, over = -10**18, 10**20+1
    while over - l > 1:
        m = (l+over)//2
        if calc(m) < K: l = m
        else: over = m
    print(l)

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
def main():
    readline=stdin.readline
    N,K=map(int,readline().split())
    A=list(map(int,readline().split()))
    A.sort()

    
    index=[len(A),len(A)]
    mode=0
    for i in range(N):
        if mode==0:
            if A[i]==0:
                index[0]=i
                mode=1
            elif A[i]>0:
                index[0],index[1]=i,i
                break
        else:
            if A[i]>0:
                index[1]=i
                break

    
    l=-10**18
    r=10**18+1
    while(l<r-1):
        x=(l+r)//2
        count=0

        
        if x>0:
            now_j=index[0]
            for i in range(index[0]):  
                for j in range(now_j,-1,-1):
                    if A[i]*A[j-1]>=x:
                        now_j=j
                        count+=len(A)-now_j
                        if now_j<=i:
                            count-=1
                        break
                else:
                    now_j=0
                    count+=len(A)
                    count-=1

            for i in range(index[0],index[1]):  
                if x>0:
                    count+=len(A)-1
                else:
                    break
            
            now_j=index[0]
            for i in range(len(A)-1,index[1]-1,-1):
                for j in range(now_j,len(A)):
                    if A[i]*A[j]>=x:
                        now_j=j
                        count+=now_j
                        if now_j>=i+1:
                            count-=1
                        break
                else:
                    now_j=len(A)
                    count+=len(A)
                    count-=1

        else:
            now_j=len(A)
            for i in range(index[0]-1,-1,-1):  
                for j in range(now_j,-1,-1):
                    if A[i]*A[j-1]>=x:
                        now_j=j
                        count+=len(A)-now_j
                        if now_j<=i:
                            count-=1
                        break
            
            now_j=0
            for i in range(index[1],len(A)):
                for j in range(now_j,len(A)):
                    if A[i]*A[j]>=x:
                        now_j=j
                        count+=now_j
                        if now_j>=i+1:
                            count-=1
                        break

        count//=2
        if count<K:
            l=x
        else:
            r=x

    print(l)

if __name__=="__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mina = []
zera = []
plua = []
for x in a:
  if x > 0: plua.append(x)
  elif x == 0: zera.append(x)
  else: mina.append(x)

mlim = len(mina) * len(plua)
zlim = len(zera) * (len(mina) + len(plua)) + len(zera) * (len(zera) - 1) // 2 + mlim

def minacheck(x):
  res = 0
  j = 0
  for i in range(len(plua)):
    while j < len(mina) and (plua[i] * mina[j]) <= x: j += 1
    res += j
  return res >= K

def pluacheck(x):
  res = 0
  j = 0
  for i in range(len(mina) - 1, -1, -1):
    while j < len(mina) and (mina[i] * mina[j] <= x): j += 1
    res += max(0, j - i - 1)
  j = 0
  for i in range(len(plua) - 1, -1, -1):
    while j < len(plua) and (plua[i] * plua[j] <= x): j += 1
    res += max(0, j - i - 1)
  return res >= K - zlim

if K <= mlim:
  ng = -pow(10, 18)
  ok = 0
  while ok - ng > 1:
    m = (ok + ng) // 2
    if minacheck(m): ok = m
    else: ng = m
  print(ok)
elif K <= zlim: print(0)
else:
  for i in range(len(mina)): mina[i] = -mina[i]
  mina.reverse()
  ng = 0
  ok = pow(10, 18)
  while ok - ng > 1:
    m = (ok + ng) // 2
    if pluacheck(m): ok = m
    else: ng = m
  print(ok)

Solution (Python):
from bisect import bisect_left, bisect_right

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

neg_end = bisect_left(A, 0)
pos_start = bisect_right(A, 0)
n_pos = N - pos_start
n_neg = neg_end
n_zero = N - (n_pos + n_neg)

n_prod_neg = n_pos * n_neg
n_prod_zero = n_zero * (n_pos + n_neg) + (n_zero * (n_zero - 1) // 2)

if K <= n_prod_neg: 
    
    def cond(x):
        
        counter = 0; r = pos_start
        for l in range(neg_end): 
            while r < N and A[l] * A[r] > x: r += 1
            counter += n_pos - (r - pos_start) 
        return counter >= K
    MAX = 0
    MIN = -10**18
    left, right = MIN, MAX 
    while right - left > 1:
        mid = (left + right) // 2
        if cond(mid): right = mid
        else: left = mid
    print(right)
elif K <= n_prod_neg + n_prod_zero: 
    print(0)
else: 
    K -= n_prod_neg + n_prod_zero
    
    def cond(x):
        
        counter = 0
        r = N - 1
        for l in range(pos_start, N): 
            while l < r and A[l] * A[r] > x: r -= 1
            counter += max(0, r - l) 
            if l >= r: break
        l = 0
        for r in range(neg_end - 1, -1, -1): 
            while l < r and A[l] * A[r] > x: l += 1
            counter += max(0, r - l) 
            if l >= r: break
        return counter >= K
    MAX = 10**18
    MIN = 0
    left, right = MIN, MAX 
    while right - left > 1:
        mid = (left + right) // 2
        if cond(mid): right = mid
        else: left = mid
    print(right)

Solution (Python):
import numpy as np
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = np.array(a)
a.sort()
p = a[a>0]
z = a[a==0]
m = a[a<0]
low = -10**18
high = 10**18
while high-low>1:
    mid = (high + low) //2
    count = 0
    if mid >= 0:
        count += len(z)*n
    count += a.searchsorted(mid//p,side = "right").sum()
    count += (n-a.searchsorted(-(-mid//m),side = "left")).sum()
    count -= np.count_nonzero(a*a <= mid)
    count /= 2
    if count >= k:
        high = mid
    if count < k:
        low = mid
print(high)

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
import numpy as np
def resolve():
    N, K = lr()
    A = np.sort(np.array(lr(), 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 // n), side='left')).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)
resolve()

Solution (Python):
from bisect import bisect_left,bisect_right
n,k=map(int,input().split())
a=list(map(int,input().split()))
inf=10**20
a.sort()
mc=zc=pc=0
m=[]
p=[]
for i in a:
  if i<0:
    mc+=1
    m.append(i)
  elif i==0:
    zc+=1
  else:
    pc+=1
    p.append(i)
if mc*pc>=k:
  
  for i in range(len(m)):m[i]*=-1
  k=mc*pc-k+1
  m=m[::-1]
  p=[0]+p
  ng=0
  ok=10**19+7
  mi=10**19+7
  while ng+1!=ok:
    ma=0
    mid=(ng+ok)//2
    co=0
    j=len(p)-1
    for i in m:
      while p[j]*i>mid:j-=1
      co+=j
      ma=max(ma,p[j]*i)
    if co<k:ng=mid
    else:
      ok=mid
      mi=min(mi,ma)
  print(-mi)
elif mc*pc+zc*(zc-1)//2+zc*(pc+mc)>=k:
  
  print(0)
else:
  k-=mc*pc+zc*(zc-1)//2+zc*(pc+mc)
  for i in range(len(m)):m[i]*=-1
  m=m[::-1]
  m=[0]+m
  p=[0]+p
  ng=0
  ok=10**19+7
  mi=10**19+7
  while ng+1!=ok:
    ma=0
    mid=(ok+ng)//2
    co=0
    jjj=0
    j=len(p)-1
    pok=[]
    for i in range(len(p)):
      if p[i]==0:continue
      while p[j]*p[i]>mid:j-=1
      co+=max(0,j-i)
      ma=max(ma,p[j]*p[i])
    j=len(m)-1
    for i in range(len(m)):
      if m[i]==0:continue
      while m[j]*m[i]>mid:j-=1
      co+=max(0,j-i)
      ma=max(ma,m[j]*m[i])
    if co<k:ng=mid
    else:
      ok=mid
      mi=min(mi,ma)
  print(mi)

Solution (Python):

import numpy as np
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = np.array(a)
a.sort()

plus = a[a>0]
zero = a[a==0]
minus= a[a<0]

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

while left+1 < right:
    mid = (left+right)//2
    cnt = 0
    
    if mid >=0:
        cnt += len(zero) * n
    
    cnt += a.searchsorted(mid//plus, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//minus), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt /= 2
    
    if cnt >= k:
        right = mid
    if cnt < k:
        left=mid
        
print(right)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from bisect import bisect_right

N,K = LI()
A = LI()

P = []
Z = []
M = []
for a in A:
    if a < 0:
        M.append(a)
    elif a == 0:
        Z.append(a)
    else:
        P.append(a)

P.sort()
M.sort()

lm,lz,lp = len(M),len(Z),len(P)

nm = lm*lp
nz = lz*(lz-1)//2 + lz*(lm+lp)

if K <= nm:
    ok = 0
    ng = -10**18-1
    while abs(ok-ng) > 1:
        now = (ok+ng)//2
        num = 0
        p = -1
        for i in range(lp):
            tmp = p
            for j in range(p+1,lm):
                if P[i]*M[j] <= now:
                    tmp = j
                else:
                    break
            p = tmp
            num += p+1
        if num >= K:
            ok = now
        else:
            ng = now
    print(ok)
elif K <= nm+nz:
    print(0)
else:
    
    M = [-m for m in M]
    M.sort()
    ok = 10**18+1
    ng = 0
    while abs(ok-ng) > 1:
        now = (ok+ng)//2
        num = 0
        p = -1
        for i in range(lp)[::-1]:
            tmp = p
            for j in range(p+1,i):
                if P[i]*P[j] <= now:
                    tmp = j
                else:
                    break
            p = tmp
            num += min(p+1,i)
        p = -1
        for i in range(lm)[::-1]:
            tmp = p
            for j in range(p+1,i):
                if M[i]*M[j] <= now:
                    tmp = j
                else:
                    break
            p = tmp
            num += min(p+1,i)
        if num >= K-nm-nz:
            ok = now
        else:
            ng = now
    print(ok)

Solution (Python):
N,K = map(int,input().split())
A_s = list(map(int,input().split()))
minus = [-x for x in A_s if x < 0]
plus = [x for x in A_s if x >= 0]
minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        r = 0
        x = -x
        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


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

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

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

A = np.sort(A)
pos = A[A > 0]
neg = A[A < 0]
zero = len(A[A == 0])

def cnt(x):
    """return 
    ret = 0

    if x >= 0:
        ret += zero * N

    ret += np.searchsorted(A, x // pos, side='right').sum()
    ret += (N - np.searchsorted(A, (-x - 1) // (-neg), side='right')).sum()
    ret -= ((A * A) <= x).sum()
    return ret // 2

overEq = 10**18 + 100
less = -10**18 - 100

while less + 1 < overEq:
    mid = (overEq + less) // 2
    if cnt(mid) >= K:
        overEq = mid
    else:
        less = mid

print(overEq)

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

a.sort()

plus = a[a > 0]
minus = a[a < 0]
zero = a[a == 0]


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

while left + 1 < right:
    x = (left + right) // 2
    cnt = 0
    if x >= 0:
        cnt += n * len(zero)
    cnt += a.searchsorted(x // plus, side="right").sum()
    cnt += (n - a.searchsorted(-(-x // minus), side="left")).sum()
    cnt -= np.count_nonzero(a * a <= x)
    cnt //= 2

    if cnt >= k:
        right = x
    else:
        left = x

print(right)

Solution (Python):
import sys
import numpy as np
INF = 10**18+5
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a = np.sort(a)
    ap = a[a > 0]
    an = a[a < 0]
    zc = n * (n - ap.size - an.size)

    l = -INF
    r = INF
    while(l+1 < r):
        x = (l+r)//2

        total = (n-np.searchsorted(a, -(-x // an), side='left')).sum()
        if x >= 0:
            total += zc
        total += np.searchsorted(a, x // ap, side='right').sum()
        total -= a[a*a <= x].size
        total //= 2
        if total < k:
            l = x
        else:
            r = x

    print(r)


main()

Solution (Python):
import numpy as np
def f(nums, a):
  return 0  if nums.size<=1 else (np.searchsorted(nums, a//nums, side='right').sum()-np.searchsorted(nums, int(pow(a, 1/2)), side='right'))//2

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:] if p>0 else np.array([])
AN=A[:q] if q>0 else np.array([])

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  if q>1:
    AN=-AN[::-1]
  x=0
  y=10**18
  K=K-a-b
  while y-x>1:
    tmp=(y+x)//2
    if f(AP, tmp)+f(AN, tmp)<K:
      x=tmp
    else:
      y=tmp
  print(y)

Solution (Python):
import numpy as np
def f(nums, a):
  return 0  if nums.size<=1 else (np.searchsorted(nums, a//nums, side='right').sum()-np.searchsorted(nums, int(pow(a, 1/2)), side='right'))//2

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:] if p>0 else np.array([])
AN=A[:q] if q>0 else np.array([])

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  x=0
  y=10**18
  K=K-a-b
  if q<=1:
    while y-x>1:
      tmp=(y+x)//2
      if f(AP, tmp)<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  AN=AN[::-1]
  AN=-AN
  
  if p<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=f(AN, tmp)
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  while y-x>1:
    tmp=(y+x)//2
    if f(AP, tmp)+f(AN, tmp)<K:
      x=tmp
    else:
      y=tmp
  print(y)