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 math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().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)

p_zeros = zeros*(len_negatives+len_positives) + nC2(zeros)
p_positives = nC2(len_positives) + nC2(len_negatives)
p_negatives = len_positives * len_negatives

log(len_negatives, zeros, len_positives)
log(p_negatives, p_zeros, p_positives)

if p_negatives < k <= (p_negatives+p_zeros):
    print(0)
    exit()

if k <= p_negatives:
    # 負の場合
    nokori = k
    log("nokori", nokori)

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

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

        left2 = len_positives-1
        right2 = len_negatives-1

        count = 0

        while right2 > 0 and positives[left2] * negatives[right2] < center:
            right2 -= 1
        
        # log("right2", right2)

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

        # left2 = len_positives-1
        # right2 = len_negatives-1

        # while left2 > 0 and positives[left2] * negatives[right2] < center:
        #     left2 -= 1
        # while right2 >= 0 and left2 < len_positives and (len_positives-left2 < len_negatives-right2):
        #     log(positives[left2] * negatives[right2])
        #     if positives[left2] * negatives[right2] < center:
        #         count += len_positives - left2
        #         right2 -= 1
        #     else:
        #         left2 += 1
        
        # log("count", count)
        if count < nokori:
            left = center
        else:
            right = center - 1
    print(left)
    exit()

# 正の場合
nokori = k - p_negatives - p_zeros
# log("nokori", nokori)

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

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

    left2 = 0
    right2 = len_positives-1

    count = 0

    while left2 < right2:
        if positives[left2] * positives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    left2 = 0
    right2 = len_negatives-1

    while left2 < right2:
        if negatives[left2] * negatives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1
    
    # log("center", center, "count", count)

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

Submission status: Accepted

Solution code:
import numpy as np
import math
stdin = open(0)

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

maxA = max(np.abs(A))

z = A[A==0]
p = A[A>0]
n = A[A<0]

def check(x):
    ret = 0
    if x >= 0:
        ret += N*len(z)
    ret += np.searchsorted(A,x//p,side='right').sum()
    ret += (N - np.searchsorted(A, -(x // -n))).sum()
#     ret += (N-np.searchsorted(A,np.ceil(x/n))).sum()
    ret -= np.count_nonzero(A*A<=x)
    return ret//2;

ub = maxA*maxA
lb = -ub-1
while ub-lb > 1:
    mid = (ub+lb)>>1
    if check(mid) < K:
        lb = mid
    else:
        ub = mid
print(ub)

Submission status: Accepted

Solution code:
import numpy as np
import math
stdin = open(0)

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

maxA = max(np.abs(A))

z = A[A==0]
p = A[A>0]
n = A[A<0]

def check(x):
    ret = 0
    if x >= 0:
        ret += N*len(z)
    ret += np.searchsorted(A,x//p,side='right').sum()
    ret += (N - np.searchsorted(A, (x+1) // n, side='right')).sum()
#     ret += (N-np.searchsorted(A,np.ceil(x/n))).sum()
    ret -= np.count_nonzero(A*A<=x)
    return ret//2;

ub = maxA*maxA
lb = -ub-1
while ub-lb > 1:
    mid = (ub+lb)>>1
    if check(mid) < K:
        lb = mid
    else:
        ub = mid
print(ub)

Submission status: Accepted

Solution code:
import numpy as np
import math
stdin = open(0)

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

maxA = max(np.abs(A))

z = A[A==0]
p = A[A>0]
n = A[A<0]

def check(x):
    ret = 0
    if x >= 0:
        ret += N*len(z)
    ret += np.searchsorted(A,x//p,side='right').sum()
    ret += (N - np.searchsorted(A, (-x - 1) // (-n), side='right')).sum()
#     ret += (N-np.searchsorted(A,np.ceil(x/n))).sum()
    ret -= np.count_nonzero(A*A<=x)
    return ret//2;

ub = maxA*maxA
lb = -ub-1
while ub-lb > 1:
    mid = (ub+lb)>>1
    if check(mid) < K:
        lb = mid
    else:
        ub = mid
print(ub)

Submission status: Accepted

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

    A.sort()

    # 負数、 0数、 正数
    neg, zero, pos = [], [], []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a == 0:
            zero.append(a)
        else:
            pos.append(a)

    prod_neg = len(neg) * len(pos)
    prod_zero = len(zero) * (len(neg)+len(pos))+len(zero)*(len(zero)-1)//2
    # prod_pos = len(neg)*(len(neg)-1)//2 + len(pos)*(len(pos)-1)//2

    if prod_neg >= K:
        # 二分探索
        left = neg[0]*pos[-1]-1
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            # しゃくとり法
            counter = 0
            ps = 0
            for ns in range(len(neg)):
                while ps < len(pos) and neg[ns]*pos[ps] > mid:
                    ps += 1
                if ps == len(pos):
                    break
                counter += len(pos)-ps
            if counter < K:
                left = mid
            else:
                right = mid
        print(right)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        KK = K-prod_neg-prod_zero
        # 二分探索
        left = 0
        right = 0
        if len(neg) > 0:
            right = max(neg[0]**2, right)
        if len(pos) > 0:
            right = max(pos[-1]**2, right)
        while right - left > 1:
            mid = (left + right)//2
            # しゃくとり法
            counter = 0
            end = len(pos)-1
            for start in range(len(pos)):
                while end >= start and pos[start]*pos[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
            start = 0
            for end in range(len(neg)-1, -1, -1):
                while end >= start and neg[start]*neg[end] >= mid:
                    start += 1
                if end <= start:
                    break
                counter += end-start
            if counter < KK:
                left = mid
            else:
                right = mid
        print(left)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


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

    A.sort()

    # 負数、 0数、 正数
    neg, zero, pos = [], [], []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a == 0:
            zero.append(a)
        else:
            pos.append(a)

    prod_neg = len(neg) * len(pos)
    prod_zero = len(zero) * (len(neg)+len(pos))+len(zero)*(len(zero)-1)//2
    prod_pos = len(neg)*(len(neg)-1)//2 + len(pos)*(len(pos)-1)//2

    if prod_neg >= K:
        # 二分探索
        left = neg[0]*pos[-1]-1
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            # しゃくとり法
            counter = 0
            ps = 0
            for ns in range(len(neg)):
                while ps < len(pos) and neg[ns]*pos[ps] > mid:
                    ps += 1
                if ps == len(pos):
                    break
                counter += len(pos)-ps
            if counter < K:
                left = mid
            else:
                right = mid
        print(right)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        # 二分探索
        left = 0
        right = 0
        if len(neg) > 0:
            right = max(neg[0]**2, right)
        if len(pos) > 0:
            right = max(pos[-1]**2, right)
        while right - left > 1:
            mid = (left + right)//2
            # しゃくとり法
            counter = 0
            end = len(pos)-1
            for start in range(len(pos)):
                while end >= start and pos[start]*pos[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
            start = 0
            for end in range(len(neg)-1, -1, -1):
                while end >= start and neg[start]*neg[end] >= mid:
                    start += 1
                if end <= start:
                    break
                counter += end-start
            if counter < K-prod_neg-prod_zero:
                left = mid
            else:
                right = mid
        print(left)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
a.sort()
pz = a[a > 0]
ng = a[a < 0]
z = np.count_nonzero(a == 0)


def count(x):
    res = 0
    if x >= 0:
        res += z * n
    res += np.searchsorted(a, x // pz, side="right").sum()
    res += n * len(ng) - np.searchsorted(a, -(-x // ng), side="left").sum()
    res -= np.count_nonzero(a * a <= x)
    return res // 2


l, r = -10 ** 19, 10 ** 19
while r - l > 1:
    m = (l + r) // 2
    if count(m) >= k:
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

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

  Ans, Aps, Azs = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      Azs.append(A)
    else:
      Ans.append(A)

  def count(xs, ys, ub):
    c = 0
    r = len(ys) - 1
    for l in range(len(xs)):
      while  r >= 0 and xs[l] * ys[r] > ub:
        r -= 1
      c += r+1
    return c 

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      
      tot = 0      
      tot += count(Aps, Aps, mid) - sum([1 for A in Aps if A**2 <= mid])
      tot += count(Ans[::-1], Ans[::-1], mid) - sum([1 for A in Ans if A**2 <= mid])
      tot //= 2

      if mid >=0:
        tot += (len(Aps) + len(Ans)) * len(Azs) + (len(Azs) * (len(Azs) - 1)) // 2
      tot += count(Aps[::-1], Ans, mid)
      
      if tot < k:
        l = mid
      else:
        r = mid
  
  print(bs(MIN-1, MAX+1))
    
    
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(i) for i in input().split()]
Pos = [x for x in L if x > 0]
Zero = [x for x in L if x == 0]
Neg = [x for x in L if x < 0]
Pos.sort()
Neg.sort(reverse=True)

Po = len(Pos)
Ne = len(Neg)
Ze= len(Zero)

ZeN = Ze*(Ze-1)//2 + Ze*(Po+Ne)
NeN = Po*Ne

if NeN<K<=NeN+ZeN:
    print(0)

else:
    def f(x):
        cnt = 0
        if x < 0:
            j = Po - 1
            for i in range(Ne):
                j=min(Po-1,j+1)
                while j >=0:
                    if Neg[i] * Pos[j] <= x:
                        j = j - 1
                    else:
                        break
                cnt = cnt + Po - j - 1
        else:
            j = 0
            for i in range(Po)[::-1]:
                j=max(0,j-1)
                while j < i:
                    if Pos[i]*Pos[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            j = 0
            for i in range(Ne)[::-1]:
                j = max(0, j - 1)
                while j < i:
                    if Neg[i]*Neg[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            cnt = cnt + ZeN + NeN
        return(cnt)

    Hi = 10**18
    Lo = -10**18

    while Hi-Lo > 1:
        Mid = (Hi + Lo) // 2
        if f(Mid) >= K:
            Hi = Mid
        else:
            Lo = Mid
    print(Hi)

Submission status: Accepted

Solution code:
import numpy as np

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

mn = n[np.where(n<0)]
mz = len(n[np.where(n==0)])
mp = n[np.where(n>0)]
M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    if pos >= 0: a+=mz*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
        
print(M)

Submission status: Accepted

Solution code:
import numpy as np

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

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]
M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    if pos >= 0: a+=len(mz)*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
        
print(M)

Submission status: Accepted

Solution code:
import numpy as np

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

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]

cn = len(mn)
cp = len(mp)
cz = len(mz)

if cn*cp < K <= cn*cp + (N-cz)*cz + cz*(cz-1)//2:
    print(0)
    exit(0)

M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    if pos >= 0: a+=cz*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
#print(M,m)
print(M)

Submission status: Accepted

Solution code:
import numpy as np

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

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]

#cn = len(mn)
##cp = len(mp)
#cz = len(mz)
#tcn = cn*cp

#if cn*cp < K <= cn*cp + (N-cz)*cz + cz*(cz-1)//2:
#    print(0)
#    exit(0)

M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    if pos >= 0: a+=len(mz)*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
#print(M,m)
print(M)

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x):
    ans = 0
    la, lb = len(a), len(b)
    J = (i for i in range(lb)) if a == b else (-1 for i in range(la))

    j = lb - 1
    for i, k in enumerate(J):
        xa = a[i]

        for j in range(j, k, -1):
            x1 = b[j] * xa
            if x1 <= x:
                break
        else:
            break
        ans += j - k

    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        #print(A[0], A[2])
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        #print((lo, hi), K1)
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid)
            #print((lo, hi), mid, k, K1)
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A[0].sort(reverse=True)
    A[2].sort()
    K3 = K - a0 - a1 - 1
    #print(A[0], A[2], a0, a1, K3)
    lo, hi = 0, 10**18
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A[0], A[0], mid) + cnt_val(A[2], A[2], mid)
        #print((lo, hi), k3, K3)
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            while pR>=0:
                if na*pA[pR]>x: break
                pR-=1
            ret+=len(pA)-pR-1
    elif x==0:
        ret+=neg
        ret+=zzz
        ret//=2
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)-1
        for na in nA:
            while pR>=0:
                if na*nA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if na*na<=x else 0
        pR=len(pA)-1
        for pa in pA:
            while pR>=0:
                if pa*pA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if pa*pa<=x else 0
        ret//=2
    return ret
#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x, cache):
    ans = 0
    la, lb = len(a), len(b)
    J = (i for i in range(lb)) if a == b else (-1 for i in range(la))

    if len(cache) == 0:
        ca = [x, 0]
        cb = [inf, lb-1]
        cache.append(ca)
        cache.append(cb)
    else:
        ca, cb = cache
        if x <= ca[0]:
            cache[0], cache[1] = ca, cb = cb, ca
        ca[0] = x

    j = cb[1]
    #for i in range(la):
    for i, k in enumerate(J):
        xa = a[i]

        for j in range(j, k, -1):
            x1 = b[j] * xa
            if x1 <= x:
                break
        else:
            break
        ans += j - k
        if i == 0:
            ca[1] = j

    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        #print(A[0], A[2])
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        cache1 = []
        #print((lo, hi), K1)
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid, cache1)
            #print((lo, hi), mid, k, K1)
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    #print(A[0], A[2], a0, a1, K3)
    lo, hi = 0, 10**18
    cache1, cache2 = [], []
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid, cache1) + cnt_val(A[2], A[2], mid, cache2)
        #print((lo, hi), k3, K3)
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x, cache):
    ans = 0
    la, lb = len(a), len(b)
    J = (i for i in range(lb)) if a == b else (-1 for i in range(la))

    j = lb - 1
    #for i in range(la):
    for i, k in enumerate(J):
        xa = a[i]

        for j in range(j, k, -1):
            x1 = b[j] * xa
            if x1 <= x:
                break
        else:
            break
        ans += j - k

    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        #print(A[0], A[2])
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        cache1 = []
        #print((lo, hi), K1)
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid, cache1)
            #print((lo, hi), mid, k, K1)
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    #print(A[0], A[2], a0, a1, K3)
    lo, hi = 0, 10**18
    cache1, cache2 = [], []
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid, cache1) + cnt_val(A[2], A[2], mid, cache2)
        #print((lo, hi), k3, K3)
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(c) for c in input().split()]
Ap = []
An = []
Az = []
for i in range(N):
  if A[i]>0:
    Ap += [A[i]]
  elif A[i]<0:
    An += [A[i]]
  else:
    Az += [A[i]]
lp = len(Ap)
ln = len(An)
lz = len(Az)
Ap.sort(reverse=True)
An.sort(reverse=True)
def f(m, B, C):
  cnt = 0
  j  = 0
  lb = len(B)
  lc = len(C)
  for i in range(lc):
    while j<lb:
      if B[j]*C[i]>=m:
        cnt += j
        break
      j += 1
    else:
      cnt += j
  return cnt
if K<=lp*ln:
  r = 1
  l = -10**18+10
  while l+1<r:
    n = (l+r)//2
    if f(n,Ap,An)>=K:
      r = n
    else:
      l = n
  print(l)
  import sys
  sys.exit()
K -= lp*ln
if K<=lz*(lp+ln) + lz*(lz-1)//2:
  print(0)
  import sys
  sys.exit()
K -= lz*(lp+ln) + lz*(lz-1)//2
r = 10**18+10
l = -1
while l+1<r:
  n = (l+r)//2
  P = f(n,Ap[::-1],Ap)
  for i in range(lp):
    if Ap[lp-1-i]*Ap[lp-1-i]<n:
      P -= 1
    else:
      break
  P //= 2
  N = f(n,An,An[::-1])
  for i in range(ln):
    if An[i]*An[i]<n:
      N -= 1
    else:
      break
  N //= 2
  if P+N>=K:
    r = n
  else:
    l = n
print(l)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])


def main():
    read = sys.stdin.read

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

    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    if m > 0:
    	negative = np.array(A[:m], np.int64)
    else:
      	negative = np.array([], np.int64)
    if p > 0:
    	positive = np.array(A[-p:], np.int64)
    else:
      	positive = np.array([], np.int64)
    negative = -negative[::-1]
    # 負の数の操作(pythonの挙動)は頭がこんがらがるので正の数にして考える

    if K <= M:
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, (mid + negative - 1) // negative, side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        left = 0
        right = max(A[0] * A[1], A[-1] * A[-2])
        positive2 = positive ** 2
        negative2 = negative ** 2
        while left + 1 < right:
            mid = (left + right) // 2
            a = np.searchsorted(negative, mid // negative, side='right').sum() - (mid >= negative2).sum()
            b = np.searchsorted(positive, mid // positive, side='right').sum() - (mid >= positive2).sum()

            if (a + b) // 2 < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])


def main():
    read = sys.stdin.read

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

    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    A = np.array(A, np.int64)
    negative = A[A < 0]
    positive = A[A > 0]
    m = len(negative)
    p = len(positive)
    z = N - m - p

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = -negative[::-1]
    # 負の数の操作(pythonの挙動)は頭がこんがらがるので正の数にして考える

    if K <= M:
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, (mid + negative - 1) // negative, side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        left = 0
        right = max(A[0] * A[1], A[-1] * A[-2])
        positive2 = positive ** 2
        negative2 = negative ** 2
        while left + 1 < right:
            mid = (left + right) // 2
            a = np.searchsorted(negative, mid // negative, side='right').sum() - (mid >= negative2).sum()
            b = np.searchsorted(positive, mid // positive, side='right').sum() - (mid >= positive2).sum()

            if (a + b) // 2 < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    #~A[p-1]:negative, A[q]~:positive
    p = bisect.bisect_left(a,0)
    q = bisect.bisect_right(a,0)
    zeros = q-p

    ok = 10**18
    ng = -ok-1
    while ok-ng > 1:
        mid = (ok+ng)//2

        #count
        cnt = 0
        if mid == 0:
            #{(negative),(zero,positive)}
            cnt += p*(n-p)
            #{(zero,positive),(zero,positive)}
            cnt += (n-p)*(n-p-1)//2
        elif mid > 0:
            #{(negative),(negative)}
            #{(A[j]~A[p-1]),A[i]) >>> clear!
            j = 0
            for i in range(p-1,-1,-1):
                while j <= p-1:
                    if a[i]*a[j] > mid:
                        j += 1
                    else:
                        break
                cnt += p-1-j+1
                if j <= i:
                    cnt -= 1
            
            #{(positive),(positive)}
            #{(A[q]~A[j]),A[i]} >>> clear!
            j = n-1
            for i in range(q,n):
                while j >= q:
                    if a[i]*a[j] >  mid:
                        j -= 1
                    else:
                        break
                cnt += j-q+1
                if i <= j:
                    cnt -= 1
            
            cnt = cnt//2

            #{(negative),(zero,positive)}
            cnt += p*(n-p)
            
            #{(zero),(zero)}
            cnt += zeros*(zeros-1)//2

            #{(positive),(zero)}
            cnt += zeros*(n-q)
        else:
            #{(negative),(positive)}
            #{(A[j]~A[n-1]),A[i]} >>> clear!
            j = q
            for i in range(p):
                while j < n:
                    if a[i]*a[j] >  mid:
                        j += 1
                    else:
                        break
                cnt += n-1-j+1

        if cnt >= k:
            ok = mid
        else:
            ng = mid
    print(ok)

if __name__ == "__main__":
    main()

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=np.array(A)
    A=np.sort(A)
    Ap=A[A>0]
    Az=A[A==0]
    Am=A[A<0]   
    lm,lz,lp=len(Am),len(Az),len(Ap)
    Am2=Am**2
    Ap2=Ap**2
    #print(Ap,Am,Az,Ap2,Am2)
    def cnt_product(x): #ある数字の組であってその積がx以下となるものの数
        if x<0:
            X=np.searchsorted(Am,x//Ap,side='right')
            #print(X)
            return X.sum()
        
        else:
            ans=lz*(n-lz)+lz*(lz-1)//2+lp*lm

            X=np.searchsorted(Ap,x//Ap,side='right')
            Xd=np.count_nonzero(Ap2<=x)

            Y=np.searchsorted(Am,(-x-1)//(-Am),side='right')
            Yd=np.count_nonzero(Am2<=x)
            
            ans+=(X.sum()-Xd+lm**2-Y.sum()-Yd)//2
            return ans

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

if __name__=='__main__':
    main()