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()))

li_p = []
li_m = []
li_0 = []
li_all = []

a.sort()

for i in range(n):
    if a[i]<0:
        li_m.append(a[i])
    elif a[i] == 0:
        li_0.append(a[i])
    else:
        li_p.append(a[i])


LI_m =len(li_m)
LI_0 =len(li_0)
LI_p =len(li_p)


if k <= LI_0 - 1:
    print(0)

elif LI_0 - 1 < k < LI_m * LI_p:
    li_p.sort(reverse=True)
    for i in range(LI_m):
        for j in range(LI_p):

            li_all.append(li_m[i]*li_p[j])
            li_all.sort()
    else:
        print(li_all[k - LI_0 -1])

# else:
#     li_p.sort(reverse=True)
#     for i in range(LI_m-1):

Submission status: Wrong Answer

Solution code:
def General_Binary_Increase_Search(L,R,cond,Integer=True,ep=1/(1<<20)):
    """条件式が単調増加であるとき,一般的な二部探索を行う.
    L:解の下限
    R:解の上限
    cond:条件(1変数関数,広義単調減少 or 広義単調減少を満たす)
    Integer:解を整数に制限するか?
    ep:Integer=Falseのとき,解の許容する誤差
    """
    if not(cond(R)):
        return False

    if Integer:
        R+=1
        while R-L>1:
            C=L+(R-L)//2
            if cond(C):
                R=C
            else:
                L=C
        return R
    else:
        while (R-L)>=ep:
            C=L+(R-L)/2
            if cond(C):
                R=C
            else:
                L=C
        return R

def f(R):
    I=0
    S=0
    for a in Pos:
        if I<Negative:
            while a*Neg[I]<=R:
                I+=1
                if I==Negative:
                    break

        S+=I
    return S

def g(R):
    S=0

    I=Positive
    for a in Pos:
        if I>0:
            while a*Pos[I-1]>R:
                I-=1
                if I==0:
                    break
        S+=I
        if a*a<=R:
            S-=1

    J=0
    for b in Neg:
        if J<Negative:
            while b*Neg[-(J+1)]<=R:
                J+=1
                if J==Negative:
                    break
        S+=J
        if b*b<=R:
            S-=1

    return S>>1
#================================================
N,K=map(int,input().split())

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

Pos=[a for a in A if a>0]
Neg=[a for a in A if a<0]

Positive=Zero=Negative=0
for a in A:
    if a>0:
        Positive+=1
    elif a==0:
        Zero+=1
    else:
        Negative+=1

Pos_Count=(Positive*(Positive-1))//2+(Negative*(Negative-1))//2
Neg_Count=Positive*Negative
Zero_Count=(N*(N-1))//2-(Pos_Count+Neg_Count)

H=max(A,key=lambda a:abs(a))
H=H*H+1

if Neg_Count+1<=K<=Zero: #ゼロ確定
    Ans=0
elif K<=Neg_Count: #負確定
    Ans=General_Binary_Increase_Search(-H,0,lambda x:f(x)>=K)
else: #正確定
    Ans=General_Binary_Increase_Search(0,H,lambda x:g(x)>=K-(Neg_Count+Zero_Count))

print(Ans)

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()))

    minus, plus, zero = [], [], 0
    for i in range(n):
        if a[i] < 0:
            minus.append(a[i])
        elif a[i] > 0:
            plus.append(a[i])
        else:
            zero += 1
    
    minus_count = len(minus) * len(plus)
    zero_count = zero * (zero - 1) // 2 + zero * (len(minus) + len(plus))

    minus.sort()
    plus.sort()

    if k <= minus_count:
        l, r = -int(1e18), 0
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            for v in minus:
                border = (-value-1) // (-v) + 1
                count += len(plus) - bisect.bisect_left(plus, border)

            if count >= k:
                r = value
            else:
                l = value

        ans = r
    elif k <= zero_count:
        ans = 0
    else:
        l, r = 0, int(1e18)
        count_default = minus_count + zero_count
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            
            for v in minus:
                border = -value // -v
                count += (len(minus) - bisect.bisect_left(minus, border))
                if v >= border:
                    count -= 1

            for v in plus:
                border = value // v
                count += bisect.bisect_right(plus, border)
                if v <= border:
                    count -= 1
            
            count //= 2
            count += count_default

            if count >= k:
                r = value
            else:
                l = value
        ans = r
    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = inpl()
mi = []
mi_ab = []
pl = []
ze = 0
for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(x)
        mi_ab.append(-x)
    else:
        ze += 1
mi_cnt = len(mi); pl_cnt = len(pl)
mi.sort(); mi_ab.sort(); pl.sort()

def sol(x):
    cnt = 0
    if x >= 0:
        for y in pl:
            now = x//y
            cnt += bisect_right(pl,now)
            if y <= now: cnt -= 1
        for y in mi_ab:
            now = x//y
            cnt += bisect_right(mi_ab,now)
            if y <= now: cnt -= 1
        cnt //= 2
        cnt += ze*(n-1) - ze*(ze-1)//2
        cnt += mi_cnt*pl_cnt
    else:
        for y in pl:
            now = x//y
            cnt += bisect_right(mi,now)
            if x == -8: print(cnt,now)
        if x == -8: print(1234567,cnt)
    return True if cnt >= k else False

if k <= mi_cnt*pl_cnt:
    ok = -1; ng = -pow(10,18)-1
else:
    ok = pow(10,18)+1; ng = -1


while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    # print(mid)
    if sol(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

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

plus = [i for i in A if i > 0]
minus = [-i for i in A if i < 0]
zero = [i for i in A if i == 0]
plus.sort()
minus.sort()
m = len(minus)
p = len(plus)
plusNum = (len(plus) * (len(plus)-1))/2 + (len(minus) * (len(minus)-1))/2
minusNum = len(plus) * len(minus)
zeroNum = len(zero)*(len(zero)-1)/2 + len(zero)*(N-len(zero))

def cnt(x, flag):
    c = 0
    i , j = 0, 0
    if flag == 1:
        while j < p:
            if minus[i] * plus[j] < -x:
                i += 1
                if i == m:
                    i = 0
                    j += 1
            else:
                c += p - i
                j += 1
                i = 0
    else:
        i += 1
        while i < m:
            if minus[i] * minus[j] < x:
                i += 1
                c += 1
                if i == m:
                    j += 1
                    i = j + 1
            else:
                if i - j == 1:
                    break
                j += 1
                i = j + 1
        i, j = 1, 0
        while i < p:
            if plus[i] * plus[j] < x:
                i += 1
                c += 1
                if i == p:
                    j += 1
                    i = j + 1
            else:
                if i - j == 1:
                    break
                j += 1
                i = j + 1
    return c


if minusNum >= K:
    flag = 1
    add = 0
elif minusNum + zeroNum >= K:
    print(0)
    exit()
else:
    flag = 0
    add = minusNum + zeroNum
bottom = -10**18 - 1
top = 10**18 + 1
while top - bottom > 1:
    middle = (top + bottom) // 2
    judge = cnt(middle, flag) + add
    if judge < K:
        bottom = middle
    else:
        top = middle
print((top+bottom)//2 + flag)

Submission status: Wrong Answer

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

plus = [i for i in A if i > 0]
minus = [-i for i in A if i < 0]
zero = [i for i in A if i == 0]
plus.sort()
minus.sort()
m = len(minus)
p = len(plus)
plusNum = (len(plus) * (len(plus)-1))/2 + (len(minus) * (len(minus)-1))/2
minusNum = len(plus) * len(minus)
zeroNum = len(zero)*(len(zero)-1)/2 + len(zero)*(N-len(zero))

def cnt(x, flag):
    c = 0
    i , j = 0, 0
    if flag == 1:
        while j < p:
            if minus[i] * plus[j] < -x:
                i += 1
                if i == m:
                    i = 0
                    j += 1
            else:
                c += p - i
                j += 1
                i = 0
    else:
        i += 1
        while i < m:
            if minus[i] * minus[j] < x:
                i += 1
                c += 1
                if i == m:
                    j += 1
                    i = j + 1
            else:
                j += 1
                i = j + 1
        i, j = 1, 0
        while i < p:
            if plus[i] * plus[j] < x:
                i += 1
                c += 1
                if i == p:
                    j += 1
                    i = j + 1
            else:
                j += 1
                i = j + 1
    return c


if minusNum >= K:
    flag = 1
    add = 0
elif minusNum + zeroNum >= K:
    print(0)
    exit()
else:
    flag = 0
    add = minusNum + zeroNum
bottom = -10**18 - 1
top = 10**18 + 1
while top - bottom > 1:
    middle = (top + bottom) // 2
    judge = cnt(middle, flag) + add
    if judge < K:
        bottom = middle
    else:
        top = middle
print((top+bottom)//2 + flag)

Submission status: Wrong Answer

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

plus = [i for i in A if i > 0]
minus = [-i for i in A if i < 0]
zero = [i for i in A if i == 0]
plus.sort()
minus.sort()
m = len(minus)
p = len(plus)
plusNum = (len(plus) * (len(plus)-1))/2 + (len(minus) * (len(minus)-1))/2
minusNum = len(plus) * len(minus)
zeroNum = len(zero)*(len(zero)-1)/2 + len(zero)*(N-len(zero))

def cnt(x, flag):
    c = 0
    i , j = 0, 0
    if flag == 1:
        while j < p:
            if minus[i] * plus[j] < -x:
                i += 1
                if i == m:
                    i = 0
                    j += 1
            else:
                c += p - i
                j += 1
                i = 0
    else:
        i += 1
        while i < m:
            if minus[i] * minus[j] < x:
                i += 1
                c += 1
                if i == m:
                    j += 1
                    i = j + 1
            else:
                j += 1
                i = j + 1
        i, j = 1, 0
        while i < p:
            if plus[i] * plus[j] < x:
                i += 1
                c += 1
                if i == p:
                    j += 1
                    i = j + 1
            else:
                j += 1
                i = j + 1
    return c


if minusNum >= K:
    flag = 1
    add = 0
elif minusNum + zeroNum >= K:
    print(0)
    exit()
else:
    flag = 0
    add = minusNum + zeroNum
bottom = -10**18
top = 10**18
while top - bottom > 1:
    middle = (top + bottom) // 2
    judge = cnt(middle, flag) + add
    if judge < K:
        bottom = middle
    else:
        top = middle
print((top+bottom)//2 + flag)

Submission status: Wrong Answer

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

plus = [i for i in A if i > 0]
minus = [-i for i in A if i < 0]
zero = [i for i in A if i == 0]
plus.sort()
minus.sort()

plusNum = (len(plus) * (len(plus)-1))/2 + (len(minus) * (len(minus)-1))/2
minusNum = len(plus) * len(minus)
zeroNum = len(zero)*(len(zero)-1)/2 + len(zero)*(N-len(zero))

def cnt(x, flag):
    c = 0
    i , j = 0, 0
    if flag == 1:
        while j < len(plus):
            if minus[i] * plus[j] < -x:
                i += 1
                if i == len(minus):
                    i = 0
                    j += 1
            else:
                c += len(plus) - i
                j += 1
                i = 0
    else:
        i += 1
        while i < len(minus):
            if minus[i] * minus[j] < x:
                i += 1
                c += 1
                if i == len(minus):
                    j += 1
                    i = j + 1
            else:
                j += 1
                i = j + 1
        i, j = 1, 0
        while i < len(plus):
            if plus[i] * plus[j] < x:
                i += 1
                c += 1
                if i == len(plus):
                    j += 1
                    i = j + 1
            else:
                j += 1
                i = j + 1
    return c


if minusNum >= K:
    flag = 1
    add = 0
elif minusNum + zeroNum >= K:
    print(0)
    exit()
else:
    flag = 0
    add = minusNum + zeroNum
bottom = -10**18
top = 10**18
while top - bottom > 1:
    middle = (top + bottom) // 2
    judge = cnt(middle, flag) + add
    if judge < K:
        bottom = middle
    else:
        top = middle
print((top+bottom)//2 + flag)

Submission status: Wrong Answer

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

plus = [i for i in A if i > 0]
minus = [-i for i in A if i < 0]
zero = [i for i in A if i == 0]
plus.sort()
minus.sort()

plusNum = (len(plus) * (len(plus)-1))/2 + (len(minus) * (len(minus)-1))/2
minusNum = len(plus) * len(minus)
zeroNum = len(zero)*(len(zero)-1)/2 + len(zero)*(N-len(zero))

def cnt(x, flag):
    c = 0
    i , j = 0, 0
    if flag == -1:
        while j < len(plus):
            if minus[i] * plus[j] < -x:
                i += 1
                if i == len(minus):
                    i = 0
                    j += 1
            else:
                c += len(plus) - i
                j += 1
                i = 0
    else:
        i += 1
        while i < len(minus):
            if minus[i] * minus[j] < x:
                i += 1
                c += 1
                if i == len(minus):
                    j += 1
                    i = j + 1
            else:
                j += 1
                i = j + 1
        i, j = 1, 0
        while i < len(plus):
            if plus[i] * plus[j] < x:
                i += 1
                c += 1
                if i == len(plus):
                    j += 1
                    i = j + 1
            else:
                j += 1
                i = j + 1
    return c


if minusNum >= K:
    flag = -1
    add = 0
elif minusNum + zeroNum >= K:
    print(0)
    exit()
else:
    flag = 1
    add = minusNum + zeroNum
bottom = -10**18
top = 10**18
while top - bottom > 1:
    middle = (top + bottom) // 2
    judge = cnt(middle, flag) + add
    if judge < K:
        bottom = middle
    else:
        top = middle
    print(top, bottom)
print((top+bottom)//2)

Submission status: Wrong Answer

Solution code:
import bisect
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

def isOK(x):
    # 積の中でx以下のものがいくつあるかを調べる
    res=0
    for a in A:
        if a<0:
            # x/a以上の要素の数
            i=N-bisect.bisect_left(A,x/a)
        elif a>0:
            # x/a以下の要素の数
            i=bisect.bisect_right(A,x/a)
        else:
            if x>=0:
                i=N
            else:
                i=0
        if a*a<=x:
            i-=1
#         print(a,i)
        res+=i
    # x以下のものはres//2個
#     print(x,res)
    return res<K*2

###
# B=[]
# for i in range(len(A)):
#     for j in range(len(A)):
#         if not i<j:
#             continue
#         else:
#             B.append(A[i]*A[j])
# B.sort()
# print(B,B[K-1])
###


# for b in list(set(B)):
# b=-3
# isOK(b)


ng=max([A[0]*A[0],A[0]*A[-1],A[-1]*A[-1]])+1
ok=min([A[0]*A[0],A[0]*A[-1],A[-1]*A[-1]])-1

isOK(ng)
isOK(ok)
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if isOK(mid):
        ok=mid
    else:
        ng=mid
print(ng)

Submission status: Wrong Answer

Solution code:
import sys
N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = 10 **19
ok = inf
ng = -inf

def is_ok(arg):
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = 0
        ng = N
        if A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid       
            ans += N-ok   
    ans /= 2
    return K < ans
 





while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
print(mid)

Submission status: Wrong Answer

Solution code:
N,K= map(int,input().split())
A = list(map(int,input().split()))
ans = []
for i in range(N):
    for j in range(i,N):
        ans.append(A[i]*A[j])
ans.sort()
print(ans[K-1])

Submission status: Wrong Answer

Solution code:
N,K= map(int,input().split())
A = list(map(int,input().split()))
ans = []
for i in range(N):
    for j in range(i,N):
        ans.append(A[i]*A[j])
ans.sort()
print(ans[K])

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect

def main():
    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0
        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            elif a < 0:
                aa = -(((-arg) - 1) // a)
                cnt += N - bisect.bisect_left(A, aa)
                if aa <= a:
                    cnt -= 1
            else:
                aa = arg // a
                cnt += bisect.bisect_right(A, aa)
                if aa >= a:
                    cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    N, K = MI()
    A = LI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)
    cnt_neg = bisect.bisect_left(A, 0)
    cnt_pos = N - bisect.bisect_right(A, 0)
    cnt_zer = N - cnt_pos - cnt_neg
    neg_pair = cnt_neg * cnt_pos

    if K <= neg_pair:
        ng = p_min - 1
        ok = 1
        ans = meguru_bisect(ng, ok)
        print(ans)
    elif K <= neg_pair + cnt_zer * (N - 1) - cnt_zer * (cnt_zer - 1) // 2:
        print(0)
    else:
        ng = -1
        ok = p_max + 1
        ans = meguru_bisect(ng, ok)
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect



def main():
    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0
        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            elif a < 0:
                d = divmod(arg, a)
                if d[1] == 0:
                    aa = d[0]
                else:
                    aa = d[0] + 1
                cnt += N - bisect.bisect_left(A, aa)
                if aa <= a:
                    cnt -= 1
            else:
                aa = arg // a
                cnt += bisect.bisect_right(A, aa)
                if aa >= a:
                    cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    N, K = MI()
    A = LI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)
    cnt_neg = bisect.bisect_left(A, 0)
    cnt_pos = bisect.bisect_right(A, 0)
    cnt_zer = N - cnt_pos - cnt_neg

    if K <= cnt_neg * cnt_pos:
        ng = p_min - 1
        ok = 1
        ans = meguru_bisect(ng, ok)
        print(ans)
    elif K <= cnt_neg * cnt_pos + cnt_zer * (N - 1) - cnt_zer * (cnt_zer - 1) // 2:
        print(0)
    else:
        ng = -1
        ok = p_max + 1
        ans = meguru_bisect(ng, ok)
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect



def main():
    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0
        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            elif a < 0:
                d = divmod(arg, a)
                if d[1] == 0:
                    aa = d[0]
                else:
                    aa = d[0] + 1
                cnt += N - bisect.bisect_left(A, aa)
                if aa <= a:
                    cnt -= 1
            else:
                aa = arg // a
                cnt += bisect.bisect_right(A, aa)
                if aa >= a:
                    cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    N, K = MI()
    A = LI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)
    cnt_neg = bisect.bisect_left(A, 0)
    cnt_pos = bisect.bisect_right(A, 0)
    cnt_zer = N - cnt_pos - cnt_neg

    if K <= cnt_neg * cnt_pos:
        ng = p_min
        ok = 1
        ans = meguru_bisect(ng, ok)
        print(ans)
    elif K <= cnt_neg * cnt_pos + cnt_zer * (N - 1) - cnt_zer * (cnt_zer - 1) // 2:
        print(0)
    else:
        ng = -1
        ok = p_max
        ans = meguru_bisect(ng, ok)
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
def main():
    N, K = MI()
    A = LI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)

    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0

        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            else:
                if a < 0:
                    aa = math.ceil(arg / a)
                    cnt += N - bisect.bisect_left(A, aa)
                    if aa <= a:
                        cnt -= 1
                else:
                    aa = arg // a
                    cnt += bisect.bisect_right(A, aa)
                    if aa >= a:
                        cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    ans = meguru_bisect(p_min - 1, p_max + 1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
def main():
    N, K = MI()
    A = LI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)

    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0

        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            else:
                if a < 0:
                    aa = math.ceil(arg / a)
                    cnt += N - bisect.bisect_left(A, aa)
                    if aa < a:
                        cnt -= 1
                else:
                    aa = arg // a
                    cnt += bisect.bisect_right(A, aa)
                    if aa > a:
                        cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    ans = meguru_bisect(p_min - 1, p_max + 1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
def main():
    N, K = MI()
    A = LI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)

    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0

        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            else:
                aa = arg // a
                if a < 0:
                    aa = math.ceil(arg / a)
                    cnt += N - bisect.bisect_left(A, aa)
                    if aa < a:
                        cnt -= 1
                else:
                    aa = arg // a
                    cnt += bisect.bisect_right(A, aa)
                    if aa > a:
                        cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    ans = meguru_bisect(p_min - 1, p_max + 1)
    print(ans)

if __name__ == "__main__":
    main()