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

negs, zeros, pos = [], [], []
for i in range(n):
    if a[i] < 0:
        negs.append(a[i])
    elif a[i] == 0:
        zeros.append(a[i])
    else:
        pos.append(a[i])

negs.sort()
pos.sort()
n_neg_prod = len(negs) * len(pos)
n_zero_prod = len(zeros) * (len(zeros) - 1) // 2 + len(zeros) * (len(negs) + len(pos))
n_pos_prod = len(negs) * (len(negs) - 1) // 2 + len(pos) * (len(pos) - 1) // 2
negs2 = [-b for b in negs][::-1]

from bisect import bisect_left
if k <= n_neg_prod:
    k = n_neg_prod - k + 1

    def C(x):
        # No of products <= x
        count = 0
        for i, a in enumerate(pos):
            div = x // a
            idx = bisect_left(negs2, div)
            if negs2[idx] != div:
                count += idx
            else:
                count += idx + 1

        return count

    lb = pos[0] * negs2[0] - 1
    ub = pos[-1] * negs2[-1] + 1
    while (ub - lb) > 1:
        mid = (lb + ub) // 2
        if C(mid) < k:
            lb = mid
        else:
            ub = mid
    print(-ub)

elif k <= n_neg_prod + n_zero_prod:
    print(0)
else:
    k -= (n_neg_prod + n_zero_prod)

    def C(x):
        # No of products <= x
        count = 0
        for arr in [negs2, pos]:
            for i, a in enumerate(arr):
                div = x // a
                if div >= a:
                    count += i
                else:
                    idx = bisect_left(arr, div)
                    if arr[idx] != div:
                        count += idx
                    else:
                        count += idx + 1

        return count

    m, M = float('inf'), 0
    if pos:
        m, M = min(m, pos[0] ** 2), max(M, pos[-1] ** 2)
    if negs2:
        m, M = min(m, negs2[0] ** 2), max(M, negs2[-1] ** 2)
    lb = m - 1
    ub = M + 1
    while (ub - lb) > 1:
        mid = (lb + ub) // 2
        if C(mid) < k:
            lb = mid
        else:
            ub = mid
    print(ub)

Submission status: Runtime Error

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

negs, zeros, pos = [], [], []
for i in range(n):
    if a[i] < 0:
        negs.append(a[i])
    elif a[i] == 0:
        zeros.append(a[i])
    else:
        pos.append(a[i])

negs.sort()
pos.sort()
n_neg_prod = len(negs) * len(pos)
n_zero_prod = len(zeros) * (len(zeros) - 1) // 2 + len(zeros) * (len(negs) + len(pos))
n_pos_prod = len(negs) * (len(negs) - 1) // 2 + len(pos) * (len(pos) - 1) // 2
negs2 = [-b for b in negs][::-1]

from bisect import bisect_left
if k <= n_neg_prod:
    k = n_neg_prod - k + 1

    def C(x):
        # No of products <= x
        count = 0
        for i, a in enumerate(pos):
            div = x // a
            idx = bisect_left(negs2, div)
            if negs2[idx] != div:
                count += idx
            else:
                count += idx + 1

        return count

    lb = pos[0] * negs2[0] - 1
    ub = pos[-1] * negs2[-1] + 1
    while (ub - lb) > 1:
        mid = (lb + ub) // 2
        if C(mid) < k:
            lb = mid
        else:
            ub = mid
    print(-ub)

elif k <= n_neg_prod + n_zero_prod:
    print(0)
else:
    k -= (n_neg_prod + n_zero_prod)

    def C(x):
        # No of products <= x
        count = 0
        for arr in [negs2, pos]:
            for i, a in enumerate(arr):
                div = x // a
                if div >= a:
                    count += i
                else:
                    idx = bisect_left(arr, div)
                    if arr[idx] != div:
                        count += idx
                    else:
                        count += idx + 1

        return count

    m, M = float('inf'), 0
    if pos:
        m, M = min(m, pos[0]), max(M, pos[-1])
    if negs2:
        m, M = min(m, negs2[0]), max(M, negs2[-1])
    lb = m - 1
    ub = M + 1
    while (ub - lb) > 1:
        mid = (lb + ub) // 2
        if C(mid) < k:
            lb = mid
        else:
            ub = mid
    print(ub)

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,K = LI()
    pl = []
    mi = []
    z = 0
    for x in sys.stdin.readline().split():
        x = int(x)
        if x > 0:
            pl.append(x)
        elif x < 0:
            mi.append(-x)
        else:
            z += 1
    pl.sort()
    mi.sort()

    minus = len(pl) * len(mi)
    zero = z * (len(pl) + len(mi)) + z * (z-1) // 2

    h = 10**18+1
    l = -10**18

    while l+1 < h:
        m = (h+l)//2

        if m > 0:
            k = minus + zero
            j = len(pl)-1
            for i in range(len(pl)-1):
                if i >= j: break
                while pl[i] * pl[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
            j = len(mi)-1
            for i in range(len(mi)-1):
                if i >= j: break
                while mi[i] * mi[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
        elif m < 0:
            k = 0
            j = 0
            for i in range(len(pl)):
                while -pl[i] * mi[j] > m:
                    j += 1
                    if j == len(mi): break
                else:
                    k += len(mi) - j
                    continue
                break
        else:
            k = minus + zero

        if k < K:
            l = m
        else:
            h = m

    print(h)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,K = LI()
    pl = []
    mi = []
    z = 0
    for x in sys.stdin.readline().split():
        x = int(x)
        if x > 0:
            pl.append(x)
        elif x < 0:
            mi.append(-x)
        else:
            z += 1
    pl.sort()
    mi.sort()

    minus = len(pl) * len(mi)
    zero = z * (len(pl) + len(mi)) + z * (z-1) // 2

    h = 10**18+1
    l = -10**18

    while l+1 < h:
        m = (h+l)//2

        if m >= 0:
            k = minus + zero
            j = len(pl)-1
            for i in range(len(pl)-1):
                if i >= j: break
                while pl[i] * pl[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
            j = len(mi)-1
            for i in range(len(mi)-1):
                if i >= j: break
                while mi[i] * mi[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
        elif m < 0:
            k = 0
            j = 0
            for i in range(len(pl)):
                while -pl[i] * mi[j] > m:
                    j += 1
                    if j == len(mi): break
                else:
                    k += len(mi) - j
                    continue
                break

        if k >= K:
            h = m
        else:
            l = m

    print(h)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,K = LI()
    pl = []
    mi = []
    z = 0
    for x in sys.stdin.readline().split():
        x = int(x)
        if x > 0:
            pl.append(x)
        elif x < 0:
            mi.append(-x)
        else:
            z += 1
    pl.sort()
    mi.sort()

    minus = len(pl) * len(mi)
    zero = z * (len(pl) + len(mi)) + z * (z-1) // 2

    h = 10**9+1
    l = -10**9

    while l+1 < h:
        m = (h+l)//2

        if m > 0:
            k = minus + zero
            j = len(pl)-1
            for i in range(len(pl)):
                while pl[i] * pl[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
            j = len(mi)-1
            for i in range(len(mi)-1,-1,-1):
                while mi[i] * mi[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
        elif m < 0:
            k = 0
            j = 0
            for i in range(len(pl)):
                while -pl[i] * mi[j] > m:
                    j += 1
                    if j == len(mi): break
                else:
                    k += len(mi) - j
                    continue
                break
        else:
            k = minus

        if k >= K:
            h = m
        else:
            l = m

    print(h)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

# 負の個数
num_neg = bisect.bisect_left(A, 0)
# 0の個数
num_zero = bisect.bisect_right(A, 0) - num_neg
# 正の個数
num_pos = N - num_neg - num_zero

A_neg = A[:num_neg][::-1] # 絶対値が小さいものからになるようにソート
A_pos = A[num_neg + num_zero:]

A_neg_rev = A_neg[::-1] # 絶対値が大きいものからになるようにソート
A_pos_rev = A_pos[::-1]

# 値が0になるペアの個数
cnt_zero = num_zero * (num_pos + num_neg) + (num_zero * (num_zero - 1) // 2)
# 値が負になるペアの個数
cnt_neg = num_pos * num_neg

# 値が正になるとき
def bin_search_pos(arr, mid):
    cnt = 0
    for i in range(len(arr) - 1):
        ok = i + 1
        ng = len(arr) - 1
        a = arr[i]
        if a * arr[ok] > mid:
            return cnt
        elif a * arr[ng] <= mid:
            cnt += ng - i
        else:
            while ok + 1 < ng:
                c = (ok + ng) // 2
                if a * arr[c] <= mid:
                    ok = c
                else:
                    ng = c
        
            cnt += ok - i
    return cnt

# 値が負になるとき
def bin_search_neg(arr_pos, arr_neg, mid):
    cnt = 0
    for a in arr_pos:
        ok = 0
        ng = len(arr_neg) - 1
        if a * arr_neg[ok] > mid:
            return cnt
        elif a * arr_neg[ng] <= mid:
            cnt += ng + 1
        else:
            while ok + 1 < ng:
                c = (ok + ng) // 2
                if a * arr_neg[c] <= mid:
                    ok = c
                else:
                    ng = c
        
            cnt += ok + 1
    return cnt

# 自分以下の数になるペアの個数がK個以上になる
ok = 10 ** 18
ng = -ok - 1
while ng + 1 < ok:
    mid = (ok + ng) // 2
    cnt = 0
    if mid > 0:
        cnt += cnt_zero
        cnt += cnt_neg
        cnt += bin_search_pos(A_pos, mid) + bin_search_pos(A_neg, mid)
    elif mid == 0:
        cnt += cnt_zero
        cnt += cnt_neg
    else:
        cnt += bin_search_neg(A_pos_rev, A_neg_rev, mid)
    if cnt >= K:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Runtime Error

Solution code:
import numpy as np
stdin = open(0)

N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().split(), np.int64)


A = np.sort(A)
zero = A[A == 0]
pos = list(A[A > 0])
neg = list(A[A < 0])

neg_count = len(pos) * len(neg)
pos_count = len(pos) * (len(pos) - 1) // 2 + len(neg) * (len(neg) - 1) // 2
zero_count = N * (N - 1) // 2 - neg_count - pos_count

if K > neg_count and K <= neg_count + zero_count:
    print(0)
    exit(0)

def f(x):
    """x以下の積の組み合わせを数える(k番目が負の場合)"""
    count = 0
    pos_idx = None
    neg_idx = len(neg) - 1
    for idx, p in enumerate(reversed(pos)):
        if p * neg[neg_idx] <= x:
            pos_idx = len(pos) - idx - 1
        else:
            break
    # pos_idxに最大の負の値x正の値 <= xを満たす最小の正値のindexが入っている
    if pos_idx is not None:
        count += len(pos) - pos_idx
    else:
        pos_idx = 0
    while neg_idx > 0:
        neg_idx -= 1
        ans = None
        for i in reversed(range(pos_idx + 1)):
            if pos[i] * neg[neg_idx] <= x:
                ans = i
                break
        if ans is None:
            break
        # iにはneg_idxの位置の負数と掛けたときに<=xを満たす最小の正数のindexが入る
        # print(i)
        count += len(pos) - ans
        pos_idx = i
    return count

def g(x):
    """x以下の積の組み合わせを数える(k番目が正の場合)"""
    count = neg_count + zero_count
    # print('c1', count)
    l_idx = 0
    r_idx = 0
    # 正数 x 正数の場合
    for idx, p in enumerate(reversed(pos)):
        if p * pos[l_idx] <= x:
            r_idx = len(pos) - idx - 1
            break
    if r_idx > 0:
        count += (r_idx + 1) - 1  # index = 0の分は引く
        while r_idx - l_idx > 0:
            l_idx += 1
            ans = l_idx
            # print(l_idx, r_idx)
            for i in reversed(range(l_idx + 1, r_idx + 1)):
                # print(i, pos[i], l_idx, pos[l_idx])
                if pos[i] * pos[l_idx] <= x:
                    ans = i
                    break
            # print('ans', ans, l_idx)
            if ans > l_idx:
                count += ans - l_idx
                r_idx = ans
            else:
                break
    # print('c2', count)
    # 負数 x 負数の場合
    r_idx = len(neg) - 1
    l_idx = len(neg) - 1
    for idx, n in enumerate(neg):
        if n * neg[r_idx] <= x:
            l_idx = idx
            break
    # print(l_idx, r_idx)
    if l_idx < r_idx:
        count += len(neg) - l_idx - 1 # r_idxの分は引く
        # print('c3', count)
        while r_idx - l_idx > 0:
                r_idx -= 1
                ans = r_idx
                # print(l_idx, r_idx)
                for i in range(l_idx, r_idx):
                    # print(i, pos[i], l_idx, pos[l_idx])
                    if neg[i] * neg[r_idx] <= x:
                        ans = i
                        break
                # print(l_idx, r_idx, ans)
                # print('ans', ans, l_idx)
                if ans < r_idx:
                    count += r_idx - ans
                    l_idx = ans
                else:
                    break
    return count


def h(x):
    return f(x) if K <= neg_count else g(x)

# print(h(100000000000))

l = -1 * 10 ** 18
r = 10 ** 18
if K <= neg_count:
    r = -1
    h = f
else:
    l = 1
    h = g

while r - l > 1:
    mid = (l + r) // 2
    count = h(mid)
    # print(mid, count)
    if count >= K:
        r = mid
    else:
        l = mid
print(r)

Submission status: Runtime Error

Solution code:
# 片方、しゃくとりにして高速化
from bisect import bisect_left, bisect_right

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

zero_num = bisect_right(A, 0) - bisect_left(A, 0)
minus_num = bisect_left(A, 0)
plus_num = n - (zero_num + minus_num)
AP = A[zero_num + minus_num :]
AM = A[:minus_num]
RAM = AM[::-1]
plus = plus_num * (plus_num - 1) // 2 + minus_num * (minus_num - 1) // 2
zero = zero_num * (zero_num - 1) // 2 + zero_num * (n - zero_num)
minus = plus_num * minus_num

# ↑ここまでで正負の積の数をそれぞれ求めておく。


def count(x):
    cnt = 0
    if x > 0:
        right = plus_num
        for left in range(plus_num):
            seki = AP[left] * AP[right - 1]
            while seki > x and right > 0:
                right -= 1
                seki = AP[left] * AP[right - 1]
            cnt += right
        for i in range(plus_num):
            if AP[i] ** 2 <= x:
                cnt -= 1
        right = minus_num
        for left in range(minus_num):
            seki = RAM[left] * RAM[right - 1]
            while seki > x and right > 0:
                right -= 1
                seki = RAM[left] * RAM[right - 1]
            cnt += right
        for i in range(minus_num):
            if RAM[i] ** 2 <= x:
                cnt -= 1
        cnt //= 2
        cnt += minus + zero
    elif x < 0:
        right = minus_num
        for left in range(plus_num):
            seki = AP[left] * AM[right - 1]
            while seki > x and right > 0:
                right -= 1
                seki = AP[left] * RAM[right - 1]
            cnt += right
    else:
        cnt = minus + zero
    return cnt


ok = 10 ** 20
ng = -(10 ** 20)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if count(mid) >= k:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Runtime Error

Solution code:
# 片方、しゃくとりにして高速化
from bisect import bisect_left, bisect_right

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

zero_num = bisect_right(A, 0) - bisect_left(A, 0)
minus_num = bisect_left(A, 0)
plus_num = n - (zero_num + minus_num)
AP = A[zero_num + minus_num :]
AM = A[:minus_num]
RAM = AM[::-1]
plus = plus_num * (plus_num - 1) // 2 + minus_num * (minus_num - 1) // 2
zero = zero_num * (zero_num - 1) // 2 + zero_num * (n - zero_num)
minus = plus_num * minus_num

# ↑ここまでで正負の積の数をそれぞれ求めておく。


def count(x):
    cnt = 0
    if x > 0:
        right = plus_num  # 半開区間で考えるので[0,1)から始める
        for left in range(plus_num):
            seki = AP[left] * AP[right - 1]
            while seki > x and right > 0:
                right -= 1
                seki = AP[left] * AP[right - 1]
            cnt += right
        for i in range(plus_num):
            if AP[i] ** 2 <= x:
                cnt -= 1
        right = minus_num
        for left in range(minus_num):
            seki = RAM[left] * RAM[right - 1]
            while seki > x and right > 0:
                right -= 1
                seki = RAM[left] * RAM[right - 1]
            cnt += right
        for i in range(minus_num):
            if RAM[i] ** 2 <= x:
                cnt -= 1
        cnt //= 2
        cnt += minus + zero
    elif x < 0:
        right = 1  # 半開区間で考えるので[0,1)から始める
        for left in range(plus_num):
            seki = AP[left] * RAM[right - 1]
            while seki > x and right < minus_num:
                right += 1
                seki = AP[left] * RAM[right - 1]
            cnt += minus_num - right + 1
    else:
        cnt = minus + zero
    return cnt


ok = 10 ** 20
ng = -(10 ** 20)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if count(mid) >= k:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Runtime Error

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N,K = MI()
A = LI()
minus,zero,plus = [], [], []
for i in A:
    if i<0:
        minus.append(i)
    elif i==0:
        zero.append(i)
    else:
        plus.append(i)
m = len(minus)
p = len(plus)
z = len(zero)
minus.sort()
plus.sort()

def count_lower_negpos(v): #pos*negでv以下のペアを数える
    m_idx = 0
    p_idx = 0
    ans = 0
    while True:
        val = minus[m_idx]*plus[p_idx]
        if val < v:
            ans += p - p_idx
            m_idx += 1
            if m_idx>m-1:
                break
        else:
            p_idx += 1
            if p_idx>p-1:
                break
    return ans

def count_lower_pospos(v): #pos同士でv以下のペアを数える
    left = 0
    right = p-1
    ans = 0
    while True:
        val = plus[left]*plus[right]
        if val < v:
            ans += right - left
            left += 1
            if left>=right:
                break
        else:
            right -= 1
            if left>=right:
                break
    return ans

def count_lower_negneg(v): #neg同士でv以下のペアを数える
    left = 0
    right = m-1
    ans = 0
    while True:
        val = minus[left]*minus[right]
        if val < v:
            ans += right - left
            right -= 1
            if left>=right:
                break
        else:
            left += 1
            if left>=right:
                break
    return ans


if K <= m*p: #答えがマイナス
    l = minus[0]*plus[-1]
    r = 0
    while l+1<r:
        x = (l+r)//2
        if count_lower_negpos(x) < K:
            l = x
        else:
            r = x
    print(l)


elif K <= m*p+z*(m+p)+z*(z-1)//2: #答えがゼロ
    print(0)

else: #答えがプラス
    K = K - (m*p+z*(m+p)+z*(z-1)//2)
    l = 0
    r = 10**18+5
    while l+1<r:
        x = (l+r)//2
        if count_lower_pospos(x)+count_lower_negneg(x) < K:
            l = x
        else:
            r = x
    print(l)

Submission status: Runtime Error

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N,K = MI()
A = LI()
minus,zero,plus = [], [], []
for i in A:
    if i<0:
        minus.append(i)
    elif i==0:
        zero.append(i)
    else:
        plus.append(i)
m = len(minus)
p = len(plus)
z = len(zero)
minus.sort()
plus.sort()

def count_lower_negpos(v): #pos*negでv以下のペアを数える
    m_idx = 0
    p_idx = 0
    ans = 0
    while True:
        val = minus[m_idx]*plus[p_idx]
        if val < v:
            ans += p - p_idx
            m_idx += 1
            if m_idx>m-1:
                break
        else:
            p_idx += 1
            if p_idx>p-1:
                break
    return ans

def count_lower_pospos(v): #pos同士でv以下のペアを数える
    left = 0
    right = p-1
    ans = 0
    while True:
        val = plus[left]*plus[right]
        if val < v:
            ans += right - left
            left += 1
            if left>=right:
                break
        else:
            right -= 1
            if left>=right:
                break
    return ans

def count_lower_negneg(v): #neg同士でv以下のペアを数える
    left = 0
    right = m-1
    ans = 0
    while True:
        val = minus[left]*minus[right]
        if val < v:
            ans += right - left
            right -= 1
            if left>=right:
                break
        else:
            left += 1
            if left>=right:
                break
    return ans


if K <= m*p: #答えがマイナス
    l = minus[0]*plus[-1]
    r = 0
    while l+1<r:
        x = (l+r)//2
        if count_lower_negpos(x) < K:
            l = x
        else:
            r = x
    print(l)


elif K <= m*p+z*(m+p)+z*(z-1)//2: #答えがゼロ
    print(0)

else: #答えがプラス
    K = K - (m*p+z*(m+p)+z*(z-1)//2)
    l = 0
    r = max(minus[0]**2,plus[-1]**2)
    while l+1<r:
        x = (l+r)//2
        if count_lower_pospos(x)+count_lower_negneg(x) < K:
            l = x
        else:
            r = x
    print(l)

Submission status: Runtime Error

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N,K = MI()
A = LI()
minus,zero,plus = [], [], []
for i in A:
    if i<0:
        minus.append(i)
    elif i==0:
        zero.append(i)
    else:
        plus.append(i)
m = len(minus)
p = len(plus)
z = len(zero)
minus.sort()
plus.sort()

def count_lower_negpos(v): #pos*negでv以下のペアを数える
    m_idx = 0
    p_idx = 0
    ans = 0
    while True:
        val = minus[m_idx]*plus[p_idx]
        if val < v:
            ans += p - p_idx
            m_idx += 1
            if m_idx>m-1:
                break
        else:
            p_idx += 1
            if p_idx>p-1:
                break
    return ans

def count_lower_pospos(v): #pos同士でv以下のペアを数える
    left = 0
    right = p-1
    ans = 0
    while True:
        val = plus[left]*plus[right]
        if val < v:
            ans += right - left
            left += 1
            if left>=right:
                break
        else:
            right -= 1
            if left>=right:
                break
    return ans

def count_lower_negneg(v): #neg同士でv以下のペアを数える
    left = 0
    right = m-1
    ans = 0
    while True:
        val = minus[left]*minus[right]
        if val < v:
            ans += right - left
            right -= 1
            if left>=right:
                break
        else:
            left += 1
            if left>=right:
                break
    return ans


if K <= m*p: #答えがマイナス
    l = minus[0]*plus[-1]
    r = 0
    while l+1<r:
        x = (l+r)//2
        if count_lower_negpos(x) < K:
            l = x
        else:
            r = x
    print(l)


elif K <= m*p+z*(m+p)+z*(z-1)//2: #答えがゼロ
    print(0)

else: #答えがプラス
    K = K - (m*p+z*(m+p)+z*(z-1)//2)
    print(K)
    l = 0
    r = max(minus[0]**2,plus[-1]**2)
    while l+1<r:
        x = (l+r)//2
        if count_lower_pospos(x)+count_lower_negneg(x) < K:
            l = x
        else:
            r = x
    print(l)

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop
N,K=map(int,input().split())
A=list(map(int,input().split()))

Am = []
A0 = []
Ap = []
for i in A:
    if i<0:
        Am.append(i)
    elif i ==0:
        A0.append(i)
    else:
        Ap.append(i)
        
D=[]
# -*+の方が小さい
if len(Am)*len(Ap)>=K:
    Am.sort()
    Ap.sort(reverse=True)
    hq = []
    arg_hash = {}
    val = Am[0]*Ap[0]
    heappush(hq,(val,0,0))
    
    ans=0
    for i in range(K):
        ans,m,p = heappop(hq)
        arg_m = (m+1,p)
        arg_p = (m,p+1)
        if m<len(Am)-1 and arg_m not in arg_hash:
            arg_hash[arg_p]=1
            heappush(hq,(Am[m+1]*Ap[p],)+arg_m)
        if p<len(Ap)-1 and arg_p not in arg_hash:
            arg_hash[arg_p]=1
            heappush(hq,(Am[m]*Ap[p+1],)+arg_p)
    print(ans)
elif len(Am)*len(Ap)<K<=len(Am)*len(Ap)+len(A0)*(len(Am)+len(Ap))+len(A0)*(len(A0)-1)//2:
    print(0)
else:
    l=K-len(Am)*len(Ap)-len(A0)*(len(Am)+len(Ap))-len(A0)*(len(A0)-1)//2
    Am.sort(reverse=True)
    Ap.sort()
    for p in range(1,len(Am)+1):
        for q in range(p+1,len(Am)+1):
            if p*q//2<=l:
                D.append(Am[p-1]*Am[q-1])
    for p in range(1,len(Ap)+1):
        for q in range(p+1,len(Ap)+1):
            if p*q//2<=l:
                D.append(Ap[p-1]*Ap[q-1])
    D.sort()
    print(D[l-1])