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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def nC2(n):
    return n * (n-1) // 2

n,k = get_nums_l()
aaa = get_nums_l()

negatives = []
zeros = 0
positives = []

for a in aaa:
    if a == 0:
        zeros += 1
    elif a > 0:
        positives.append(a)
    else:
        negatives.append(a)

# 絶対値小さい順
positives.sort()
negatives.sort(reverse=True)

len_positives = len(positives)
len_negatives = len(negatives)

# 要素の個数から、ペアの積を負,0,正に分けた場合の個数を数える
p_zeros = zeros*(len_negatives+len_positives) + nC2(zeros)
p_positives = nC2(len_positives) + nC2(len_negatives)
p_negatives = len_positives * len_negatives

if p_negatives < k <= (p_negatives+p_zeros):
    # ゼロの場合
    print(0)
    exit()

if k <= p_negatives:
    # 負の場合
    nokori = k

    left = -1 * ((10**9)**2 + 1)
    right = -1

    # 積がcenter未満になるペアがnokori個未満になる最大のcenterを探す
    while left < right:
        center = (left+right+1) // 2

        left2 = len_positives-1
        right2 = len_negatives-1

        count = 0

        # 正の数と負の数を掛けてcenter未満になる個数を数える
        while right2 > 0 and positives[left2] * negatives[right2] < center:
            right2 -= 1

        while 0<=left2<len_positives and 0<=right2<len_negatives:
            if positives[left2] * negatives[right2] < center:
                count += len_negatives - right2
                left2 -= 1
            else:
                right2 += 1

        if count < nokori:
            left = center
        else:
            right = center - 1
    print(left)
    exit()

# 正の場合
nokori = k - p_negatives - p_zeros

left = 1
right = (10**9)**2 + 1

# 積がcenter未満になるペアがnokori個未満になる最大のcenterを探す
while left < right:
    center = (left+right+1) // 2

    left2 = 0
    right2 = len_positives-1

    count = 0

    # 正の数同士で掛けてcenter未満になる個数を数える
    while left2 < right2:
        if positives[left2] * positives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    left2 = 0
    right2 = len_negatives-1

    # 負の数同士で掛けてcenter未満になる個数を数える
    while left2 < right2:
        if negatives[left2] * negatives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    if count < nokori:
        left = center
    else:
        right = center-1
print(left)

Submission status: Accepted

Solution code:

import numpy as np


# 解がマイナスのとき
def solve1(k, ml, pl):
    left, right = -(10 ** 18) - 1, 0
    while right - left > 1:
        x = (left + right) // 2
        n = (len(pl) - np.searchsorted(pl, x // ml + (x % ml != 0))).sum()
        if k <= n:
            right = x
        else:
            left = x
    return right


# 解がプラスのとき
def solve2(k, ml, pl):
    left, right = 0, 10 ** 18
    while right - left > 1:
        x = (left + right) // 2
        n = 0
        n += (len(ml) - np.searchsorted(ml, x // ml + (x % ml != 0))).sum()
        n -= np.count_nonzero(ml ** 2 <= x)
        n += (np.searchsorted(pl, x // pl, side="right")).sum()
        n -= np.count_nonzero(pl ** 2 <= x)
        assert n % 2 == 0
        n //= 2
        if k <= n:
            right = x
        else:
            left = x
    return right


def main():
    N, K = list(map(int, input().split()))
    A = np.array(input().split(), dtype=int)
    A.sort()
    ml = A[A < 0]
    pl = A[A > 0]
    zl = A[A == 0]
    mn = len(ml) * len(pl)
    zn = sum([N - i - 1 for i in range(len(zl))])
    if K <= mn:
        ans = solve1(K, ml, pl)
    elif K <= mn + zn:
        ans = 0
    else:
        ans = solve2(K - mn - zn, ml, pl)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://note.com/tanon_cp/n/ne423915acdaa
from bisect import bisect

INF = 10 ** 18

def check_neg(m, k, pos, neg):
    len_pos = len(pos)
    less = 0  # かけたら m 未満になるペア数
    j = 0
    for a in neg:
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if len_pos == j:
            break
        less += len_pos - j
    return less < k

def check_pos(m, k, pos, neg):
    less_eq = 0  # かけたら m 以下になるペア数
    j = 0
    len_pos = len(pos)
    len_neg = len(neg)
    for i in range(len_pos - 1, -1, -1):
        a = pos[i]
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if j == len_pos:
            less_eq += len_pos * (i + 1)
            break
        less_eq += j

    j = 0
    for i in range(len_neg - 1, -1, -1):
        a = neg[i]
        d = m // a
        while j < len_neg and neg[j] <= d:
            j += 1
        if j == len_neg:
            less_eq += len_neg * (i + 1)
            break
        less_eq += j

    m_sqrt = int(m ** 0.5)
    less_eq -= bisect(pos, m_sqrt)
    less_eq -= bisect(neg, m_sqrt)
    less_eq //= 2
    return less_eq < k


def solve(n, k, A):
    pos = []
    neg = []
    zeros = []
    for a in A:
        if a == 0:
            zeros.append(a)
        elif a > 0:
            pos.append(a)
        else:
            neg.append(a)

    pos = [a for a in A if a > 0]
    neg = [a for a in A if a < 0]
    num_neg = len(neg) * len(pos)
    num_zero = (len(neg) + len(pos)) * len(zeros) + len(zeros) * (len(zeros) - 1) // 2
    if k <= num_neg:
        l = -INF
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg):
                l = m
            else:
                r = m
        return l
    elif num_neg < k <= num_neg + num_zero:
        return 0
    else:
        k -= (num_neg + num_zero)
        l = 0
        r = INF
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg):
                l = m
            else:
                r = m
        return r


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

Submission status: Accepted

Solution code:
import numpy as np


def count_pair(x):
    # A内のペアで積がxより小さいものの個数
    # まず(i,j)と(j,i)を重複して数える
    cnt = 0
    # A[i]<0なる各iに対してA[j]>x/A[i]なるjの個数
    cnt += (N-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        # 各iに対してA[j]=0なるjの個数
        cnt += len(A_zero)*N
    # A[i]>0なる各iに対してA[j]<x/A[i]なるjの個数
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    # i=jを除いてから2で割る
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt


# count_pair(x)<Kをみたすxの最大値を二分探索で求める
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:
# TLE

import numpy as np
import sys
input = sys.stdin.readline


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

    zero_left = np.searchsorted(A, 0, side='left')
    zero_right = np.searchsorted(A, 0, side='right')

    negative = zero_left
    positive = N - zero_right
    zero = zero_right - zero_left
    non_posi = negative * positive + zero * (N - zero) + zero * (zero - 1) // 2

    if K <= negative * positive:
        Nega = A[A < 0]
        Posi = A[A > 0]

        left = -(10**18)
        right = 0
        while right - left > 1:
            x = (left + right) // 2
            count = np.searchsorted(Nega, x // Posi, side='right').sum()

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

        print(right)

    elif K <= non_posi:
        print(0)

    else:
        Nega = np.sort(np.abs(A[A < 0]))
        Posi = A[A > 0]

        left = 0
        right = 10**18
        while right - left > 1:
            x = (left + right) // 2
            n = np.searchsorted(Nega, x // Nega, side='right')
            p = np.searchsorted(Posi, x // Posi, side='right')
            count = 0
            count += n.sum()
            count += p.sum()
            count -= np.int_(np.where(n >= np.arange(1,negative+1), True, False)).sum()
            count -= np.int_(np.where(p >= np.arange(1,positive+1), True, False)).sum()
            count //= 2

            if count + non_posi < K:
                left = x
            else:
                right = x

        print(right)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


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

    negative = A[A < 0]
    positive = A[A > 0]
    ln = len(negative)
    lp = len(positive)
    zero = np.count_nonzero(A == 0)

    def count(x):
        count = 0
        if x >= 0:
            count += N * zero
        count += np.searchsorted(A, x // positive, side='right').sum()
        count += N * ln - np.searchsorted(A, -(-x // negative), side='left').sum()
        count -= np.count_nonzero(A * A <= x)
        count //= 2

        return count


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

    print(right)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline

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:
import sys
input = sys.stdin.readline
import numpy as np

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

A_m = np.array(sorted([abs(int(x)) for x in A if x < 0]), np.int64)
N_m = len(A_m)

A_p = np.array(sorted([int(x) for x in A if x > 0]), np.int64)
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = np.searchsorted(A_m, x // A_p, side="right").sum()
    return cnt >= M - K + 1

if K <= M:
    left = -1 -10 ** 18
    right = 1 + 10 ** 18
    while right - left> 1:
        mid = (left + right) // 2
        if cnt_M(mid):
            right = mid
        else:
            left = mid
 
    print(-right)
    sys.exit()

K -= (M + Z)
def cnt_P(x):
    cnt = 0
    ng = 0
    cnt += np.searchsorted(A_m, x // A_m, side="right").sum()
    cnt += np.searchsorted(A_p, x // A_p, side="right").sum()
    ng = np.count_nonzero(A_m * A_m <= x) + np.count_nonzero(A_p * A_p <= x)
    cnt = (cnt - ng) // 2
    return cnt >= K

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

while right - left > 1:
    mid = (left + right) // 2
    if cnt_P(mid):
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A_minus,A_zero,A_plus=[],[],[]
    x=bisect_left(A,0)
    y=bisect_right(A,0)
    A_minus=A[:x]
    A_minus=list(reversed(list(map(lambda x: -x,A_minus))))
    A_zero=A[x:y]
    A_plus=A[y:]
    if K<=len(A_minus)*len(A_plus):
        def nibutan1(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve1(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve1(mid):
            c=0
            z=bisect_left(A_plus,-(-mid//A_minus[0]))
            c+=len(A_plus)-z
            for x in A_minus[1:]:
                if z>0 and A_plus[z-1] >= -(-mid//x):
                    while z>0 and A_plus[z-1] >= -(-mid//x):
                        z-=1
                c+=len(A_plus)-z
            if c>=K:
                return True
            else:
                return False
        
        print(-nibutan1(0,10**18+1))
    K-=len(A_minus)*len(A_plus)
    if 0<K<=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2:
        print(0)
    K-=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2
    if K>0:
        def nibutan2(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve2(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve2(mid):
            c=0
            if len(A_minus)>1:
                z=bisect_right(A_minus,mid//A_minus[0])
                c+=z
                if mid//A_minus[0]>=A_minus[0]:
                    c-=1
                for x in A_minus[1:]:
                    if z>0 and A_minus[z-1] > mid//x:
                        while z>0 and A_minus[z-1] > mid//x:
                            z-=1
                    c+=z
                    if mid//x>=x:
                        c-=1
            if len(A_plus)>1:
                z=bisect_right(A_plus,(mid//A_plus[0]))
                c+=z
                if (mid//A_plus[0])>=A_plus[0]:
                    c-=1
                for x in A_plus[1:]:
                    if z>0 and A_plus[z-1] > mid//x:
                        while z>0 and A_plus[z-1] > mid//x:
                            z-=1
                    c+=z
                    if mid//x>=x:
                        c-=1
            c//=2
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan2(10**18+1,0))

    
        
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.array([int(i) for i in input().split()])
A.sort()

A_max = max(np.abs(A))
A_minus = A[A<0]
A_zero = A[A==0]
A_plus = A[A>0]

def check(x):
    ret = 0
    if x >= 0:
        ret += N * len(A_zero)
    ret += np.searchsorted(A, x // A_plus, side='right').sum()
    ret += (N - np.searchsorted(A, -(x // -A_minus))).sum()
    ret -= np.count_nonzero(A * A <= x)
    return ret // 2

right = A_max * A_max
left = -right - 1
while (right - left > 1):
    middle = (right + left) >> 1
    if check(middle) < K:
        left = middle
    else:
        right = middle
print(right)

Submission status: Accepted

Solution code:
import numpy as np
import sys
 
n,k=map(int,sys.stdin.readline().split())
a=np.array(list(map(int, input().split())))
 
a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]
 
def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2
 
 
left=-10**18
right=10**18
 
while left+1<right:
    x=(left+right)//2
    out=count(x)
    if out>=k:
        right=x
    if out<k:
        left=x
print(right)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#import sys; sys.stdin=open('input_file.txt')
#------------------------------------------
import numpy as np

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

A = np.sort(A)

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

hi = 10**18+1
lo = -10**18-1

while hi-lo > 1:
    mid = (hi+lo)//2
    under_mid = 0

    if mid > 0: under_mid += N*zero
    under_mid += np.searchsorted(A,-(-mid//pos),side='left').sum()
    under_mid += (N-np.searchsorted(A,mid//neg,side='right')).sum()
    under_mid -= np.count_nonzero(A*A < mid)
    under_mid //= 2

    if under_mid < K:
        lo = mid
    else:
        hi = mid

print(lo)

Submission status: Accepted

Solution code:
import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.read().split(),dtype=np.int64)

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

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


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

while left+1<right:
    x=(left+right)//2
    out=count(x)
    if out>=k:
        right=x
    if out<k:
        left=x

print(right)

Submission status: Accepted

Solution code:
import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.readline().split(),dtype=np.int64)

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

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


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

while left+1<right:
    x=(left+right)//2
    out=count(x)
    if out>=k:
        right=x
    if out<k:
        left=x

print(right)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(x):
    cnt = 0
    if x < 0:
        j = p-1
        for i in range(m)[::-1]:
            while j >= 0 and plus[j]*minus[i] <= x:
                j -= 1
            cnt += p - j - 1
    else:
        j = 0
        for i in range(m)[::-1]:
            while j < m and minus[j]*minus[i] > x:
                j += 1
            cnt += max(0,i-j)
        j = p-1
        for i in range(p):
            while j >= 0 and plus[j]*plus[i] > x:
                j -= 1
            cnt += max(0,j-i)
        cnt += zero*(zero-1)//2 + m*p + zero*(m+p)
    
    return cnt >= k

n,k = LI()
a = LI()
a.sort()
minus = [x for x in a if x < 0]
plus = [x for x in a if x > 0]
m,p = len(minus),len(plus)
zero = bl(a,1) - br(a,-1)
ok,ng = 10**18,-10**18-1

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N,K = map(int, input().split())
A = np.array([int(i) for i in input().split()], np.int64)

INF = 10**18 + 1

A = np.sort(A)
# []内の条件文を満たす値の配列
zero = A[A == 0]
pos = A[A > 0]
neg = A[A < 0]

# 積がX以下となる個数がK未満 -> True
def is_under_K(X:int):
    cnt = 0

    # A[i] == 0
    if X >= 0:
        cnt += len(zero) * N
    
    # A[i] > 0
    tmp = X // pos
    cnt += np.searchsorted(A, tmp, "right").sum()

    # A[i] < 0
    tmp = (-X-1) // (-neg)
    cnt += (N - np.searchsorted(A, tmp, "right")).sum()

    # A[i] * A[i] <= X
    cnt -= np.count_nonzero(A * A <= X)

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

def main():
    # 二分探索 O(log(INF))
    ok, ng = -INF, INF
    while ng - ok > 1:
        mid = (ng + ok) // 2
        if is_under_K(mid):
            ok = mid
        else:
            ng = mid

    """
    is_under_K(X) = Flaseとなる最小値X
    -> X = ng
    """
    print(ng)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from subprocess import*
call(("pypy3","-c","""
def main():
  from bisect import bisect
  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:
      i=n
      for y in a:
        while i and a[i-1]*y>x:i-=1   
        s+=i
        if y*y<=x:s-=1
      i=m
      for y in b:
        while i and b[i-1]*y>x:i-=1
        s+=i
        if y*y<=x:s-=1
      s=s//2+n*m
    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:
def main():
  from bisect import bisect
  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:
from bisect import*
def solve(x):
  s=t=0
  i=n
  j=-1
  for y in a:
    while i and a[i-1]*y>x:i-=1
    while j+1<m and b[j+1]*y<=x:j+=1
    s+=j+1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  t=0
  i=m
  for y in c:
    while i and c[i-1]*y>x:i-=1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  return s
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bisect(t,0)
a,b,c=t[i:],t[:i],t[i-1::-1]
n,m=len(a),len(b)
ok=10**18
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if solve(mid)>=k:ok=mid
  else:ng=mid
print(ok)

Submission status: Accepted

Solution code:
from numpy import int64, searchsorted, count_nonzero

N, K, *A = map(int, open(0).read().split())
A = int64(A)

A.sort()

Minus, Zero, Plus = A[A < 0], A[A == 0], A[0 < A]

def is_ok(md):
    cnt = 0 if md < 0 else len(Zero) * N

    cnt += searchsorted(A, md // Plus, side='right').sum()
    cnt += (N - searchsorted(A, (-md - 1) // (-Minus), side='right')).sum()
    cnt -= count_nonzero(A * A <= md)

    return (cnt // 2 >= K)


ng, ok = -10 ** 18, 10 ** 18
while ok - ng > 1:
    md = (ok + ng) // 2
    if is_ok(md):
        ok = md
    else:
        ng = md

print(ok)

Submission status: Accepted

Solution code:
import sys

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def nC2(n):
    return n * (n-1) // 2

n,k = get_nums_l()
aaa = get_nums_l()

negatives = []
zeros = 0
positives = []

for a in aaa:
    if a == 0:
        zeros += 1
    elif a > 0:
        positives.append(a)
    else:
        negatives.append(a)

# 絶対値小さい順
positives.sort()
negatives.sort(reverse=True)

len_positives = len(positives)
len_negatives = len(negatives)

# 要素の個数から、ペアの積を負,0,正に分けた場合の個数を数える
p_zeros = zeros*(len_negatives+len_positives) + nC2(zeros)
p_positives = nC2(len_positives) + nC2(len_negatives)
p_negatives = len_positives * len_negatives

if p_negatives < k <= (p_negatives+p_zeros):
    # ゼロの場合
    print(0)
    exit()

if k <= p_negatives:
    # 負の場合
    nokori = k

    left = -1 * ((10**9)**2 + 1)
    right = -1

    # 積がcenter未満になるペアがnokori個未満になる最大のcenterを探す
    while left < right:
        center = (left+right+1) // 2

        left2 = len_positives-1
        right2 = len_negatives-1

        count = 0

        # 正の数と負の数を掛けてcenter未満になる個数を数える
        while right2 > 0 and positives[left2] * negatives[right2] < center:
            right2 -= 1

        while 0<=left2<len_positives and 0<=right2<len_negatives:
            if positives[left2] * negatives[right2] < center:
                count += len_negatives - right2
                left2 -= 1
            else:
                right2 += 1

        if count < nokori:
            left = center
        else:
            right = center - 1
    print(left)
    exit()

# 正の場合
nokori = k - p_negatives - p_zeros

left = 1
right = (10**9)**2 + 1

# 積がcenter未満になるペアがnokori個未満になる最大のcenterを探す
while left < right:
    center = (left+right+1) // 2

    left2 = 0
    right2 = len_positives-1

    count = 0

    # 正の数同士で掛けてcenter未満になる個数を数える
    while left2 < right2:
        if positives[left2] * positives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    left2 = 0
    right2 = len_negatives-1

    # 負の数同士で掛けてcenter未満になる個数を数える
    while left2 < right2:
        if negatives[left2] * negatives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    if count < nokori:
        left = center
    else:
        right = center-1
print(left)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from bisect import bisect_left


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

    A.sort()

    # 負数、 0数、 正数
    Ns = 0
    Zs = bisect_left(A, 0)
    Ps = bisect_left(A, 1)

    # print(Ns, Zs, Ps)
    lneg = Zs-Ns
    lzer = Ps-Zs
    lpos = N-Ps
    # print(lneg, lzer, lpos)

    prod_neg = lneg * lpos
    prod_zero = lzer * (lneg+lpos)+lzer*(lzer-1)//2
    # prod_pos = lneg*(lneg-1)//2 + lpos*(lpos-1)//2
    # print(prod_neg, prod_zero, prod_pos)

    if prod_neg >= K:
        # 二分探索
        left = A[0]*A[-1]
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            # しゃくとり法
            counter = 0
            ps = Ps
            for ns in range(Ns, Zs):
                while ps < N and A[ns]*A[ps] > mid-1:
                    ps += 1
                if ps == N:
                    break
                counter += N-ps
                # print("add: ", N-ps)
            # print("{} in [{}, {}] ==> {}".format(mid, left, right, counter))
            if counter < K:
                left = mid
            else:
                right = mid
        print(left)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        KK = K-prod_neg-prod_zero
        # 二分探索
        left = 0
        right = max(A[0]**2, A[-1]**2)
        while right - left > 1:
            mid = (left + right)//2
            # しゃくとり法
            counter = 0
            end = N-1
            for start in range(Ps, N):
                while end >= start and A[start]*A[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
            start = 0
            for end in range(Zs-1, -1, -1):
                while end >= start and A[start]*A[end] >= mid:
                    start += 1
                if end <= start:
                    break
                counter += end-start
            # print("{} in [{}, {}] ==> {}".format(mid, left, right, counter))
            if counter < KK:
                left = mid
            else:
                right = mid
        print(left)


if __name__ == '__main__':
    main()