Problem:


Score: 400 points

Problem Statement

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?

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \frac{N(N-1)}{2}

-10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 3
3 3 -4 -2

Sample Output 1

-6

There are six ways to form a pair. The products of those pairs are 9, -12, -6, -12, -6, 8.

Sorting those numbers in ascending order, we have -12, -12, -6, -6, 8, 9. The third number in this list is -6.

Sample Input 2

10 40
5 4 3 2 -1 0 0 0 0 0

Sample Output 2

6

Sample Input 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

Sample Output 3

448283280358331064



Sample input:
4 3
3 3 -4 -2


Sample output:
-6

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

INF = pow(10, 18) + 1

l = -INF
r = INF

while l+1 < r:
  x = (l+r)//2
  total = 0
  for i in range(n):
    if a[i] < 0:
      left = -1
      right = n
      while left+1 < right:
        c = (left+right)//2
        if a[c]*a[i] < x:
          right = c
        else:
          left = c
      total += n-right
    else:
      left = -1
      right = n
      while left+1 < right:
        c = (left+right)//2
        if a[c]*a[i] < x:
          left = c
        else:
          right = c
      total += right
    if a[i]*a[i] < x:
      total -= 1
  total = total // 2
  if total < k:
    l = x
  else:
    r = x
print(x-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
from math import floor, ceil

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

def less(x):
    res = 0
    for i in range(N):
        e = A[i]
        if e < 0:
            res += i - bisect_right(A, floor(x / e), 0, i)
        elif e > 0:
            res += bisect_left(A, ceil(x / e), 0, i)
        elif x > 0:
            res += i
    return res

l = - (10 ** 18 + 1)
r = - l
while l + 1 < r:
    m = (l + r) // 2
    if less(m) < K:
        l = m
    else:
        r = m
print(l)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    ans = - 10**18

    from bisect import bisect_left, bisect_right


    N, K = LMIIS()
    A = LMIIS()
    A.sort()
    num_negative = bisect_left(A,0)
    num_zero = bisect_right(A,0) - num_negative
    num_positive = N - num_negative - num_zero
    B = A[:num_negative]
    

    
    inf = 10**18+1
    u = inf
    l = -inf
    # 答えが負
    if num_negative * num_positive >= K:
        def f(x):
            ans = 0
            for i in range(num_negative):
                for j in range(N-1,num_negative+num_zero-1,-1):
                    if A[i]*A[j] < x:
                        ans += 1
                    else:
                        break
            return ans
        # prev = m = (u+l)//2
        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if f(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        print(max_m)
        return m

    # 答えがゼロ
    elif num_negative * num_positive + num_negative * num_zero + num_positive * num_zero + num_zero*(num_zero-1)//2 >= K:
        print(0)
        return

    # 答えが正
    else:
        K-=num_negative * num_positive + num_negative * num_zero + num_positive * num_zero + num_zero*(num_zero-1)//2
        def f(x):
            ans = 0
            for i in range(num_negative-1,0,-1):
                for j in range(i-1,-1,-1):
                    
                    if A[i]*A[j] < x:
                        ans += 1
                    else:
                        break
            for i in range(num_negative+num_zero,N-1):
                for j in range(i+1,N):
                    if A[i]*A[j] < x:
                        ans += 1
                    else:
                        break
            return ans
        min_m = inf
        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            fm = f(m)
            if fm >= K:
                u = m
            else:
                min_m = min(min_m,m)
                max_m = max(max_m,m)
                l = m
        print(min_m,max_m)
        return

        #Bは負数
        # B.sort(reverse=True)
        # K -= num_negative * num_not_negatibe
        # dbg(K)
        # for i in range(1,K):
        #     j = K-i
        #     ans = min(ans,B[i]*B[j])
        # B_remain = A[num_negative:]
        # for i in range(1,K):
        #     j = K-1
        #     ans = min(ans,B_remain[i]*B_remain[j])
        # print(ans)
        return
        




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]

#cn = len(mn)
##cp = len(mp)
#cz = len(mz)
#tcn = cn*cp

#if cn*cp < K <= cn*cp + (N-cz)*cz + cz*(cz-1)//2:
#    print(0)
#    exit(0)

M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    a+=len(mz)*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
#print(M,m)
print(M)

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]

cn = len(mn)
cp = len(mp)
cz = len(mz)
tcn = cn*cp

if cn*cp < K <= cn*cp + (N-cz)*cz + cz*(cz-1)//2:
    print(0)
    exit(0)

M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    a+=cz*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
#print(M,m)
print(M)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect, bisect_left

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    Minus = []
    zero = 0
    Plus = []
    MinusNum = 0
    PlusNum = 0
    for a in A:
        if a < 0: 
            Minus.append(a)
            MinusNum += 1
        elif a == 0: zero += 1
        else: 
            Plus.append(a)
            PlusNum += 1
    Minus.sort()
    Plus.sort()
    minusNumTotal = MinusNum * PlusNum
    zeroNumTotal = zero * (zero - 1) // 2 + zero * (MinusNum + PlusNum)
    plusNumTotal = MinusNum * (MinusNum - 1) // 2 + PlusNum * (PlusNum - 1) // 2
    allNum = N * (N - 1) // 2

    if K <= minusNumTotal: #Kが負の数の時の処理
        minNum = Minus[0] * Plus[-1]
        low, high = minNum, 0
        while high - low > 1:
            smaller = 0
            mid = (low + high) // 2
            for i, m in enumerate(Minus):
                plow, phigh = 0, PlusNum
                while phigh - plow > 1:
                    pmid = (plow + phigh) // 2
                    if Plus[pmid] * m <= mid: phigh = pmid
                    else: plow = pmid
                if plow == PlusNum - 1 and m * Plus[plow] > mid: plow += 1
                smaller += (PlusNum - plow)
            if smaller >= K: high = mid
            else: low = mid
        print(high)   

    elif minusNumTotal < K <= minusNumTotal + zeroNumTotal:
        print(0)
    else: #Kが正の数の時の処理Total - Kで判定するとやると楽?
        maxNum = 0
        if MinusNum > 1: maxNum = max(maxNum, Minus[0] * Minus[1])
        if PlusNum > 1: maxNum = max(maxNum, Plus[PlusNum - 1] * Plus[PlusNum - 2]) 
        low, high = 0, maxNum + 1
        while high - low > 1:
            mid = (low + high) // 2
            larger = 0
            if MinusNum > 1:
                for i, m in enumerate(Minus):
                    mlow, mhigh = 0, MinusNum
                    while mhigh - mlow > 1:
                        mmid = (mlow + mhigh) // 2
                        if m * Minus[mmid] >= mid: mlow = mmid
                        else: mhigh = mmid
                    if mlow > i: larger += (mlow - i)
            if PlusNum > 1:
                for i, p in enumerate(Plus):
                    plow, phigh = 0, PlusNum
                    while phigh - plow > 1:
                        pmid = (plow + phigh) // 2
                        if p * Plus[pmid] >= mid: phigh = pmid
                        else: plow = pmid
                    if plow > i: larger += (PlusNum - plow - 1)
                    else: larger += (PlusNum - i - 1)
            if larger >= allNum - K + 1 : low = mid
            else: high = mid
        print(low)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect, bisect_left

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    Minus = []
    zero = 0
    Plus = []
    MinusNum = 0
    PlusNum = 0
    for a in A:
        if a < 0: 
            Minus.append(a)
            MinusNum += 1
        elif a == 0: zero += 1
        else: 
            Plus.append(a)
            PlusNum += 1
    Minus.sort()
    Plus.sort()
    minusNumTotal = MinusNum * PlusNum
    zeroNumTotal = zero * (zero - 1) // 2 + zero * (MinusNum + PlusNum)
    plusNumTotal = MinusNum * (MinusNum - 1) // 2 + PlusNum * (PlusNum - 1) // 2
    allNum = N * (N - 1) // 2

    if K <= minusNumTotal: #Kが負の数の時の処理
        minNum = Minus[0] * Plus[-1]
        low, high = minNum, 0
        while high - low > 1:
            smaller = 0
            mid = (low + high) // 2
            for i, m in enumerate(Minus):
                plow, phigh = 0, PlusNum
                while phigh - plow > 1:
                    pmid = (plow + phigh) // 2
                    if Plus[pmid] * m >= mid: plow = pmid
                    else: phigh = pmid
                smaller += (PlusNum - plow)
            if smaller <= K: low = mid
            else: high = mid
        print(low)   

    elif minusNumTotal < K <= minusNumTotal + zeroNumTotal:
        print(0)
    else: #Kが正の数の時の処理Total - Kで判定するとやると楽?
        maxNum = 0
        if MinusNum > 1: maxNum = max(maxNum, Minus[0] * Minus[1])
        if PlusNum > 1: maxNum = max(maxNum, Plus[PlusNum - 1] * Plus[PlusNum - 2]) 
        low, high = 0, maxNum + 1
        while high - low > 1:
            mid = (low + high) // 2
            larger = 0
            if MinusNum > 1:
                for i, m in enumerate(Minus):
                    mlow, mhigh = 0, MinusNum
                    while mhigh - mlow > 1:
                        mmid = (mlow + mhigh) // 2
                        if m * Minus[mmid] >= mid: mlow = mmid
                        else: mhigh = mmid
                    if mlow > i: larger += (mlow - i)
            if PlusNum > 1:
                for i, p in enumerate(Plus):
                    plow, phigh = 0, PlusNum
                    while phigh - plow > 1:
                        pmid = (plow + phigh) // 2
                        if p * Plus[pmid] >= mid: phigh = pmid
                        else: plow = pmid
                    if plow > i: larger += (PlusNum - plow - 1)
                    else: larger += (PlusNum - i - 1)
            if larger >= allNum - K + 1 : low = mid
            else: high = mid
        print(low)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
NK=list(map(int, input().split()))
A=list(map(int, input().split()))
N=NK[0]
List=[]
i=0
Len=len(A)
while i<Len:
    j=i+1
    while j < Len:
      List.append(A[i]*A[j])
      j=j+1
    i=i+1
List.sort()
print(List)
print(List[NK[1]-1])

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    if m > 0:
    	negative = np.array(A[:m], np.int64)
    else:
      	negative = np.array([], np.int64)
    if p > 0:
    	positive = np.array(A[-p:], np.int64)
    else:
      	positive = np.array([], np.int64)
    negative = -negative[::-1]
    # 負の数の操作(pythonの挙動)は頭がこんがらがるので正の数にして考える

    if K <= M:
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = p ** 2 - np.searchsorted(positive, (mid + negative - 1) // negative, side='left').sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        left = 0
        right = max(A[0] * A[1], A[-1] * A[-2])
        positive2 = positive ** 2
        negative2 = negative ** 2
        while left + 1 < right:
            mid = (left + right) // 2
            a = np.searchsorted(negative, mid // negative, side='right').sum() - (mid >= negative2).sum()
            b = np.searchsorted(positive, mid // positive, side='right').sum() - (mid >= positive2).sum()

            if (a + b) // 2 < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r

n, k, *a = map(int, sys.stdin.read().split())
a.sort()

def count(border):
    cnt = 0
            
    for i in range(n-1):
        l = a[i]
        if l == 0:
            if border >= 0:
                cnt += n - (i + 1)
        else:
            b = border / l
            if l < 0:
                j = bi_l(a, b)
                cnt += n - max(i+1, j)
            else:
                j = bi_r(a, b)
                cnt += max(j-(i+1), 0)
    return cnt

def main():
    lo = -10 ** 18 - 1
    hi = 10 ** 18 + 1
    while lo + 1 < hi:
        border = (lo + hi) // 2
        if count(border) >= k:
            hi = border
        else:
            lo = border
    return hi

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys,bisect
input = sys.stdin.readline

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))

    po = []
    ne = []
    for e in a:
        if e < 0:
            ne.append(-e)
        elif e > 0:
            po.append(e)
    po.sort()
    ne.sort()


    p = len(po)
    q = len(ne)
    zeros = n-p-q
    ok = 10**18
    ng = -ok-1
    while ok-ng > 1:
        mid = (ok+ng)//2

        #count
        cnt = 0
        if mid == 0:
            #{(negative),(zero,positive)}
            cnt += q*(n-q)
            #{(zero,positive),(zero,positive)}
            cnt += (n-q)*(n-q-1)//2
        elif mid > 0:
            #{(negative),(negative)}
            for i in range(q):
                j = bisect.bisect_right(ne,mid//ne[i])
                cnt += j
                if j >= i:
                    cnt -= 1
            
            

            #{(positive),(positive)}
            for i in range(p):
                j = bisect.bisect_right(po,mid//po[i])
                cnt += j
                if j >= i+1:
                    cnt -= 1
            cnt = cnt//2
            #{(negative),(zero,positive)}
            cnt += q*(n-q)
            
            #{(zero),(zero)}
            cnt += zeros*(zeros-1)//2

            #{(positive),(zero)}
            cnt += zeros*p
        else:
            #{(negative),(positive)}
            mid = -mid
            for i in range(p):
                j = bisect.bisect_left(ne,(mid-1)//po[i]+1)
                cnt += q-j
            mid = -mid
        
        if cnt >= k:
            ok = mid
        else:
            ng = mid
    print(ok)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import numpy as np
 
 
def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])
 
 
def main():
    read = sys.stdin.read
 
    N, K, *A = map(int, read().split())
 
    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z
 
    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = np.array(A[:m], np.int64)
    positive = np.array(A[-p:], np.int64)
    negative = -negative[::-1]
    # 負の数の操作(pythonの挙動)は頭がこんがらがるので正の数にして考える

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    A = np.array(A, np.int64)
    negative = A[A < 0]
    positive = A[A > 0]
    m = len(negative)
    p = len(positive)
    z = N - m - p

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = -negative[::-1]

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = np.array(A[:m], np.int64)
    positive = np.array(A[-p:], np.int64)
    negative = -negative[::-1]
    # 負の数の操作(pythonの挙動)は頭がこんがらがるので正の数にして考える

    if K <= M:
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, (mid + negative - 1) // negative, side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        left = 0
        right = max(A[0] * A[1], A[-1] * A[-2])
        positive2 = positive ** 2
        negative2 = negative ** 2
        while left + 1 < right:
            mid = (left + right) // 2
            a = np.searchsorted(negative, mid // negative, side='right').sum() - (mid >= negative2).sum()
            b = np.searchsorted(positive, mid // positive, side='right').sum() - (mid >= positive2).sum()

            if (a + b) // 2 < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = np.array(A[:m], np.int64)
    positive = np.array(A[-p:], np.int64)
    negative = -negative[::-1]
    # 負の数の操作(pythonの挙動)は頭がこんがらがるので正の数にして考える

    if K <= M:
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = p ** 2 - np.searchsorted(positive, (mid + negative - 1) // negative, side='left').sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        left = 0
        right = max(A[0] * A[1], A[-1] * A[-2])
        positive2 = positive ** 2
        negative2 = negative ** 2
        while left + 1 < right:
            mid = (left + right) // 2
            a = np.searchsorted(negative, mid // negative, side='right').sum() - (mid >= negative2).sum()
            b = np.searchsorted(positive, mid // positive, side='right').sum() - (mid >= positive2).sum()

            if (a + b) // 2 < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = list(map(int, input().split()))
a = list(map(int, input().split()))

b = []
for i in range(len(a)):
    for j in range(i+1, len(a)):
        b.append(a[i]*a[j])
        print(" ".join([str(i),str(j)]))

b.sort()
print(b[k-1])

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = np.array(A[:m], np.int64)
    positive = np.array(A[-p:], np.int64)

    if K <= M:
        negative = -negative[::-1]
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, (mid + negative - 1) // negative, side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        negative = -negative[::-1]
        left = 0
        right = max(A[0] * A[1], A[-1] * A[-2])
        positive2 = positive ** 2
        negative2 = negative ** 2
        while left + 1 < right:
            mid = (left + right) // 2
            a = mid // negative
            b = np.searchsorted(negative, a, side='right').sum() - np.count_nonzero(mid >= negative2)
            b //= 2

            d = mid // positive
            e = np.searchsorted(positive, d, side='right').sum() - np.count_nonzero(mid >= positive2)
            e //= 2

            if b + e < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r
from math import floor, ceil

n, k, *a = map(int, sys.stdin.read().split())
a.sort()

def count(border):
    cnt = 0
    for i in range(n):
        l = a[i]
        if l == 0:
            if border >= 0:
                cnt += n - 1 - i
        else:
            if l < 0:
                b = ceil(border / l)
                j = bi_l(a, b)
                if j <= i:
                    cnt += n - 1 - i
                else:
                    cnt += n - j
            else:
                b = floor(border / l)
                j = bi_r(a, b)
                cnt += max(j - i - 1, 0)
    
    return cnt

def main():
    lo = -10 ** 18 - 1
    hi = 10 ** 18 + 1
    while lo + 1 < hi:
        border = (lo + hi) // 2
        if count(border) >= k:
            hi = border
        else:
            lo = border
    return hi

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer)
    print(answer[K - 1])


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    # test(A, K)
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = np.array(A[:m], np.int64)
    positive = np.array(A[-p:], np.int64)

    if K <= M:
        negative = -negative[::-1]
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, (mid + negative - 1) // negative, side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        negative = np.abs(negative[::-1])
        left = 0
        right = max(A[0] ** 2, A[-1] ** 2)
        while left + 1 < right:
            mid = (left + right) // 2
            a = mid // negative
            b = np.searchsorted(negative, a, side='right').sum() - np.count_nonzero(mid >= negative ** 2)
            b //= 2

            d = mid // positive
            e = np.searchsorted(positive, d, side='right').sum() - np.count_nonzero(mid >= positive ** 2)
            e //= 2

            if b + e < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer)
    print(answer[K - 1])


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    # test(A, K)
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = np.array(A[:m], np.int64)
    positive = np.array(A[-p:], np.int64)

    if K <= M:
        negative = -negative[::-1]
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, np.ceil(mid / negative).astype(int), side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        negative = np.abs(negative[::-1])
        left = 0
        right = max(A[0] ** 2, A[-1] ** 2)
        while left + 1 < right:
            mid = (left + right) // 2
            a = mid // negative
            b = np.searchsorted(negative, a, side='right').sum() - (mid >= negative ** 2).sum()
            b //= 2

            d = mid // positive
            e = np.searchsorted(positive, d, side='right').sum() - (mid >= positive ** 2).sum()
            e //= 2

            if b + e < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    from bisect import bisect_left,bisect_right
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=np.array(A)
    A=np.sort(A)
    Ap=A[A>0]
    Az=A[A==0]
    Am=A[A<0]   
    lm,lz,lp=len(Am),len(Az),len(Ap)
    Ap2=Ap**2
    Am2=Am**2
    #print(Ap,Am,Az,Ap2,Am2)
    def cnt_product(x): #ある数字の組であってその積がx以下となるものの数
        if x<0:
            X=np.searchsorted(Am,x//Ap,side='right')
            #print(X)
            return X.sum()
        
        else:
            ans=lz*(n-lz)+lz*(lz-1)//2+lp*lm

            X=np.searchsorted(Ap,x//Ap,side='right')
            Xd=np.count_nonzero(Ap2<=x)

            Y=np.searchsorted(Am,(-x-1)//(-Am))
            Yd=np.count_nonzero(Am2<=x)
            
            ans+=(X.sum()-Xd+lm**2-Y.sum()-Yd)//2
            return ans
    #print(cnt_product(448283280358331042))
    left=-10**18
    right=10**18
    while right-left>1:
        mid=(left+right)//2
        if cnt_product(mid)<k:
            left=mid
        else:
            right=mid
    print(right)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer)
    print(answer[K - 1])


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    test(A, K)
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = np.array(A[:m], np.int64)
    positive = np.array(A[-p:], np.int64)

    if K <= M:
        negative = -negative[::-1]
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, np.ceil(mid / negative).astype(int), side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        negative = np.abs(negative[::-1])
        left = 0
        right = max(A[0] ** 2, A[-1] ** 2)
        while left + 1 < right:
            mid = (left + right) // 2
            a = mid // negative
            b = np.searchsorted(negative, a, side='right').sum() - (mid >= negative ** 2).sum()
            b //= 2

            d = mid // positive
            e = np.searchsorted(positive, d, side='right').sum() - (mid >= positive ** 2).sum()
            e //= 2

            if b + e < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()