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: Runtime Error

Solution code:
import numpy as np


def main():
    N, K = list(map(int, input().split(' ')))
    A = np.array(map(int, input().split(' ')))
    A.sort()
    pos_A = A[A > 0]
    zero_A = A[A == 0]
    neg_A = A[A < 0]

    def check(x):
        # Return True if more than K pairs exist whose products are not more than x.
        cnt = 0
        cnt += (np.searchsorted(A, x // pos_A, side='right')).sum()
        if x >= 0:
            cnt += len(zero_A) * N
        cnt += (N - np.searchsorted(A, (-x-1) // neg_A, side='right')).sum()
        cnt -= np.count_nonzero(A * A <= x)
        cnt //= 2
        return cnt >= K

    # binary search
    ok = 10**10
    ng = - ok
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-02-16abc-155#toc3
# https://atcoder.jp/contests/abc155/submissions/10152895
# 写経


# 条件を満たす要素を抽出
# ndarray[条件式]

def binary_search(*, ok, ng, func):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    import sys
    import numpy as np

    inf = 10 ** 18 + 1
    input = sys.stdin.readline

    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)

    A.sort()

    zero = A[A == 0]
    pos = A[A > 0]
    neg = A[A < 0]

    def count(x):
        """
        定数cに対して Ai*Aj<=c となる(i,j)の数え上げ
        順序制約 i<j -> 順序制約のない(i,j)からi==jの場合の個数を引いて2で割る
        iを固定して a=Ai とする
        a=0
            ax=0(<=c?),解なしまたは任意のx
        a>0
            ax<=c
            <-> x<=c/a
            <-> x<=c//a
        a<0
            ax<=c
            <-> (-a)x>=(-c)

            否定をとり,aの対候補全体=Nから引く

            (-a)x<(-c)
            <-> (-a)x<=(-c-1)
            <-> x<=(-c-1)//(-a)
        """
        cnt = 0
        cnt += zero.size * N  # (a:=0)*v<=x
        cnt += np.searchsorted(a=A, v=x // pos, side='right').sum()  # (a:>0)*v<=x
        cnt += (N - np.searchsorted(a=A, v=(-x - 1) // (-neg), side='right')).sum()  # (a:<0)*v<=x
        cnt -= ((A * A) <= x).sum()  # i==j
        assert cnt % 2 == 0
        return cnt // 2

    ans = binary_search(
        ng=-inf,
        ok=inf,
        func=lambda x: count(x) >= K
    )

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
Pos = []
Neg = []
m, z, p = 0, 0, 0
for i in range(N):
  if A[i] < 0:
    m += 1
    Neg.append(-A[i])
  elif A[i] == 0:
    z += 1
  elif A[i] > 0:
    p += 1
    Pos.append(A[i])
Neg.sort()
mm, zz, pp = p*m, z*(N-z)+(z*(z-1))//2, (p*(p-1)+m*(m-1))//2
if K <= mm:
  cnt = 1
  L, R = 0, -(A[0] * A[-1]) + 1
  D = (L + R) // 2
  tmp = R
  while tmp != 0:
    cnt += 1
    tmp //= 2
  ccnt = 1
  tmp1 = p
  while tmp1 != 0:
    ccnt += 1
    tmp1 //= 2
  for i in range(cnt+1):
    pnt = 0
    for j in range(m):
      # search #{x|-A[j] * A[x] >= D, m+z <= x < N}
      l, r = m + z, N
      d = (l + r) // 2
      if A[l] * (-A[j]) >= D:
        pnt += r - l
      elif A[N-1] * (-A[j]) < D:
        pnt += 0
      else:
        for k in range(ccnt+2):
          if A[d] * (-A[j]) < D:
            l = d
            d = (l + r) // 2
          else:
            r = d
            d = (l + r) // 2
        pnt += N - d - 1
    if pnt >= K:
      L = D
      D = (L + R) // 2
    else:
      R = D
      D = (L + R) // 2
  print(-D)
elif mm < K <= mm + zz:
  print(0)
else:
  cnt = 1
  if m == 1:
    L, R = 0, Pos[-1] * Pos[-2] + 1
  elif p == 1:
    L, R = 0, Neg[-1] * Neg[-2] + 1
  else:
    L, R = 0, max(Pos[-1] * Pos[-2], Neg[-1] * Neg[-2]) + 1
  D = (L + R) // 2
  tmp = R
  while tmp != 0:
    cnt += 1
    tmp //= 2
  ccnt = 1
  tmp1 = m*(m-1)//2
  while tmp1 != 0:
    ccnt += 1
    tmp1 //= 2
  cccnt = 1
  tmp2 = p*(p-1)//2
  while tmp2 != 0:
    cccnt += 1
    tmp2 //= 2
  for i in range(cnt+1):
    pnt = 0
    for j in range(m-1):
      l, r = j+1, m
      d = (l + r) // 2
      if Neg[j] * Neg[j+1] > D:
        pnt += 0
      elif Neg[j] * Neg[m-1] <= D:
        pnt += m - j - 1
      else:
        for k in range(ccnt+1):
          if Neg[d] * Neg[j] <= D:
            l = d
            d = (l + r) // 2
          else:
            r = d
            d = (l + r) // 2
        pnt += d - j
    for j in range(p-1):
      l, r = j + 1, p
      d = (l + r) // 2
      if Pos[j] * Pos[j+1] > D:
        pnt += 0
      elif Pos[j] * Pos[p-1] <= D:
        pnt += p - j - 1
      else:
        for k in range(cccnt+1):
          if Pos[d] * Pos[j] <= D:
            l = d
            d = (l + r) // 2
          else:
            r = d
            d = (l + r) // 2
        pnt += d - j
    if pnt < K - mm - zz:
      L = D + 1
      D = (L + R) // 2
    else:
      R = D
      D = (L + R) // 2
  print(D)

Submission status: Runtime Error

Solution code:
def kake(a,i,j,wk):
    if j<i+1:
        return 0
    wk.append(a[i]*a[j])
#    print(wk)
    kake(a,i,j-1,wk)
    return wk

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

seki=[]

for i in range(n-1):
    j=n-1
    wk =[]
    seki += (kake(a,i,j,wk))

seki.sort()

print(seki[k-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations as com
n, k = map(int, input().split())
a = list(map(int, input().split()))
e = []
for i, j in com(a, 2):
    e.append(i*j)
e.sort()
e = list(set(e))
print(e[k-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

def solve_m(S, T, K):
    def count(x):
        ret, ti = 0, 0
        for s in S:
            # 積がxを初めて下回るtiを求める。なければlen(T)
            while ti < len(T) and s * T[ti] > x:
                ti += 1
            if ti == len(T):
                break
            ret += len(T) - ti
        return ret
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid) < K:
            left = mid
        else:
            right = mid
    return right

def solve(S, mS, K):
    def count(x, T):
        ret, j = 0, len(T) - 1
        for i, t in enumerate(T):
            while j >= 0 and t * T[j] > x:
                j -= 1
            if j == -1:
                break
            ret += j + 1 - (1 if i <= j else 0)
        return ret // 2
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid, S) + count(mid, mS) < K:
            left = mid
        else:
            right = mid
    return right

def main():
    from itertools import groupby
    N, K = list(map(int, input().split()))
    A = sorted(map(int, input().split()), reverse=True)
    B = {k:list(g) for k, g in groupby(A, lambda x: 0 if x==0 else x // abs(x))}
    m = len(B[-1]) * len(B[1]) if -1 in B and 1 in B else 0
    z = len(B[0]) * (N-len(B[0])) + len(B[0]) * (len(B[0])-1) // 2 if 0 in B else 0
    if K <= m:
        print(solve_m(B[1], B[-1], K))
    elif K <= m + z:
        print(0)
    else:
        print(solve(sorted(B[1]), B[-1], K - m - z))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

def solve_m(S, T, K):
    def count(x):
        ret, ti = 0, 0
        for s in S:
            # 積がxを初めて下回るtiを求める。なければlen(T)
            while ti < len(T) and s * T[ti] > x:
                ti += 1
            if ti == len(T):
                break
            ret += len(T) - ti
        return ret
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid) < K:
            left = mid
        else:
            right = mid
    return right

def solve(S, mS, K):
    def count(x, T):
        ret, j = 0, len(T) - 1
        for i, t in enumerate(T):
            while j >= 0 and t * T[j] > x:
                j -= 1
            if j == -1:
                break
            ret += j + 1 - (1 if i <= j else 0)
        return ret // 2
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid, S) + count(mid, mS) < K:
            left = mid
        else:
            right = mid
    return right

def main():
    from itertools import groupby
    N, K = list(map(int, input().split()))
    A = sorted(map(int, input().split()), reverse=True)
    B = {k:list(g) for k, g in groupby(A, lambda x: 0 if x==0 else x // abs(x))}
    m = len(B[-1]) * len(B[1]) if -1 in B else 0
    z = len(B[0]) * (N-len(B[0])) + len(B[0]) * (len(B[0])-1) // 2 if 0 in B else 0
    if K <= m:
        print(solve_m(B[1], B[-1], K))
    elif K <= m + z:
        print(0)
    else:
        print(solve(sorted(B[1]), B[-1], K - m - z))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

def solve_m(S, T, K):
    def count(x):
        ret, ti = 0, 0
        for s in S:
            # 積がxを初めて下回るtiを求める。なければlen(T)
            while ti < len(T) and s * T[ti] > x:
                ti += 1
            if ti == len(T):
                break
            ret += len(T) - ti
        return ret
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid) < K:
            left = mid
        else:
            right = mid
    return right

def solve(S, mS, K):
    def count(x, T):
        ret, j = 0, len(T) - 1
        for i, t in enumerate(T):
            while j >= 0 and t * T[j] > x:
                j -= 1
            if j == -1:
                break
            ret += j + 1 - (1 if i <= j else 0)
        return ret // 2
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid, S) + count(mid, mS) < K:
            left = mid
        else:
            right = mid
    return right

def main():
    from itertools import groupby
    N, K = list(map(int, input().split()))
    A = sorted(map(int, input().split()), reverse=True)
    B = {k:list(g) for k, g in groupby(A, lambda x: 0 if x==0 else x // abs(x))}
    m = len(B[-1]) * len(B[1])
    z = len(B[0]) * (N-len(B[0])) + len(B[0]) * (len(B[0])-1) // 2 if 0 in B else 0
    if K <= m:
        print(solve_m(B[1], B[-1], K))
    elif K <= m + z:
        print(0)
    else:
        print(solve(sorted(B[1]), B[-1], K - m - z))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

def solve_m(S, T, K):
    def count(x):
        ret, ti = 0, 0
        for s in S:
            # 積がxを初めて下回るtiを求める。なければlen(T)
            while ti < len(T) and s * T[ti] > x:
                ti += 1
            if ti == len(T):
                break
            ret += len(T) - ti
        return ret
    left, right = -(10**9), 10**9+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid) < K:
            left = mid
        else:
            right = mid
    return right

def solve(S, mS, K):
    def count(x, T):
        ret, j = 0, len(T) - 1
        for i, t in enumerate(T):
            while j >= 0 and t * T[j] > x:
                j -= 1
            if j == -1:
                break
            ret += j + 1 - (1 if i <= j else 0)
        return ret // 2
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid, S) + count(mid, mS) < K:
            left = mid
        else:
            right = mid
    return right

def main():
    from itertools import groupby
    N, K = list(map(int, input().split()))
    A = sorted(map(int, input().split()), reverse=True)
    B = {k:list(g) for k, g in groupby(A, lambda x: 0 if x==0 else x // abs(x))}
    m = len(B[-1]) * len(B[1])
    z = len(B[0]) * (N-len(B[0])) + len(B[0]) * (len(B[0])-1) // 2 if 0 in B else 0
    if K <= m:
        print(solve_m(B[1], B[-1], K))
    elif K <= m + z:
        print(0)
    else:
        print(solve(sorted(B[1]), B[-1], K - m - z))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect
import numpy as npy
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
n0 = 0
np = 0
nn = 0
for i in a:
  if i>0:
    np += 1
  elif i == 0:
    n0 += 1
  else:
    nn += 1
kp = (np**2-np+nn**2-nn)//2
k0 = n0*(n-n0)+(n0**2-n0)//2
kn = nn*np
if kn < k <= kn+k0:
  print(0)
  exit()
nls = []
pls = []
for i in range(n):
  if a[i] < 0:
    nls.append(a[i])
  elif a[i] > 0:
    pls.append(a[i])
ln = len(nls)
lp = len(pls)
if k <= kn:
  nls = npy.array(nls,dtype=npy.int32)
  pls = npy.array(pls,dtype=npy.int32)
  l = a[0]*a[-1]-1
  r = 0
  while l+1 < r:
    m = (l+r)//2
    mls = m//nls
    tmp = npy.searchsorted(pls,mls,side="right").sum()
    if tmp > kn-k:
      l = m
    else:
      r = m
  print(l)
else:
  print(2/0)
  """
  l = 0
  r = max(a[0]**2,a[-1]**2)+1
  while l+1 < r:
    m = (l+r)//2
    tmp = 0
    for i in range(ln):
      tmp += 
"""

Submission status: Runtime Error

Solution code:
import bisect
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
n0 = 0
np = 0
nn = 0
for i in a:
  if i>0:
    np += 1
  elif i == 0:
    n0 += 1
  else:
    nn += 1
kp = (np**2-np+nn**2-nn)//2
k0 = n0*(n-n0)+(n0**2-n0)//2
kn = nn*np
if kn < k <= kn+k0:
  print(0)
  exit()
nls = []
pls = []
for i in range(n):
  if a[i] < 0:
    nls.append(a[i])
  elif a[i] > 0:
    pls.append(a[i])
ln = len(nls)
lp = len(pls)
if k <= kn:
  l = a[0]*a[-1]
  r = 0
  while l+1 < r:
    m = (l+r)//2
    tmp = 0
    for i in range(ln):
      tmp += bisect.bisect_right(pls,m//nls[i])
    if tmp >= kn-k:
      l = m
    else:
      r = m
  print(l)
else:
  print(2/0)

Submission status: Runtime Error

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

ap, am, a0 = [], [], []
for i in a:
    if i > 0:
        ap.append(i)
    elif i < 0:
        am.append(i)
    else:
        a0.append(i)
lp, lm, l0 = len(ap), len(am), len(a0)
ap.sort()
am.sort(reverse=True)

# binary search
if k <= lp * lm:
    start = max(ap) * min(am)
    stop = -1
    while start < stop:
        # i以下になるペアがnum個ある
        # 尺取法
        num = 0
        i = (start + stop) // 2
        j = 0
        flag = True
        for l in range(lm-1, -1, -1):
            while flag and am[l] * ap[j] > i:
                j += 1
                if j == lp:
                    flag = False
                    break
            num += lp - j
        if num < k:
            start = i + 1
        else:
            stop = i
    print(start)

elif k <= lp * lm + (lp + lm) * l0 + l0 * (l0 - 1) // 2:
    print(0)

else:
    k -= lp * lm + (lp + lm) * l0 + l0 * (l0 - 1) // 2
    start = 1
    stop = max([max(ap) * max(ap), min(am) * min(am)])
    while start < stop:
        # 1以上i以下になるペアがnum個ある
        # 尺取法
        num = 0
        i = (start + stop) // 2

        # 正の数
        j = 0
        flag = True
        flag2 = True
        for l in range(lp-1, -1, -1):
            while flag and ap[l] * ap[j] <= i:
                if flag2 and l <= j:
                    num -= l + 1
                    flag2 = False
                j += 1
                if j == lp:
                    flag = False
            num += j

        # 負の数
        j = 0
        flag = True
        flag2 = True
        for l in range(lm-1, -1, -1):
            while flag and am[l] * am[j] <= i:
                if flag2 and l <= j:
                    num -= l + 1
                    flag2 = False
                j += 1
                if j == lm:
                    flag = False
            num += j

        num //= 2
        if num < k:
            start = i + 1
        else:
            stop = i
    print(start)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

memo_r = {}
memo_l = {}

def check(t):
    res = 0
    tr = math.sqrt(abs(t))
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                if not memo_r[aj]:
                    memo_r[aj] = bisect_right(a, aj)
                res += memo_r[aj]
            else:
                if t % ai:
                    if not memo_r[aj]:
                        memo_r[aj] = bisect_right(a, aj)
                    res += n - memo_r[aj]
                else:
                    if not memo_l[aj]:
                        memo_l[aj] = bisect_right(a, aj)
                    res += n - memo_l[aj]
        else:
            if t >= 0:
                res += n
        if t >= 0 and abs(ai) <= tr:
            res -= 1
    return res // 2


m = max(max(a)**2, min(a)**2)
l = -m
r = m

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = [int(i) for i in input().split(' ')]
A = np.array([int(i) for i in input().split(' ')])
A.sort()

minus = A[A<0]
zero = A[A==0]
plus = A[A>0]

def f(x):
    cnt = 0
    if x>0:
        cnt += len(zero) * N
    cnt += np.searchsorted(A,x//plus,side='right').sum()
    cnt += (N - np.searchsorted(A,-(x//-minus),side='left')).sum()
    cnt -= np.count_nonzero(A*A<=x)

    assert cnt%2 == 0
    return cnt//2

left = -10**18
right = 10**18
while left + 1 < right:
    mid = (left+right) // 2
    if f(mid) >= K:
        right = mid
    else:
        left = mid

print(right)

Submission status: Runtime Error

Solution code:
def solve_negative():
    def count_less_x(x):
        ret = 0
        i = 0
        j = 0
        while i < len(negative_a):
            while j < len(positive_a) and positive_a[j] * negative_a[i] > x:
                j += 1
            ret += len(positive_a) - j
            i += 1

        return ret

    upper = -1
    lower = -1000000001*1000000001
    while upper - lower > 1:
        middle = (upper + lower) // 2
        if count_less_x(middle) >= k:
            upper = middle
        else:
            lower = middle
    return upper


def solve_positive():
    def count_less_x(x):
        ret = 0
        i = 0
        j = len(positive_a) - 1
        while i < len(positive_a):
            while j > i and positive_a[i] * positive_a[j] > x:
                j -= 1
            ret += j - i
            i += 1
            if i >= j:
                break
        i = 0
        j = len(r_negative_a) - 1
        while i < len(r_negative_a):
            while j > i and r_negative_a[i] * r_negative_a[j] > x:
                j -= 1
            ret += j - i
            i += 1
            if i >= j:
                break
        return ret
    lower = 0
    upper = 1000000001*1000000001
    while upper - lower > 1:
        middle = (upper + lower) // 2
        if count_less_x(middle) + num_mul_n + num_mul_z >= k:
            upper = middle
        else:
            lower = middle
    return upper


def solve_zero():
    return 0


def create_sign_split_a(a):
    negative = []
    positive = []
    zero = []
    for x in a:
        if x < 0:
            negative.append(x)
        elif x > 0:
            positive.append(x)
        else:
            zero.append(x)
    return negative, zero, positive


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

a.sort()

num_n = sum([(a_ < 0) for a_ in a])
num_p = sum([(a_ > 0) for a_ in a])
num_z = sum([(a_ == 0) for a_ in a])
negative_a, zero_a, positive_a = create_sign_split_a(a)
r_negative_a = negative_a.copy()
r_negative_a.reverse()

num_mul_p = num_n * (num_n - 1) // 2 + num_p * (num_p - 1) // 2
num_mul_z = num_n * num_z + num_p * num_z + num_z * (num_z - 1) // 2
num_mul_n = n * (n - 1) // 2 - num_mul_p - num_mul_z
print(num_mul_p, num_mul_z, num_mul_n)


if num_mul_n >= k:
    ans = solve_negative()
elif num_mul_n < k <= num_mul_n + num_mul_z:
    ans = solve_zero()
else:
    ans = solve_positive()
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
#尺取り法

from bisect import bisect_left, bisect_right

def main():
    N, K =  [int(i) for i in input().split()]
    A =  sorted(list(map(int, input().split())))

    nega_end = bisect_left(A, 0)
    posi_start = bisect_right(A, 0)

    posi_cnt = N - posi_start
    nega_cnt = nega_end
    zero_cnt = N - (posi_cnt + nega_cnt)

    nega_pairs_cnt = posi_cnt * nega_cnt
    zero_pairs_cnt = zero_cnt * (posi_cnt + nega_cnt) + (zero_cnt * (zero_cnt-1) // 2)

    if K <= nega_pairs_cnt:
        ok, ng = 0, -10 ** 18

        while abs(ok - ng) > 1:

            X = (ok + ng) // 2
            or_higher_cnt, r = 0, posi_start

            for l in range(nega_end):
                while (r < N) and (A[l] * A[r] > X):
                    r += 1
                or_higher_cnt += posi_cnt - (r - posi_start)

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

    elif nega_pairs_cnt < K <= nega_pairs_cnt + zero_pairs_cnt:
        print(0)
        return
    else:
        K -= (nega_pairs_cnt + zero_pairs_cnt)        
        ok, ng = 0, 10 ** 18
        while abs(ok - ng) > 1:
            X = (ok + ng) // 2
            r = N - 1
            for l in range(posi_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(nega_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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
aa = np.array(list(map(int, input().split())))

p = aa[aa > 0]
m = aa[aa < 0]
z = aa[aa == 0]
d = len(p) * len(m) + len(z) * (2*len(m) + 2*len(p) + len(z) - 1) // 2
# ans < 0
if k < len(p) * len(m):
    bb = [pi*mj for pi in p for mj in m]
    bb.sort()
    print(bb[k-1])
# ans == 0
elif k < d:
    print(0)
# ans > 0
else:
    bb = [p[i]*p[j] for i in range(len(p)) for j in range(i+1, len(p))]\
        + [m[i]*m[j] for i in range(len(m)) for j in range(i+1, len(m))]
    bb.sort()
    print(bb[k - d - 1])

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
aa = np.array(list(map(int, input().split())))
bb = [aa[i]*aa[j] for i in range(len(aa)) for j in range(i+1, len(aa))]
bb.sort()
print(bb[k])

Submission status: Runtime Error

Solution code:
import numpy as np

def count_pair(x):
    cnt = 0
    cnt += (n-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        cnt += len(A_zero)*n
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt

n, k = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < K:
        l = c
    else:
        r = c
print(l)

Submission status: Runtime Error

Solution code:
n = [int(_) for _ in list(input())]
a, b = 0, 1
for i in n:
    a, b = min(a+i, b+10-i), min(a+(i+1), b+10-(i+1))
print(a)

Submission status: Runtime Error

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

# inputを正負で分割
p = []
ne = []
z = 0
for v in a:
    if v > 0:
        p.append(v)
    elif v == 0:
        z += 1
    else:
        ne.append(v)
l_p = len(p)
l_n = len(ne)

num_negative = l_p * l_n
if z != 0:
    num_zero = int((l_p + l_n) * z + z * (z-1) / 2)
else:
    num_zero = 0

if l_p > 0 and l_n > 0:
    num_positive = int(l_p * (l_p-1) / 2 + l_n * (l_n-1) / 2)
    tmp = []
    if k <= num_negative:
        for i in p:
            for j in ne:
                tmp.append(i*j)
        ans = sorted(tmp)[k-1]
    elif num_negative < k <= num_negative + num_zero:
        ans = 0
    else:
        index = k - num_negative - num_zero - 1
        for i in range(l_p):
            for j in range(i+1, l_p):
                tmp.append(p[i]*p[j])
        for i in range(l_n):
            for j in range(i+1, l_n):
                tmp.append(ne[i]*ne[j])
        ans = sorted(tmp)[index]
        
# positive only
elif l_p > 0 and l_n == 0:
    if k <= num_zero:
        ans = 0
    else:
        p = sorted(p)
        index_tmp = k - num_zero
        i = 1
        while index_tmp > 0:
            if index_tmp > (l_p - i):
                index_tmp = index_tmp - (l_p - i)
                i += 1
            else:
                ans = p[i-1] * p[i-1 + index_tmp]
                break

elif l_p == 0 and l_n > 0:
    if k <= num_zero:
        ans = 0
    else:
        ne = sorted([-1*v for v in ne])
        # n = list(np.sort(np.array(n) * -1))
        index_tmp = k - num_zero
        i = 1
        while index_tmp > 0:
            if index_tmp > (l_n - i):
                index_tmp = index_tmp - (l_n - i)
                i += 1
            else:
                ans = ne[i-1] * ne[i-1 + index_tmp]
                break


print(ans)

Submission status: Runtime Error

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

# inputを正負で分割
p = []
ne = []
z = 0
for v in a:
    if v > 0:
        p.append(v)
    elif v == 0:
        z += 1
    else:
        n.append(v)
l_p = len(p)
l_n = len(ne)

num_negative = l_p * l_n
if z != 0:
    num_zero = int((l_p + l_n) * z + z * (z-1) / 2)
else:
    num_zero = 0

if l_p > 0 and l_n > 0:
    num_positive = int(l_p * (l_p-1) / 2 + l_n * (l_n-1) / 2)
    tmp = []
    if k <= num_negative:
        for i in p:
            for j in ne:
                tmp.append(i*j)
        ans = sorted(tmp)[k-1]
    elif num_negative < k <= num_negative + num_zero:
        ans = 0
    else:
        index = k - num_negative - num_zero - 1
        for i in range(l_p):
            for j in range(i+1, l_p):
                tmp.append(p[i]*p[j])
        for i in range(l_n):
            for j in range(i+1, l_n):
                tmp.append(ne[i]*ne[j])
        ans = sorted(tmp)[index]
        
# positive only
elif l_p > 0 and l_n == 0:
    if k <= num_zero:
        ans = 0
    else:
        p = sorted(p)
        index_tmp = k - num_zero
        i = 1
        while index_tmp > 0:
            if index_tmp > (l_p - i):
                index_tmp = index_tmp - (l_p - i)
                i += 1
            else:
                ans = p[i-1] * p[i-1 + index_tmp]
                break

elif l_p == 0 and l_n > 0:
    if k <= num_zero:
        ans = 0
    else:
        ne = sorted([-1*v for v in ne])
        # n = list(np.sort(np.array(n) * -1))
        index_tmp = k - num_zero
        i = 1
        while index_tmp > 0:
            if index_tmp > (l_n - i):
                index_tmp = index_tmp - (l_n - i)
                i += 1
            else:
                ans = ne[i-1] * ne[i-1 + index_tmp]
                break


print(ans)

Submission status: Runtime Error

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

# inputを正負で分割
p = []
n = []
z = 0
for v in a:
    if v > 0:
        p.append(v)
    elif v == 0:
        z += 1
    else:
        n.append(v)
l_p = len(p)
l_n = len(n)

num_negative = l_p * l_n
if z != 0:
    num_zero = int((l_p + l_n) * z + z * (z-1) / 2)
else:
    num_zero = 0

if l_p > 0 and l_n > 0:
    num_positive = int(l_p * (l_p-1) / 2 + l_n * (l_n-1) / 2)
    tmp = []
    if k <= num_negative:
        for i in p:
            for j in n:
                tmp.append(i*j)
        ans = sorted(tmp)[k-1]
    elif num_negative < k <= num_negative + num_zero:
        ans = 0
    else:
        index = k - num_negative - num_zero - 1
        for i in range(l_p):
            for j in range(i+1, l_p):
                tmp.append(p[i]*p[j])
        for i in range(l_n):
            for j in range(i+1, l_n):
                tmp.append(n[i]*n[j])
        ans = sorted(tmp)[index]
        
# positive only
elif l_p > 0 and l_n == 0:
    if k <= num_zero:
        ans = 0
    else:
        p = sorted(p)
        index_tmp = k - num_zero
        i = 1
        while index_tmp > 0:
            if index_tmp > (l_p - i):
                index_tmp = index_tmp - (l_p - i)
                i += 1
            else:
                ans = p[i-1] * p[i-1 + index_tmp]
                break

elif l_p == 0 and l_n > 0:
    if k <= num_zero:
        ans = 0
    else:
        n = sorted([-1*v for v in n])
        # n = list(np.sort(np.array(n) * -1))
        index_tmp = k - num_zero
        i = 1
        while index_tmp > 0:
            if index_tmp > (l_n - i):
                index_tmp = index_tmp - (l_n - i)
                i += 1
            else:
                ans = n[i-1] * n[i-1 + index_tmp]
                break


print(ans)