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:
def solve_m(k, a_m, a_p):
    def syaku(mid):
        """mid以下になる組の数を数える"""
        rm = 0
        cnt = 0
        for lp, num in enumerate(a_p):
            while True:
                if rm >= len(a_m) or num * a_m[rm] > mid :
                    break
                else:
                    rm += 1
            cnt += rm
        return cnt
                
    ok, ng = 1, -10 ** 20
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if syaku(mid) >= k:
            ok = mid
        else:
            ng = mid
    return ok

    
def solve_p(k, a_m, a_p):
    print(aaa)
    def syaku(mid):
        """mid以下になる組の数を数える"""
        r = len(a_p)
        cnt = 0
        for l, num in enumerate(a_p):
            while True:
                if r == 0 or num * a_p[r - 1] <= mid:
                    break
                else:
                    r -= 1
            cnt += r
            if l <= r:
                cnt -= 1
        r = len(a_m)
        for l, num in enumerate(a_m):
            while True:
                if r == 0 or num * a_m[r - 1] <= mid:
                    break
                else:
                    r -= 1
            cnt += r
            if l <= r:
                cnt -= 1
        return cnt

    a_m = sorted([-num for num in a_m])
    ok, ng = 10 ** 20, -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if syaku(mid) >= k:
            ok = mid
        else:
            ng = mid
    return ok


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

cnt_p, cnt_m, cnt_0 = 0, 0, 0
tmp_p, tmp_m, tmp_0 = 0, 0, 0
for num in a:
    if num > 0:
        tmp_p += 1
    elif num < 0:
        tmp_m += 1
    else:
        tmp_0 += 1
cnt_p += tmp_p * (tmp_p - 1) // 2 + tmp_m * (tmp_m - 1) // 2
cnt_m += tmp_p * tmp_m
cnt_0 += (tmp_p + tmp_m) * tmp_0 + tmp_0 * (tmp_0 - 1) // 2
# print(cnt_p, cnt_m, cnt_0)

a_m = sorted([a[i] for i in range(n) if a[i] < 0])
a_p = sorted([a[i] for i in range(n) if a[i] > 0])

if k <= cnt_m:
    ans = solve_m(k, a_m, a_p)
elif cnt_m < k <= cnt_m + cnt_0:
    ans = 0
else:
    ans = solve_p(k - cnt_m - cnt_0, a_m, a_p)
      
print(ans)

Submission status: Runtime Error

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

a_minus = [a[i] for i in range(n) if a[i] < 0]
a_plus = [a[i] for i in range(n) if a[i] > 0]
a_zero = a.count(0)

len_minus = len(a_minus)
len_plus = len(a_plus)

#print(a_minus, a_plus)  #

if len_minus * len_plus >= k:
    
    x_min = a_minus[-1] * a_plus[0]
    x_max =  a_minus[0] * a_plus[-1]

    # x未満となる積がk個未満になるようなxの最大値を二分探索で求める
    p = x_min
    q = x_max
    m = (p + q) // 2
    while p + 1 < q:

        point_minus = len_minus - 1
        point_plus = len_plus - 1
        counter = 0
        is_not_loop_broken = True

        while is_not_loop_broken:

            while is_not_loop_broken:

                if a_plus[point_plus] * a_minus[point_minus] < m:
                    counter += (point_minus + 1)
                    break

                point_minus -= 1
                if point_minus < 0:
                    is_not_loop_broken = False
            
            point_plus -= 1
            if point_plus < 0:
                is_not_loop_broken = False
        
        if counter < k:
            p = m
        if counter >= k:
            q = m
        m = (p + q) // 2

    print(p)
    quit()



if len_minus * len_plus + a_zero * (len_minus + len_plus) + a_zero * (a_zero - 1) // 2 >= k:
    print(0)
    quit()



if len_minus * len_plus + a_zero * (len_minus + len_plus) + a_zero * (a_zero - 1) // 2 < k:
    k -= len_minus * len_plus + a_zero * (len_minus + len_plus) + a_zero * (a_zero - 1) // 2
    #print(k)

    x_min = min(a_minus[-1] ** 2, a_plus[0] ** 2) 
    x_max = max(a_minus[0] **2, a_plus[-1] **2)

    
    p = x_min
    q = x_max
    m = (p + q) // 2
    while p + 1 < q:

        counter = 0

        #負*負
        left = 0
        right = len_minus - 1
        minus_counter = 0
        is_not_loop_broken = True
        square = 0

        while is_not_loop_broken:

            while is_not_loop_broken:

                if a_minus[left] * a_minus[right] < m:
                    minus_counter += (len_minus - left)
                    
                    if square == 0:
                        if left >= right:
                            square = len_minus - max(left, right)
                    break

                left += 1
                if left == len_minus:
                    is_not_loop_broken = False
            
            right -= 1
            if right < 0:
                is_not_loop_broken = False
        
        counter += ((minus_counter - square) // 2)
        #print(counter)

        # 正*正
        left = 0
        right = len_plus - 1
        plus_counter = 0
        is_not_loop_broken = True
        square = 0

        while is_not_loop_broken:

            while is_not_loop_broken:

                if a_plus[left] * a_plus[right] >= m:
                    plus_counter += left
                    
                    if square == 0:
                        if left > right:
                            square = min(left, right) + 1
                    break

                left += 1
                if left == len_plus:
                    plus_counter += len_plus * (right + 1)
                    if square == 0:
                        if left > right:
                            square = min(left, right) + 1    
                    is_not_loop_broken = False
            
            right -= 1
            if right < 0:
                is_not_loop_broken = False
        counter += ((plus_counter - square) // 2)
        #print(counter)

        if counter < k:
            p = m
        if counter >= k:
            q = m
        m = (p + q) // 2

        #print(p, q)
        

    print(p)
    quit()

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

n = int(N*(N-1)/2)

cnt = 0
Ap, An = A[A>0], A[A<0]


Ap.sort()
An.sort()

Np = len(Ap)
Nn = len(An)

pn = Np*Nn
pp = Np**2
nn = Nn**2

Amul = []

if pn>=K:
    for i in range(Np):
        for j in range(Nn):
            Amul.append(Ap[i]*An[j])
    ans=sorted(Amul)[K]
elif pp+nn>=n-K+1:
    for i in range(0,Np-1):
        for j in range(i+1,Np):
            if i!=j:
                Amul.append(Ap[i]*Ap[j])
    for i in range(0,Nn-1):
        for j in range(i+1,Nn):
            if i!=j:
                Amul.append(An[i]*An[j])
    ans=sorted(Amul, reverse=True)[n-K]
else:
    ans=0

print(ans)

Submission status: Runtime Error

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

n = int(N*(N-1)/2)
cnt = 0
Ap = []
Am = []

for i in range(N):
    if A[i]>0:
        Ap.append(A[i])
    elif A[i]<0:
        Am.append(A[i])

Ap.sort()
Am.sort()

Np = len(Ap)
Nm = len(Am)

pm = Np*Nm
pp = Np**2
mm = Nm**2

Amul = []

if pm>=K:
    for i in range(Np):
        for j in range(Nm):
            Amul.append(Ap[i]*Am[j])
    ans=sorted(Amul)[K]
elif pp+mm>=n-K+1:
    for i in range(0,Np-1):
        for j in range(i+1,Np):
            if i!=j:
                Amul.append(Ap[i]*Ap[j])
    for i in range(0,Nm-1):
        for j in range(i+1,Nm):
            if i!=j:
                Amul.append(Am[i]*Am[j])
    ans=sorted(Amul, reverse=True)[n-K]
else:
    ans=0

print(ans)

Submission status: Runtime Error

Solution code:
#標準入力からの値取得(N)
N, K = (int(x) for x in input().split())
TMP = [int(x) for x in input().split()]
#List:TMPから、値が0の要素を取り出して別Listに格納する
A = []
Z = 0
for row in TMP:
  if row == 0:
    Z += 1
  else:
    A += [row]
#計算本体処理
ans = []
for i in range(0,len(A)-1):
  for j in range(i+1,len(A)):
    ans += [A[i] * A[j]]
#0を突っ込む処理
ZC = ((N*(N-1))/2) - ((len(A)*(len(A)-1)/2))
ans += ( [0] * int(ZC) )
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
#標準入力からの値取得(N)
N, K = (int(x) for x in input().split())
TMP = [int(x) for x in input().split()]
#List:TMPから、値が0の要素を取り出して別Listに格納する
A = []
Z = 0
for row in TMP:
  if row == 0:
    Z += 1
  else:
    A.append(row)
#計算本体処理
ans = []
for i in range(0,len(A)-1):
  for j in range(i+1,len(A)):
    ans.append( A[i] * A[j] )
#0を突っ込む処理
ZC = ((N*(N-1))/2) - ((len(A)*(len(A)-1)/2))
ans += ( [0] * int(ZC) )
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l

n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
p = bisect_left(A, 0)
an = A[:p]
ap = A[p:]

if k < p * (n - p):
    def helper(x):
        t = 0
        r = 0
        for p in ap:
            while t < len(an) and an[t] * p <= x:
                t += 1
            r += t
        return r < k
    l = binsearch(ap[-1] * an[0] - 1, 1, helper)
else:
    k -= p * (n - p)
    an.reverse()
    def helper(x):
        r = 0
        for a in [ap, an]:
            t = len(a) - 1
            for i, p in enumerate(a):
                if t <= i:
                    break
                while t > i and a[t] * p > x:
                    t -= 1
                r += t - i
            return r < k
        m = ap[-1]
        if an:
            m = max(m, -an[-1])
        l = binsearch(-1, m * m, helper)
print(l + 1)

Submission status: Runtime Error

Solution code:
import sys

def f1(m):
    j=0
    num=0
    for x in ap:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    while True:
        plus+=1
    h,l=-1,ap[-1]*am[-1]
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        else: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    k-=pz
    if ap: h,l=ap[-1]**2,ap[0]**2-1
    if am: h,l=max(h,am[-1]**2),min(l,am[0]**2-1)
    while h-l>1:
        md=(h+l)//2
        p=f2(md)
        if p>=k: h=md
        else: l=md
    print(h)

Submission status: Runtime Error

Solution code:
import sys

def f1(m):
    j=0
    num=0
    for x in ap:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    h,l=0,ap[-1]*am[-1]
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        elif p<k: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    try:
        k-=pz
        if ap: h,l=ap[-1]**2,ap[0]**2-1
        if am: h,l=max(h,am[-1]**2),min(l,am[0]**2-1)
        while h-l>1:

            md=(h+l)//2
            p=f2(md)
            if p>=k: h=md
            elif p<k: l=md
        print(h)
    except IndexError:
        b=1
        while True:
            b+=1

Submission status: Runtime Error

Solution code:
import sys

def f1(m):
    j=0
    num=0
    for x in ap:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    h,l=0,ap[-1]*am[-1]
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        elif p<k: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    k-=pz
    if ap: h,l=ap[-1]**2,ap[0]**2-1
    if am: h,l=max(h,am[-1]**2),min(l,am[0]**2)
    while h-l>1:

        md=(h+l)//2
        p=f2(md)
        if p>=k: h=md
        elif p<k: l=md
    print(h)

Submission status: Runtime Error

Solution code:
import sys

def f1(m):
    j=0
    num=0
    for x in ap:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    h,l=0,ap[-1]*am[-1]
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        elif p<k: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    k-=pz
    h,l=max(ap[-1]**2,am[-1]**2),min(am[1]**2,am[1]**2)-1
    while h-l>1:

        md=(h+l)//2
        p=f2(md)
        if p>=k: h=md
        elif p<k: l=md
    print(h)

Submission status: Runtime Error

Solution code:
t = int(input())

def getProduct(n, m):
    product = 1
    for i in range(2, len(n)):
        product *= pow(n[i], m[i])
    return product

def getSum(n):
    sum = 0
    for item in n:
        sum += item
    return sum

def getCombo(n):
    factors = []
    powers = []
    j = 2

    while n != 1:
        if n % j == 0:
            factors.append(j)
            i = 0
            while n % j == 0:
                n = int(n / j)
                i += 1
            powers.append(i)
        j += 1
    sum = getSum(powers)
    if len(factors) >= 3:
        print(f"YES\n{pow(factors[0], powers[0])} {pow(factors[1], powers[1])} {getProduct(factors, powers)}")
    elif len(factors) == 2:
        if sum < 4:
            print("NO")
        else:
            print(f"YES\n{factors[0]} {factors[1]} {pow(factors[0], powers[0] - 1) * pow(factors[1], powers[1] - 1)}")
    else:
        if sum >= 6:
            print(f"YES\n{factors[0]} {factors[0] * factors[0]} {pow(factors[0], sum - 3)}")
        else:
            print("NO")


for i in range(t):
    n = int(input())
    getCombo(n)

Submission status: Runtime Error

Solution code:
n = list(map(int, input().split(" ")))
ar = list(map(int, input().split(" ")))

def pairing(n, k, a):
    next = 1
    pairs = []

    while next != n:
        for i in range(0, n - next):
            pairs.append(a[i] * a[i + next])
        next += 1
    pairs = sorted(pairs)
    print(pairs[k])

pairing(n[0], n[1], ar)

Submission status: Runtime Error

Solution code:
import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    minus = bisect.bisect_left(a, 0)
    zero = bisect.bisect_left(a, 1) - minus
    plus = n - (minus + zero)

    minus_product = minus * plus
    zero_product = zero * (minus + plus) + ((zero - 1) * zero) // 2

    a_minus = list(map(abs, a[0:minus]))
    a_minus.sort()
    a_plus = a[minus + zero:]

    if k <= minus_product:
        km = k - 1
        a_minus.reverse()
        a_plus.reverse()
        m_absmin = a_minus[-1] * a_plus[-1]
        m_absmax = a_minus[0] * a_plus[0]

        ok = m_absmax
        ng = m_absmin - 1

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            mm = 0
            cnt = 0
            for pp in range(plus):
                mm = 0
                x = a_plus[pp] * a_minus[mm]
                while x > mid:
                    mm += 1
                    x = a_plus[pp] * a_minus[mm]
                cnt += (mm - 1)
            if cnt < km:
                ok = mid
            else:
                ng = mid

        print(-ok)

    elif k <= (minus_product + zero_product):
        print(0)
    else:
        kp = k - (minus_product + zero_product) - 1
        ppmin, pmmin = INF, INF
        ppmax, pmmax = -1, -1
        if plus >= 2:
            ppmin = a_plus[0] * a_plus[1]
            ppmax = a_plus[-1] * a_plus[-2]
        if minus >= 2:
            pmmin = a_minus[0] * a_minus[1]
            pmmax = a_minus[-1] * a_minus[-2]

        p_absmin = min(ppmin, pmmin)
        p_absmax = max(ppmax, pmmax)

        ok = p_absmin
        ng = p_absmax + 1
        mid = (ok + ng) // 2

        while abs(ng - ok) > 1:
            prev_mid = mid
            mid = (ok + ng) // 2
            cnt = 0
            p2 = 0

            for p1 in range(plus):
                p2 = p1 + 1
                while p2 < plus and a_plus[p1] * a_plus[p2] < mid:
                    p2 += 1
                cnt += (p2 - p1 - 1)

            m2 = 0
            for m1 in range(minus):
                m2 = m1 + 1
                while m2 < minus and a_minus[m1] * a_minus[m2] < mid:
                    m2 += 1
                cnt += (m2 - m1 - 1)

            if cnt <= kp:
                ok = mid
            else:
                ng = mid

        print(ok)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = input()
f = n.count('0')
while f != 0:
  e = int(n)-1
  f = f- 1
import numpy as np
print(np.product(np.array(list(map(int , str(e))))))

Submission status: Runtime Error

Solution code:
w = list(map(int , input().split()))
n = w[0]
m = w[1]
p  =[]
l = list(map(int , input().split()))
from itertools import combinations 
import numpy as np
r =  list(combinations(l, 2)) 
for i in r:
  p.append(np.product(np.array(i)))
print(sorted(p)[m])

Submission status: Runtime Error

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


b=list()
for i in range(1,len(a)+1):
    for j in range(1,i):
        b.append(j*i)
b.sort()

print(b[k])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
M=[i for i in A if i<0] ; m=len(M)
Z=[i for i in A if i==0] ; z=len(Z)
P=[i for i in A if i>0] ; p=len(P)
if 1<=k<=m*p:
  ans=sorted([i*j for i in M for j in P])
  print(ans[k-1])
  exit()
elif m*p+1<=k<=m*p+(m+p)*z+(z-1)*z//2:
  k-=(mp+1)
  print(0)
  exit()
else:
  k-=(m*p+p*z+z*m+1+z*(z-1)//2)
  ans=sorted([M[i]*M[j] for i in range(m) for j in range(i)]+[P[i]*P[j] for i in range(p) for j in range(i)])
  print(ans[k])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
M=[i for i in A if i<0] ; m=len(M)
Z=[i for i in A if i==0] ; z=len(Z)
P=[i for i in A if i>0] ; p=len(P)
if 1<=k<=m*p:
  ans=sorted([i*j for i in M for j in P])
  print(ans[k-1])
  exit()
elif m*p+1<=k<=m*p+(m+p)*z:
  k-=(mp+1)
  print(0)
  exit()
else:
  k-=(m*p+p*z+z*m+1)n,k=map(int,input().split())
A=list(map(int,input().split()))
M=[i for i in A if i<0] ; m=len(M)
Z=[i for i in A if i==0] ; z=len(Z)
P=[i for i in A if i>0] ; p=len(P)
print(m,z,p)
if 1<=k<=m*p:
  ans=sorted([i*j for i in M for j in P])
  print(ans[k-1])
  exit()
elif m*p+1<=k<=m*p+(m+p)*z+(z-1)*z//2:
  k-=(mp+1)
  print(0)
  exit()
else:
  k-=(m*p+p*z+z*m+1+z*(z-1)//2)
  ans=sorted([M[i]*M[j] for i in range(m) for j in range(i)]+[P[i]*P[j] for i in range(p) for j in range(i)])
  print(ans[k])
  ans=sorted([i*j for i in M for j in M if i!=j]+[i*j for i in P for j in P if i!=j])
  print(ans[k])

Submission status: Runtime Error

Solution code:
import numpy as np
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
plus=[i for i in a if i>0]
zero=[i for i in a if i==0]
minus=[i for i in a if i<0]
p_p_l=int((len(plus)*(len(plus)-1)/2)+(len(minus)*(len(minus)-1)/2))
p_z_l=int(len(zero)*(len(plus)+len(minus)))
p_m_l=int(len(plus)*len(minus))
if k<=p_m_l:
  p=[i*j for i in plus for j in minus]
  p=sorted(p)
  print(p[k-1])
elif k<=p_m_l+p_z_l:
  print(0)
else:
  p=[plus[i]*plus[-j-1] for i in range(len(plus)) for j in range(len(plus)-i-1)]
  p+=[minus[i]*minus[-j-1] for i in range(len(minus)) for j in range(len(minus)-i-1)]
  p=sorted(p)
  print(p[k-1-(p_m_l+p_z_l)])

Submission status: Runtime Error

Solution code:
import numpy as np

from bisect import bisect

DEBUG = False


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

A.sort()
A = np.array(A, dtype=np.int64)
neg = A[A < 0]
zero = A[A == 0]
pos = A[A > 0]

# Only keep the abs value of the negatives and flip so it's sorted
revAbsNeg = np.flip(-neg)


def countDistinctPairsLessThan(arr, prod):
    # Given a sorted array find the number of distinct pairs that are < prod
    # O(N * log(N)) where N = len(arr)

    N = arr.shape[0]
    assert arr.shape == (N,)
    count3 = np.sum(
        np.minimum(np.arange(N), np.searchsorted(arr, (prod - 1) // arr, side="right"))
    )

    if DEBUG:
        count = 0
        for i, x in enumerate(arr):
            count += bisect(arr, (prod - 1) // x, 0, i)

        count2 = 0
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                if arr[i] * arr[j] < prod:
                    count2 += 1
        assert count == count2 == count3
    return count3


def countPairsLessThanOrEqual(arr1, arr2, prod):
    # Given two sorted arrays containing *positive* numbers only,
    # find the number of pairs between the two arrays that are <= prod
    # O(N * log(M)) where N = len(arr1), M = len(arr2)
    if len(arr1) > len(arr2):
        arr1, arr2 = arr2, arr1

    count3 = np.sum(np.searchsorted(arr2, prod // arr1, side="right"))

    if DEBUG:
        count = 0
        for x in arr1:
            count += bisect(arr2, prod // x)
        count2 = 0
        for x in arr1:
            for y in arr2:
                if x * y <= prod:
                    count2 += 1
        assert count == count2 == count3
    return count3


def getIndex(prod):
    # Count number of pairs strictly less than prod
    count = 0
    if prod < 0:
        # All negatives except for the negatives with abs value less than or equal -prod
        count += len(pos) * len(neg)
        count -= countPairsLessThanOrEqual(pos, revAbsNeg, -prod)
    elif prod >= 0:
        # All negatives
        count += len(pos) * len(neg)
        if prod > 0:
            # All zeroes
            count += len(zero) * len(neg)
            count += (len(zero) * (len(zero) - 1)) // 2
            count += len(zero) * len(pos)
            # Positives with positives
            count += countDistinctPairsLessThan(pos, prod)
            # Negatives with negatives
            count += countDistinctPairsLessThan(revAbsNeg, prod)

    if DEBUG:
        count2 = 0
        for i in range(N):
            for j in range(i + 1, N):
                if A[i] * A[j] < prod:
                    count2 += 1
        assert count == count2
    return count


def bisect_f(f, lo, hi):
    if DEBUG:
        assert f(lo) and not f(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if f(mid):
            lo = mid
        else:
            hi = mid
        if DEBUG:
            assert f(lo) and not f(hi)
    if DEBUG:
        assert hi - lo == 1
        assert f(lo) and not f(hi)
    return lo


def solve(K):
    lo = -10 ** 18
    hi = 10 ** 18 + 1
    if DEBUG:
        assert getIndex(lo) <= K < getIndex(hi)
    prod = bisect_f(lambda prod: getIndex(prod) <= K, lo, hi)
    if DEBUG:
        assert getIndex(prod) <= K < getIndex(prod + 1)
    return prod


if DEBUG:
    for k in range((N * (N - 1)) // 2):
        print("k", k, solve(k))

print(solve(K - 1))  # K is 1-indexed

Submission status: Runtime Error

Solution code:
import numpy as np

from bisect import bisect

DEBUG = False


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

A = np.array(A, dtype=np.int64)
A.sort()
neg = A[A < 0]
zero = A[A == 0]
pos = A[A > 0]

# Only keep the abs value of the negatives and flip so it's sorted
revAbsNeg = np.flip(-neg)


def countDistinctPairsLessThan(arr, prod):
    # Given a sorted array find the number of distinct pairs that are < prod
    # O(N * log(N)) where N = len(arr)

    N = arr.shape[0]
    #assert arr.shape == (N,)
    count3 = np.sum(
        np.minimum(np.arange(N), np.searchsorted(arr, (prod - 1) // arr, side="right"))
    )

    if DEBUG:
        count = 0
        for i, x in enumerate(arr):
            count += bisect(arr, (prod - 1) // x, 0, i)

        count2 = 0
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                if arr[i] * arr[j] < prod:
                    count2 += 1
        assert count == count2 == count3
    return count3


def countPairsLessThanOrEqual(arr1, arr2, prod):
    # Given two sorted arrays containing *positive* numbers only,
    # find the number of pairs between the two arrays that are <= prod
    # O(N * log(M)) where N = len(arr1), M = len(arr2)
    if len(arr1) > len(arr2):
        arr1, arr2 = arr2, arr1

    count3 = np.sum(np.searchsorted(arr2, prod // arr1, side="right"))

    if DEBUG:
        count = 0
        for x in arr1:
            count += bisect(arr2, prod // x)
        count2 = 0
        for x in arr1:
            for y in arr2:
                if x * y <= prod:
                    count2 += 1
        assert count == count2 == count3
    return count3


def getIndex(prod):
    # Count number of pairs strictly less than prod
    count = 0
    if prod < 0:
        # All negatives except for the negatives with abs value less than or equal -prod
        count += len(pos) * len(neg)
        count -= countPairsLessThanOrEqual(pos, revAbsNeg, -prod)
    elif prod >= 0:
        # All negatives
        count += len(pos) * len(neg)
        if prod > 0:
            # All zeroes
            count += len(zero) * len(neg)
            count += (len(zero) * (len(zero) - 1)) // 2
            count += len(zero) * len(pos)
            # Positives with positives
            count += countDistinctPairsLessThan(pos, prod)
            # Negatives with negatives
            count += countDistinctPairsLessThan(revAbsNeg, prod)

    if DEBUG:
        count2 = 0
        for i in range(N):
            for j in range(i + 1, N):
                if A[i] * A[j] < prod:
                    count2 += 1
        assert count == count2
    return count


def bisect_f(f, lo, hi):
    if DEBUG:
        assert f(lo) and not f(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if f(mid):
            lo = mid
        else:
            hi = mid
        if DEBUG:
            assert f(lo) and not f(hi)
    if DEBUG:
        assert hi - lo == 1
        assert f(lo) and not f(hi)
    return lo


def solve(K):
    lo = -10 ** 18
    hi = 10 ** 18 + 1
    if DEBUG:
        assert getIndex(lo) <= K < getIndex(hi)
    prod = bisect_f(lambda prod: getIndex(prod) <= K, lo, hi)
    if DEBUG:
        assert getIndex(prod) <= K < getIndex(prod + 1)
    return prod


if DEBUG:
    for k in range((N * (N - 1)) // 2):
        print("k", k, solve(k))

print(solve(K - 1))  # K is 1-indexed