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 bisect import bisect_left, bisect_right

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

INF = 10**20
ga = bisect_left(A, 0)
gc = N-bisect_right(A, 0)
gb = N-ga-gc

if K<=ga*gc:
    l, r = -INF, 1
    while abs(r-l)>1:
        m = (r+l)//2
        b = 0
        for i in range(ga+gb, N):
            b += bisect_left(A, m/A[i])
        if b>K:
            r = m
        else:
            l = m
    print(l)
elif ga*gc<K<=ga*gc+ga*gb+gb*gc+(gb*(gb-1)//2):
    print(0)
else:
    K -= ga*gc+ga*gb+gb*gc+(gb*(gb-1)//2)
    l1, l2 = [], []
    for i in range(ga):
        l1.append(-A[i])
    for i in range(ga+gb, N):
        l2.append(A[i])
    l1.sort()
    l2.sort()

    l, r = -1, INF
    while abs(r-l)>1:
        m = (r+l)//2
        b = 0
        for i in range(ga):
            tmp = bisect_right(l1, m//l1[i])
            if tmp>i:
                tmp -= 1
            b += tmp
        for i in range(gc):
            tmp = bisect_right(l2, m//l2[i])
            if tmp>i:
                tmp -= 1
            b += tmp
        b //= 2
        
        if b>=K:
            r = m
        else:
            l = m
    print(r)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
neg_end = bisect_left(A, 0)
pos_start = bisect_right(A, 0)

pos_cnt = N - pos_start
neg_cnt = neg_end
zero_cnt = N - pos_cnt - neg_cnt

neg_pairs_cnt = pos_cnt * neg_cnt
zero_pairs_cnt = zero_cnt * (pos_cnt + neg_cnt) + (zero_cnt * (zero_cnt-1) // 2)

if K <= neg_pairs_cnt:
  # X以下のpairはK個以上あるか？
  ok, ng = 0, -10**18
  while abs(ok - ng) > 1:
    X = (ok+ng) // 2
    or_higher_cnt, r = 0, pos_start
    # それぞれのnegごとに尺取り法
    for l in range(neg_end):
      while r < N and A[l] * A[r] > X:
        r += 1
      # positive_integers - (max_point - positive_start_index)
      or_higher_cnt += pos_cnt - (r - pos_start)

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

elif K <= zero_pairs_cnt:
  print(0)

else:
  K -= (neg_pairs_cnt + zero_pairs_cnt)
  ok, ng = 10**18, 0
  while abs(ok - ng)> 1:
    X = (ok+ng) // 2
    or_higher_cnt = 0

    r = N - 1
    for l in range(pos_start, N):
      while r < N and A[l] * A[r] > X and l < r:
        r -= 1
      or_higher_cnt += max(0, r-l)

    l = 0
    for r in range(neg_end-1, -1, -1):
      while l < N and A[l] * A[r] > X and l < r:
        l += 1
      or_higher_cnt += max(0, r-l)

    if or_higher_cnt >= K:
      ok = X
    else:
      ng = X

  print(ok)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=list(map(int, input().split()))
# slice
tmp=sum(p[:k])
res = tmp
for i in range(n-k):
  tmp -= p[i]
  tmp += p[i+k]
  res = max(res, tmp)
print((res+k)/2)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int, input().split()))
limit = 10**9
comb=[]
for i in range(n):
  for j in range(i):
    val = a[i]*a[j]
    if val > limit:
      comb.append(10**9-1)
    comb.append(val)
comb.sort()
print(comb[k-1])

Submission status: Wrong Answer

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

negs, zeros, pos = [], [], []
for i in range(n):
    if a[i] < 0:
        negs.append(-a[i])
    elif a[i] == 0:
        zeros.append(a[i])
    else:
        pos.append(a[i])

negs.sort()
pos.sort()
n_neg_prod = len(negs) * len(pos)
n_zero_prod = len(zeros) * (len(zeros) - 1) // 2 + len(zeros) * (len(negs) + len(pos))
n_pos_prod = len(negs) * (len(negs) - 1) // 2 + len(pos) * (len(pos) - 1) // 2

from bisect import bisect_left
if k <= n_neg_prod:
    k = n_neg_prod - k + 1

    def C(x):
        # No of products <= x
        count = 0
        for i, a in enumerate(pos):
            div = x // a
            idx = bisect_left(negs, div)
            if idx == len(negs):
                count += len(negs)
            elif negs[idx] != div:
                count += idx
            else:
                count += idx + 1

        return count

    lb = pos[0] * negs[0] - 1
    ub = pos[-1] * negs[-1] + 1
    while (ub - lb) > 1:
        mid = (lb + ub) // 2
        if C(mid) < k:
            lb = mid
        else:
            ub = mid
    print(-ub)

elif k <= n_neg_prod + n_zero_prod:
    print(0)
else:
    k -= (n_neg_prod + n_zero_prod)

    def C(x):
        # No of products <= x
        count = 0
        for arr in [negs, pos]:
            for i, a in enumerate(arr):
                div = x // a
                if div >= a:
                    count += i
                else:
                    idx = bisect_left(arr, div)
                    if arr[idx] != div:
                        count += idx
                    else:
                        count += idx + 1

        return count

    m, M = 10 ** 18, 0
    if pos:
        m, M = min(m, pos[0] ** 2), max(M, pos[-1] ** 2)
    if negs:
        m, M = min(m, negs[0] ** 2), max(M, negs[-1] ** 2)
    lb = m - 1
    ub = M + 1
    while (ub - lb) > 1:
        mid = (lb + ub) // 2
        if C(mid) < k:
            lb = mid
        else:
            ub = mid
    print(ub)

Submission status: Wrong Answer

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

negs, zeros, pos = [], [], []
for i in range(n):
    if a[i] < 0:
        negs.append(-a[i])
    elif a[i] == 0:
        zeros.append(a[i])
    else:
        pos.append(a[i])

negs.sort()
pos.sort()
n_neg_prod = len(negs) * len(pos)
n_zero_prod = len(zeros) * (len(zeros) - 1) // 2 + len(zeros) * (len(negs) + len(pos))
n_pos_prod = len(negs) * (len(negs) - 1) // 2 + len(pos) * (len(pos) - 1) // 2

from bisect import bisect_left
if k <= n_neg_prod:
    k = n_neg_prod - k + 1

    def C(x):
        # No of products <= x
        count = 0
        for i, a in enumerate(pos):
            div = x // a
            idx = bisect_left(negs, div)
            if idx < len(negs) and negs[idx] != div:
                count += idx
            else:
                count += idx + 1

        return count

    lb = pos[0] * negs[0] - 1
    ub = pos[-1] * negs[-1] + 1
    while (ub - lb) > 1:
        mid = (lb + ub) // 2
        if C(mid) < k:
            lb = mid
        else:
            ub = mid
    print(-ub)

elif k <= n_neg_prod + n_zero_prod:
    print(0)
else:
    k -= (n_neg_prod + n_zero_prod)

    def C(x):
        # No of products <= x
        count = 0
        for arr in [negs, pos]:
            for i, a in enumerate(arr):
                div = x // a
                if div >= a:
                    count += i
                else:
                    idx = bisect_left(arr, div)
                    if arr[idx] != div:
                        count += idx
                    else:
                        count += idx + 1

        return count

    m, M = 10 ** 18, 0
    if pos:
        m, M = min(m, pos[0] ** 2), max(M, pos[-1] ** 2)
    if negs:
        m, M = min(m, negs[0] ** 2), max(M, negs[-1] ** 2)
    lb = m - 1
    ub = M + 1
    while (ub - lb) > 1:
        mid = (lb + ub) // 2
        if C(mid) < k:
            lb = mid
        else:
            ub = mid
    print(ub)

Submission status: Wrong Answer

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

negs, zeros, pos = [], [], []
for i in range(n):
    if a[i] < 0:
        negs.append(a[i])
    elif a[i] == 0:
        zeros.append(a[i])
    else:
        pos.append(a[i])

negs.sort()
pos.sort()
n_neg_prod = len(negs) * len(pos)
n_zero_prod = len(zeros) * (len(zeros) - 1) // 2 + len(zeros) * (len(negs) + len(pos))
n_pos_prod = len(negs) * (len(negs) - 1) // 2 + len(pos) * (len(pos) - 1) // 2

import math
from bisect import bisect_left, bisect_right
if k <= n_neg_prod:
    def C(x):
        count = 0
        for a in pos:
            div = int(math.ceil(x / a))
            idx = bisect_left(negs, div)
            count += len(negs) - idx
        return count

    lb = -10 ** 18
    ub = 0
    while (ub - lb) > 1:
        mid = (lb + ub) // 2
        if C(mid) >= n_neg_prod - k + 1:
            lb = mid
        else:
            ub = mid
    print(lb)

elif k <= n_neg_prod + n_zero_prod:
    print(0)
else:
    k -= (n_neg_prod + n_zero_prod)
    negs2 = [-b for b in negs]
    negs2.sort()

    def C(x):
        # No of products <= x
        count = 0
        for arr in [negs2, pos]:
            for i, a in enumerate(arr):
                div = x // a
                if div >= a:
                    count += i
                else:
                    idx = bisect_left(arr, div)
                    if arr[idx] != div:
                        count += idx
                    else:
                        count += idx + 1

        return count

    lb = 0
    ub = 10 ** 18
    while (ub - lb) > 1:
        mid = (lb + ub) // 2
        if C(mid) < k:
            lb = mid
        else:
            ub = mid
    print(ub)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
import bisect
def func(x): #x未満となる個数を返す
  ret=0
  for i in range(n):
    if a[i]>0:
      ret+=max(0,bisect.bisect_left(a,x/a[i])-(i+1))
    elif a[i]==0:
      ret+=(n-(i+1)) if x>0 else 0
    else:
      ret+=min(n-(i+1),n-bisect.bisect_right(a,x/a[i]))
  return ret

l,r=-pow(10,18),pow(10,18)+1
while r-l>1:
  x=(l+r)//2
  b=func(x)
  if b>=k:
    l,r=l,x
  else:
    l,r=x,r
x=(l+r)//2
print(x)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,K = LI()
    pl = []
    mi = []
    z = 0
    for x in sys.stdin.readline().split():
        x = int(x)
        if x > 0:
            pl.append(x)
        elif x < 0:
            mi.append(-x)
        else:
            z += 1
    pl.sort()
    mi.sort()

    minus = len(pl) * len(mi)
    zero = z * (len(pl) + len(mi)) + z * (z-1) // 2

    h = INF
    l = -INF-1

    while l+1 < h:
        m = (h+l)//2

        if m > 0:
            k = minus + zero
            j = len(pl)-1
            for i in range(len(pl)-1):
                if i >= j: break
                while pl[i] * pl[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
            j = len(mi)-1
            for i in range(len(mi)-1):
                if i >= j: break
                while mi[i] * mi[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
        elif m < 0:
            k = 0
            j = 0
            if len(mi) > 0:
                for i in range(len(pl)):
                    while -pl[i] * mi[j] > m:
                        j += 1
                        if j == len(mi): break
                    else:
                        k += len(mi) - j
                        continue
                    break
        else:
            k = minus + zero

        if k < K:
            l = m
        else:
            h = m

    print(h)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,K = LI()
    pl = []
    mi = []
    z = 0
    for x in sys.stdin.readline().split():
        x = int(x)
        if x > 0:
            pl.append(x)
        elif x < 0:
            mi.append(-x)
        else:
            z += 1
    pl.sort()
    mi.sort()

    minus = len(pl) * len(mi)
    zero = z * (len(pl) + len(mi)) + z * (z-1) // 2

    h = 10**18
    l = -10**18-1

    while l+1 < h:
        m = (h+l)//2

        if m > 0:
            k = minus + zero
            j = len(pl)-1
            for i in range(len(pl)-1):
                if i >= j: break
                while pl[i] * pl[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
            j = len(mi)-1
            for i in range(len(mi)-1):
                if i >= j: break
                while mi[i] * mi[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
        elif m < 0:
            k = 0
            j = 0
            if len(mi) > 0:
                for i in range(len(pl)):
                    while -pl[i] * mi[j] > m:
                        j += 1
                        if j == len(mi): break
                    else:
                        k += len(mi) - j
                        continue
                    break
        else:
            k = minus + zero

        if k < K:
            l = m
        else:
            h = m

    print(h)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,K = LI()
    pl = []
    mi = []
    z = 0
    for x in sys.stdin.readline().split():
        x = int(x)
        if x > 0:
            pl.append(x)
        elif x < 0:
            mi.append(-x)
        else:
            z += 1
    pl.sort()
    mi.sort()

    minus = len(pl) * len(mi)
    zero = z * (len(pl) + len(mi)) + z * (z-1) // 2

    h = 10**18+1
    l = -10**18

    while l+1 < h:
        m = (h+l)//2

        if m > 0:
            k = minus + zero
            j = len(pl)-1
            for i in range(len(pl)-1):
                if i >= j: break
                while pl[i] * pl[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
            j = len(mi)-1
            for i in range(len(mi)-1):
                if i >= j: break
                while mi[i] * mi[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
        elif m < 0:
            k = 0
            j = 0
            for i in range(len(pl)):
                while -pl[i] * mi[j] > m:
                    j += 1
                    if j == len(mi): break
                else:
                    k += len(mi) - j
                    continue
                break
        else:
            k = minus

        if k >= K:
            h = m
        else:
            l = m

    print(h)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from bisect import *

def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    
    plus, p = [], 0
    minus, m = [], 0
    zero = 0
    
    for a in A:
        if a == 0: zero += 1
        elif a > 0: plus.append(a); p += 1
        else: minus.append(a); m += 1
    
    plus = sorted(plus)
    minus = sorted(minus)
        
    if K <= p*m:
        l = -10**18
        r = -1
        
        while r-l > 1:
            c = 0
            mid = (r+l) // 2
            
            for a in plus:
                c += bisect_right(minus, mid//a)
                
            if c >= K: r = mid
            else: l = mid
            
        print(r)
        
    elif K <= zero*(zero-1)//2 + p*m:
        print(0)
        
    else:
        l = 0
        r = 10**18
        K -= ((zero*(zero-1))//2 + zero*(p+m) + p*m)
        
        for i in range(m): minus[i] = abs(minus[i])
        minus = sorted(minus)
        
        while r-l > 1:
            c = 0
            mid = (r+l) // 2
            
            for i in range(p):
                idx = bisect_right(plus, mid//plus[i])
                if i < idx: idx -= 1
                c += idx
                
            for i in range(m):
                idx = bisect_right(minus, mid//minus[i])
                if i < idx: idx -= 1
                c += idx
                
            c //= 2
            if c >= K: r = mid
            else: l = mid
            
        print(r)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import *

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

plus, p = [], 0
minus, m = [], 0
zero = 0

for a in A:
    if a == 0: zero += 1
    elif a > 0: plus.append(a); p += 1
    else: minus.append(a); m += 1

plus = sorted(plus)
minus = sorted(minus)
    
if K <= p*m:
    l = -10**18
    r = -1
    
    while r-l > 1:
        c = 0
        mid = (r+l) // 2
        
        for a in plus:
            c += bisect_right(minus, mid//a)
            
        if c >= K: r = mid
        else: l = mid
        
    print(r)
    
elif K <= zero*(zero-1)//2 + p*m:
    print(0)
    
else:
    l = 0
    r = 10**18
    K -= ((zero*(zero-1))//2 + zero*(p+m) + p*m)
    
    for i in range(m): minus[i] = abs(minus[i])
    minus = sorted(minus)
    
    while r-l > 1:
        c = 0
        mid = (r+l) // 2
        
        for i in range(p):
            idx = bisect_right(plus, mid//plus[i])
            if i < idx: idx -= 1
            c += idx
            
        for i in range(m):
            idx = bisect_right(minus, mid//minus[i])
            if i < idx: idx -= 1
            c += idx
            
        c //= 2
        if c >= K: r = mid
        else: l = mid
        
    print(r)

Submission status: Wrong Answer

Solution code:
import sys

def main():
  input = sys.stdin.readline
  n, K = map(int, input().split())
  a = [int(x) for x in input().split()]
  z = 0
  minus_list = []
  plus_list = []
  for i in range(n):
    if a[i] < 0:
      minus_list.append(a[i])
    if a[i] == 0:
      z += 1
    if a[i] > 0:
      plus_list.append(a[i])
  m = len(minus_list)
  minus = m*(n-z-m)
  zero = z*(n-z)+z*(z-1)//2
  plus = n*(n-1)//2-minus-zero
  if minus < K <= minus+zero:
    print(0)
  elif K <= minus:
    minus_list.sort()
    plus_list.sort()
    l, r = -pow(10, 18)-1, 0
    while r-l > 1:
      key = (r+l)//2
      count = 0
      for i in range(len(minus_list)):
        p, q = -1, len(plus_list)
        while q-p>1:
          index = (p+q)//2
          if minus_list[i]*plus_list[index] <= key:
            p = index
          else:
            q = index
        count += q
      if count <= K:
        l = key
      else:
        r = key
    print(r)
  else:
    minus_list.sort(reverse=True)
    plus_list.sort()
    l, r = 0, pow(10, 18)+1
    while r-l > 1:
      key = (r+l)//2
      count = 0
      for i in range(len(minus_list)):
        p, q = i, len(minus_list)
        while q-p>1:
          index = (p+q)//2
          if minus_list[i]*minus_list[index] <= key:
            p = index
          else:
            q = index
        count += (p-i)
      for i in range(len(plus_list)):
        p, q = i, len(plus_list)
        while q-p>1:
          index = (p+q)//2
          if plus_list[i]*plus_list[index] <= key:
            p = index
          else:
            q = index
        count += (p-i)
      if count < K-minus-zero:
        l = key
      else:
        r = key
    print(r)
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import numpy as np
stdin = open(0)

N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().split(), np.int64)


A = np.sort(A)
zero = A[A == 0]
pos = list(A[A > 0])
neg = list(A[A < 0])

neg_count = len(pos) * len(neg)
pos_count = len(pos) * (len(pos) - 1) // 2 + len(neg) * (len(neg) - 1) // 2
zero_count = N * (N - 1) // 2 - neg_count - pos_count

if K > neg_count and K <= neg_count + zero_count:
    print(0)
    exit(0)

def f(x):
    """x以下の積の組み合わせを数える(k番目が負の場合)"""
    count = 0
    pos_idx = None
    neg_idx = len(neg) - 1
    for idx, p in enumerate(reversed(pos)):
        if p * neg[neg_idx] <= x:
            pos_idx = len(pos) - idx - 1
        else:
            break
    # pos_idxに最大の負の値x正の値 <= xを満たす最小の正値のindexが入っている
    if pos_idx is not None:
        count += len(pos) - pos_idx
    else:
        pos_idx = 0
    while neg_idx > 0:
        neg_idx -= 1
        ans = None
        for i in reversed(range(pos_idx + 1)):
            if pos[i] * neg[neg_idx] <= x:
                ans = i
                break
        if ans is None:
            break
        # iにはneg_idxの位置の負数と掛けたときに<=xを満たす最小の正数のindexが入る
        # print(i)
        count += len(pos) - ans
        pos_idx = i
    return count

def g(x):
    """x以下の積の組み合わせを数える(k番目が正の場合)"""
    count = neg_count + zero_count
    # print('c1', count)
    l_idx = 0
    r_idx = 0
    # 正数 x 正数の場合
    for idx, p in enumerate(reversed(pos)):
        if p * pos[l_idx] <= x:
            r_idx = len(pos) - idx - 1
            break
    if r_idx > 0:
        count += (r_idx + 1) - 1  # index = 0の分は引く
        while r_idx - l_idx > 0:
            l_idx += 1
            ans = l_idx
            # print(l_idx, r_idx)
            for i in reversed(range(l_idx + 1, r_idx + 1)):
                # print(i, pos[i], l_idx, pos[l_idx])
                if pos[i] * pos[l_idx] <= x:
                    ans = i
                    break
            # print('ans', ans, l_idx)
            if ans > l_idx:
                count += ans - l_idx
                r_idx = ans
            else:
                break
    # print('c2', count)
    # 負数 x 負数の場合
    r_idx = len(neg) - 1
    l_idx = len(neg) - 1
    for idx, n in enumerate(neg):
        if n * neg[r_idx] <= x:
            l_idx = idx
            break
    # print(l_idx, r_idx)
    if l_idx < r_idx:
        count += len(neg) - l_idx - 1 # r_idxの分は引く
        # print('c3', count)
        while r_idx - l_idx > 0:
                r_idx -= 1
                ans = r_idx
                # print(l_idx, r_idx)
                for i in range(l_idx, r_idx):
                    # print(i, pos[i], l_idx, pos[l_idx])
                    if neg[i] * neg[r_idx] <= x:
                        ans = i
                        break
                # print(l_idx, r_idx, ans)
                # print('ans', ans, l_idx)
                if ans < r_idx:
                    count += r_idx - ans
                    l_idx = ans
                else:
                    break
    return count


def h(x):
    return f(x) if K <= neg_count else g(x)

# print(h(100000000000))

l = -1 * 10 ** 18
r = 10 ** 18
if K <= neg_count:
    r = 0
    h = f
else:
    l = 0
    h = g

while l + 1 < r:
    mid = (l + r) // 2
    count = h(mid)
    # print(mid, count)
    if count >= K:
        r = mid
    else:
        l = mid
print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np
stdin = open(0)

N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().split(), np.int64)


A = np.sort(A)
zero = A[A == 0]
pos = list(A[A > 0])
neg = list(A[A < 0])

neg_count = len(pos) * len(neg)
pos_count = len(pos) * (len(pos) - 1) // 2 + len(neg) * (len(neg) - 1) // 2
zero_count = N * (N - 1) // 2 - neg_count - pos_count

if K > neg_count and K <= neg_count + zero_count:
    print(0)
    exit(0)

def f(x):
    """x以下の積の組み合わせを数える(k番目が負の場合)"""
    count = 0
    pos_idx = None
    neg_idx = len(neg) - 1
    for idx, p in enumerate(reversed(pos)):
        if p * neg[neg_idx] <= x:
            pos_idx = len(pos) - idx - 1
        else:
            break
    # pos_idxに最大の負の値x正の値 <= xを満たす最小の正値のindexが入っている
    if pos_idx is not None:
        count += len(pos) - pos_idx
    else:
        pos_idx = 0
    while neg_idx > 0:
        neg_idx -= 1
        ans = None
        for i in reversed(range(pos_idx + 1)):
            if pos[i] * neg[neg_idx] <= x:
                ans = i
                break
        if ans is None:
            break
        # iにはneg_idxの位置の負数と掛けたときに<=xを満たす最小の正数のindexが入る
        # print(i)
        count += len(pos) - ans
        pos_idx = i
    return count

def g(x):
    """x以下の積の組み合わせを数える(k番目が正の場合)"""
    count = neg_count + zero_count
    # print('c1', count)
    l_idx = 0
    r_idx = 0
    # 正数 x 正数の場合
    for idx, p in enumerate(reversed(pos)):
        if p * pos[l_idx] <= x:
            r_idx = len(pos) - idx - 1
            break
    if r_idx > 0:
        count += (r_idx + 1) - 1  # index = 0の分は引く
        while r_idx - l_idx > 0:
            l_idx += 1
            ans = l_idx
            # print(l_idx, r_idx)
            for i in reversed(range(l_idx + 1, r_idx + 1)):
                # print(i, pos[i], l_idx, pos[l_idx])
                if pos[i] * pos[l_idx] <= x:
                    ans = i
                    break
            # print('ans', ans, l_idx)
            if ans > l_idx:
                count += ans - l_idx
                r_idx = ans
            else:
                break
    # print('c2', count)
    # 負数 x 負数の場合
    r_idx = len(neg) - 1
    l_idx = len(neg) - 1
    for idx, n in enumerate(neg):
        if n * neg[r_idx] <= x:
            l_idx = idx
            break
    # print(l_idx, r_idx)
    if l_idx < r_idx:
        count += len(neg) - l_idx - 1 # r_idxの分は引く
        # print('c3', count)
        while r_idx - l_idx > 0:
                r_idx -= 1
                ans = r_idx
                # print(l_idx, r_idx)
                for i in range(l_idx, r_idx):
                    # print(i, pos[i], l_idx, pos[l_idx])
                    if neg[i] * neg[r_idx] <= x:
                        ans = i
                        break
                # print(l_idx, r_idx, ans)
                # print('ans', ans, l_idx)
                if ans < r_idx:
                    count += r_idx - ans
                    l_idx = ans
                else:
                    break
    return count


def h(x):
    return f(x) if K <= neg_count else g(x)

# print(f(0)) # => 4になってほしい(01.inの場合)
# print(f(-6)) # => 4になってほしい(01.inの場合)
# print(f(-7)) # => 2になってほしい(01.inの場合)
# print(f(-12)) # => 2になってほしい(01.inの場合)
# print(f(-13)) # => 0になってほしい(01.inの場合)

# print(h(10)) # => 10になってほしい(04.inの場合)
# print(h(14)) # => 11になってほしい(04.inの場合)
# print(h(23)) # => 12になってほしい(04.inの場合)
# print(h(72)) # => 15になってほしい(04.inの場合)
# print(h(39)) # => 13になってほしい(04.inの場合)

# print(h(11)) # => 7になってほしい(05.inの場合)
# print(h(5)) # => 5になってほしい(05.inの場合)
# print(h(80)) # => 10になってほしい(05.inの場合)
# print(h(100)) # => 10になってほしい(05.inの場合)

l = -1 * 10 ** 18
r = 10 ** 18
if K <= neg_count:
    r = -1
    h = f
else:
    l = 1
    h = g

while r - l > 1:
    mid = (l + r) // 2
    count = h(mid)
    # print(mid, count)
    if count >= K:
        r = mid
    else:
        l = mid
print(r)