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 numba import njit


@njit
def main(I):
    N,K=I[0],I[1]
    A = I[2:]
    A.sort()
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

I=np.array([int(_) for _ in open(0).read().split()],dtype=int)
print(main(I))

Solution (Python):
import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()


@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))

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
n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l = sys.maxsize * (-1)
r = sys.maxsize

while l+1 < r:
  x = (l+r)//2
  def isOk():
    tot = 0
    for i in range(n):
      if a[i] < 0:
        l = -1
        r = n
        while (l+1<r):
          c = (l+r)//2;
          if (a[c] * a[i] < x):
            r = c
          else:
            l = c
        tot += n-r
      else:
        l = -1
        r = n
        while (l+1<r):
          c = (l+r)//2
          if (a[c] * a[i] < x):
            l = c
          else:
            r = c
        tot += r
      if (a[i]*a[i] < x):
        tot -= 1
    tot /= 2
    return tot < k
  if (isOk()):
    l = x
  else:
    r = x;
print(l)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def find_x_miman(pos, i, neg, x):
    if len(neg) == 0:
        return 0
    if neg[0] * pos[i] >= x:
        return 0
    ok = 0
    ng = len(neg)
    while ok + 1 < ng:
        m = (ng + ok) // 2
        if neg[m] * pos[i] < x:
            ok = m
        else:
            ng = m
    return ok + 1

def find_x_miman_from_right(arr, i, x):
    if not (i + 1  < len(arr)):
        return 0
    if arr[i] * arr[i+1] >= x:
        return 0

    ok = i + 1
    ng = len(arr)
    while ok + 1 < ng:
        m = (ng + ok) // 2
        if arr[m] * arr[i] < x:
            ok = m
        else:
            ng = m
    return ok - i

def main():
    N, K = LI()
    A = LI()
    A = sorted(A)
    pos = [a for a in A if a > 0]
    neg = [a for a in A if a < 0]
    rev_neg = [abs(a) for a in neg][::-1]
    n_zero = N - len(neg) - len(pos)
    l = -10**18 - 1 
    r = 10**18 + 1

    def count_miman(x):
        
        cnt = 0
        if x < 0:
            for i in range(len(pos)):
                cnt += find_x_miman(pos, i, neg, x)
        else: 
            if x > 0:
                cnt += n_zero * (len(neg) + len(pos)) + (n_zero * (n_zero - 1)) // 2
            for i in range(len(pos)):
                cnt += find_x_miman_from_right(pos, i, x)
            for i in range(len(rev_neg)):
                cnt += find_x_miman_from_right(rev_neg, i, x)
            cnt += len(pos) * len(neg)
        return cnt

    
    while l + 1 < r:
        m = (l + r) // 2
        mimcount = count_miman(m)
        if mimcount < K:
            l = m
        else:
            r = m
    print(l)

main()

Solution (Python):
N, K, *A = map(int, open(0).read().split())

l_pos = sorted(v for v in A if v > 0)
l_neg = sorted(-v for v in A if v < 0)

cnt_pos = len(l_pos)
cnt_neg = len(l_neg)

pair_pos = cnt_pos * (cnt_pos - 1) // 2 + cnt_neg * (cnt_neg - 1) // 2
pair_neg = cnt_pos * cnt_neg
pair_zro = N * (N - 1) // 2 - pair_pos - pair_neg


def solve_neg(n):
    ub = 10 ** 18 + 1
    lb = 0
    while ub - lb > 1:
        mid = (ub + lb) // 2
        
        
        n_pos = len(l_pos)
        cnt = 0
        j = 0
        for v in reversed(l_neg):
            while j < n_pos and v * l_pos[j] < mid:
                j += 1
            cnt += n_pos - j

        if cnt < n:
            ub = mid
        else:
            lb = mid

    return -lb


def solve_pos(n):
    lb = 0
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        cnt = 0
        mid = (ub + lb) // 2

        
        n_neg = len(l_neg)
        j = 0
        for v in reversed(l_neg):
            if v ** 2 <= mid:
                cnt -= 1
            while j < n_neg and v * l_neg[j] < mid:
                j += 1
            cnt += j

        
        n_pos = len(l_pos)
        j = 0
        for v in reversed(l_pos):
            if v ** 2 <= mid:
                cnt -= 1
            while j < n_pos and v * l_pos[j] < mid:
                j += 1
            cnt += j

        
        cnt //= 2

        if cnt < n:
            lb = mid
        else:
            ub = mid
            
    return lb


if K <= pair_neg:
    ans = solve_neg(K)
elif K <= pair_neg + pair_zro:
    ans = 0
else:
    ans = solve_pos(K - pair_neg - pair_zro)
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
m,p=[],[]
for a in A:
    if a<0:
        m.append(a)
    elif a>0:
        p.append(a)
M,P=len(m),len(p)
Z=N-M-P
m.sort()
p.sort()
if M*P<K<=N*(N-1)//2-M*(M-1)//2-P*(P-1)//2:
    print(0)
elif K<=M*P:
    l,r=-10**18-1,0
    while l+1<r:
        t=(l+r)//2
        x=0
        mi=0
        for pi in range(P):
            while mi<M and m[mi]*p[pi]<=t:
                mi+=1
            x+=mi
        if K<=x:
            r=t
        else:
            l=t
    print(r)
else:
    l,r=0,10**18+1
    K-=M*P+Z*(Z-1)//2+Z*(M+P)
    m.reverse()
    while l+1<r:
        t=(l+r)//2
        x=0
        mi,pi=0,0
        for mj in range(M-1,-1,-1):
            while mi<M and m[mi]*m[mj]<=t:
                mi+=1
            x+=mi-(1 if mj<mi else 0)
        for pj in range(P-1,-1,-1):
            while pi<P and p[pi]*p[pj]<=t:
                pi+=1
            x+=pi-(1 if pj<pi else 0)
        if K<=x//2:
            r=t
        else:
            l=t
    print(r)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

left = -INF
right = INF
while right - left > 1:
    x = (left + right) // 2
    s = 0 
    t = 0 
    for a in A:
        if a > 0:
            l = -1
            r = N
            while r - l > 1:
                m = (l + r) // 2
                if A[m] * a <= x:
                    l = m
                else:
                    r = m
            s += r
        elif a < 0:
            l = -1
            r = N
            while r - l > 1:
                m = (l + r) // 2
                if A[m] * a <= x:
                    r = m
                else:
                    l = m
            s += N - r
        elif a == 0 and x >= 0:
            s += N

        if a * a <= x:
            t += 1
    count = (s - t) // 2
    if count >= K:
        right = x
    else:
        left = x
print(right)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, K = getNM()
A = getList()
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 numpy as np
def resolve():
    n, k = map(int, input().split())
    a = np.array(input().split(), dtype=np.int64)
    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__":
    resolve()

Solution (Python):
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    ps = []
    ms = []
    n0 = 0
    for i in ipt().split():
        ii = int(i)
        if ii == 0:
            n0 += 1
        elif ii > 0:
            ps.append(ii)
        else:
            ms.append(-ii)

    pn = len(ps)
    mn = len(ms)
    if k <= pn*mn:
        ps.sort()
        ms.sort(reverse=True)
        l = -10**(18)
        r = -1
        while l < r:
            mid = l + (r-l)//2
            num = 0 
            mi = 0
            for i in ps:
                for j in range(mi,mn):
                    if -i*ms[j] > mid:
                        break
                    mi += 1
                num += mi
            if num < k:
                l = mid+1
            else:
                r = mid
        print(l)

    elif k <= pn*mn+n0*(pn+mn)+n0*(n0-1)//2:
        print(0)

    else:
        k -= pn*mn+n0*(pn+mn)+n0*(n0-1)//2
        ps.sort()
        ms.sort()
        l = 1
        r = 10**18
        while l < r:
            mid = l + (r-l)//2
            num = 0 
            mi = 0
            pi = 0
            for i,mk in enumerate(ms[::-1]):
                mi = min(mi,mn-i-1)
                for j in range(mi,mn-i-1):
                    if mk*ms[j] > mid:
                        break
                    mi += 1
                num += mi
            for i,pk in enumerate(ps[::-1]):
                pi = min(pi,pn-i-1)
                for j in range(pi,pn-i-1):
                    if pk*ps[j] > mid:
                        break
                    pi += 1
                num += pi

            if num < k:
                l = mid+1
            else:
                r = mid
        print(l)
    return None

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


@njit('(i8,i8,i4[:],i4[:],i8,i8)', cache=True)
def judge1(tn, K, Ap, Am, Nm, Np):

    count = 0
    for i in range(Nm):
        search = -(-tn // -Am[i])
        j = np.searchsorted(Ap, search, side='left')
        count += Np - j

    return count >= K


@njit('(i8,i8,i4[:],i4[:],i8,i8,i8,i8)', cache=True)
def judge2(tn, K, Ap, Am, Nm, Np, m_count, z_count):

    count = 0
    for i in range(Np):
        search = tn // Ap[i]
        j = np.searchsorted(Ap, search, side='right')
        count += max(0, j - i - 1)

    for i in range(Nm):
        search = tn // Am[i]
        j = np.searchsorted(Am, search, side='right')
        count += max(0, j - i - 1)

    return count >= (K - m_count - z_count)


@njit('(i8,i8,i4[:],i4[:],i8,)', cache=True)
def solve(N, K, Ap, Am, Nz):

    INF = 10**18
    Np = Ap.size
    Nm = Am.size

    m_count = Np * Nm
    z_count = Nz * (Np + Nm) + Nz * (Nz - 1) // 2

    if K <= m_count:

        min_n, max_n = -INF, -1
        while max_n - min_n != 1:
            tn = (min_n + max_n) // 2
            if judge1(tn, K, Ap, Am, Nm, Np):
                max_n = tn
            else:
                min_n = tn

        ans = max_n

    elif K <= m_count + z_count:
        ans = 0

    else:

        min_n, max_n = 1, INF
        while max_n - min_n != 1:
            tn = (min_n + max_n) // 2
            if judge2(tn, K, Ap, Am, Nm, Np, m_count, z_count):
                max_n = tn
            else:
                min_n = tn

        ans = max_n

    return ans


def main():
    N, K = in_nn()
    A = in_nl()
    Ap, Am = [], []
    Nz = 0

    for i in range(N):
        if A[i] > 0:
            Ap.append(A[i])
        elif A[i] == 0:
            Nz += 1
        else:
            Am.append(A[i])

    Ap = np.array(sorted(Ap), np.int32)
    Am = np.array(sorted([-a for a in Am]), np.int32)

    print(solve(N, K, Ap, Am, Nz))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

INF = 10**18


def binary_search(min_n, max_n, judge):

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if judge(tn):
            max_n = tn
        else:
            min_n = tn

    return max_n


def main():
    N, K = in_nn()
    A = in_nl()

    Ap = []
    Am = []
    Nz = 0

    for i in range(N):
        if A[i] > 0:
            Ap.append(A[i])
        elif A[i] == 0:
            Nz += 1
        else:
            Am.append(A[i])

    Np = len(Ap)
    Nm = len(Am)

    m_count = Np * Nm
    z_count = Nz * (Np + Nm) + Nz * (Nz - 1) // 2
    

    if K <= m_count:

        Ap.sort()
        Am.sort()

        def judge(tn):

            count = 0
            for i in range(Nm):
                search = -(-tn // Am[i])
                j = bisect.bisect_left(Ap, search)
                count += Np - j

            return count >= K

        ans = binary_search(-INF, -1, judge)

    elif K <= m_count + z_count:
        ans = 0
    else:

        Ap.sort()
        Am = sorted([-a for a in Am])

        def judge(tn):

            count = 0
            for i in range(Np):
                search = tn // Ap[i]
                j = bisect.bisect_right(Ap, search)
                count += max(0, j - i - 1)

            for i in range(Nm):
                search = tn // Am[i]
                j = bisect.bisect_right(Am, search)
                count += max(0, j - i - 1)

            return count >= (K - m_count - z_count)

        ans = binary_search(1, INF, judge)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

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

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

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

l=-10**18
r=10**18

while l<r:
    pov=(l+r)//2
    if f(pov)>=k:
        r=pov
    else:
        l=pov+1
print(l)

Solution (Python):

from bisect import bisect_left, bisect_right
def resolve():
    def judge_m(mid):
        tot = 0
        for i in range(p_n):
            d = mid//P[i]
            tot += bisect_right(M, d)
        return tot >= K


    def judge_p(mid):
        tot = 0
        for i in range(p_n): 
            d = mid//P[i]
            tmp = bisect_right(P, d)
            if i < tmp:
                tmp -= 1 
            tot += tmp
        for i in range(m_n): 
            d = mid//M[i]
            tmp = bisect_right(M, d)
            if i < tmp:
                tmp -= 1 
            tot += tmp
        tot //= 2
        return tot >= K


    INF = 10 ** 18 + 1
    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))

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

    p_n = len(P)
    m_n = len(M)
    z_n = len(Z)
    minus = p_n * m_n
    zero = z_n*(z_n-1)//2 + z_n*p_n + z_n*m_n
    plus = p_n*(p_n - 1)//2 + m_n*(m_n-1)//2

    if K <= minus: 
        M.sort()
        l, u = -INF, 0
        while u - l > 1:
            mid = (u+l)//2
            if judge_m(mid):
                u = mid
            else:
                l = mid
        return print(u)
    elif K <= (minus + zero):
        return print(0)
    elif K <= (minus + zero + plus):
        K -= (minus + zero)
        M = [abs(m) for m in M]
        P.sort()
        M.sort()
        l, u = -1, INF
        while u - l > 1:
            mid = (u + l)//2
            if judge_p(mid):
                u = mid
            else:
                l = mid
        return print(u)


if __name__ == "__main__":
    resolve()

Solution (Python):

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

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

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

    print(high)


if __name__ == "__main__":
    resolve()

Solution (Python):

import numpy as np
def resolve():
    n, k = map(int, input().split())
    a = np.array(input().split(), dtype=np.int64)
    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__":
    resolve()

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

n, k = map(int, input().split())
a, b, c = 0, 0, 0
L, R = [], []
for p in map(int, input().split()):
  if p < 0:
    a += 1
    L.append(p)
  elif p == 0:
    b += 1
  else:
    c += 1
    R.append(p)
L.sort()
R.sort()
s = a*c
t = b*(b-1)//2 + (a+c)*b
if s < k <= s+t:
  ans = 0
else:
  if k <= s:
    ok = -1
    ng = -(10**18+1)
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = 0
      temp = 0
      for l in L:
        while now < c and l*R[now] > mid:
          now += 1
        temp += c - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  else:
    ok = 10**18
    ng = 0
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = c - 1
      temp = s+t
      for i, r in enumerate(R):
        if now <= i:
          break
        while now > i and r*R[now] > mid:
          now -= 1
        temp += now - i
      now = 0
      for i in range(a-1, -1, -1):
        l = L[i]
        if now >= i:
          break
        while now < i and l*L[now] > mid:
          now += 1
        temp += i - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  ans = ok
print(ans)

Solution (Python):
def comb(li):
    return len(li) * (len(li) - 1) // 2


def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)


if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)


elif k >= n * (n - 1) // 2 - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()

    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg) + count_large(m, pos)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)



else:
    print(0)

Solution (Python):




from bisect import bisect_left, bisect_right

import sys

input = sys.stdin.buffer.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

minus_num = bisect_left(A, 0)
zero_num = bisect_right(A, 0) - minus_num
plus_num = n - (minus_num + zero_num)

seki_minus = plus_num * minus_num
seki_plus = plus_num * (plus_num - 1) // 2 + minus_num * (minus_num - 1) // 2
seki_zero = zero_num * (plus_num + minus_num) + zero_num * (zero_num - 1) // 2
assert seki_minus + seki_plus + seki_zero == n * (n - 1) // 2

mA = A[:minus_num]
pA = A[-plus_num:]



def calc(num):
    res = 0
    if num < 0:
        lim = minus_num - 1
        mmA = mA[::-1]
        for i in range(plus_num):
            while lim >= 0:
                if mmA[lim] * pA[i] <= num:
                    lim -= 1
                else:
                    break
            res += minus_num - (lim + 1)
    elif num == 0:
        res = seki_zero + seki_minus
    else:
        
        lim = plus_num - 1
        for i in range(plus_num):
            while lim >= 0:
                if pA[lim] * pA[i] > num:
                    lim -= 1
                else:
                    break
            if lim >= i:
                res -= 1
            res += lim + 1
        
        lim = minus_num - 1
        mmA = mA[::-1]
        for i in range(minus_num):
            while lim >= 0:
                if mmA[lim] * mmA[i] > num:
                    lim -= 1
                else:
                    break
            if lim >= i:
                res -= 1
            res += lim + 1
        assert res % 2 == 0
        res //= 2
        res += seki_minus
        res += seki_zero
    return res


ok = 10 ** 20
ng = -(10 ** 20)

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


print(ok)

Solution (Python):





import sys
input = sys.stdin.readline

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


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