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:
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:
                    cnt += N - bisect.bisect_left(A, aa + 1)
                    if aa + 1 < a:
                        cnt -= 1
                else:
                    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:
                    cnt += N - bisect.bisect_right(A, aa)
                    if aa < a:
                        cnt -= 1
                else:
                    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:
                    cnt += N - bisect.bisect_right(A, aa)
                    if aa < a:
                        cnt -= 1
                else:
                    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 numpy as np

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

a = np.array(a)
a.sort()

nega = a[a<0]
zero = a[a==0]
posi = a[a>0]

l = -10**18-1
r = 10**18+1
while r - l > 1:
   mid = (r+l)//2
   cnt = 0
   if mid >= 0:
      cnt += len(zero)*n
   cnt += a.searchsorted(mid//posi, side='right').sum()
   cnt += (n - a.searchsorted(mid//nega, side='left')).sum()
   cnt -= np.count_nonzero(a*a <= mid)
   cnt //=2
   if cnt >= k:
      r = mid
   else:
      l= mid

print(r)

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((mid)//(H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

Submission status: Wrong Answer

Solution code:
def count(x): # x未満の組み合わせを数える
    cnt = 0
    minus = 0
    plus = len(a) - 1
    for i in a:
        if i < 0:
            while minus < len(a) and i * a[minus] >= x:
                minus += 1
            cnt += n - minus
            # print(x, i, cnt, minus)
        else:
            while plus >= 0 and i * a[plus] >= x:
                plus -= 1
            cnt += plus + 1
            # print(x, i, cnt, plus)
        if i * i < x:
            cnt -= 1
    cnt //= 2
    print(cnt)
    return cnt < k

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

a.sort()

left = -10**18-1
right = 10**18+1

while left + 1 < right:
    mid = left + right
    mid //= 2
    print(mid)
    if count(mid):
        left = mid
    else:
        right = mid

print(left)

Submission status: Wrong Answer

Solution code:
def count(x): # x未満の組み合わせを数える
    cnt = 0
    minus = 0
    plus = len(a) - 1
    for i in a:
        if i < 0:
            while minus < len(a) and i * a[minus] >= x:
                minus += 1
            cnt += n - minus
            # print(x, i, cnt, minus)
        else:
            while plus >= 0 and i * a[plus] >= x:
                plus -= 1
            cnt += plus + 1
            # print(x, i, cnt, plus)
        if i * i < x:
            cnt -= 1
    cnt //= 2
    # print(x, cnt)
    return cnt < k

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

a.sort()

mini = min(a)
maxi = max(a)
left = min(mini*mini, mini*maxi, maxi*maxi) - 1
right = max(mini*mini, mini*maxi, maxi*maxi) + 1

while left + 1 < right:
    mid = left + right
    mid //= 2
    print(mid)
    if count(mid):
        left = mid
    else:
        right = mid

print(left)

Submission status: Wrong Answer

Solution code:
def count(x): # x未満の組み合わせを数える
    cnt = 0
    minus = 0
    plus = len(a) - 1
    for i in a:
        if i < 0:
            flag = 0
            while minus < len(a) and i * a[minus] >= x:
                minus += 1
                flag = 1
            cnt += n - minus
            # print(x, i, cnt, minus)
        else:
            flag = 0
            while plus >= 0 and i * a[plus] >= x:
                plus -= 1
                flag = 1
            cnt += plus + 1
            # print(x, i, cnt, plus)
        if i * i < x:
            cnt -= 1
    cnt //= 2
    # print(x, cnt)
    return cnt < k

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

a.sort()

mini = min(a)
maxi = max(a)
left = min(mini*mini, mini*maxi, maxi*maxi) - 1
right = max(mini*mini, mini*maxi, maxi*maxi) + 1

while left + 1 < right:
    mid = left + right
    mid //= 2
    if count(mid):
        left = mid
    else:
        right = mid

print(left)

Submission status: Wrong Answer

Solution code:
def count(x): # x未満の組み合わせを数える
    cnt = 0
    for i in a:
        if i < 0:
            left = -1
            right = len(a)
            while left + 1 < right:
                mid = left + right
                mid //= 2
                if i * a[mid] < x:
                    right = mid
                else:
                    left = mid
            cnt += n - right

        else:
            left = -1
            right = len(a)
            while left + 1 < right:
                mid = left + right
                mid //= 2
                if i * a[mid] < x:
                    left = mid
                else:
                    right = mid
            cnt += right
        if i * i < x:
            cnt -= 1
    cnt //= 2
    return cnt < k

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

a.sort()

left = min(min(a)*min(a), min(a)*max(a)) - 1
right = max(min(a)*min(a), min(a)*max(a)) + 1

while left + 1 < right:
    mid = left + right
    mid //= 2
    if count(mid):
        left = mid
    else:
        right = mid

print(left)

Submission status: Wrong Answer

Solution code:
import math
import bisect


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

    def count(v):

        res = 0

        for i, a in enumerate(A):
            if a < 0:
                b = math.ceil(v/a)
                if b > a:
                    res += N - bisect.bisect_right(A, b-1)
                    continue

                elif b <= a:
                    res += N - (i + 1)
                    continue

            elif a == 0:
                if v >= 0:
                    res += N - 1 - i
                continue

            elif a > 0:
                count_r = bisect.bisect_right(A, v//a)
                if i < count_r - 1:
                    res += count_r - 1 - i

        return res

    lower_bound = -10**18 - 1
    upper_bound = 10**18 + 1

    while upper_bound - lower_bound > 1:
        med = (lower_bound + upper_bound)//2
        if count(med) >= K:
            upper_bound = med
        else:
            lower_bound = med

    print(upper_bound)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import bisect


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

    def count(v):
        # v 以下のものが何個あるのか
        res = 0
        for i, a in enumerate(A):
            if a > 0:
                count_r = bisect.bisect_right(A, v//a)
                if i < count_r - 1:
                    res += count_r - 1 - i

            elif a == 0:
                if v >= 0:
                    res += N-1 - i

            elif a < 0:
                b = math.ceil(v/a)
                count_l = bisect.bisect_right(A, b-1)
                res += min(N-1-i, N-count_l)

        return res

    lower_bound = -10**18 - 100
    upper_bound = 10**18 + 100

    while upper_bound - lower_bound > 1:
        med = (lower_bound + upper_bound)//2
        if count(med) >= K:
            upper_bound = med
        else:
            lower_bound = med

    print(upper_bound)
    return


if __name__ == "__main__":
    main()

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 Binary_Search_Small_Count(A,x,equal=False,sort=False):
    """2分探索によって,x未満の要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"未満"がx"以下"になる
    """
    if sort:
        A.sort()

    if A[0]>x or ((not equal) and A[0]==x):
        return 0

    L,R=0,len(A)
    while R-L>1:
        C=L+(R-L)//2
        if A[C]<x or (equal and A[C]==x):
            L=C
        else:
            R=C

    return L+1

def Binary_Search_Big_Count(A,x,equal=False,sort=False):
    """2分探索によって,xを超える要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"を超える"がx"以上"になる
    """

    if sort:
        A.sort()

    if A[-1]<x or ((not equal) and A[-1]==x):
        return 0

    L,R=-1,len(A)-1
    while R-L>1:
        C=L+(R-L)//2
        if A[C]>x or (equal and A[C]==x):
            R=C
        else:
            L=C
    return len(A)-R

def h(x):
    S=0
    for a in A:
        if a>0:
            S+=Binary_Search_Small_Count(A,x//a,True)
        elif a<0:
            S+=Binary_Search_Big_Count(A,(-x-a-1)//(-a),True)
        else:
            if x>=0:
                S+=N

    if x>=0:
        T=Binary_Search_Small_Count(B,x,True)
    else:
        T=0

    return (S-T)//2
#================================================
N,K=map(int,input().split())

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

B=[a*a for a in A]
B.sort()

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

print(General_Binary_Increase_Search(-H,H,lambda x:h(x)>=K))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    from bisect import bisect_left, bisect_right

    N, K = map(int, input().split())
    A = sorted([int(x) for x in input().split()])

    negative_end = bisect_left(A, 0)
    postive_start = bisect_right(A, 0)

    postive_cnt = N - postive_start
    negative_cnt = negative_end
    zero_cnt = N - postive_cnt - negative_cnt

    negative_pairs_cnt = postive_cnt * negative_cnt
    zero_pairs_cnt = (zero_cnt * (postive_cnt + negative_cnt)
                      + (zero_cnt * (zero_cnt - 1) // 2))
    
    # 答えが負の場合
    if K <= negative_pairs_cnt:
        # 二分探索：mid以下になるペアがK個以上あるか？
        ok, ng = 0, -10 ** 18
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            or_higher_cnt, right = 0, postive_cnt
            for left in range(negative_end):
                while (right < N) and (A[left] * A[right] > mid):
                    right += 1
                or_higher_cnt += postive_cnt - (right - postive_start)
            if or_higher_cnt >= K:
                ok = mid
            else:
                ng = mid
        print(ok)
    # 答えが0の場合
    elif K <= negative_pairs_cnt + zero_pairs_cnt:
        print(0)
    # 答えが正の場合
    else:
        # 二分探索：mid以下になるペアがK個以上あるか？
        K -= negative_pairs_cnt + zero_pairs_cnt
        ok, ng = 10 ** 18, 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            # 正*正の場合
            or_higher_cnt, right = 0, N - 1
            for left in range(postive_start, N):
                while right < N and A[left] * A[right] > mid and left < right:
                    right -= 1
                or_higher_cnt += max(0, right - left)
            # 負*負の場合
            left = 0
            for right in range(negative_end - 1, -1, -1):
                while left < N and A[left] * A[right] > mid and left < right:
                    left += 1
                or_higher_cnt += max(0, right - left)

            if or_higher_cnt >= K:
                ok = mid
            else:
                ng = mid
        print(ok)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    from itertools import combinations

    N, K = map(int, input().split())
    A = [int(x) for x in input().split()]

    lst = []
    for a, b in combinations(A, 2):
        if a < 0 and b < 0:
            lst.append(sorted([-a, -b]))
        else:
            lst.append(sorted([a, b]))
            
    lst = sorted(lst)
    print(lst[K - 1][0] * lst[K - 1][1])
    # print(lst)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

zero = []
posi = []
nega = []

zero_l = 0
posi_l = 0
nega_l = 0

for i in range(n):
    if a[i]==0:
        zero.append(a[i])
        zero_l+=1
    elif a[i]>0:
        posi.append(a[i])
        posi_l+=1
    else:
        nega.append(a[i])
        nega_l+=1
posi.sort()
nega.sort(reverse=True)

zero_pair = zero_l*(n-zero_l) + zero_l*(zero_l-1)//2
posi_pair = posi_l*(posi_l-1)//2 + nega_l*(nega_l-1)//2
nega_pair = posi_l*nega_l

if k <= nega_pair:
    dist = k
    left = -10 ** 18
    right = 0
    while left + 1 < right:
        x = (left + right) // 2        
        tmp=0
        for i in range(nega_l):
            for j in range(posi_l):
                if nega[i]*posi[j]<=x:
                    tmp +=1
                else:
                    break
        if tmp >= dist:
            right = x
        else:
            left = x
    print(right)
elif k <= nega_pair+zero_pair:
    print(0)
else:
    dist = k-zero_pair-nega_pair
    left = 0
    right = 10 ** 18
    while left + 1 < right:
        x = (left + right) // 2        
        tmp=0
        for i in range(posi_l-1):
            for j in range(i+1,posi_l):
                if posi[i]*posi[j]<=x:
                    tmp +=1
                else:
                    break
        for i in range(nega_l-1):
            for j in range(i+1,nega_l):
                if nega[i]*nega[j]<=x:
                    tmp +=1
                else:
                    break
        if tmp >= dist:
            right = x
        else:
            left = x
    print(right)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().rstrip().split())
a = list(map(int,input().rstrip().split()))
a.sort()
zero = [a[i] for i in range(n) if a[i]==0]
posi = [a[i] for i in range(n) if a[i]>0]
nega = [a[i] for i in range(n) if a[i]<0][::-1]
zero_l = len(zero)
posi_l = len(posi)
nega_l = len(nega)
zero_pair = zero_l*(n-zero_l) + zero_l*(zero_l-1)//2
posi_pair = posi_l*(posi_l-1)//2 + nega_l*(nega_l-1)//2
nega_pair = posi_l*nega_l

if k <= nega_pair:
    dist = k
    left = -10 ** 18
    right = 0
    while left + 1 < right:
        x = (left + right) // 2        
        tmp=0
        for i in range(nega_l):
            for j in range(posi_l):
                if nega[i]*posi[j]<x:
                    tmp +=1
                else:
                    break
        if tmp >= dist:
            right = x
        else:
            left = x
    print(left)
elif k <= nega_pair+zero_pair:
    print(0)
else:
    dist = k-zero_pair-nega_pair
    left = 0
    right = 10 ** 18
    while left + 1 < right:
        x = (left + right) // 2        
        tmp=0
        for i in range(posi_l-1):
            for j in range(i+1,posi_l):
                if posi[i]*posi[j]<x:
                    tmp +=1
                else:
                    break
        for i in range(nega_l-1):
            for j in range(i+1,nega_l):
                if nega[i]*nega[j]<x:
                    tmp +=1
                else:
                    break
        if tmp >= dist:
            right = x
        else:
            left = x
    print(left)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()
 
 
def is_ok(arg, sei, hu, k):
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    for index, NN in enumerate(sei, 1):
        if NN==0:
            count+=len(sei)-index
        else:
            if NN**2 >= arg:
                break
            count += bisect.bisect_right(sei, ((arg)//NN))-index  # n以下の個数を数える
    for index, NN in enumerate(hu, 1):
        if NN**2 >= arg:
            break
        count += bisect.bisect_right(hu, ((arg)//NN))-index  # n以下の個数を数える
    return count >= k
 
 
def meguru_bisect(ng, ok, sei, hu, k):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, sei, hu, k):
            ok = mid
        else:
            ng = mid
    return ok
 
 
def is_ok2(arg, sei, hu, k):#seiとhuの組み合わせで-arg以上の数がk個あるか？
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    hulen=len(hu)
    for NN in hu:
        count += hulen-bisect.bisect_right(sei, ((-arg)-1)//NN)#n未満の個数を数える
    return count >= k
 
def meguru_bisect2(ng, ok, sei, hu, k):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok2(mid, sei, hu, k):
            ok = mid
        else:
            ng = mid
    return ok
 
def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    sei = []
    hu = []
    for AA in A:
        if AA >= 0:
            sei.append(AA)
        else:
            hu.append(-AA)
    sei.sort()
    hu.sort()
    seinum = len(sei)
    hunum = len(hu)
    if seinum*hunum < k:
        ans=meguru_bisect(-1, 10**18, sei, hu, k-seinum*hunum)
    else:
        ans=meguru_bisect2(-1*10**18, 0, sei, hu, k)
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()


def is_ok(arg, sei, hu, k):
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    for index, NN in enumerate(sei, 1):
        if NN==0:
            count+=len(sei)-index
        else:
            if NN**2 >= arg:
                break
            count += bisect.bisect_right(sei, ((arg)//NN))-index  # n以下の個数を数える
    for index, NN in enumerate(hu, 1):
        if NN**2 >= arg:
            break
        count += bisect.bisect_right(hu, ((arg)//NN))-index  # n以下の個数を数える
    return count >= k


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


def is_ok2(arg, sei, hu, k):#seiとhuの組み合わせで-arg以上の数がk個あるか？
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    hulen=len(hu)
    for NN in hu:
        count += hulen-bisect.bisect_left(sei, (((-arg)-1)//NN)+1)
    return count >= k

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

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    sei = []
    hu = []
    for AA in A:
        if AA >= 0:
            sei.append(AA)
        else:
            hu.append(-AA)
    sei.sort()
    hu.sort()
    seinum = len(sei)
    hunum = len(hu)
    if seinum*hunum < k:
        ans=meguru_bisect(-1, 10**20, sei, hu, k-seinum*hunum)
    else:
        ans=meguru_bisect2(-1*10**20, 0, sei, hu, k)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()


def is_ok(arg, sei, hu, k):
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    for index, NN in enumerate(sei, 1):
        if NN==0:
            count+=len(sei)-index
        else:
            if NN**2 >= arg:
                break
            count += bisect.bisect_right(sei, ((arg)//NN))-index  # n以下の個数を数える
    for index, NN in enumerate(hu, 1):
        if NN**2 >= arg:
            break
        count += bisect.bisect_right(hu, ((arg)//NN))-index  # n以下の個数を数える
    return count >= k


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


def is_ok2(arg, sei, hu, k):#seiとhuの組み合わせで-arg以上の数がk個あるか？
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    hulen=len(hu)
    for NN in hu:
        count += hulen-bisect.bisect_left(sei, (((-arg)-1)//NN)+1)
    return count >= k

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

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    sei = []
    hu = []
    for AA in A:
        if AA >= 0:
            sei.append(AA)
        else:
            hu.append(-AA)
    sei.sort()
    hu.sort()
    seinum = len(sei)
    hunum = len(hu)
    if seinum*hunum < k:
        ans=meguru_bisect(-1, 10**20, sei, hu, k-seinum*hunum)
    else:
        ans=meguru_bisect2(-1*10**20, 0, sei, hu, k)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()


def is_ok(arg, sei, hu, k):
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    for index, NN in enumerate(sei, 1):
        if NN==0:
            count+=len(sei)-index
        else:
            if NN**2 >= arg:
                break
            count += bisect.bisect_right(sei, ((arg)//NN))-index  # n以下の個数を数える
    for index, NN in enumerate(hu, 1):
        if NN**2 >= arg:
            break
        count += bisect.bisect_right(hu, ((arg)//NN))-index  # n以下の個数を数える
    return count >= k


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


def is_ok2(arg, sei, hu, k):#seiとhuの組み合わせで-arg以上の数がk個あるか？
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    hulen=len(hu)
    for NN in hu:
        count += hulen-bisect.bisect_left(sei, (((-arg)-1)//NN)+1)
    return count >= k

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

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    sei = []
    hu = []
    for AA in A:
        if AA >= 0:
            sei.append(AA)
        else:
            hu.append(-AA)
    sei.sort()
    hu.sort()
    seinum = len(sei)
    hunum = len(hu)
    if seinum*hunum < k:
        ans=meguru_bisect(-1, 10**20, sei, hu, k-seinum*hunum)
    else:
        ans=meguru_bisect2(-1*10**20, 0, sei, hu, k)
    print(ans)

if __name__ == '__main__':
    main()