Problem p02774 (python)

Fixed submission:
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_rev = A[:num_neg] # 絶対値が大きいものからになるようにソート
A_pos = A[num_neg + num_zero:] # 絶対値が小さいものからになるようにソート

A_neg = A_neg_rev[::-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 syakutori_pos(arr, mid):
    if len(arr) == 0:
        return 0
    cnt = 0
    l = 0
    r = len(arr) - 1
    while l < r:
        if arr[l] * arr[r] <= mid:
            cnt += r - l
            l += 1
        else:
            r -= 1
    return cnt

# 値が負になるとき
def syakutori_neg(arr_pos, arr_neg, mid):
    if len(arr_pos) == 0 or len(arr_neg) == 0:
        return 0
    arr = arr_neg + arr_pos
    cnt = 0
    l = 0
    r = len(arr) - 1
    while l < len(arr_neg) and r >= len(arr_neg):
        if arr[l] * arr[r] <= mid:
            cnt += r - len(arr_neg) + 1
            l += 1
        else:
            r -= 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 += syakutori_pos(A_pos, mid) + syakutori_pos(A_neg, mid)
    elif mid == 0:
        cnt += cnt_zero
        cnt += cnt_neg
    else:
        cnt += syakutori_neg(A_pos_rev, A_neg_rev, mid)
    if cnt >= K:
        ok = mid
    else:
        ng = mid

print(ok)

Buggy submission (verdict: Runtime Error):
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)