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 math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


def f(x): 
    cnt = 0
    if x < 0: 
        j = p-1
        for i in range(m)[::-1]:
            while j >= 0:
                if minus[i]*plus[j] <= x:
                    j -= 1
                else:
                    break
            cnt += p - j - 1
    else: 
        
        j = p-1
        for i in range(p):
            while j >= 0:
                if plus[i]*plus[j] > x:
                    j -= 1
                else:
                    break
            cnt += max(0,j - i)
        
        j = 0
        for i in range(m)[::-1]:
            while j < m:
                if minus[i]*minus[j] > x:
                    j += 1
                else:
                    break
            cnt += max(0,i - j)
        
        cnt += (m+p)*zero + zero*(zero-1)//2 + m*p
    
    return cnt >= k
        
n,k = LI()
a = LI()
a.sort()
minus = [x for x in a if x < 0]
plus = [x for x in a if x > 0]
m = len(minus)
p = len(plus)
zero = bl(a,1) - br(a,-1)
ok = 10**18
ng = -10**18-1
while ok-ng > 1:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(x):
    cnt = 0
    if x < 0:
        j = p-1
        for i in range(m)[::-1]:
            while j >= 0:
                if minus[i]*plus[j] <= x:
                    j -= 1
                else:
                    break
            cnt += p - j - 1
    else:
        j = p-1
        for i in range(p):
            while j >= 0:
                if plus[i]*plus[j] > x:
                    j -= 1
                else:
                    break
            cnt += max(0,j - i)
        j = 0
        for i in range(m)[::-1]:
            while j < m:
                if minus[i]*minus[j] > x:
                    j += 1
                else:
                    break
            cnt += max(0,i - j)
        cnt += (m+p)*zero + zero*(zero-1)//2 + m*p
    return cnt >= k
        
n,k = LI()
a = LI()
a.sort()
minus = [x for x in a if x < 0]
plus = [x for x in a if x > 0]
m = len(minus)
p = len(plus)
zero = bl(a,1) - br(a,-1)
ok = 10**18
ng = -10**18-1
while ok-ng > 1:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
import numpy as np

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

a = np.sort(a)

u = a[a > 0]
d = a[a < 0]
z = len(a[a == 0])

if len(u) * len(d) < k <= len(u) * len(d) + z * (n-z) + z * (z-1) // 2:
    print(0)
    exit()

L = - 10 ** 18
H = 10 ** 18

while H - L > 1:
    M = (H + L) // 2
    count = 0
    if M > 0:
        count += z * n
    count += np.searchsorted(a, M // u, side='right').sum()
    count += (n - np.searchsorted(a, (- M - 1) // (- d), side='right')).sum()
    count -= np.count_nonzero(a * a <= M)
    count //= 2
    
    if count >= k:
        H = M
    else:
        L = M

print(H)

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
pos = N - bisect(A,0)
zero = A.count(0)
neg = N - pos - zero

def is_ok(m):
    if m < 0:
        k = 0
        l = 1
        for i in range(neg):
            a = A[i]
            while a*A[l] > m:
                l += 1
                if l==N: break
            k += N-l
            if k >= K: return True
            if l==N: break
        return False
    else:
        k = diag = 0
        r = neg-1
        for i in range(neg):
            a = A[i]
            while a*A[r] <= m:
                r -= 1
                if r==-1: break
            k += r+1
            if r>=i: diag += 1
            if r==-1: break
        nz = neg+zero
        l = nz
        for i in range(N-1,nz-1,-1):
            a = A[i]
            while a*A[l] <= m:
                l += 1
                if l==N: break
            k += N-l
            if l<=i: diag += 1
            if l==N: break
        tmp = N*(N-1)//2 - (k-diag)//2
        return tmp >= K

ng = -10**18-1
ok = 10**18+1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

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

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

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

def count(x): 
    ans = 0
    if x >= 0:
        ans += n * len(zero)
    
    ans += np.searchsorted(a_list,x // pos, side='right').sum()
    
    ans += (n - np.searchsorted(a_list, (-x - 1) // (-neg), side='right')).sum()
    
    ans -= np.count_nonzero(a_list * a_list <= x)
    return ans // 2

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

print(right)

Solution (Python):


def count1(T, A, B):
	if T <= 0 or len(A) == 0 or len(B) == 0:
		return 0

	count, it = 0, -1
	for i in range(len(A) - 1, -1, -1):
		while it + 1 < len(B) and A[i] * B[it + 1] < T:
			it += 1

		
		count += len(B) - it - 1
	return count





def count2(T, A):
	count_all = len(A) * (len(A) - 1) // 2
	count = count1(T + 1, A, A)

	
	for e in A:
		if e * e >= T + 1:
			count -= 1

	count /= 2 

	return count_all - count


if __name__ == "__main__":
	N, K = map(int, input().split())
	A = list(map(int, input().split()))

	
	
	
	X, Y, Z = [], [], 0
	for e in A:
		if e < 0:
			X.append(-e)
		elif e > 0:
			Y.append(e)
		else:
			Z += 1
	X.sort()
	Y.sort()


	
	def check(T):
		count = 0
		if T < 0:
			count += count1(abs(T), X, Y)
		else:
			count += len(X) * len(Y) 
			count += Z * (Z - 1) // 2 + Z * (N - Z) 
			count += count2(T, X) + count2(T, Y)

		return count < K


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

	print(ok + 1)

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

def count(A, B, x):
    N = len(A)
    M = len(B)
    res = 0
    r = -1
    for l in range(N):
        a = A[l]
        while r < M-1 and B[r+1]*a <= x:
            r += 1
        res += r+1
    return res

def count2(A, x):
    res = 0
    for a in A:
        if a*a <= x:
            res += 1
    return res
        

N, K = map(int, readline().split())
A = list(map(int, readline().split()))
Am = []
Ap = []

minus = 0
zero = 0
plus = 0
for a in A:
    if a < 0:
        minus += 1
        Am.append(-a)
    elif a == 0:
        zero += 1
    else:
        plus += 1
        Ap.append(a)

ms = minus*plus
zs = ms + zero*(minus+plus) + zero*(zero-1)//2

Am.sort()
Ap.sort()
Amr = Am[::-1]
Apr = Ap[::-1]

if K <= ms:
    K = ms+1-K
    ok = max(max(Am+[0]), max(Ap+[0]))**2
    ng = 0
    while abs(ok-ng)>1:
        med = (ok+ng)//2
        if count(Amr, Ap, med) >= K:
            ok = med
        else:
            ng = med
    ans = -ok
elif K <= zs:
    ans = 0
else:
    K -= zs
    ok = max(max(Am+[0]), max(Ap+[0]))**2
    ng = 0
    while abs(ok-ng)>1:
        med = (ok+ng)//2
        if (count(Amr, Am, med) + count(Apr, Ap, med) - count2(Am, med) - count2(Ap, med))//2 >= K:
            ok = med
        else:
            ng = med
    ans = ok

print(ans)

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

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

def f(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)
    
    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):
import numpy as np

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

A = np.array(input().split(), np.int64)

A.sort()

posA = A[A > 0]
negA = A[A < 0]
zeros = (A==0).sum()

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

while left+1 < right:
    num = (left+right)//2
    
    less_count = 0
    
    if num >= 0:
        less_count += zeros * n
    
    limit_pair_for_pos = num // posA
    limit_idxs = np.searchsorted(A, limit_pair_for_pos, side='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = -(num // -negA)
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A**2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2
    
    if less_count >= k:
        right = num
    else:
        left = num

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

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

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

def f(x):
    ans = 0
    if x >= 0:
        ans += n * len(zero)
    ans += np.searchsorted(A, x// pos, side="right").sum()
    ans += (n - np.searchsorted(A, (-x-1)//(-neg), side="right")).sum()
    ans -= np.count_nonzero(A*A<=x)
    return ans // 2

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

Solution (Python):

import numpy as np

def main():
    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:
        cur = (ok+ng)//2
        if count(cur)>=K:
            ok = cur
        else:
            ng = cur
    print(int(ok))


    
if __name__ == "__main__":
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    P = []
    Z = 0
    N = []
    for a in A:
        if a == 0:
            Z += 1
        elif a < 0:
            N.append(a)
        else:
            P.append(a)
    N.sort()
    P.sort()

    NN = len(N) * len(P)
    ZN = len(N) * Z + len(P) * Z + Z * (Z-1) // 2
    if M <= NN:
        N.reverse()
        def f(n):
            ans = 0
            i = bisect.bisect_left(P, -(n // -N[0]))
            for nn in N:
                m = -(n // -nn)
                while i != 0 and P[i-1] >= m:
                    i -= 1
                ans += len(P) - i
            return ans
        bs = Bisect(f)

        return bs.bisect_right(M-1, -INF, 0)

    elif M <= NN + ZN:
        return 0
    else:
        M -= NN + ZN
        N = [-v for v in N]
        N.sort()

        def f(n):
            ans = 0
            if N:
                i = bisect.bisect_right(N, n//N[0])
                for nn in N:
                    m = n // nn
                    while i != 0 and N[i-1] > m:
                        i -= 1
                    ans += i
                    if i > 0 and N[i-1] >= nn:
                        ans -= 1
            if P:
                i = bisect.bisect_right(P, n//P[0])
                for pn in P:
                    m = n // pn
                    while i != 0 and P[i-1] > m:
                        i -= 1
                    ans += i
                    if i > 0 and P[i-1] >= pn:
                        ans -= 1
            ans //= 2
            return ans
        bs = Bisect(f)
        return bs.bisect_right(M-1, 1, INF)

def f(N, M, A):
    ans = []
    for i in range(N):
        for j in range(i+1, N):
            ans.append((A[i]*A[j], A[i], A[j]))
    ans.sort()
    for i, r in enumerate(ans):
        print(i, r)

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import groupby

def sgn(num):
    if num<0:
        return -1
    elif num==0:
        return 0
    else:
        return 1


N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
a=0
b=0
c=0
B=[sgn(A[i]) for i in range(0,N)]
B=groupby(B)
for key,group in B:
    g=len(list(group))
    if key==-1:
        a=g
    elif key==0:
        b=g
    else:
        c=g
if a*c>=K:
    def condition(num):
        s=0
        t=a+b
        set=0
        while a+b+c-1>=t and a-1>=s:
            if A[s]*A[t]>num:
                t+=1
            else:
                set+=a+b+c-t
                s+=1
        if set>=K:
            return True
        else:
            return False
    start=-10**18
    end=-1
    while end-start>1:
        test=(start+end)//2
        if condition(test):
            end=test
        else:
            start=test
    if condition(start):
        print(start)
    else:
        print(end)
elif a*c+a*b+b*c+b*(b-1)//2>=K:
    print(0)
else:
    K-=a*c+a*b+b*c+b*(b-1)//2
    def condition(num):
        set=0
        s=a-1
        t=0
        while a-1>=t and s>=0:
            if A[s]*A[t]>num:
                t+=1
            else:
                set+=a-t
                if s>=t:
                    set-=1
                s-=1
        s=a+b
        t=a+b+c-1
        while t>=a+b and a+b+c-1>=s:
            if A[s]*A[t]>num:
                t-=1
            else:
                set+=t-a-b+1
                if t>=s:
                    set-=1
                s+=1
        if set>=2*K:
            return True
        else:
            return False
    start=1
    end=10**18
    while end-start>1:
        test=(end+start)//2
        if condition(test):
            end=test
        else:
            start=test
    if condition(start):
        print(start)
    else:
        print(end)

Solution (Python):
N, K = map(int, input().split())
plus = []
minus = []
zero = 0
for i in map(int, input().split()):
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1
plus.sort()
minus.sort(reverse=True)





ok, ng = -10 ** 19, 10 ** 19
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    cnt = 0
    if mid >= 0:
        cnt += len(plus) * len(minus)
        if mid > 0:
            cnt += zero * (zero - 1) // 2 + zero * (N - zero)
            for a in (plus, minus):
                l, r = 0, len(a) - 1
                while l < r:
                    while l < r and a[l] * a[r] >= mid:
                        r -= 1
                    cnt += r - l
                    l += 1
    else:
        r = len(minus) - 1
        for l in range(len(plus)):
            while r >= 0 and plus[l] * minus[r] < mid:
                r -= 1
            cnt += len(minus) - (r + 1)

    if cnt < K:
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):
import sys

n, k = map(int, sys.stdin.readline().strip().split())
a = map(int, sys.stdin.readline().strip().split())

def main(n, k, a):
    nega = []
    posi = []
    zeros = 0

    for ai in a:
        if ai < 0:
            nega.append(ai)
        elif ai > 0:
            posi.append(ai)
        else:
            zeros += 1

    posi.sort()
    nega.sort(reverse=True)

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

    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0

        if mid >= 0:
            cnt += zeros * (zeros - 1) // 2 + zeros * (n - zeros)

        if mid > 0:
            cnt += len(nega) * len(posi)
            for a in (posi, nega):
                l = 0
                r = len(a)-1
                while l < r:
                    while l < r and a[l] * a[r] > mid:
                        r -= 1
                    cnt += r - l
                    l += 1
        else:
            r = len(nega) - 1
            for l in range(len(posi)):
                while r >= 0 and posi[l] * nega[r] <= mid:
                    r -= 1
                cnt += len(nega) - r - 1

        if cnt >= k:
            ok = mid
        else:
            ng = mid
    print(ok)


main(n, k, a)

Solution (Python):

import numpy as np


def main():
    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)

if __name__ == '__main__':
    main()

Solution (Python):


from bisect import bisect_right

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    zero_count = 0
    plus = []
    minus = []

    for i in range(N):
        if A[i] == 0:
            zero_count += 1
        elif A[i] >0 :
            plus.append(A[i])
        else:
            minus.append(A[i])

    zero_count = zero_count*(zero_count-1)//2+len(plus)*zero_count+len(minus)*zero_count
    minus_count = len(minus)*len(plus)

    if minus_count<K<=minus_count+zero_count:
        print(0)
        return
    elif K <= minus_count:
        left = -10**18-1
        right = 0

        while right - left > 1:
            mid = (right + left) //2
            
            count = 0
            j = 0
            
            for i in range(len(plus)):
                while j < len(minus) and plus[i]*minus[j]<=mid:
                    j+=1 
                count += j
            
            if count >= K:
                right = mid
            else:
                left = mid
        print(right)

    else:
        K -= (minus_count+zero_count)
        left = -1
        right = 10**18+1

        for i in range(len(minus)):
            minus[i] = -minus[i]
        minus = minus[::-1]        

        while right - left > 1:
            mid = (right + left) //2
            
            count = 0
            j = 0
            
            for i in range(len(plus)-1,-1,-1):
                if plus[i]**2 <= mid:
                    count -= 1

                while j < len(plus) and plus[i]*plus[j] <= mid:
                    j += 1
                count += j
            
            
            j = 0
            for i in range(len(minus)-1,-1,-1):
                if minus[i]**2 <= mid:
                    count -= 1
                while j < len(minus) and minus[i]*minus[j] <= mid:
                    j += 1
                count += j
            
            if count//2 >= K:
                right = mid
            else:
                left = mid
        print(right)


if __name__ == '__main__':
    main()

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 bisect

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

A.sort()
Nn = bisect.bisect_left(A, 0) 
Nz = bisect.bisect_left(A, 1) - Nn 
Np = N - Nn - Nz 
An = A[:Nn]
Ap = A[Nn+Nz:]


if Nn*Np >= K: 
  left = -10**18-1 
  right = -1 
  n = Nn*Np - K 
  while left+1 < right:
    mid = (left+right) // 2
    i = j = 0
    c = 0
    while i < Nn and j < Np:
      if An[i]*Ap[j] > mid:
        c += 1
        j += 1
        if j >= Np:
          c += (Nn - 1 - i)*Np
      else:
        c += j
        i += 1
      if c > n:
        break
    if c > n:
      left = mid
    else:
      right = mid
  ans = right 
elif Nn*Np + Nz*(Nn+Np) + Nz*(Nz-1)//2 >= K: 
  ans = 0
else: 
  An = [-an for an in An][::-1]
  N = Nn*(Nn-1)//2 + Np*(Np-1)//2 
  k = K - Nn*Np - Nz*(Nn+Np) - Nz*(Nz-1)//2 
  n = N - k
  left = 0 
  right = 10**18 + 1 
  while left+1 < right:
    mid = (left+right) // 2
    i = 0
    j = Nn - 1
    c = 0
    while i < j:
      if An[i]*An[j] > mid:
        c += 1
        j -= 1
      else:
        c += Nn - 1 - j
        i += 1
      if i == j:
          c += (Nn-i-1)*(Nn-i-2) // 2
      if c > n:
        break
    
    if c > n:
      left = mid
    else:
      i = 0
      j = Np - 1
      while i < j:
        if Ap[i]*Ap[j] > mid:
          c += 1
          j -= 1
        else:
          c += Np - 1 - j
          i += 1
        if i == j:
            c += (Np-i-1)*(Np-i-2) // 2
        if c > n:
          break
      if c > n:
        left = mid
      else:
        right = mid
  ans = right


print(ans)

Solution (Python):
import numpy as np



import sys
input = sys.stdin.readline



def cnt(x,A,An,Ap,N,Nz):
    res = 0
    if x >= 0:
        res += N * Nz
    res += np.searchsorted(A,x//Ap,side='right').sum()
    res += N * len(An) - np.searchsorted(A,-(-x//An),side='left').sum()
    res -= np.count_nonzero(A*A<=x)
    return res//2


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

    A = np.array(A)
    A.sort()

    An = A[A<0]
    Az = A[A==0]
    Ap = A[A>0]

    Nz = np.count_nonzero(A==0)

    INF = 10 ** 18

    l = - INF - 1
    r = INF

    while r-l > 1:
        m = (l+r)//2
        if cnt(m,A,An,Ap,N,Nz) >= K:
            r = m
        else:
            l = m

    print(r)





main()