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
from numba import njit
N,K=[int(_) for _ in input().split()]
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()


@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,0- (-target)//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))


import numpy as np
from numba import njit


@njit
def main(I):
    N,K=I[0],I[1]
    A = np.array(I[2:],dtype=int)
    A.sort()
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

I=np.array([int(_) for _ in open(0).read().split()],dtype=int)
print(main(I))

import bisect
import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()
#A=sorted([int(_) for _ in input().split()])



@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    # Min x for check(x) == True
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                    cnt+=d
                    continue
                q,r=divmod(target,a)
                if a < 0:
                    
                    
                    il = np.searchsorted(A,q+(r>0),side='left')
                    
                    d = max(i - il, 0)
                else:
                    
                    
                    ir = np.searchsorted(A,q,side='right')
                    
                    d = min(ir, i)
                #print(target,a,d)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))


import bisect
import numpy as np
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()
#A=sorted([int(_) for _ in input().split()])



def check(target):
    cnt=0
    for i, a in enumerate(A):
        if a < 0:
            
            il = np.searchsorted(A,target/a,side='left')
            
            d = max(i - il, 0)
        elif a > 0:
            
            ir = np.searchsorted(A,target/a,side='right')
            
            d = min(ir, i)
        else:
            d = i if target >= 0 else 0
        #print(target,a,d)
        cnt+=d
    return cnt>=K

lb = -10**18-1
rb = 10 ** 18 + 1
# Min x for check(x) == True
while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(mid):
        rb = mid
    else:
        lb = mid
print(rb)




import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
if N==4:
    raise
A = np.array([int(_) for _ in input().split()],dtype=int)
#A.sort()
#A=sorted([int(_) for _ in input().split()])



@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    # Min x for check(x) == True
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                    cnt+=d
                    continue
                q,r=divmod(target,a)
                if a < 0:
                    
                    
                    il = np.searchsorted(A,q+(r>0),side='left')
                    
                    d = max(i - il, 0)
                else:
                    
                    
                    ir = np.searchsorted(A,q,side='right')
                    
                    d = min(ir, i)
                #print(target,a,d)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))


import numpy as np
from numba import njit
N, K = [int(_) for _ in input().split()]
A = np.array(sorted([int(_) for _ in input().split()]))


@njit
def solve(N, K, A):
    lb = -10**18 - 1
    rb = 10**18 + 1

    def check(x):
        
        cnt = 0
        for i, a in enumerate(A):
            
            l = 0
            r = i
            if a > 0:
                l = -1
                r = np.searchsorted(A, x // a, side='right')
            elif a < 0:
                l = np.searchsorted(A, 0 - x // (-a), side='left')
                r = N + 1
            elif x < 0:
                r = 0
            l = min(max(l, 0), i)
            r = max(min(r, i), 0)
            cnt += r - l
        return cnt >= K

    # Min x for check(x) == True
    while rb - lb > 1:
        mid = (rb + lb) // 2
        if check(mid):
            rb = mid
        else:
            lb = mid
    print(rb)


solve(N, K, A)


Verdicts: Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted