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: Time Limit Exceeded

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

def upper_bound(A,X):
    if X<A[0]:
        return 0
    if A[-1]<=X:
        return len(A)
    l=0;r=len(A);mid=0
    while abs(r-l)>1:
        mid = (l+r)//2
        if A[mid]<=X:
            l=mid
        else:
            r=mid
    return r

INF = 1145141919810893364
#INFはすくなくとも10^18+1は必要(10^9の積を扱うので)

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

Posi=[];Nega=[];Zero=[]
Nega2=[]


#まず、Aの要素を正、負、０に分ける
for a in A:
    if a>0:
        Posi.append(a)
    elif a<0:
        Nega.append(a)
        Nega2.append(-a)
    else:
        Zero.append(a)
#Zeroの要素は0のみなのであえてvectorで持つ必要はないが、あえてこうしておく

#二分探索できるよう、ソートしておく
Posi.sort()
Nega.sort()
Nega2.sort()
Zero.sort()

#次に、N(N-1)/2個ある積のうち、正であるものの個数を求める
#負であるもの、０であるものも同様に求める

#積が正になるもの：ともに正かともに負
#積が負になるもの：正と負の組み合わせ
#積が０になるもの　どちらかが０
P_posi=0;P_nega=0;P_zero=0
P_posi += (len(Posi))*(len(Posi)-1)//2
P_posi += (len(Nega))*(len(Nega)-1)//2

P_nega += (len(Posi))*(len(Nega))

P_zero += (len(Zero))*(len(Zero)-1)//2
P_zero += (len(Zero))*(len(Posi))
P_zero += (len(Zero))*(len(Nega))

#にぶたん開始
l = -INF;r=INF;mid=0

while abs(r-l)>1:
    mid=(l+r)//2
    #このにぶたんでは、mid未満の数はいくつあるかを数えたい
    #それは、O(NlogN)で計算できる
    
    #Xより少ない数はいくつある？
    R=0
    if mid<0:
        #midより小さい数はいくつ？？
        #midより小さい数は、絶対値がmidのものより大きい
        #なのでにぶたんでは、絶対値がmidより真に大きいものの数を数える必要がある
        #直接この処理を走らせることは困難
        #なので、「絶対値がmidのものと同じか小さいもの」の数を数え、それを総数から引くことで数える
        for v in Nega:
            R += upper_bound(Posi,mid//v)
        R = P_nega-R
    
    elif mid==0:
        R = P_nega
        
    else:
        #負の数をそのままにぶたんをするとこわれやすい(実装と頭が)
        #なので負の要素を全て正にしておいたもの(Nega2)を用意してそれでにぶたんをした
        
        #midより小さい数はいくつ？？
        #まず０と負の数は明らかにmidより小さい
        R+=P_nega+P_zero;
        #基本的には負の場合と同様の処理をする
        #しかし、正の場合はPosi*Posi,Nega*Negaなので重複をケアする必要がある
        #以下のように処理することでケアができる(図解すると理解が早い)
        for i in range(len(Posi)):
            temp = upper_bound(Posi,(mid-1)//Posi[i])
            R += min(temp,i)
        for i in range(len(Nega2)):
            temp = upper_bound(Nega2,(mid-1)//Nega2[i])
            R += min(temp,i)
    
    num = R
    #mid未満の数はnum個である！
    
    #midより小さい数がK個と同じか少なかったらmidが小さすぎる
    if num<K:
        l=mid
    else:
        r=mid

print(l)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect
INF = 1145141919810893364
#INFはすくなくとも10^18+1は必要(10^9の積を扱うので)

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

Posi=[];Nega=[];Zero=[]
Nega2=[]


#まず、Aの要素を正、負、０に分ける
for a in A:
    if a>0:
        Posi.append(a)
    elif a<0:
        Nega.append(a)
        Nega2.append(-a)
    else:
        Zero.append(a)
#Zeroの要素は0のみなのであえてvectorで持つ必要はないが、あえてこうしておく

#二分探索できるよう、ソートしておく
Posi.sort()
Nega.sort()
Nega2.sort()
Zero.sort()

#次に、N(N-1)/2個ある積のうち、正であるものの個数を求める
#負であるもの、０であるものも同様に求める

#積が正になるもの：ともに正かともに負
#積が負になるもの：正と負の組み合わせ
#積が０になるもの　どちらかが０
P_posi=0;P_nega=0;P_zero=0
P_posi += (len(Posi))*(len(Posi)-1)//2
P_posi += (len(Nega))*(len(Nega)-1)//2

P_nega += (len(Posi))*(len(Nega))

P_zero += (len(Zero))*(len(Zero)-1)//2
P_zero += (len(Zero))*(len(Posi))
P_zero += (len(Zero))*(len(Nega))

def main():
    
    #にぶたん開始
    l = -INF;r=INF;mid=0
    
    while abs(r-l)>1:
        mid=(l+r)//2
        #このにぶたんでは、mid未満の数はいくつあるかを数えたい
        #それは、後述する自作関数less_than()でO(NlogN)で計算できる
        num = less_than(mid);
        #mid未満の数はnum個である！
        
        #midより小さい数がK個と同じか少なかったらmidが小さすぎる
        if num<K:
            l=mid
        else:
            r=mid
    
    print(l)

def upper_bound(A,X):
    if X<A[0]:
        return 0
    if A[-1]<=X:
        return len(A)
    l=0;r=len(A);mid=0
    while abs(r-l)>1:
        mid = (l+r)//2
        if A[mid]<=X:
            l=mid
        else:
            r=mid
    return r

#Xより少ない数はいくつある？
def less_than(X):
    R=0
    
    if X<0:
        #Xより小さい数はいくつ？？
        #Xより小さい数は、絶対値がXのものより大きい
        #なのでにぶたんでは、絶対値がXより真に大きいものの数を数える必要がある
        #直接この処理を走らせることは困難
        #なので、「絶対値がXのものと同じか小さいもの」の数を数え、それを総数から引くことで数える
        num=0
        for v in Nega:
            num += upper_bound(Posi,X//v)
        num = P_nega-num
        R=num
    
    elif X==0:
        R = P_nega
        
    else:
        #負の数をそのままにぶたんをするとこわれやすい(実装と頭が)
        #なので負の要素を全て正にしておいたもの(Nega2)を用意してそれでにぶたんをした
        
        #Xより小さい数はいくつ？？
        #まず０と負の数は明らかにXより小さい
        R+=P_nega+P_zero;
        #基本的には負の場合と同様の処理をする
        #しかし、正の場合はPosi*Posi,Nega*Negaなので重複をケアする必要がある
        #以下のように処理することでケアができる(図解すると理解が早い)
        num = 0
        for i in range(len(Posi)):
            temp = upper_bound(Posi,(X-1)//Posi[i])
            num += min(temp,i)
        for i in range(len(Nega2)):
            temp = upper_bound(Nega2,(X-1)//Nega2[i])
            num += min(temp,i)
        R += num
    return R

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
stdin = open(0)
INF = 1145141919810893364
#INFはすくなくとも10^18+1は必要(10^9の積を扱うので)

N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().split(), np.int64)

#まず、Aの要素を正、負、０に分ける
Posi = A[A>0]
Nega = A[A<0]
Nega2 = Nega*-1
Zero = A[A==0]
#Zeroの要素は0のみなのであえてvectorで持つ必要はないが、あえてこうしておく

#二分探索できるよう、ソートしておく
Posi = np.sort(Posi)
Nega = np.sort(Nega)
Nega2 = np.sort(Nega2)
Zero = np.sort(Zero)

#次に、N(N-1)/2個ある積のうち、正であるものの個数を求める
#負であるもの、０であるものも同様に求める

#積が正になるもの：ともに正かともに負
#積が負になるもの：正と負の組み合わせ
#積が０になるもの　どちらかが０
P_posi=0;P_nega=0;P_zero=0
P_posi += (len(Posi))*(len(Posi)-1)//2
P_posi += (len(Nega))*(len(Nega)-1)//2

P_nega += (len(Posi))*(len(Nega))

P_zero += (len(Zero))*(len(Zero)-1)//2
P_zero += (len(Zero))*(len(Posi))
P_zero += (len(Zero))*(len(Nega))

def main():
    
    #にぶたん開始
    l = -INF;r=INF;mid=0
    
    while abs(r-l)>1:
        mid=(l+r)//2
        #このにぶたんでは、mid未満の数はいくつあるかを数えたい
        #それは、後述する自作関数less_than()でO(NlogN)で計算できる
        num = less_than(mid);
        #mid未満の数はnum個である！
        
        #midより小さい数がK個と同じか少なかったらmidが小さすぎる
        if num<K:
            l=mid
        else:
            r=mid
    
    print(l)


#Xより少ない数はいくつある？
def less_than(X):
    R=0
    
    if X<0:
        #Xより小さい数はいくつ？？
        num=0
        for v in Nega:
            num += np.searchsorted(Posi, X//v, side='right')
        num = P_nega-num
        R=num
    
    elif X==0:
        R = P_nega
        
    else:
        #負の数をそのままにぶたんをするとこわれやすい(実装と頭が)
        #なので負の要素を全て正にしておいたもの(Nega2)を用意してそれでにぶたんをした
        
        #Xより小さい数はいくつ？？
        #まず０と負の数は明らかにXより小さい
        R+=P_nega+P_zero;
        #基本的には負の場合と同様の処理をする
        #しかし、正の場合はPosi*Posi,Nega*Negaなので重複をケアする必要がある
        #以下のように処理することでケアができる(図解すると理解が早い)
        num = 0
        for i in range(len(Posi)):
            temp = np.searchsorted(Posi, (X-1)//Posi[i], side='right')
            num += min(temp,i)
        for i in range(len(Nega2)):
            temp = np.searchsorted(Nega2, (X-1)//Nega2[i], side='right')
            num += min(temp,i)
        R += num
    return R

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
from itertools import chain, combinations
import json
import numpy as np
import bisect


def main():
    # N = int(input())
    N, K = [int(a) for a in input().split()]
    A = [int(a) for a in input().split()]

    A = sorted(A)
    A = np.array(A)

    l = -(10 ** 18)
    r = 10 ** 18 + 1
    while r != l + 1:
        total = 0
        mid = (r + l) // 2
        for i, a in enumerate(A):
            if a == 0:
                if mid >= 0:
                    pos = N
                else:
                    pos = 0
            else:
                if a < 0:
                    pos = N - bisect.bisect_right(A, (-mid - 1) // -a)
                else:
                    pos = bisect.bisect_right(A, mid // a)

            total += pos

        c = len([0 for a in A if a * a <= mid])
        total -= c
        assert total % 2 == 0
        total //= 2
        if total >= K:
            r = mid
        else:
            l = mid
    print(r)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=input().split(' ')
n=int(n)
k=int(k)
xs=[int(x) for x in input().split(' ')]
s=[]

from heapq import *

for i in range(len(xs)):
    for j in range(i):
        heappush(s, xs[i]*xs[j])
        
for _ in range(k-1):
    heappop(s)

print(heappop(s))

Submission status: Time Limit Exceeded

Solution code:
n,k=input().split(' ')
n=int(n)
k=int(k)
xs=[int(x) for x in input().split(' ')]
s=[]

import sys 
  
def kthSmallest(arr, l, r, k):
    if (k > 0 and k <= r - l + 1): 
        pos = partition(arr, l, r) 
        if (pos - l == k - 1): 
            return arr[pos] 
        if (pos - l > k - 1):
            return kthSmallest(arr, l, pos - 1, k) 
        return kthSmallest(arr, pos + 1, r, 
                            k - pos + l - 1) 
    return sys.maxsize 
  
def partition(arr, l, r): 
  
    x = arr[r] 
    i = l 
    for j in range(l, r): 
        if (arr[j] <= x): 
            arr[i], arr[j] = arr[j], arr[i] 
            i += 1
    arr[i], arr[r] = arr[r], arr[i] 
    return i 

for i in range(len(xs)):
    for j in range(i):
        s.append(xs[i]*xs[j])
        
print(kthSmallest(s, 0, len(s)-1, k))

Submission status: Time Limit Exceeded

Solution code:
n,k=input().split(' ')
k=int(k)
xs=[int(x) for x in input().split(' ')]
s=[]
for i in range(len(xs)):
    for j in range(i):
        s.append(xs[i]*xs[j])
print(sorted(s)[k-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
from itertools import chain, combinations
import json
import numpy as np
import bisect


def main():
    # N = int(input())
    N, K = [int(a) for a in input().split()]
    A = [int(a) for a in input().split()]

    A = sorted(A)

    l = -(10 ** 18)
    r = 10 ** 18 + 1
    while r != l + 1:
        total = 0
        mid = (r + l) // 2
        for i, a in enumerate(A):
            arr = [aa * a for aa in A]
            if a < 0:
                arr = list(reversed(arr))
            pos = bisect.bisect_left(arr, mid)
            total += pos

        c = len([0 for a in A if a * a < mid])
        total -= c
        assert total % 2 == 0
        total //= 2
        if total >= K:
            r = mid
        else:
            l = mid
    print(l)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

INF = 10**18 + 1
def count(A, a, x):
    l = -1
    r = len(A)
    c = (l + r) // 2

    if a > 0:
        while(l + 1 < r):
            if A[c] * a < x:
                l = c
            else:
                r = c
            c = (l + r) // 2
        
        return l + 1
    else:
        while(l + 1 < r):
            if A[c] * a < x:
                r = c
            else:
                l = c
            c = (l + r) // 2

        return len(A) - r

def allCount(A, x):
    cnt = 0
    notCnt = 0
    for a in A:
        cnt += count(A, a, x)
        if a * a < x:
            notCnt += 1
    cnt = (cnt - notCnt) // 2

    return cnt


l = -INF
r = INF
c = (l + r) // 2

while (l + 1 < r):
    cnt = allCount(A, c)
    if cnt < K:
        l = c
    else:
        r = c

    c = (l + r) // 2

print(l)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

INF = 10**18 + 1
def count(A, a, x):
    l = -1
    r = len(A)
    c = (l + r) // 2

    if a > 0:
        while(l + 1 < r):
            if A[c] * a < x:
                l = c
            else:
                r = c
            c = (l + r) // 2
        
        return r
    else:
        while(l + 1 < r):
            if A[c] * a < x:
                r = c
            else:
                l = c
            c = (l + r) // 2

        return len(A) - r

def allCount(A, x):
    cnt = 0
    notCnt = 0
    for a in A:
        cnt += count(A, a, x)
        if a * a < x:
            notCnt += 1
    cnt = (cnt - notCnt) // 2

    return cnt


l = -INF
r = INF
c = (l + r) // 2

while (l + 1 < r):
    cnt = allCount(A, c)
    if cnt < K:
        l = c
    else:
        r = c

    c = (l + r) // 2

print(l)

Submission status: Time Limit Exceeded

Solution code:
#大きな数の割り算は計算重いかも，for文内も掛け算の二分探索に

def main():
    import sys
    input = sys.stdin.readline

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

    #積がX未満になるものがK-1個以下になる最大のXを探す

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

    while ng-ok>1:
        X=(ok+ng)//2
        temp=0

        for i in range(N):
            if A[i]>0:
                #A[i]*A[j]がX未満となるjの個数を数える
                l=-1
                r=N
                while r-l>1:
                    med=(l+r)//2
                    if A[i]*A[med]<X:
                        l=med
                    else:
                        r=med
                temp+=r
                if r>i:
                    temp-=1

            elif A[i]<0:
                #A[i]*A[j]がX未満となるjの個数を数える
                l=-1
                r=N
                while r-l>1:
                    med=(l+r)//2
                    if A[i]*A[med]<X:
                        r=med
                    else:
                        l=med
                temp+=N-r
                if r<=i:
                    temp-=1

            else:
                if X>0:
                    temp+=N-1


        temp=temp//2

        if temp>=K:
            ng=X
        else:
            ok=X

    print(ok)


main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

A.sort()

left=-10**18
right=10**18
count=0

a=bisect.bisect_left(A,0)
b=bisect.bisect_right(A,0)

if b*(n-a)-(b-a)-(b-a)*(b-a-1)//2>=k:
    right=0
else:
    left=1

while right!=left:
    pos=(left+right)//2
    count=0
    for a in A:
        if a==0:
            if pos>=0:
                count+=n-1
        elif a<0:
            i=bisect.bisect_right(A,(-1-pos)//(-a))
            count+=n-i + (-1 if a*a<=pos else 0)
        else:
            i=bisect.bisect_right(A,pos//a)
            count+=i + (-1 if a*a<=pos else 0)
    if count>=2*k:
        right=pos
    else:
        left=pos+1

print(left)

Submission status: Time Limit Exceeded

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

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

M=[]
Z=[]
P=[]

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

M.reverse()

MINUS=len(M)*len(P)
PLUS=len(P)*(len(P)-1)//2+len(M)*(len(M)-1)//2
ZERO=N*(N-1)//2-PLUS-MINUS

if MINUS<K and K<=MINUS+ZERO:
    print(0)
    sys.exit()

if K<=MINUS:
    OK=10**18
    NG=0

    while OK-NG>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(M)):
            while NOW>=0 and mid<M[i]*P[NOW]:
                NOW-=1
            ANS+=len(P)-NOW-1

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(-OK)

else:
    OK=0
    NG=10**18
    K-=MINUS+ZERO

    while NG-OK>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(P)):
            while NOW>0 and mid<=P[i]*P[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        NOW=len(M)-1

        for i in range(len(M)):
            while NOW>0 and mid<=M[i]*M[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(OK)

Submission status: Time Limit Exceeded

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

import numpy as np

A = np.array(A)
A.sort()

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

A = list(A)

import bisect
 
#条件に合うものを重複して数えて後から重複しない組み合わせに変換
def fun(x):
    count = 0
    #xが0より大きいとき、後ろにある0は何個あるか
    if x >= 0:
        count += len(zero)*N
    #xを正で割ったとき、Aの中に何個それより大きいものがあるか
    for i in range(len(pos)):
        count += bisect.bisect_right(A,x//pos[i])
    #xを負で割ったとき、Aの中に何個それより小さいものがあるか(符合が逆転)
    #x+1にする(同じ数字がAにあるから)
    for i in range(len(neg)):
        count += N - bisect.bisect_right(A,(x+1)//neg[i])
    #条件に合う同じ要素を選ぶものを除く    
    for i in range(len(A)):
        if x >= A[i]**2:
            count-=1
    #半分にすれば重複しない組み合わせになる        
    return count//2
 
left = -10**18
right = 10**18
 
#二分探索する
while right - left > 1:
    mid = (left+right)//2
    
    if fun(mid) >= K:
        right = mid
    else:
        left = mid
        
print(right)

Submission status: Time Limit Exceeded

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

pos = []
neg = []
zero = []
 
A.sort()

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] == 0:
        zero.append(A[i])
    else:
        neg.append(A[i])
        
import bisect
 
#条件に合うものを重複して数えて後から重複しない組み合わせに変換
def fun(x):
    count = 0
    #xが0より大きいとき、後ろにある0は何個あるか
    if x >= 0:
        count += len(zero)*N
    #xを正で割ったとき、Aの中に何個それより大きいものがあるか
    for i in range(len(pos)):
        count += bisect.bisect_right(A,x//pos[i])
    #xを負で割ったとき、Aの中に何個それより小さいものがあるか(符合が逆転)
    #x+1にする(同じ数字がAにあるから)
    for i in range(len(neg)):
        count += N - bisect.bisect_right(A,(x+1)//neg[i])
    #条件に合う同じ要素を選ぶものを除く    
    for i in range(len(A)):
        if x >= A[i]**2:
            count-=1
    #半分にすれば重複しない組み合わせになる        
    return count//2
 
left = -10**18
right = 10**18
 
#二分探索する
while right - left > 1:
    mid = (left+right)//2
    
    if fun(mid) >= K:
        right = mid
    else:
        left = mid
        
print(right)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc155/tasks/abc155_d


def main():
    n, k = map(int, input().split(" "))
    M = []
    Z = []
    P = []
    for s in input().split(" "):
        i = int(s)
        if i == 0:
            Z.append(i)
        elif i < 0:
            M.append(i)
        else:
            P.append(i)
    m = len(M)
    z = len(Z)
    p = len(P)
    minus_range = m * p
    zero_range = (m * z) + (p * z) + (z * (z - 1) // 2)
    plus_range = (m * (m - 1) / 2) + (p * (p - 1) // 2)
    if k <= minus_range:
        # only M * P
        array = []
        for i in M:
            for j in P:
                array.append(i * j)
        array.sort()
        print(array[k - 1])
    elif k <= minus_range + zero_range:
        print("0")
    else:
        # only M * M and P * P
        array = []
        for i in range(m - 1):
            for j in range(i + 1, m):
                array.append(M[i] * M[j])
        for i in range(p - 1):
            for j in range(i + 1, p):
                array.append(P[i] * P[j])
        array.sort()
        print(array[k - minus_range - zero_range - 1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]

A.sort()

# 積がx未満となる組み合わせの数を求める
def n_prod_lt(x):
    n_prod = 0
    for i in range(n - 1): # A[0], A[1], ..., A[n-2]について
        n_prod += n_partner(i, x)
    return n_prod

# i > jであるjのうち、A[i] * A[j] < xとなるjの数
def n_partner(i, x):
    if A[i] > 0:
        if A[i] * A[i + 1] >= x:
            ans = 0
        elif A[i] * A[n - 1] < x:
            ans = n - 1 - i
        else:
            ok = i + 1
            ng = n - 1
            while ng - ok > 1:
                mid = (ng + ok) // 2
                if A[i] * A[mid] < x:
                    ok = mid
                else:
                    ng = mid
            ans = ok - i
    else:
        if A[i] * A[i + 1] < x:
            ans = n - 1 - i
        elif A[i] * A[n - 1] >= x:
            ans = 0
        else:
            ng = i + 1
            ok = n - 1
            while ok - ng > 1:
                mid = (ng + ok) // 2
                if A[i] * A[mid] < x:
                    ok = mid
                else:
                    ng = mid
            ans = n - 1 - ng
    return(ans)

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

while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_prod_lt(mid) < k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 解説放送の改変
# aを負0正に分けて処理

def main():
    inf = 10 ** 18 + 1

    def bs_kth_lt_0():
        def negative(e):
            ok, ng = len_p, -1
            cand_ = -cand
            while ok - ng > 1:
                mid = (ng + ok) // 2
                if p[mid] * e > cand_:  # -cand:
                    ok = mid
                else:
                    ng = mid
            return len_p - ok
            # [ok,n)の区間が
            # a[ok] * e < cand を満たす
            # 区間の長さ n - ok = 積がcand未満という条件を満たす候補数になる
            # 同じもの同士のペアやペアの二重計上があるので、あとで減らす

        ok, ng = -inf, 0
        while ng - ok > 1:
            cand = (ng + ok) // 2
            tot = sum(negative(e) for e in m)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

    def bs_kth_gt_0():
        def positive(e, lis):
            ok, ng = -1, len(lis)
            while ng - ok > 1:
                mid = (ng + ok) // 2
                if lis[mid] * e < cand:
                    ok = mid
                else:
                    ng = mid
            return ok + 1
            # [0,ok]の区間が
            # a[ok] * e < cand を満たす
            # ok は 0-indexed なので 1-indexed に直すと、
            # 区間の長さ = 積がcand未満という条件を満たす候補数になる
            # 同じもの同士のペアやペアの二重計上があるので、あとで減らす

        def is_ok(cand):
            tot = 0
            for e in m:
                tot += positive(e, m)
                if e * e < cand:
                    tot -= 1  # 同じもの同士のペアを減らす
            for e in p:
                tot += positive(e, p)
                if e * e < cand:
                    tot -= 1  # 同じもの同士のペアを減らす
            tot //= 2  # (1,2),(2,1)のような同一ペアの二重計上を減らす
            return tot < k

        ok, ng = 0, inf
        while ng - ok > 1:
            cand = (ng + ok) // 2
            if is_ok(cand):
                ok = cand
            else:
                ng = cand
        return ok

    n, k = map(int, input().split())
    a = map(int, input().split())

    m, z, p = [], [], []
    for x in a:
        if x < 0:
            m.append(x)
        elif x == 0:
            z.append(x)
        else:
            p.append(x)

    *m, = sorted(-x for x in m)  # 正に符号変換して昇順ソート
    p.sort()

    len_m = len(m)
    len_z = len(z)
    len_p = len(p)

    cnt_m = len_m * len_p
    cnt_z = len_z * (len_z - 1) // 2 + len_z * (n - len_z)

    if k <= cnt_m:
        # k番目の値は負
        ans = bs_kth_lt_0()
        print(ans)
        return

    elif k <= cnt_m + cnt_z:
        # k番目の値は0
        print(0)
        return
    else:
        # k番目の値は正
        k -= cnt_m + cnt_z  # 正の値の中での順位に直す

        ans = bs_kth_gt_0()
        print(ans)
        return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

pos = []
neg = []
zero = []

A.sort()

A2 = [A[i]**2 for i in range(N)] 
A2.sort()
for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] == 0:
        zero.append(A[i])
    else:
        neg.append(A[i])
      
import bisect


#条件に合うものを重複して数えて後から重複しない組み合わせに変換
def fun(x):
    count = 0
    #xが0より大きいとき、後ろにある0は何個あるか
    if x >= 0:
        count += len(zero)*N
    #xを正で割ったとき、Aの中に何個それより大きいものがあるか
    for i in range(len(pos)):
        count += bisect.bisect_right(A,x//pos[i])
    #xを負で割ったとき、Aの中に何個それより小さいものがあるか(符合が逆転)
    #x+1にする(同じ数字がAにあるから)
    for i in range(len(neg)):
        count += N - bisect.bisect_right(A,(x+1)//neg[i])
    #条件に合う同じ要素を選ぶものを除く    
    count -= bisect.bisect_right(A2,x)
    #半分にすれば重複しない組み合わせになる        
    return count//2

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

#二分探索する
while right - left > 1:
    mid = (left+right)//2
    
    if fun(mid) >= K:
        right = mid
    else:
        left = mid
        
print(right)

Submission status: Time Limit Exceeded

Solution code:
# 解説放送の改変
# aを負0正に分けて処理

def main():
    from bisect import bisect_left

    def bs_kth_lt_0():
        inf = 10 ** 18 + 1
        n = len(p)

        def negative(e):
            ok, ng = n, -1  # len(p), -1
            cand_ = -cand
            while ok - ng > 1:
                mid = (ng + ok) // 2
                if p[mid] * e > cand_:  # -cand:
                    ok = mid
                else:
                    ng = mid
            return n - ok  # len(p) - ok
            # [ok,n)の区間が
            # a[ok] * e < cand を満たす
            # 区間の長さ n - ok = 積がcand未満という条件を満たす候補数になる
            # 同じもの同士のペアやペアの二重計上があるので、あとで減らす

        ok, ng = -inf, 0
        while ng - ok > 1:
            cand = (ng + ok) // 2
            tot = sum(negative(e) for e in m)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

    def bs_kth_gt_0():
        inf = 10 ** 18 + 1

        def positive(e, lis):
            ok, ng = -1, len(lis)
            while ng - ok > 1:
                mid = (ng + ok) // 2
                if lis[mid] * e < cand:
                    ok = mid
                else:
                    ng = mid
            return ok + 1
            # [0,ok]の区間が
            # a[ok] * e < cand を満たす
            # ok は 0-indexed なので 1-indexed に直すと、
            # 区間の長さ = 積がcand未満という条件を満たす候補数になる
            # 同じもの同士のペアやペアの二重計上があるので、あとで減らす

        def is_ok(cand):
            tot = 0
            for lis in (m, p):
                for e in lis:
                    tot += positive(e, lis)
                    if e * e < cand:
                        tot -= 1  # 同じもの同士のペアを減らす
            tot //= 2  # (1,2),(2,1)のような同一ペアの二重計上を減らす
            return tot < k

        ok, ng = 0, inf
        while ng - ok > 1:
            cand = (ng + ok) // 2
            if is_ok(cand):
                ok = cand
            else:
                ng = cand
        return ok

    n, k = map(int, input().split())
    *a, = sorted(map(int, input().split()))

    i = bisect_left(a, 0)
    j = bisect_left(a, 1)
    m, z, p = a[:i], a[i:j], a[j:]

    *m, = sorted(-x for x in m)  # 正に符号変換して昇順ソート

    cnt_m = len(m) * len(p)
    cnt_z = len(z) * (len(z) - 1) // 2 + len(z) * (n - len(z))

    if k <= cnt_m:
        # k番目の値は負
        ans = bs_kth_lt_0()
        print(ans)
        return

    elif k <= cnt_m + cnt_z:
        # k番目の値は0
        print(0)
        return
    else:
        # k番目の値は正
        k -= cnt_m + cnt_z  # 正の値の中での順位に直す

        ans = bs_kth_gt_0()
        print(ans)
        return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説放送の改変
# aを負0正に分けて処理

def main():
    from bisect import bisect_left

    def bs_kth_lt_0():
        inf = 10 ** 18 + 1

        def negative(e):
            ok, ng = len(p), -1
            while abs(ng - ok) > 1:
                mid = (ng + ok) // 2
                if p[mid] * e > -cand:
                    ok = mid
                else:
                    ng = mid
            return len(p) - ok
            # [ok,n)の区間が
            # a[ok] * e < cand を満たす
            # 区間の長さ n - ok = 積がcand未満という条件を満たす候補数になる
            # 同じもの同士のペアやペアの二重計上があるので、あとで減らす

        ok, ng = -inf, 0
        while abs(ng - ok) > 1:
            cand = (ng + ok) // 2
            tot = sum(negative(e) for e in m)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

    def bs_kth_gt_0():
        inf = 10 ** 18 + 1

        def positive(e, lis):
            ok, ng = -1, len(lis)
            while abs(ng - ok) > 1:
                mid = (ng + ok) // 2
                if lis[mid] * e < cand:
                    ok = mid
                else:
                    ng = mid
            return ok + 1
            # [0,ok]の区間が
            # a[ok] * e < cand を満たす
            # ok は 0-indexed なので 1-indexed に直すと、
            # 区間の長さ = 積がcand未満という条件を満たす候補数になる
            # 同じもの同士のペアやペアの二重計上があるので、あとで減らす

        def is_ok(cand):
            tot = 0
            for lis in (m, p):
                for e in lis:
                    tot += positive(e, lis)
                    if e * e < cand:
                        tot -= 1  # 同じもの同士のペアを減らす
            tot //= 2  # (1,2),(2,1)のような同一ペアの二重計上を減らす
            return tot < k

        ok, ng = 0, inf
        while abs(ng - ok) > 1:
            cand = (ng + ok) // 2
            if is_ok(cand):
                ok = cand
            else:
                ng = cand
        return ok

    n, k = map(int, input().split())
    *a, = sorted(map(int, input().split()))

    i = bisect_left(a, 0)
    j = bisect_left(a, 1)
    m, z, p = a[:i], a[i:j], a[j:]

    *m, = sorted(-x for x in m)  # 正に符号変換して昇順ソート

    cnt_m = len(m) * len(p)
    cnt_z = len(z) * (len(z) - 1) // 2 + len(z) * (n - len(z))

    if k <= cnt_m:
        # k番目の値は負
        ans = bs_kth_lt_0()
        print(ans)
        return

    elif k <= cnt_m + cnt_z:
        # k番目の値は0
        print(0)
        return
    else:
        # k番目の値は正
        k -= cnt_m + cnt_z  # 正の値の中での順位に直す

        ans = bs_kth_gt_0()
        print(ans)
        return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**20

# 一方をpに固定したとき、積がx未満になるペアの個数
def f(p, x, n, a):
    if p > 0:
        l = -1
        r = n
        while l + 1 < r:
            mid = (l + r) // 2
            if p * a[mid] < x:
                l = mid
            else:
                r = mid
        return l+1
    else:
        l = -1
        r = n
        while l + 1 < r:
            mid = (l + r)//2
            if p * a[mid] < x:
                r = mid
            else:
                l = mid
        return n-r

# x未満になる組み合わせ数がk未満ならTrue
def is_under(x, k, n, a):
    ans = 0
    for c in a:
        ans += f(c, x, n, a)
        if c**2 < x:
            ans -= 1
    ans /= 2
    return ans < k

def main():
    n, k = list(map(int, input().strip().split()))
    a = sorted(list(map(int, input().strip().split())))
    l = -INF
    r = INF
    while l + 1 < r:
        mid = (l+r)//2
        if is_under(mid, k, n, a):
            l = mid
        else:
            r = mid
    print(l)

if __name__ == '__main__':
    main()