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:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# neg, zero, posに分けて、二分探索
N, K = lr()
A = np.array(lr()); A.sort()
neg = A[A<0]
zero = A[A==0]
pos = A[A>0]

def check(x):
    '''x以下の積がK個以上あるならTrueを返す'''
    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)
    assert cnt % 2 == 0
    return (cnt//2) >= K

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

print(ok)
# 30

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# neg, zero, posに分けて、二分探索
N, K = lr()
A = np.array(lr()); A.sort()
neg = A[A<0]
zero = A[A==0]
pos = A[A>0]

def check(x):
    '''x以下の積がK個以上あるならTrueを返す'''
    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)
    assert cnt % 2 == 0
    return (cnt//2) >= K

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

print(ok)
# 30

Submission status: Accepted

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

# 負、ゼロ、正の個数
np = 0
nA = []
zp = 0
pp = 0
pA = []

# Aの正負の判定
for i in A:
    if i < 0:
        np += 1
        nA.append(-i)
    elif i >0:
        pp += 1
        pA.append(i)
    else:
        zp += 1
nA=nA[::-1]
# この時点で、両方絶対値の昇順になっている

# K番目の積の正負の判定ように数を作成
ncc = np*pp
zcc = zp*(np+pp)+(zp*(zp-1))//2
pcc = (np*(np-1))//2+(pp*(pp-1))//2

# 負の場合
if K <= ncc:
    K = ncc-K
    # nAから一つとpAから一つをかける
    # 積がxより大きい個数を求めて、それを二分探査で狭めていく
    minK = 0
    maxK = 10**18+1
    while maxK-minK != 1:
        x = (maxK+minK)//2
        # 積がxより大きい個数をしゃくとり法で求める
        count = 0
        pos = pp-1
        for i in range(np):
            while pos != -1:
                if pA[pos] > x//nA[i]:
                    pos -= 1
                else:
                    break
            count += pos+1
        if count > K:
            maxK = x
        else:
            minK = x
    print(-maxK)
elif K <= (ncc+zcc):
    print(0)
# 正の場合
else:
    K-=(ncc+zcc)
    # nAとnAをかけるかpAとpAをかける
    minK = 0
    maxK = 10 ** 18
    x = 0
    while maxK-minK != 1:
        x = (maxK + minK) // 2
        # 積がxより大きい個数をしゃくとり法で求める
        count = 0
        pos = np-1
        for i in range(np):
            while pos !=-1:
                if nA[pos] > x//nA[i]:
                    pos -=1
                else:
                    break
            count += pos+1
            if nA[i]**2<x:
                count -= 1
        pos = pp-1
        for i in range(pp):
            while pos != -1:
                if pA[pos] > x // pA[i]:
                    pos -= 1
                else:
                    break
            count += pos + 1
            if pA[i] ** 2 < x:
                count -= 1
        count = count//2
        if count >= K:
            maxK = x
        else:
            minK = x
    print(maxK)

Submission status: Accepted

Solution code:
import numpy as np
n,k=map(int,input().split())
a=np.sort(np.array(input().split(),'int64'))

plus=a[a>0]
zeros=np.sum(a==0)
minus=a[a<0]

def counter(T):
  c=0
  if T>=0:
    c+=zeros*n
  c+=np.searchsorted(a,T//plus,side='right').sum()
  c+=(n-np.searchsorted(a,(-T-1)//(-minus),side='right')).sum()
  c-=np.count_nonzero(a*a<=T)
  return c//2

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,k=f()
lm,lp=[],[]
for i in f():
  if i<0: lm.append(-i)
  else: lp.append(i)
lm.sort()
lp.sort()
cm=len(lm)
cp=len(lp)
def cnt(x):
  c=0
  if x<0:
    r=cp
    for i in lm:
      while r and i*lp[r-1]>=-x: r-=1
      c+=cp-r
    return c
  r=cm
  for i in lm:
    while r and i*lm[r-1]>x: r-=1
    c+=r
    if i*i<=x: c-=1
  r=cp
  for i in lp:
    while r and i*lp[r-1]>x: r-=1
    c+=r
    if i*i<=x: c-=1
  return cm*cp+c//2
INF=10**18+1
l,r=-INF,INF
while r-l>1:
  m=l+r>>1
  if cnt(m)<k: l=m
  else: r=m
print(r)

Submission status: Accepted

Solution code:
import numpy as np
import sys
input=sys.stdin.readline
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
pos = np.sort(a[a>0])
neg = np.sort(np.abs(a[a<0]))
zero = (a==0).sum()

INF = 2*(10**18)
l = -INF
r = INF
while(r-l>1):
    mid = (l+r)//2
    cnt = 0
    if mid >= 0:
        cnt = len(pos)*len(neg)  #(+) * (-)
        cnt += (len(pos)+len(neg)) * zero # 0 * (non-zero)
        cnt += (zero*(zero-1))//2 # 0 * 0
        x = np.searchsorted(pos, mid//pos, side='right').sum() #(+) * (+)
        x += np.searchsorted(neg, mid//neg, side='right').sum() #(-) * (-)
        x -= (pos*pos<=mid).sum()
        x -= (neg*neg<=mid).sum()
        cnt += x/2
    else:
        #積がmid以上になれば良い -> midよりも小さい
        cnt = (len(neg) - np.searchsorted(neg, abs(mid)//pos + (mid%pos!=0), side='left')).sum()
    #print(mid, cnt)
    #cnt := 積がmid以下になる物の数
    #k番目の数　-> それ以下のものがk個以上ある事が必要
    #cntがk個よりも少ない -> 条件を満たしていない
    #cntがそれ以上ならok
    if cnt < k:
        l = mid
    else:
        r = mid
print(r)

Submission status: Accepted

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

INF = 2*(10**18)
l = -INF
r = INF

while(r-l>1):
    mid = (l+r)//2
    cnt = 0
    if mid >= 0:
        cnt = len(pos)*len(neg)  #(+) * (-)
        cnt += (len(pos)+len(neg)) * zero # 0 * (non-zero)
        cnt += (zero*(zero-1))//2 # 0 * 0
        x = np.searchsorted(pos, mid//pos, side='right').sum() #(+) * (+)
        x += np.searchsorted(neg, mid//neg, side='right').sum() #(-) * (-)
        x -= (pos*pos<=mid).sum()
        x -= (neg*neg<=mid).sum()
        cnt += x/2
    else:
        #積がmid以上になれば良い -> midよりも小さい
        cnt = (len(neg) - np.searchsorted(neg, abs(mid)//pos + (mid%pos!=0), side='left')).sum()
    #print(mid, cnt)
    #cnt := 積がmid以下になる物の数
    #k番目の数　-> それ以下のものがk個以上ある事が必要
    #cntがk個よりも少ない -> 条件を満たしていない
    #cntがそれ以上ならok
    if cnt < k:
        l = mid
    else:
        r = mid
print(r)

Submission status: Accepted

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

# np.int64をつけないと、後でA**2を計算したときに桁あふれする
A = np.array(sorted(list(map(int,input().split()))), np.int64)
posA = A[A > 0] # 正の数のみの配列
negA = A[A < 0] # 負の数のみの配列
z = (A==0).sum() # 0の個数

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

while left+1 < right:
    num = (left+right)//2
    # ペア積の配列の中で、numより小さいものの数を数えていく。
    count = 0 # まずは0で初期化する。
    # もしnumが0以上であれば、積がゼロになるペア積の数を足しこむ
    if num >= 0:
        # この段階では値がゼロのものについて自分との積をあえてカウントする
        count += z*n 
    # 正の数に対して、かけてもnumを超えない最大の数字のリスト
    limit_pos = num // posA
    # limit_posの各数字を下回る数がAの中に何個あるかのリスト
    limit_idx = np.searchsorted(A, limit_pos, side='right')
    count += limit_idx.sum()

    # 負の数に対して、かけてもnumを超えない最大の数字のリスト
    limit_neg = -(-num // negA)
    # limit_negの各数字を下回る数がAの中に何個あるかのリスト
    limit_idx = n - np.searchsorted(A, limit_neg, side='left')
    count += limit_idx.sum()
    
    duplicate_cases = (A ** 2 <= num).sum()

    count -= duplicate_cases
    count //= 2

    if count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Accepted

Solution code:
import numpy as np

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

a_list.sort()

zero_list = a_list[a_list == 0]
minus_list = a_list[a_list < 0]
plus_list = a_list[a_list > 0]

def index_count(x):
    cnt = 0
    if x >= 0:
        cnt += len(zero_list) * n
    cnt += np.searchsorted(a_list, x // plus_list, side='right').sum()
    cnt += (n - np.searchsorted(a_list, -(-x // minus_list), side='left')).sum()
    cnt -= np.count_nonzero(a_list * a_list <= x)
 
    assert cnt % 2 == 0
    return cnt // 2
 
 
left = -10**18
right = 10**18
 
while left + 1 < right:
    mid = (left + right) // 2
    a = index_count(mid)
    if a >= k:
        right = mid
    else:
        left = mid
 
print(right)

Submission status: Accepted

Solution code:
from copy import copy

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

        return ret

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


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


def solve_zero():
    return 0


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


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

a.sort()

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

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


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

Submission status: Accepted

Solution code:
import numpy as np
N,K = [int(i) for i in input().split(' ')]

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

A.sort()
zero = A[A==0]
minus = A[A<0]
plus = A[A>0]

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

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


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

while left + 1 < right:
    mid = (left +right) //2
    a = index_count(mid)
    if a >= K:
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:


from bisect import bisect

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

cnt_positive = N - bisect(A, 0)
cnt_zero = A.count(0)
cnt_negative = N - cnt_positive - cnt_zero


def is_ok(mid):
    
    if mid < 0:
        cnt_under_mid = 0
        # i=0のときと組み合わせが被らないようにjは1から
        j = 1
        for i in range(cnt_negative):
            a = A[i]
            # A[i]が負なので、A[i] * A[j]は単調減少
            while a * A[j] > mid:
                j += 1
                if j >= N:
                    break
            # あるiについて、A[i] * A[j~N-1] <= mid を満たすペアの数を足す
            cnt_under_mid += (N - j)

            # この時点で積がmid以下になるペアの数がK個以上あれば、そのmidについてそれ以上調べる必要はない
            if cnt_under_mid >= K:
                return True

            # この時点で積がmidのペアの個数がK未満かつ、それ以上mid以下にできる組み合わせがない場合、探索を打ち切る
            if j >= N:
                break

        return False

    # midが0以上の場合、

    else:
        """
        こちらではmidより大きくなる個数を全ペアの個数から引いて考える
        """
        cnt_over_mid = 0
        cnt_duplicate = 0
        r = cnt_negative-1 # A[l]が負のindexで一番右にあるやつ
        for l in range(cnt_negative):
            a = A[l]
            # A[l] * A[r]はrを左に寄せてくるにつれて大きくなる（負 x 負で,右側の負の徐々に絶対値が大きくなるから）
            while a * A[r] <= mid:
                r -= 1
                # lについて、いずれのrをペアにとってもmidを上回らないなら、負の要素についての探索を打ち切る
                if r <= -1:
                    break
            cnt_over_mid += r+1 # 例えばidxでj=2になった時に積がmidを上回るなら、j=0,1,2の三つとの積でmidを超える、みたいな
            # 同じインデックスでペアを作る場合、重複を取り除く
            if r >= l: cnt_duplicate += 1
            # iを右に動かすにつれて、ｊを左に動かさないとmidを超える積ができなくなる（iを右にすると絶対値が小さくなるので、jのほうは絶対値を大きくする必要がある）
            # jをもう動かすことができなくなったら、A[i]が負の場合に、それ以上midを上回るペアを作れないので探索を打ち切る
            if r <= -1:
                break
        
        # Aの要素について、負以外の場合
        cnt_not_positive = cnt_negative + cnt_zero
        l = cnt_not_positive
        # 今度は右から見ていって、対象をlとして、lより右側にある物とペアになればmidを超える、みたいな
        for r in range(N-1, cnt_not_positive-1, -1):
            a = A[r]
            while a * A[l] <= mid:
                # ペアを作って積がmidを超えるまで、lを右にずらしていく
                l += 1
                # これ以上lを右にずらせない場合打ち切り
                if l >= N:
                    break
            # あるrについて、lより右にあるものとペアを作るとmidを超えるので、その個数を足す
            cnt_over_mid += N-l
            # rのペアにrを選んでいる場合は取り除く
            if l <= r:
                cnt_duplicate += 1

            # それ以上lを右にずらせない場合は探索を打ち切る
            if l >= N:
                break
        
        cnt_under_mid = (N*(N-1) // 2) - ((cnt_over_mid - cnt_duplicate) // 2)
        return cnt_under_mid >= K


ok = 10**18 + 1
ng = -1 * 10**18 - 1

while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

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

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

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

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

        while abs(ok - ng) > 1:

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

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

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

    elif nega_pairs_cnt < K <= nega_pairs_cnt + zero_pairs_cnt:
        print(0)
        return
    else:
        K -= (nega_pairs_cnt + zero_pairs_cnt)
        ok, ng = 10 ** 18, 0
        while abs(ok - ng) > 1:
            X = (ok + ng) // 2
            or_higher_cnt = 0
            r = N - 1
            for l in range(posi_start, N):
                while (r < N) and (A[l] * A[r] > X) and (l < r):
                    r -= 1
                or_higher_cnt += max(0, r - l)

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

                or_higher_cnt += max(0, r - l)

            if or_higher_cnt >= K:
                ok = X
            else:
                ng = X
        print(ok)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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]
#print(posi)
# 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

    # a.searchsorted(v, side="left"): a[i-1] < v <= a[i]であるvのindexを返す
    # a.searchsorted(v, side="right"): a[i-1] <= v < a[i]であるvのindexを返す

    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
    #print("mid:", mid)
    #print("mid//posi:", mid//posi)
    #print("search:", a.searchsorted(mid//posi,side="right"))
    #print("-(-mid//nega):", -(-mid//nega))
    #print("search:", a.searchsorted(-(-mid//nega),side="left"))
    #print("nonzero_count:", np.count_nonzero(a*a<=mid))
    #print("count:", cnt)
    #print('-' * 20)
    if cnt >= k:
        r = mid
    else:
        l = mid
print(r)

Submission status: Accepted

Solution code:
import numpy as np

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

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

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = np.sort(A)

G = A[A > 0]
Z = A[A == 0]
L = A[A < 0]

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

while l-r > 1:
  # 「積がm以下になるペアの数」を調べる。
  m = (l+r) // 2

  # A[A > 0]内から条件を満たすものの数?
  Pk = np.searchsorted(A, m//G, side="right").sum()

  # A[A < 0]内から条件を満たすものの数?
  Nk = (N - np.searchsorted(A, (-m-1)//(-L), side="right")).sum()

  # 同じ要素同士の積は重複しているため、条件を満たしていたら減らす
  duplicate = np.count_nonzero(A*A <= m)

  # A[0]内から条件を満たすものの数?
  Zk = 0
  if m >= 0:
    Zk += len(Z) * N

  # 条件を満たす要素の数を合わせる
  k = Pk + Nk + Zk - duplicate
  
  # 全要素が二重になっている。重複要素を削除
  k //= 2

  # 条件を満たす要素数kがK個以上ならmを低く、Kより少ないならmを高くする
  if k >= K:
    l = m
  else:
    r = m
#lとrが一致すればmが一意に定まる
print(l)

Submission status: Accepted

Solution code:
from bisect import *
from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = []
Am = []
for a in A:
    if a >= 0:
        Ap.append(a)
    elif a < 0:
        Am.append(a)
p = len(Ap)
m = len(Am)
Ap.sort()
Am.sort(reverse=True)
U = 10 ** 18
L = - 10 ** 18
while U - L > 1:
    mid = (U+L)//2
    cnt = 0
    if mid >= 0:
        cnt += p*m
        i = p
        t = 0
        for a in Ap:
            while i and Ap[i-1] * a > mid:
                i -= 1
            t += i
            if a*a <= mid:
                t -= 1
        cnt += t//2
        i = m
        t = 0
        for a in Am:
            while i and Am[i-1] * a > mid:
                i -= 1
            t += i
            if a*a <= mid:
                t -= 1
        cnt += t//2
    else:
        i = m
        for a in Ap:
            while i and Am[i-1] * a <= mid:
                i -= 1
            cnt += m - i   
    if cnt < K:
        L = mid
    else:
        U = mid
print(U)

Submission status: Accepted

Solution code:
import numpy as np

def check(mid):
  cnt=0
  if mid>=0:
    cnt+=len(zero)*N
  cnt+=np.searchsorted(A, mid//pos, side="right").sum()
  cnt+=(N-np.searchsorted(A, (-mid-1)//(-neg), side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  return cnt//2

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

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

high=10**18
low=-10**18
while low+1<high:
  mid=(high+low)//2
  if check(mid)>=K:
    high=mid
  else:
    low=mid
print(high)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

def comb(n, k):
	p, q = 1, 1
	for i in range(1, k+1):
		p = p * (n-i+1)
		q = q * i
	return p // q

def binsearch(l, r, f):
	while r - l > 1:
		c = (r + l) // 2
		if f(c):
			r = c
		else:
			l = c
	return r

N, K = rl()
A = rl()

pos = 0
neg = 0
zero = 0
Ap = []
An = []
for a in A:
	if a > 0:
		pos += 1
		Ap.append(a)
	elif a < 0:
		neg += 1
		An.append(a)
	else:
		zero += 1
Ap.sort()
An.sort()
n_pos = comb(pos, 2) + comb(neg, 2)
n_neg = pos * neg
n_zero = zero*(N-zero) + comb(zero, 2)

def num_gt(A, x):
	j = len(A) - 1
	cnt = 0
	for i in range(len(A)):
		while i < j and A[i] * A[j] > x:
			j -= 1
		if i >= j:
			break
		cnt += max(j - i, 0)
	return cnt

def num_gt2(A, B, x):
	j = len(B) - 1
	cnt = 0
	for i in reversed(range(len(A))):
		while j >= 0 and A[i] * B[j] > x:
			j -= 1
		if j < 0:
			break
		cnt += max(j+1, 0)
	return cnt

def check_plus(x):
	cnt = n_neg + n_zero
	cnt += num_gt(Ap, x)
	cnt += num_gt(list(reversed(An)), x)
	return cnt >= K

def check_minus(x):
	cnt = num_gt2(Ap, An, x)
	return cnt >= K

ans = 0
if K <= n_neg:
	l = An[0] * Ap[-1] - 1
	r = 0
	ans = binsearch(l, r, check_minus)
elif K <= n_neg + n_zero:
	ans = 0
else:
	l = 0
	r = 1
	if len(Ap) >= 2:
		r = max(r, Ap[-1] * Ap[-2]) + 1
	if len(An) >= 2:
		r = max(r, An[0] * An[1]) + 1
	ans = binsearch(l, r, check_plus)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
np,nn=len(ap),len(an)
def fminus(x):
  j=0
  cnt=0
  for i in range(np):
    cnt+=j
    while j<nn and an[j]*ap[i]>=x:
      j+=1
      cnt+=1
  return cnt
def fplus(x,length,lis):
  r=length-1
  cnt=0
  for l in range(length):
    while lis[r]*lis[l]>x:
      if r==l:
        break
      r-=1
    if r==l:
      break
    elif lis[r]*lis[l]<=x:
      cnt+=r-l
  return cnt
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    an.sort(reverse=True)
    ap.sort()
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      if fminus(mid)>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    an.sort()
    ap.sort()
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      if fplus(mid,nn,an)+fplus(mid,np,ap)>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n, k = MI()

a = np.array(sorted([int(i) for i in input().split()]))

pos = a[a > 0]
zero = a[a == 0]
neg = 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 // pos, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid // neg), 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

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def solve_negative():
        ok = -1
        ng = -(10 ** 18)
        a_neg_desc = a_neg[::-1]
        a_pos_desc = a_pos[::-1]

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            pidx = 0
            count = 0
            for elem_neg in a_neg_desc:
                while pidx < pos_cnt:
                    elem_pos = a_pos_desc[pidx]
                    prod = elem_neg * elem_pos
                    if prod > mid:
                        break
                    else:
                        pidx += 1
                count += pidx
            if count >= k:
                ok = mid
            else:
                ng = mid

        print(ok)

    def solve_positive():
        kp = k - (prod_neg_cnt + prod_zer_cnt)
        ok = 10 ** 18
        ng = 0
        a_neg_desc = a_neg[::-1]
        a_pos_desc = a_pos[::-1]

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            pidx = 0
            nidx = 0
            count = 0
            for i, elem_pos1 in enumerate(a_pos_desc):
                while pidx < pos_cnt:
                    elem_pos2 = a_pos[pidx]
                    prod = elem_pos1 * elem_pos2
                    if prod > mid:
                        break
                    else:
                        pidx += 1
                count += min(pidx, pos_cnt - (i + 1))

            for i, elem_neg1 in enumerate(a_neg):
                while nidx < neg_cnt:
                    elem_neg2 = a_neg_desc[nidx]
                    prod = elem_neg1 * elem_neg2
                    if prod > mid:
                        break
                    else:
                        nidx += 1
                count += min(nidx, neg_cnt - (i + 1))

            if count >= kp:
                ok = mid
            else:
                ng = mid

        print(ok)

    import bisect
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    neg_cnt = bisect.bisect_left(a, 0)
    zer_cnt = bisect.bisect_left(a, 1) - neg_cnt
    pos_cnt = n - (neg_cnt + zer_cnt)

    prod_neg_cnt = neg_cnt * pos_cnt
    prod_pos_cnt = (neg_cnt * (neg_cnt - 1) + pos_cnt * (pos_cnt - 1)) // 2
    prod_zer_cnt = ((n * (n - 1)) // 2) - (prod_neg_cnt + prod_pos_cnt)

    a_neg = a[:neg_cnt]
    a_pos = a[(n - pos_cnt):]

    if k <= prod_neg_cnt:
        solve_negative()
    elif k <= (prod_neg_cnt + prod_zer_cnt):
        print(0)
    else:
        solve_positive()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, k = map(int, readline().split())
a = np.array(list(map(int, readline().split())), np.int64)
a = np.sort(a)
z = a[a == 0]
p = a[a > 0]
m = a[a < 0]


def check(mid):
    cnt = 0
    # 0以上のとき
    if mid >= 0:
        cnt += len(z) * n
    cnt += np.searchsorted(a, mid // p, side='right').sum()
    cnt += (n - np.searchsorted(a, (-mid - 1) // (-m), side='right')).sum()
    cnt -= np.count_nonzero(a * a <= mid)
    return cnt // 2


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

Submission status: Accepted

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

neg_nums = []
pos_nums = []
nums.sort()
for num in nums:
    if num < 0:
        neg_nums.append(num)
    else:
        pos_nums.append(num)
l = -1231232132131232112213
r = 12312321321312312312


def cost_k(m):
    cur_k = 0
    l_pos, r_pos = 0, len(pos_nums) - 1
    while l_pos < r_pos:
        if pos_nums[l_pos] * pos_nums[r_pos] <= m:
            cur_k += r_pos - l_pos
            l_pos += 1
        else:
            r_pos -= 1
    l_neg, r_neg = 0, len(neg_nums) - 1
    while l_neg < r_neg:
        if neg_nums[l_neg] * neg_nums[r_neg] <= m:
            cur_k += r_neg - l_neg
            r_neg -= 1
        else:
            l_neg += 1
    l_pos, l_neg = 0, 0
    while l_pos < len(pos_nums) and l_neg < len(neg_nums):
        if neg_nums[l_neg] * pos_nums[l_pos] <= m:
            cur_k += len(pos_nums) - l_pos
            l_neg += 1
        else:
            l_pos += 1
    return cur_k


while r - l > 1:
    m = (r + l) // 2
    # pos pos
    # neg neg
    # neg pos
    cur_k = cost_k(m)
    if cur_k < k:
        l = m
    else:
        r = m
print(r)