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:
# D - Pairs

import numpy as np

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

n_zero = len(A[A == 0])
A_posi = A[A > 0]
A_nega = A[A < 0]

def n_pairs_less_than_or_equal_to_border(product_border):
    n_pairs = -np.sum(A*A <= product_border) # i==jかつ条件を満たすペアの個数を先に引き、以降重複を許して数える
    n_pairs += n_zero * N * (product_border >= 0)

    n_pairs += np.searchsorted(A, product_border//A_posi, side="right").sum()
    n_pairs += (N - np.searchsorted(A, -(-product_border//A_nega), side="left")).sum()

    # 上記2行は下記と同様の処理だが下記の実装だとTLE
    # for i in range(N):
    #     if A[i] > 0:
    #         n_pairs += np.searchsorted(A, product_border//A[i], side="right")
    #     elif A[i] < 0:
    #         n_pairs += N - np.searchsorted(A, -(-product_border//A[i]), side="left")

    n_pairs //= 2
    return n_pairs


lower = -(10**18)
upper = 10**18

while lower <= upper:
    x = (lower + upper) // 2
    if n_pairs_less_than_or_equal_to_border(x) >= K:
        ans = x
        upper = x - 1
    else:
        lower = x + 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    from bisect import bisect_left, bisect_right

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

    A.sort()

    n = bisect_left(A, 0)
    p = bisect_right(A, 0)

    Negative = np.array(A[:n], dtype = np.int64)
    Positive = np.array(A[p:], dtype = np.int64)

    Number_Negative = len(Negative) * len(Positive)
    Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
    Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

    # print (Number_Negative)
    # print (Negative)
    # print (Number_Positive)
    # print (Positive)
    # print (Number_Zero)

    def Ncount(x): #x以下の数を数える(x < 0)
        tmp = 0
        for a in Negative:
            tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
        # print (x, tmp)
        return tmp

    def Ncount1(x):
        tmp = (len(Positive) - np.searchsorted(Positive, (-x - 1) // (-Negative), side = 'right')).sum() 
        return tmp 

    def Pcount(x): #x以下の数を数える(x > 0)
        tmp = 0
        for index, a in enumerate(Positive):
            tmp += bisect_right(Positive[index + 1:], x // a)
        for index, b in enumerate(Negative):
            tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
            # print (bisect_right(Negative[index + 1:], x / b))
        # print (x, tmp)
        return tmp

    def Pcount1(x):
        tmp = 0
        tmp += np.searchsorted(Positive, x // Positive, side = 'right').sum()
        tmp += (len(Negative) - np.searchsorted(Negative, (-x - 1) // (-Negative), side = 'rigth')).sum()
        tmp -= np.count_nonzero(Positive * Positive <= x)
        tmp -= np.count_nonzero(Negative * Negative <= x)
        return tmp // 2

    if Number_Negative >= K:
        # ここに二分探索を書く
        l = -10 ** 18
        r = 0
        while r - l > 1:
            mid = (l + r) // 2
            if K <= Ncount1(mid):
                r = mid
            else:
                l = mid
        print (r)
        exit()
            

    elif Number_Negative < K <= Number_Negative + Number_Zero:
        print (0)
        exit()

    else:
        # ここに二分探索を書く
        l = 0
        r = 10 ** 18
        K -= (Number_Negative + Number_Zero)
        while r - l > 1:
            mid = (l + r) // 2
            if K <= Pcount1(mid):
                r = mid
            else:
                l = mid

        print (r)
        # exit()

    # print (Pcount(l) + Number_Negative + Number_Zero)
    # print (Pcount(r) + Number_Negative + Number_Zero)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(map(int, args[1].split())))
    N = A[A < 0]
    P = A[0 < A]

    count = 0
    left, right = -10**18, 10**18
    while left+1 < right:
        x = (left+right)//2
        count = (n-np.searchsorted(A, -(-x//N), side='left')).sum()
        count += n * (A == 0).sum() if 0 <= x else 0
        count += np.searchsorted(A, x//P, side='right').sum()
        count -= (A*A <= x).sum()
        count //= 2

        if count < k:
            left = x
        else:
            right = x

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(map(int, args[1].split())))
    N = A[A < 0]
    P = A[0 < A]

    count = 0
    left, right = -10**18, 10**18
    while left+1 < right:
        x = (left+right)//2
        count = 0

        if k <= len(N)*len(P):
            count += (len(P)-np.searchsorted(P, -(-x//N), side='left')).sum()

        elif (n*(n-1) - len(N)*(len(N)-1) - len(P)*(len(P)-1))//2 < k:
            for D in (-(N[::-1]), P):
                count += np.searchsorted(D, x//D, side='right').sum()
                count -= len(D[D*D <= x])
            count //= 2
            count += (n*(n-1) - len(N)*(len(N)-1) - len(P)*(len(P)-1))//2

        else:
            right = 0
            break

        if count < k:
            left = x
        else:
            right = x

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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]
zero = a[a==0]
neg = a[a<0]
negpos = (neg*(-1))[::-1]

lenn = len(neg)
lenz = len(zero)
lenp = len(pos)

nnres = lenn * lenp
nzres = int(lenz*(lenn+lenp)+lenz*(lenz-1)/2)
npres = int(lenn*(lenn-1)/2 + lenp*(lenp-1)/2)

if k<=nnres:
    def count_nnres(x):
        cnt = np.searchsorted(neg,x//pos,side='right').sum()
        return int(cnt)
    left = -10**18
    right = -1
    while left+1<right:
        mid = (left+right)//2
        nebefore = count_nnres(mid)
        if nebefore >= k:
            right = mid
        elif nebefore < k:
            left = mid
    print(right)
    
elif nnres<k<=nnres+nzres:
    print(0)
    
elif nnres+nzres<k:
    def count_npres(x):
        cnt = 0
        cnt += int(np.searchsorted(pos,x//pos,side='right').sum() - ((x//pos)>=pos).sum())//2
        cnt += int(np.searchsorted(negpos,x//negpos,side='right').sum() - ((x//negpos)>=negpos).sum())//2
        return cnt
    k -= nnres+nzres
    left = 1
    right = 10**18
    while left+1<right:
        mid = (left+right)//2
        nebefore = count_npres(mid)
        if nebefore >= k:
            right = mid
        elif nebefore < k:
            left = mid
    print(right)

Submission status: Accepted

Solution code:
import numpy as np
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):
    count = 0
    c = x // pos
    count += np.searchsorted(a, c, side='right').sum()
    count += N*len(zero) if x >= 0 else 0
    c = -(-x // neg)
    count += (N - np.searchsorted(a, c, side='left')).sum()
    count -= a[a*a <= x].size
    count //= 2
    return count

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

Submission status: Accepted

Solution code:
import numpy as np
# in your code
def p(*args, **kargs):
    if DBG:print(*args, **kargs)
read = input 
rn = lambda :list(map(int, read().split()))
debug = False
def sol(A):
    A = np.array(A, np.int64)
    A = np.sort(A)
    _A = np.sort(-A)

    pos = A[A>0]
    neg = A[A<0]
    zero = A[A==0]
    def searchsorted(*args, **kargs):
        ret = np.searchsorted(*args, **kargs)

#         print(args, kargs)
#         print(ret)
        return ret

    # python 保证余数>0，即，整除，向无穷小round。
    # <= x，pairs that <= x
    def  f(x):
        ret = 0
        if x >= 0:
            ret += len(zero) * len(A)
            ret += searchsorted(A, x//pos, side="right").sum()
            ret += searchsorted(_A, x//(-neg), side="right").sum()
        else :
            ret += searchsorted(A, x//pos,  side="right").sum()
            ret += searchsorted(_A, x//(-neg),  side="right").sum()

        ret -= np.count_nonzero(A*A<=x)
        assert ret % 2 == 0
        return ret // 2
        if debug: print(pos, neg, zero)
    return f

f = sol([-4, -2, 3, 3 ])
assert f(-12) == 2
assert f(-6) == 4 # or 3
# 二分搜索
def bs(A, index):
    A = np.array(A, np.int64)
    f = sol(A)
    max_ele = max(abs(A))

    right = max_ele * max_ele + 1
    left  = - right
    while left + 1 < right:
        middle = (left + right)//2
        m_index = f(middle)
        if debug : print(middle, m_index, left, right, sep="\t")
        if index <= m_index:
            right = middle
        else :
            left = middle
    return right

n,index = rn()
A = np.array(read().split(), np.int64)
print(bs(A, index))

Submission status: Accepted

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

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

def f(x):
  tmp = 0
  if x>=0:
    tmp += zero*N
  tmp += np.searchsorted(L, x//pos, side='right').sum()
  tmp += (N - np.searchsorted(L, -(-x//neg), side='left')).sum()
  tmp -= np.count_nonzero(L*L<=x)
  return tmp//2

l, r = -10**18, 10**18
while l<r-1:
  m = (l+r)//2
  count = f(m)
  if count >= K:
    r = m
  else:
    l = m

print(r)

Submission status: Accepted

Solution code:
def d_pairs():
    # 参考: https://maspypy.com/atcoder-参加感想-2019-02-16abc-155
    import numpy as np
    N, K = [int(i) for i in input().split()]
    A = np.array([int(i) for i in input().split()], np.int64)

    A = np.sort(A)
    zero = A[A == 0]
    positive = A[A > 0]
    negative = A[A < 0]

    def f(c):
        """数列 A から 2 要素を選んで積を取ったとき、c 以下となるようなペアの選び方"""
        count_pair = 0

        # a (数列の要素) == 0 かつ c >= 0 なら、a * x <= c となる x は数列の任意の要素
        if c >= 0:
            count_pair += len(zero) * N
        # a > 0 の場合
        count_pair += np.searchsorted(A, c // positive, side='right').sum()
        # a < 0 の場合 (全体から引くようにすると、見通しがよい)
        count_pair += (N - np.searchsorted(A, (-c - 1) // (-negative), side='right')).sum()
        # 添字の順序に制約があることを反映する
        count_pair -= np.count_nonzero(A * A <= c)  # 「添字が同じ要素を 2 度選んだ場合」を引く
        return count_pair // 2

    # 数列から要素を 2 個選んで積を取ったとき、制約からあり得る値の範囲
    lower, upper = -10 ** 18, 10 ** 18
    while upper - lower > 1:
        x = (lower + upper) // 2
        if f(x) >= K:
            upper = x
        else:
            lower = x
    return upper

print(d_pairs())

Submission status: Accepted

Solution code:
import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

A_pos = A[A > 0]
A_neg = A[A < 0]
A_zero = A[A == 0]

# 積がc以下となる組み合わせの数を求める
def n_comb_lt(c):
    n_comb = 0
    # A[i] > 0であるA[i]について
    target = c // A_pos  # target以下の値がA[i]の相方
    n_comb += np.searchsorted(A, target, side="right").sum()

    # A[i] == 0であるA[i]について
    n_comb += n * len(A_zero) if c >= 0 else 0

    # A[i] < 0であるA[i]について
    target = -(-c // A_neg)
    n_comb += (n - np.searchsorted(A, target, side="left")).sum()

    # 組み合わせのうち、A[i]*A[i]となっているものを引いて、2で割る
    n_comb -= A[A * A <= c].size
    n_comb //= 2

    return n_comb

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

# k番目の積は、積がm未満となる組み合わせがk個未満となる最大のm
# ←→積が(m-1)以下となる組み合わせがk個未満となる最大のm
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

A_pos = A[A > 0]
A_neg = A[A < 0]
A_zero = A[A == 0]

# 積がc以下となる組み合わせの数を求める
def n_comb_lt(c):
    n_comb = 0
    # A[i] > 0であるA[i]について
    target = c // A_pos  # target以下の値がA[i]の相方
    n_comb += np.searchsorted(A, target, side="right").sum()

    # A[i] == 0であるA[i]について
    n_comb += n * len(A_zero) if c >= 0 else 0

    # A[i] < 0であるA[i]について
    target = -(-c // A_neg)
    n_comb += (n - np.searchsorted(A, target, side="left")).sum()

    # 組み合わせのうち、A[i]*A[i]となっているものを引いて、2で割る
    n_comb -= A[A * A <= c].size
    n_comb //= 2

    return n_comb

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

# k番目の積は、積がm未満となる組み合わせがk個未満となる最大のm
# ←→積が(m-1)以下となる組み合わせがk個未満となる最大のm
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import numpy as np

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):
    """count the number of products , <= x"""
    cnt_tpl = 0
    # zero and ...
    if x >= 0:
        cnt_tpl += len(zero) * n
    # positive and ...
    cnt_tpl += np.searchsorted(a, x // pos, side='right').sum()
    # negative and ...
    cnt_tpl += (n - np.searchsorted(a, (-x - 1) // (-neg), side='right')).sum()
    # a^2
    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:
    x = (left + right) // 2
    if f(x) >= k:
        right = x
    else:
        left = x

print(right)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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


def main():
    N, K = list(map(int, input().split()))
    A = sorted(list(map(int, input().split())))
    p = bisect_left(A, 0)
    An = A[:p]
    Ap = A[p:]

    if K <= p * (N - p):
        def helper(x):
            t = 0
            r = 0
            for p in Ap:
                while t < len(An) and An[t] * p <= x:
                    t += 1
                r += t
            return r < K
        l = binsearch(Ap[-1] * An[0] - 1, 1, helper)
    else:
        K -= p * (N - p)
        An.reverse()
        def helper(x):
            r = 0
            for a in [Ap, An]:
                t = len(a) - 1
                for i, p in enumerate(a):
                    if t <= i:
                        break
                    while t > i and a[t] * p > x:
                        t -= 1
                    r += t - i
            return r < K 
        m = Ap[-1]
        if An:
            m = max(m, -An[-1])
        l = binsearch(-1, m * m, helper)
    print(l + 1)


main()

Submission status: Accepted

Solution code:
import numpy as np


def main():
    N, K = [int(x) for x in input().split()]
    A = np.array(input().split(), np.int64)
    A = np.sort(A)
    minus = A[A<0]
    zero = A[A==0]
    plus = A[A>0]


    def f(x):
        """number of products <=x
        """
        res = 0
        if x >= 0:
            res += len(zero) * N
        # positive
        res += np.searchsorted(A, x // plus, side="right").sum()

        # negative
        res += (N - np.searchsorted(A, (-x-1) // (-minus), side="right")).sum()

        # remove dup
        res -= np.count_nonzero(A*A <= x)
        res //= 2

        return res

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

    while l+1 < r:
        mid = (l+r)//2
        if f(mid) >= K:
            r = mid
        else:
            l = mid
    print(r)


if __name__ == '__main__':
    main()