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:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, K = getNM()
A = getList()
minus = [-x for x in A if x < 0]
plus = [x for x in A if x >= 0]

minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        x = -x
        r = 0
        # - * +
        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

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


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
def resolve():
    n, k = map(int, input().split())
    a = np.array(input().split(), dtype=np.int64)
    a.sort()
 
    zero = np.count_nonzero(a == 0)
    positive = a[a > 0]
    negative = a[a < 0]
 
    def count(x):  # 積が x 以下のペアは何個あるか？
        ans = 0
        if x >= 0:  # 片側が 0 の場合
            ans += n * zero
        ans += np.searchsorted(a, x // positive, side="right").sum()  # 片側が正の場合
        ans += n * len(negative) - np.searchsorted(a, -(-x // negative), side="left").sum()  # 片側が負の場合 切り上げは -(-a//b)
        ans -= np.count_nonzero(a * a <= x)  # 同じもの2つは選べない
        return ans // 2
 
    ok = 10 ** 18
    ng = -ok - 1
    while ok - ng > 1:  # 二分探索
        cen = (ok + ng) // 2
        if count(cen) >= k:
            ok = cen
        else:
            ng = cen
    print(ok)
 
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    ps = []
    ms = []
    n0 = 0
    for i in ipt().split():
        ii = int(i)
        if ii == 0:
            n0 += 1
        elif ii > 0:
            ps.append(ii)
        else:
            ms.append(-ii)

    pn = len(ps)
    mn = len(ms)
    if k <= pn*mn:
        ps.sort()
        ms.sort(reverse=True)
        l = -10**(18)
        r = -1
        while l < r:
            mid = l + (r-l)//2
            num = 0 #積がmid以下になる個数
            mi = 0
            for i in ps:
                for j in range(mi,mn):
                    if -i*ms[j] > mid:
                        break
                    mi += 1
                num += mi
            if num < k:
                l = mid+1
            else:
                r = mid
        print(l)

    elif k <= pn*mn+n0*(pn+mn)+n0*(n0-1)//2:
        print(0)

    else:
        k -= pn*mn+n0*(pn+mn)+n0*(n0-1)//2
        ps.sort()
        ms.sort()
        l = 1
        r = 10**18
        while l < r:
            mid = l + (r-l)//2
            num = 0 #積がmid以下になる個数
            mi = 0
            pi = 0
            for i,mk in enumerate(ms[::-1]):
                mi = min(mi,mn-i-1)
                for j in range(mi,mn-i-1):
                    if mk*ms[j] > mid:
                        break
                    mi += 1
                num += mi
            for i,pk in enumerate(ps[::-1]):
                pi = min(pi,pn-i-1)
                for j in range(pi,pn-i-1):
                    if pk*ps[j] > mid:
                        break
                    pi += 1
                num += pi
#            print(mid,num,k)
            if num < k:
                l = mid+1
            else:
                r = mid
        print(l)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


@njit('(i8,i8,i4[:],i4[:],i8,i8)', cache=True)
def judge1(tn, K, Ap, Am, Nm, Np):

    count = 0
    for i in range(Nm):
        search = -(-tn // -Am[i])
        j = np.searchsorted(Ap, search, side='left')
        count += Np - j

    return count >= K


@njit('(i8,i8,i4[:],i4[:],i8,i8,i8,i8)', cache=True)
def judge2(tn, K, Ap, Am, Nm, Np, m_count, z_count):

    count = 0
    for i in range(Np):
        search = tn // Ap[i]
        j = np.searchsorted(Ap, search, side='right')
        count += max(0, j - i - 1)

    for i in range(Nm):
        search = tn // Am[i]
        j = np.searchsorted(Am, search, side='right')
        count += max(0, j - i - 1)

    return count >= (K - m_count - z_count)


@njit('(i8,i8,i4[:],i4[:],i8,)', cache=True)
def solve(N, K, Ap, Am, Nz):

    INF = 10**18
    Np = Ap.size
    Nm = Am.size

    m_count = Np * Nm
    z_count = Nz * (Np + Nm) + Nz * (Nz - 1) // 2

    if K <= m_count:

        min_n, max_n = -INF, -1
        while max_n - min_n != 1:
            tn = (min_n + max_n) // 2
            if judge1(tn, K, Ap, Am, Nm, Np):
                max_n = tn
            else:
                min_n = tn

        ans = max_n

    elif K <= m_count + z_count:
        ans = 0

    else:

        min_n, max_n = 1, INF
        while max_n - min_n != 1:
            tn = (min_n + max_n) // 2
            if judge2(tn, K, Ap, Am, Nm, Np, m_count, z_count):
                max_n = tn
            else:
                min_n = tn

        ans = max_n

    return ans


def main():
    N, K = in_nn()
    A = in_nl()
    Ap, Am = [], []
    Nz = 0

    for i in range(N):
        if A[i] > 0:
            Ap.append(A[i])
        elif A[i] == 0:
            Nz += 1
        else:
            Am.append(A[i])

    Ap = np.array(sorted(Ap), np.int32)
    Am = np.array(sorted([-a for a in Am]), np.int32)

    print(solve(N, K, Ap, Am, Nz))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

INF = 10**18


def binary_search(min_n, max_n, judge):

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if judge(tn):
            max_n = tn
        else:
            min_n = tn

    return max_n


def main():
    N, K = in_nn()
    A = in_nl()

    Ap = []
    Am = []
    Nz = 0

    for i in range(N):
        if A[i] > 0:
            Ap.append(A[i])
        elif A[i] == 0:
            Nz += 1
        else:
            Am.append(A[i])

    Np = len(Ap)
    Nm = len(Am)

    m_count = Np * Nm
    z_count = Nz * (Np + Nm) + Nz * (Nz - 1) // 2
    # p_count = Np * (Np - 1) // 2 + Nm * (Nm - 1) // 2

    if K <= m_count:

        Ap.sort()
        Am.sort()

        def judge(tn):

            count = 0
            for i in range(Nm):
                search = -(-tn // Am[i])
                j = bisect.bisect_left(Ap, search)
                count += Np - j

            return count >= K

        ans = binary_search(-INF, -1, judge)

    elif K <= m_count + z_count:
        ans = 0
    else:

        Ap.sort()
        Am = sorted([-a for a in Am])

        def judge(tn):

            count = 0
            for i in range(Np):
                search = tn // Ap[i]
                j = bisect.bisect_right(Ap, search)
                count += max(0, j - i - 1)

            for i in range(Nm):
                search = tn // Am[i]
                j = bisect.bisect_right(Am, search)
                count += max(0, j - i - 1)

            return count >= (K - m_count - z_count)

        ans = binary_search(1, INF, judge)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

n,k=map(int,input().split())
A=np.array(input().split(),np.int64)
A.sort()

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

def f(x): # count pairs x or less
    cnt=0
    #zero
    if x>=0:
        cnt += len(zero)*n
    #pos
    cnt += A.searchsorted(x//pos,side="right").sum()
    #neg
    cnt += (n-A.searchsorted(-(-x//neg),side="left")).sum()
    #except a*a
    cnt-=np.count_nonzero(A*A<=x)
    return cnt//2

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

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

Submission status: Accepted

Solution code:

from bisect import bisect_left, bisect_right
def resolve():
    def judge_m(mid):
        tot = 0
        for i in range(p_n):
            d = mid//P[i]
            tot += bisect_right(M, d)
        return tot >= K


    def judge_p(mid):
        tot = 0
        for i in range(p_n): # 正と正の積
            d = mid//P[i]
            tmp = bisect_right(P, d)
            if i < tmp:
                tmp -= 1 # 自身を除く
            tot += tmp
        for i in range(m_n): # 負と負の積
            d = mid//M[i]
            tmp = bisect_right(M, d)
            if i < tmp:
                tmp -= 1 # 自身を除く
            tot += tmp
        tot //= 2
        return tot >= K


    INF = 10 ** 18 + 1
    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))

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

    p_n = len(P)
    m_n = len(M)
    z_n = len(Z)
    minus = p_n * m_n
    zero = z_n*(z_n-1)//2 + z_n*p_n + z_n*m_n
    plus = p_n*(p_n - 1)//2 + m_n*(m_n-1)//2

    if K <= minus: # X が負の時
        M.sort()
        l, u = -INF, 0
        while u - l > 1:
            mid = (u+l)//2
            if judge_m(mid):
                u = mid
            else:
                l = mid
        return print(u)
    elif K <= (minus + zero):
        return print(0)
    elif K <= (minus + zero + plus):
        K -= (minus + zero)
        M = [abs(m) for m in M]
        P.sort()
        M.sort()
        l, u = -1, INF
        while u - l > 1:
            mid = (u + l)//2
            if judge_p(mid):
                u = mid
            else:
                l = mid
        return print(u)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

def resolve():
    def counts(x):
        ans = 0
        if x < 0:
            x = -x
            r = 0
            for mi in minus[::-1]:
                while r < len(plus) and plus[r] * mi < x:
                    r += 1
                ans += len(plus) - r
            return ans

        r = 0
        for l in minus[::-1]:
            if l * l <= x: ans -= 1
            while r < len(minus) and minus[r] * l <= x:
                r += 1
            ans += r
        r = 0
        for l in plus[::-1]:
            if l * l <= x: ans -= 1
            while r < len(plus) and plus[r] * l <= x:
                r += 1
            ans += r

        ans //= 2
        ans += len(minus) * len(plus)
        return ans

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

    minus.sort()
    plus.sort()

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

    print(high)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

import numpy as np
def resolve():
    n, k = map(int, input().split())
    a = np.array(input().split(), dtype=np.int64)
    a.sort()

    zero = np.count_nonzero(a == 0)
    positive = a[a > 0]
    negative = a[a < 0]

    def count(x):  # 積が x 以下のペアは何個あるか？
        ans = 0
        if x >= 0:  # 片側が 0 の場合
            ans += n * zero
        ans += np.searchsorted(a, x // positive, side="right").sum()  # 片側が正の場合
        ans += n * len(negative) - np.searchsorted(a, -(-x // negative), side="left").sum()  # 片側が負の場合 切り上げは -(-a//b)
        ans -= np.count_nonzero(a * a <= x)  # 同じもの2つは選べない
        return ans // 2

    ok = 10 ** 18
    ng = -ok - 1
    while ok - ng > 1:  # 二分探索
        cen = (ok + ng) // 2
        if count(cen) >= k:
            ok = cen
        else:
            ng = cen
    print(ok)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def comb(li):
    return len(li) * (len(li) - 1) // 2


def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n * (n - 1) // 2 - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()

    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg) + count_large(m, pos)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)


# k-th is 0
else:
    print(0)

Submission status: Accepted

Solution code:
# 親の顔より見たPairs
# 小さい順に見てk番目
# x以下の数がk個以上となる最小のxを求める
# x以下の数がk個以上かつx−1以下の数はk個未満
from bisect import bisect_left, bisect_right

import sys

input = sys.stdin.buffer.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

minus_num = bisect_left(A, 0)
zero_num = bisect_right(A, 0) - minus_num
plus_num = n - (minus_num + zero_num)

seki_minus = plus_num * minus_num
seki_plus = plus_num * (plus_num - 1) // 2 + minus_num * (minus_num - 1) // 2
seki_zero = zero_num * (plus_num + minus_num) + zero_num * (zero_num - 1) // 2
assert seki_minus + seki_plus + seki_zero == n * (n - 1) // 2

mA = A[:minus_num]
pA = A[-plus_num:]


# ある数以下のものが何個有るかを返す関数
def calc(num):
    res = 0
    if num < 0:
        lim = minus_num - 1
        mmA = mA[::-1]
        for i in range(plus_num):
            while lim >= 0:
                if mmA[lim] * pA[i] <= num:
                    lim -= 1
                else:
                    break
            res += minus_num - (lim + 1)
    elif num == 0:
        res = seki_zero + seki_minus
    else:
        # pA
        lim = plus_num - 1
        for i in range(plus_num):
            while lim >= 0:
                if pA[lim] * pA[i] > num:
                    lim -= 1
                else:
                    break
            if lim >= i:
                res -= 1
            res += lim + 1
        # mA
        lim = minus_num - 1
        mmA = mA[::-1]
        for i in range(minus_num):
            while lim >= 0:
                if mmA[lim] * mmA[i] > num:
                    lim -= 1
                else:
                    break
            if lim >= i:
                res -= 1
            res += lim + 1
        assert res % 2 == 0
        res //= 2
        res += seki_minus
        res += seki_zero
    return res


ok = 10 ** 20
ng = -(10 ** 20)

while ok - ng > 1:
    mid = (ok + ng) // 2
    if calc(mid) >= k:
        ok = mid
    else:
        ng = mid
    # print(ok, ng)


print(ok)

Submission status: Accepted

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A)
ok, ng = 10**18, -10**18

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    ### ここから判定ロジック ###
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s, t = 0, 0
    for i in range(N):
        if A[i] > 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= mid:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= mid:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        elif mid >= 0:
            s += N
        if A[i] * A[i] <= mid:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) // 2
    judge = total >= K
    ### ここまで判定ロジック ###
    # それがK個以上あるかを判定する
    if judge:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A)
ok, ng = 10**18, -10**18

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    t = 0
    for i in range(N):
        if A[i] > 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= mid:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        elif A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= mid:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
        elif mid >= 0:
            s += N
        if A[i] * A[i] <= mid:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) // 2
    # それがK個以上あるかを判定する
    if total >= K:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
# https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-02-16abc-155
import numpy as np

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
A.sort()
G = A[A > 0]
Z = A[A == 0]
L = A[A < 0]

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

# x以下がK個以上であるxの最小値

while ok - ng > 1:
    mid = (ng + ok) // 2
    # mid以下のペアの個数を数える

    # 正のもののうち、mid以下のペアの個数を数える
    cg = np.searchsorted(A, mid // G, side="right").sum()

    # 負のもののうちmid以下のペアの個数を数える
    cl = (N - np.searchsorted(A, (mid + 1) // L, side="right")).sum()

    # 同じ数字同士の積がmid以下のものを数える
    d = np.count_nonzero(A * A <= mid)

    # 0がmid以下なら、それもプラスするために必要
    z = 0
    if mid >= 0:
        z += len(Z) * N

    c = cg + cl + z - d

    # 二重になっているので、割る
    c //= 2

    # mid以下のペアの個数がK個以上のとき
    if c >= K:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
# https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-02-16abc-155
import numpy as np

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
A.sort()
G = A[A > 0]
Z = A[A == 0]
L = A[A < 0]

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

# x以下がK個以上であるxの最小値

while ok - ng > 1:
    mid = (ng + ok) // 2
    # mid以下のペアの個数を数える

    # 正のもののうち、mid以下のペアの個数を数える
    cg = np.searchsorted(A, mid // G, side="right").sum()

    # 負のもののうちmid以下のペアの個数を数える
    cl = (N - np.searchsorted(A, (-mid - 1) // (-L), side="right")).sum()

    # 同じ数字同士の積がmid以下のものを数える
    d = np.count_nonzero(A * A <= mid)

    # 0がmid以下なら、それもプラスするために必要
    z = 0
    if mid >= 0:
        z += len(Z) * N

    c = cg + cl + z - d

    # 二重になっているので、割る
    c //= 2

    # mid以下のペアの個数がK個以上のとき
    if c >= K:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from math import ceil

def main():
    n,k = map(int, input().split())
    al = list(map(int, input().split()))
    al.sort()

    al_n = []
    al_p = []
    al_n_p = []
    zero_cnt = 0
    for a in al:
        if a < 0: 
            al_n.append(a)
            al_n_p.append(-1*a)
        elif a > 0: 
            al_p.append(a)
        else: 
            zero_cnt += 1
    al_n_p = al_n_p[::-1]

    n_cnt = len(al_n)
    p_cnt = len(al_p)

    m_n_cnt = n_cnt*p_cnt
    m_p_cnt = n_cnt*(n_cnt-1)//2 + p_cnt*(p_cnt-1)//2
    m_zero_cnt = zero_cnt*(n_cnt+p_cnt) + zero_cnt*(zero_cnt-1)//2


    if k <= m_n_cnt:
        left = (-1)*(10**18)
        right = -1
        while right-left>1:
            curr_num = left + (right-left)//2
            curr_cnt = 0
            num_exist = False
            for an in al_n:
                targt_p = abs(curr_num)//abs(an)
                p_ind = bisect_right(al_p,targt_p)
                ok_p_cnt = len(al_p) - p_ind
                curr_cnt += ok_p_cnt
                if p_ind > 0 and al_p[p_ind-1]*an == curr_num:
                    num_exist = True
            
            if curr_cnt > k-1:
                right = curr_num
            elif curr_cnt < k-1:
                left = curr_num
            else:
                if num_exist:
                    print(curr_num)
                    exit()
                else:
                    left = curr_num


    elif m_n_cnt < k <= m_n_cnt+m_zero_cnt:
        print(0)
        exit()

    else:
        k = k - m_n_cnt - m_zero_cnt # 1-index
        right = (10**18)
        left = 0
        while right-left > 1:
            cnt = k
            # print(f'k:{k}')
            # print('----')
            curr_num = left + (right-left)//2
            curr_cnt = 0
            num_exist = False
            # curr_num = 6
            # print(curr_num, left, right)
            for i, an in enumerate(al_n_p):
                targt_p = abs(curr_num)//abs(an)
                ok_p_cnt = max(bisect_right(al_n_p,targt_p)-i-1, 0)
                cnt -= ok_p_cnt
            
            for i, an in enumerate(al_p):
                # print(f'----- {an} -----')
                targt_p = abs(curr_num)//abs(an)
                
                ok_p_cnt = max(bisect_right(al_p,targt_p)-i-1, 0)
                cnt -= ok_p_cnt
                # print(ok_p_cnt)

            if cnt > 0:
                left = curr_num
            else:
                right = curr_num

        print(right)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 小さい方からk番目がx
# x以下がk個以上となる最小のx
# 負の数のところでバグってそう
from bisect import bisect_left, bisect_right

import sys

input = sys.stdin.buffer.readline

n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
minusA = bisect_left(A, 0)
mA = A[:minusA]

zeroA = bisect_right(A, 0) - bisect_left(A, 0)
plusA = n - minusA - zeroA
pA = A[-plusA:]
minus = minusA * plusA
plus = plusA * (plusA - 1) // 2 + minusA * (minusA - 1) // 2
zero = zeroA * (zeroA - 1) // 2 + (n - zeroA) * zeroA


# x以下の数を数える
def calc(x):
    mmA = mA[::-1]
    res = 0
    if x > 0:
        lim = plusA - 1
        for i in range(plusA):
            while lim >= 0:
                if pA[i] * pA[lim] > x:
                    lim -= 1
                else:
                    break
            res += lim + 1
            if lim >= i:
                res -= 1
        lim = minusA - 1
        mmA = mA[::-1]
        for i in range(minusA):
            while lim >= 0:
                if mmA[i] * mmA[lim] > x:
                    lim -= 1
                else:
                    break
            res += lim + 1
            if lim >= i:
                res -= 1
        res //= 2
        res += minus + zero
    elif x == 0:
        res += minus + zero
    else:
        # 正の数、左絶対値小さい
        # 負の数、左絶対値大きい
        lim = minusA - 1
        for i in range(plusA):
            while lim >= 0:
                if pA[i] * mmA[lim] <= x:
                    lim -= 1
                else:
                    break
            res += minusA - (lim + 1)
    return res


ng = -(10 ** 20)
ok = 10 ** 20
while ok - ng > 1:
    mid = (ok + ng) // 2
    if calc(mid) >= k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    M, P = [], [0]
    Z = 0
    for a in A:
        if a < 0: M.append(a)
        elif a == 0: Z += 1
        else: P.append(a)
    M.sort(reverse = True)
    mL, pL = len(M), len(P)

    minusT = mL * pL
    zeroT = Z * (mL + pL)

    if K <= minusT: #K番目の数が負の値
        P.sort(reverse = True)
        low, high = - 10 ** 18 - 1, 0
        while high - low > 1:
            mid = (low + high) // 2
            pi = 0
            count = 0
            for i in range(mL):
                while M[i] * P[pi] <= mid: pi += 1
                count += pi
            #print(mid, count)
            if count >= K: high = mid
            else: low = mid
        print(high)

    elif K <= minusT + zeroT: #K番目の数が0
        print(0)

    else: #正の数の内、K番目の数は何か
        M.append(0)
        P.sort()
        T = N * (N - 1) // 2
        low, high = 0, 10 ** 18 + 1
        while high - low > 1:
            mid = (high + low) // 2
            count = 0
            pi = pL - 1
            for i in range(pL):
                while P[i] * P[pi] >= mid:
                    pi -= 1
                count += pL - 1 - max(i, pi)
               
            mi = mL - 1
            for i in range(mL):
                while M[i] * M[mi] >= mid:
                    mi -= 1
                count += mL - 1 - max(i, mi)

            #midよりも大きい数字がcount個ある
  
            if T - count >= K: high = mid
            else: low = mid
        print(low)
   
    return 0

if __name__ == "__main__":
    solve()