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
from numba import njit


@njit
def main(I):
    N,K=I[0],I[1]
    A = np.array(I[2:],dtype=int)
    A.sort()
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

I=np.array([int(_) for _ in open(0).read().split()],dtype=int)
print(main(I))

Submission status: Runtime Error

Solution code:
import bisect
import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()
#A=sorted([int(_) for _ in input().split()])

#target以下の積がK個以上ある最小のtarget

@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    # Min x for check(x) == True
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                    cnt+=d
                    continue
                q,r=divmod(target,a)
                if a < 0:
                    #il = bisect.bisect_left(A,  q+(r>0))
                    #il = bisect.bisect_left(A,  target / a)
                    il = np.searchsorted(A,q+(r>0),side='left')
                    #ilからiまで、ただしilがiを超えたら0
                    d = max(i - il, 0)
                else:
                    #ir = bisect.bisect_right(A, q)
                    #ir = bisect.bisect_right(A, target / a)
                    ir = np.searchsorted(A,q,side='right')
                    #0からirまで、ただしirがiを超えたらi
                    d = min(ir, i)
                #print(target,a,d)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))

Submission status: Runtime Error

Solution code:
#import bisect
import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
A = np.array([int(_) for _ in input().split()],dtype=int)
#A.sort()
#A=sorted([int(_) for _ in input().split()])

#target以下の積がK個以上ある最小のtarget

@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    # Min x for check(x) == True
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                    cnt+=d
                    continue
                q,r=divmod(target,a)
                if a < 0:
                    #il = bisect.bisect_left(A,  q+(r>0))
                    #il = bisect.bisect_left(A,  target / a)
                    il = np.searchsorted(A,q+(r>0),side='left')
                    #ilからiまで、ただしilがiを超えたら0
                    d = max(i - il, 0)
                else:
                    #ir = bisect.bisect_right(A, q)
                    #ir = bisect.bisect_right(A, target / a)
                    ir = np.searchsorted(A,q,side='right')
                    #0からirまで、ただしirがiを超えたらi
                    d = min(ir, i)
                #print(target,a,d)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))

Submission status: Runtime Error

Solution code:
import bisect
#import numpy as np
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
#A = np.array([int(_) for _ in input().split()],dtype=int)
#A.sort()
A=sorted([int(_) for _ in input().split()])

#target以下の積がK個以上ある最小のtarget


lb = -10**18-1
rb = 10 ** 18 + 1
# Min x for check(x) == True
while rb - lb > 1:
    target = (rb + lb) // 2
    if 1:
        cnt=0
        for i, a in enumerate(A):
            if a==0:
                d = i if target >= 0 else 0
                cnt+=d
                continue
            q,r=divmod(target,a)
            if a < 0:
                il = bisect.bisect_left(A,  q+(r>0))
                #il = bisect.bisect_left(A,  target / a)
                #il = np.searchsorted(A,target/a,side='left')
                #ilからiまで、ただしilがiを超えたら0
                d = max(i - il, 0)
            else:
                ir = bisect.bisect_right(A, q)
                #ir = bisect.bisect_right(A, target / a)
                #ir = np.searchsorted(A,target/a,side='right')
                #0からirまで、ただしirがiを超えたらi
                d = min(ir, i)
            #print(target,a,d)
            cnt+=d
    if cnt>=K:
        rb = target
    else:
        lb = target
print(rb)

Submission status: Runtime Error

Solution code:
import bisect
#import numpy as np
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
#A = np.array([int(_) for _ in input().split()],dtype=int)
#A.sort()
A=sorted([int(_) for _ in input().split()])

#target以下の積がK個以上ある最小のtarget

def check(target):
    cnt=0
    for i, a in enumerate(A):
        if a < 0:
            il = bisect.bisect_left(A,  target / a)
            #il = np.searchsorted(A,target/a,side='left')
            #ilからiまで、ただしilがiを超えたら0
            d = max(i - il, 0)
        elif a > 0:
            ir = bisect.bisect_right(A, target / a)
            #ir = np.searchsorted(A,target/a,side='right')
            #0からirまで、ただしirがiを超えたらi
            d = min(ir, i)
        else:
            d = i if target >= 0 else 0
        #print(target,a,d)
        cnt+=d
    return cnt>=K

lb = -10**18-1
rb = 10 ** 18 + 1
# Min x for check(x) == True
while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(mid):
        rb = mid
    else:
        lb = mid
print(rb)

Submission status: Runtime Error

Solution code:
import bisect
import numpy as np
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()
#A=sorted([int(_) for _ in input().split()])

#target以下の積がK個以上ある最小のtarget

def check(target):
    cnt=0
    for i, a in enumerate(A):
        if a < 0:
            #il = bisect.bisect_left(A,  target / a)
            il = np.searchsorted(A,target/a,side='left')
            #ilからiまで、ただしilがiを超えたら0
            d = max(i - il, 0)
        elif a > 0:
            #ir = bisect.bisect_right(A, target / a)
            ir = np.searchsorted(A,target/a,side='right')
            #0からirまで、ただしirがiを超えたらi
            d = min(ir, i)
        else:
            d = i if target >= 0 else 0
        #print(target,a,d)
        cnt+=d
    return cnt>=K

lb = -10**18-1
rb = 10 ** 18 + 1
# Min x for check(x) == True
while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(mid):
        rb = mid
    else:
        lb = mid
print(rb)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[]
C=[]
D=[]
B_sub=[]
for ai in range(len(A)):
    if ai<0:
        B.append(A[ai])
    elif ai==0:
        C.append(A[ai])
    else:
        D.append(A[ai])
for bi in range(len(B)):
    B_sub.append(-B[bi])
B_sub.sort()
def f_1(x):
    m=0
    M=10**18+1
    while m+1!=M:
        mid=(m+M)//2
        cnt=0
        pos=len(D)-1
        for bi in range(len(B_sub)):
            while pos!=-1:
                if D[pos] > mid//B_sub[bi]:
                    pos-=1
                else:
                    break        
            cnt+=pos+1
        if cnt>x:
            M=mid
        else:
            m=mid
    return M
def f_2(x):
    return 0
def f_3(x):
    m=0
    M=10**18+1
    while m+1!=M:
        mid=(m+M)/2
        cnt=0
        pos=len(B_sub)-1
        for bi in range(len(B_sub)):
            while pos!=-1:
                if B_sub[pos] > mid//B_sub[bi]:
                    pos-=1
                else:
                    break
            cnt+=pos+1
        pos=len(D)-1
        for di in range(len(D)):
            while pos!=-1:
                if D[pos] > mid//D[di]:
                    pos-=1
                else:
                    break
            cnt+=pos+1
        last1=0
        while B_sub[last1]**2<=mid:
            cnt-=1
            last1+=1
        last2=0
        while D[last2]**2<=mid:
            cnt-=1
            last2+=1
        if cnt>x:
            M=mid
        else:
            m=mid
    return M
na=len(B)*len(D)
nc=len(B)*(len(B)-1)/2+len(D)*(len(D)-1)/2
nb=N*(N-1)/2-na-nc
if K<= na:
    print((-1)*(f_1(na-K+1)))
elif (na<K and K<=na+nb):
    print(f_2(K-na))
else:
    print(f_3(K-na-nb))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return (count < K)

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = A[0] * A[-1] - 1
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = 0
    r = max(A[-1] * A[-2], A[0] * A[1])
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)

Submission status: Runtime Error

Solution code:
def comb(li):
    return len(li) * (len(li) - 1) // 2


def count_small(x, li):
    cnt = 0
    j = len(li)
    for i, e in enumerate(li[1:], 1):
        while li[j-1] * e > x:
            j -= 1
        cnt += min(i - 1, j - 1)

    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n - comb(pos) - comb(neg) + 1:
    raise Exception
    k -= len(pos) * len(neg)
    cnt0 = a.count(0)
    k -= cnt0 * (n - 1) - cnt0 * (cnt0 - 1) // 2
    neg = [-e for e in neg]
    neg.sort()
    neg.insert(0, 0)
    pos.sort()
    pos.insert(0, 0)

    lb = 0
    ub = 10 ** 18
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_small(m, neg) + count_small(m, pos)
        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is 0
else:
    print(0)

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()
G=[a for a in A if a>0]
Z=[a for a in A if a==0]
L=[a for a in A if a<0]

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

while ok-ng>1:
  mid=(ok+ng)//2
  sg=0
  for g in G:
    cg=np.searchsorted(A,mid//g,side="right")
    sg+=cg
  sl=0
  for l in L:
    cl=n-np.serchsorted(A,mid+1//l,side="right")
    sl+=cl
  d=sum(0<x**2<=mid for x in A)
  z=0
  if mid>=0:
    z+=len(Z)*n
  c=sg+sl+z-d
  c//=2
  if c>=k:
    ok=mid
  else:
    ng=mid
print(ok)

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()
G=[a for a in A if a>0]
Z=[a for a in A if a==0]
L=[a for a in A if a<0]

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

while ok-ng>1:
  mid=(ok+ng)//2
  sg=0
  for g in G:
    cg=np.searchsorted(A,mid//g,side="right")
    sg+=cg
  sl=0
  for l in L:
    cl=n-np.serchsorted(A,mid//l,side="left")
    sl+=cl
  d=sum(0<x**2<=mid for x in A)
  z=0
  if mid>=0:
    z+=len(Z)*n
  c=sg+sl+z-d
  c//=2
  if c>=k:
    ok=mid
  else:
    ng=mid
print(ok)

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()
G=[a for a in A if a>0]
Z=[a for a in A if a==0]
L=[a for a in A if a<0]

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

while ok-ng>1:
  mid=(ok+ng)//2
  sg=0
  for g in G:
    cg=np.searchsorted(a,mid//g,side="right")
    sg+=cg
  sl=0
  for l in L:
    cl=n-np.serchsorted(a,mid//l,side="left")
    sl+=cl
  d=sum(0<x**2<=mid for x in a)
  z=0
  if mid>=0:
    z+=len(Z)*n
  c=sg+cl+z-d
  c//=2
  if c>=k:
    ok=mid
  else:
    ng=mid
print(ok)

Submission status: Runtime Error

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A)
ok, ng = 10**18, -10**18

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    t = 0
    for i in range(N):
        if A[i] > 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= mid:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        elif mid >= 0:
            s += N
        if A[i] * A[i] <= mid:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) // 2
    # それがK個以上あるかを判定する
    if total >= K:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Runtime Error

Solution code:
from bisect import *
N,K=map(int,input().split())
A=list(map(int,input().split()))
X=[0]*3
Y=[0]*3
Z=[[],[],[]]
for i in range(N):
  if A[i]<0:
    X[0]+=1
    Z[0].append(A[i])
  elif A[i]==0:
    X[1]+=1
    Z[1].append(0)
  else:
    X[2]+=1
    Z[2].append(A[i])
Y[1]=X[1]*(N-1)-((X[1]-1)*X[1])//2
Y[0]=X[0]*X[2]
Y[2]=(N*(N-1))//2-Y[1]-Y[0]
Z[0].sort()
Z[2].sort()
def s0lve():
  global Z,K
  L,R,M,C=-(10**18),-1,0,0
  while L<R:
    M=(L+R)//2
    C=0
    for i in range(len(Z[0])):
      C+=len(Z[2])-bisect_left(Z[2],M/Z[0][i])
    for i in range(len(Z[2])):
      C+=bisect_right(Z[0],M/Z[2][i])
    C=C//2
    if C<=K:
      L=max(M,L+1)
    else:
      R=M
  print(L)

def so1ve():
  assert(False)

if Y[0]>=K:
  s0lve()
elif Y[0]+Y[1]>=K:
  print(0)
else:
  K-=Y[0]+Y[1]
  so1ve()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
from math import ceil

def main():
    n,k = map(int, input().split())
    al = list(map(int, input().split()))
    al.sort()

    al_n = []
    al_p = []
    al_n_p = []
    zero_cnt = 0
    for a in al:
        if a < 0: 
            al_n.append(a)
            al_n_p.append(-1*a)
        elif a > 0: 
            al_p.append(a)
        else: 
            zero_cnt += 1
    al_n_p = al_n_p[::-1]

    m_n_cnt = n_cnt*p_cnt
    m_p_cnt = n_cnt*(n_cnt-1)//2 + p_cnt*(p_cnt-1)//2
    m_zero_cnt = zero_cnt*(n_cnt+p_cnt) + zero_cnt*(zero_cnt-1)//2


    if k <= m_n_cnt:
        left = (-1)*(10**18)
        right = -1
        while right-left>1:
            curr_num = left + (right-left)//2
            curr_cnt = 0
            num_exist = False
            for an in al_n:
                targt_p = abs(curr_num)//abs(an)
                p_ind = bisect_right(al_p,targt_p)
                ok_p_cnt = len(al_p) - p_ind
                curr_cnt += ok_p_cnt
                if p_ind > 0 and al_p[p_ind-1]*an == curr_num:
                    num_exist = True
            
            if curr_cnt > k-1:
                right = curr_num
            elif curr_cnt < k-1:
                left = curr_num
            else:
                if num_exist:
                    print(curr_num)
                    exit()
                else:
                    left = curr_num


    elif m_n_cnt < k <= m_n_cnt+m_zero_cnt:
        print(0)
        exit()

    else:
        k = k - m_n_cnt - m_zero_cnt # 1-index
        right = (10**18)
        left = 0
        while right-left > 1:
            cnt = k
            # print(f'k:{k}')
            # print('----')
            curr_num = left + (right-left)//2
            curr_cnt = 0
            num_exist = False
            # curr_num = 6
            # print(curr_num, left, right)
            for i, an in enumerate(al_n_p):
                targt_p = abs(curr_num)//abs(an)
                ok_p_cnt = max(bisect_right(al_n_p,targt_p)-i-1, 0)
                cnt -= ok_p_cnt
            
            for i, an in enumerate(al_p):
                # print(f'----- {an} -----')
                targt_p = abs(curr_num)//abs(an)
                
                ok_p_cnt = max(bisect_right(al_p,targt_p)-i-1, 0)
                cnt -= ok_p_cnt
                # print(ok_p_cnt)

            if cnt > 0:
                left = curr_num
            else:
                right = curr_num

        print(right)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
from math import ceil

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

n_cnt = bisect_right(al,-1)
p_cnt = n-bisect_left(al,1)
zero_cnt = n-p_cnt-n_cnt
al_n = al[:n_cnt]
al_p = al[(-1)*p_cnt:]
al_n_p = [-1*v for v in al_n]
al_n_p = al_n_p[::-1]

m_n_cnt = n_cnt*p_cnt
m_p_cnt = n_cnt*(n_cnt-1)//2 + p_cnt*(p_cnt-1)//2
m_zero_cnt = zero_cnt*(n_cnt+p_cnt) + zero_cnt*(zero_cnt-1)//2

# print(m_n_cnt, m_p_cnt, m_zero_cnt)


if k <= m_n_cnt:
    left = (-1)*(10**18)
    right = -1
    while True:
        curr_num = left + (right-left)//2
        curr_cnt = 0
        num_exist = False
        for an in al_n:
            targt_p = abs(curr_num)//abs(an)
            p_ind = bisect_right(al_p,targt_p)
            ok_p_cnt = len(al_p) - p_ind
            curr_cnt += ok_p_cnt
            if p_ind > 0 and al_p[p_ind-1]*an == curr_num:
                num_exist = True
        
        if curr_cnt > k-1:
            right = curr_num
        elif curr_cnt < k-1:
            left = curr_num
        else:
            if num_exist:
                print(curr_num)
                exit()
            else:
                left = curr_num


elif m_n_cnt < k <= m_n_cnt+m_zero_cnt:
    print(0)
    exit()

else:
    k = k - m_n_cnt - m_zero_cnt # 1-index
    right = (10**18)
    left = 0
    while right-left > 1:
        cnt = k
        # print(f'k:{k}')
        # print('----')
        curr_num = left + (right-left)//2
        curr_cnt = 0
        num_exist = False
        # curr_num = 6
        # print(curr_num, left, right)
        for i, an in enumerate(al_n_p):
            targt_p = abs(curr_num)//abs(an)
            ok_p_cnt = max(bisect_right(al_n_p,targt_p)-i-1, 0)
            cnt -= ok_p_cnt
        
        for i, an in enumerate(al_p):
            # print(f'----- {an} -----')
            targt_p = abs(curr_num)//abs(an)
            
            ok_p_cnt = max(bisect_right(al_p,targt_p)-i-1, 0)
            cnt -= ok_p_cnt
            # print(ok_p_cnt)

        if cnt > 0:
            left = curr_num
        else:
            right = curr_num

    print(right)

Submission status: Runtime Error

Solution code:
a, b = map(int, input().split())
List = list(map(int, input().split()))
an=0
a0=0
ap=0
n=[]
p=[]
for i in List:
    if i>0:
        ap+=1
        n.append(i)
    if i<0:
        p.append(i)
        an+=1
    if i==0:
        a0+=1
n.sort()
p.sort()

qan=an*ap
qa0=(an+ap)*a0+int(a0*(a0-1)/2)
if 0<b<=qan:
    lista=[]
    for i in range(an):
        for u in range(ap):
            lista.append(n[i]*p[u])
    lista.sort()
    print(lista[b-1])
if qan<b<=qan+qa0:
    print(0)
if qan+qa0<b:
    listc=[]
    for l in [n,p]:
        for i in range(len(l)):
            for u in range(i+1,len(l)):
                listc.append(l[i]*l[u])
    listc.sort()
    #print(listc)
    #print(qan+qa0)
    print(listc[b-(qan+qa0)-1])

Submission status: Runtime Error

Solution code:
a1=[]
z=[]
z2=[]
n, k= map(int,input().split())

for i in range(n+1):
    a1.append(i)
del a1[0]

a=map(str, input().split())
for i in a:
    z.append(i)

for i in z:
    z2.append(int(i))
    
z3=z2[:len(z2)//2]
z4 = z2[len(z2)//2:]
    
h=[ x*y for x in z3 for y in z4]

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

Submission status: Runtime Error

Solution code:
# 解説を参考に作成


# import sys
# sys.setrecursionlimit(10 ** 6)
def cmb(n, r):
    import math
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


from decorator import stop_watch


@stop_watch
def solve(N, K, As):
    As.sort()  # 破壊的～
    # -X, 0, +X に分類
    minus = []
    zero = []
    plus = []
    for A in As:
        if A > 0:
            plus.append(A)
        elif A < 0:
            minus.append(A)
        else:
            zero.append(A)
    # -X, 0, +X のパターンの数を算出
    under_zero = len(minus) * len(plus)
    just_zero = len(zero) * (len(minus) + len(plus)) + cmb(len(zero), 2)
    over_zero = cmb(len(minus), 2) + cmb(len(plus), 2)
    # -X, ..., 0, ..., + X の順番に並んでいることになるので、3パターンで場合分け
    ans = 0
    # print(minus)
    # print(zero)
    # print(plus)
    # print(under_zero, just_zero, over_zero)
    # 場合分け① 0 の番号なら0を出力
    if under_zero < K <= under_zero + just_zero:
        ans = 0
    # 場合分け② -X の番号なら、負の数となる組み合わせから二部探索
    elif K <= under_zero:
        upper = -1
        lower = - 10 ** 18
        while True:
            middle = (upper + lower) // 2
            c = 0
            p = 1
            sub = - float('inf')
            for m in minus:
                while p < len(plus) - 1 and plus[p] * m > middle:
                    p += 1
                # print(p, m)
                if plus[p] * m <= middle:
                    c += len(plus) - (p - 1)
                    sub = max(sub, plus[p] * m)
            # print(c, lower, middle, upper)
            # input()
            if c < K:
                if abs(lower - middle) == 0:
                    upper = upper + 1
                lower = middle
            elif c > K:
                if abs(upper - middle) == 1:
                    ans = sub
                    break
                upper = middle
            else:
                ans = sub
                break
    # 場合分け③ +X の番号なら、正の数となる組み合わせから二部探索
    else:
        upper = 10 ** 18
        lower = 1
        minus = sorted([- i for i in minus])
        re_plus = list(reversed(plus))
        re_minus = list(reversed(minus))
        while True:
            middle = (upper + lower) // 2
            c = 0
            cm = 0
            sub = - float('inf')
            # 正 * 正
            p2 = 0
            for p in re_plus:
                while p2 < len(plus) - 1 and plus[p2 + 1] * p <= middle:
                    p2 += 1
                if plus[p2] * p <= middle:
                    cm += p2 + 1
                    sub = max(sub, plus[p2 if plus[p2] != p else p2 - 1] * p)
                    if p ** 2 <= middle:
                        cm -= 1  # 重複分を削除
            c += cm // 2
            # 負 * 負
            cm = 0
            m2 = 0
            for m in re_minus:
                while m2 < len(minus) - 1 and minus[m2 + 1] * m <= middle:
                    m2 += 1
                if minus[m2] * m <= middle:
                    cm += m2 + 1
                    sub = max(sub, minus[m2 if minus[m2] != m else m2 - 1] * m)
                    if m ** 2 <= middle:
                        cm -= 1  # 重複分を削除
            c += cm // 2
            # print(c, lower, middle, upper)
            # print(K - under_zero - just_zero)
            # input()
            # 個数判定
            if c < K - under_zero - just_zero:
                if abs(lower - middle) == 0:
                    upper = upper + 1
                lower = middle
            elif c > K - under_zero - just_zero:
                if abs(upper - middle) == 1:
                    ans = sub
                    break
                upper = middle
            else:
                ans = sub
                break
    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    As = [int(i) for i in input().split()]
    solve(N, K, As)

Submission status: Runtime Error

Solution code:
from itertools import combinations

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

m = [0] * int(n*(n-1)/2)
i = 0
for v in combinations(a, 2):
    m[i] = v[0] * v[1]
    i += 1

print(sorted(m)[k-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys, bisect

sys.setrecursionlimit(300000)

def solve(n, k, A):
    def _count(A, B, v):
        ret = 0
        for a in A:
            idx = bisect.bisect_right(B, v / a)
            ret += idx
        return ret
    def _count_2(A, B, v):
        ret = 0
        for a in A:
            idx = bisect.bisect_right(A, v // a)
            if a * a <= v:
                idx -= 1
            #print(v, a, idx)
            ret += idx
        for b in B:
            idx = bisect.bisect_right(B, v // b)
            if b * b <= v:
                idx -= 1
            #print(v, b, idx)
            ret += idx
        return ret // 2
    A.sort()
    ns, zs, ps, np = [], [], [], []
    for a in A:
        if a < 0:
            ns.append(a)
            np.append(-a)
        elif a == 0:
            zs.append(a)
        else:
            ps.append(a)
    nn = len(ns) * len(ps)
    zn = len(zs) * (n - len(zs)) + len(zs) * (len(zs) - 1) // 2
    pn = len(ps) * (len(ps) - 1) // 2 + len(ns) * (len(ns) - 1) // 2
    #print(nn, zn, pn)
    if k <= nn:
        #print('a')
        a, b = ps, ns
        l = ns[0] * ps[-1]
        r = 0
        while r - l > 1:
            m = (r + l) // 2
            count = _count(a, b, m)
            if count < k:
                l = m
            else:
                r = m
        ret = r
    elif k <= nn + zn:
        #print('b')
        ret = 0
    else:
        #print('c')
        k -= nn + zn
        np.sort()
        a, b = np, ps
        l = 0
        r = max(np[-1] ** 2, ps[-1] ** 2) + 1
        while r - l > 1:
            m = (r + l) // 2
            count = _count_2(a, b, m)
            #print(m, count, k)
            if count < k:
                l = m
            else:
                r = m
        ret = r
    print(ret)
    return


def _solve(n, k ,A):
    x = []
    y = []
    an = []
    ap = []
    nn = 0
    n0 = 0
    np = 0
    for v in A:
        if v < 0:
            nn += 1
            ap.append(abs(v))
            x.append(v)
        elif v == 0:
            n0 += 1
        else:
            np += 1
            ap.append(abs(v))
            y.append(v)
    nnn = nn * np
    if n0 > 0:
        nn0 = n0 * (n - n0) + (n0 * (n0 - 1)) // 2
    else:
        nn0 = 0
    nnp = n * (n - 1) // 2 - nnn - nn0
    if k <= nnn:
        ret = solve_a(x, y, k)
    elif k <= nnn + nn0:
        ret = 0
    else:
        ret = solve_b(ap, k)
    print(nnn, nn0, nnp)
    print(A)
    return

def main():
    n, k = map(int, input().split())
    a = (list(map(int, input().split())))
    solve(n, k, a)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

from itertools import product
li = []

for i,k in product(A,2):
  li.append(i*k)
li.sort()
print(li[k])

Submission status: Runtime Error

Solution code:
#初期入力
N,K = (int(x) for x in input().split())
A = list(map(int, input().split()))

import numpy as np 
a_np =np.array(A,dtype=np.int64)
ans =np.zeros((N,N),dtype=np.int64)
for i in range(N):
    a =a_np *a_np[i] 
    ans[i] =a

ans =np.triu(ans,k=1)
tri_matrix =np.tri(N,k=-1).T

ans =ans[np.where(tri_matrix ==1)]
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int, input().split()))
limit = 10**9
comb=[]
for i in range(n):
  for j in range(i):
    val = a[i]*a[j]
    if val > limit:
      break
    comb.append(val)
comb.sort()
print(comb[k-1])

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
import sys
input = sys.stdin.readline
nums = list(map(int,input().split()))
import itertoolsjj
cmbs = itertools.combinations(nums,2)
ans=[cmb[0] * cmb[1] for cmb in cmbs]
ans.sort()
print(ans[K-1])