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 sys
input=sys.stdin.readline
import bisect
def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    print(A)

    left_target=-10**18
    right_target=10**18
    while left_target<right_target-1:
        mid_target=(left_target+right_target)//2
        count=0
        for i in range(N-1):
            a=A[i]
            if a<0:
                if mid_target/a!=mid_target//a:
                    count+=(N-i-1)-bisect.bisect_right(A[i+1:],mid_target/a)
                else:
                    count+=(N-i-1)-bisect.bisect_right(A[i+1:],mid_target//a)
            elif a==0:
                if mid_target>0:
                    count+=(N-(i+1))
            elif a>0:
                if mid_target/a!=mid_target//a:
                    count+=bisect.bisect_left(A[i+1:],mid_target/a)
                else:
                    count+=bisect.bisect_left(A[i+1:],mid_target//a)
        if count<K:
            left_target=mid_target
        else:
            right_target=mid_target
        #print("m:",mid_target,"c:",count)
    print(left_target)

if __name__=="__main__":
    main()

import sys
input=sys.stdin.readline
"""
def binary_search_m(i,a,N,A,mid_target):
    left_index=-1
    right_index=N
    while left_index<right_index-1:
        mid_index=(left_index+right_index)//2
        if a*A[mid_index]>=mid_target:
            left_index=mid_index
        else:
            right_index=mid_index
    return N-(left_index+1)

def binary_search_p(i,a,N,A,mid_target):
    left_index=-1
    right_index=N
    while left_index<right_index-1:
        mid_index=(left_index+right_index)//2
        if a*A[mid_index]<mid_target:
            left_index=mid_index
        else:
            right_index=mid_index
    return left_index+1
"""
def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()

    left_target=-10**18
    right_target=10**18+1
    while left_target<right_target-1:
        mid_target=(left_target+right_target)//2
        count=0
        for i in range(N):
            a=A[i]
            if a<0:
                left_index=-1
                right_index=N
                while left_index<right_index-1:
                    mid_index=(left_index+right_index)//2
                    if a*A[mid_index]>=mid_target:
                        left_index=mid_index
                    else:
                        right_index=mid_index
                count+=N-(left_index+1)
            elif a>=0:
                left_index=-1
                right_index=N
                while left_index<right_index-1:
                    mid_index=(left_index+right_index)//2
                    if a*A[mid_index]<mid_target:
                        left_index=mid_index
                    else:
                        right_index=mid_index
                count+=left_index+1

            if a*a<mid_target:
                count-=1
        count//=2
        if count<K:
            left_target=mid_target
        else:
            right_target=mid_target
    print(left_target)

from sys import stdin
import numpy as np
def main():
    
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=np.array(readline().strip().split(),dtype="int64")
    
    a.sort()
    neg=a[a<0]
    neg_p=neg**2
    zero=a[a==0]
    pos=a[a>0]
    pos_p=pos**2
    l=-10**18-1
    r=10**18
    while l<r-1:
        x=(l+r)//2
        cnt=0
        if neg.size>0:
            cnt+=(a.size-np.searchsorted(a,(x+neg+1)//neg)).sum()
            cnt-=neg_p[neg_p<=x].size
        if zero.size>0:
            if x>=0:
                cnt+=(a.size-1)*zero.size
        if pos.size>0:
            cnt+=np.searchsorted(a,x//pos,side="right").sum()
            cnt-=pos_p[pos_p<=x].size

        cnt//=2
        if cnt>=k: r=x
        else: l=x

    print(r)

if __name__=="__main__":
    main()

Verdicts: Wrong Answer

Wrong Answer

Accepted