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 bisect
import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
A = np.sort(A)

Aneg = A[A < 0]
Azero = A[A == 0]
Apos = A[A > 0]

neg = len(Aneg)
zero = len(Azero)
pos = len(Apos)

Nneg = neg * pos
Npos = 0
if neg > 0:
    Npos += neg * (neg - 1) // 2
if pos > 0:
    Npos += pos * (pos - 1) // 2
Nzero = N * (N - 1) // 2 - Npos - Nneg
print(Nneg, Npos, Nzero)


def C(N, ar):
    if len(ar) <= 1:
        return 0
    tmp = np.arange(len(ar))+1
    n = np.searchsorted(ar, N / ar, side="left")
    return (len(ar)-np.maximum(n, tmp)).sum()


def C1(N, ar1, ar2):
    tmp = np.arange(len(ar1))+1
    n = np.searchsorted(ar1, N / ar2, side="left")
    return (len(ar1)-np.maximum(n, tmp)).sum()


def bs_Neg():
    l, r = -10 ** 20, 0
    while r - l > 1:
        m = (r - l) // 2
        num = C1(m, Apos, Aneg)
        if num < K:
            r = m
        else:
            l = m
    return l


def bs_Pos(K):
    l, r = 0, 10 ** 20
    while r - l > 1:
        m = (r - l) // 2
        num = C(m, Apos) + C(m, Aneg)
        if num < K:
            r = m
        else:
            l = m
    return l


if K <= Nneg:
    ans = bs_Neg()
elif K <= Nneg + Nzero:
    ans = 0
else:
    K = K-Nneg-Nzero
    ans = bs_Pos(K)

print(ans)


import numpy as np


def get_Negative(K, pos, neg):
    K = len(pos) * len(neg) - K + 1
    l = 0
    r = 10 ** 18 + 10
    while r - l > 1:
        m = (l + r) // 2
        target = m // pos
        x = np.searchsorted(neg, target, side="right").sum()
        if x >= K:
            r = m
        else:
            l = m
    return -r


def get_Positive(K, pos, neg):
    l = 0
    r = 10 ** 18 + 10
    tmp_pos = np.arange(len(pos))
    tmp_neg = np.arange(len(neg))
    while r - l > 1:
        m = (r + l) // 2
        cnt = 0
        if len(pos) > 1:
            t1 = m // pos
            x1 = np.searchsorted(pos, t1, side="right")
            x1 = np.maximum(0, x1 - tmp_pos - 1)
            cnt += x1.sum()
        if len(neg) > 0:
            t2 = m // neg
            x2 = np.searchsorted(neg, t2, side="right")
            x2 = np.maximum(0, x2 - tmp_neg - 1)
            cnt += x2.sum()
        if cnt >= K:
            r = m
        else:
            l = m
    return r


def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)

    positive = A[A > 0]
    negative = -A[A < 0]
    positive.sort()
    negative.sort()

    Npos = len(positive)
    Nneg = len(negative)
    Nzero = N - Npos - Nneg

    P_neg = Npos * Nneg
    P_pos = 0
    if Npos:
        P_pos += Npos * (Npos - 1) // 2
    if Nneg:
        P_pos += Nneg * (Nneg - 1) // 2
    P_zero = N * (N - 1) // 2 - P_pos - P_neg

    if K <= P_neg:
        ans = get_Negative(K, positive, negative)
        return ans
    K -= P_neg
    if K <= P_zero:
        return 0
    K -= P_zero
    ans = get_Positive(K, positive, negative)
    return ans


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

Verdicts: Runtime Error

Accepted