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



Sample input:
4 3
3 3 -4 -2


Sample output:
-6

Submission status: Runtime Error

Solution code:
import bisect
import sys
input = sys.stdin.readline
n,k = map(int, input().split())
a= list(map(int, input().split()))
a.sort()
r=10**18+1
l=-10**18-1
while r-l>1:
    m = (r + l) // 2
    count=0
    for i in range(n):
        x = m // a[i]
        y = bisect.bisect_right(a, x)
        y1 = n - y
        if a[i]>0:
            if y<=i:
                count+=y
            else:
                count+=y-1
        elif a[i]<0:
            if y>i:
                count+=y1
            else:
                count+=y1-1
        else:
            if m>=0:
                count+=n-1
    if count//2>=k:
        r=m
    else:
        l=m
print(r)

Submission status: Runtime Error

Solution code:
def main():
  n, k = map(int, input().split(' '))
  A = list(map(int, input().split(' ')))
  A_minus_ls = []
  A_zero_ls = []
  A_plus_ls = []
  for a in A:
    if a < 0:
      A_minus_ls.append(a)
    elif a == 0:
      A_zero_ls.append(a)
    else:
      A_plus_ls.append(a)
  A_minus_num = len(A_minus_ls)
  A_zero_num = len(A_zero_ls)
  A_plus_num = len(A_plus_ls)
  
  product_minus_num = A_minus_num * A_plus_num
  product_zero_num = (A_minus_num + A_plus_num) * A_zero_num
  product_plus_num = n * (n-1) / 2 - product_minus_num - product_zero_num

  
  def calc_products_ls(ls1, ls2):
    products_ls = []
    for itm1 in ls1:
      for itm2 in ls2:
        products_ls.append(itm1 * itm2)
    return products_ls
  
  def calc_comb_products_ls(ls):
    comb_products_ls = []
    for i in range(len(ls)):
      for j in range(i, len(ls)):
        if i != j:
          comb_products_ls.append(ls[i] * ls[j])
    return comb_products_ls
  
  
  if k <= product_minus_num:
    ans_ls = sorted(calc_products_ls(A_plus_ls, A_minus_ls))
    print(ans_ls[k-1])    
  elif k <= product_minus_num + product_zero_num:
    print(0)
  else:
    plus_comb_list = calc_comb_products_ls(A_plus_ls)
    minus_comb_list = calc_comb_products_ls(A_minus_ls)
    plus_comb_list.extend(minus_comb_list)
    plus_comb_list = sorted(plus_comb_list)
    print(plus_comb_list[int(k - n*(n-1)/2)-1])

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
#pairs
listforcheck = []
checknumber = 0
n,k = list(map(int,input().split()))
nums = list(map(int,input().split()))
for checknum in range(n-1):
    for checknum2 in range (checknum,n-1):
        checknumber = nums[checknum]*nums[checknum2+1]
        listforcheck.append(checknumber)
listforcheck.sort(reverse = True)
print(listforcheck[k])

Submission status: Runtime Error

Solution code:
def bin_search(array, num):
    if array[0] > num: return 0
    if array[-1] < num: return len(array)
    mx = len(array) - 1
    mn = 0
    while mx >= mn :
        median = mn + (mx - mn)//2 
        target = array[median]
        if target == num:
            return median + 1
        elif target > num:
            mx = median - 1
        else:
            mn = median + 1

    return median + 1

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

mn = -10 ** 18 - 1
mx = 10 ** 18 + 1

while mx >= mn:
    m = mn + (mx - mn)//2

    score = 0
    for a in arr:
        if a > 0:
            thres = m//a
            score += bin_search(arr, thres)
        
        elif a < 0:
            thres = m//a
            score += n - bin_search(arr, thres-1)
        
        else:
            if m >= 0:
                score += n

        if a <= m: score -= 1
    
    assert score % 2 == 0

    score /= 2    
    under = score
    if under < k:
        mn = m
    
    else:
        mx = m

print(m)

Submission status: Runtime Error

Solution code:
def d_pairs():
    # 参考: https://maspypy.com/atcoder-参加感想-2019-02-16abc-155
    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

        # a (数列の要素) == 0 かつ c >= 0 なら、a * x <= c となる x は数列の任意の要素
        if c >= 0:
            count_pair += len(zero) * N
        # a > 0 の場合
        count_pair += np.searchsorted(A, c // positive, side='right').sum()
        # a < 0 の場合 (全体から引くようにすると、見通しがよい)
        count_pair += (N - np.searchsorted(A, (-c - 1) // (-negative), side='right')).sum()
        # 添字の順序に制約があることを反映する
        count_pair -= np.count_nonzero(A * A <= c)  # 「添字が同じ要素を 2 度選んだ場合」を引く
        return count_pair // 2

    # 数列から要素を 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 f(x)

print(d_pairs())

Submission status: Runtime Error

Solution code:
def bin_search(array, num):
    if array[0] > num: return 0
    if array[-1] < num: return len(array)
    mx = len(array) - 1
    mn = 0
    while mx >= mn :
        median = mn + (mx - mn)//2 
        target = array[median]
        if target == num:
            return median + 1
        elif target > num:
            mx = median - 1
        else:
            mn = median + 1

    return median + 1

n, k = map(int, input().split())
arr = list(map(int, input().split()))
# arr = list(map(int, '5 4 3 2 -1 0 0 0 0 0'.split()))
arr.sort()

n_int = 0
n_range = [None, None]
z_int = 0
zero_range = [None, None]
p_int = 0
p_range = [None, None]

for idx, i in enumerate(arr):
    if i < 0:
        n_int += 1
        if n_range[0] == None: n_range[0] = idx
        n_range[1] = idx + 1
    elif i == 0:
        z_int += 1
        if zero_range[0] == None: zero_range[0] = idx
        zero_range[1] = idx + 1
    
    else:
        p_int += 1
        if p_range[0] == None: p_range[0] = idx
        p_range[1] = idx + 1

negative = n_int * p_int
zero = z_int * (n_int + p_int) + (z_int*(z_int-1)//2)
positive = (p_int*(p_int-1)//2) + (n_int*(n_int-1)//2)
# print(negative, zero, positive)

if k > zero + negative:
    n_list = arr[n_range[0]: n_range[1]]
    p_list = arr[p_range[0]: p_range[1]]

    goal = k - zero - negative

    if len(n_list) < 2:
        mn = p_list[0] * p_list[1]
        mx = p_list[-1] * p_list[-2]
    
    elif len(p_list) <2:
        mn = n_list[-1] * n_list[-2]
        mx = n_list[0] * n_list[1]
     
    else:
        mn = min (n_list[-1]*n_list[-2], p_list[0]*p_list[1])
        mx = max (n_list[0]*n_list[1], p_list[-1]*p_list[-2])

    while mx >= mn:
        m = mn + (mx - mn)//2
        under = 0
        p_under = 0
        for a in p_list:
            thres = m//a
            score = bin_search(p_list, thres)
            if a*a <= m:
                score -= 1
            p_under += score
        p_under /= 2
        under += p_under
        
        n_under = 0
        for a in n_list:
            thres = m//a
            score = n_int - bin_search(n_list, thres - 1)
            if a*a <= m:
                score -= 1
            n_under += score
        n_under /= 2
        under += n_under

        if under >= goal:
            mx = m - 1
        
        else:
            mn = m + 1
    
    print(m)

Submission status: Runtime Error

Solution code:
def bin_search(array, num):
    if array[0] > num: return 0
    if array[-1] < num: return len(array)
    mx = len(array) - 1
    mn = 0
    while mx >= mn :
        median = mn + (mx - mn)//2 
        target = array[median]
        if target == num:
            return median + 1
        elif target > num:
            mx = median - 1
        else:
            mn = median + 1

    return median + 1

n, k = map(int, input().split())
arr = map(int, input().split())
# arr = list(map(int, '5 4 3 2 -1 0 0 0 0 0'.split()))
arr.sort()

n_int = 0
n_range = [None, None]
z_int = 0
zero_range = [None, None]
p_int = 0
p_range = [None, None]

for idx, i in enumerate(arr):
    if i < 0:
        n_int += 1
        if n_range[0] == None: n_range[0] = idx
        n_range[1] = idx + 1
    elif i == 0:
        z_int += 1
        if zero_range[0] == None: zero_range[0] = idx
        zero_range[1] = idx + 1
    
    else:
        p_int += 1
        if p_range[0] == None: p_range[0] = idx
        p_range[1] = idx + 1

negative = n_int * p_int
zero = z_int * (n_int + p_int) + (z_int*(z_int-1)//2)
positive = (p_int*(p_int-1)//2) + (n_int*(n_int-1)//2)
# print(negative, zero, positive)

if k > zero + negative:
    n_list = arr[n_range[0]: n_range[1]]
    p_list = arr[p_range[0]: p_range[1]]

    goal = k - zero - negative

    if len(n_list) < 2:
        mn = p_list[0] * p_list[1]
        mx = p_list[-1] * p_list[-2]
    
    elif len(p_list) <2:
        mn = n_list[-1] * n_list[-2]
        mx = n_list[0] * n_list[1]
     
    else:
        mn = min (n_list[-1]*n_list[-2], p_list[0]*p_list[1])
        mx = max (n_list[0]*n_list[1], p_list[-1]*p_list[-2])

    while mx >= mn:
        m = mn + (mx - mn)//2
        under = 0
        p_under = 0
        for a in p_list:
            thres = m//a
            score = bin_search(p_list, thres)
            if a*a <= m:
                score -= 1
            p_under += score
        p_under /= 2
        under += p_under
        
        n_under = 0
        for a in n_list:
            thres = m//a
            score = n_int - bin_search(n_list, thres - 1)
            if a*a <= m:
                score -= 1
            n_under += score
        n_under /= 2
        under += n_under

        if under >= goal:
            mx = m - 1
        
        else:
            mn = m + 1
    
    print(m)

Submission status: Runtime Error

Solution code:
data1=[int(x) for x in input().split()]
data2=[int(x) for x in input().split()]
hu=[0,0,0]
plus=[]
minus=[]
zero=[]
for x in data2:
  if x>0:
    hu[0]=hu[0]+1
    plus.append(x)
  elif x<0:
    hu[2]=hu[2]+1
    minus.append(x)
  else:
    hu[1]=hu[1]+1
    zero.append(0)
ans=[hu[0]*(hu[0]-1)/2+hu[2]*(hu[2]-1)/2,(hu[0]+hu[2])*hu[1],hu[0]*hu[2]]
check=[]
if ans[2]>data1[1]:
  for x in plus:
    for y in minus:
      check.append(x*y)
  check.sort()
  print(check[data1[1]])
elif ans[2]+ans[1]>data1[1]:
  print(0)
else:
  for x in [plus,minus]:
    for i in range(len(x)):
      for j in range(i,len(x)):
        check.append(x[j]*x[i])
  check.sort()
  print(check[data1[1]-ans[2]-ans[1]])

Submission status: Runtime Error

Solution code:
import numpy as np

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

b = np.tile(a,N).reshape(N,-1).astype('float128')
c = np.tril(b * b.T, k=-1)
d = c + np.tri(N).T * np.max(c)

print(int(sorted(d.flatten())[K-1]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

b = np.tile(a,N).reshape(N,-1).astype('float128')
c = np.tril(b * b.T, k=-1)
d = c + np.tri(N).T * np.max(c)

print(d)
print(int(sorted(d.flatten())[K-1]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

b = np.tile(a,N).reshape(N,-1)
c = b * b.T * np.tri(N, k=-1)
d = c + np.tri(N).T * np.max(c)

print(int(sorted(d.flatten())[K-1]))

Submission status: Runtime Error

Solution code:
def fec(n):
  if n <= 1:
    return 1
  return n * fec(n-1)
def c(n, m):
  return int(fec(n) / fec(m) / fec(n - m))

N, K = [int(x) for x in input().split(' ')]
neg, zer, pos = [], [], []
for a in input().split(' '):
  A = int(a)
  if A < 0:
    neg.append(A)
  elif A == 0:
    zer.append(A)
  else:
    pos.append(A)
n_pos = c(len(neg), 2) + c(len(pos), 2)
n_zer = len(zer) * (len(neg) + len(pos)) + c(len(zer), 2)
n_neg = len(neg) * len(pos)
if n_neg >= K:
  print(sorted([i * j for i in neg for j in pos])[K-1])
else:
  K -= n_neg
  if n_zer >= K:
    print(0)
  else:
    K -= n_zer
    print(sorted([
      pos[i] * pos[j]
      for i in range(len(pos))
      for j in range(i+1, len(pos))
    ] + [
      neg[i] * neg[j]
      for i in range(len(neg))
      for j in range(i+1, len(neg))
    ])[K-1])

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
lst=[]

la = len(a)
a=[i for i in a if i != 0]
p=[i for i in a if i > 0]
m=[i for i in a if i < 0]

lp=len(p)
lm=len(m)
lz=la-len(a)

ps=int(lp*(lp-1)/2+lm*(lm-1)/2)
ms=int(lm*lp)
zs=int(lz*(lp+lm)+lz*(lz-1)/2)

if k<ms:
  for i in range(lm):
    for j in range(lp):
      lst.append(m[i]*p[j])
  lst.sort()
  print(lst[k-1])
elif k>=ms+zs:
  for i in range(lp):
    for j in range(i+1,lp):
      lst.append(p[i]*p[j])
  for i in range(lm):
    for j in range(i+1,lm):
      lst.append(m[i]*m[j])
  lst.sort()
  print(lst[k-ms-zs-1])
else:
  print(0)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))

d_plus = sorted([i for i in a if i>=0])
d_minus = sorted([i for i in a if i<0])

d = []
if len(d_plus)*len(d_minus) <= K:
  for i in d_plus:
    for j in d_minus:
      d.append(i*j)
  print(sorted(d)[K-1])
else:
  for i in range(len(d_plus)):
    for j in range(len(d_plus)):
      if i==j:
        continue
      else:
        d.append(d_plus[i]*d_plus[j])
  for i in range(len(d_minus)):
    for j in range(len(d_minus)):
      if i==j:
        continue
      else:
        d.append(d_minus[i]*d_minus[j])
  print(sorted(d)[K-1-len(d_plus)*len(d_minus)])

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split())

d = []
for i in range(N):
  for j in range(N):
    if j == i:
      continue
    else:
      d.append(a[i]*a[j])
      
print(sorted(d)[K-1])

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int),input().split())

d = []
for i in range(N):
  for j in range(N):
    if j == i:
      continue
    else:
      d.append(a[i]*a[j])
      
print(sorted(d)[K-1])

Submission status: Runtime Error

Solution code:
import bisect
N,K = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
An.sort()
idx = bisect.bisect_left(An,0)
positive = An[idx:] 
negative = An[:idx]


max_candidate = 101 #10**18 + 1
min_candidate = -100 #-1 * (10**18) - 1

while True:
    middle = (max_candidate + min_candidate)//2
    if 0 <= middle:
        current_length = len(positive) * len(positive)
        candidate_list = []
        #正 * 正
        for i,n1 in enumerate(positive):
            n2_list = positive[i+1:]
            n2_candidate = middle / n1
            n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            current_length += n2_idx
            if 0 < n2_idx:
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
        #負 * 負
        for i,n1 in enumerate(negative):
            n2_list = negative[i+1:]
            n2_candidate = middle / n1
            n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            if n2_idx < len(n2_list):
                current_length += len(n2_list) - n2_idx - 1
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
    else:
        current_length = 0
        candidate_list = []
        #正 * 負
        for i,n1 in enumerate(negative): 
            n2_list = positive
            n2_candidate = middle / n1
            n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            #current_length += n2_idx
            if n2_idx < len(n2_list):
                current_length += len(n2_list) - n2_idx
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
    if min_candidate+1 == max_candidate:
        break
    if current_length == K:
        print(max(candidate_list))
        exit(0)
    elif current_length < K:
        min_candidate = middle
    else:
        max_candidate = middle
print(max(candidate_list))

Submission status: Runtime Error

Solution code:
nk = input().split() #nk input
n = int(nk[0])
k = int(nk[1])
num = input().split() #number input
list = []
for i in range(0,n-1):
  for j in range(i+1,n):
    list.append(i*j)
print((list.sort())[k-1])

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
inList = list(map(int, input().split()))

inList.sort()

if inList[0] * inList[N-1] <= 0:
  l_ba = inList[0] * inList[N-1]
else:
  l_ba = inList[0] * inList[1]

r_ba = max(inList[0] * inList[1], inList[N-2] * inList[N-1])

if l_ba == r_ba:
  print(l_ba)
else:
  
  l_ba = l_ba - 1
  r_ba = r_ba + 1
  l_first = l_ba
  
  x = int(0.5 * (l_ba + r_ba))
  
  for time in range(int(0.5 * N * (N-1))):
    count = 0
    Ans = l_first
    
    for indx in range(N):
      if inList[indx] <= 0:
        for mulIndx in range(indx, -1, -1):
          if inList[indx] * inList[mulIndx] <= x:
            if indx != mulIndx:
              count += 1
              Ans = max(Ans, inList[indx] * inList[mulIndx])
          else:
            break
      elif inList[indx] > 0:
        for mulIndx in range(indx):
          if inList[indx] * inList[mulIndx] <= x:
            if indx != mulIndx:
              count += 1
              Ans = max(Ans, inList[indx] * inList[mulIndx])
          else:
            break
    
    count = count
#    print(l_ba, x, r_ba, count)
    
    if count == K:
      break
    elif count < K:
      l_ba = x
      x = int(0.5 * (l_ba + r_ba))
    else:
      r_ba = x
      x = int(0.5 * (l_ba + r_ba))
    
    if (r_ba - l_ba) == 1:
      x = r_ba
      l_ba = r_ba
      break
    elif l_ba == r_ba:
      break

print(Ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
inList = list(map(int, input().split()))

inList.sort()

if inList[0] * inList[N-1] <= 0:
  l_ba = inList[0] * inList[N-1]
else:
  l_ba = inList[0] * inList[1]

r_ba = max(inList[0] * inList[1], inList[N-2] * inList[N-1])

if l_ba == r_ba:
  print(l_ba)
else:
  
  l_ba = l_ba - 1
  r_ba = r_ba + 1
  l_first = l_ba
  
  x = int(0.5 * (l_ba + r_ba))
  
  for time in range(int(0.5 * N * (N-1))):
    count = 0
    Ans = l_first
    
    for indx in range(N):
      if inList[indx] <= 0:
        for mulIndx in range(indx, -1, -1):
          if inList[indx] * inList[mulIndx] <= x:
            if indx != mulIndx:
              count += 1
              Ans = max(Ans, inList[indx] * inList[mulIndx])
          else:
            break
      elif inList[indx] > 0:
        for mulIndx in range(indx):
          if inList[indx] * inList[mulIndx] <= x:
            if indx != mulIndx:
              count += 1
              Ans = max(Ans, inList[indx] * inList[mulIndx])
          else:
            break
    
    count = count
#    print(l_ba, x, r_ba, count)
    
    if count == K:
      break
    elif count < K:
      l_ba = x
    else:
      r_ba = x
    
    x = int(0.5 * (l_ba + r_ba))

print(Ans)

Submission status: Runtime Error

Solution code:
import bisect
def judge(k, A):
    if len(A) == 1:
        return 0
    t = 0
    for i, v in enumerate(A):
        j = bisect.bisect_left(A[i+1:], k/v)
        t += j
    return t

def judge2(k, A, B):
    t = 0
    for i in A:
        j = bisect.bisect_left(B, k/i)
        t += j
    return t
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    mi = bisect.bisect_left(A, 0)
    zi = bisect.bisect_right(A, 0)
    ml = A[:mi]
    zl = A[mi:zi]
    pl = A[zi:]
    pn = len(ml) * (len(ml)-1) // 2 + len(pl) * (len(pl)-1)//2
    zn = len(zl) * (len(zl) - 1) // 2 + len(zl) * (len(ml) + len(pl))
    mn = len(ml) * len(pl)
    if mn < K and mn + zn >= K:
        return 0
    if mn > K:
        t = 0
        b = max(pl) * min(ml)
        while t - b > 1:
            m = (t + b)//2
            i = judge2(m, pl, ml)
            if i >= K:
                t = m
            else:
                b = m
        return b
    K -= (mn + zn)
    t = max(max(pl) ** 2, min(ml) ** 2) 
    b = 0
    ml = [-i for i in ml]
    ml.sort()
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, pl)
        j = judge(m, ml)
        if i + j >= K:
            t = m
        else:
            b = m
    return b
print(main())

Submission status: Runtime Error

Solution code:
import numpy as np
# from numba import njit

# @njit('(i8,i8[:],i8[:])')
def solve1(m, minus, plus):
    minus = np.sort(minus)
    plus = np.sort(plus)[::-1]
    # ２分探索
    lo = minus[0] * plus[0]
    hi = minus[-1] * plus[-1]
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0
        j = plus.shape[0] - 1
        for i in range(plus.shape[0]):
            while j >= 0 and minus[j] * plus[i] > mid:
                j -= 1
            if j > -1:
                num += j + 1
            else:
                break
        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j = minus.shape[0] - 1
    res = minus[0] * plus[0]
    for i in range(plus.shape[0]):
        while j >= 0 and minus[j] * plus[i] > hi:
            j -= 1
        if j > -1:
            res = max(res, minus[j] * plus[i])
        else:
            break
    return res

# @njit('(i8,i8[:],i8[:])')
def solve2(m, minus, plus):
    minus = np.sort(minus)[::-1]
    plus = np.sort(plus)
    # ２分探索
    lo = 0
    hi = plus[-1] * plus[-2] if len(plus) > 1 else 0
    hi += minus[-1] * minus[-2] if len(minus) > 1 else 0
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0

        j1 = plus.shape[0] - 1
        if j1 > 0:
            for i in range(plus.shape[0]):
                s = mid // plus[i]
                while j1 >= 0 and plus[j1] > s:
                    j1 -= 1
                if j1 > i:
                    num += j1 - i

        j2 = minus.shape[0] - 1
        if j2 > 0:
            for i in range(minus.shape[0]):
                s = mid // -minus[i]
                while j2 >= 0 and minus[j2] < -s:
                    j2 -= 1
                if j2 > i:
                    num += j2 - i

        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j1 = plus.shape[0] - 1
    j2 = minus.shape[0] - 1
    res = 0
    if j1 > 0:
        for i in range(plus.shape[0]):
            while j1 >= 0 and plus[j1] * plus[i] > hi:
                j1 -= 1
            if j1 > i:
                res = max(res, plus[j1] * plus[i])
            else:
                break
    if j2 > 0:
        for i in range(minus.shape[0]):
            while j2 >= 0 and minus[j2] * minus[i] > hi:
                j2 -= 1
            if j2 > i:
                res = max(res, minus[j2] * minus[i])
            else:
                break
    return res


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

    n_zero = len(zero)
    p_minus = len(minus) * len(plus)
    p_zero = n_zero * (len(minus) + len(plus)) + n_zero * (n_zero - 1) // 2

    if K <= p_minus:
        ans = solve1(K, minus, plus)
        print(ans)
    elif K <= p_minus + p_zero:
        print(0)
    else:
        ans = solve2(K - p_minus - p_zero, minus, plus)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

def solve1(m, minus, plus):
    minus = np.sort(minus)
    plus = np.sort(plus)[::-1]
    # ２分探索
    lo = minus[0] * plus[0]
    hi = minus[-1] * plus[-1]
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0
        j = minus.shape[0] - 1
        for i in range(plus.shape[0]):
            while j >= 0 and minus[j] * plus[i] > mid:
                j -= 1
            if j > -1:
                num += j + 1
            else:
                break
        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j = minus.shape[0] - 1
    res = minus[0] * plus[0]
    for i in range(plus.shape[0]):
        while j >= 0 and minus[j] * plus[i] > hi:
            j -= 1
        if j > -1:
            res = max(res, minus[j] * plus[i])
        else:
            break
    return res

def solve2(m, minus, plus):
    minus = np.sort(minus)[::-1]
    plus = np.sort(plus)
    # ２分探索
    lo = 0
    hi = plus[-1] * plus[-2] if len(plus) > 1 else 0
    hi += minus[-1] * minus[-2] if len(minus) > 1 else 0
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0

        j1 = plus.shape[0] - 1
        if j1 > 0:
            for i in range(plus.shape[0]):
                while j1 >= 0 and plus[j1] * plus[i] > mid:
                    j1 -= 1
                if j1 > i:
                    num += j1 - i

        j2 = minus.shape[0] - 1
        if j2 > 0:
            for i in range(minus.shape[0]):
                while minus[j2] * minus[i] > mid:
                    j2 -= 1
                if j2 > i:
                    num += j2 - i

        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j1 = plus.shape[0] - 1
    j2 = minus.shape[0] - 1
    res = 0
    if j1 > 0:
        for i in range(plus.shape[0]):
            while j1 >= 0 and plus[j1] * plus[i] > hi:
                j1 -= 1
            if j1 > i:
                res = max(res, plus[j1] * plus[i])
            else:
                break
    if j2 > 0:
        for i in range(minus.shape[0]):
            while j2 >= 0 and minus[j2] * minus[i] > hi:
                j2 -= 1
            if j2 > i:
                res = max(res, minus[j2] * minus[i])
            else:
                break
    return res


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

    n_minus = len(minus)
    n_zero = len(zero)
    n_plus = len(plus)

    p_minus = n_minus * n_plus
    p_zero = n_zero * (n_minus + n_plus) + n_zero * (n_zero - 1) // 2

    if K <= p_minus:
        ans = solve1(K, minus, plus)
        print(ans)
    elif K <= p_minus + p_zero:
        print(0)
    else:
        ans = solve2(K - p_minus - p_zero, minus, plus)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

def solve1(m, minus, plus):
    minus = np.sort(minus)
    plus = np.sort(plus)[::-1]
    # ２分探索
    lo = minus[0] * plus[0]
    hi = minus[-1] * plus[-1]
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0
        j = minus.shape[0] - 1
        for i in range(plus.shape[0]):
            while j >= 0 and minus[j] * plus[i] > mid:
                j -= 1
            if j > -1:
                num += j + 1
            else:
                break
        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j = minus.shape[0] - 1
    res = 0
    for i in range(plus.shape[0]):
        while j >= 0 and minus[j] * plus[i] > hi:
            j -= 1
        if j > -1:
            res = min(res, minus[j] * plus[i])
    return res

def solve2(m, minus, plus):
    minus = np.sort(minus)[::-1]
    plus = np.sort(plus)
    # ２分探索
    lo = 0
    hi = plus[-1] * plus[-2] if len(plus) > 1 else 0
    hi += minus[-1] * minus[-2] if len(minus) > 1 else 0
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0

        j1 = plus.shape[0] - 1
        if j1 > 0:
            for i in range(plus.shape[0]):
                while j1 >= 0 and plus[j1] * plus[i] > mid:
                    j1 -= 1
                if j1 > i:
                    num += j1 - i

        j2 = minus.shape[0] - 1
        if j2 > 0:
            for i in range(minus.shape[0]):
                while minus[j2] * minus[i] > mid:
                    j2 -= 1
                if j2 > i:
                    num += j2 - i

        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j1 = plus.shape[0] - 1
    j2 = minus.shape[0] - 1
    res = 0
    if j1 > 0:
        for i in range(plus.shape[0]):
            while j1 >= 0 and plus[j1] * plus[i] > hi:
                j1 -= 1
            if j1 > i:
                res = max(res, plus[j1] * plus[i])
            else:
                break
    if j2 > 0:
        for i in range(minus.shape[0]):
            while j2 >= 0 and minus[j2] * minus[i] > hi:
                j2 -= 1
            if j2 > i:
                res = max(res, minus[j2] * minus[i])
            else:
                break
    return res


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

    n_minus = len(minus)
    n_zero = len(zero)
    n_plus = len(plus)

    p_minus = n_minus * n_plus
    p_zero = n_zero * (n_minus + n_plus) + n_zero * (n_zero - 1) // 2

    if K <= p_minus:
        ans = solve1(K, minus, plus)
        print(ans)
    elif K <= p_minus + p_zero:
        print(0)
    else:
        ans = solve2(K - p_minus - p_zero, minus, plus)
        print(ans)

if __name__ == '__main__':
    main()