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 f1(m):
    j=0
    num=0
    for x in ap[::-1]:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    h,l=0,10**18
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        else: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    k-=pz
    h,l=10**20,0
    while h-l>1:
        md=(h+l)//2
        p=f2(md)
        if p>=k: h=md
        else: l=md
    print(h)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

positive = A[A>0]
negative = A[A<0]
zero = A[A==0]

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

while l + 1 < r:
    x = (l+r) // 2 # 中央位置
    cnt = 0
    if x >= 0:
        cnt += N * len(zero)
    
    # x//pos : 中央値/posのそれぞれの値
    cnt += A.searchsorted(x//positive, side="right").sum()
    cnt += (N - A.searchsorted(-(-x//negative), side="left")).sum()
    cnt -= np.count_nonzero(A * A <= x)
    cnt //= 2
 
    if cnt >= K:
        r = x
    else:
        l = x
print(r)

Submission status: Accepted

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

# 2分探索, midより小さいものを数える
l = -10**18-1
r = 10**18+1
while r-l > 1:
    mid = (r+l)//2
    cnt = 0
    if mid >= 0:
        cnt += len(zero)*n
    
    # a.searchsorted(v, side="left"): a[i-1] < v <= a[i]であるvのindexを返す  
    # a.searchsorted(v, side="right"): a[i-1] <= v < a[i]であるvのindexを返す  

    cnt += a.searchsorted(mid//posi, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//nega), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt //= 2
    # print("mid:", mid)
    # print("mid//posi:", mid//posi)
    # print("search:", a.searchsorted(mid//posi,side="right"))
    # print("-(-mid//nega):", -(-mid//nega))
    # print("search:", a.searchsorted(-(-mid//nega),side="left"))
    # print("nonzero_count:", np.count_nonzero(a*a<=mid))
    # print("count:", cnt)
    # print('-' * 20)
    if cnt >= k:
        r = mid
    else:
        l = mid
print(r)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()


def countPair(Ap, Am, plus, minus, zero, x):
    """
    「積がx未満になる組」の個数を返す。

    Aiをfixしたとき、Ai * Aj < xなるjの個数をカウントしていけば良い。
    二分探索では間に合わなかったので、尺取り法で実装する。
    """
    num = 0
    if x < 0:
        idx = 0 # Amの各値に対して、Ap上を走査する
        for a in Am:
            while idx < plus and a * Ap[idx] >= x:
                idx += 1
            if idx >= plus:
                break
            num += plus - idx
        return num

    elif x == 0:
        num = plus * minus
        return num

    else:
        num = plus * minus # 積が負になる組
        num += zero * (plus + minus) # 0 * a (ただしa!=0)なる組
        num += zero * (zero - 1) // 2 # 0 * 0なる組

        """
        以下のカウントでは(A[i]*A[j])と(A[j]*A[i])を区別してしまう。
        また(A[i]*A[i])も数えてしまうので、あえてまずはこのような重複をありにして、
        最後に２で割るなりして処理する。
        """
        prenum = 0
        dupl = 0
        # 正＊正の場合
        idx = plus - 1 # Apの各値に対して、Ap上を走査する
        for a in Ap:
            while idx >= 0 and a * Ap[idx] >= x:
                idx -= 1
            prenum += idx + 1

            if a * a < x:
                dupl += 1

        # 負＊負の場合
        idx = minus - 1 # Amの各値に対して、Am上を走査する
        for a in Am:
            while idx >= 0 and a * Am[idx] < x:
                idx -= 1
            prenum += minus - idx - 1

            if a * a < x:
                dupl += 1

        return num + (prenum - dupl) // 2

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    Ap = []
    Am = []
    plus = 0
    minus = 0
    zero = 0
    for a in A:
        if a > 0:
            Ap.append(a)
            plus += 1
        elif a < 0:
            Am.append(a)
            minus += 1
        else:
            zero += 1
    Ap.sort()
    Am.sort()

    """
    (K個目の値) = (「積がx未満になる組がK個未満」であるようなxの最大値)
    として決め打ち二分探索を行う。
    """

    l = -10 ** 18 - 1
    r = 10 ** 18 + 1
    while r - l > 1:
        m = (l + r) // 2
        if countPair(Ap, Am, plus, minus, zero, m) < K:
            l = m
        else:
            r = m
    print(l)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=[int(j) for j in input().split()]
from numpy import *
a=array([int(j) for j in input().split()])
a.sort()
lm=a[a<0]
lp=a[a>0]
lz=a[a==0]
np=len(lp)
nm=len(lm)
nz=len(lz)

import bisect
import math
def f(x):
    c=0
    if x>=0:
        c+=nz*n
    c+=searchsorted(a,x//lp,side="right").sum()
    c+=(n-searchsorted(a,(-x-1)//(-lm),side="right")).sum()
    c-=count_nonzero(a*a<=x)
    return c//2

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

Submission status: Accepted

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

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    
    posi,zero,nega = [],[],[]
    for num in a:
        if num > 0:
            posi.append(num)
        elif num == 0:
            zero.append(num)
        else:
            nega.append(num)
            
    lp,lz,ln = len(posi),len(zero),len(nega)
    posi.sort(),nega.sort()
    posi,zero,nega = np.array(posi),np.array(zero),np.array(nega)
    _nega = nega[::-1]*(-1)
    
    def ch(x):
        if x == 0:
            return (lz*(lz-1))//2+lz*(lp+ln)+lp*ln
        elif x > 0:
            count = (lz*(lz-1))//2+lz*(lp+ln)+lp*ln
            puse = np.searchsorted(posi,(x//posi),side="right")
            pdup = np.count_nonzero(posi**2<=x)
            nuse = np.searchsorted(_nega,x//_nega,side="right")
            ndup = np.count_nonzero(_nega**2<=x)
            return (np.sum(puse)+np.sum(nuse)-pdup-ndup)//2+count
        else:
            count = np.searchsorted(nega,x//posi,side="right")
            return np.sum(count)

    l,r = -10**18-1,10**18+1
    while r-l > 1:
        mid = (r+l)//2
        if ch(mid) >= K:
            r = mid
        else:
            l = mid
    print(r)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,K = map(int,input().split())
    a = np.array(list(map(int,input().split())))
    a.sort()
    posi,zero,nega = a[a>0],a[a==0],a[a<0]
    lz = len(zero)
    
    def ch(x):
        count = 0
        if x >= 0:
            count += lz*N
        count += np.searchsorted(a,x//posi,side="right").sum()
        count += (N-np.searchsorted(a,-(-x//nega))).sum()
        count -= np.count_nonzero(a**2<=x)
        return count//2

    l,r = -10**18-1,10**18
    while r-l > 1:
        mid = (r+l)//2
        if ch(mid) >= K:
            r = mid
        else:
            l = mid

    print(r)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

from bisect import bisect

DEBUG = False


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

A.sort()
A = np.array(A, dtype=np.int64)
neg = A[A < 0]
zero = A[A == 0]
pos = A[A > 0]

# Only keep the abs value of the negatives and flip so it's sorted
revAbsNeg = -neg[::-1]


def countDistinctPairsLessThan(arr, prod):
    # Given a sorted array find the number of distinct pairs that are < prod
    # O(N * log(N)) where N = len(arr)

    N = arr.shape[0]
    assert arr.shape == (N,)
    count3 = np.sum(
        np.minimum(np.arange(N), np.searchsorted(arr, (prod - 1) // arr, side="right"))
    )

    if DEBUG:
        count = 0
        for i, x in enumerate(arr):
            count += bisect(arr, (prod - 1) // x, 0, i)

        count2 = 0
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                if arr[i] * arr[j] < prod:
                    count2 += 1
        assert count == count2 == count3
    return count3


def countPairsLessThanOrEqual(arr1, arr2, prod):
    # Given two sorted arrays containing *positive* numbers only,
    # find the number of pairs between the two arrays that are <= prod
    # O(N * log(M)) where N = len(arr1), M = len(arr2)
    if len(arr1) > len(arr2):
        arr1, arr2 = arr2, arr1

    count3 = np.sum(np.searchsorted(arr2, prod // arr1, side="right"))

    if DEBUG:
        count = 0
        for x in arr1:
            count += bisect(arr2, prod // x)
        count2 = 0
        for x in arr1:
            for y in arr2:
                if x * y <= prod:
                    count2 += 1
        assert count == count2 == count3
    return count3


def getIndex(prod):
    # Count number of pairs strictly less than prod
    count = 0
    if prod < 0:
        # All negatives except for the negatives with abs value less than or equal -prod
        count += len(pos) * len(neg)
        count -= countPairsLessThanOrEqual(pos, revAbsNeg, -prod)
    elif prod >= 0:
        # All negatives
        count += len(pos) * len(neg)
        if prod > 0:
            # All zeroes
            count += len(zero) * len(neg)
            count += (len(zero) * (len(zero) - 1)) // 2
            count += len(zero) * len(pos)
            # Positives with positives
            count += countDistinctPairsLessThan(pos, prod)
            # Negatives with negatives
            count += countDistinctPairsLessThan(revAbsNeg, prod)

    if DEBUG:
        count2 = 0
        for i in range(N):
            for j in range(i + 1, N):
                if A[i] * A[j] < prod:
                    count2 += 1
        assert count == count2
    return count


def bisect_f(f, lo, hi):
    if DEBUG:
        assert f(lo) and not f(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if f(mid):
            lo = mid
        else:
            hi = mid
        if DEBUG:
            assert f(lo) and not f(hi)
    if DEBUG:
        assert hi - lo == 1
        assert f(lo) and not f(hi)
    return lo


def solve(K):
    lo = -10 ** 18
    hi = 10 ** 18 + 1
    if DEBUG:
        assert getIndex(lo) <= K < getIndex(hi)
    prod = bisect_f(lambda prod: getIndex(prod) <= K, lo, hi)
    if DEBUG:
        assert getIndex(prod) <= K < getIndex(prod + 1)
    return prod


if DEBUG:
    for k in range((N * (N - 1)) // 2):
        print("k", k, solve(k))

print(solve(K - 1))  # K is 1-indexed

Submission status: Accepted

Solution code:
import numpy as np

from bisect import bisect

DEBUG = False


def bisect_f(f, lo, hi):
    if DEBUG:
        assert f(lo) and not f(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if f(mid):
            lo = mid
        else:
            hi = mid
        if DEBUG:
            assert f(lo) and not f(hi)
    if DEBUG:
        assert hi - lo == 1
        assert f(lo) and not f(hi)
    return lo


N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
neg = []
zero = []
pos = []
for x in A:
    if x < 0:
        neg.append(x)
    elif x == 0:
        zero.append(x)
    else:
        assert x > 0
        pos.append(x)

revAbsNeg = [-x for x in reversed(neg)]  # Reverse neg and keep magnitude only
posSq = [x ** 2 for x in pos]
negSq = [x ** 2 for x in revAbsNeg]

pos = np.array(pos, dtype=np.int64)
revAbsNeg = np.array(revAbsNeg, dtype=np.int64)


def countDistinctPairsLessThan(arr, prod):
    # Given a sorted array find the number of pairs that are < prod
    # O(N * log(N)) where N = len(arr)

    N = arr.shape[0]
    assert arr.shape == (N,)
    count3 = np.sum(
        np.minimum(np.arange(N), np.searchsorted(arr, (prod - 1) // arr, side="right"))
    )

    if DEBUG:
        count = 0
        for i, x in enumerate(arr):
            count += bisect(arr, (prod - 1) // x, 0, i)

        count2 = 0
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                if arr[i] * arr[j] < prod:
                    count2 += 1

        print(count, count2, count3)
        assert count == count2 == count3
    return count3


def countPairsLessThanOrEqual(arr1, arr2, prod):
    # Given two sorted arrays containing *positive* numbers only,
    # find the number of pairs between the two arrays that are <= prod
    # O(N * log(M)) where N = len(arr1), M = len(arr2)
    if len(arr1) > len(arr2):
        arr1, arr2 = arr2, arr1

    count3 = np.sum(np.searchsorted(arr2, prod // arr1, side="right"))

    if DEBUG:
        count = 0
        for x in arr1:
            count += bisect(arr2, prod // x)
        count2 = 0
        for x in arr1:
            for y in arr2:
                if x * y <= prod:
                    count2 += 1
        assert count == count2 == count3
    return count3


def getIndex(prod):
    # Count number of pairs strictly less than prod
    count = 0
    if prod < 0:
        # All negatives except for the negatives with abs value less than or equal -prod
        count += len(pos) * len(neg)
        count -= countPairsLessThanOrEqual(pos, revAbsNeg, -prod)
    elif prod >= 0:
        # All negatives
        count += len(pos) * len(neg)
        if prod > 0:
            # All zeroes
            count += len(zero) * len(neg)
            count += (len(zero) * (len(zero) - 1)) // 2
            count += len(zero) * len(pos)
            # Positives with positives
            count += countDistinctPairsLessThan(pos, prod)
            # Negatives with negatives
            count += countDistinctPairsLessThan(revAbsNeg, prod)

    if DEBUG:
        count2 = 0
        for i in range(N):
            for j in range(i + 1, N):
                if A[i] * A[j] < prod:
                    count2 += 1
        assert count == count2
    return count


def solve(K):
    lo = -10 ** 18
    hi = 10 ** 18 + 1
    if DEBUG:
        assert getIndex(lo) <= K < getIndex(hi)
    prod = bisect_f(lambda prod: getIndex(prod) <= K, lo, hi)
    if DEBUG:
        assert getIndex(prod) <= K < getIndex(prod + 1)
    return prod


if DEBUG:
    for k in range((N * (N - 1)) // 2):
        print("k", k, solve(k))

print(solve(K - 1))  # K is 1-indexed

Submission status: Accepted

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

def main():
    N, K = map(int,input().split())
    A = np.sort(np.array(list(map(int, input().split())), np.int64))
    z = A[A == 0]
    p = A[A > 0]
    n = A[A < 0]
    
    def count_func(x):
        cnt = 0
        if x >= 0:
            cnt += len(z) * N
        cnt += np.searchsorted(A, x // p, side='right').sum()
        cnt += (N - np.searchsorted(A, -(-x // n), side='left')).sum()
        cnt -= np.count_nonzero(A * A <= x)
        assert cnt % 2 == 0
        return cnt // 2
    
    l = -10 ** 18
    r = 10 ** 18
    while l + 1 < r:
        x = (l + r) // 2
        if count_func(x) >= K:
            r = x
        else:
            l = x
    
    print(r)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=-A_neg[::-1]
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
p = []
z = []
m = []
for i in range(n):
    if a[i] > 0:
        p.append(a[i])
    elif a[i] == 0:
        z.append(a[i])
    else:
        m.append(a[i])
nb1 = -10**18-1
nb2 = 10**18+1
p1 = len(p)
z1 = len(z)
m1 = len(m)
#print(p,m)
#print(p1,z1,m1)
def sytr(x,p,z,m,p1,z1,m1):
    ans = 0
    ans2 = 0
    ans3 = -10**18
    if x > 0:
        m.sort(reverse=True)
        p.sort()
        ans += p1*m1 + (p1+m1)*z1 + (z1-1)*z1//2
        ans2 += ans
        now = 0
        #print(p)
        now1 = p1-1
        now2 = 0
        now3 = p1-1
        if p1 > 1:
            while now < now1:
                if p[now]*p[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,p[now]*p[now1])
                    ans += now1-now
                    now += 1
            while now2 < now3:
                if p[now2]*p[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3 - now2
                    now2 += 1
        if m1 > 1:
            now = 0
            now1 = m1-1
            now2 = 0
            now3 = m1-1
            while now < now1:
                if m[now]*m[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,m[now]*m[now1])
                    ans += now1 - now
                    now += 1
            while now2 < now3:
                if m[now2]*m[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3 - now2
                    now2 += 1
    elif x == 0:
        p.sort()
        m.sort()
        if p1 > 0 and m1 > 0:
            ans3 = p[0]*m[m1-1]
        if z1 > 0:
            ans3 = 0
        ans += p1*m1+1
        ans2 += (p1+m1)*z1 + ans - 1
        if z1 > 1:
            ans2 += z1*(z1-1)//2
    else:
        p.sort(reverse=True)
        m.sort()
        now = 0
        now1 = m1-1
        now2 = 0
        now3 = m1-1
        if p1 > 0 and m1 > 0:
            while now < p1 and now1 >= 0:
                if p[now]*m[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,p[now]*m[now1])
                    ans += now1+1
                    now += 1
            while now2 < p1 and now3 >= 0:
                if p[now2]*m[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3+1
                    now2 += 1
    return [ans,ans2,ans3]
while nb1 + 1 < nb2:
    #print(nb1,nb2)
    x = (nb1+nb2)//2
    #print(sytr(x,p,z,m,p1,z1,m1))
    if max(sytr(x,p,z,m,p1,z1,m1)[0],sytr(x,p,z,m,p1,z1,m1)[1]) < k:
        nb1 = x
    elif min(sytr(x,p,z,m,p1,z1,m1)[0],sytr(x,p,z,m,p1,z1,m1)[1]) > k:
        nb2 = x
    else:
        if abs(sytr(x,p,z,m,p1,z1,m1)[1]-sytr(x,p,z,m,p1,z1,m1)[0]) == 0:
            x = sytr(x,p,z,m,p1,z1,m1)[2]
            break
        else:
            break
print(x)

Submission status: Accepted

Solution code:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline

import numpy as np

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

P = A[A>0]
Z = A[A==0]
N = A[A<0]

#t = n*(n-1)//2

def ok(x):
    # x以下になる組み合わせがk個以上
    cnt = 0
    #cnt += np.searchsorted(A, np.ceil(x/P), side='right').sum()
    cnt += np.searchsorted(A, x//P, side='right').sum()
    #cnt += n-np.searchsorted(A, np.floor(x/N), side='left').sum()
    cnt += (n-np.searchsorted(A, (-x-1)//(-N), side='right')).sum()
    if x >= 0:
        cnt += len(Z)*n
    cnt -= np.count_nonzero(A*A <= x)
    cnt = cnt//2
    if cnt >= k:
        return True
    else:
        return False

l = -10**18-1
r = 10**18+1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(r)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = map(int, input().split())

    neg, pos, zero = list(), list(), 0
    for a in A:
        if a < 0: neg.append(a)
        elif a > 0: pos.append(a)
        else: zero += 1
    neg.sort()
    pos.sort()

    #x未満になる組み合わせの個数
    def calc(x):
        result = 0
        if x < 0:
            #負になるのは 正*負, 負*正
            i, j = len(pos)-1, len(neg)-1
            while i >= 0:
                while j >= 0 and pos[i]*neg[j] >= x: j -= 1
                if j < 0: break
                result += j + 1
                i -= 1
        elif x == 0:
            result += len(neg) * len(pos) #負
        else:
            #正*正
            i, j = 0, len(pos)-1
            while i < len(pos):
                while j >= 0 and pos[i]*pos[j] >= x: j -= 1
                if j < 0: break
                result += j + 1
                if pos[i]*pos[i] < x: result -= 1 #同じもの同士を除外
                i += 1
            #負*負
            i, j = len(neg)-1, 0
            while i >= 0:
                while j < len(neg) and neg[i]*neg[j] >= x: j += 1
                if j >= len(neg): break
                result += len(neg) - j
                if neg[i]*neg[i] < x: result -= 1 #同じもの同士を除外
                i -= 1
            result //= 2 #ペアの入れ替え分
            result += len(neg) * len(pos) #負
            result += (len(neg) + len(pos)) * zero + (zero)*(zero-1)//2 #0
        return result
    
    #二分探索
    l, over = -10**18, 10**18+1
    while over - l > 1:
        m = (l+over)//2
        if calc(m) < K: l = m
        else: over = m
    print(l)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = map(int, input().split())

    neg, pos, zero = list(), list(), 0
    for a in A:
        if a < 0: neg.append(a)
        elif a > 0: pos.append(a)
        else: zero += 1
    neg.sort()
    pos.sort()

    #x未満になる組み合わせの個数
    def calc(x):
        result = 0
        if x < 0:
            #負になるのは 正*負, 負*正
            i, j = len(pos)-1, len(neg)-1
            while i >= 0:
                while j >= 0 and pos[i]*neg[j] >= x: j -= 1
                if j < 0: break
                result += j + 1
                i -= 1
        elif x == 0:
            result += len(neg) * len(pos) #負
        else:
            #正*正
            i, j = 0, len(pos)-1
            while i < len(pos):
                while j >= 0 and pos[i]*pos[j] >= x: j -= 1
                if j < 0: break
                result += j + 1
                if pos[i]*pos[i] < x: result -= 1 #同じもの同士を除外
                i += 1
            #負*負
            i, j = len(neg)-1, 0
            while i >= 0:
                while j < len(neg) and neg[i]*neg[j] >= x: j += 1
                if j >= len(neg): break
                result += len(neg) - j
                if neg[i]*neg[i] < x: result -= 1 #同じもの同士を除外
                i -= 1
            result //= 2 #ペアの入れ替え分
            result += len(neg) * len(pos) #負
            result += (len(neg) + len(pos)) * zero + (zero)*(zero-1)//2 #0
        return result
    
    #二分探索
    l, over = -10**18, 10**20+1
    while over - l > 1:
        m = (l+over)//2
        if calc(m) < K: l = m
        else: over = m
    print(l)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    readline=stdin.readline
    N,K=map(int,readline().split())
    A=list(map(int,readline().split()))
    A.sort()

    #符号が - → 0 , 0 → + となるindexを求める
    index=[len(A),len(A)]
    mode=0
    for i in range(N):
        if mode==0:
            if A[i]==0:
                index[0]=i
                mode=1
            elif A[i]>0:
                index[0],index[1]=i,i
                break
        else:
            if A[i]>0:
                index[1]=i
                break

    #二分探索
    l=-10**18
    r=10**18+1
    while(l<r-1):
        x=(l+r)//2
        count=0

        #尺取り法
        if x>0:
            now_j=index[0]
            for i in range(index[0]):  #A[i]<0
                for j in range(now_j,-1,-1):
                    if A[i]*A[j-1]>=x:
                        now_j=j
                        count+=len(A)-now_j
                        if now_j<=i:
                            count-=1
                        break
                else:
                    now_j=0
                    count+=len(A)
                    count-=1

            for i in range(index[0],index[1]):  #A[i]=0
                if x>0:
                    count+=len(A)-1
                else:
                    break
            
            now_j=index[0]
            for i in range(len(A)-1,index[1]-1,-1):
                for j in range(now_j,len(A)):
                    if A[i]*A[j]>=x:
                        now_j=j
                        count+=now_j
                        if now_j>=i+1:
                            count-=1
                        break
                else:
                    now_j=len(A)
                    count+=len(A)
                    count-=1

        else:
            now_j=len(A)
            for i in range(index[0]-1,-1,-1):  #A[i]<0
                for j in range(now_j,-1,-1):
                    if A[i]*A[j-1]>=x:
                        now_j=j
                        count+=len(A)-now_j
                        if now_j<=i:
                            count-=1
                        break
            
            now_j=0
            for i in range(index[1],len(A)):
                for j in range(now_j,len(A)):
                    if A[i]*A[j]>=x:
                        now_j=j
                        count+=now_j
                        if now_j>=i+1:
                            count-=1
                        break

        count//=2
        if count<K:
            l=x
        else:
            r=x

    print(l)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mina = []
zera = []
plua = []
for x in a:
  if x > 0: plua.append(x)
  elif x == 0: zera.append(x)
  else: mina.append(x)

mlim = len(mina) * len(plua)
zlim = len(zera) * (len(mina) + len(plua)) + len(zera) * (len(zera) - 1) // 2 + mlim

def minacheck(x):
  res = 0
  j = 0
  for i in range(len(plua)):
    while j < len(mina) and (plua[i] * mina[j]) <= x: j += 1
    res += j
  return res >= K

def pluacheck(x):
  res = 0
  j = 0
  for i in range(len(mina) - 1, -1, -1):
    while j < len(mina) and (mina[i] * mina[j] <= x): j += 1
    res += max(0, j - i - 1)
  j = 0
  for i in range(len(plua) - 1, -1, -1):
    while j < len(plua) and (plua[i] * plua[j] <= x): j += 1
    res += max(0, j - i - 1)
  return res >= K - zlim

if K <= mlim:
  ng = -pow(10, 18)
  ok = 0
  while ok - ng > 1:
    m = (ok + ng) // 2
    if minacheck(m): ok = m
    else: ng = m
  print(ok)
elif K <= zlim: print(0)
else:
  for i in range(len(mina)): mina[i] = -mina[i]
  mina.reverse()
  ng = 0
  ok = pow(10, 18)
  while ok - ng > 1:
    m = (ok + ng) // 2
    if pluacheck(m): ok = m
    else: ng = m
  print(ok)

Submission status: Accepted

Solution code:
import numpy as np
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = np.array(a)
a.sort()
p = a[a>0]
z = a[a==0]
m = a[a<0]
low = -10**18
high = 10**18
while high-low>1:
    mid = (high + low) //2
    count = 0
    if mid >= 0:
        count += len(z)*n
    count += a.searchsorted(mid//p,side = "right").sum()
    count += (n-a.searchsorted(-(-mid//m),side = "left")).sum()
    count -= np.count_nonzero(a*a <= mid)
    count /= 2
    if count >= k:
        high = mid
    if count < k:
        low = mid
print(high)