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
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
import numpy as np
def resolve():
    N, K = lr()
    A = np.sort(np.array(lr(), np.int64))
    z = A[A == 0]
    p = A[A > 0]
    n = A[A < 0]
    
    def count_func(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 // n), side='left')).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 count_func(x) >= K:
            r = x
        else:
            l = x
    
    print(r)
resolve()

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right
n,k=map(int,input().split())
a=list(map(int,input().split()))
inf=10**20
a.sort()
mc=zc=pc=0
m=[]
p=[]
for i in a:
  if i<0:
    mc+=1
    m.append(i)
  elif i==0:
    zc+=1
  else:
    pc+=1
    p.append(i)
if mc*pc>=k:
  #ans<0
  for i in range(len(m)):m[i]*=-1
  k=mc*pc-k+1
  m=m[::-1]
  p=[0]+p
  ng=0
  ok=10**19+7
  mi=10**19+7
  while ng+1!=ok:
    ma=0
    mid=(ng+ok)//2
    co=0
    j=len(p)-1
    for i in m:
      while p[j]*i>mid:j-=1
      co+=j
      ma=max(ma,p[j]*i)
    if co<k:ng=mid
    else:
      ok=mid
      mi=min(mi,ma)
  print(-mi)
elif mc*pc+zc*(zc-1)//2+zc*(pc+mc)>=k:
  #ans=0
  print(0)
else:
  k-=mc*pc+zc*(zc-1)//2+zc*(pc+mc)
  for i in range(len(m)):m[i]*=-1
  m=m[::-1]
  m=[0]+m
  p=[0]+p
  ng=0
  ok=10**19+7
  mi=10**19+7
  while ng+1!=ok:
    ma=0
    mid=(ok+ng)//2
    co=0
    jjj=0
    j=len(p)-1
    pok=[]
    for i in range(len(p)):
      if p[i]==0:continue
      while p[j]*p[i]>mid:j-=1
      co+=max(0,j-i)
      ma=max(ma,p[j]*p[i])
    j=len(m)-1
    for i in range(len(m)):
      if m[i]==0:continue
      while m[j]*m[i]>mid:j-=1
      co+=max(0,j-i)
      ma=max(ma,m[j]*m[i])
    if co<k:ng=mid
    else:
      ok=mid
      mi=min(mi,ma)
  print(mi)

Submission status: Accepted

Solution code:
#abc_155_d
import numpy as np
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = np.array(a)
a.sort()

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

left = -10**18
right = 10**18

while left+1 < right:
    mid = (left+right)//2
    cnt = 0
    
    if mid >=0:
        cnt += len(zero) * n
    
    cnt += a.searchsorted(mid//plus, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//minus), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt /= 2
    
    if cnt >= k:
        right = mid
    if cnt < k:
        left=mid
        
print(right)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_right

N,K = LI()
A = LI()

P = []
Z = []
M = []
for a in A:
    if a < 0:
        M.append(a)
    elif a == 0:
        Z.append(a)
    else:
        P.append(a)

P.sort()
M.sort()

lm,lz,lp = len(M),len(Z),len(P)

nm = lm*lp
nz = lz*(lz-1)//2 + lz*(lm+lp)

if K <= nm:
    ok = 0
    ng = -10**18-1
    while abs(ok-ng) > 1:
        now = (ok+ng)//2
        num = 0
        p = -1
        for i in range(lp):
            tmp = p
            for j in range(p+1,lm):
                if P[i]*M[j] <= now:
                    tmp = j
                else:
                    break
            p = tmp
            num += p+1
        if num >= K:
            ok = now
        else:
            ng = now
    print(ok)
elif K <= nm+nz:
    print(0)
else:
    # 負数のリストを正数のリストと同様に扱えるようにする
    M = [-m for m in M]
    M.sort()
    ok = 10**18+1
    ng = 0
    while abs(ok-ng) > 1:
        now = (ok+ng)//2
        num = 0
        p = -1
        for i in range(lp)[::-1]:
            tmp = p
            for j in range(p+1,i):
                if P[i]*P[j] <= now:
                    tmp = j
                else:
                    break
            p = tmp
            num += min(p+1,i)
        p = -1
        for i in range(lm)[::-1]:
            tmp = p
            for j in range(p+1,i):
                if M[i]*M[j] <= now:
                    tmp = j
                else:
                    break
            p = tmp
            num += min(p+1,i)
        if num >= K-nm-nz:
            ok = now
        else:
            ng = now
    print(ok)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A_s = list(map(int,input().split()))
minus = [-x for x in A_s if x < 0]
plus = [x for x in A_s if x >= 0]
minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        r = 0
        x = -x
        for num in minus[::-1]:
            while r < len(plus) and plus[r] * num < x:
                r += 1
            ans += len(plus) - r
        return ans
        
    r = 0
    for num in minus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(minus) and minus[r] * num <= x:
            r += 1
        ans += r
    r = 0
    for num in plus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(plus) and plus[r] * num <= x:
            r += 1
        ans += r
    ans //= 2
    ans += len(minus) * len(plus)
    return ans


top = 2 * (10**18) + 2
bottom = 0

while top - bottom > 1:
    mid = (top + bottom) // 2
    if cnt(mid-10**18-1) < K:
        bottom = mid
    else:
        top = mid
print(int(top-10**18-1))

Submission status: Accepted

Solution code:
import numpy as np

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

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

def cnt(x):
    """return #{a <= x | a in A}"""
    ret = 0

    if x >= 0:
        ret += zero * N

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

overEq = 10**18 + 100
less = -10**18 - 100

while less + 1 < overEq:
    mid = (overEq + less) // 2
    if cnt(mid) >= K:
        overEq = mid
    else:
        less = mid

print(overEq)

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()

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

#infだと割ってもinf
left = -10 ** 18
right = 10 ** 18

while left + 1 < right:
    x = (left + right) // 2
    cnt = 0
    if x >= 0:
        cnt += n * len(zero)
    cnt += a.searchsorted(x // plus, side="right").sum()
    cnt += (n - a.searchsorted(-(-x // minus), side="left")).sum()
    cnt -= np.count_nonzero(a * a <= x)
    cnt //= 2

    if cnt >= k:
        right = x
    else:
        left = x

print(right)

Submission status: Accepted

Solution code:
import sys
import numpy as np
INF = 10**18+5
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a = np.sort(a)
    ap = a[a > 0]
    an = a[a < 0]
    zc = n * (n - ap.size - an.size)

    l = -INF
    r = INF
    while(l+1 < r):
        x = (l+r)//2

        total = (n-np.searchsorted(a, -(-x // an), side='left')).sum()
        if x >= 0:
            total += zc
        total += np.searchsorted(a, x // ap, side='right').sum()
        total -= a[a*a <= x].size
        total //= 2
        if total < k:
            l = x
        else:
            r = x

    print(r)


main()

Submission status: Accepted

Solution code:
import numpy as np
def f(nums, a):
  return 0  if nums.size<=1 else (np.searchsorted(nums, a//nums, side='right').sum()-np.searchsorted(nums, int(pow(a, 1/2)), side='right'))//2

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:] if p>0 else np.array([])
AN=A[:q] if q>0 else np.array([])

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  if q>1:
    AN=-AN[::-1]
  x=0
  y=10**18
  K=K-a-b
  while y-x>1:
    tmp=(y+x)//2
    if f(AP, tmp)+f(AN, tmp)<K:
      x=tmp
    else:
      y=tmp
  print(y)

Submission status: Accepted

Solution code:
import numpy as np
def f(nums, a):
  return 0  if nums.size<=1 else (np.searchsorted(nums, a//nums, side='right').sum()-np.searchsorted(nums, int(pow(a, 1/2)), side='right'))//2

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:] if p>0 else np.array([])
AN=A[:q] if q>0 else np.array([])

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  x=0
  y=10**18
  K=K-a-b
  if q<=1:
    while y-x>1:
      tmp=(y+x)//2
      if f(AP, tmp)<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  AN=AN[::-1]
  AN=-AN
  
  if p<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=f(AN, tmp)
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  while y-x>1:
    tmp=(y+x)//2
    if f(AP, tmp)+f(AN, tmp)<K:
      x=tmp
    else:
      y=tmp
  print(y)

Submission status: Accepted

Solution code:
import numpy as np

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
if p>0:
  AP=A[-p:]
else:
  AP=[]
if q>0:
  AN=A[:q]
else:
  AN=[]

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  x=0
  y=10**18
  K=K-a-b
  if q<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  AN=AN[::-1]
  AN=-AN
  
  if p<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  while y-x>1:
    tmp=(y+x)//2
    counter1=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
    counter2=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)

Submission status: Accepted

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

def main():
  N,K = map(int,input().split())
  A = sorted(list(map(int,input().split())))
  
  # AM:Aのうち負のもの
  # AP:Aのうち正のもの
  AM = []
  AP = []
  for a in A:
    if a > 0:
      AP.append(a)
    elif a < 0:
      AM.append(a)

  INF = 10**18+1
  l = -INF
  r = INF
  while(l+1 < r):
    # 積がc未満となるペアの個数xを求める。
    # K番目の積は、それより小さい積の個数がK未満である積のうち最大のもの。
    c = (l+r)//2
    x = 0
    if c > 0:
      # cが正の場合
      # まず、正×正または負×負のペアのうち、c未満となるペアの個数を求める。
      i = len(AP)-1
      for j in range(len(AP)):
        if j >= i:
          break
        while(j < i and AP[i]*AP[j] >= c):
          i -= 1
        x += i-j
      i = 0
      for j in range(len(AM)-1,-1,-1):
        if j <= i:
          break
        while (i < j and AM[i]*AM[j] >= c):
          i += 1
        x += j-i
      # さらに、正×負のペアは必ずc未満となるので、そのペアの個数も加算する。
      x += len(AP)*len(AM)
      # さらにさらに、0と任意のaとのペアも必ずc未満となるので、そのペアの個数も加算する。
      x += (len(AP)+len(AM))*(N-len(AP)-len(AM))
      if N-len(AP)-len(AM) > 1:
        x += (N-len(AP)-len(AM))*(N-len(AP)-len(AM)-1)//2
    elif c == 0:
      # cが0の場合
      # 正×負のペアがc未満となるペアになるので、その個数を求める。
      x += len(AP)*len(AM)
    else:
      # cが負の場合
      # 正×負のペアのうち、c未満となるペアの数を求める。
      i = 0
      for j in range(len(AM)):
        while(i < len(AP) and AP[i]*AM[j] >= c):
          i += 1
        x += len(AP)-i

    #print(l,r,c,x)
    if x < K:
      l = c
    else:
      r = c
  print(l)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

def main():
  N,K = map(int,input().split())
  A = sorted(list(map(int,input().split())))
  
  AM = []
  AP = []
  for a in A:
    if a > 0:
      AP.append(a)
    elif a < 0:
      AM.append(a)

  INF = 10**18+1
  l = -INF
  r = INF
  while(l+1 < r):
    # 積がc未満となるペアの個数xを求める。
    # K番目の積は、それより小さい積の個数がK未満である席のうち最大のもの。
    c = (l+r)//2
    x = 0
    if c > 0:
      i = len(AP)-1
      for j in range(len(AP)):
        if j >= i:
          break
        while(j < i and AP[i]*AP[j] >= c):
          i -= 1
        x += i-j
      i = 0
      for j in range(len(AM)-1,-1,-1):
        if j <= i:
          break
        while (i < j and AM[i]*AM[j] >= c):
          i += 1
        x += j-i
      #print(c,x)
      x += len(AP)*len(AM)
      x += (len(AP)+len(AM))*(N-len(AP)-len(AM))
      if N-len(AP)-len(AM) > 1:
        x += (N-len(AP)-len(AM))*(N-len(AP)-len(AM)-1)//2
    elif c == 0:
      x += len(AP)*len(AM)
    else:
      i = 0
      for j in range(len(AM)):
        while(i < len(AP) and AP[i]*AM[j] >= c):
          i += 1
        x += len(AP)-i

    #print(l,r,c,x)
    if x < K:
      l = c
    else:
      r = c
  print(l)

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()

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

l = -10**18
r = 10**18

while l + 1 < r:
    x = (l+r) // 2
    cnt = 0
    if x >= 0:
        cnt += N * len(zero)

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

    if cnt >= K:
        r = x
    else:
        l = x

print(r)

Submission status: Accepted

Solution code:
import numpy as np

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

A = np.array(input().split(), np.int64)

A.sort()

posA = A[A > 0]
negA = A[A < 0]
zeros = (A==0).sum()

left = -10**18
right = 10**18

while left+1 < right:
    num = (left+right)//2
    
    less_count = 0
    
    if num >= 0:
        less_count += zeros * n
    
    limit_pair_for_pos = num // posA
    limit_idxs = np.searchsorted(A, limit_pair_for_pos, side='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = -(num // -negA)
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A**2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2
    
    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Accepted

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

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

if K <= negative_pairs_cnt:
    # にぶたん: X以下になるペアがK個以上あるか？
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)

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

    print(ok)

elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

else:
    # にぶたん: X以下になるペアがK個以上あるか？
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0

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

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

            or_higher_cnt += max(0, r - l)

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

    print(ok)

Submission status: Accepted

Solution code:
import numpy as np

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

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

l = -10**18
r = 10**18

# 二分探索
# x以下になる組み合わせがいくつあるか計算する
while l+1<r:
    x = (l + r) // 2
    cnt = 0

    # 0になる組み合わせの個数のカウントを追加
    if x >= 0:
        cnt += n * len(zero)

    cnt += a.searchsorted(x//pos,side='right').sum()
    cnt += (n-a.searchsorted(-(-x//neg),side='left')).sum()
    cnt -= np.count_nonzero(a*a<=x)
    cnt//=2

    if cnt >= k:
        r = x
    else:
        l = x

print(r)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
z = 0
while a[z] < 0:
    z += 1
am = a[:z]
ap = a[z:]

if k <= len(am)*len(ap):
    ap = ap[::-1]
    a = -(10**18)-10
    b = 1000
    while True:
        if b-a <= 1:
            break
        m = (a+b)//2
        count = 0
        r = 0
        while r+1 < len(am) and ap[0]*am[r] <= m:
            r += 1
        for i in range(len(ap)):
            while r > 0 and ap[i]*am[r] > m:
                r -= 1
            if ap[i]*am[r] <= m:
                count += r+1
            else:
                count += r
        if count < k:
            a = m
        else:
            b = m
    print(b)
else:
    k -= len(am)*len(ap)
    am = list(map(lambda x: -x, am[::-1]))
    a = -1000
    b = 10**18+10
    while True:
        if b-a <= 1:
            break
        m = (a+b)//2
        count = 0
        r = len(ap)-1
        for i in range(len(ap)):
            while r > 0 and ap[i]*ap[r] > m:
                r -= 1
            if ap[i]*ap[r] <= m:
                if i <= r:
                    count -= 1
                count += r+1
            else:
                if i < r:
                    count -= 1
                count += r
        r = len(am)-1
        for i in range(len(am)):
            while r > 0 and am[i]*am[r] > m:
                r -= 1
            if am[i]*am[r] <= m:
                if i <= r:
                    count -= 1
                count += r+1
            else:
                if i < r:
                    count -= 1
                count += r
        if count//2 < k:
            a = m
        else:
            b = m
    print(b)

Submission status: Accepted

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

A = [A[i] for i in range(N) if A[i]!=0]
c = (N+len(A)-1)*(N-len(A))
N = len(A)
A.sort()
B = A[::-1]

def count(m):
    res = 0
    if m>=0:
        res += c
        j = N
        for i in range(N):
            if A[i]>0:
                break
            while j>0:
                if A[i]*A[j-1]<=m:
                    j -= 1
                else:
                    break
            res += N-j
        if A[i]>0:
            j = N-1
            for i in range(i,N):
                while j>=0:
                    if A[i]*A[j]>m:
                        j -= 1
                    else:
                        break
                res += j+1
    else:
        j = 0
        for i in range(N):
            if B[i]<0:
                break
            while j<N:
                if B[i]*B[j]>m:
                    j += 1
                else:
                    break
            res += N-j
        if B[i]<0:
            j = -1
            for i in range(i,N):
                while j<N-1:
                    if B[i]*B[j+1]<=m:
                        j += 1
                    else:
                        break
                res += j+1
    for i in range(N):
        if A[i]*A[i]<=m:
            res -= 1
    res //= 2
    return res

ng = -10**18
ok = 10**18
m = (ng+ok)//2
if N==0:
    ans = 0
else:
    for n in range(100):
        if count(m)<K:
            ng = m
        else:
            ok = m
        m = (ng+ok)//2
    ans = int(ok)
print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False


n,k = m()

a = l()

a.sort()

po = bs.bisect(a,0)

a,b = a[po:],a[po-1::-1]

n,m = len(a),len(b)

ok = 10 ** 18

bad = - ok

while ok - bad > 1:
    x = (ok + bad)//2
    s = 0
    if x >= 0:
        s += n*m
        t = 0
        i = n
        for y in a:
            while i and a[i-1] * y > x:
                i -= 1
            t+= i
            if y*y <= x:
                t-=1
        s += t // 2
        t = 0
        i = m
        for y in b:
            while i and b[i-1] * y> x:
                i -= 1
            t += i
            if y * y <= x:
                t -= 1
        s += t//2
    else:
        i = m
        for y in a:
            while i and b[i-1] * y <= x:
                i -= 1
            s += m-i
    if s >= k:
        ok = x
    else:
        bad = x
print(ok)

Submission status: Accepted

Solution code:
import bisect
import numpy as np

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

#N,K = 9,9
#A = [-3,-2,-2,-2,0,0,1,2,2]

def simple():
    B = sorted([A[i] * A[j] for i in range(N) for j in range(i+1,N)])
    return B[K-1]

def solve():
    A.sort()

    iplus = bisect.bisect_right(A,0)
    izeros = bisect.bisect_left(A,0)

    pluss = np.array(A[iplus:]).astype(np.int64)
    zeros = A[izeros:iplus]
    minuss = np.array(A[:izeros]).astype(np.int64)

    nplus = len(pluss)
    nzero = len(zeros)
    nminus = len(minuss)

    npminus = nplus * nminus
    npzeros = nzero * (nplus + nminus) + nzero * (nzero-1)//2

    if npminus < K <= npminus + npzeros:
        return 0
    elif K <= npminus:
        mn = A[-1] * A[0] - 1
        mx = 0
        while mx-mn > 1:
            mid = (mn+mx)//2
            xs = -(-mid//minuss)
            cnt = nplus * nminus
            cnt -= np.sum(np.searchsorted(pluss,xs,side="left"))
            if cnt >= K:
                mx = mid
            else:
                mn = mid
        return mx
    else:
        nK = K - npminus - npzeros
        pluss2 = (-minuss)[::-1]
        mn = -1
        mx = max(A[0]**2, A[-1]**2)
        pluss_p2 = pluss**2
        pluss2_p2 = pluss2**2
        while mx-mn > 1:
            mid = (mn+mx)//2
            cnt = 0
            xs = mid//pluss
            cnt += np.sum(np.searchsorted(pluss,xs,side='right'))
            cnt -= np.count_nonzero(pluss_p2 <= mid)
            xs2 = mid//pluss2
            cnt += np.sum(np.searchsorted(pluss2,xs2,side='right'))
            cnt -= np.count_nonzero(pluss2_p2 <= mid)
            cnt = cnt //2
            #print(mn,mid,mx,cnt)
            if nK <= cnt:
                mx = mid
            else:
                mn = mid
        return mx

print(solve())
#for K in range(1,N*(N-1)//2+1):
#    print(solve(),simple())

Submission status: Accepted

Solution code:
from sys import stdin
f_i = stdin

import numpy as np

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

A = np.sort(A)
zero_left = A.searchsorted(0, side='left')
zero_right = A.searchsorted(0, side='right')
zero_cnt = zero_right - zero_left
pos = A[zero_right:]
neg = A[:zero_left]

def f(x):
    cnt = 0
    
    if x >= 0:
        cnt += zero_cnt * 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 ** 2 <= x)
    return cnt // 2


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

print(right)

Submission status: Accepted

Solution code:
import bisect

N, K = map(int, input().split())
A = [int(x) for x in input().split()]

# Aを正負で分け、「積が負、積が0、積が正」それぞれのペア数を求める
A_minus = sorted([a for a in A if a < 0])
A_plus = sorted([a for a in A if a > 0])
len_minus = len(A_minus)
len_plus = len(A_plus)
len_zero = N - len_minus - len_plus
pairs_num = (len_minus * len_plus,
             (len_minus + len_plus) * len_zero + len_zero * (len_zero - 1) // 2,
             len_minus * (len_minus - 1) // 2 + len_plus * (len_plus - 1) // 2)
assert sum(pairs_num) == N * (N - 1) // 2

if K <= pairs_num[0]:
    L = -10 ** 18
    R = -1
    while True:
        M = (L + R) // 2
        count = 0
        j = 0
        for i in range(len_plus):
            while j < len_minus and A_plus[i] * A_minus[j] <= M:
                j += 1
            count += j
        
        if count < K and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M
            
elif pairs_num[0] < K <= pairs_num[0] + pairs_num[1]:
    print(0)
    
else:
    K -= pairs_num[0] + pairs_num[1]
    A_minus = list(map(lambda x: -x, reversed(A_minus)))
    L = 1
    R = 10 ** 18
    while True:
        M = (L + R) // 2
        count = 0
        j = 0
        for i in range(len_minus-1, -1, -1):
            while j < len_minus and A_minus[i] * A_minus[j] <= M:
                j += 1
            count += max(0, j - i - 1)
        j = 0
        for i in range(len_plus-1, -1, -1):
            while j < len_plus and A_plus[i] * A_plus[j] <= M:
                j += 1
            count += max(0, j - i - 1)
            
        if count < K and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M

Submission status: Accepted

Solution code:
from bisect import bisect
def main():
  n,k,*a=map(int,open(0).read().split())
  a.sort()
  i=bisect(a,0)
  a,b=a[i:],a[i-1::-1]
  n,m=len(a),len(b)
  ok=10**18
  ng=-ok
  while ok-ng>1:
    x=(ok+ng)//2
    s=0
    if x>=0:
      s+=n*m
      t=0
      i=n
      for y in a:
        while i and a[i-1]*y>x:
          i-=1
        t+=i
        if y*y<=x:
          t-=1
      s+=t//2
      t=0
      i=m
      for y in b:
        while i and b[i-1]*y>x:
          i-=1
        t+=i
        if y*y<=x:
          t-=1
      s+=t//2
    else:
      i=m
      for y in a:
        while i and b[i-1]*y<=x:
          i-=1
        s+=m-i
    if s>=k:
      ok=x
    else:
      ng=x
  print(ok)

main()

Submission status: Accepted

Solution code:
import numpy as np


def partsolve(A, x, positive, zero, negative):
    """
    :param A:
    :param x:
    :return: Aの積のペアの中で、x以下となるペアの個数
    """
    count = 0
    if x >= 0:
        count = len(zero) * len(A)
    P = x // positive
    Pc = np.searchsorted(A, P, side='right')
    count += Pc.sum()

    N = (-x-1) // -negative
    Nc = np.searchsorted(A, N, side='right')
    Nc = len(A) - Nc
    count += Nc.sum()

    count -= np.count_nonzero(A * A <= x)
    return count // 2

def solve(N, K, As):
    A = np.array(sorted(As), np.int64)
    positive = A[A > 0]
    zero = A[A == 0]
    negative = A[A < 0]

    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(A, mid, positive, zero, negative)
        if c < K:
            left = mid
        else:
            right = mid
    return right


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Submission status: Accepted

Solution code:
import numpy as np


def partsolve(A, x, positive, zero, negative):
    """
    :param A:
    :param x:
    :return: Aの積のペアの中で、x以下となるペアの個数
    """
    count = 0
    if x >= 0:
        count = len(zero) * len(A)
    P = x // positive
    Pc = np.searchsorted(A, P, side='right')
    count += Pc.sum()

    N = (-x-1) // -negative
    Nc = np.searchsorted(A, N, side='right')
    Nc = len(A) - Nc
    count += Nc.sum()

    count -= np.count_nonzero(A * A <= x)
    return count // 2

def solve(N, K, As):
    A = np.array(sorted(As), np.int64)
    positive = A[A > 0]
    zero = A[A == 0]
    negative = A[A < 0]

    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(A, mid, positive, zero, negative)
        if c < K:
            left = mid
        else:
            right = mid
    return right



if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))