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: Time Limit Exceeded

Solution code:
import bisect
import sys

input = sys.stdin.readline

def is_ok_minus(x):
    cnt = 0
    for i in range(len(mA)):
        for j in range(len(pA)):
            if mA[i]*pA[-(j+1)] <= x:
                cnt += 1
            else:
                break
    if cnt >= k:
        return True
    return False

def meguru_bisect_minus(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok_minus(mid):
            ok = mid
        else:
            ng = mid
    return ok
    
def is_ok_plus(x):
    cnt = minus*plus + zeros*(minus+plus) + zeros*(zeros-1)//2
    for i in range(len(mA)):
        for j in range(i+1,len(mA)):
            if mA[-(i+1)]*mA[-(j+1)] <= x:
                cnt += 1
            else:
                break
    
    for i in range(len(pA)):
        for j in range(i+1,len(pA)):
            if pA[i]*pA[j] <= x:
                cnt += 1
            else:
                break
    
    if cnt >= k:
        return True
    return False

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

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

A.sort()

minus = bisect.bisect_right(A, -1)
zeros = bisect.bisect_right(A, 0) - minus
plus = n - (minus+zeros)

mA = A[:minus]
zA = A[minus:minus+zeros]
pA = A[minus+zeros:]

minus_pair = minus*plus
zero_pair = zeros*(n-zeros) + zeros*(zeros-1)//2
plus_pair = n*(n-1)//2-(minus_pair+zero_pair)

#print("minus",minus*plus)
#print("0",zeros*(minus+plus))

if k <= minus_pair:
    print(meguru_bisect_minus(-10**18,10**18))
elif minus_pair+1 <= k <= minus_pair+zero_pair:
    print(0)
else:
    print(meguru_bisect_plus(-10**18,10**18))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def counts(x):
        tot = 0
        for i in range(N):
            if A[i] < 0:
                l, r = -1, N
                while r-l > 1:
                    c = (l+r)//2
                    if A[c]*A[i] < x:
                        r = c
                    else:
                        l = c
                tot += N - r
            else:
                l, r = -1, N
                while r-l > 1:
                    c = (l + r) // 2
                    if A[c] * A[i] < x:
                        l = c
                    else:
                        r = c
                tot += r
            if A[i] * A[i] < x:
                tot -= 1
        tot //= 2
        return tot < K
 
 
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
 
    l = -(10**18)
    r = 10**18
    while r-l > 1:
        x = (l + r) // 2
        if counts(x):
            l = x
        else:
            r = x
    print(l)
 
 
if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    def counts(x):
        tot = 0
        for i in range(N):
            if A[i] < 0:
                l, r = -1, N
                while r-l > 1:
                    c = (l+r)//2
                    if A[c]*A[i] < x:
                        r = c
                    else:
                        l = c
                tot += N - r
            else:
                l, r = -1, N
                while r-l > 1:
                    c = (l + r) // 2
                    if A[c] * A[i] < x:
                        l = c
                    else:
                        r = c
                tot += r
            if A[i] * A[i] < x:
                tot -= 1
        tot //= 2
        return tot < K


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

    l = -(10**18)
    r = 10**18
    while r-l > 1:
        x = (l + r) // 2
        if counts(x):
            l = x
        else:
            r = x
    print(l)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    A = LI()
    A = sorted(A)

    left = - 1_000_000_000_000_000_000_000
    right = 1_000_000_000_000_000_000_000
    while right - left > 1:
        x = (left + right) // 2
        ltx = dup = 0
        for a in A:
            l2 = -1
            r2 = N
            if a > 0:
                while r2 - l2 > 1:
                    m = (l2 + r2) // 2
                    if a * A[m] <= x: l2 = m
                    else: r2 = m
                ltx = ltx + l2 + 1
            elif a < 0:
                while r2 - l2 > 1:
                    m = (l2 + r2) // 2
                    if a * A[m] <= x: r2 = m
                    else: l2 = m
                ltx = ltx + N - r2
            else:
                if x >= 0: ltx = ltx + N

            # 重複
            if a * a <= x: dup += 1

        cnt = (ltx - dup) // 2
        if cnt >= K: right = x
        else: left = x
        # print(x)
    print(right)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

def main():
  n, k = map(int, input().split())
  a, b, c = 0, 0, 0
  L, R = [], []
  for p in map(int, input().split()):
    if p < 0:
      a += 1
      L.append(p)
    elif p == 0:
      b += 1
    else:
      c += 1
      R.append(p)
  L.sort()
  R.sort()
  s = a*c
  t = b*(b-1)//2 + (a+c)*b
  if s < k <= s+t:
    ans = 0
  else:
    if k <= s:
      ok = -1
      ng = -(10**18+1)
      while ok - ng > 1:
        mid = (ok+ng)//2
        now = 0
        temp = 0
        for l in L:
          while now < c and l*R[now] > mid:
            now += 1
          temp += c - now
        if temp >= k:
          ok = mid
        else:
          ng = mid
    else:
      ok = 10**18
      ng = 0
      while ok - ng > 1:
        mid = (ok+ng)//2
        now = c - 1
        temp = s+t
        for i, r in enumerate(R):
          if now <= i:
            break
          while now > i and r*R[now] > mid:
            now -= 1
          temp += now - i
        now = 0
        for i in range(a-1, -1, -1):
          l = L[i]
          if now >= i:
            break
          while now < i and l*L[now] > mid:
            now += 1
          temp += i - now
        if temp >= k:
          ok = mid
        else:
          ng = mid
    ans = ok
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

n, k = map(int, input().split())
a, b, c = 0, 0, 0
L, R = [], []
for p in map(int, input().split()):
  if p < 0:
    a += 1
    L.append(p)
  elif p == 0:
    b += 1
  else:
    c += 1
    R.append(p)
L.sort()
R.sort()
s = a*c
t = b*(b-1)//2 + (a+c)*b
if s < k <= s+t:
  ans = 0
else:
  if k <= s:
    ok = -1
    ng = -(10**18+1)
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = 0
      temp = 0
      for l in L:
        while now < c and l*R[now] > mid:
          now += 1
        temp += c - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  else:
    ok = 10**18
    ng = 0
    while ok - ng > 1:
      mid = (ok+ng)//2
      now = c - 1
      temp = s+t
      for i, r in enumerate(R):
        if now <= i:
          break
        while now > i and r*R[now] > mid:
          now -= 1
        temp += now - i
      now = 0
      for i in range(a-1, -1, -1):
        l = L[i]
        if now >= i:
          break
        while now < i and l*L[now] > mid:
          now += 1
        temp += i - now
      if temp >= k:
        ok = mid
      else:
        ng = mid
  ans = ok
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def comb(li):
    return len(li) * (len(li) - 1) // 2


def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


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

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n * (n - 1) // 2 - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()

    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg) + count_large(m, pos)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)


# k-th is 0
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit


def comb(li):
    return len(li) * (len(li) - 1) // 2


@njit
def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n * (n - 1) // 2 - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()

    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg) + count_large(m, pos)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)


# k-th is 0
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit
from numba.typed import List


def comb(li):
    return len(li) * (len(li) - 1) // 2


@njit
def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n * (n - 1) // 2 - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()
    neg2 = List()
    [neg2.append(e) for e in neg]
    pos2 = List()
    [pos2.append(e) for e in pos]


    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg2) + count_large(m, pos2)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)


# k-th is 0
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=list(itertools.combinations(a,2))
d=[c[i][0]*c[i][1] for i in range(len(c))]
d.sort()
print(d[k-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,K = map(int,readline().split())
K = 2*K
A = list(map(int,readline().split()))
A.sort()

# ペアの中のmid以下の個数
def check(mid):
    ans = 0
    for a in A:
        if a == 0:
            if mid >= 0:
                ans += N-1
        elif a > 0:
            ng2 = N
            ok2 = -1
            while ng2-ok2 > 1:
                mid2 = (ok2+ng2)//2
                if a*A[mid2] <= mid:
                    ok2 = mid2
                else:
                    ng2 = mid2
            if a**2 <= mid:
                ans += ok2
            else:
                ans += ok2+1
        else:
            ng2 = -1
            ok2 = N
            while ok2-ng2 > 1:
                mid2 = (ok2+ng2)//2
                if a * A[mid2] <= mid:
                    ok2 = mid2
                else:
                    ng2 = mid2
            if a**2 <= mid:
                ans += N-ok2-1
            else:
                ans += N-ok2
    return ans

# 二分探索
ng = -INF
ok = INF
while ok - ng > 1:
    mid = (ok + ng) // 2
    # check(mid):ペアの中のmid以下の個数
    # K個以上なら、上界をmidにする(満たす)
    if check(mid) >= K:
        ok = mid
    # K個未満なら、下界をmidにする(満たさない)
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A)
ok, ng = 10**18, -10**18

# 判定条件の実装「数列から２個選んだ積がx以下のものがK個以上ある」
def is_ok(x, A, N, K):
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    t = 0
    for i in range(N):
        if A[i] > 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        elif x >= 0:
            s += N
        if A[i] * A[i] <= x:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) // 2
    # それがK個以上あるかを判定する
    return total >= K

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
ok, ng = 10**18, -10**18

# 判定条件の実装「数列から２個選んだ積がx以下のものがK個以上ある」
def is_ok(x, A, N, K):
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    t = 0
    for i in range(N):
        if A[i] > 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        elif x >= 0:
            s += N
        if A[i] * A[i] <= x:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) // 2
    # それがK個以上あるかを判定する
    return total >= K

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく
import sys
input = sys.stdin.readline

# N, K = [int(x) for x in input().split()]
# A = [int(x) for x in input().split()]
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ok, ng = 10**18, -10**18

# 判定条件の実装「数列から２個選んだ積がx以下のものがK個以上ある」
def is_ok(x, A, N, K):
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    t = 0
    for i in range(N):
        if A[i] > 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        elif x >= 0:
            s += N
        if A[i] * A[i] <= x:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) / 2
    # それがK個以上あるかを判定する
    return total >= K

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
ok, ng = 10**18, -10**18

# 判定条件の実装「数列から２個選んだ積がx以下のものがK個以上ある」
def is_ok(x, A, N, K):
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    t = 0
    for i in range(N):
        if A[i] > 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        elif x >= 0:
            s += N
        if A[i] * A[i] <= x:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) / 2
    # それがK個以上あるかを判定する
    return total >= K

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
ok, ng = 10**18, -10**18

# 判定条件の実装「数列から２個選んだ積がx以下のものがK個以上ある」
def is_ok(x, A, N, K):
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    t = 0
    for i in range(N):
        if A[i] > 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        elif x >= 0:
            s += N
        if A[i] * A[i] <= x:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) / 2
    # それがK個以上あるかを判定する
    return total >= K

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
ok, ng = 10**18, -10**18

# 判定条件の実装「数列から２個選んだ積がx以下のものがK個以上ある」
def is_ok(x, A, N, K):
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    t = 0
    for i in range(N):
        if A[i] >= 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        if A[i] * A[i] <= x:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) / 2
    # それがK個以上あるかを判定する
    return total >= K

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
ok, ng = 10**18, -10**18

# 判定条件の実装「数列から２個選んだ積がx以下のものがK個以上ある」
def is_ok(x, A, N, K):
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    t = 0
    for i in range(N):
        if A[i] >= 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        if A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        if A[i] * A[i] <= x:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) / 2
    # それがK個以上あるかを判定する
    return total >= K

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid
print(ok)