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:
def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res


def search_count(A, a, q):
    left = -1
    right = N

    if a == 0:
        if q > 0:
            return N
        else:
            return 0
    elif a > 0:
        while left+1 < right:
            i = (left+right)//2
            if A[i]*a < q:
                left = i
            else:
                right = i
        return left+1
    else:
        while left+1 < right:
            i = (left+right)//2
            if A[i]*a < q:
                right = i
            else:
                left = i
        return N-right

# N=7
# print(search_count([-2,-1,1,2,3, 4, 5], -1, 2))
# #-2(l=0) -1(r=1) 1() 2 3
# 2(l=0) 1(r=1) -1 -2 -3 -4 -5
# exit()


# 1 1 2 3(K=4) 3 4

N, K = l_in()
A = l_in()
A.sort()

inf = int(1e18)+1
# inf = 10
ql = int(-inf)
qr = int(inf)

while ql + 1 < qr:
    q = (ql + qr)//2
    r = 0
    for a in A:
        r += search_count(A, a, q)
        # print(a, q, search_count(A, a, q))
        if a*a < q:
            r -= 1
    r //= 2

    # r = q未満のペア個数
    # res = 12, K = 4
     # -inf(r=0) 10 11 12(r = 4) | 13(r = 5) 14 inf(r=N)
    # print(ql, q, qr, r)

    if r < K:
        ql = q
    else:
        qr = q


print(ql)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N,K=map(int,input().split())
A=list(map(int,input().split()))
ans=[]
for i in combinations(A,2):
    ans.append(i[0]*i[1])
print(sorted(ans)[K-1])

Submission status: Time Limit Exceeded

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

def ok(x):
    res = 0
    for i in range(N):
        if A[i]<0:
            left, right = -1, N
            while left + 1 < right:
                c = (left + right) // 2
                if A[c]*A[i] < x: right = c
                else:             left  = c
            res += N - right
        else:
            left, right = -1, N
            while left + 1 < right:
                c = (left + right) // 2
                if A[c]*A[i] < x: left  = c
                else:             right = c
            res += right
        if A[i]*A[i] < x:
            res -= 1
    res //= 2
    return res < K

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

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

while left+1 < right:
    num = (left+right)//2
    
    less_count = 0
    for a in A:
        if a < 0:
            limit_pair = -(-num // a)
            limit_idx = np.searchsorted(A, limit_pair, side='left')
            if a ** 2 <= num:
                less_count -= 1
            less_count += n - limit_idx
        
        elif a == 0:
            if num >= 0:
                less_count += n-1
        
        elif a > 0:
            limit_pair = num // a
            limit_idx = np.searchsorted(A, limit_pair, side='right')
            if a ** 2 <= num:
                less_count -= 1
            less_count += limit_idx
    
    less_count //= 2
    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
L = -10**18-1
R = 10**18+1
while L+1 < R:
    M = (L+R)//2
    total = 0
    for i in range(n):
        l = -1
        r = n
        if a[i] < 0:
            while l+1 < r:
                m = (l+r)//2
                if a[m] * a[i] < M:
                    r = m
                else:
                    l = m
            total += n-r
        else:
            while l+1 < r:
                m = (l+r)//2
                if a[m] * a[i] < M:
                    l = m
                else:
                    r = m
            total += r
        if a[i]*a[i] < M: total -= 1
    total //= 2
    if total < k:
        L = M
    else:
        R = M
print(L)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = map(int, input().split())
a = list(a)
d = []
for i in range(n-1):
    for j in range(i+1, n):
        d.append(a[i]*a[j])
d.sort()
print(d[k-1])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
l = -10**18-1
r = 10**18+1

while l+1 < r:
    x = (l + r) // 2
    total = 0
    for i in range(n):
        l1, r1 = -1, n
        if(a[i] < 0):
            while(l1+1 < r1):
                c = (l1 + r1) // 2
                if a[c] * a[i] < x:
                    r1 = c
                else:
                    l1 = c
            total += n-r1
        else: # a[i] => 0
            while l1+1 < r1:
                c = (l1 + r1) // 2
                if a[c] * a[i] < x:
                    l1 = c
                else:
                    r1 = c
            total += r1
        if a[i] * a[i] < x:
            total -= 1
    total /= 2
    if total < k:
        l = x
    else:
        r = x
print(l)

Submission status: Time Limit Exceeded

Solution code:
import itertools as iters

N,K = [int(i) for i in input().rstrip().split()]
A = [int(i) for i in input().rstrip().split()]
S = []

for a,b in iters.combinations(A,2):
    S += [a*b]
print(sorted(S)[K-1])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
l = -10**100-1
r = 10**100+1

while l+1 < r:
    x = (l + r) // 2
    total = 0
    for i in range(n):
        l1, r1 = -1, n
        if(a[i] < 0):
            while(l1+1 < r1):
                c = (l1 + r1) // 2
                if a[c] * a[i] < x:
                    r1 = c
                else:
                    l1 = c
            total += n-r1
        else: # a[i] => 0
            while l1+1 < r1:
                c = (l1 + r1) // 2
                if a[c] * a[i] < x:
                    l1 = c
                else:
                    r1 = c
            total += r1
        if a[i] * a[i] < x:
            total -= 1
    total /= 2
    if total < k:
        l = x
    else:
        r = x
print(l)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
arr = list(map(int, input().split()))
arr = sorted(arr)

nc = 0
zc = 0
pc = 0

# count negative value, zero and positive value
for i in range(n):
    if arr[i] < 0:
        nc += 1
    elif arr[i] == 0:
        zc += 1
    else:
        pc += 1

# count negative pair and so on 
ncc = nc * pc
zcc = zc * (nc + pc) + (zc * (zc - 1)) // 2
pcc = (nc * (nc - 1)) // 2 + (pc * (pc - 1)) // 2

# when k is less than ncc
if k <= ncc:
    # sort absolute value
    arr1 = [] # negative absolute
    arr2 = []
    for i in range(n):
        if arr[i] < 0:
            arr1.append(-arr[i])
        elif arr[i] > 0:
            arr2.append(arr[i])
    arr1 = arr1[::-1]
    c1 = len(arr1)
    c2 = len(arr2)
    l = 0
    r = 10 ** 18 + 1
    k = ncc - k

    # binary search
    while r - l != 1:
        mid = (l + r) // 2
        cnt = 0
        pos = c2 - 1
        # しゃくとり法
        for i in range(c1):
            while pos != -1:
                if arr2[pos] > mid // arr1[i]:
                    pos -= 1
                else:
                    break
            cnt += pos + 1
        if cnt > k:
            r = mid
        else:
            l = mid
    print(-r)
elif k <= (ncc + zcc):
    print(0)
else:
    arr1 = []
    arr2 = []
    for i in range(n):
        if arr[i] < 0:
            arr1.append(-arr[i])
        elif arr[i] > 0:
            arr2.append(arr[i])
    arr1 = arr1[::-1]
    c1 = len(arr1)
    c2 = len(arr2)
    l = 0
    r = 10 ** 18 + 1
    k -= (ncc + zcc)
    while r - l != 1:
        mid = (l + r) // 2
        cnt1 = 0
        pos1 = c1 - 1
        for i in range(c1):
            tmp = 0
            while pos1 != -1:
                if arr1[pos1] > mid // arr1[i]:
                    pos1 -= 1
                else:
                    break
            tmp += pos1 + 1
            if arr1[i] ** 2 < mid:
                tmp -= 1
            cnt1 += tmp
        cnt1 = cnt1 // 2
        cnt2 = 0
        pos2 = c2 - 1
        for i in range(c2):
            tmp = 0
            while pos2 != -1:
                if arr2[pos2] > mid // arr2[i]:
                    pos2 -= 1
                else:
                    break
            tmp += pos2 + 1
            if arr2[i] ** 2 < mid:
                tmp -= 1
            cnt2 += tmp
        cnt2 = cnt2 // 2
        cnt = cnt1 + cnt2
        if cnt >= k:
            r = mid
        else:
            l = mid
    print(r)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 18 + 1

a.sort()


def f(x):
    total = 0
    for e in a:
        l = -1
        r = n
        if e < 0:
            while r - l > 1:
                m = (l + r) // 2
                if e * a[m] < x:
                    r = m
                else:
                    l = m

            total += n - r

        else:
            while r - l > 1:
                m = (l + r) // 2
                if e * a[m] < x:
                    l = m
                else:
                    r = m

            total += r

        if e * e < x:
            total -= 1

    total //= 2

    return total < k


l = -INF
r = INF

while r - l > 1:
    m = (l + r) // 2
    if f(m):
        l = m
    else:
        r = m

ans = l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
xy = [int(x) for x in input().split()]

re = []
for l in range(N-1):
    for r in range(l+1,N):
        re.append(xy[l]*xy[r])
        r +=1

re.sort()
print(re[K-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
def getlist2():
    return [int(x) * 100000 for x in input().split()]
import math
import bisect
import heapq
from decimal import Decimal
# from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15

def judge(nums, k, cand, n):
    ll, rr = 0,0
    for num in nums:
        if num == 0:
            if cand == 0:
                rr += n - 1
            elif cand > 0:
                ll += n - 1
                rr += n - 1
        else:
            l = bisect.bisect_left(nums, Decimal(cand)/Decimal(num))
            r = bisect.bisect_right(nums, Decimal(cand)/Decimal(num))
            if num > 0:
                if num < cand/num:
                    l -= 1
                if num <= cand/num:
                    r -= 1
                ll += l
                rr += r
            else:
                if num > cand/num:
                    r += 1
                if num >= cand/num:
                    l += 1
                ll += n - r
                rr += n - l
        # print(ll, rr, num)

    rr /= 2
    ll /= 2
    # print(ll, rr)
    if rr != ll and rr >= k and ll < k:
        return 0
    elif ll >= k:
        return -1
    else:
        return 1

"""
448283280358331113/834475626
10 46
5 4 3 2 -1 0 0 0 0 0
"""

def main():
    n, k = getlist()
    nums = getlist()
    nums.sort()
    mx = 10 ** 32
    mn = -(10 ** 32)
    while(mx - mn > 1):
        mid = (mx + mn) // 2
        # mid = 448283280358331064
        # print(mid)
        state = judge(nums, k, mid, n)
        if state == 0:
            print(mid)
            # print(mx, mn)
            return
        elif state == 1:
            mn = mid
        else:
            mx = mid
    # print(448283280358331064 / 537203564)
    # print("=====================")
    if judge(nums, k, mx, n) == 0:
        print(mx)
        return
    else:
        print(mn)
        return

if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Time Limit Exceeded

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

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

r = []
for i in range(N):
  for j in range(i+1,N):
    r.append(A[i]*A[j])

print(sorted(r)[K-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, K = map(int, input().split())
A = list(map(int, input().split()))
comb = itertools.combinations(A, 2)
res = []
for x in comb:
    res.append(x[0] * x[1])
res.sort()
print(res[K-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from heapq import heappop, heappush
m = []
n, k = map(int, input().split())
a = map(int, input().split())
for c0, c1 in combinations(a, 2):
    heappush(m, c0 * c1)
for _ in range(k):
    ans = heappop(m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
x = list(map(int, input().split()))
numbers = list(map(int, input().split()))
 
answers = [numbers[i]*numbers[j] for i in range(x[0]) for j in range(x[0]) if i<j]

sort=answers.sort()
sort
print(answers[x[1]-1])

Submission status: Time Limit Exceeded

Solution code:
x = list(map(int, input().split()))
numbers = list(map(int, input().split()))
 
answers = [numbers[i]*numbers[j] for i in range(x[0]) for j in range(x[0]) if i<j]

sort=answers.sort()
sort
print(answers[x[1]-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    P = []
    Z = 0
    N = []
    for a in A:
        if a == 0:
            Z += 1
        elif a < 0:
            N.append(a)
        else:
            P.append(a)
    N.sort()
    P.sort()

    NN = len(N) * len(P)
    ZN = len(N) * Z + len(P) * Z + Z * (Z-1) // 2
    if M <= NN:
        def f(n):
            ans = 0
            for nn in N:
                m = -(n // -nn)
                i = len(P) - bisect.bisect_left(P, m)
                ans += i
            return ans
        bs = Bisect(f)

        return bs.bisect_right(M-1, -INF, 0)

    elif M <= NN + ZN:
        return 0
    else:
        M -= NN + ZN
        N = [-v for v in N]
        N.reverse()

        def f(n):
            ans = 0
            if N:
                i = bisect.bisect_right(N, n//N[0])
                for nn in N:
                    m = n // nn
                    while i != 0 and N[i-1] > m:
                        i -= 1
                    ans += i
                    if i > 0 and N[i-1] >= nn:
                        ans -= 1
            if P:
                i = bisect.bisect_right(P, n//P[0])
                for pn in P:
                    m = n // pn
                    while i != 0 and P[i-1] > m:
                        i -= 1
                    ans += i
                    if i > 0 and P[i-1] >= pn:
                        ans -= 1
            ans //= 2
            return ans
        bs = Bisect(f)
        return bs.bisect_right(M-1, 1, INF)

def f(N, M, A):
    ans = []
    for i in range(N):
        for j in range(i+1, N):
            ans.append((A[i]*A[j], A[i], A[j]))
    ans.sort()
    for i, r in enumerate(ans):
        print(i, r)

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n, k = map(int, input().split())
a = map(int, input().split())
m = sorted(c[0] * c[1] for c in combinations(a, 2))
print(m[k - 1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
f=[]
for i in range(n-1):
    for j in range(i+1,n):
        f.append(a[i]*a[j])
print(sorted(f)[k-1])

Submission status: Time Limit Exceeded

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

    left_target=-10**18
    right_target=10**18+1
    while left_target<right_target-1:
        mid_target=(left_target+right_target)//2
        count=0
        for i in range(N):
            a=A[i]
            if a<0:
                left_index=-1
                right_index=N
                while left_index<right_index-1:
                    mid_index=(left_index+right_index)//2
                    if a*A[mid_index]>=mid_target:
                        left_index=mid_index
                    else:
                        right_index=mid_index
                count+=N-(left_index+1)
            else:
                left_index=-1
                right_index=N
                while left_index<right_index-1:
                    mid_index=(left_index+right_index)//2
                    if a*A[mid_index]<mid_target:
                        left_index=mid_index
                    else:
                        right_index=mid_index
                count+=left_index+1

            if a*a<mid_target:
                count-=1
        count//=2
        if count<K:
            left_target=mid_target
        else:
            right_target=mid_target
    print(left_target)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
"""
def binary_search_m(i,a,N,A,mid_target):
    left_index=-1
    right_index=N
    while left_index<right_index-1:
        mid_index=(left_index+right_index)//2
        if a*A[mid_index]>=mid_target:
            left_index=mid_index
        else:
            right_index=mid_index
    return N-(left_index+1)

def binary_search_p(i,a,N,A,mid_target):
    left_index=-1
    right_index=N
    while left_index<right_index-1:
        mid_index=(left_index+right_index)//2
        if a*A[mid_index]<mid_target:
            left_index=mid_index
        else:
            right_index=mid_index
    return left_index+1
"""
def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()

    left_target=-10**18
    right_target=10**18+1
    while left_target<right_target-1:
        mid_target=(left_target+right_target)//2
        count=0
        for i in range(N):
            a=A[i]
            if a<0:
                left_index=-1
                right_index=N
                while left_index<right_index-1:
                    mid_index=(left_index+right_index)//2
                    if a*A[mid_index]>=mid_target:
                        left_index=mid_index
                    else:
                        right_index=mid_index
                count+=N-(left_index+1)
            else:
                left_index=-1
                right_index=N
                while left_index<right_index-1:
                    mid_index=(left_index+right_index)//2
                    if a*A[mid_index]<mid_target:
                        left_index=mid_index
                    else:
                        right_index=mid_index
                count+=left_index+1

            if a*a<mid_target:
                count-=1
        count//=2
        if count<K:
            left_target=mid_target
        else:
            right_target=mid_target
    print(left_target)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    P = []
    Z = 0
    N = []
    for a in A:
        if a == 0:
            Z += 1
        elif a < 0:
            N.append(a)
        else:
            P.append(a)
    N.sort()
    P.sort()


    NN = len(N) * len(P)
    ZN = len(N) * Z + len(P) * Z + Z * (Z-1) // 2
    if M <= NN:
        def f(n):
            ans = 0
            for nn in N:
                m = -(n // -nn)
                i = len(P) - bisect.bisect_left(P, m)
                ans += i
            return ans
        bs = Bisect(f)

        return bs.bisect_right(M-1, -INF, 0)

    elif M <= NN + ZN:
        error_print('zero')
        return 0
    else:
        M -= NN + ZN
        N = [-v for v in N]
        N.reverse()
        def f(n):
            ans = 0
            for nn in N:
                m = n // nn
                i = bisect.bisect_right(N, m)
                if i > 0 and N[i-1] >= nn:
                    i -= 1
                ans += i
            for pn in P:
                m = n // pn
                i = bisect.bisect_right(P, m)
                if i > 0 and P[i-1] >= pn:
                    i -= 1
                ans += i
            ans //= 2
            return ans
        bs = Bisect(f)
        return bs.bisect_right(M-1, 1, INF)

def f(N, M, A):
    ans = []
    for i in range(N):
        for j in range(i+1, N):
            ans.append((A[i]*A[j], A[i], A[j]))
    ans.sort()
    for i, r in enumerate(ans):
        print(i, r)

def main():
    N, M = read_int_n()
    A = read_int_n()

    # N = 2 * 10**5
    # M = random.randint(1, N*(N-1)//2)
    # A = [random.randint(-10**9, 10**9) for _ in range(N)]
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def binary_search_m(i,a,N,A,mid_target):
    left_index=-1
    right_index=N
    while left_index<right_index-1:
        mid_index=(left_index+right_index)//2
        if a*A[mid_index]>=mid_target:
            left_index=mid_index
        else:
            right_index=mid_index
    return N-(left_index+1)

def binary_search_p(i,a,N,A,mid_target):
    left_index=-1
    right_index=N
    while left_index<right_index-1:
        mid_index=(left_index+right_index)//2
        if a*A[mid_index]<mid_target:
            left_index=mid_index
        else:
            right_index=mid_index
    return left_index+1

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

    left_target=-10**18
    right_target=10**18+1
    while left_target<right_target-1:
        mid_target=(left_target+right_target)//2
        count=0
        for i in range(N):
            a=A[i]
            if a<0:
                count+=binary_search_m(i,a,N,A,mid_target)
            elif a>=0:
                count+=binary_search_p(i,a,N,A,mid_target)

            if a*a<mid_target:
                count-=1
        count//=2
        if count<K:
            left_target=mid_target
        else:
            right_target=mid_target
    print(left_target)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

from bisect import bisect_right

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    zero_count = 0
    plus = []
    minus = []

    for i in range(N):
        if A[i] == 0:
            zero_count += 1
        elif A[i] >0 :
            plus.append(A[i])
        else:
            minus.append(A[i])

    zero_count = zero_count*(zero_count-1)//2+len(plus)*zero_count+len(minus)*zero_count
    minus_count = len(minus)*len(plus)

    if minus_count<K<=minus_count+zero_count:
        print(0)
        return
    elif K <= minus_count:
        left = -10**18-1
        right = 0

        while right - left > 1:
            mid = (right + left) //2
            ## mid 以下になる組み合わせがkこ以上あるか
            count = 0
            j = 0
            # 尺取り
            for i in range(len(plus)):
                while j < len(minus) and plus[i]*minus[j]<=mid:
                    j+=1 
                count += j
            
            if count >= K:
                right = mid
            else:
                left = mid
        print(right)

    else:
        K -= (minus_count+zero_count)
        left = -1
        right = 10**18+1

        for i in range(len(minus)):
            minus[i] = -minus[i]
        minus = minus[::-1]        

        while right - left > 1:
            mid = (right + left) //2
            ## mid 以下になる組み合わせがkこ以上あるか
            count = 0
            j = 0
            ## plus
            for i in range(len(plus)-1,-1,-1):
                if plus[i]**2 <= mid:
                    count -= 1

                while j < len(plus) and plus[i]*plus[j] <= mid:
                    j += 1
                count += j
            
            ## minus
            j = 0
            for i in range(len(minus)-1,-1,-1):
                if minus[i]**2 <= mid:
                    count -= 1
                while j < len(minus) and minus[i]*minus[j] <= mid:
                    j += 1
                count += j
            
            if count//2 >= K:
                right = mid
            else:
                left = mid
        print(right)


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.sort()
Nn = bisect.bisect_left(A, 0) # 負の数の数
Nz = bisect.bisect_left(A, 1) - Nn # 0の数
Np = N - Nn - Nz # 正の数の数
An = A[:Nn]
Ap = A[Nn+Nz:]


if Nn*Np >= K: # 答えが負の数
  left = -10**18-1 # False
  right = -1 # True
  n = Nn*Np - K # midより大きくなるのがn個より多いとmid以下のペアがK個以上にならない
  while left+1 < right:
    mid = (left+right) // 2
    i = j = 0
    c = 0
    while i < Nn and j < Np:
      if An[i]*Ap[j] > mid:
        c += 1
        j += 1
        if j >= Np:
          c += (Nn - 1 - i)*Np
      else:
        c += j
        i += 1
      if c > n:
        break
    if c > n:
      left = mid
    else:
      right = mid
  ans = right 
elif Nn*Np + Nz*(Nn+Np) + Nz*(Nz-1)//2 >= K: # 答えが0
  ans = 0
else: # 答えが正
  An = [-an for an in An][::-1]
  N = Nn*(Nn-1)//2 + Np*(Np-1)//2 # 積が正となる組合せ
  k = K - Nn*Np - Nz*(Nn+Np) - Nz*(Nz-1)//2 # 正の数の中でk番目に小さい数が答え
  n = N - k
  left = 0 # False
  right = 10**18 + 1 # True
  while left+1 < right:
    mid = (left+right) // 2
    i = 0
    j = Nn - 1
    c = 0
    while i < j:
      if An[i]*An[j] > mid:
        c += 1
        j -= 1
      else:
        c += Nn - 1 - j
        i += 1
      if i == j:
          c += (Nn-i-1)*(Nn-i-2) // 2
      if c > n:
        break
    
    if c > n:
      left = mid
    else:
      i = 0
      j = Np - 1
      while i < j:
        if Ap[i]*Ap[j] > mid:
          c += 1
          j -= 1
        else:
          c += Np - 1 - j
          i += 1
        if i == j:
            c += (Np-i-1)*(Np-i-2) // 2
        if c > n:
          break
      if c > n:
        left = mid
      else:
        right = mid
  ans = right


print(ans)