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):
def bin_search(array, num):
    if array[0] > num: return 0
    if array[-1] < num: return len(array)
    mx = len(array) - 1
    mn = 0
    while mx >= mn :
        median = mn + (mx - mn)//2 
        target = array[median]
        if target == num:
            return median + 1
        elif target > num:
            mx = median - 1
        else:
            mn = median + 1

    return median + 1

n, k = map(int, input().split())
arr = list(map(int, input().split()))
# arr = list(map(int, '5 4 3 2 -1 0 0 0 0 0'.split()))
arr.sort()

n_int = 0
n_range = [None, None]
z_int = 0
zero_range = [None, None]
p_int = 0
p_range = [None, None]

for idx, i in enumerate(arr):
    if i < 0:
        n_int += 1
        if n_range[0] == None: n_range[0] = idx
        n_range[1] = idx + 1
    elif i == 0:
        z_int += 1
        if zero_range[0] == None: zero_range[0] = idx
        zero_range[1] = idx + 1
    
    else:
        p_int += 1
        if p_range[0] == None: p_range[0] = idx
        p_range[1] = idx + 1

negative = n_int * p_int
zero = z_int * (n_int + p_int) + (z_int*(z_int-1)//2)
positive = (p_int*(p_int-1)//2) + (n_int*(n_int-1)//2)


if k > zero + negative:
    n_list = arr[n_range[0]: n_range[1]]
    p_list = arr[p_range[0]: p_range[1]]

    goal = k - zero - negative

    if len(n_list) < 2:
        mn = p_list[0] * p_list[1]
        mx = p_list[-1] * p_list[-2]
    
    elif len(p_list) <2:
        mn = n_list[-1] * n_list[-2]
        mx = n_list[0] * n_list[1]
     
    else:
        mn = min (n_list[-1]*n_list[-2], p_list[0]*p_list[1])
        mx = max (n_list[0]*n_list[1], p_list[-1]*p_list[-2])

    while mx >= mn:
        m = mn + (mx - mn)//2
        under = 0
        p_under = 0
        for a in p_list:
            thres = m//a
            score = bin_search(p_list, thres)
            if a*a <= m:
                score -= 1
            p_under += score
        p_under /= 2
        under += p_under
        
        n_under = 0
        for a in n_list:
            thres = m//a
            score = n_int - bin_search(n_list, thres - 1)
            if a*a <= m:
                score -= 1
            n_under += score
        n_under /= 2
        under += n_under

        if under >= goal:
            mx = m - 1
        
        else:
            mn = m + 1
    
    print(m)




def bin_search(array, num):
    if array[0] > num: return 0
    if array[-1] < num: return len(array)
    mx = len(array) - 1
    mn = 0
    while mx >= mn :
        median = mn + (mx - mn)//2 
        target = array[median]
        if target == num:
            return median + 1
        elif target > num:
            mx = median - 1
        else:
            mn = median + 1

    return median + 1

n, k = map(int, input().split())
arr = map(int, input().split())
# arr = list(map(int, '5 4 3 2 -1 0 0 0 0 0'.split()))
arr.sort()

n_int = 0
n_range = [None, None]
z_int = 0
zero_range = [None, None]
p_int = 0
p_range = [None, None]

for idx, i in enumerate(arr):
    if i < 0:
        n_int += 1
        if n_range[0] == None: n_range[0] = idx
        n_range[1] = idx + 1
    elif i == 0:
        z_int += 1
        if zero_range[0] == None: zero_range[0] = idx
        zero_range[1] = idx + 1
    
    else:
        p_int += 1
        if p_range[0] == None: p_range[0] = idx
        p_range[1] = idx + 1

negative = n_int * p_int
zero = z_int * (n_int + p_int) + (z_int*(z_int-1)//2)
positive = (p_int*(p_int-1)//2) + (n_int*(n_int-1)//2)


if k > zero + negative:
    n_list = arr[n_range[0]: n_range[1]]
    p_list = arr[p_range[0]: p_range[1]]

    goal = k - zero - negative

    if len(n_list) < 2:
        mn = p_list[0] * p_list[1]
        mx = p_list[-1] * p_list[-2]
    
    elif len(p_list) <2:
        mn = n_list[-1] * n_list[-2]
        mx = n_list[0] * n_list[1]
     
    else:
        mn = min (n_list[-1]*n_list[-2], p_list[0]*p_list[1])
        mx = max (n_list[0]*n_list[1], p_list[-1]*p_list[-2])

    while mx >= mn:
        m = mn + (mx - mn)//2
        under = 0
        p_under = 0
        for a in p_list:
            thres = m//a
            score = bin_search(p_list, thres)
            if a*a <= m:
                score -= 1
            p_under += score
        p_under /= 2
        under += p_under
        
        n_under = 0
        for a in n_list:
            thres = m//a
            score = n_int - bin_search(n_list, thres - 1)
            if a*a <= m:
                score -= 1
            n_under += score
        n_under /= 2
        under += n_under

        if under >= goal:
            mx = m - 1
        
        else:
            mn = m + 1
    
    print(m)




def bin_search(array, num):
    if array[0] > num: return 0
    if array[-1] < num: return len(array)
    mx = len(array) - 1
    mn = 0
    while mx >= mn :
        median = mn + (mx - mn)//2 
        target = array[median]
        if target == num:
            return median + 1
        elif target > num:
            mx = median - 1
        else:
            mn = median + 1

    return median + 1

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

mn = -10 ** 18 - 1
mx = 10 ** 18 + 1

while mx >= mn:
    m = mn + (mx - mn)//2

    score = 0
    for a in arr:
        if a > 0:
            thres = m//a
            score += bin_search(arr, thres)
        
        elif a < 0:
            thres = m//a
            score += n - bin_search(arr, thres-1)
        
        else:
            if m >= 0:
                score += n

        if a <= m: score -= 1
    
    assert score % 2 == 0

    score /= 2    
    under = score
    if under < k:
        mn = m
    
    else:
        mx = m

print(m)



import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

A_pos = A[A > 0]
A_neg = A[A < 0]
A_zero = A[A == 0]


def n_comb_lt(c):
    n_comb = 0
    
    target = c // A_pos  
    n_comb += np.searchsorted(A, target, side="right").sum()

    
    n_comb += n * len(A_zero) if c >= 0 else 0

    
    target = -(-c // A_neg)
    n_comb += (n - np.searchsorted(A, target, side="left")).sum()

    
    n_comb -= A[A * A <= c].size
    n_comb //= 2

    return n_comb

ok = -10 ** 18 - 1
ng = 10 ** 18 + 1



while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        ok = mid
    else:
        ng = mid

print(ok)


Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted