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 sys
from itertools import count

def f(plus, minus, zero, val):
    t = 0
    if val > 0:
        t += len(plus) * len(minus) + zero * (len(plus) + len(minus)) + zero * (zero - 1) // 2
        # print(f'    zero {len(plus) * len(minus) + zero * (len(plus) + len(minus)) + zero * (zero - 1) // 2=}')
        if len(plus) >= 2:
            right_index = len(plus) -1
            for left_index, left in enumerate(plus):
                while left_index < right_index and left * plus[right_index] > val:
                    right_index -= 1
                t += max(0, right_index - left_index)
                # print(f'    plus {right_index-left_index=}')
        if len(minus) >= 2:
            left_index = 0
            for right_index, right in zip(count(len(minus) - 1, -1), reversed(minus)):
                while left_index < right_index and minus[left_index] * right > val:
                    left_index += 1
                t += max(0, right_index - left_index)
                # print(f'    minus {right_index-left_index=} {right_index=} {right=}')
    elif val < 0:
        if plus:
            plus_index = 0
            for m in minus:
                while plus_index < len(plus) and plus[plus_index] * m > val:
                    plus_index += 1
                t += len(plus) - plus_index
                # print(f'    mix {len(plus) - plus_index=}')
    else:
        t += len(plus) * len(minus) + zero * (len(plus) + len(minus)) + zero * (zero - 1) // 2
        # print(f'    zero {len(plus) * len(minus) + zero * (len(plus) + len(minus)) + zero * (zero - 1) // 2=}')
    # print(f'  {val=}, {t=}')
    return t


def resolve(in_):
    N, K = map(int, in_.readline().split())
    plus = []
    minus = []
    zero = 0
    for a in map(int, in_.readline().split()):
        if a > 0:
            plus.append(a)
        elif a < 0:
            minus.append(a)
        else:
            zero += 1

    plus.sort()
    minus.sort()

    ng = -(10 ** 18) - 1
    ok = 10 ** 18
    while ok - ng > 1:
        mid = (ok + ng) // 2
        # print(f'{ok=} {ng=} {mid=}')

        if f(plus, minus, zero, mid) >= K:
            ok = mid
        else:
            ng = mid

    # print(f'{ok=} {ng=} {mid=}')
    return ok


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def bis(K, A, B, t):
    # K 番目に小さい <=> x 未満の数が K 個未満であるような最大の x
    if t==1:
        ok = 0
        ng = 10**18+1
        while ok + 1 < ng:
            c = ok+ng>>1
            cnt = 0
            idx_B = len(B)-1
            for a in A:
                while idx_B >= 0 and a * B[idx_B] >= c:
                    idx_B -= 1
                cnt += idx_B + 1
            if cnt < K:
                ok = c
            else:
                ng = c
    else:
        ok = 0
        ng = 10**18+1
        while ok + 1 < ng:
            c = ok+ng>>1
            cnt = 0
            idx_A = len(A)-1
            idx_B = len(B)-1
            for a in A:
                while idx_A >= 0 and a * A[idx_A] >= c:
                    idx_A -= 1
                cnt += idx_A + 1
                if a*a < c:
                    cnt -= 1
            for b in B:
                while idx_B >= 0 and b * B[idx_B] >= c:
                    idx_B -= 1
                cnt += idx_B + 1
                if b*b < c:
                    cnt -= 1
            cnt >>= 1
            if cnt < K:
                ok = c
            else:
                ng = c
    return ok

def main():
    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    cnt_m = cnt_0 = cnt_p = 0
    for a in A:
        if a < 0:
            cnt_m += 1
        elif a == 0:
            cnt_0 += 1
        else:
            cnt_p += 1
    cnt2_m = cnt_m * cnt_p
    cnt2_0 = cnt_0 * N - cnt_0 * (cnt_0 + 1) // 2
    cnt2_p = cnt_p * (cnt_p - 1) // 2 + cnt_m * (cnt_m - 1) // 2
    assert cnt2_m + cnt2_0 + cnt2_p == N * (N - 1) // 2

    if K <= cnt2_m:
        # 絶対値が cnt2_m - K + 1 番目に小さい
        ans = -bis(cnt2_m-K+1, [-a for a in A[::-1] if a<0], [a for a in A if a>0], 1)
    elif K <= cnt2_m + cnt2_0:
        ans = 0
    else:
        ans = bis(K-cnt2_m-cnt2_0, [-a for a in A[::-1] if a<0], [a for a in A if a>0], 2)
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def f(A, val):
    t = 0
    for a in A:
        if a > 0:
            ok = -1
            ng = len(A)
            while ng - ok > 1:
                mid = (ok + ng) // 2
                if a * A[mid] <= val:
                    ok = mid
                else:
                    ng = mid
            t += ok + 1
        elif a < 0:
            ok = len(A)
            ng = -1
            while ok - ng > 1:
                mid = (ok + ng) // 2
                if a * A[mid] <= val:
                    ok = mid
                else:
                    ng = mid
            t += len(A) - ok
        else:
            if 0 <= val:
                t += len(A)

    return t


def binsearch(A, val):
    t = f(A, val)
    n = sum(1 for v in A if v * v <= val)
    # print(f'  {val=} {t=} {n=} {(t - n) // 2 =}')

    return (t - n) // 2


def resolve(in_):
    N, K = map(int, in_.readline().split())
    A = list(map(int, in_.readline().split()))
    A.sort()

    ng = -(10 ** 18) - 1
    ok = 10 ** 18
    while ok - ng > 1:
        mid = (ok + ng) // 2
        # print(f'{ok=} {ng=} {mid=}')

        if binsearch(A, mid) >= K:
            ok = mid
        else:
            ng = mid

    # print(f'{ok=} {ng=} {mid=}')
    return ok


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, K = map(int, input().split())
A = sorted(map(int, input().split()))
ok = -10**20  # There are <= K pairs <= ok
ng = 10**20   
# x, count

while ok + 1 < ng:
  x = (ok + ng) //2
  count = 0
  for i, a in enumerate(A):
    if a > 0:
      j = bisect.bisect_right(A, x // a)
      if i < j:
        count += j - 1
      else:
        count += j
    elif a < 0:
      j = bisect.bisect_left(A, - (-x // a))
      #print(x, a, -(-x//a), j)
      if i >= j:
        count += N - j - 1
      else:
        count += N - j
    else: # a == 0
      if x >= 0:
        count += N-1
    #print(x, a, count)
  count //= 2
  #print(x, count)
  if count < K:
    ok = x
  else:
    ng = x
  
  
print(ng)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, K = map(int, input().split())
A = sorted(map(int, input().split()))
ok = -10**20  # There are <= K pairs <= ok
ng = 10**20   
# x, count

while ok + 1 < ng:
  x = (ok + ng) //2
  count = 0
  for i, a in enumerate(A):
    if a > 0:
      j = bisect.bisect_right(A, x // a)
      if i < j:
        count += j - 1
      else:
        count += j
    elif a < 0:
      j = bisect.bisect_left(A, - (-x // a))
      #print(x, a, -(-x//a), j)
      if i >= j:
        count += N - j - 1
      else:
        count += N - j
    else: # a == 0
      if x >= 0:
        count += N-1
    #print(x, a, count)
  count //= 2
  #print(x, count)
  if count < K:
    ok = x
  else:
    ng = x
  
  
print(ng)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,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:
def abc155_d():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    from bisect import bisect_left, bisect_right
    lower = -10**18
    upper = 10**18
    while upper - lower > 1:
        x = (upper + lower) // 2
        cnt = 0
        for i in range(n-1):
            a = A[i]
            if a < 0:
                idx = bisect_left(A, (x+a+1)//a)
                cnt += n - max(idx, i+1)
            elif a > 0:
                idx = bisect_right(A, x//a)
                cnt += max(0, idx - i - 1)
            else:  # a == 0
                if x >= 0:
                    cnt += n - i - 1
            if cnt >= k: break
        if cnt >= k: upper = x
        else: lower = x
    print(upper)

if __name__ == '__main__':
    abc155_d()

Submission status: Time Limit Exceeded

Solution code:
a,b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
from itertools import combinations
p=list(combinations(c,2))
l=[]
# print(p)
for i in range(0,len(p)):
    l.append(p[i][0]*p[i][1])
l=sorted(l)
# print(l)
print(l[b-1])

Submission status: Time Limit Exceeded

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

numlist = list(numarr)
multipleList = []
firstindex = 0
for i in range(len(numlist)):
    firstindex += 1
    for j in range(firstindex, len(numlist)):
        multipleList.append(numlist[i] * numlist[j])

sortList = sorted(multipleList)
print(sortList[k-1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=sorted(map(int,input().split()))
b=[i for i in a if i<0]
c=[i for i in a if i>=0]
result=[]
for i in b:
  for j in c:
    result.append(i*j)
for i in range(len(b)):
  for j in range(i+1,len(b)):
    result.append(b[i]*b[j])
for i in range(len(c)):
  for j in range(i+1,len(c)):
    result.append(c[i]*c[j])
print(sorted(result)[k-1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0

# 負数の数(nc)、0の数(zc)、正数の数(pc)を数える
for i in range(n):
 if arr[i]<0:
   nc+=1
 elif arr[i]==0:
   zc+=1
 else:
   pc+=1

# 積が負となるペアの個数を求める
ncc=nc*pc
# 積が0となるペアの個数を求める
zcc=zc*(nc+pc)+(zc*(zc-1))//2
# 積が正となるペアの個数を求める
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2

# K番目の値が負の場合
if k <= ncc:
 arr1=[]
 arr2=[]
 # 負数、正数をそれぞれ昇順に並べる
 for i in range(n):
   if arr[i] < 0:
     arr1.append(-arr[i])
   elif arr[i] > 0:
     arr2.append(arr[i])
 arr1=arr1[::-1]
 c1=len(arr1)
 c2=len(arr2)
 l = 0         # left
 r = 10**18+1  # right 答えでもある
 # 負数のマイナスを取って計算しているため積の大小が逆転するので、大きなほうからK番目
 # 小さなほうから(積が負となるペアの個数-K)番目の値を求める
 k = ncc-k
 while r-l != 1: # rとlが1違い、すなわちrが答えとなるまで繰り返す
   mid=(l+r)//2 # 区間の中間値を更新
   cnt=0
   pos=c2-1
   # 区間[left, right)でのしゃくとり法
   # 各負数ごとに積が勝手に決めた値midよりも小さくなる正数の個数を求め足し合わせる
   for i in range(c1):
     while pos!=-1:
       if arr2[pos] > mid//arr1[i]:
         pos-=1
       else:
         break        
     cnt+=pos+1
   # 勝手に決めた値mid以下の個数が(積が負となるペアの個数-K)個以上であれば真の値はmid以下
   if cnt > k:
     r = mid  # rightをmidに更新してやり直し
   # そうでなければ真の値はmid以上
   else:
     l = mid  # leftをmidに更新してカウントやり直し
 # 負数のマイナスを取って計算したので最後にマイナスを付けて出力する
 print(-r)

# K番目の値が0の場合
elif k <= (ncc+zcc):
 print(0)

# K番目の値が正の場合
else:
 arr1=[]
 arr2=[]
 for i in range(n): #負数、正数をそれぞれ昇順に並べる
   if arr[i] < 0:
     arr1.append(-arr[i])
   elif arr[i] > 0:
     arr2.append(arr[i])
 arr1=arr1[::-1]
 c1=len(arr1)
 c2=len(arr2)
 l=0
 r=10**18+1
 k -= (ncc+zcc) #正数の中で小さい順にK番目の数を調べたいので負数、0の数を取り除く
 while r-l != 1:
   mid=(l+r)//2
   cnt1=0
   pos1=c1-1
   # 各負数ごとに積が勝手に決めた値midよりも小さくなる負数の個数を求め足し合わせる(しゃくとり法)
   for i in range(c1):
     tmp=0
     while pos1 != -1:
       if arr1[pos1] > mid//arr1[i]:
         pos1-=1
       else:
         break
     tmp+=pos1+1
     # 各要素について、自身を2回選んだ場合の積が勝手に決めた値mid以下なら条件を満たすペアの個数を1減らす
     if arr1[i]**2 < mid:
       tmp-=1
     cnt1+=tmp
   cnt1 = cnt1//2 #上記の処理では同じペアが2回数えられているので個数を半分にする
   cnt2=0
   pos2=c2-1
   # 各正数ごとに積が勝手に決めた値midよりも小さくなる正数の個数を求め足し合わせる(しゃくとり法)
   for i in range(c2):
     tmp=0
     while pos2!=-1:
       if arr2[pos2] > mid//arr2[i]:
         pos2-=1
       else:
         break
     tmp+=pos2+1
     if arr2[i]**2 < mid:
       tmp-=1 #各要素について、自身を2回選んだ場合の積が勝手に決めた値mid以下なら条件を満たすペアの個数を1減らす
     cnt2+=tmp
   cnt2=cnt2//2 #上記の処理では同じペアが2回数えられているので個数を半分にする
   cnt=cnt1+cnt2
   if cnt >= k: #勝手に決めた値mid以下の個数がK個以上であれば真の値はmid以下
     r = mid
   else: #そうでなければ真の値はmid以上
     l = mid
 print(r)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[]
C=[]
for ai in range(len(A)):
    if A[ai]<0:
        B.append(A[ai])
    else:
        C.append(A[ai])
s=len(B)*len(C)
if K<=s:
    D=[]
    for bi in range(len(B)):
        for ci in range(len(C)):
            D.append(B[bi]*C[ci])
    D.sort()
    print(D[K-1])
else:
    E=[]
    for bi in range(len(B)):
        for bj in range(bi+1,len(B)):
            E.append(B[bi]*B[bj])
    for ci in range(len(C)):
        for cj in range(ci+1,len(C)):
            E.append(C[ci]*C[cj])
    E.sort()
    print(E[K-s-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l = sys.maxsize * (-1)
r = sys.maxsize

while l+1 < r:
  x = (l+r)//2
  def isOk():
    tot = 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] < x):
            r = c
          else:
            l = c
        tot += n-r
      else:
        l = -1
        r = n
        while (l+1<r):
          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
  if (isOk()):
    l = x
  else:
    r = x;
print(l)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def find_x_miman(pos, i, neg, x):
    if len(neg) == 0:
        return 0
    if neg[0] * pos[i] >= x:
        return 0
    ok = 0
    ng = len(neg)
    while ok + 1 < ng:
        m = (ng + ok) // 2
        if neg[m] * pos[i] < x:
            ok = m
        else:
            ng = m
    return ok + 1

def find_x_miman_from_right(arr, i, x):
    if not (i + 1  < len(arr)):
        return 0
    if arr[i] * arr[i+1] >= x:
        return 0

    ok = i + 1
    ng = len(arr)
    while ok + 1 < ng:
        m = (ng + ok) // 2
        if arr[m] * arr[i] < x:
            ok = m
        else:
            ng = m
    return ok - i

def main():
    N, K = LI()
    A = LI()
    A = sorted(A)
    pos = [a for a in A if a > 0]
    neg = [a for a in A if a < 0]
    rev_neg = sorted([abs(a) for a in neg])
    n_zero = N - len(neg) - len(pos)
    l = -10**18 - 1 # K未満
    r = 10**18 + 1

    def count_miman(A, x):
        # return count of mul less than x
        cnt = 0
        if x < 0:
            for i in range(len(pos)):
                cnt += find_x_miman(pos, i, neg, x)
        else: # x > 0
            if x > 0:
                cnt += n_zero * (len(neg) + len(pos)) + (n_zero * (n_zero - 1)) // 2
            for i in range(len(pos)):
                cnt += find_x_miman_from_right(pos, i, x)
            for i in range(len(rev_neg)):
                cnt += find_x_miman_from_right(rev_neg, i, x)
            cnt += len(pos) * len(neg)
        return cnt

    # x未満がK個未満あるような最大のx
    while l + 1 < r:
        m = (l + r) // 2
        mimcount = count_miman(A, m)
        if mimcount < K:
            l = m
        else:
            r = m
    print(l)

main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def find_x_miman(pos, i, neg, x):
    if len(neg) == 0:
        return 0
    if neg[0] * pos[i] >= x:
        return 0
    ok = 0
    ng = len(neg)
    while ok + 1 < ng:
        m = (ng + ok) // 2
        if neg[m] * pos[i] < x:
            ok = m
        else:
            ng = m
    return ok + 1

def find_x_miman_from_right(arr, i, x):
    if not (i + 1  < len(arr)):
        return 0
    if arr[i] * arr[i+1] >= x:
        return 0

    ok = i + 1
    ng = len(arr)
    while ok + 1 < ng:
        m = (ng + ok) // 2
        if arr[m] * arr[i] < x:
            ok = m
        else:
            ng = m
    return ok - i

def main():
    N, K = LI()
    A = LI()
    A = sorted(A)

    s = []
    for i in range(N):
        for j in range(i+1, N):
            s.append(A[i] * A[j])
    s = sorted(s)

    pos = [a for a in A if a > 0]
    neg = [a for a in A if a < 0]
    rev_neg = sorted([abs(a) for a in neg])
    n_zero = N - len(neg) - len(pos)
    l = -10**18 - 1 # K未満
    r = 10**18 + 1

    def count_miman(A, x):
        # return count of mul less than x
        cnt = 0
        if x < 0:
            for i in range(len(pos)):
                cnt += find_x_miman(pos, i, neg, x)
        else: # x > 0
            if x > 0:
                cnt += n_zero * (len(neg) + len(pos)) + (n_zero * (n_zero - 1)) // 2
            for i in range(len(pos)):
                cnt += find_x_miman_from_right(pos, i, x)
            for i in range(len(rev_neg)):
                cnt += find_x_miman_from_right(rev_neg, i, x)
            cnt += len(pos) * len(neg)
        return cnt

    # x未満がK個未満あるような最大のx
    while l + 1 < r:
        m = (l + r) // 2
        mimcount = count_miman(A, m)
        if mimcount < K:
            l = m
        else:
            r = m
    print(l)

main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = As[0] * As[-1] - 1
    r = 10000000
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = -10000000
    r = max(As[-1] * As[-2], As[0] * As[1])
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
        if count >= K:
            r = mid
            break
    else:
        l = mid

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = As[0] * As[-1] - 1
    r = 100
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = -100
    r = max(As[-1] * As[-2], As[0] * As[1])
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
        if count >= K:
            r = mid
            break
    else:
        l = mid

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = As[0] * As[-1] - 1
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = 0
    r = max(As[-1] * As[-2], As[0] * As[1])
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
        if count >= K:
            r = mid
            break
    else:
        l = mid

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while r - l > 1:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
        if count >= K:
            r = mid
            break
    else:
        l = mid

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while r - l > 1:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-t)//A), lo = i+1)
        else:
            if t >= 0:
                count += N - i - 1
    return (count < K)
        


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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -((-t)//A), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    return (count < K)
        


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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return True

l = As[0] * As[-1] - 1
r = max(As[-1] * As[-2], As[0] * As[1]) + 1

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return (count < K)

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = As[0] * As[-1] - 1
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = 0
    r = max(As[-1] * As[-2], As[0] * As[1])
else:
    print(0)
    exit()

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return True

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 10 ** 9
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = -(10 ** 9)
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return True

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 10 ** 18 + 10
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = - (10 ** 18 + 10)
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return True

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 10
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = -10
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return True

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = 0
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

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

print(r)