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 numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A = 0]
nega = A[A < 0]


def check(x):
    count = 0  
    if x >= 0:
        count += len(zero) * N  
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += np.searchsorted(A, (-x - 1) // nega, side = 'left').sum()  
    count -= np.count_nonzero(A * A <= x)  
    return count // 2  


low = -10 ** 18
high = 10 ** 18
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid) >= K:
        low = mid
    else:
        high = mid

print(low)


import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A == 0]
nega = A[A < 0]


def check(x):
    count = 0  
    if x >= 0:
        count += len(zero) * N  
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += np.searchsorted(A, (-x - 1) // nega, side = 'left').sum()  
    count -= np.count_nonzero(A * A <= x)  
    return count // 2  


low = -10 ** 18
high = 10 ** 18
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid) >= K:
        low = mid
    else:
        high = mid

print(low)


import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A == 0]
nega = A[A < 0]


def check(x):
    count = 0  
    if x >= 0:
        count += len(zero) * N  
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += np.searchsorted(A, (-x - 1) // (-nega), side = 'left').sum()  
    count -= np.count_nonzero(A * A <= x)  
    return count // 2  


low = -10 ** 18
high = 10 ** 18
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid) < K:  # OK
        low = mid
    else:               # NG
        high = mid

print(high)


import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A == 0]
nega = A[A < 0]


def check(x):
    count = 0  
    if x >= 0:
        count += len(zero) * N  
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += np.searchsorted(A, (-x - 1) // (-nega), side = 'right').sum()  
    count -= np.count_nonzero(A * A <= x)  
    return count // 2  


low = -10 ** 18
high = 10 ** 18
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid) < K:  # OK
        low = mid
    else:               # NG
        high = mid

print(high)


import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A == 0]
nega = A[A < 0]


def check(x):
    count = 0  
    if x >= 0:
        count += len(zero) * N  
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += (N - np.searchsorted(A, (-x - 1) // (-nega), side = 'right')).sum()  
    count -= np.count_nonzero(A * A <= x)  
    return count // 2  


low = -10 ** 18
high = 10 ** 18
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid) < K:  # OK
        low = mid
    else:               # NG
        high = mid

print(high)


Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Accepted