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

Solution (Python):
import sys
import numpy as np


TEST_INPUT = [
    """
    4 3
    3 3 -4 -2
    """,
    """
    10 40
    5 4 3 2 -1 0 0 0 0 0
    """,
    """
    30 413
    -170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0
    """
]
ANSWER = [
    "-6",
    "6",
    "448283280358331064"
]


class InputHandler:

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

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


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

    

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


def solve(n, k, a_list):

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

    a_arr = np.array(a_list)

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

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

    return right


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


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


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


if __name__ == "__main__":
    
    main()

Solution (Python):
from bisect import bisect_left, bisect_right

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

negative_end = bisect_left(a, 0)
positive_begin = bisect_right(a, 0)

negative_cnt = negative_end
positive_cnt = n - positive_begin
zero_cnt = n - negative_cnt - positive_cnt

prod_negative = negative_cnt * positive_cnt

prod_zero = zero_cnt * (negative_cnt + positive_cnt) + zero_cnt * (zero_cnt - 1) // 2


if k <= prod_negative:
    high, low = 0, -10**18
    while high > low + 1:
        mid = (high + low) // 2
        or_higher = 0
        r = positive_begin
        for l in range(negative_end):
            while r < n and a[l] * a[r] > mid:
                r += 1
            or_higher += positive_cnt - (r - positive_begin)

        if or_higher >= k:
            high = mid
        else:
            low = mid

    res = high

elif k <= prod_negative + prod_zero:
    res = 0

else:
    k -= prod_negative + prod_zero
    high, low = 10**18, 0
    while high > low + 1:
        mid = (high + low) // 2
        or_higher = 0
        r = n - 1
        for l in range(positive_begin, n):
            while r < n and a[l] * a[r] > mid and l < r:
                r -= 1
            or_higher += r - l if l < r else 0
        l = 0
        for r in range(negative_end - 1, -1, -1):
            while l < n and a[l] * a[r] > mid and l < r:
                l += 1
            or_higher += r - l if l < r else 0

        if or_higher >= k:
            high = mid
        else:
            low = mid

    res = high

print(res)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    inf = 10**20
    

    N,k = map(int, input().split())
    zero, p, n = 0, [], []
    a = list(map(int, input().split()))
    for i in a:
        if i==0:
            zero += 1
        elif i > 0:
            p.append(i)
        else:
            n.append(i)
    p.sort()
    n.sort(reverse=True)

    
    
    l, r = -inf, inf
    while r - l > 1:
        mid = (l + r) // 2
        cnt = 0
        
        if mid >= 0:
            cnt += zero*(zero-1)//2 + zero*(N-zero)
        
        if mid > 0:
            
            cnt += len(n) * len(p)
            
            for a in (p, n):
                left, right = 0, len(a)-1
                while left < right:
                    
                    while left<right and a[left]*a[right]>mid:
                        right -= 1
                    cnt += right - left
                    
                    left += 1
        else:
            right = len(n) - 1
            for left in range(len(p)):
                while right>=0 and p[left]*n[right]<=mid:
                    right -= 1
                cnt += len(n) - right - 1
        
        if cnt >= k:
            r = mid
        else:
            l = mid

    print(r)



if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A == 0]
nega = A[A < 0]


def check(x):
    count = 0  
    if x >= 0:
        count += len(zero) * N  
    count += np.searchsorted(A, x // posi, side = 'right').sum()  
    count += (N - np.searchsorted(A, (-x - 1) // (-nega), side = 'right')).sum()  
    count -= np.count_nonzero(A * A <= x)  
    return count // 2  


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

print(high)

Solution (Python):
import numpy as np
 
N,K=map(int, input().split())
A=np.sort(np.array(input().split(),np.int64))
z=A[A==0]
p=A[A>0]
n=A[A<0]
 
def f(x):
 cnt=0
 if x>=0:
  cnt+=len(z)*N
 cnt+=np.searchsorted(A,x//p,side='right').sum()
 cnt+=(N-np.searchsorted(A,(-x-1)//(-n),side='right')).sum()
 cnt-=np.count_nonzero(A*A<=x)
 assert cnt%2==0
 return cnt//2
 
l=-10**18
r=10**18
while l+1<r:
 x=(l+r)//2
 if f(x)>=K:
  r=x
 else:
  l=x
print(r)

Solution (Python):
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    Neg=[-a for a in A if a<0]
    Pos=[a for a in A if a>=0]
    Neg.sort(); Pos.sort()
    ln,lp=len(Neg),len(Pos)
 
    def cnt(x):
        ret=0
        if x<0:
            x=-x
            pos_idx=0
            for num in Neg[::-1]:
                while pos_idx<lp and Pos[pos_idx]*num<x:
                    pos_idx+=1
                ret+=lp-pos_idx
                if pos_idx==lp:
                    break
            return ret
        idx=0
        for num in Neg[::-1]:
            if num**2<=x:
                ret-=1
            while idx<ln and Neg[idx]*num<=x:
                idx+=1
            ret+=idx
        idx=0
        for num in Pos[::-1]:
            if num**2<= x:
                ret-=1
            while idx<lp and Pos[idx]*num<=x:
                idx+=1
            ret+=idx
        ret//=2
        ret+=ln*lp
        return ret
    
    l,r=-(10**18+1),10**18+1
    while r-l>1:
        m=(l+r)//2
        if cnt(m)<k:
            l=m
        else:
            r=m
    print(r)
    
if __name__=='__main__':
    main()

Solution (Python):
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    Neg=[-a for a in A if a<0]
    Pos=[a for a in A if a>=0]
    Neg.sort(); Pos.sort()
    ln,lp=len(Neg),len(Pos)

    def cnt(x):
        ret=0
        if x<0:
            x=-x
            pos_idx=0
            for num in Neg[::-1]:
                while pos_idx<lp and Pos[pos_idx]*num<x:
                    pos_idx+=1
                ret+=lp-pos_idx
                if pos_idx==lp:
                    break
            return ret
        idx=0
        for num in Neg[::-1]:
            if num**2<=x:
                ret-=1
            while idx<ln and Neg[idx]*num<=x:
                idx+=1
            ret+=idx
        idx=0
        for num in Pos[::-1]:
            if num**2<= x:
                ret-=1
            while idx<lp and Pos[idx]*num<=x:
                idx+=1
            ret+=idx
        ret//=2
        ret+=ln*lp
        return ret
    
    l,r=-(10**18+1),10**18+1
    while r-l>1:
        m=(l+r)//2
        if cnt(m)<k:
            l=m
        else:
            r=m
    print(r)
    
if __name__=='__main__':
    main()

Solution (Python):
def solve_m(k, a_m, a_p):
    def syaku(mid):
        """mid以下になる組の数を数える"""
        rm = 0
        cnt = 0
        for lp, num in enumerate(a_p):
            while True:
                if rm >= len(a_m) or num * a_m[rm] > mid :
                    break
                else:
                    rm += 1
            cnt += rm
        return cnt
                
    ok, ng = 1, -10 ** 20
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if syaku(mid) >= k:
            ok = mid
        else:
            ng = mid
    return ok

    
def solve_p(k, a_m, a_p):
    def syaku(mid):
        """mid以下になる組の数を数える"""
        r = len(a_p)
        cnt = 0
        for l, num in enumerate(a_p):
            while True:
                if r == 0 or num * a_p[r - 1] <= mid:
                    break
                else:
                    r -= 1
            cnt += r
            if l <= r - 1:
                cnt -= 1
        r = len(a_m)
        for l, num in enumerate(a_m):
            while True:
                if r == 0 or num * a_m[r - 1] <= mid:
                    break
                else:
                    r -= 1
            cnt += r
            if l <= r - 1:
                cnt -= 1
        return cnt // 2

    a_m = sorted([-num for num in a_m])
    ok, ng = 10 ** 20, -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if syaku(mid) >= k:
            ok = mid
        else:
            ng = mid
    return ok


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

cnt_p, cnt_m, cnt_0 = 0, 0, 0
tmp_p, tmp_m, tmp_0 = 0, 0, 0
for num in a:
    if num > 0:
        tmp_p += 1
    elif num < 0:
        tmp_m += 1
    else:
        tmp_0 += 1
cnt_p += tmp_p * (tmp_p - 1) // 2 + tmp_m * (tmp_m - 1) // 2
cnt_m += tmp_p * tmp_m
cnt_0 += (tmp_p + tmp_m) * tmp_0 + tmp_0 * (tmp_0 - 1) // 2


a_m = sorted([a[i] for i in range(n) if a[i] < 0])
a_p = sorted([a[i] for i in range(n) if a[i] > 0])

if k <= cnt_m:
    ans = solve_m(k, a_m, a_p)
elif cnt_m < k <= cnt_m + cnt_0:
    ans = 0
else:
    ans = solve_p(k - cnt_m - cnt_0, a_m, a_p)
      
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right

def count(x, li1, li2, p):
    cnt = 0
    now = len(li2)-1 if p else 0
    for ind, i in enumerate(li1):
        rng = range(now, -1, -1) if p else range(now, len(li2))
        for j in rng:
            if p and ind==j:
                continue
            if i*li2[j]<x:
                
                cnt += j+1 if p else len(li2)-j
                cnt -= 1 if p and ind<j else 0
                now = j
                break
        else:
            break
    return cnt//2 if p else cnt

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

def p_solve(x):
    tmp = count(x, posi, posi, True)
    tmp += count(x, nega[::-1], nega[::-1], True)
    
    return np*nn+nn*nz+nz*np+nz*(nz-1)//2+tmp < k

def n_solve(x):
    return count(x, nega, posi, False) < k


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
nega = a[:bisect_left(a, 0)]
posi = a[bisect_right(a, 0):]
np = len(posi)
nn = len(nega)
nz = n - np - nn
if k <= np*nn:
    ans = bisect(nega[0]*posi[-1]-1, 0, n_solve)
elif k <= np*nn+nn*nz+nz*np+nz*(nz-1)//2:
    ans = 0
else:
    ma = 0
    if len(nega)>1:
        ma = nega[0]*nega[1]
    if len(posi)>1 and ma<posi[-1]*posi[-2]:
        ma = posi[-1]*posi[-2]
    ans = bisect(1, ma+1, p_solve)
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right

def count(x, li1, li2, p):
    cnt = 0
    now = len(li2)-1 if p else 0
    for ind, i in enumerate(li1):
        rng = range(now, -1, -1) if p else range(now, len(li2))
        for j in rng:
            if p and ind==j:
                continue
            if i*li2[j]<x:
                
                cnt += j+1 if p else len(li2)-j
                cnt -= 1 if p and ind<j else 0
                now = j
                break
        else:
            break
    return cnt//2 if p else cnt

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

def p_solve(x):
    tmp = count(x, posi, posi, True)
    tmp += count(x, nega[::-1], nega[::-1], True)
    
    return np*nn+nn*nz+nz*np+nz*(nz-1)//2+tmp < k

def n_solve(x):
    return count(x, nega, posi, False) < k


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
nega = a[:bisect_left(a, 0)]
posi = a[bisect_right(a, 0):]
np = len(posi)
nn = len(nega)
nz = n - np - nn
if k <= np*nn:
    ans = bisect(-10**18-1, 0, n_solve)
elif k <= np*nn+nn*nz+nz*np+nz*(nz-1)//2:
    ans = 0
else:
    ma = 0
    if len(nega)>1:
        ma = nega[-1]*nega[-2]
    if len(posi)>1 and ma<posi[-1]*posi[-2]:
        ma = posi[-1]*posi[-2]
    ans = bisect(1, 10**18+1, p_solve)
print(ans)

Solution (Python):
import numpy as np

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



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

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

print(right)

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

import bisect
n_m = bisect.bisect_left(a, 0)
n_0 = bisect.bisect_left(a, 1) - n_m
n_p = n - (n_m + n_0)

nn_p = n - (n_m * n_p + n_0 * (n - n_0) + n_0*(n_0-1)//2)

if( n_m * n_p < k)&(k <= n - nn_p):
    print(0)
    exit()

def calc_m(a, b, len_a, len_b, x):
    i = len_a-1
    j = 0
    cnt = 0
    while(True):
        tmp = a[i] * b[j]
        if( tmp < x):
            cnt += i+1
            j += 1
        else:
            i -= 1

        if(i < 0)|(j >= len_b):
            break
    return cnt

def calc_p(a,len_a, x):
    if(len_a <= 1):
        return 0

    i = len_a - 1
    j = 0
    cnt = 0
    while(True):
        tmp = a[i] * a[j]
        if( tmp < x):
            cnt += i+1 - ( i >= j)
            j += 1
        else:
            i -= 1

        if(i < 0)|(j >= len_a):
            break
    return cnt//2

if( n_m * n_p >= k):
    a_m = tuple(a[:n_m])
    a_p = tuple(a[  :(n - n_p -1):-1])

    ul = [a_m[-1] * a_p[-1]+1, n_m*n_p]
    dl = [a_m[0] * a_p[0]-1, 0]

    while(True):
        if(ul[0] - dl[0] == 1):
            break
        mid = (dl[0] + ul[0])//2
        mid_cnt = calc_m(a_m,a_p,n_m,n_p, mid)

        if( mid_cnt < k):
            dl = [ mid, mid_cnt ]
        else:
            ul = [ mid, mid_cnt ]

    print(dl[0])

else:
    k = k - (n - nn_p)
    a_m = tuple(a[n_m - 1::-1])
    a_p = tuple(a[ (n - n_p) :])

    if(n_m <= 1):
        ul = [a_p[-1] * a_p[-2]+1, nn_p]
        dl = [a_p[0] * a_p[1]-1, 0]
    elif(n_p <= 1):
        ul = [a_m[-1] * a_m[-2]+1, nn_p]
        dl = [a_m[0] * a_m[1]-1, 0]
    else:
        ul = [max(a_m[-1] * a_m[-2]+1 ,a_p[-1] * a_p[-2]+1), nn_p]
        dl = [min(a_p[0] * a_p[1]-1 ,a_m[0] * a_m[1]-1), 0]

    while(True):
        if(ul[0] - dl[0] == 1):
            break
        mid = (dl[0] + ul[0])//2
        mid_cnt = calc_p(a_m,n_m, mid) + calc_p(a_p,n_p, mid)

        if( mid_cnt < k):
            dl = [ mid, mid_cnt ]
        else:
            ul = [ mid, mid_cnt ]

    print(dl[0])

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


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

right = 10**18+1
left = -(10**18+1)

while left+1 < right:
    mid = (left + right)//2

    if cnt(mid) < k:
        left = mid
    else:
        right = mid

print(int(right))

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
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

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

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


def test(x):
    cnt = 0

    if x >= 0:
        cnt += len(zero) * N

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

    cnt //= 2

    return K <= cnt


l = -(10 ** 19)  
r = 10 ** 19  

while l + 1 != r:
    mid = (l + r) // 2

    if test(mid):
        r = mid
    else:
        l = mid

print(r)

Solution (Python):
import sys

def f1(m):
    j=0
    num=0
    for x in ap[::-1]:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    h,l=0,10**18
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        else: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    k-=pz
    h,l=10**20,0
    while h-l>1:
        md=(h+l)//2
        p=f2(md)
        if p>=k: h=md
        else: l=md
    print(h)

Solution (Python):
import itertools
import numpy as np

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

positive = A[A>0]
negative = A[A<0]
zero = A[A==0]

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

while l + 1 < r:
    x = (l+r) // 2 
    cnt = 0
    if x >= 0:
        cnt += N * len(zero)
    
    
    cnt += A.searchsorted(x//positive, side="right").sum()
    cnt += (N - A.searchsorted(-(-x//negative), side="left")).sum()
    cnt -= np.count_nonzero(A * A <= x)
    cnt //= 2
 
    if cnt >= K:
        r = x
    else:
        l = x
print(r)

Solution (Python):
import numpy as np
n, k = map(int,input().split())
a = np.array(list(map(int,input().split())))
a.sort()
posi = a[a>0]
zero = a[a==0]
nega = a[a<0]


l = -10**18-1
r = 10**18+1
while r-l > 1:
    mid = (r+l)//2
    cnt = 0
    if mid >= 0:
        cnt += len(zero)*n
    
    
    

    cnt += a.searchsorted(mid//posi, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//nega), 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
from bisect import bisect_left, bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()


def countPair(Ap, Am, plus, minus, zero, x):
    """
    「積がx未満になる組」の個数を返す。

    Aiをfixしたとき、Ai * Aj < xなるjの個数をカウントしていけば良い。
    二分探索では間に合わなかったので、尺取り法で実装する。
    """
    num = 0
    if x < 0:
        idx = 0 
        for a in Am:
            while idx < plus and a * Ap[idx] >= x:
                idx += 1
            if idx >= plus:
                break
            num += plus - idx
        return num

    elif x == 0:
        num = plus * minus
        return num

    else:
        num = plus * minus 
        num += zero * (plus + minus) 
        num += zero * (zero - 1) // 2 

        """
        以下のカウントでは(A[i]*A[j])と(A[j]*A[i])を区別してしまう。
        また(A[i]*A[i])も数えてしまうので、あえてまずはこのような重複をありにして、
        最後に２で割るなりして処理する。
        """
        prenum = 0
        dupl = 0
        
        idx = plus - 1 
        for a in Ap:
            while idx >= 0 and a * Ap[idx] >= x:
                idx -= 1
            prenum += idx + 1

            if a * a < x:
                dupl += 1

        
        idx = minus - 1 
        for a in Am:
            while idx >= 0 and a * Am[idx] < x:
                idx -= 1
            prenum += minus - idx - 1

            if a * a < x:
                dupl += 1

        return num + (prenum - dupl) // 2

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    Ap = []
    Am = []
    plus = 0
    minus = 0
    zero = 0
    for a in A:
        if a > 0:
            Ap.append(a)
            plus += 1
        elif a < 0:
            Am.append(a)
            minus += 1
        else:
            zero += 1
    Ap.sort()
    Am.sort()

    """
    (K個目の値) = (「積がx未満になる組がK個未満」であるようなxの最大値)
    として決め打ち二分探索を行う。
    """

    l = -10 ** 18 - 1
    r = 10 ** 18 + 1
    while r - l > 1:
        m = (l + r) // 2
        if countPair(Ap, Am, plus, minus, zero, m) < K:
            l = m
        else:
            r = m
    print(l)


if __name__ == "__main__":
    main()

Solution (Python):
n,k=[int(j) for j in input().split()]
from numpy import *
a=array([int(j) for j in input().split()])
a.sort()
lm=a[a<0]
lp=a[a>0]
lz=a[a==0]
np=len(lp)
nm=len(lm)
nz=len(lz)

import bisect
import math
def f(x):
    c=0
    if x>=0:
        c+=nz*n
    c+=searchsorted(a,x//lp,side="right").sum()
    c+=(n-searchsorted(a,(-x-1)//(-lm),side="right")).sum()
    c-=count_nonzero(a*a<=x)
    return c//2

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

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

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    
    posi,zero,nega = [],[],[]
    for num in a:
        if num > 0:
            posi.append(num)
        elif num == 0:
            zero.append(num)
        else:
            nega.append(num)
            
    lp,lz,ln = len(posi),len(zero),len(nega)
    posi.sort(),nega.sort()
    posi,zero,nega = np.array(posi),np.array(zero),np.array(nega)
    _nega = nega[::-1]*(-1)
    
    def ch(x):
        if x == 0:
            return (lz*(lz-1))//2+lz*(lp+ln)+lp*ln
        elif x > 0:
            count = (lz*(lz-1))//2+lz*(lp+ln)+lp*ln
            puse = np.searchsorted(posi,(x//posi),side="right")
            pdup = np.count_nonzero(posi**2<=x)
            nuse = np.searchsorted(_nega,x//_nega,side="right")
            ndup = np.count_nonzero(_nega**2<=x)
            return (np.sum(puse)+np.sum(nuse)-pdup-ndup)//2+count
        else:
            count = np.searchsorted(nega,x//posi,side="right")
            return np.sum(count)

    l,r = -10**18-1,10**18+1
    while r-l > 1:
        mid = (r+l)//2
        if ch(mid) >= K:
            r = mid
        else:
            l = mid
    print(r)
    
if __name__ == "__main__":
    main()

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

def main():
    N,K = map(int,input().split())
    a = np.array(list(map(int,input().split())))
    a.sort()
    posi,zero,nega = a[a>0],a[a==0],a[a<0]
    lz = len(zero)
    
    def ch(x):
        count = 0
        if x >= 0:
            count += lz*N
        count += np.searchsorted(a,x//posi,side="right").sum()
        count += (N-np.searchsorted(a,-(-x//nega))).sum()
        count -= np.count_nonzero(a**2<=x)
        return count//2

    l,r = -10**18-1,10**18
    while r-l > 1:
        mid = (r+l)//2
        if ch(mid) >= K:
            r = mid
        else:
            l = mid

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

Solution (Python):
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

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

a_minus = a_zero = a_plus = 0
for i in range(n):
    if a[i] > 0:
        a_plus += 1
    elif a[i] == 0:
        a_zero += 1
    else:
        a_minus += 1

aa_minus = a_minus * a_plus
aa_zero = a_zero * (n - a_zero) + a_zero * (a_zero - 1) // 2


def check_minus(x):
    
    
    cnt = 0
    j = a_minus + a_zero
    for i in range(a_minus):
        
        while j < n and a[i] * a[j] > x:
            j += 1
        cnt += n - j

    return cnt >= k


def check_plus(x):
    
    

    def func(b, m):
        
        
        c = 0
        j = m - 1
        for i in range(m):
            while j > 0 and b[i] * b[j] > x:
                j -= 1
            c += max(j - i, 0)
        return c

    cnt = aa_minus + aa_zero
    cnt += func(a[-a_plus:], a_plus)
    cnt += func(list(reversed(a[:a_minus])), a_minus)
    return cnt >= k


if k <= aa_minus:
    
    lb = a[0] * a[-1] - 1  
    ub = 0  
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_minus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub
elif k <= aa_minus + aa_zero:
    
    ans = 0
else:
    
    lb = 0  
    ub = max(a[0]**2, a[-1]**2) + 1  
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_plus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub

print(ans)

Solution (Python):
import numpy as np

from bisect import bisect

DEBUG = False


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

A.sort()
A = np.array(A, dtype=np.int64)
neg = A[A < 0]
zero = A[A == 0]
pos = A[A > 0]


revAbsNeg = -neg[::-1]


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


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