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: Accepted

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

import numpy as np

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

nega_list=A[A<0]
posi_list=A[A>0]
zero_num=A[A==0].size

nega_list=np.sort(nega_list)
posi_list=np.sort(posi_list)

nega_cnt=nega_list.size * posi_list.size
posi_cnt=((posi_list.size * posi_list.size-1) // 2) + ((nega_list.size * nega_list.size-1) // 2)

zero_cnt=(zero_num * (zero_num-1)) // 2 + zero_num * (nega_list.size + posi_list.size)

# Kがどこに属するかを判断
if K <= nega_cnt:
  # 負の数が答え
  # かけてX以下になる組み合わせをK個以上作れればOK
  
  def isOkNega(x):
    return np.searchsorted(nega_list,x//posi_list,side="right").sum() >= K
    
  ok=0
  ng=-10**18-1
  while (ok-ng)>1:
    mid=(ok+ng)//2
    if isOkNega(mid):
      ok=mid
    else:
      ng=mid
  print(ok)
  
elif K <= nega_cnt+zero_cnt:
  # 0が答え
  print(0)
  
else:  
  # 正の数が答え
  K-=(nega_cnt+zero_cnt)
  # 正のグループ内の積、負のグループ内の積、それぞれを合わせてX以下の数をK個以上作れる
  
  # 負の数リストは、掛け合わせた絶対値が小さいものを求める必要があるため、正のリストに変更
  nega_list = np.flipud(nega_list * (-1))
  
  # 自分自身との積は除外する必要があるため、自分同士の積リストを作成
  self_nega=nega_list * nega_list
  self_posi=posi_list * posi_list
  
  def isOkPosi(x):
    # 重複を考えずに、負の数同士の積で条件を満たすものをカウント
    nega_all = np.searchsorted(nega_list, x // nega_list, side = "right")
    
    # 自分自身を掛け合わせたもので、条件を満たすものの個数はカウントから除外する必要がある
    nega_cnt = nega_all.sum() - self_nega[self_nega <= x].size
    
    # 同じペアを二回数えているため1/2する
    nega_cnt //= 2
    
    # 正の数リストで同じことをする
    posi_all = np.searchsorted(posi_list, x // posi_list, side = "right")
    posi_cnt = posi_all.sum() - self_posi[self_posi <= x].size
    posi_cnt //= 2
        
    return nega_cnt + posi_cnt >= K
  
  ok=10**18+1
  ng=0
  while abs(ok-ng)>1:
    mid=abs(ok+ng)//2
    if isOkPosi(mid):
      ok=mid
    else:
      ng=mid
  print(ok)

Submission status: Accepted

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

import numpy as np

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

nega_list=A[A<0]
posi_list=A[A>0]
zero_num=A[A==0].size

# print(nega_list)
# print(posi_list)
# print(zero_num)

nega_list=np.sort(nega_list)
posi_list=np.sort(posi_list)

nega_cnt=nega_list.size * posi_list.size
posi_cnt=((posi_list.size * posi_list.size-1) // 2) + ((nega_list.size * nega_list.size-1) // 2)

zero_cnt=(zero_num * (zero_num-1)) // 2 + zero_num * (nega_list.size + posi_list.size)

# print(nega_cnt)
# print(posi_cnt)
# print(zero_cnt)


# Kがどこに属するかを判断
if K <= nega_cnt:
  # 負の数が答え
  # かけてX以下になる組み合わせをK個以上作れればOK
  
  def isOkNega(x):
    return np.searchsorted(nega_list,x//posi_list,side="right").sum() >= K
    
  ok=0
  ng=-10**18-1
  while (ok-ng)>1:
    mid=(ok+ng)//2
    if isOkNega(mid):
      ok=mid
    else:
      ng=mid
  print(ok)
  
elif K <= nega_cnt+zero_cnt:
  # 0が答え
  print(0)
  
else:  
  # 正の数が答え
  K-=(nega_cnt+zero_cnt)
  # 正のグループ内の積、負のグループ内の積、それぞれを合わせてX以下の数をK個以上作れる
  
  # 負の数リストは、掛け合わせた絶対値が小さいものを求める必要があるため、正のリストに変更
  nega_list = np.flipud(nega_list * (-1))
  
  # 自分自身との積は除外する必要があるため、自分同士の積リストを作成
  self_nega=nega_list * nega_list
  self_posi=posi_list * posi_list
  
  def isOkPosi(x):
    # print("x",x)
    # 重複を考えずに、負の数同士の積で条件を満たすものをカウント
    nega_all = np.searchsorted(nega_list, x // nega_list, side = "right")
    # print(nega_all)
    # print("self_nega[self_nega <= x]",self_nega[self_nega <= x])
    # 自分自身を掛け合わせたもので、条件を満たすものの個数はカウントから除外する必要がある
    nega_cnt = nega_all.sum() - self_nega[self_nega <= x].size
    # print(nega_cnt)
    
    # 同じペアを二回数えているため1/2する
    nega_cnt //= 2
    
    # 正の数リストで同じことをする
    posi_all = np.searchsorted(posi_list, x // posi_list, side = "right")
    # print(posi_all)
    # print("self_posi[self_posi <= x]",self_posi[self_posi <= x])
    posi_cnt = posi_all.sum() - self_posi[self_posi <= x].size
    # print(posi_cnt)
    posi_cnt //= 2
        
    return nega_cnt + posi_cnt >= K
  
  ok=10**18+1
  ng=0
  while abs(ok-ng)>1:
    mid=abs(ok+ng)//2
    if isOkPosi(mid):
      ok=mid
    else:
      ng=mid
  print(ok)

Submission status: Accepted

Solution code:
import numpy as np

n, k = [int(i) for i in input().split()]
a = np.array(sorted([int(i) for i in input().split()]))
posi = a[a > 0]
zero = a[a == 0]
nega = a[a < 0]

# 2分探索, mid より小さいものを数える
l = -10 ** 18 - 1
r = 10 ** 18 + 1
while r - l > 1:
    mid = (r + l) // 2
    cnt = 0
    if mid >= 0:
        cnt += len(zero) * n

    cnt += a.searchsorted(mid // posi, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid // nega), side="left")).sum()
    cnt -= np.count_nonzero(a * a <= mid)
    cnt //= 2
    if cnt >= k:
        r = mid
    else:
        l = mid
print(r)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [int(i) for i in input().split()]

A = sorted(A)

B = []
C = []
D = []

for i in range(len(A)):
  if A[i] < 0:
    B.append(A[i])
  elif A[i] == 0:
    C.append(A[i])
  else:
    D.append(A[i])

b = len(B)
c = len(C)
d = len(D)

def f(n):#積がn以下になる組み合わせの個数
  if n < 0:
    i = 0
    j = 0
    k = 0
    while i < b and j < d:
      if B[i]*D[j] > n:
        j += 1
      else:
        i += 1
        k += d-j
    return k
  
  elif n == 0:
    return (c*(c-1))//2 + b*c + b*d + c*d
  
  else:
    i = 0
    j = b-1
    k = 0
    while i < b and j > -1:
      if B[i]*B[j] > n:
        i += 1
        k += j+1
      else:
        j -= 1
    
    k = b**2-k
    
    i = 0
    j = d-1
    while i < d and j > -1:
      if D[i]*D[j] <= n:
        i += 1
        k += j+1
      else:
        j -= 1
        
    l = 0   
    for i in range(b):
      if B[i]**2 <= n:
        l += 1
        
    for i in range(d):
      if D[i]**2 <= n:
        l += 1
        
    return (k-l)//2 + (c*(c-1))//2 + b*c + b*d + c*d
  
l = - 10**18
h = 10**18

while l+1 < h:
  m = (l+h)//2
  if f(m) >= K:
    h = m
  else:
    l = m

print(h)

Submission status: Accepted

Solution code:
import numpy as np
n,k = map(int,input().split())
a = np.array(list(map(int,input().split())))
a.sort()
posi = a[a>0]
zero = a[a==0]
nega = a[a<0]

def cnt(x):
    c = 0
    if x >= 0:
        c += len(zero)*n
    c += np.searchsorted(a, x // posi, side = 'right').sum()
    c += (n-np.searchsorted(a, (- x - 1) // (-nega), side = 'right')).sum()
    c -= np.count_nonzero(a * a <= x)
    return c // 2

l = - 10 ** 18
r = 10 ** 18
while l + 1 < r:
    m = (l + r) // 2
    if cnt(m) < k:
        l = m
    else:
        r = m
print(r)

Submission status: Accepted

Solution code:
import bisect

n,k = map(int,input().split())
A = sorted([int(i) for i in input().split()])

inm = bisect.bisect_left(A,0)
inp = bisect.bisect_right(A,0)
mi = [-x for x in A[:inm]]
mi = mi[::-1]
pl = A[inp:]
zero = inp-inm
numm = inm
nump = n-inp

def shaku(x,l):
    count = 0
    ma = len(l)
    ri = ma-1
    for i in range(ma):
        while ri >= 0 and l[ri]*l[i] > x:
            ri -= 1
        count += max(ri-i,0)
        
    return count 

def search(x):
    count = 0
    if x >= 0:
        count += zero*(n-zero)+numm*nump+(zero*(zero-1))//2
        count += shaku(x,pl)
        count += shaku(x,mi)
            
        return count
    else:
        ri = 0
        for i in pl[::-1]:
            while ri < numm and i*mi[ri] < -x:
                ri += 1
            count += numm-ri
        return count

left = -10**18-1
right = 10**18+1
while right > left+1:
    mid = (left+right)//2
    a = search(mid)
    
    if a >= k:
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
import bisect

n,k = map(int,input().split())
A = sorted([int(i) for i in input().split()])


zero = A.count(0)
inm = bisect.bisect_left(A,0)
inp = bisect.bisect_right(A,0)
mi = [-x for x in A[:inm]]
mi = mi[::-1]
pl = A[inp:]
numm = inm
nump = n-inp

def shaku(x,l):
    count = 0
    if len(l) <= 1:
        return 0
    ri = len(l)-1
    for i in range(len(l)):
        while ri >= 0 and l[ri]*l[i] > x:
            ri -= 1
        
        count += max(ri-i,0)
        
    return count 

def search(x):
    count = 0
    if x >= 0:
        count += zero*(n-zero)+numm*nump+(zero*(zero-1))//2
        count += shaku(x,pl)
        count += shaku(x,mi)
            
        return count
    else:
        ri = 0
        
        for i in pl[::-1]:
            while ri < numm and i*mi[ri] < -x:
                ri += 1
            count += numm-ri
        return count

left = -10**18-1
right = 10**18+1
while right > left+1:
    mid = (left+right)//2
    a = search(mid)
    
    if a >= k:
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
import bisect

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

zero = A.count(0)
inm = bisect.bisect_left(A,0)
inp = bisect.bisect_right(A,0)
mi = [-x for x in A[:inm]]
mi = mi[::-1]
pl = A[inp:]
numm = inm
nump = n-inp

def shaku(x,l):
    count = 0
    if len(l) <= 1:
        return 0
    ri = len(l)-1
    for i in range(len(l)):
        while ri >= 0 and l[ri]*l[i] > x:
            ri -= 1
        
        count += max(ri-i,0)
        
    return count 

def search(x):
    count = 0
    if x >= 0:
        count += zero*(n-zero)+numm*nump+(zero*(zero-1))//2
        count += shaku(x,pl)
        count += shaku(x,mi)
            
        return count
    else:
        ri = 0
        
        for i in pl[::-1]:
            while ri < numm and i*mi[ri] < -x:
                ri += 1
            count += numm-ri
        return count

left = -10**18-1
right = 10**18+1
while right > left+1:
    mid = (left+right)//2
    a = search(mid)
    
    if a >= k:
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
N=[];Z=[];P=[]
for i in range(n):
  if a[i]<0:
    N.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    P.append(a[i])

if k<=len(N)*len(P):
  for i in range(len(N)):
    N[i]*=-1
  N.sort()
  P.sort()
  Nr=list(reversed(N))
  L=0;R=10**18+1
  while R-L>1:
    x=(L+R)//2
    ct=0
    ct2=0
    for j in range(len(Nr)):
      if ct2!=len(P):
        while Nr[j]*P[ct2]<x:
          ct2+=1
          if ct2==len(P):
            break
      ct+=len(P)-ct2
    if ct<k:
      R=x
    else:
      L=x
  print(-L)

elif k<=len(N)*len(P)+(len(Z)*(len(Z)-1))//2+len(Z)*(len(N)+len(P)):
  print(0)

else:
  y=len(N)*len(P)+(len(Z)*(len(Z)-1))//2+len(Z)*(len(N)+len(P))
  for i in range(len(N)):
    N[i]*=-1
  N.sort()
  P.sort()
  L=0;R=10**18+1
  Nr=list(reversed(N))
  Pr=list(reversed(P))
  while R-L>1:
    x=(L+R)//2
    ct=0
    ct2=0
    for j in range(len(Nr)):
      if ct2!=len(N):
        while Nr[j]*N[ct2]<=x:
          ct2+=1
          if ct2==len(N):
            break
      ct+=min(ct2,len(N)-1-j)
    ct3=0
    for j in range(len(Pr)):
      if ct3!=len(P):
        while Pr[j]*P[ct3]<=x:
          ct3+=1
          if ct3==len(P):
            break
      ct+=min(ct3,len(P)-1-j)
    if ct<k-y:
      L=x
    else:
      R=x
  print(R)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)


def main():
  n, k = map(int, input().split())
  A = np.array(input().split(), np.int64)
  
  A = np.sort(A)
  
  zero = A[A == 0]
  pos = A[A>0]
  neg = A[A<0]
  
  def F(x):
    cnt_tpl = 0
    #zero multipy ...
    if x>= 0:
      cnt_tpl += len(zero)*n
    #positive multipy ...
    cnt_tpl += np.searchsorted(A, x//pos, side='right').sum()
    cnt_tpl += (n - np.searchsorted(A, (-x-1)//(-neg), side='right')).sum()
    cnt_tpl -= np.count_nonzero(A*A<=x)
    assert cnt_tpl %2 ==0
    return cnt_tpl//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)
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
import numpy as np


TEST_INPUT = [
    """
    4 3
    3 3 -4 -2
    """,
    """
    10 40
    5 4 3 2 -1 0 0 0 0 0
    """,
    """
    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
    """
]
ANSWER = [
    "-6",
    "6",
    "448283280358331064"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


def query(a, n, a_arr_p, a_arr_n, n_zeros, k):

    # return (num of pairs <= a) < k

    if a >= 0:
        # negative
        res = len(a_arr_p) * len(a_arr_n)
        # zero
        res += n_zeros * (n - n_zeros) + n_zeros * (n_zeros - 1) // 2
        # p * p
        res_pp = np.searchsorted(a_arr_p, a // a_arr_p, side="right").sum()
        res_pp -= (a_arr_p * a_arr_p <= a).sum()
        res += res_pp // 2
        # n * n
        res_nn = np.searchsorted(a_arr_n, a // a_arr_n, side="right").sum()
        res_nn -= (a_arr_n * a_arr_n <= a).sum()
        res += res_nn // 2
    else:
        # p * n
        res = len(a_arr_p) * len(a_arr_n) - np.searchsorted(a_arr_n, (a_arr_p - a - 1) // a_arr_p, side="left").sum()
    # print(a, res)
    if res >= k:
        return True
    else:
        return False


def solve(n, k, a_list):

    left = - 10 ** 18 - 1
    right = 10 ** 18 + 1
    center = 0

    a_arr = np.array(a_list)

    a_arr_p = a_arr[a_arr > 0]
    a_arr_n = - a_arr[a_arr < 0]
    n_zeros = (a_arr == 0).sum()
    a_arr_p.sort()
    a_arr_n.sort()

    while left<right:
        center=(left+right)//2
        if query(center, n, a_arr_p, a_arr_n, n_zeros, k):
            right=center
        else:
            left=center+1

    return right


def input_and_solve(ih):
    n, k = map(int, ih.input().split())
    a_list = list(map(int, ih.input().split()))
    res = solve(n, k, a_list)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        # print(res, ans)
        assert str(res) == str(ans)


if __name__ == "__main__":
    #test()
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**20
    #mod = 10**9 + 7

    N,k = map(int, input().split())
    zero, p, n = 0, [], []
    a = list(map(int, input().split()))
    for i in a:
        if i==0:
            zero += 1
        elif i > 0:
            p.append(i)
        else:
            n.append(i)
    p.sort()
    n.sort(reverse=True)

    #決め打ち二分探索
    #rはk個以上作れる, lはk個作れない
    l, r = -inf, inf
    while r - l > 1:
        mid = (l + r) // 2
        cnt = 0
        #0以上とき0の分足す
        if mid >= 0:
            cnt += zero*(zero-1)//2 + zero*(N-zero)
        
        if mid > 0:
            #負数足す
            cnt += len(n) * len(p)
            #p, nについてそれぞれ尺取り法で調べる
            for a in (p, n):
                left, right = 0, len(a)-1
                while left < right:
                    #a[l]*a[r]は小さくなっていきmid以下になったらそこから数える
                    while left<right and a[left]*a[right]>mid:
                        right -= 1
                    cnt += right - left
                    #lは最小から始まるのでrの値をリセットする必要はない
                    left += 1
        else:
            right = len(n) - 1
            for left in range(len(p)):
                while right>=0 and p[left]*n[right]<=mid:
                    right -= 1
                cnt += len(n) - right - 1
        
        if cnt >= k:
            r = mid
        else:
            l = mid

    print(r)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A == 0]
nega = A[A < 0]

# 積がx以下の組を求める
def check(x):
    count = 0  # 積がx以下の組
    if x >= 0:
        count += len(zero) * N  # zero * N
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += (N - np.searchsorted(A, (-x - 1) // (-nega), side = 'right')).sum()  # nega * N
    count -= np.count_nonzero(A * A <= x)  # 自分自身との組
    return count // 2  #重複を消す

# 二分探索
low = -10 ** 18
high = 10 ** 18
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid) < K:  # OK
        low = mid
    else:               # NG
        high = mid

print(high)

Submission status: Accepted

Solution code:
import numpy as np
 
N,K=map(int, input().split())
A=np.sort(np.array(input().split(),np.int64))
z=A[A==0]
p=A[A>0]
n=A[A<0]
 
def f(x):
 cnt=0
 if x>=0:
  cnt+=len(z)*N
 cnt+=np.searchsorted(A,x//p,side='right').sum()
 cnt+=(N-np.searchsorted(A,(-x-1)//(-n),side='right')).sum()
 cnt-=np.count_nonzero(A*A<=x)
 assert cnt%2==0
 return cnt//2
 
l=-10**18
r=10**18
while l+1<r:
 x=(l+r)//2
 if f(x)>=K:
  r=x
 else:
  l=x
print(r)

Submission status: Accepted

Solution code:
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    Neg=[-a for a in A if a<0]
    Pos=[a for a in A if a>=0]
    Neg.sort(); Pos.sort()
    ln,lp=len(Neg),len(Pos)
 
    def cnt(x):
        ret=0
        if x<0:
            x=-x
            pos_idx=0
            for num in Neg[::-1]:
                while pos_idx<lp and Pos[pos_idx]*num<x:
                    pos_idx+=1
                ret+=lp-pos_idx
                if pos_idx==lp:
                    break
            return ret
        idx=0
        for num in Neg[::-1]:
            if num**2<=x:
                ret-=1
            while idx<ln and Neg[idx]*num<=x:
                idx+=1
            ret+=idx
        idx=0
        for num in Pos[::-1]:
            if num**2<= x:
                ret-=1
            while idx<lp and Pos[idx]*num<=x:
                idx+=1
            ret+=idx
        ret//=2
        ret+=ln*lp
        return ret
    
    l,r=-(10**18+1),10**18+1
    while r-l>1:
        m=(l+r)//2
        if cnt(m)<k:
            l=m
        else:
            r=m
    print(r)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    Neg=[-a for a in A if a<0]
    Pos=[a for a in A if a>=0]
    Neg.sort(); Pos.sort()
    ln,lp=len(Neg),len(Pos)

    def cnt(x):
        ret=0
        if x<0:
            x=-x
            pos_idx=0
            for num in Neg[::-1]:
                while pos_idx<lp and Pos[pos_idx]*num<x:
                    pos_idx+=1
                ret+=lp-pos_idx
                if pos_idx==lp:
                    break
            return ret
        idx=0
        for num in Neg[::-1]:
            if num**2<=x:
                ret-=1
            while idx<ln and Neg[idx]*num<=x:
                idx+=1
            ret+=idx
        idx=0
        for num in Pos[::-1]:
            if num**2<= x:
                ret-=1
            while idx<lp and Pos[idx]*num<=x:
                idx+=1
            ret+=idx
        ret//=2
        ret+=ln*lp
        return ret
    
    l,r=-(10**18+1),10**18+1
    while r-l>1:
        m=(l+r)//2
        if cnt(m)<k:
            l=m
        else:
            r=m
    print(r)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def solve_m(k, a_m, a_p):
    def syaku(mid):
        """mid以下になる組の数を数える"""
        rm = 0
        cnt = 0
        for lp, num in enumerate(a_p):
            while True:
                if rm >= len(a_m) or num * a_m[rm] > mid :
                    break
                else:
                    rm += 1
            cnt += rm
        return cnt
                
    ok, ng = 1, -10 ** 20
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if syaku(mid) >= k:
            ok = mid
        else:
            ng = mid
    return ok

    
def solve_p(k, a_m, a_p):
    def syaku(mid):
        """mid以下になる組の数を数える"""
        r = len(a_p)
        cnt = 0
        for l, num in enumerate(a_p):
            while True:
                if r == 0 or num * a_p[r - 1] <= mid:
                    break
                else:
                    r -= 1
            cnt += r
            if l <= r - 1:
                cnt -= 1
        r = len(a_m)
        for l, num in enumerate(a_m):
            while True:
                if r == 0 or num * a_m[r - 1] <= mid:
                    break
                else:
                    r -= 1
            cnt += r
            if l <= r - 1:
                cnt -= 1
        return cnt // 2

    a_m = sorted([-num for num in a_m])
    ok, ng = 10 ** 20, -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if syaku(mid) >= k:
            ok = mid
        else:
            ng = mid
    return ok


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

cnt_p, cnt_m, cnt_0 = 0, 0, 0
tmp_p, tmp_m, tmp_0 = 0, 0, 0
for num in a:
    if num > 0:
        tmp_p += 1
    elif num < 0:
        tmp_m += 1
    else:
        tmp_0 += 1
cnt_p += tmp_p * (tmp_p - 1) // 2 + tmp_m * (tmp_m - 1) // 2
cnt_m += tmp_p * tmp_m
cnt_0 += (tmp_p + tmp_m) * tmp_0 + tmp_0 * (tmp_0 - 1) // 2
# print(cnt_p, cnt_m, cnt_0)

a_m = sorted([a[i] for i in range(n) if a[i] < 0])
a_p = sorted([a[i] for i in range(n) if a[i] > 0])

if k <= cnt_m:
    ans = solve_m(k, a_m, a_p)
elif cnt_m < k <= cnt_m + cnt_0:
    ans = 0
else:
    ans = solve_p(k - cnt_m - cnt_0, a_m, a_p)
      
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

def count(x, li1, li2, p):
    cnt = 0
    now = len(li2)-1 if p else 0
    for ind, i in enumerate(li1):
        rng = range(now, -1, -1) if p else range(now, len(li2))
        for j in rng:
            if p and ind==j:
                continue
            if i*li2[j]<x:
                # print(cnt, ind, j)
                cnt += j+1 if p else len(li2)-j
                cnt -= 1 if p and ind<j else 0
                now = j
                break
        else:
            break
    return cnt//2 if p else cnt

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

def p_solve(x):
    tmp = count(x, posi, posi, True)
    tmp += count(x, nega[::-1], nega[::-1], True)
    # print(x, tmp)
    return np*nn+nn*nz+nz*np+nz*(nz-1)//2+tmp < k

def n_solve(x):
    return count(x, nega, posi, False) < k


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
nega = a[:bisect_left(a, 0)]
posi = a[bisect_right(a, 0):]
np = len(posi)
nn = len(nega)
nz = n - np - nn
if k <= np*nn:
    ans = bisect(nega[0]*posi[-1]-1, 0, n_solve)
elif k <= np*nn+nn*nz+nz*np+nz*(nz-1)//2:
    ans = 0
else:
    ma = 0
    if len(nega)>1:
        ma = nega[0]*nega[1]
    if len(posi)>1 and ma<posi[-1]*posi[-2]:
        ma = posi[-1]*posi[-2]
    ans = bisect(1, ma+1, p_solve)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

def count(x, li1, li2, p):
    cnt = 0
    now = len(li2)-1 if p else 0
    for ind, i in enumerate(li1):
        rng = range(now, -1, -1) if p else range(now, len(li2))
        for j in rng:
            if p and ind==j:
                continue
            if i*li2[j]<x:
                # print(cnt, ind, j)
                cnt += j+1 if p else len(li2)-j
                cnt -= 1 if p and ind<j else 0
                now = j
                break
        else:
            break
    return cnt//2 if p else cnt

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

def p_solve(x):
    tmp = count(x, posi, posi, True)
    tmp += count(x, nega[::-1], nega[::-1], True)
    # print(x, tmp)
    return np*nn+nn*nz+nz*np+nz*(nz-1)//2+tmp < k

def n_solve(x):
    return count(x, nega, posi, False) < k


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
nega = a[:bisect_left(a, 0)]
posi = a[bisect_right(a, 0):]
np = len(posi)
nn = len(nega)
nz = n - np - nn
if k <= np*nn:
    ans = bisect(-10**18-1, 0, n_solve)
elif k <= np*nn+nn*nz+nz*np+nz*(nz-1)//2:
    ans = 0
else:
    ma = 0
    if len(nega)>1:
        ma = nega[-1]*nega[-2]
    if len(posi)>1 and ma<posi[-1]*posi[-2]:
        ma = posi[-1]*posi[-2]
    ans = bisect(1, 10**18+1, p_solve)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.sort(np.array(input().split(),np.int64))
z = A[A == 0]
p = A[A > 0]
n = A[A < 0]



def check(x):
    # x以下の数がK個以上ある時、Trueを返す
    count = 0 #最後に２で割る
    if x >= 0:
        count += len(z) * N
    count += (np.searchsorted(A, x//p, side='right')).sum()
    count += (N - np.searchsorted(A, (-x-1)//(-n), side='right')).sum()
    count -= np.count_nonzero(A * A <= x) #ペアなので自分自身は駄目
    assert count % 2 == 0
    count //= 2
    return count >= K

left = - 10 ** 19 # NG
right = 10 ** 19 # OK
while right > left + 1:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

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

import bisect
n_m = bisect.bisect_left(a, 0)
n_0 = bisect.bisect_left(a, 1) - n_m
n_p = n - (n_m + n_0)

nn_p = n - (n_m * n_p + n_0 * (n - n_0) + n_0*(n_0-1)//2)

if( n_m * n_p < k)&(k <= n - nn_p):
    print(0)
    exit()

def calc_m(a, b, len_a, len_b, x):
    i = len_a-1
    j = 0
    cnt = 0
    while(True):
        tmp = a[i] * b[j]
        if( tmp < x):
            cnt += i+1
            j += 1
        else:
            i -= 1

        if(i < 0)|(j >= len_b):
            break
    return cnt

def calc_p(a,len_a, x):
    if(len_a <= 1):
        return 0

    i = len_a - 1
    j = 0
    cnt = 0
    while(True):
        tmp = a[i] * a[j]
        if( tmp < x):
            cnt += i+1 - ( i >= j)
            j += 1
        else:
            i -= 1

        if(i < 0)|(j >= len_a):
            break
    return cnt//2

if( n_m * n_p >= k):
    a_m = tuple(a[:n_m])
    a_p = tuple(a[  :(n - n_p -1):-1])

    ul = [a_m[-1] * a_p[-1]+1, n_m*n_p]
    dl = [a_m[0] * a_p[0]-1, 0]

    while(True):
        if(ul[0] - dl[0] == 1):
            break
        mid = (dl[0] + ul[0])//2
        mid_cnt = calc_m(a_m,a_p,n_m,n_p, mid)

        if( mid_cnt < k):
            dl = [ mid, mid_cnt ]
        else:
            ul = [ mid, mid_cnt ]

    print(dl[0])

else:
    k = k - (n - nn_p)
    a_m = tuple(a[n_m - 1::-1])
    a_p = tuple(a[ (n - n_p) :])

    if(n_m <= 1):
        ul = [a_p[-1] * a_p[-2]+1, nn_p]
        dl = [a_p[0] * a_p[1]-1, 0]
    elif(n_p <= 1):
        ul = [a_m[-1] * a_m[-2]+1, nn_p]
        dl = [a_m[0] * a_m[1]-1, 0]
    else:
        ul = [max(a_m[-1] * a_m[-2]+1 ,a_p[-1] * a_p[-2]+1), nn_p]
        dl = [min(a_p[0] * a_p[1]-1 ,a_m[0] * a_m[1]-1), 0]

    while(True):
        if(ul[0] - dl[0] == 1):
            break
        mid = (dl[0] + ul[0])//2
        mid_cnt = calc_p(a_m,n_m, mid) + calc_p(a_p,n_p, mid)

        if( mid_cnt < k):
            dl = [ mid, mid_cnt ]
        else:
            ul = [ mid, mid_cnt ]

    print(dl[0])

Submission status: Accepted

Solution code:
import numpy as np
n,k=map(int,input().split())
a=np.array(list(map(int,input().split())))
a.sort()
p=a[a>0]
z=a[a==0]
m=a[a<0]
l=-10**18
r=10**18
while r-l>1:
  mid=(r+l)//2
  cnt=0
  if mid>=0:
    cnt+=len(z)*n
  cnt+=a.searchsorted(mid//p,side='right').sum()
  cnt+=(n-a.searchsorted(-(-mid//m),side='left')).sum()
  cnt-=np.count_nonzero(a*a<=mid)
  cnt//=2
  if cnt>=k:
    r=mid
  else:
    l=mid
print(r)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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


def test(x):
    cnt = 0

    if x >= 0:
        cnt += len(zero) * N

    cnt += np.searchsorted(A, x // pos, side='right').sum()
    cnt += (N - np.searchsorted(A, (-x - 1) // -neg, side='right')).sum()
    cnt -= np.count_nonzero(A * A <= x)

    cnt //= 2

    return K <= cnt


l = -(10 ** 19)  # NG
r = 10 ** 19  # OK

while l + 1 != r:
    mid = (l + r) // 2

    if test(mid):
        r = mid
    else:
        l = mid

print(r)