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

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,k = nm()
l = nl()
f = list(filter(lambda x:x>0, l))
g = list(filter(lambda x:x<0, l))
f.sort(); g.sort(reverse=True)
pl = len(f); mi = len(g)
ze = n - pl - mi
tomi = pl*mi
if tomi >= k:
    def jud(z):
        ret = 0
        i = mi
        for x in f:
            while i and x*g[i-1] <= z: i -= 1
            ret += mi - i
        return ret
    ok,ng = 0,max(f)*min(g)-1
    while ok - ng > 1:
        mid = (ok+ng)//2
        if jud(mid) < k:
            ng = mid
        else:
            ok = mid
    print(ok)
    exit(0)

tomi += ze*(n-ze) + (ze-1)*ze//2
if tomi >= k:
    print(0); exit(0)

else:
    k -= tomi
    def jud2(z):
        ret = 0
        i = pl
        for e,x in enumerate(f):
            while i and f[i-1]*x > z: i -= 1
            ret += i - (e<=i-1)
        i = mi
        for e,x in enumerate(g):
            while i and g[i-1]*x > z: i -= 1
            ret += i - (e<=i-1)
        return ret//2
    ok,ng = 0,max(max(f+[0])**2, min(g+[0])**2)
    while ng - ok > 1:
        mid = (ok+ng)//2
        if jud2(mid) < k:
            ok = mid
        else:
            ng = mid
    print(ng)

Solution (Python):
N, K = map(int, input().split())
A = sorted([int(a) for a in input().split()])

pos = 0
zer = 0
neg = 0
for a in A:
    if a > 0: pos += 1
    elif a < 0: neg += 1
    else: zer += 1
B = [a for a in A if a > 0]
C = [-a for a in A if a < 0][::-1]
b = len(B)
c = len(C)

def cnt(x):
    if x >= 0:
        re = pos * neg + zer * (pos + neg) + zer * (zer - 1) // 2
        j = b - 1
        for i in range(b):
            while j >= 0 and B[i] * B[j] > x:
                j -= 1
            re += max(j - i, 0)
        j = c - 1
        for i in range(c):
            while j >= 0 and C[i] * C[j] > x:
                j -= 1
            re += max(j - i, 0)
        return re
        
    re = 0
    j = 0
    y = -x
    for i in range(b)[::-1]:
        while j < c and B[i] * C[j] < y:
            j += 1
        re += c - j
    return re

l, r = - (1<<60), 1<<60
while r - l > 1:
    m = (l+r) // 2
    if cnt(m) >= K:
        r = m
    else:
        l = m

print(r)

Solution (Python):
import itertools
import os
import sys

import numpy as np



if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N, K = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

A = np.array(A, dtype=int)
minuses = np.msort(np.abs(A[A < 0]))
pluses = np.msort(A[A > 0])
zeros = A[A == 0]


def solve():
    p = []
    for a, b in itertools.combinations(A, r=2):
        p.append(a * b)
    p.sort()
    print(p[K - 1])


def test(n):
    
    minus_cnt = len(minuses) * len(pluses)
    zeros_cnt = len(zeros) * (N - len(zeros)) + (len(zeros) * (len(zeros) - 1) // 2)
    if n == 0:
        return minus_cnt + zeros_cnt >= K
    ret = minus_cnt + zeros_cnt
    if n > 0:
        a = np.searchsorted(pluses, n // pluses, side='right')
        b = np.searchsorted(minuses, n // minuses, side='right')
        c = pluses ** 2 <= n
        d = minuses ** 2 <= n
        return ret + (a.sum() + b.sum() - c.sum() - d.sum()) // 2 >= K
    else:
        a = np.searchsorted(-minuses[::-1], n // pluses, side='right')
        b = np.searchsorted(-pluses[::-1], n // minuses, side='right')
        return (a.sum() + b.sum()) // 2 >= K


ok = 10 ** 18 - 1
ng = -10 ** 18 - 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if test(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
Am = []
n0 = 0
Ap = []
for a in A:
    if a<0: Am.append(a)
    if a==0: n0+=1
    if a>0: Ap.append(a)

Am = sorted(Am)
Ap = sorted(Ap)
    
nm = len(Am)
np = len(Ap)

Nm = nm*np
N0 = n0*(n0-1)//2 + n0*(nm+np)
Np = nm*(nm-1)//2 + np*(np-1)//2

if K<=Nm:
    
    min_ok = 0
    max_ng = -10**20
    while min_ok-max_ng>1:
        tgt = (min_ok+max_ng)//2

        k=0
        i=0
        for a in Am:
            while i<np and a*Ap[i]>tgt: i+=1
            k+=np-i

        if k>=K:
            min_ok = tgt
        else:
            max_ng = tgt
            
    print(min_ok)

elif K<=Nm+N0:
    
    print(0)

else:
    
    K-= Nm+N0
    
    Am = [-a for a in Am[::-1]]
    
    min_ok = +10**20
    max_ng = 0
    while min_ok-max_ng>1:
        tgt = (min_ok+max_ng)//2

        k=0
        i=np-1
        for j,a in enumerate(Ap):
            while i>=0 and a*Ap[i]>tgt: i-=1
            if i<=j: break
            k+=i-j
            
        i=nm-1
        for j,a in enumerate(Am):
            while i>=0 and a*Am[i]>tgt: i-=1
            if i<=j: break
            k+=i-j
            
        if k>=K:
            min_ok = tgt
        else:
            max_ng = tgt
            
    print(min_ok)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def solve_binary(mid):
  count = 0

  if mid == 0:
    count = (P+M)*zero + P*M + (zero*(zero-1)//2 if zero >= 2 else 0)
    return k <= count

  if mid < 0:
    
    
    
    j=0
    for i in range(M):
      while j<P and Plus[j]*Minus[i] > mid:
        j += 1
      count += P-j
    return k <= count

  if mid > 0:
    count += (P+M)*zero + P*M + (zero*(zero-1)//2 if zero >= 2 else 0)
    
    
    j = 0
    for i in range(M-1,-1,-1):
      while j<M and Minus[j]*Minus[i] > mid:
        j += 1
      count += max(0,i-j)
    
    
    j = P-1
    for i in range(P):
      while 0<=j and Plus[j]*Plus[i] > mid:
        j -= 1
      count += max(0,j-i)
    
    return k <= count
      

def binary_search(n):
    ng=-n-1
    ok=n
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve_binary(mid):
            ok=mid
        else:
            ng=mid
    return ok

zero=0
n,k=map(int,input().split())
A=list(map(int,input().split()))
Minus=[]; Plus=[]
for ai in A:
  if ai < 0: Minus.append(ai)
  elif ai == 0 : zero += 1
  elif ai > 0: Plus.append(ai)
Minus.sort(); Plus.sort()
M = len(Minus) ; P = len(Plus)




X = binary_search(10 ** 18)
print(X)

Solution (Python):
import sys
range = xrange
input = raw_input

n, k = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
i = 0
while i < n and A[i] < 0:
    i += 1
Aneg = A[:i]
Apos = A[i:]

Aneg.reverse()
nneg = len(Aneg)
npos = len(Apos)

l = -10**18 - 100
r = 10**18 + 100
while l < r:
    mid = l + r >> 1

    counter = 0
    if mid >= 0:
        counter += nneg * npos
        for B in Aneg, Apos:
            j = 0
            for i in reversed(range(len(B))):
                b = B[i]
                while j < len(B) and B[j] * b <= mid:
                    j += 1
                counter += min(j, i)
    else:
        j = 0
        for i in range(nneg):
            a = Aneg[i]
            while j < npos and Apos[~j] * a <= mid:
                j += 1
            counter += j
    
    if counter >= k:
        r = mid
    else:
        l = mid + 1

print l

Solution (Python):

import numpy as np
stdin = open(0)

N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().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):
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:
        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))