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:
# 解説放送の改変
# aを負0正に分けて処理
# 尺取り?

def main():
    inf = 10 ** 18 + 1

    def bs_kth_lt_0():
        def shakutori(cand):
            ret = 0
            cand_pos = -cand  # 正に変換
            r = len_p - 1
            for l in range(len_m):
                while r > 0 and m[l] * p[r] <= cand_pos:
                    r -= 1
                if r == 0 and m[l] * p[r] <= cand: break
                ret += r + 1
            return ret

        ok, ng = -inf, 0
        while ng - ok > 1:
            cand = (ng + ok) // 2
            tot = shakutori(cand)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

    def bs_kth_gt_0():
        def shakutori(lis, length):
            ret = 0
            r = length - 1
            for l in range(length):
                while r - l > 0 and lis[l] * lis[r] >= cand:
                    r -= 1
                # r==l または lis[l]*lis[r]<candを満たすl,r
                if l == r: break
                ret += r - l
            return ret

        ok, ng = 0, inf
        while ng - ok > 1:
            cand = (ng + ok) // 2
            tot = shakutori(m, len_m) + shakutori(p, len_p)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

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

    m, z, p = [], [], []
    for x in a:
        if x < 0:
            m.append(x)
        elif x == 0:
            z.append(x)
        else:
            p.append(x)

    *m, = sorted(-x for x in m)  # 正に符号変換して昇順ソート
    p.sort()
    # 正数昇順にしておく

    len_m, len_z, len_p = len(m), len(z), len(p)

    cnt_m = len_m * len_p
    cnt_z = len_z * (len_z - 1) // 2 + len_z * (n - len_z)

    if k <= cnt_m:
        # k番目の値は負
        ans = bs_kth_lt_0()
        print(ans)
        return

    elif k <= cnt_m + cnt_z:
        # k番目の値は0
        print(0)
        return
    else:
        # k番目の値は正
        k -= cnt_m + cnt_z  # 正の値の中での順位に直す

        ans = bs_kth_gt_0()
        print(ans)
        return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import bisect
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

def check(x):
    cnt = 0
    for a in A:
        if a == 0:
            if x > 0:
                cnt += n
        elif a > 0:
            cnt += bisect.bisect_right(A, x//a)
        elif a < 0:
            cnt += n - bisect.bisect_left(A, (x-1)//a)
        if a*a <= x:
            cnt -= 1
    return cnt < k*2

l, r = -10**18-10, 10**18+10
while (r-l)>1:
    m = (l+r)//2
    if check(m):
        l = m
    else:
        r = m
print(r)

Submission status: Wrong Answer

Solution code:
#大きな数の割り算は計算重いかも，for文内も掛け算の二分探索に
#neg,zero,posで分けてみる？(全部正，全部負などのケースで遅くなると思うのだが...)
import bisect
import sys
input = sys.stdin.readline

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

#積がX未満になるものがK-1個以下になる最大のXを探す


s0=bisect.bisect_left(A,0)



ng=10**18+1
ok=-ng

while ng-ok>1:
    X=(ok+ng)//2
    temp=0
    
    for i in range(N):
        if A[i]>0:
            #A[i]*A[j]がX未満となるjの個数を数える
            
            if X>=0:
                l=s0
                r=N
            else:
                l=-1
                r=s0
                
            
            while r-l>1:
                med=(l+r)//2
                if A[i]*A[med]<X:
                    l=med
                else:
                    r=med
            temp+=r
            if r>i:
                temp-=1

        elif A[i]<0:
            #A[i]*A[j]がX未満となるjの個数を数える

            if X>=0:
                l=-1
                r=s0
            else:
                l=s0
                r=N
            
            while r-l>1:
                med=(l+r)//2
                if A[i]*A[med]<X:
                    r=med
                else:
                    l=med
            temp+=N-r
            if r<=i:
                temp-=1
            
        else:
            if X>0:
                temp+=N-1

            
    temp=temp//2
    
    if temp>=K:
        ng=X
    else:
        ok=X

print(ok)

Submission status: Wrong Answer

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

def main():
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    L=min(a[0]**2,a[0]*a[-1],a[-1]**2)-1
    R=max(a[0]**2,a[0]*a[-1],a[-1]**2)
    while L+1<R:
        X=(L+R)//2
        cnt=0
        for i in range(n):
            l,r=-1,n
            if a[i]<0:
                while l+1<r:
                    x=(l+r)//2
                    if a[x]*a[i]<X:
                        r=x
                    else:
                        l=x
                cnt+=n-r
            else:
                while l+1<r:
                    x=(l+r)//2
                    if a[x]*a[i]<X:
                        l=x
                    else:
                        r=x
                cnt+=r
            if a[i]*a[i]<X:
                cnt-=1
        cnt/=2
        if cnt<k:
            L=X
        else:
            R=X
    print(L)

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from  bisect import bisect_left,bisect_right
    n,k=map(int,input().split())
    A=list(map(int,input().split())) 
    
    Am,Az,Ap=[],[],[]
    for i in range(n):
      if A[i]<0:
        Am.append(A[i])
      elif A[i]==0:
        Az.append(A[i])
      else:
        Ap.append(A[i])      
    Am.sort()
    Az.sort()
    Ap.sort()
    #print(Az,Am,Ap)
    lm,lz,lp=len(Am),len(Az),len(Ap) 
    
    def cnt_pr(x): #ある数字の組でその積がx以上となる組の数
        if x<=0:
            ans=lz*(n-lz)+lz*(lz-1)//2+lp*(lp-1)//2+lm*(lm-1)//2
            a=0
            for p in Ap:
                a+=lm-bisect_left(Am,x/p)
            return ans+a
          
        else:
            ans=0
            for p in Ap:
                ans+=lp-bisect_left(Ap,x/p)
                if p**2>=x:
                  ans-=1
            for m in Am:
                ans+=bisect_right(Am,x/m)
                if m**2>=x:
                  ans-=1
            return ans//2
          
    #print(cnt_pr(-6),cnt_pr(-7),cnt_pr(6))
    right=10**18+1
    left=-10**18-1
    k=n*(n-1)//2-k+1
    while right-left>1:
        mid=(left+right)//2
        #print(mid)
        if cnt_pr(mid)<k:
            right=mid
        else:
            left=mid
    
    print(left)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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


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


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

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

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

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

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

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

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

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    from  bisect import bisect_left,bisect_right
    n,k=map(int,input().split())
    A=list(map(int,input().split())) 
    A=np.array(A)
    Am=A[A<0]
    Az=A[A==0]
    Ap=A[A>0]
    Am.sort()
    Az.sort()
    Ap.sort()
    #print(Az,Am,Ap)
    lm,lz,lp=len(Am),len(Az),len(Ap) 
    
    def cnt_pr(x): #ある数字の組でその積がx以上となる組の数
        if x<=0:
            ans=lz*(n-lz)+lz*(lz-1)//2+lp*(lp-1)//2+lm*(lm-1)//2
            a=0
            for p in Ap:
                a+=lm-bisect_left(Am,x/p)
            return ans+a//2
          
        else:
            ans=0
            for p in Ap:
                ans+=lp-bisect_left(Ap,x/p)
                if p**2>=x:
                  ans-=1
            for m in Am:
                ans+=bisect_right(Am,x/m)
                if m**2>=x:
                  ans-=1
            return ans//2
          
    #print(cnt_pr(8),cnt_pr(7),cnt_pr(6))
    right=10**18+1
    left=-10**18-1
    k=n*(n-1)//2-k
    while right-left>1:
        mid=(left+right)//2
        #print(mid)
        if cnt_pr(mid)<k:
            right=mid
        else:
            left=mid
    
    print(left)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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


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


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

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

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

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

    if K <= M:
        minuses = -minuses[::-1]
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            # mid以下の積はK個未満か？ left以下の積は常にK個未満
            mid = (left + right) // 2
            mid = -mid
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses), side='left')).sum()

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

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

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

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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


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

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

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

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

    if K <= M:
        minuses = np.abs(minuses[::-1])
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            # mid以下の積はK個未満か？ left以下の積は常にK個未満
            mid = (left + right) // 2
            mid = -mid
            cnt = (p - np.searchsorted(pluses, (mid + 1) // minuses, side='left')).sum()

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

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

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

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  Ans, Aps, A0s = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      A0s.append(A)
    else:
      Ans.append(A)
  Aps.sort()
  A0s.sort()
  Ans.sort()
  
  cp, c0, cn = (len(Aps)*(len(Aps)-1) + len(Ans)*(len(Ans)-1))//2, len(A0s) * (len(Ans) + len(Aps) + (len(A0s)-1)//2), len(Ans) * len(Aps)
  
  if k <= cn:
    flag = 0
  elif k <= cn + c0:
    print(0)
    return
  else:
    flag = 1
  
  def count(l, r, x, ub, xs):
    while True:
      mid = (l+r)//2
      if x > 0:
        if r - l <=1:
          return r - (1 if x**2 <= ub else 0) * flag
        if x * xs[mid] <= ub:
          l = mid
        else:
          r = mid
      else:
        if r - l <=1:
          return len(xs) - r - (1 if x**2 <= ub else 0) * flag
        if x * xs[mid] <= ub:
          r = mid
        else:
          l = mid

  def bs(l, r, xs, ys, k):
    if flag == 1:
      while True:
        mid = (l+r) // 2
        if r - l <= 1:
          return r
        tot = 0
        for x in xs:
          tot += count(-1, len(xs), x, mid, xs)
        for y in ys:
          tot += count(-1, len(ys), y, mid, ys)
        tot //= 2
        if tot < k:
          l = mid
        else:
          r = mid
    else:
      while True:
        mid = (l+r) // 2
        if r - l <= 1:
          return r
        tot = 0
        for x in xs:
          tot += count(-1, len(ys), x, mid, ys)
        if tot < k:
          l = mid
        else:
          r = mid
        
  if flag == 1:
    print(bs(0, MAX+1, Aps, Ans, k - cn - c0))
  else:
    print(bs(MIN-1, 0, Aps, Ans, k))
    
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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


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


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

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

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

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

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            # mid以下の積はK個未満か？ left以下の積は常にK個未満
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses).astype(int), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

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

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

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

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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


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

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

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

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

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            # mid以下の積はK個未満か？ left以下の積は常にK個未満
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses).astype(int), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

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

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

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

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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


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

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

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

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

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            # mid以下の積はK個未満か？ left以下の積は常にK個未満
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses).astype(int), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

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

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

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

        print(right)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def num_search(l,r,mid):
  total = 0
  for i in range(N):
    if(A[i] < 0):
      l=-1
      r=N
      while l+1 < r:
        c = (l+r)//2
        if(A[c]*A[i]<mid):
          r=c
        else:
          l=c
        #print(str(i)+'[m] l='+str(l)+' r='+str(r))
      total += N-r
    else:
      l=-1
      r = N
      while l+1 < r:
        c = (l+r)//2
        if(A[c]*A[i]<mid):
          l=c
        else:
          r=c
        #print(str(i)+'[p] l='+str(l)+' r='+str(r))
      total += r
  if(A[i]*A[i] < mid):
    total-=1
  total = total//2
  #print('total = '+str(total))
  return total < K

low = -100000000000000
high = 100000000000000
while low+1 < high:
  mid = (low + high) // 2
  ok = num_search(low,high,mid)
  #print(str(low)+' '+str(high))
  if(ok):
    low = mid
  else:
    high = mid
print(low)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=pL=0

#積がx以下になる組み合わせの数
def f(x):
    global pR,pL
    ret=0
    if x<0:
        pL=-1
        for na in nA:
            ret+=g2(pA,na,x)
        pL=-1
        for pa in pA:
            ret+=g2(nA,pa,x)
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        pR=len(nA)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        pR=len(pA)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=pR
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    pR=over
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    global pL
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=pL
    r=len(L)-1
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    pL=under
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)
        for na in nA:
            ret+=g2(pA,na,x)
        pR=len(nA)
        for pa in pA:
            ret+=g2(nA,pa,x)
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        pR=len(nA)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        pR=len(pA)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=pR
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    pR=over
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=pR
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    pR=under
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left as bl

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

    inf = 10**18+1

    ok = -inf
    ng = inf
    start_0 = bl(a, 0)
    start_1 = bl(a, 1)

    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        if mid > 0:
            cnt += n * (start_1 - start_0)
            if start_0 > 0:
                now = 0
                for i in a[start_0-1::-1]:
                    while now < start_0:
                        if i*a[now] >= mid:
                            now += 1
                        else:
                            break
                    cnt += n - now
            now = n
            for i in a[start_1:]:
                while now > start_1:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        elif mid < 0:
            now = start_1
            for i in a[:start_0]:
                while now < n:
                    if i*a[now] >= mid:
                        now += 1
                    else:
                        break
                cnt += n - now
            now = start_0
            for i in a[n-1:start_1-1:-1]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        else:
            cnt += (start_1-start_0)*n

        cnt -= len([None for i in a if i*i < mid])
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Submission status: Wrong Answer

Solution code:
import bisect
N, K = map(int, input().split())
A = sorted(map(int, input().split()))
bleft = bisect.bisect_left
bright = bisect.bisect_right
zero_i = bleft(A, 0)
zero_i2 = bright(A, 0)
tmp_zero_num = zero_i2-zero_i
zero_num = tmp_zero_num * (N-tmp_zero_num) + tmp_zero_num*(tmp_zero_num-1)//2

minus_A = A[:zero_i][::-1]
plus_A = A[zero_i2:]
LM = len(minus_A)
LP = len(plus_A)

minus_num = len(minus_A) * len(plus_A)
plus_num = len(minus_A)*(len(minus_A)-1)//2 + len(plus_A)*(len(plus_A)-1)//2
if K <= minus_num:
    def isOK(score):
        count = 0
        for a in minus_A:
            border_score = (score*(-1)) // (-a)
            #print(a, border_score)
            index = bright(plus_A, border_score)
            count += LP - index

        if count >= K:
            return True
        else:
            return False
    ok = minus_A[0] * plus_A[0]
    ng = minus_A[-1] * plus_A[-1] - 1

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

    print(ok)
    # print(plus_A, minus_A)
elif K <= zero_num+minus_num:
    print(0)
else:
    def isOK(score):
        count = 0
        if LM > 1:
            for i, a in enumerate(minus_A):
                if i == LM - 1:
                    break
                border_score = score//a
                index = bright(minus_A[i+1:], border_score)
                count += index
                if count >= K:
                    return True
        if LP > 1:
            for i, a in enumerate(plus_A):
                if i == LP - 1:
                    break
                border_score = score//a
                index = bright(plus_A[i+1:], border_score)
                count += index
                #print(count)
                if count >= K:
                    return True
        return False

    K -= (minus_num + zero_num)
    minus_A = [-1 * a for a in minus_A]

    if len(minus_A) <= 1:
        ok = plus_A[-1]*plus_A[-2]
        ng = plus_A[0]*plus_A[1] - 1
    elif len(plus_A) <= 1:
        ok = minus_A[-1]*minus_A[-2]
        ng = minus_A[0]*minus_A[1] - 1
    else:
        ok = max(minus_A[-1]*minus_A[-2], plus_A[-1]*plus_A[-2])
        ng = min(minus_A[0]*minus_A[1], plus_A[0]*plus_A[1]) - 1

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

Submission status: Wrong Answer

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

a.sort()

#2分探索
#負の数あるぞ

j = bisect.bisect_left(a,-0)##
l = bisect.bisect_right(a,0)#3
a1 = a[:j]
a2 = a[l:]
if j*(n-l)>=k:##負の数で揃う
    mx = 0
    mn = -max(a1[0]*a1[0],a2[-1]*a2[-1])-1##
    while mx-mn>1:
        md = (mx+mn)//2
        cnt = 0
        for t in range(j):
            tmp = bisect.bisect_left(a2,md//a1[t])
            cnt += n-l-tmp
        if cnt >=k:
            mx = md
        else:
            mn = md
        print(mx)
        exit()
k -= j*(n-l)

if k<=(l-j)*(l-j-1)//2+(n-l+j)*(l-j):
    print(0)
    exit()
#print(k,(n-l+j)*(l-j)+(l-j)*(l-j-1)//2)
k-=(l-j)*(l-j-1)//2+(n-l+j)*(l-j)
#print(k,k)
if a1 and a2:
    mx = max(a1[-1]*a1[-1],a2[-1]*a2[-1])+1##
elif a1:
    mx = a1[-1]**2+1
else:
    mx = a2[-1]**2+1
mn = -1
a1 = [-a1[j-i-1] for i in range(j)]
while mx-mn>1:
    md = (mx+mn)//2
    cnt = 0
    for t in range(j):
        tmp = bisect.bisect_right(a1,md//a1[t])
        cnt += tmp
        if tmp >=t+1:
            cnt-=1
    for t in range(n-l):
        tmp = bisect.bisect_right(a2,md//a2[t])
        cnt += tmp
        if tmp>=t+1:
            tmp-=1
    if cnt >= 2*k:
        mx = md
    else:
        mn = md
print(mx)