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 numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))

# inputを正負で分割
p = []
n = []
z = 0
for v in a:
    if v > 0:
        p.append(v)
    elif v == 0:
        z += 1
    else:
        n.append(v)
l_p = len(p)
l_n = len(n)

num_negative = l_p * l_n
if z != 0:
    num_zero = int((l_p + l_n) * z + z * (z-1) / 2)
else:
    num_zero = 0

if l_p > 0 and l_n > 0:
    num_positive = int(l_p * (l_p-1) / 2 + l_n * (l_n-1) / 2)
    tmp = []
    if k <= num_negative:
        for i in p:
            for j in n:
                tmp.append(i*j)
        ans = sorted(tmp)[k-1]
    elif num_negative < k <= num_negative + num_zero:
        ans = 0
    else:
        index = k - num_negative - num_zero - 1
        for i in range(l_p):
            for j in range(i+1, l_p):
                tmp.append(p[i]*p[j])
        for i in range(l_n):
            for j in range(i+1, l_n):
                tmp.append(n[i]*n[j])
        ans = sorted(tmp)[index]
        
# positive only
elif l_p > 0 and l_n == 0:
    if k <= num_zero:
        ans = 0
    else:
        p = sorted(p)
        index_tmp = k - num_zero
        i = 1
        while index_tmp > 0:
            if index_tmp > (l_p - i):
                index_tmp = index_tmp - (l_p - i)
                i += 1
            else:
                ans = p[i-1] * p[i-1 + index_tmp]
                break

elif l_p == 0 and l_n > 0:
    if k <= num_zero:
        ans = 0
    else:
        n = list(np.sort(np.array(n) * -1))
        index_tmp = k - num_zero
        i = 1
        while index_tmp > 0:
            if index_tmp > (l_n - i):
                index_tmp = index_tmp - (l_n - i)
                i += 1
            else:
                ans = n[i-1] * n[i-1 + index_tmp]
                break


print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a_lst = list(map(int, input().split()))

minus = []
zero = []
plus = []

for i, a in enumerate(a_lst):
  for b in a_lst[i+1:]:
    if a == 0:
      zero.append(0)
    elif b == 0:
      zero.append(0)
    else:
      if a < 0:
      	if b < 0:
        	plus.append(a * b)
      	else:
        	minus.append(a * b)
      else:
      	if b < 0:
        	minus.append(a * b)
      	else:
        	plus.append(a * b)
if k < len(minus):
  print(minus[k])
elif k - len(minus) < len(zero):
  print(0)
else:
  print(plus[k - len(zero) - len(minus)])

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a_lst = map(int, input().split())
a_lst = sorted(a_lst)

res = []
for i, a in enumerate(a_lst):
  for b in a_lst[i+1:]:
    res.append(a * b)
res = sorted(res)
print(res[k])

Submission status: Runtime Error

Solution code:
A

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

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

def mlDevelopment(PL, ML, P):
  ret = []
  for i in PL:
    for j in ML:
      ret += [i*j]
      if len(ret) == (P+1):
        return ret[P]
  
def plDevelopment(PL, ML, P):
  ret1 = []
  
  # 正の数同士の積
  if len(PL) > 1:
    for i in range(0, len(PL)-1):
      for j in range(i+1, len(PL)):
        ret1 += [PL[i] * PL[j]]
  else:
    ret1 += PL
  
  
  # 負の数同士の積
  ret2 = []
  if len(ML) > 1:
    for i in range(0, len(ML)-1):
      for j in range(i+1, len(ML)):
        ret2 += [ML[i] * ML[j]]
        
  ret = ret1 + ret2
  ret.sort()
  return ret[P]

# Aの中身を、正の数・負の数・マイナスに分けて再格納
PL = []
ML = []
ZL = []
for row in A:
  if row == 0:
    ZL = ZL + [0]
  elif row > 0:
    PL = PL + [row]
  else:
    ML = ML + [row]
# ソート
PL.sort()
ML.sort()    

# 「負の数」「ゼロ」「正の数」と並ぶのでそれぞれの要素数を求める。
PC = comb(len(PL),2,exact=True) + comb(len(ML),2,exact=True)
MC = len(PL) * len(ML)
ZC = len(PL) * len(ZL) + len(ML) * len(ZL) + comb(len(ZL),2,exact=True)
# 探索値の所属する場所を特定する
if MC > K:
  #print('マイナス値')
  ans = mlDevelopment(PL, ML, K)
else:
  K -= MC
  if ZC > K:
    #print('ゼロ')
    ans = 0
  else:
    K -= ZC
    #print('プラス値')
    ans = plDevelopment(PL, ML, K-1)

print(ans)

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

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

def mlDevelopment(PL, ML):
  ret = []
  for i in PL:
    for j in ML:
      ret += [i*j]
  return sorted(ret)
  
def plDevelopment(PL, ML):
  ret = []
  # 正の数同士の積
  if len(PL) > 1:
    for i in range(0, len(PL)-1):
      for j in range(i+1, len(PL)):
        ret += [PL[i] * PL[j]]
  else:
    ret += PL
  
  # 負の数同士の積
  if len(ML) > 1:
    for i in range(0, len(ML)-1):
      for j in range(i+1, len(ML)):
        ret += [ML[i] * ML[j]]
  else:
    ret += ML

  return sorted(ret)

# Aの中身を、正の数・負の数・マイナスに分けて再格納
PL = []
ML = []
ZL = []
for row in A:
  if row == 0:
    ZL = ZL + [0]
  elif row > 0:
    PL = PL + [row]
  else:
    ML = ML + [row]

# 「負の数」「ゼロ」「正の数」と並ぶのでそれぞれの要素数を求める。
PC = comb(len(PL),2,exact=True) + comb(len(ML),2,exact=True)
MC = len(PL) * len(ML)
ZC = len(PL) * len(ZL) + len(ML) * len(ZL) + comb(len(ZL),2,exact=True)
# 探索値の所属する場所を特定する
posi = 0
tgls = []
if MC > K:
  #print('マイナス値')
  tglc = mlDevelopment(PL, ML)
  ans = tglc[K-1]
else:
  if MC + ZC > K:
    #print('ゼロ')
    ans = 0
  else:
    #print('プラス値')
    tglc = plDevelopment(PL, ML)
    ans = tglc[K - (MC + ZC + PC) -1]

print(ans)

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

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

def mlDevelopment(PL, ML):
  ret = []
  for i in PL:
    for j in ML:
      ret += [i*j]
  return sorted(ret)
  
def plDevelopment(PL, ML):
  ret = []
  # 正の数同士の積
  for i in range(0, len(PL)-1):
    for j in range(i+1, len(PL)):
      ret += [PL[i] * PL[j]]
  
  # 負の数同士の積
  for i in range(0, len(ML)-1):
    for j in range(i+1, len(ML)):
      ret += [ML[i] * ML[j]]
      
  return sorted(ret)

# Aの中身を、正の数・負の数・マイナスに分けて再格納
PL = []
ML = []
ZL = []
for row in A:
  if row == 0:
    ZL = ZL + [0]
  elif row > 0:
    PL = PL + [row]
  else:
    ML = ML + [row]
# 「負の数」「ゼロ」「正の数」と並ぶのでそれぞれの要素数を求める。
PC = comb(len(PL),2,exact=True) + comb(len(ML),2,exact=True)
MC = len(PL) * len(ML)
ZC = len(PL) * len(ZL) + len(ML) * len(ZL) + comb(len(ZL),2,exact=True)
# 探索値の所属する場所を特定する
posi = 0
tgls = []
if MC > K:
  #print('マイナス値')
  tglc = mlDevelopment(PL, ML)
  ans = tglc[K-1]
else:
  if MC + ZC > K:
    #print('ゼロ')
    ans = 0
  else:
    #print('プラス値')
    tglc = plDevelopment(PL, ML)
    ans = tglc[K - (MC + ZC + PC) -1]

#print(MC,ZC,PC)
#print(tglc)
print(ans)

Submission status: Runtime Error

Solution code:
from subprocess import *subprocess import *
call (( "pypy3" , "-c" , "" "
       
       
       
N , K = map ( int , input (). Split ())
l = list (map (int, input (). split ()))
s = []
for i in range (0, N):
    for      j      in      range ( i    +   1 , N      ):
        s.append (l [i] * l [j])
s.sort ()
print ( s [ K-1 ])
   
       
       
       
  

   """ ))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
np,nn=len(ap),len(an)
def fminus(x):
  j=0
  cnt=0
  for i in range(np):
    cnt+=j
    while j<np and an[j]*ap[i]>=x:
      j+=1
      cnt+=1
  return cnt
def fplus(x,length,lis):
  r=length-1
  cnt=0
  for l in range(length):
    if r==l:
      break
    while lis[r]*lis[l]>x:
      if r==l:
        break
      r-=1
    if lis[r]*lis[l]<=x:
      cnt+=r-l
  return cnt
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    an.sort(reverse=True)
    ap.sort()
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      if fminus(mid)>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    an.sort()
    ap.sort()
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      if fplus(mid,nn,an)+fplus(mid,np,ap)>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

Submission status: Runtime Error

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

for i in range(n):
  for j in range(i+1,n):
    l.append(a[i]*a[j])

l.sort()
print(l[k])

Submission status: Runtime Error

Solution code:
#155d
import bisect
N,K = map(int, input().split())
A_list = [int(e) for e in input().split()]

#負・0・正の三つに分ける
A_list.sort(reverse=False)
zero_left = bisect.bisect_left(A_list,0)
zero_right = bisect.bisect_right(A_list,0)
A_list_minus = A_list[:zero_left]
A_list_zero = A_list[zero_left:zero_right]
A_list_plus = A_list[zero_right:]

#print("分割したリストの確認")
#print(A_list_minus)
#print(A_list_zero)
#print(A_list_plus)

#print("分割したリストのそれぞれの長さ")
#print("-",len(A_list_minus))
#print("0",len(A_list_zero))
#print("+",len(A_list_plus))
minus_num = len(A_list_minus)
zero_num = len(A_list_zero)
plus_num = len(A_list_plus)

#print("#multiplied#") #掛け算により出てくる数の個数
#print("-",minus_num * plus_num) #正*負
#print("0",int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2)) #ゼロ×any
#print("+",int(minus_num*(minus_num-1)/2 + plus_num*(plus_num-1)/2)) #負*負 or 正*正
#同じ種類同士の掛け算の場合は組み合わせなのでnC2
#異なる種類同士の掛け算の場合はmC1 * nC1


#実は、K番目の数 X を求める時の典型テクニックとして、
#勝手に決めた値Xよりも積が小さくなるペアの個数を数え、
#それがK個以上であればK番目の値はXより小さく、K個未満であればK番目の値はXより大きいことが分かります。

#Xを二部探索する
#ペアの個数の計算はaを固定し
#a*b <= X
#b <= X/aでいける。
#aは回す。

if K <= minus_num * plus_num :
    #答えは負の値
    min_X = A_list_minus[0]*A_list_plus[-1]
    max_X = 0

    while 1:
        X = int((min_X+max_X) / 2)
        
        print("-------------------------------")
        print("積が",X,"以下の個数を計算する。")
        
        under_X_sum = 0
        
        for i in range(minus_num):
            A = A_list_minus[i]
            print(A,X/A,[A_list_plus])
            under_X = plus_num - bisect.bisect_left(A_list_plus,X/A)
            
            under_X_sum += under_X
        
        print("積が",X,"以下の個数は",under_X_sum)
        
        if under_X_sum < K:
            min_X = X
        else:
            max_X = X
    
        if abs(max_X - min_X) <= 1:
            print("#ans#")
            print(max_X)
            break
    
elif minus_num * plus_num < K <= minus_num * plus_num + int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2):
    #答えは0
    print(0)
    
elif minus_num * plus_num + int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2) < K:
    #答えは正の値となる
    #print("ans is plus")
    min_X = 0
    if minus_num >= 2:
        minus_max = A_list_minus[0]*A_list_minus[1]
    else:
        minus_max = 0
        
    if plus_num >= 2:
        plus_max = A_list_plus[-1]*A_list_plus[-2]
    else:
        plus_max = 0   

    max_X = max(plus_max,minus_max)
        
    while 1:
        X = int((min_X+max_X) / 2)
        
        print("-------------------------------")
        print("積が",X,"以下の個数を計算する。")
        
        under_X_sum = 0
        
        #負×負
        for i in range(minus_num):
            A = A_list_minus[i]
            print(A,X/A,[A_list_minus])
            under_X = bisect.bisect_left(A_list_minus,X/A)
            
            under_X_sum += under_X
        
        #正×正
        for i in range(plus_num):
            A = A_list_plus[i]
            print(A,X/A,[A_list_plus])
            under_X = bisect.bisect_left(A_list_plus,X/A)
            
            under_X_sum += under_X
        
        under_X_sum /= 2 #同じ組み合わせを2回カウントしているので割る
        
        print("積が",X,"以下の個数は",under_X_sum)
        
        if under_X_sum < K:
            min_X = X
        else:
            max_X = X
    
        if abs(max_X - min_X) <= 1:
            print("#ans#")
            print(max_X)
            break

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, insort_left
import sys


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

temp = [float('inf')] * K

for i in range(1, N):
    for k in range(i):
        insort_left(temp, A[i] * A[k])
    temp = temp[:K]
    # print(temp)

print(temp[-1])

Submission status: Runtime Error

Solution code:
#155d
import bisect
N,K = map(int, input().split())
A_list = [int(e) for e in input().split()]

#負・0・正の三つに分ける
A_list.sort(reverse=False)
zero_left = bisect.bisect_left(A_list,0)
zero_right = bisect.bisect_right(A_list,0)
A_list_minus = A_list[:zero_left]
A_list_zero = A_list[zero_left:zero_right]
A_list_plus = A_list[zero_right:]

#print("分割したリストの確認")
#print(A_list_minus)
#print(A_list_zero)
#print(A_list_plus)

#print("分割したリストのそれぞれの長さ")
#print("-",len(A_list_minus))
#print("0",len(A_list_zero))
#print("+",len(A_list_plus))
minus_num = len(A_list_minus)
zero_num = len(A_list_zero)
plus_num = len(A_list_plus)

#print("#multiplied#") #掛け算により出てくる数の個数
#print("-",minus_num * plus_num) #正*負
#print("0",int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2)) #ゼロ×any
#print("+",int(minus_num*(minus_num-1)/2 + plus_num*(plus_num-1)/2)) #負*負 or 正*正
#同じ種類同士の掛け算の場合は組み合わせなのでnC2
#異なる種類同士の掛け算の場合はmC1 * nC1

#尺取り法もどきで最終解答を求める
#小さい値同士で積算していき、Kを超えたら、次の値を試す。


if K <= minus_num * plus_num :
    
    #答えは負の値となる
    #print("ans is minus")
    #正負共に0から遠い値から計算していく
    for i in range(0,minus_num,1):
        X = A_list_minus[i]
        for j in range(plus_num-1,-1,-1):
            Y = A_list_plus[j]
            
            #print(X,Y)
            
            if len(multiplied_list) <= K:
                multiplied_list.insert(bisect.bisect_right(multiplied_list,X*Y),X*Y)
            else:
                if multiplied_list[K-1] > X*Y:
                    multiplied_list.pop()
                    insert_place = bisect.bisect_right(multiplied_list,X*Y)
                    multiplied_list.insert(insert_place,X*Y)    
                else:
                    break
                
    print(multiplied_list[K-1])
    
elif minus_num * plus_num < K <= minus_num * plus_num + int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2):
    #答えは0
    print(0)
elif minus_num * plus_num + int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2) < K:
    #答えは正の値となる
    #print("ans is plus")
    #マイナスと0の値の分を0で埋めておく
    multiplied_list = [0 for _ in range(minus_num * plus_num + int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2))]

    #まずマイナス同士から
    #0に近い値から試す。
    for i in range(minus_num-1,0,-1):
        X = A_list_minus[i]
        for j in range(i-1,-1,-1):
            Y = A_list_minus[j]
            
            print(X,Y)
            
            if len(multiplied_list) <= K:
                multiplied_list.insert(bisect.bisect_right(multiplied_list,X*Y),X*Y)
            else:
                if multiplied_list[K-1] > X*Y:
                    multiplied_list.pop()
                    insert_place = bisect.bisect_right(multiplied_list,X*Y)
                    multiplied_list.insert(insert_place,X*Y)    
                else:
                    break
                
    #次にプラス同士
    #0に近い値から試す。
    for i in range(0,plus_num-1):
        X = A_list_plus[i]
        for j in range(i+1,plus_num):
            Y = A_list_plus[j]
            
            #print(X,Y)
            
            if len(multiplied_list) <= K:
                multiplied_list.insert(bisect.bisect_right(multiplied_list,X*Y),X*Y)
            else:
                if multiplied_list[K-1] > X*Y:
                    multiplied_list.pop()
                    insert_place = bisect.bisect_right(multiplied_list,X*Y)
                    multiplied_list.insert(insert_place,X*Y)    
                else:
                    break    
    
    print(multiplied_list[K-1])

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
# print(A)

# テスト
"""
B = []
for i in range(N):
    for j in range(i+1,N):
        B += A[i]*A[j],
B.sort()
# print(B[413])
# print(B[400:450])
"""
# Aを符号で分割
for i in range(N):
    if A[i] > 0:
        zl = i
        break
zr = zl
for i in range(N):
    if A[-i] == 0:
        zr = N+1-i
        break
# print(zl,zr)

M = A[:zl]
nM = zl
# Z = A[zl:zr]
nZ = zr-zl
P = A[zr:]
nP = N-zr
# print(nM,nZ,nP)

# 積がx以下になるものの個数を算出
def product_order_P(L,x):
    if L[0]<0:
        L.reverse()
    n = len(L)
    l = 0
    r = n-1
    c = 0
    while r-l > 0:
        # print(l,r)
        # print("L[l]*L[r] =",L[l]*L[r])
        if L[l]*L[r] <= x:
            c += r-l
            # print("c=",c)
            l += 1
        else:
            r -= 1
    if L[0]<0:
        L.reverse()
    return c

# 積がx以下になるものの個数を算出
def product_order_M(L1,L2,x):
    n1 = len(L1)
    n2 = len(L2)
    r1 = n1-1
    r2 = n2-1
    c = 0
    while r1 >= 0 and r2 >= 0:
        # print(l,r)
        # print("L[l]*L[r] =",L[l]*L[r])
        if L1[r1]*L2[r2] <= x:
            c += r1+1
            r2 -= 1
        else:
            r1 -= 1
    return c
            
zl2 = nM*nP
zr2 = N*(N-1)//2 - nM*(nM-1)//2 - nP*(nP-1)//2
# print(zl2,zr2)

# Kの値によって場合分け
if zl2 <= K < zr2:
    print(0)
    
elif K <= zl2:
    # print("M",M)
    # print("P",P)
    M2min = M[0]*P[-1] 
    M2max = 0
    k = 10**10
    pk = 10**10+1
    
    while pk != k:
        pk = k
        k = (M2min+M2max)//2
        # print("k=",k)
        # print(product_order_M(M,P,k))
        p = product_order_M(M,P,k)
        if p < K:
            M2min = k
        else:
            M2max = k
        # else:
            # print(k)
            # break
    print(k+1)
    
else:
    # print("M",M)
    # print("P",P)
    M2min = 0 
    M2max = max(M[0]**2,P[-1]**2)
    k = 10**10
    pk =  10**10+1
    
    while pk != k:
        pk = k
        k = (M2min+M2max)//2
        """
        print("M2min,M2max,k =",M2min,M2max,k)
        print(product_order_P(P,k)+product_order_P(M,k)+zr2,"番目")
        print("product_order_P(P,k),product_order_P(M,k) =",product_order_P(P,k),product_order_P(M,k))
        """
        p = product_order_P(P,k)+product_order_P(M,k)
        if p+zr2 < K:
            M2min = k
        else:
            M2max = k
        # else:
            # print(k)
            # break
    print(k+1)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
# print(A)

# テスト
"""
B = []
for i in range(N):
    for j in range(i+1,N):
        B += A[i]*A[j],
B.sort()
# print(B[413])
# print(B[400:450])
"""
# Aを符号で分割
for i in range(N):
    if A[i] > 0:
        zl = i
        break
zr = zl
for i in range(N):
    if A[-i] == 0:
        zr = N+1-i
        break
# print(zl,zr)

M = A[:zl]
nM = zl
# Z = A[zl:zr]
nZ = zr-zl
P = A[zr:]
nP = N-zr
# print(nM,nZ,nP)

# 積がx以下になるものの個数を算出
def product_order_P(L,x):
    if L[0]<0:
        L.reverse()
    n = len(L)
    l = 0
    r = n-1
    c = 0
    while r-l > 0:
        # print(l,r)
        # print("L[l]*L[r] =",L[l]*L[r])
        if L[l]*L[r] <= x:
            c += r-l
            # print("c=",c)
            l += 1
        else:
            r -= 1
    if L[0]<0:
        L.reverse()
    return c

# 積がx以下になるものの個数を算出
def product_order_M(L1,L2,x):
    n1 = len(L1)
    n2 = len(L2)
    r1 = n1-1
    r2 = n2-1
    c = 0
    while r1 >= 0 and r2 >= 0:
        # print(l,r)
        # print("L[l]*L[r] =",L[l]*L[r])
        if L1[r1]*L2[r2] <= x:
            c += r1+1
            r2 -= 1
        else:
            r1 -= 1
    return c
            
zl2 = nM*nP
zr2 = N*(N-1)//2 - nM*(nM-1)//2 - nP*(nP-1)//2
# print(zl2,zr2)

# Kの値によって場合分け
if zl2 <= K < zr2:
    print(0)
    
elif K <= zl2:
    # print("M",M)
    # print("P",P)
    M2min = M[0]*P[-1] 
    M2max = 0
    
    for i in range(60):
        k = (M2min+M2max)//2
        # print("k=",k)
        # print(product_order_M(M,P,k))
        p = product_order_M(M,P,k)
        if p < K:
            M2min = k
        elif p >= K:
            M2max = k
        # else:
            # print(k)
            # break
    print(k+1)
    
else:
    # print("M",M)
    # print("P",P)
    M2min = 0 
    M2max = max(M[0]**2,P[-1]**2)
    
    for i in range(60):
        k = (M2min+M2max)//2
        """
        print("M2min,M2max,k =",M2min,M2max,k)
        print(product_order_P(P,k)+product_order_P(M,k)+zr2,"番目")
        print("product_order_P(P,k),product_order_P(M,k) =",product_order_P(P,k),product_order_P(M,k))
        """
        p = product_order_P(P,k)+product_order_P(M,k)
        if p+zr2 < K:
            M2min = k
        elif p+zr2 >= K:
            M2max = k
        # else:
            # print(k)
            # break
    print(k+1)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
# print(A)

# テスト
B = []
for i in range(N):
    for j in range(i+1,N):
        B += A[i]*A[j],
B.sort()
# print(B[413])
# print(B[400:450])

# Aを符号で分割
for i in range(N):
    if A[i] == 0:
        zl = i
        break
for i in range(N):
    if A[-i] == 0:
        zr = N+1-i
        break
# print(zl,zr)

M = A[:zl]
nM = zl
# Z = A[zl:zr]
nZ = zr-zl
P = A[zr:]
nP = N-zr
# print(nM,nZ,nP)

# 積がx以下になるものの個数を算出
def product_order_P(L,x):
    if L[0]<0:
        L.reverse()
    n = len(L)
    l = 0
    r = n-1
    c = 0
    while r-l > 0:
        # print(l,r)
        # print("L[l]*L[r] =",L[l]*L[r])
        if L[l]*L[r] <= x:
            c += r-l
            # print("c=",c)
            l += 1
        else:
            r -= 1
    if L[0]<0:
        L.reverse()
    return c

# 積がx以下になるものの個数を算出
def product_order_M(L1,L2,x):
    n1 = len(L1)
    n2 = len(L2)
    r1 = n1-1
    r2 = n2-1
    c = 0
    while r1 >= 0 and r2 >= 0:
        # print(l,r)
        # print("L[l]*L[r] =",L[l]*L[r])
        if L1[r1]*L2[r2] <= x:
            c += r1+1
            r2 -= 1
        else:
            r1 -= 1
    return c
            
zl2 = nM*nP
zr2 = N*(N-1)//2 - nM*(nM-1)//2 - nP*(nP-1)//2
# print(zl2,zr2)

# Kの値によって場合分け
if zl2 <= K < zr2:
    print(0)
    
elif K <= zl2:
    # print("M",M)
    # print("P",P)
    M2min = M[0]*P[-1] 
    M2max = 0
    
    for i in range(100):
        k = (M2min+M2max)//2
        # print("k=",k)
        # print(product_order_M(M,P,k))
        p = product_order_M(M,P,k)
        if p < K:
            M2min = k
        elif p >= K:
            M2max = k
        # else:
            # print(k)
            # break
    print(k+1)
    
else:
    # print("M",M)
    # print("P",P)
    M2min = 0 
    M2max = max(M[0]**2,P[-1]**2)
    
    for i in range(100):
        k = (M2min+M2max)//2
        """
        print("M2min,M2max,k =",M2min,M2max,k)
        print(product_order_P(P,k)+product_order_P(M,k)+zr2,"番目")
        print("product_order_P(P,k),product_order_P(M,k) =",product_order_P(P,k),product_order_P(M,k))
        """
        p = product_order_P(P,k)+product_order_P(M,k)
        if p+zr2 < K:
            M2min = k
        elif p+zr2 >= K:
            M2max = k
        # else:
            # print(k)
            # break
    print(k+1)

Submission status: Runtime Error

Solution code:
import itertools
nk=input().split()
N=int(nk[0])
K=int(nk[1])
list=input().split()
list1=[]
for item in list :
  list1.append(int(item))
list3=itertools.combinations(list1,2)
list4=[]
for item in list3 :
  list4.append(item[0]*item[1])

list4.sort()
print(list4[K])

Submission status: Runtime Error

Solution code:
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):

    # return (num of pairs <= a) < k

    if a >= 0:
        # negative
        res = len(a_arr_p) * len(a_arr_n)
        # zero
        res += n_zeros * (n - n_zeros) + n_zeros * (n_zeros - 1) // 2
        # p * p
        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
        # n * n
        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:
        # p * n
        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()
    # print(a, res)
    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)
        # print(res, ans)
        assert str(res) == str(ans)


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

Solution code:
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]

# x以下の数を求める
def check(x):
    count = 0  # 積がx以下の組
    if x >= 0:
        count += len(zero) * N  # zero * N
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += np.searchsorted(A, (-x - 1) // nega, side = 'left').sum()  # nega * N
    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(low)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
zenpair = int(N*(N-1)/2)
mai_list = []
pla_list = []
zero = 0
A.sort()
A.reverse()
for i in range(len(A)):
    if A[i] < 0:
        mai_list.append(A[i])
    elif A[i] > 0:
        pla_list.append(A[i])
    else :
        zero+=1
mai_pair = len(mai_list)*len(pla_list)
pla_pair = int(len(pla_list)*(len(pla_list)-1)/2 + len(mai_list)*(len(mai_list)-1)/2)
zero_pair = zenpair - (mai_pair+pla_pair)

K_list = []
if K < mai_pair:
    for p in range(len(mai_list)):
        for r in range(len(pla_list)):
            K_list.append(mai_list[p]*pla_list[r])
elif mai_pair < K and K < mai_pair+zero_pair:
    K_list.append(0)
else :
    for u in range(len(pla_list)):
        for e in range(u,len(pla_list)):
            if u != e:
                K_list.append(pla_list[u]*pla_list[e])
    if len(mai_list)>1:
        for w in range(len(mai_list)):
            for x in range(w,len(mai_list)):
                if w != x:
                    K_list.append(mai_list[w]*mai_list[x])            
K_list.sort()
if K_list[0] == 0:
    print(0)
elif K > mai_pair+zero_pair:
    print(K_list[K-mai_pair-zero_pair-1])
else :
    print(K_list[K])

Submission status: Runtime Error

Solution code:
N,K= map(int, input().split())
A = [0]*N
j=0
k=0
l=0
x=0
pair1 = (N*(N-1))/2 #全体のペア数
pair2 = 0 #正のペアの通り数
pair3 = 0 #０のペアの通り数
pair4 = 0 #負のペアの通り数
Plist = [] #Nから正の数だけが入る
Zlist = [] #Nからゼロだけが入る
Mlist = [] #Nから負の数だけが入る
Culclist = [] #計算結果が入る
A = [int(N) for N in input().split()]
for i in range(N):
    if A[i]>0:
        Plist.append(A[i])
        j+=1
    elif A[i]<0:
        Mlist.append(A[i])
        k+=1
    else:
        Zlist.append(A[i])
        l+=1
A.sort()
pair2 = int((j*(j-1))/2+(k*(k-1))/2)
pair4 = int(j*k)
pair3 = int(pair1-pair2-pair4)
if K<=pair4:
    for a in range(k):
        for b in range(j):
            Culclist.append(Mlist[a]*Plist[b])
            x+=1
    Culclist.sort
    print(Culclist[K])
elif K<=pair4+pair3:
    print(0)
else:
    for a in range(k):
        for b in range(a+1,k):
            Culclist.append(Mlist[a]*Mlist[b])
            x+=1
    for c in range(j):
        for d in range(c+1,j):
            Culclist.append(Plist[c]*Plist[d])
            x+=1
    Culclist.sort()
    print(Culclist[K-pair4-pair3-1])

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A =  list(map(int,input().split()))
c = [0] * (N * (N - 1) //2)
cnt = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    c[cnt] = A[i] * A[j]
    cnt +=1
c.sort()
print(c[K-1])

Submission status: Runtime Error

Solution code:
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=nl()
a=nl()
a.sort()
x,y=0,0
for i in a:
    if i<0:
        x+=1
    elif i==0:
        y+=1
    else:
        break
z=n-x-y
maia = x*z
zero = int((x+z)*y+y*(y-1)/2)
if k<maia:
    muls = []
    for i in range(x):
        for j in range(x+y,n):
            muls.append(a[i] * a[j])
    muls.sort()
    print(muls[k - 1])
elif k<maia+zero:
    print(0)
else:
    muls=[]
    for i in range(x):
        for j in range(i + 1, x):
            muls.append(a[i] * a[j])
    for i in range(x+y,n):
        for j in range(i+1,n):
            muls.append(a[i] * a[j])
    muls.sort()
    print(muls[k-maia-zero-1])