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

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
if p>0:
  AP=A[-p:]
else:
  AP=[]
if q>0:
  AN=A[:q]
else:
  AN=[]

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  x=0
  y=10**18
  K=K-a-b
  if q<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  AN=AN[::-1]
  AN=-AN
  
  if p<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  while y-x>1:
    tmp=(y+x)//2
    counter1=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
    counter2=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)

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

def main():
  N,K = map(int,input().split())
  A = sorted(list(map(int,input().split())))
  
  
  
  AM = []
  AP = []
  for a in A:
    if a > 0:
      AP.append(a)
    elif a < 0:
      AM.append(a)

  INF = 10**18+1
  l = -INF
  r = INF
  while(l+1 < r):
    
    
    c = (l+r)//2
    x = 0
    if c > 0:
      
      
      i = len(AP)-1
      for j in range(len(AP)):
        if j >= i:
          break
        while(j < i and AP[i]*AP[j] >= c):
          i -= 1
        x += i-j
      i = 0
      for j in range(len(AM)-1,-1,-1):
        if j <= i:
          break
        while (i < j and AM[i]*AM[j] >= c):
          i += 1
        x += j-i
      
      x += len(AP)*len(AM)
      
      x += (len(AP)+len(AM))*(N-len(AP)-len(AM))
      if N-len(AP)-len(AM) > 1:
        x += (N-len(AP)-len(AM))*(N-len(AP)-len(AM)-1)//2
    elif c == 0:
      
      
      x += len(AP)*len(AM)
    else:
      
      
      i = 0
      for j in range(len(AM)):
        while(i < len(AP) and AP[i]*AM[j] >= c):
          i += 1
        x += len(AP)-i

    
    if x < K:
      l = c
    else:
      r = c
  print(l)

if __name__ == '__main__':
  main()

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

def main():
  N,K = map(int,input().split())
  A = sorted(list(map(int,input().split())))
  
  AM = []
  AP = []
  for a in A:
    if a > 0:
      AP.append(a)
    elif a < 0:
      AM.append(a)

  INF = 10**18+1
  l = -INF
  r = INF
  while(l+1 < r):
    
    
    c = (l+r)//2
    x = 0
    if c > 0:
      i = len(AP)-1
      for j in range(len(AP)):
        if j >= i:
          break
        while(j < i and AP[i]*AP[j] >= c):
          i -= 1
        x += i-j
      i = 0
      for j in range(len(AM)-1,-1,-1):
        if j <= i:
          break
        while (i < j and AM[i]*AM[j] >= c):
          i += 1
        x += j-i
      
      x += len(AP)*len(AM)
      x += (len(AP)+len(AM))*(N-len(AP)-len(AM))
      if N-len(AP)-len(AM) > 1:
        x += (N-len(AP)-len(AM))*(N-len(AP)-len(AM)-1)//2
    elif c == 0:
      x += len(AP)*len(AM)
    else:
      i = 0
      for j in range(len(AM)):
        while(i < len(AP) and AP[i]*AM[j] >= c):
          i += 1
        x += len(AP)-i

    
    if x < K:
      l = c
    else:
      r = c
  print(l)

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

pos = A[A > 0]
neg = 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//pos, side="right").sum()
    cnt += (N - A.searchsorted(-(-x//neg), 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(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):
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_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

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

if K <= negative_pairs_cnt:
    
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

else:
    
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0

        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)

        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1

            or_higher_cnt += max(0, r - l)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

Solution (Python):
import numpy as np

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

zero = a[a==0]
pos = a[a>0]
neg = 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//pos,side='right').sum()
    cnt += (n-a.searchsorted(-(-x//neg),side='left')).sum()
    cnt -= np.count_nonzero(a*a<=x)
    cnt//=2

    if cnt >= k:
        r = x
    else:
        l = x

print(r)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
z = 0
while a[z] < 0:
    z += 1
am = a[:z]
ap = a[z:]

if k <= len(am)*len(ap):
    ap = ap[::-1]
    a = -(10**18)-10
    b = 1000
    while True:
        if b-a <= 1:
            break
        m = (a+b)//2
        count = 0
        r = 0
        while r+1 < len(am) and ap[0]*am[r] <= m:
            r += 1
        for i in range(len(ap)):
            while r > 0 and ap[i]*am[r] > m:
                r -= 1
            if ap[i]*am[r] <= m:
                count += r+1
            else:
                count += r
        if count < k:
            a = m
        else:
            b = m
    print(b)
else:
    k -= len(am)*len(ap)
    am = list(map(lambda x: -x, am[::-1]))
    a = -1000
    b = 10**18+10
    while True:
        if b-a <= 1:
            break
        m = (a+b)//2
        count = 0
        r = len(ap)-1
        for i in range(len(ap)):
            while r > 0 and ap[i]*ap[r] > m:
                r -= 1
            if ap[i]*ap[r] <= m:
                if i <= r:
                    count -= 1
                count += r+1
            else:
                if i < r:
                    count -= 1
                count += r
        r = len(am)-1
        for i in range(len(am)):
            while r > 0 and am[i]*am[r] > m:
                r -= 1
            if am[i]*am[r] <= m:
                if i <= r:
                    count -= 1
                count += r+1
            else:
                if i < r:
                    count -= 1
                count += r
        if count//2 < k:
            a = m
        else:
            b = m
    print(b)

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

A = [A[i] for i in range(N) if A[i]!=0]
c = (N+len(A)-1)*(N-len(A))
N = len(A)
A.sort()
B = A[::-1]

def count(m):
    res = 0
    if m>=0:
        res += c
        j = N
        for i in range(N):
            if A[i]>0:
                break
            while j>0:
                if A[i]*A[j-1]<=m:
                    j -= 1
                else:
                    break
            res += N-j
        if A[i]>0:
            j = N-1
            for i in range(i,N):
                while j>=0:
                    if A[i]*A[j]>m:
                        j -= 1
                    else:
                        break
                res += j+1
    else:
        j = 0
        for i in range(N):
            if B[i]<0:
                break
            while j<N:
                if B[i]*B[j]>m:
                    j += 1
                else:
                    break
            res += N-j
        if B[i]<0:
            j = -1
            for i in range(i,N):
                while j<N-1:
                    if B[i]*B[j+1]<=m:
                        j += 1
                    else:
                        break
                res += j+1
    for i in range(N):
        if A[i]*A[i]<=m:
            res -= 1
    res //= 2
    return res

ng = -10**18
ok = 10**18
m = (ng+ok)//2
if N==0:
    ans = 0
else:
    for n in range(100):
        if count(m)<K:
            ng = m
        else:
            ok = m
        m = (ng+ok)//2
    ans = int(ok)
print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False


n,k = m()

a = l()

a.sort()

po = bs.bisect(a,0)

a,b = a[po:],a[po-1::-1]

n,m = len(a),len(b)

ok = 10 ** 18

bad = - ok

while ok - bad > 1:
    x = (ok + bad)//2
    s = 0
    if x >= 0:
        s += n*m
        t = 0
        i = n
        for y in a:
            while i and a[i-1] * y > x:
                i -= 1
            t+= i
            if y*y <= x:
                t-=1
        s += t // 2
        t = 0
        i = m
        for y in b:
            while i and b[i-1] * y> x:
                i -= 1
            t += i
            if y * y <= x:
                t -= 1
        s += t//2
    else:
        i = m
        for y in a:
            while i and b[i-1] * y <= x:
                i -= 1
            s += m-i
    if s >= k:
        ok = x
    else:
        bad = x
print(ok)

Solution (Python):
import bisect
import numpy as np

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




def simple():
    B = sorted([A[i] * A[j] for i in range(N) for j in range(i+1,N)])
    return B[K-1]

def solve():
    A.sort()

    iplus = bisect.bisect_right(A,0)
    izeros = bisect.bisect_left(A,0)

    pluss = np.array(A[iplus:]).astype(np.int64)
    zeros = A[izeros:iplus]
    minuss = np.array(A[:izeros]).astype(np.int64)

    nplus = len(pluss)
    nzero = len(zeros)
    nminus = len(minuss)

    npminus = nplus * nminus
    npzeros = nzero * (nplus + nminus) + nzero * (nzero-1)//2

    if npminus < K <= npminus + npzeros:
        return 0
    elif K <= npminus:
        mn = A[-1] * A[0] - 1
        mx = 0
        while mx-mn > 1:
            mid = (mn+mx)//2
            xs = -(-mid//minuss)
            cnt = nplus * nminus
            cnt -= np.sum(np.searchsorted(pluss,xs,side="left"))
            if cnt >= K:
                mx = mid
            else:
                mn = mid
        return mx
    else:
        nK = K - npminus - npzeros
        pluss2 = (-minuss)[::-1]
        mn = -1
        mx = max(A[0]**2, A[-1]**2)
        pluss_p2 = pluss**2
        pluss2_p2 = pluss2**2
        while mx-mn > 1:
            mid = (mn+mx)//2
            cnt = 0
            xs = mid//pluss
            cnt += np.sum(np.searchsorted(pluss,xs,side='right'))
            cnt -= np.count_nonzero(pluss_p2 <= mid)
            xs2 = mid//pluss2
            cnt += np.sum(np.searchsorted(pluss2,xs2,side='right'))
            cnt -= np.count_nonzero(pluss2_p2 <= mid)
            cnt = cnt //2
            
            if nK <= cnt:
                mx = mid
            else:
                mn = mid
        return mx

print(solve())

Solution (Python):
from sys import stdin
f_i = stdin

import numpy as np

N, K = map(int, f_i.readline().split())
A = np.array(f_i.read().split(), dtype=int)

A = np.sort(A)
zero_left = A.searchsorted(0, side='left')
zero_right = A.searchsorted(0, side='right')
zero_cnt = zero_right - zero_left
pos = A[zero_right:]
neg = A[:zero_left]

def f(x):
    cnt = 0
    
    if x >= 0:
        cnt += zero_cnt * 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 ** 2 <= x)
    return cnt // 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 bisect

N, K = map(int, input().split())
A = [int(x) for x in input().split()]


A_minus = sorted([a for a in A if a < 0])
A_plus = sorted([a for a in A if a > 0])
len_minus = len(A_minus)
len_plus = len(A_plus)
len_zero = N - len_minus - len_plus
pairs_num = (len_minus * len_plus,
             (len_minus + len_plus) * len_zero + len_zero * (len_zero - 1) // 2,
             len_minus * (len_minus - 1) // 2 + len_plus * (len_plus - 1) // 2)
assert sum(pairs_num) == N * (N - 1) // 2

if K <= pairs_num[0]:
    L = -10 ** 18
    R = -1
    while True:
        M = (L + R) // 2
        count = 0
        j = 0
        for i in range(len_plus):
            while j < len_minus and A_plus[i] * A_minus[j] <= M:
                j += 1
            count += j
        
        if count < K and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M
            
elif pairs_num[0] < K <= pairs_num[0] + pairs_num[1]:
    print(0)
    
else:
    K -= pairs_num[0] + pairs_num[1]
    A_minus = list(map(lambda x: -x, reversed(A_minus)))
    L = 1
    R = 10 ** 18
    while True:
        M = (L + R) // 2
        count = 0
        j = 0
        for i in range(len_minus-1, -1, -1):
            while j < len_minus and A_minus[i] * A_minus[j] <= M:
                j += 1
            count += max(0, j - i - 1)
        j = 0
        for i in range(len_plus-1, -1, -1):
            while j < len_plus and A_plus[i] * A_plus[j] <= M:
                j += 1
            count += max(0, j - i - 1)
            
        if count < K and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M

Solution (Python):
from bisect import bisect
def main():
  n,k,*a=map(int,open(0).read().split())
  a.sort()
  i=bisect(a,0)
  a,b=a[i:],a[i-1::-1]
  n,m=len(a),len(b)
  ok=10**18
  ng=-ok
  while ok-ng>1:
    x=(ok+ng)//2
    s=0
    if x>=0:
      s+=n*m
      t=0
      i=n
      for y in a:
        while i and a[i-1]*y>x:
          i-=1
        t+=i
        if y*y<=x:
          t-=1
      s+=t//2
      t=0
      i=m
      for y in b:
        while i and b[i-1]*y>x:
          i-=1
        t+=i
        if y*y<=x:
          t-=1
      s+=t//2
    else:
      i=m
      for y in a:
        while i and b[i-1]*y<=x:
          i-=1
        s+=m-i
    if s>=k:
      ok=x
    else:
      ng=x
  print(ok)

main()

Solution (Python):
import numpy as np


def partsolve(A, x, positive, zero, negative):
    """
    :param A:
    :param x:
    :return: Aの積のペアの中で、x以下となるペアの個数
    """
    count = 0
    if x >= 0:
        count = len(zero) * len(A)
    P = x // positive
    Pc = np.searchsorted(A, P, side='right')
    count += Pc.sum()

    N = (-x-1) // -negative
    Nc = np.searchsorted(A, N, side='right')
    Nc = len(A) - Nc
    count += Nc.sum()

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

def solve(N, K, As):
    A = np.array(sorted(As), np.int64)
    positive = A[A > 0]
    zero = A[A == 0]
    negative = A[A < 0]

    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(A, mid, positive, zero, negative)
        if c < K:
            left = mid
        else:
            right = mid
    return right


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Solution (Python):
import numpy as np


def partsolve(A, x, positive, zero, negative):
    """
    :param A:
    :param x:
    :return: Aの積のペアの中で、x以下となるペアの個数
    """
    count = 0
    if x >= 0:
        count = len(zero) * len(A)
    P = x // positive
    Pc = np.searchsorted(A, P, side='right')
    count += Pc.sum()

    N = (-x-1) // -negative
    Nc = np.searchsorted(A, N, side='right')
    Nc = len(A) - Nc
    count += Nc.sum()

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

def solve(N, K, As):
    A = np.array(sorted(As), np.int64)
    positive = A[A > 0]
    zero = A[A == 0]
    negative = A[A < 0]

    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(A, mid, positive, zero, negative)
        if c < K:
            left = mid
        else:
            right = mid
    return right



if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Solution (Python):
import numpy as np


def partsolve(A, x, positive, zero, negative):
    """
    :param A:
    :param x:
    :return: Aの積のペアの中で、x以下となるペアの個数
    """
    count = 0
    if x >= 0:
        count = len(zero) * len(A)
    P = x // positive
    Pc = np.searchsorted(A, P, side='right')
    count += Pc.sum()

    N = (-x-1) // -negative
    Nc = np.searchsorted(A, N, side='right')
    Nc = len(A) - Nc
    count += Nc.sum()

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

def solve(N, K, As):
    A = np.array(sorted(As), np.int64)
    positive = A[A > 0]
    zero = A[A == 0]
    negative = A[A < 0]

    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(A, mid, positive, zero, negative)
        if c < K:
            left = mid
        else:
            right = mid
    return right


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Solution (Python):


import numpy as np

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

n_zero = len(A[A == 0])
A_posi = A[A > 0]
A_nega = A[A < 0]

def n_pairs_less_than_or_equal_to_border(product_border):
    n_pairs = -np.sum(A*A <= product_border) 
    n_pairs += n_zero * N * (product_border >= 0)

    n_pairs += np.searchsorted(A, product_border//A_posi, side="right").sum()
    n_pairs += (N - np.searchsorted(A, -(-product_border//A_nega), side="left")).sum()

    
    
    
    
    
    

    n_pairs //= 2
    return n_pairs


lower = -(10**18)
upper = 10**18

while lower <= upper:
    x = (lower + upper) // 2
    if n_pairs_less_than_or_equal_to_border(x) >= K:
        ans = x
        upper = x - 1
    else:
        lower = x + 1

print(ans)

Solution (Python):
def main():
    import numpy as np
    from bisect import bisect_left, bisect_right

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

    A.sort()

    n = bisect_left(A, 0)
    p = bisect_right(A, 0)

    Negative = np.array(A[:n], dtype = np.int64)
    Positive = np.array(A[p:], dtype = np.int64)

    Number_Negative = len(Negative) * len(Positive)
    Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
    Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

    
    
    
    
    

    def Ncount(x): 
        tmp = 0
        for a in Negative:
            tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
        
        return tmp

    def Ncount1(x):
        tmp = (len(Positive) - np.searchsorted(Positive, (-x - 1) // (-Negative), side = 'right')).sum() 
        return tmp 

    def Pcount(x): 
        tmp = 0
        for index, a in enumerate(Positive):
            tmp += bisect_right(Positive[index + 1:], x // a)
        for index, b in enumerate(Negative):
            tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
            
        
        return tmp

    def Pcount1(x):
        tmp = 0
        tmp += np.searchsorted(Positive, x // Positive, side = 'right').sum()
        tmp += (len(Negative) - np.searchsorted(Negative, (-x - 1) // (-Negative), side = 'rigth')).sum()
        tmp -= np.count_nonzero(Positive * Positive <= x)
        tmp -= np.count_nonzero(Negative * Negative <= x)
        return tmp // 2

    if Number_Negative >= K:
        
        l = -10 ** 18
        r = 0
        while r - l > 1:
            mid = (l + r) // 2
            if K <= Ncount1(mid):
                r = mid
            else:
                l = mid
        print (r)
        exit()
            

    elif Number_Negative < K <= Number_Negative + Number_Zero:
        print (0)
        exit()

    else:
        
        l = 0
        r = 10 ** 18
        K -= (Number_Negative + Number_Zero)
        while r - l > 1:
            mid = (l + r) // 2
            if K <= Pcount1(mid):
                r = mid
            else:
                l = mid

        print (r)
        

    
    

if __name__ == '__main__':
    main()

Solution (Python):

import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(map(int, args[1].split())))
    N = A[A < 0]
    P = A[0 < A]

    count = 0
    left, right = -10**18, 10**18
    while left+1 < right:
        x = (left+right)//2
        count = (n-np.searchsorted(A, -(-x//N), side='left')).sum()
        count += n * (A == 0).sum() if 0 <= x else 0
        count += np.searchsorted(A, x//P, side='right').sum()
        count -= (A*A <= x).sum()
        count //= 2

        if count < k:
            left = x
        else:
            right = x

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):

import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(map(int, args[1].split())))
    N = A[A < 0]
    P = A[0 < A]

    count = 0
    left, right = -10**18, 10**18
    while left+1 < right:
        x = (left+right)//2
        count = 0

        if k <= len(N)*len(P):
            count += (len(P)-np.searchsorted(P, -(-x//N), side='left')).sum()

        elif (n*(n-1) - len(N)*(len(N)-1) - len(P)*(len(P)-1))//2 < k:
            for D in (-(N[::-1]), P):
                count += np.searchsorted(D, x//D, side='right').sum()
                count -= len(D[D*D <= x])
            count //= 2
            count += (n*(n-1) - len(N)*(len(N)-1) - len(P)*(len(P)-1))//2

        else:
            right = 0
            break

        if count < k:
            left = x
        else:
            right = x

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
import numpy as np

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

a.sort()
pos = a[a>0]
zero = a[a==0]
neg = a[a<0]
negpos = (neg*(-1))[::-1]

lenn = len(neg)
lenz = len(zero)
lenp = len(pos)

nnres = lenn * lenp
nzres = int(lenz*(lenn+lenp)+lenz*(lenz-1)/2)
npres = int(lenn*(lenn-1)/2 + lenp*(lenp-1)/2)

if k<=nnres:
    def count_nnres(x):
        cnt = np.searchsorted(neg,x//pos,side='right').sum()
        return int(cnt)
    left = -10**18
    right = -1
    while left+1<right:
        mid = (left+right)//2
        nebefore = count_nnres(mid)
        if nebefore >= k:
            right = mid
        elif nebefore < k:
            left = mid
    print(right)
    
elif nnres<k<=nnres+nzres:
    print(0)
    
elif nnres+nzres<k:
    def count_npres(x):
        cnt = 0
        cnt += int(np.searchsorted(pos,x//pos,side='right').sum() - ((x//pos)>=pos).sum())//2
        cnt += int(np.searchsorted(negpos,x//negpos,side='right').sum() - ((x//negpos)>=negpos).sum())//2
        return cnt
    k -= nnres+nzres
    left = 1
    right = 10**18
    while left+1<right:
        mid = (left+right)//2
        nebefore = count_npres(mid)
        if nebefore >= k:
            right = mid
        elif nebefore < k:
            left = mid
    print(right)

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 = 0
    c = x // pos
    count += np.searchsorted(a, c, side='right').sum()
    count += N*len(zero) if x >= 0 else 0
    c = -(-x // neg)
    count += (N - np.searchsorted(a, c, side='left')).sum()
    count -= a[a*a <= x].size
    count //= 2
    return count

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

Solution (Python):
import numpy as np

def p(*args, **kargs):
    if DBG:print(*args, **kargs)
read = input 
rn = lambda :list(map(int, read().split()))
debug = False
def sol(A):
    A = np.array(A, np.int64)
    A = np.sort(A)
    _A = np.sort(-A)

    pos = A[A>0]
    neg = A[A<0]
    zero = A[A==0]
    def searchsorted(*args, **kargs):
        ret = np.searchsorted(*args, **kargs)



        return ret

    
    
    def  f(x):
        ret = 0
        if x >= 0:
            ret += len(zero) * len(A)
            ret += searchsorted(A, x//pos, side="right").sum()
            ret += searchsorted(_A, x//(-neg), side="right").sum()
        else :
            ret += searchsorted(A, x//pos,  side="right").sum()
            ret += searchsorted(_A, x//(-neg),  side="right").sum()

        ret -= np.count_nonzero(A*A<=x)
        assert ret % 2 == 0
        return ret // 2
        if debug: print(pos, neg, zero)
    return f

f = sol([-4, -2, 3, 3 ])
assert f(-12) == 2
assert f(-6) == 4 

def bs(A, index):
    A = np.array(A, np.int64)
    f = sol(A)
    max_ele = max(abs(A))

    right = max_ele * max_ele + 1
    left  = - right
    while left + 1 < right:
        middle = (left + right)//2
        m_index = f(middle)
        if debug : print(middle, m_index, left, right, sep="\t")
        if index <= m_index:
            right = middle
        else :
            left = middle
    return right

n,index = rn()
A = np.array(read().split(), np.int64)
print(bs(A, index))

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

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

def f(x):
  tmp = 0
  if x>=0:
    tmp += zero*N
  tmp += np.searchsorted(L, x//pos, side='right').sum()
  tmp += (N - np.searchsorted(L, -(-x//neg), side='left')).sum()
  tmp -= np.count_nonzero(L*L<=x)
  return tmp//2

l, r = -10**18, 10**18
while l<r-1:
  m = (l+r)//2
  count = f(m)
  if count >= K:
    r = m
  else:
    l = m

print(r)

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)