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):
def d_pairs():
    
    import numpy as np
    N, K = [int(i) for i in input().split()]
    A = np.array([int(i) for i in input().split()], np.int64)

    A = np.sort(A)
    zero = A[A == 0]
    positive = A[A > 0]
    negative = A[A < 0]

    def f(c):
        """数列 A から 2 要素を選んで積を取ったとき、c 以下となるようなペアの選び方"""
        count_pair = 0

        
        if c >= 0:
            count_pair += len(zero) * N
        
        count_pair += np.searchsorted(A, c // positive, side='right').sum()
        
        count_pair += (N - np.searchsorted(A, (-c - 1) // (-negative), side='right')).sum()
        
        count_pair -= np.count_nonzero(A * A <= c)  
        return count_pair // 2

    
    lower, upper = -10 ** 18, 10 ** 18
    while upper - lower > 1:
        x = (lower + upper) // 2
        if f(x) >= K:
            upper = x
        else:
            lower = x
    return upper

print(d_pairs())

Solution (Python):
import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

A_pos = A[A > 0]
A_neg = A[A < 0]
A_zero = A[A == 0]


def n_comb_lt(c):
    n_comb = 0
    
    target = c // A_pos  
    n_comb += np.searchsorted(A, target, side="right").sum()

    
    n_comb += n * len(A_zero) if c >= 0 else 0

    
    target = -(-c // A_neg)
    n_comb += (n - np.searchsorted(A, target, side="left")).sum()

    
    n_comb -= A[A * A <= c].size
    n_comb //= 2

    return n_comb

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



while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        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)
zero = a[a == 0]
pos = a[a > 0]
neg = a[a < 0]

def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    
    if x >= 0:
        cnt_tpl += len(zero) * n
    
    cnt_tpl += np.searchsorted(a, x // pos, side='right').sum()
    
    cnt_tpl += (n - np.searchsorted(a, (-x - 1) // (-neg), side='right')).sum()
    
    cnt_tpl -= np.count_nonzero(a * a <= x)
    assert cnt_tpl % 2 == 0
    return cnt_tpl // 2

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

print(right)

Solution (Python):
from bisect import bisect_left

def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l


def main():
    N, K = list(map(int, input().split()))
    A = sorted(list(map(int, input().split())))
    p = bisect_left(A, 0)
    An = A[:p]
    Ap = A[p:]

    if K <= p * (N - p):
        def helper(x):
            t = 0
            r = 0
            for p in Ap:
                while t < len(An) and An[t] * p <= x:
                    t += 1
                r += t
            return r < K
        l = binsearch(Ap[-1] * An[0] - 1, 1, helper)
    else:
        K -= p * (N - p)
        An.reverse()
        def helper(x):
            r = 0
            for a in [Ap, An]:
                t = len(a) - 1
                for i, p in enumerate(a):
                    if t <= i:
                        break
                    while t > i and a[t] * p > x:
                        t -= 1
                    r += t - i
            return r < K 
        m = Ap[-1]
        if An:
            m = max(m, -An[-1])
        l = binsearch(-1, m * m, helper)
    print(l + 1)


main()

Solution (Python):
import numpy as np


def main():
    N, K = [int(x) for x in input().split()]
    A = np.array(input().split(), np.int64)
    A = np.sort(A)
    minus = A[A<0]
    zero = A[A==0]
    plus = A[A>0]


    def f(x):
        """number of products <=x
        """
        res = 0
        if x >= 0:
            res += len(zero) * N
        
        res += np.searchsorted(A, x // plus, side="right").sum()

        
        res += (N - np.searchsorted(A, (-x-1) // (-minus), side="right")).sum()

        
        res -= np.count_nonzero(A*A <= x)
        res //= 2

        return res

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

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


if __name__ == '__main__':
    main()