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:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N,K = inpl()
aa = sorted(inpl())

l = bisect.bisect_left(aa, 0)
r = bisect.bisect_right(aa, 0)

aa_m = aa[:l]
aa_0 = aa[l:r]
aa_p = aa[r:]
N_m = len(aa_m)
N_0 = len(aa_0)
N_p = len(aa_p)
zeros = N_m * N_p + N_0 * (N_m+N_p) + (N_0)*(N_0-1)//2

# x 以下をカウント
def solve(x):
    cnt = 0
    if x == 0:
        return zeros
    elif x > 0:
        cnt += zeros
        for i,a in enumerate(aa_m):
            r = bisect.bisect_right(aa_m, x//a)
            cnt += N_m-max(i+1,r)
        for i,a in enumerate(aa_p):
            r = bisect.bisect_right(aa_p,x//a)
            cnt += max(0,r-(i+1))
        return cnt
    elif x < 0:
        for i,a in enumerate(aa_m):
            r = N_p-bisect.bisect_left(aa_p,-(-x//a))
            cnt += r
    return cnt


NG = -(10**18)
OK = 10**18

while OK-NG > 1:
    mid = (OK+NG)//2
    if solve(mid) >= K:
        OK = mid
    else:
        NG = mid

print(OK)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

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

minas=[]
plus=[]
zero=[]
for a in A:
    if a<0:
        minas.append(-a)
    elif a==0:
        zero.append(a)
    else:
        plus.append(a)
minas.sort()
plus.sort()

st=-(10**18)-1
ed=10**18+1
zero1=len(plus)*len(minas)
zero2=len(zero)*(len(minas)+len(plus))+len(zero)*(len(zero)-1)//2


def nibun(lst,value,st,ed):
    if lst[st]>value:
        return(st)
    while ed-st>1:
        mid=(st+ed)//2
        if value>=lst[mid]:
            st=mid
        else:
            ed=mid
    return(ed)


while ed-st>1:
    mid=(st+ed)//2
    if mid<0:
        j=0
        for m in minas:
            value=-mid//m+((-mid%m)>=1)*1
            j+=len(plus)-bisect_left(plus,value)
    elif mid==0:


        if K<zero1:
            ed=0
            continue
        elif K>zero1+zero2:
            st=0
            continue
        else:
            print(0)
            exit()
    else:
        j=zero1+zero2

        for i in range(len(plus)-1):
            value=mid//plus[i]#+((mid%plus[i])>=1)*1

            #j+=bisect_right(plus[i+1:],value)
            j+=nibun(plus,value,i+1,len(plus))-(i+1)
        for i in range(len(minas)-1):
            value=mid//minas[i]#+((mid%minas[i])>=1)*1

            #j+=bisect_right(minas[i+1:],value)
            j+=nibun(minas,value,i+1,len(minas))-(i+1)





    if j<K:
        st=mid
    else:
        ed=mid

print(ed)
448283280358331064
448283279821112042
448283279821127501

Submission status: Wrong Answer

Solution code:
import numpy as np

# 標準入力の受け取り
N, K = [int(i) for i in input().split()]
A = np.array([int(i) for i in input().split()], dtype=np.int64)

try:
    print(sorted(np.outer(A, A)[np.triu_indices(N, k=1)])[K - 1])

except:
    print(1)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

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

minas=[]
plus=[]
zero=[]
for a in A:
    if a<0:
        minas.append(-a)
    elif a==0:
        zero.append(a)
    else:
        plus.append(a)
minas.sort()
plus.sort()

st=-(10**18)-1
ed=10**18+1
zero1=len(plus)*len(minas)
zero2=len(zero)*(len(minas)+len(plus))+len(zero)*(len(zero)-1)//2

while ed-st>1:
    mid=(st+ed)//2
    if mid<0:
        j=0
        for m in minas:
            value=-mid//m+((-mid%m)>=1)*1
            j+=len(plus)-bisect_left(plus,value)
    elif mid==0:


        if K<zero1:
            ed=0
            continue
        elif K>zero1+zero2:
            st=0
            continue
        else:
            print(0)
            exit()
    else:
        j=zero1+zero2

        for i in range(len(plus)-1):
            value=mid//plus[i]#+((mid%plus[i])>=1)*1

            #j+=bisect_right(plus[i+1:],value)
            j+=bisect_right(plus,value,lo=i+1,hi=len(plus))-(i+1)
        for i in range(len(minas)-1):
            value=mid//minas[i]#+((mid%minas[i])>=1)*1

            #j+=bisect_right(minas[i+1:],value)
            j+=bisect_right(minas,value,lo=i+1,hi=len(minas))-(i+1)





    if j<K:
        st=mid
    else:
        ed=mid

print(ed)
448283280358331064
448283279821112042
448283279821127501

Submission status: Wrong Answer

Solution code:
import itertools, bisect, math
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
A.sort()
pos = A[bisect.bisect_right(A, 1):]
neg = [-a for a in A[:bisect.bisect_left(A, 0)][::-1]]
zero = N - len(pos) - len(neg)
if K <= len(pos) * len(neg):
    #ans<0
    #ans=「pos[i]*neg[j]>-xなるi,jがK個未満となる最大のx」
    def check(x):
        cnt = len(pos) * len(neg)
        for p in pos:
            cnt -= bisect.bisect_left(neg, math.ceil(-x / p))
        return cnt < K

    lb = -10**18 - 1
    rb = 0
    # Max x for check(x) == True
    while rb - lb > 1:
        mid = (rb + lb) // 2
        if check(mid):
            lb = mid
        else:
            rb = mid
    print(rb)
elif K <= N * (N - 1) // 2 - (len(pos) *
                              (len(pos) - 1) // 2) - (len(neg) *
                                                      (len(neg) - 1) // 2):
    #ans=0
    print(0)
else:
    #ans>0
    #ans=「pos[i]*pos[j]<xなるi,j(i<j)とneg[i]*neg[j]<xなるk,l(k<l)の個数の和がK-(0以下の個数)個を上回る最大のx」
    K -= N * (N - 1) // 2 - (len(pos) *
                             (len(pos) - 1) // 2) - (len(neg) *
                                                     (len(neg) - 1) // 2)

    def check(x):
        root = x**0.5

        def count(B):
            ret = -bisect.bisect_right(B, root)
            for b in B:
                ret += bisect.bisect_right(B, x // b)
            ret //= 2
            return ret

        return count(pos) + count(neg) < K

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

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy



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

minas=[]
plus=[]
zero=[]
for a in A:
    if a<0:
        minas.append(-a)
    elif a==0:
        zero.append(a)
    else:
        plus.append(a)
minas.sort()
plus.sort()

st=-(10**18)-1
ed=10**18+1
zero1=len(plus)*len(minas)
zero2=len(zero)*(len(minas)+len(plus))+len(zero)*(len(zero)-1)//2

while ed-st>1:
    mid=(st+ed)//2
    if mid<0:
        j=0
        for m in minas:
            value=-mid//m+((-mid%m)>=1)*1
            j+=len(plus)-bisect_left(plus,value)
    elif mid==0:


        if K<zero1:
            ed=0
            continue
        elif K>zero1+zero2:
            st=0
            continue
        else:
            print(0)
            exit()
    else:
        j=zero1+zero2

        for i in range(len(plus)-1):
            value=mid//plus[i]#+((mid%plus[i])>=1)*1
            j+=bisect_right(plus[i+1:],value)
        for i in range(len(minas)-1):
            value=mid//minas[i]#+((mid%minas[i])>=1)*1
            j+=bisect_right(minas[i+1:],value)




    if j<K:
        st=mid
    else:
        ed=mid

print(ed)
448283280358331064
448283279821112042
448283279821127501

Submission status: Wrong Answer

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

a.sort()
l = -10**9-1
r = 10**9+1

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

Submission status: Wrong Answer

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

a.sort()
l = -10**9 - 1
r = 10**9 + 1

while(l+1 < r):
    x = (l + r) / 2
    print('outer while: l = ' + str(l) + ' r = ' + str(r) + ' x = ' + str(x))
    total = 0
    for i in range(n):
        print('for:' + str(i) + ' l = ' + str(l) + ' r = ' + str(r) + ' x = ' + str(x))
        if(a[i] < 0):
            l, r = -1, n
            while(l+1 < r):
                c = (l + r) // 2
                print('inner while: l = ' + str(l) + ' r = ' + str(r) + ' c = ' + str(c))
                if a[c] * a[i] < x:
                    r = c
                else:
                    l = c
            total += r
        else: # a[i] => 0
            l, r = -1, n
            while(l+1 < r):
                c = (l + r) // 2
                print('inner while: l = ' + str(l) + ' r = ' + str(r) + ' c = ' + str(c))
                if a[c] * a[i] < x:
                    l = c
                else:
                    r = c
            total += r
        if (a[i] * a[i]) < x:
            total -= 1
    total /= 2
    if total < k:
       l = x
    else:
        r = x
print(l)

Submission status: Wrong Answer

Solution code:
N,K  = map(int, input().split())
As = list(map(int, input().split()))
As.sort()
"""
ある数Xに対して、それ未満の数を数える
f(x < X) < K => True
f(x < X) >= K => False
"""
INF = 10**18+1
from bisect import bisect_left
from bisect import bisect_right

def f(x):
    cnt = 0
    for a in As:
        if a < 0:
            ind = bisect_right(As, x/a)
            cnt += N-ind
        elif a == 0:
            if x <= 0:
                cnt += 0
            elif x > 0:
                cnt += N
        else:
            ind = bisect_left(As, x/a)
            cnt += ind
        if a * a < x:
            cnt -= 1
    # print("x",x,"cnt",cnt//2,"judge",cnt>=K)
    cnt //= 2
    return cnt >= K
# for i in range(-12,11):
#     print(f(i))

def  binarySearch(l,r):
    while r - l > 1:
        mid = (l+r)//2
        if f(mid):
            r = mid
        else:
            l = mid
    return l

ans = binarySearch(-INF,INF)
print(ans)

#AC 448283280358331064
#   448283280358331113
#   476299476577366868

Submission status: Wrong Answer

Solution code:
import sys
import bisect
input=sys.stdin.readline
def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()

    l=-10**18
    r=10**18+1
    while l<r-1:
        m=(l+r)//2
        count=0
        for i in range(N):
            a=A[i]
            if a<0:
                if m%a==0:
                    l_index=bisect.bisect_right(A,m//a)-1
                    count+=N-(l_index+1)
                else:
                    l_index=bisect.bisect_right(A,(m//a)+1)-1
                    count+=N-(l_index+1)
            elif a==0:
                if m>0:
                    count+=N
            else:
                if m%a==0:
                    l_index=bisect.bisect_left(A,m//a)-1
                    count+=l_index+1
                else:
                    l_index=bisect.bisect_left(A,m//a+1)-1
                    count+=l_index+1
            if a*a<m:
                count-=1
        count//=2
        if count<K:
            l=m
        else:
            r=m
    print(l)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    P = []
    Z = 0
    N = []
    for a in A:
        if a == 0:
            Z += 1
        elif a < 0:
            N.append(a)
        else:
            P.append(a)
    N.sort()
    P.sort()

    NN = len(N) * len(P)
    ZN = len(N) * Z + len(P) * Z + Z * (Z-1) // 2
    if M <= NN:
        N.reverse()
        def f(n):
            ans = 0
            i = bisect.bisect_left(P, -(n // -N[0]))
            for nn in N:
                m = -(n // -nn)
                while i != 0 and P[i-1] >= m:
                    i -= 1
                ans += len(P) - i
            return ans
        bs = Bisect(f)

        return bs.bisect_right(M-1, -INF, 0)

    elif M <= NN + ZN:
        return 0
    else:
        M -= NN + ZN
        N = [-v for v in N]
        # N.reverse()

        def f(n):
            ans = 0
            if N:
                i = bisect.bisect_right(N, n//N[0])
                for nn in N:
                    m = n // nn
                    while i != 0 and N[i-1] > m:
                        i -= 1
                    ans += i
                    if i > 0 and N[i-1] >= nn:
                        ans -= 1
            if P:
                i = bisect.bisect_right(P, n//P[0])
                for pn in P:
                    m = n // pn
                    while i != 0 and P[i-1] > m:
                        i -= 1
                    ans += i
                    if i > 0 and P[i-1] >= pn:
                        ans -= 1
            ans //= 2
            return ans
        bs = Bisect(f)
        return bs.bisect_right(M-1, 1, INF)

def f(N, M, A):
    ans = []
    for i in range(N):
        for j in range(i+1, N):
            ans.append((A[i]*A[j], A[i], A[j]))
    ans.sort()
    for i, r in enumerate(ans):
        print(i, r)

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
from itertools import groupby

def sgn(num):
    if num<0:
        return -1
    elif num==0:
        return 0
    else:
        return 1


N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
a=0
b=0
c=0
B=[sgn(A[i]) for i in range(0,N)]
B=groupby(B)
for key,group in B:
    g=len(list(group))
    if key==-1:
        a=g
    elif key==0:
        b=g
    else:
        c=g
if a*c>=K:
    def condition(num):
        s=0
        t=a+b
        set=0
        while a+b+c-1>=t and a-1>=s:
            if A[s]*A[t]>num:
                t+=1
            else:
                set+=a+b+c-t
                s+=1
        if set>=K:
            return True
        else:
            return False
    start=-10**18
    end=-1
    while end-start>1:
        test=(start+end)/2
        if condition(test):
            end=test
        else:
            start=test
    print(int(start))
elif a*c+a*b+b*c+b*(b-1)//2>=K:
    print(0)
else:
    K-=a*c+a*b+b*c+b*(b-1)//2
    def condition(num):
        set=0
        s=a-1
        t=0
        while a-1>=t and s>=0:
            if A[s]*A[t]>num:
                t+=1
            else:
                set+=a-t
                if s>=t:
                    set-=1
                s-=1
        s=a+b
        t=a+b+c-1
        while t>=a+b and a+b+c-1>=s:
            if A[s]*A[t]>num:
                t-=1
            else:
                set+=t-a-b+1
                if t>=s:
                    set-=1
                s+=1
        if set>=2*K:
            return True
        else:
            return False
    start=1
    end=10**18
    while end-start>1:
        test=(end+start)//2
        if condition(test):
            end=test
        else:
            start=test
    if condition(start):
        print(start)
    else:
        print(end)

Submission status: Wrong Answer

Solution code:
from itertools import groupby

def sgn(num):
    if num<0:
        return -1
    elif num==0:
        return 0
    else:
        return 1


N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
a=0
b=0
c=0
B=[sgn(A[i]) for i in range(0,N)]
B=groupby(B)
for key,group in B:
    g=len(list(group))
    if key==-1:
        a=g
    elif key==0:
        b=g
    else:
        c=g
if a*c>=K:
    def condition(num):
        s=0
        t=a+b
        set=0
        while a+b+c-1>=t and a-1>=s:
            if A[s]*A[t]>num:
                t+=1
            else:
                set+=a+b+c-t
                s+=1
        if set>=K:
            return True
        else:
            return False
    start=-10**18
    end=-1
    while end-start>1:
        test=(start+end)/2
        if condition(test):
            end=test
        else:
            start=test
    print(int(start))
elif a*c+a*b+b*c+b*(b-1)//2>=K:
    print(0)
else:
    K-=a*c+a*b+b*c+b*(b-1)//2
    def condition(num):
        set=0
        s=a-1
        t=0
        while a-1>=t and s>=0:
            if A[s]*A[t]>num:
                t+=1
            else:
                set+=a-t
                if s>=t:
                    set-=1
                s-=1
        s=a+b
        t=a+b+c-1
        while t>=a+b and a+b+c-1>=s:
            if A[s]*A[t]>num:
                t-=1
            else:
                set+=t-a-b+1
                if t>=s:
                    set-=1
                s+=1
        print(set,num)
        if set>=2*K:
            return True
        else:
            return False
    start=1
    end=10**18
    while end-start>1:
        test=(end+start)//2
        if condition(test):
            end=test
        else:
            start=test
    if condition(start):
        print(start)
    else:
        print(end)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    P = []
    Z = 0
    N = []
    for a in A:
        if a == 0:
            Z += 1
        elif a < 0:
            N.append(a)
        else:
            P.append(a)
    N.sort()
    P.sort()


    NN = len(N) * len(P)
    ZN = len(N) * Z + len(P) * Z + Z * (Z-1) // 2
    PN = (len(N) * (len(N)-1)) // 2 + (len(P) * (len(P)-1)) // 2
    if M <= NN:
        def f(n):
            ans = 0
            for nn in N:
                m = -n / -nn
                i = len(P) - bisect.bisect_left(P, m)
                ans += i
            return ans
        bs = Bisect(f)

        return bs.bisect_right(M-1, -INF, 0)

    elif M <= NN + ZN:
        error_print('zero')
        return 0
    else:
        M -= NN + ZN
        N = [-v for v in N]
        N.sort()
        def f(n):
            ans = 0
            for nn in N:
                m = n // nn
                i = bisect.bisect_right(N, m)
                if i > 0 and N[i-1] >= nn:
                    i -= 1
                ans += i
            for pn in P:
                m = n // pn
                i = bisect.bisect_right(P, m)
                if i > 0 and P[i-1] >= pn:
                    i -= 1
                ans += i
            ans //= 2
            return ans
        bs = Bisect(f)
        return bs.bisect_right(M-1, 1, INF)

def f(N, M, A):
    ans = []
    for i in range(N):
        for j in range(i+1, N):
            ans.append((A[i]*A[j], A[i], A[j]))
    ans.sort()
    for i, r in enumerate(ans):
        print(i, r)

def main():
    N, M = read_int_n()
    A = read_int_n()

    print(slv(N, M, A))
    # print(f(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys

def D(*a, **kwa):
    print(*a, file=sys.stderr, **kwa)

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

neg = A[:bisect_left(A, 0)]
pos = A[bisect_right(A, 0):]

all_pairs = N * (N-1) // 2
neg_pairs = len(neg) * len(pos)
pos_pairs = len(pos) * (len(pos)-1) // 2 + len(neg) * (len(neg)-1) // 2
zero_pairs = all_pairs - neg_pairs - pos_pairs

mi = []
ma = []
if len(neg) >= 2:
    mi.append(neg[-2] * neg[-1])
    ma.append(neg[0] * neg[1])
if zero_pairs > 0:
    mi.append(0)
    ma.append(0)
if len(pos) >= 2:
    mi.append(pos[0] * pos[1])
    ma.append(pos[-2] * pos[-1])
if len(pos) > 0 and len(neg) > 0:
    mi.append(pos[-1] * neg[0])

def cnt(x):
    res = 0
    if x < 0:
        for ne in neg:
            res += len(pos) - bisect_left(pos, (x +ne+1)// ne)
    elif x == 0:
        res = neg_pairs + zero_pairs
    else:
        for po in pos:
            i = bisect_right(pos, x // po)
            if i > 0:
                res += i - (po <= pos[i-1]) 
        for ne in neg:
            i = bisect_right(neg, x // ne)
            if len(neg) - i > 0:
                res += len(neg) - i - (ne >= neg[i]) 
        res //= 2
        res += neg_pairs + zero_pairs
    return res

l, r = min(mi)-1, max(ma)
while r-l > 1:
    m = l + (r - l) // 2
    c = cnt(m)
    #D(l, m, r, c)
    if c >= K:
        r = m
    else:
        l = m

print(r)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys

def D(*a, **kwa):
    print(*a, file=sys.stderr, **kwa)

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

neg = A[:bisect_left(A, 0)]
pos = A[bisect_right(A, 0):]

all_pairs = N * (N-1) // 2
neg_pairs = len(neg) * len(pos)
pos_pairs = len(pos) * (len(pos)-1) // 2 + len(neg) * (len(neg)-1) // 2
zero_pairs = all_pairs - neg_pairs - pos_pairs

def cnt(x):
    res = 0
    if x < 0:
        for ne in neg:
            res += len(pos) - bisect_left(pos, (x +ne+1)// ne)
    elif x == 0:
        res = neg_pairs + zero_pairs
    else:
        for po in pos:
            i = bisect_right(pos, x // po)
            if i > 0:
                res += i - (po <= pos[i-1]) 
        for ne in neg:
            i = bisect_right(neg, x // ne)
            if len(neg) - i > 0:
                res += len(neg) - i - (ne >= neg[i]) 
        res //= 2
        res += neg_pairs + zero_pairs
    return res

l, r = -10**18-1, 10**18
while r-l > 1:
    m = l + (r - l) // 2
    c = cnt(m)
    #D(l, m, r, c)
    if c >= K:
        r = m
    else:
        l = m

print(r)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def main():
    N, K = MI()
    A = LI()
    minus = [-a for a in A if a < 0]
    zero = [a for a in A if a == 0]
    plus = [a for a in A if a > 0]

    minus_max_idx = len(minus) * len(plus)
    zero_max_idx = minus_max_idx + len(zero) * (len(plus) + len(minus)) + cmb(len(zero), 2)

    # print(minus_max_idx, zero_max_idx)

    if (K-1) <= minus_max_idx:
        plus.sort()
        minus.sort(reverse=True)
        high = 10 ** 19
        low = 0

        while high - low > 1:
            mid = (high + low) // 2
            r = 0
            ans = 0
            for l in range(len(minus)):
                while r < len(plus) and minus[l] * plus[r] < mid:
                    r += 1
                ans += len(plus) - r
            if ans < K:
                high = mid
            else:
                low = mid
        print(-low)
    elif (K-1) > minus_max_idx and (K-1) < zero_max_idx:
        print(0)
    else:
        high = 10 ** 19
        low = 0
        plus.sort()
        minus.sort()

        while high - low > 1:
            mid = (high + low) // 2
            r = 0
            ans = 0
            for num in minus[::-1]:
                if num * num <= mid:
                    ans -= 1
                while r < len(minus) and minus[r] * num <= mid:
                    r += 1
                ans += r
            r = 0
            for num in plus[::-1]:
                if num * num <= mid:
                    ans -= 1
                while r < len(plus) and plus[r] * num <= mid:
                    r += 1
                ans += r
            ans //= 2
            # print('ans', ans, 'mid', mid, 'low', low, 'high', high, K - zero_max_idx)

            if ans < K - zero_max_idx:
                low = mid
            else:
                high = mid
        print(high)


if __name__ == '__main__':
    main()