Problem: 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?

Submission attempts (in order):
import sys
import bisect
sys.setrecursionlimit(10 ** 7)

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

A.sort()
minus = bisect.bisect_left(A, 0)
plus = bisect.bisect_right(A, 0)
zero = plus - minus

negative = minus * plus
positive = (plus * (plus - 1) // 2) + (minus * (minus - 1) // 2)
zeros = (N * N - 1) // 2 - (positive + negative)

if K <= negative:
    A0 = A[:minus]
    A1 = A[plus:]
    A1.sort()

    left = -(10 ** 18)
    right = 0

    print(A0)
    print(A1)

    def test(val):
        cnt = 0
        lg = len(A0)
        for a0 in A0:
            p = val // a0
            cnt += lg - bisect.bisect_left(A1, p)
        return cnt

    while (right - left) > 1:
        mid = (left + right) // 2
        res = test(mid)
        print("mid,cnt", mid, res)
        if res >= K:
            right = mid
        else:
            left = mid

    print(left)
    exit()


elif negative < K and K <= (negative + zeros):
    print(0)
    exit()
else:
    A0 = A[:minus]
    A1 = A[plus:]

    A0.sort(reverse=True)

    K -= zeros + negative

    def test(val):
        cnt = 0
        lg = len(A0)
        if lg > 1:
            for i in ren(lg - 1):
                l = i+1
                r = len(lg) - 1

                a0 = A0[i]
                if val < a0 * A0[l]:
                    continue

                while (r - l) > 1:
                    m = (l + r) // 2
                    if val < a0 * A0[m]:
                        r = m
                    else:
                        l = m

                cnt += l

        lg = len(A1)
        if lg > 1:
            for i in ren(lg - 1):
                l = i+1
                r = len(lg) - 1

                a0 = A0[i]
                if val < a0 * A0[l]:
                    continue

                while (r - l) > 1:
                    m = (l + r) // 2
                    if val < a0 * A0[m]:
                        r = m
                    else:
                        l = m

                cnt += l
        return cnt

    left = 0
    right = 10 ** 18

    while (right - left) > 1:
        mid = (left + right) // 2
        res = test(mid)
        if res >= K:
            right = mid
        else:
            left = mid

    print(left)
    exit()


import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)

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


def test(x):
    cnt = 0

    if x >= 0:
        cnt += len(zero) * N

    cnt += np.searchsorted(A, x // pos, side='right').sum()
    cnt += (N - np.searchsorted(A, (-x - 1) // -neg, side='right')).sum()
    cnt -= np.count_nonzero(A * A <= x)

    cnt //= 2

    return K <= cnt


l = -(10 ** 19)  # NG
r = 10 ** 19  # OK

while l + 1 != r:
    mid = (l + r) // 2

    if test(mid):
        r = mid
    else:
        l = mid

print(r)


Verdicts: Runtime Error

Accepted