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 main():
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
 
    import bisect
    def ok(x):
        # x以下になる組み合わせがk個以上
        cnt = 0
        for a in A:
            if a*a <= x:
                cnt -= 1
            if a > 0:
                c = x//a
                cnt += bisect.bisect_right(A, c)
            elif a < 0:
                c = (-x-1)//(-a)
                cnt += n - bisect.bisect_right(A, c)
            else:
                if x >= 0:
                    cnt += n
        cnt = cnt//2
        if cnt >= k:
            return True
        else:
            return False
 
    l = -10**18-1
    r = 10**18+1
    while l+1 < r:
        m = (l+r)//2
        if ok(m):
            r = m
        else:
            l = m
    print(r)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,K=map(int,input().split())
A=list(map(int,input().split()))
h=[]
heapq.heapify(h)
for i in range(N-1):
  a=A[i]
  for j in range(i+1,N):
    heapq.heappush(h,a*A[j])
for _ in range(K-1):
  heapq.heappop(h)
print(heapq.heappop(h))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,K=map(int,input().split())
A=sorted(map(int,input().split()))
for i in range(N):
    if A[i]>=0:
        break
minus=i
for i in range(i,N):
    if A[i]>0:
        break
zero=i-minus
plus=N-zero-minus
if minus*plus>=K:
    h=[]
    heapq.heapify(h)
    for a in A[:minus]:
        for b in A[minus+zero:]:
            heapq.heappush(h,a*b)
    for _ in range(K-1):
        heapq.heappop(h)
    print(heapq.heappop(h))
    exit()
K-=minus*plus
if zero!=0:
    for i in range(zero):
        K-=N-zero+i
    if K<=0:
        print(0)
        exit()
h=[]
heapq.heapify(h)
for i in range(minus+zero,N-1):
    for j in range(i+1,N):
        heapq.heappush(h,A[i]*A[j])
for i in range(minus-1):
    for j in range(i+1,minus):
        heapq.heappush(h,A[i]*A[j])
for _ in range(K-1):
    heapq.heappop(h)
print(heapq.heappop(h))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

cal_list = [pair[0] * pair[1] for pair in itertools.combinations(A, 2)]
print(sorted(cal_list)[K-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

cal_list = [pair[0] * pair[1] for pair in itertools.combinations(A, 2)]
print(sorted(cal_list)[K-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

cal_list = []
for pair in itertools.combinations(A, 2):
  cal_list.append(pair[0] * pair[1])
  
print(sorted(cal_list)[K-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import numpy as np

def kakeru(n):
    return n[0]*n[1]

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

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

    combi = combinations(a,2)

    pairs = list(map(kakeru,combi))
    
    pairs = np.array(pairs)
    
    pairs_sort = np.sort(pairs)

    print(pairs_sort[k-1])
    
main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def kakeru(n):
    return n[0]*n[1]

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

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

    combi = combinations(a,2)

    pairs = list(map(kakeru,combi))
    

    pairs.sort()

    print(pairs[k-1])
    
main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

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

combi = combinations(a,2)

def kakeru(n):
    return n[0]*n[1]

pairs = list(map(kakeru,combi))

pairs_sort = sorted(pairs)

print(pairs_sort[k-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k = map(int, input().split())
a = list(map(int, input().split()))
num = 0
l = []
w = []
p = []
for h in itertools.combinations(a,2):
    if 0 in h:
        num += 1
    else:
        w.append(h)
for j in range(len(w)):
    if w[j] not in p:
        for x in range(w.count(w[j])):
            l.append(w[j][0]*w[j][1])
        p.append(w[j])
l += [0]*num
l.sort()
print(l[k-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k = map(int, input().split())
a = list(map(int, input().split()))
l = []
for i in itertools.combinations(a,2):
    l.append(i[0]*i[1])
l.sort()
print(l[k-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = [int(_) for _ in input().split()]
A = np.array(sorted([int(_) for _ in input().split()]))


def solve(N, K, A):
    lb = -10**18 - 1
    rb = 10**18 + 1

    def check(x):
        #x以下の積がK個以上ある
        cnt = 0
        for i, a in enumerate(A):
            #区間i2∈[0,i) でA[i]*A[i2]<=xとなるようなi2の個数
            l = 0
            r = i
            if a > 0:
                l = -1
                r = np.searchsorted(A, x // a, side='right')
            elif a < 0:
                l = np.searchsorted(A, 0 - x // -a, side='left')
                r = N + 1
            elif x < 0:
                r = 0
            l = min(max(l, 0), i)
            r = max(min(r, i), 0)
            cnt += r - l
        return cnt >= K

    # Min x for check(x) == True
    while rb - lb > 1:
        mid = (rb + lb) // 2
        if check(mid):
            rb = mid
        else:
            lb = mid
    print(rb)


solve(N, K, A)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])


def solve(N, K, A):
    lb = -10**18 - 1
    rb = 10**18 + 1

    def check(x):
        #x以下の積がK個以上ある
        cnt = 0
        for i, a in enumerate(A):
            #区間i2∈[0,i) でA[i]*A[i2]<=xとなるようなi2の個数
            l = 0
            r = i
            if a > 0:
                l = -float('inf')
                r = bisect.bisect(A, x // a)
            elif a < 0:
                l = bisect.bisect_left(A, 0 - x // (-a))
                r = float('inf')
            elif x < 0:
                r = 0
            l = min(max(l, 0), i)
            r = max(min(r, i), 0)
            cnt += r - l
        return cnt >= K

    # Min x for check(x) == True
    while rb - lb > 1:
        mid = (rb + lb) // 2
        if check(mid):
            rb = mid
        else:
            lb = mid
    print(rb)


solve(N, K, A)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


class BisectWrapper:
    try:
        from typing import List
    except:
        List = list
    from bisect import bisect, bisect_left, bisect_right

    def __init__(self):
        pass

    # aにxが存在するか
    @staticmethod
    def exist(a: List, x: int):
        i = bisect_left(a, x)
        if i != len(a) and a[i] == x:
            return True
        return False

    # xのindex(なければ-1)
    @staticmethod
    def index(a: List, x: int):
        i = bisect_left(a, x)
        if i != len(a) and a[i] == x:
            return i
        return -1

    # y < xのようなyの中でもっとも右のindex
    @staticmethod
    def index_lt(a: List, x: int):
        i = bisect_left(a, x)
        if i:
            return i - 1
        return -1

    # y < xのようなyの個数
    @staticmethod
    def num_lt(a: List, x: int):
        return bisect_left(a, x)

    # a[lo:hi]でy <= xのようなyの中でもっとも右のindex
    @staticmethod
    def index_lte(a: List, x: int, lo: int = None, hi: int = None):
        if lo is None:
            lo = 0
        if hi is None:
            hi = len(a)

        i = bisect_right(a, x, lo=lo, hi=hi)
        if i:
            return i - 1
        return -1

    # a[lo:hi]でy <= xのようなyの個数
    @staticmethod
    def num_lte(a: List, x: int, lo: int = None, hi: int = None):
        if lo is None:
            lo = 0
        if hi is None:
            hi = len(a)

        return bisect_right(a, x, lo=lo, hi=hi) - lo

    # y > xのようなyの中でもっとも左のindex
    @staticmethod
    def index_gt(a: List, x: int):
        i = bisect_right(a, x)
        if i != len(a):
            return i
        return -1

    # y > xのようなyの個数
    @staticmethod
    def num_gt(a: List, x: int):
        return len(a) - bisect_right(a, x)

    # y >= xのようなyの中でもっとも左のindex
    @staticmethod
    def index_gte(a: List, x: int):
        i = bisect_left(a, x)
        if i != len(a):
            return i
        return -1

    # y >= xのようなyの個数
    @staticmethod
    def num_gte(a: List, x: int, lo: int = None, hi: int = None):
        if lo is None:
            lo = 0
        if hi is None:
            hi = len(a)
        return len(a) - bisect_left(a, x)


def solve(N, K, A):
    pos, neg = [], []
    for a in A:
        if a > 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)

    num_pos, num_neg, num_zero = len(pos), len(neg), N - len(pos) - len(neg)
    for i in range(num_neg):
        neg[i] *= -1
    neg.sort()
    pos.sort()

    # neg
    if K <= num_neg * num_pos:
        left, right = -10 ** 20, 0
        while right - left > 1:
            c = (right + left) // 2

            num = 0
            # c以下の数値をいくつ作れるか
            # neg * pos
            for i in range(num_neg):
                num += BisectWrapper.num_gte(pos, ceil(-c, neg[i]))

            if num >= K:
                right = c
            else:
                left = c

        return right

    K -= num_neg * num_pos
    if K <= num_zero * (num_pos + num_neg) + (num_zero * (num_zero - 1) // 2):
        return 0

    K -= num_zero * (num_pos + num_neg) + (num_zero * (num_zero - 1) // 2)
    left, right = 0, 10 ** 20
    while right - left > 1:
        c = (right + left) // 2

        num = 0
        # c以下の数値をいくつ作れるか
        # neg * neg
        for i in range(num_neg):
            num += BisectWrapper.num_lte(neg, c // neg[i], i + 1)
        # pos * pos
        for i in range(num_pos):
            num += BisectWrapper.num_lte(pos, c // pos[i], i + 1)

        if num >= K:
            right = c
        else:
            left = c

    return right


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import numpy as np
from bisect import bisect_left, bisect_right

def main():
    n, k = map(int, input().split())
    A = [int(x) for x in input().split()]
    # A = sorted(A)
    A = np.array(A, dtype=np.int64)
    A = np.sort(A)
    # 最初の0のindex(0未満（負）の個数)
    # m_end = bisect_left(A, 0)
    m_end = np.searchsorted(A, 0)
    a_cnt_m = m_end
    # 最初の正の数のindex(0以下の個数)
    # p_start = bisect_right(A, 0)
    p_start = np.searchsorted(A, 0, side='right')
    # 正の個数
    a_cnt_p = n - p_start
    # 0の個数
    a_cnt_0 = n - (a_cnt_m + a_cnt_p)
    # # 掛け算の結果負の数
    cnt_m = a_cnt_m * a_cnt_p
    # # 掛け算の結果0の数
    cnt_0 = a_cnt_0 * (a_cnt_m+a_cnt_p) + (a_cnt_0 * (a_cnt_0-1)) // 2    
    # かけて負になる場合
    if cnt_m >= k:
        # x以下のものがk個以上あるような、最小のxを求める
        r = 0
        # 初期値は制約から考えられる最小値
        l = -10 ** 18
        # 二分探索
        while r - l > 1:
            x = (r + l) // 2
            # 最初の正の数のindex
            s = p_start
            # かけあわせた値のうちx以下のパターン数
            lower_x_cnt = 0
            # 負の数の最後まで
            for i in range(m_end):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (s < n) and (A[i]*A[s] > x):
                    s += 1
                # x以下の分を数えて、足し合わせていく
                lower_x_cnt += a_cnt_p - (s - p_start)
            # sが大きいとlower_x_cntが小さくなる
            # sが小さいととlower_x_cntが大きくなる
            # lower_x_cnt == kで最小のxを知りたい
            if lower_x_cnt >= k:
                # sを大きくする方向
                # xをより小さい数にしないといけない
                r = x
            else:
                # sを小さくする方向
                # xをより大きい数にしないといけない
                l = x
        print(r)
    # かけて０になる場合
    elif k <= cnt_m + cnt_0:
        print(0)
    # かけて正になる場合
    else:
        # kを掛け合わせて正の数になる値に変更する
        k -= cnt_m + cnt_0
        # x以下のものがk個以上あるような、最小のxを求める
        # 初期値は制約から考えられる最大値
        r = 10**18
        l = 0
        # 二分探索
        while (r - l) > 1:
            x = (r + l) // 2
            # 大きい値から考える
            s = n - 1
            # かけあわせた値のうちx以下のパターン数
            lower_x_cnt = 0
            # 正の数の掛け合わせ
            for i in range(p_start, n):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (i < s) and (A[i]*A[s] > x):
                    s -= 1
                # x以下の分を数えて、足し合わせていく
                # iがs以下の時だけ考える
                if i < s:
                    lower_x_cnt += s - i
            # 負の数の掛け合わせ
            # 負の値の最初のindexなので０
            t = 0
            # 負の最後の値から0まで-1ずつ回す
            for i in range(m_end - 1, -1, -1):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (t < i) and (A[i]*A[t] > x):
                    t += 1
                # x以下の分を数えて、足し合わせていく
                # iがt以上の時だけ考える
                if t < i:
                    lower_x_cnt += i - t
            if lower_x_cnt >= k:
                # sを大きくする方向
                # xをより小さい数にしないといけない
                r = x
            else:
                # sを小さくする方向
                # xをより大きい数にしないといけない
                l = x
        print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import numpy as np
from bisect import bisect_left, bisect_right

def main():
    n, k = map(int, input().split())
    A = [int(x) for x in input().split()]
    # A = sorted(A)
    A = np.array(A, dtype=np.int64)
    A = np.sort(A)
    # 最初の0のindex(0未満（負）の個数)
    m_end = bisect_left(A, 0)
    # m_end = np.searchsorted(A_np, 0)
    a_cnt_m = m_end
    # 最初の正の数のindex(0以下の個数)
    p_start = bisect_right(A, 0)
    # p_start = np.searchsorted(A_np, 0, side='right')
    # 正の個数
    a_cnt_p = n - p_start
    # 0の個数
    a_cnt_0 = n - (a_cnt_m + a_cnt_p)
    # # 掛け算の結果負の数
    cnt_m = a_cnt_m * a_cnt_p
    # # 掛け算の結果0の数
    cnt_0 = a_cnt_0 * (a_cnt_m+a_cnt_p) + (a_cnt_0 * (a_cnt_0-1)) // 2    
    # かけて負になる場合
    if cnt_m >= k:
        # x以下のものがk個以上あるような、最小のxを求める
        r = 0
        # 初期値は制約から考えられる最小値
        l = -10 ** 18
        # 二分探索
        while r - l > 1:
            x = (r + l) // 2
            # 最初の正の数のindex
            s = p_start
            # かけあわせた値のうちx以下のパターン数
            lower_x_cnt = 0
            # 負の数の最後まで
            for i in range(m_end):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (s < n) and (A[i]*A[s] > x):
                    s += 1
                # x以下の分を数えて、足し合わせていく
                lower_x_cnt += a_cnt_p - (s - p_start)
            # sが大きいとlower_x_cntが小さくなる
            # sが小さいととlower_x_cntが大きくなる
            # lower_x_cnt == kで最小のxを知りたい
            if lower_x_cnt >= k:
                # sを大きくする方向
                # xをより小さい数にしないといけない
                r = x
            else:
                # sを小さくする方向
                # xをより大きい数にしないといけない
                l = x
        print(r)
    # かけて０になる場合
    elif k <= cnt_m + cnt_0:
        print(0)
    # かけて正になる場合
    else:
        # kを掛け合わせて正の数になる値に変更する
        k -= cnt_m + cnt_0
        # x以下のものがk個以上あるような、最小のxを求める
        # 初期値は制約から考えられる最大値
        r = 10**18
        l = 0
        # 二分探索
        while (r - l) > 1:
            x = (r + l) // 2
            # 大きい値から考える
            s = n - 1
            # かけあわせた値のうちx以下のパターン数
            lower_x_cnt = 0
            # 正の数の掛け合わせ
            for i in range(p_start, n):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (i < s) and (A[i]*A[s] > x):
                    s -= 1
                # x以下の分を数えて、足し合わせていく
                # iがs以下の時だけ考える
                if i < s:
                    lower_x_cnt += s - i
            # 負の数の掛け合わせ
            # 負の値の最初のindexなので０
            t = 0
            # 負の最後の値から0まで-1ずつ回す
            for i in range(m_end - 1, -1, -1):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (t < i) and (A[i]*A[t] > x):
                    t += 1
                # x以下の分を数えて、足し合わせていく
                # iがt以上の時だけ考える
                if t < i:
                    lower_x_cnt += i - t
            if lower_x_cnt >= k:
                # sを大きくする方向
                # xをより小さい数にしないといけない
                r = x
            else:
                # sを小さくする方向
                # xをより大きい数にしないといけない
                l = x
        print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    n, k = map(int, input().split())
    A = [int(x) for x in input().split()]
    # A.sort()
    A = sorted(A)
    # A_np = np.array(A, dtype=np.int64)
    # A_np = np.sort(A)
    # 最初の0のindex(0未満（負）の個数)
    m_end = bisect_left(A, 0)
    # m_end = np.searchsorted(A_np, 0)
    a_cnt_m = m_end
    # 最初の正の数のindex(0以下の個数)
    p_start = bisect_right(A, 0)
    # p_start = np.searchsorted(A_np, 0, side='right')
    # 正の個数
    a_cnt_p = n - p_start
    # 0の個数
    a_cnt_0 = n - (a_cnt_m + a_cnt_p)
    # # 掛け算の結果負の数
    cnt_m = a_cnt_m * a_cnt_p
    # # 掛け算の結果0の数
    cnt_0 = a_cnt_0 * (a_cnt_m+a_cnt_p) + (a_cnt_0 * (a_cnt_0-1)) // 2    
    # かけて負になる場合
    if cnt_m >= k:
        # x以下のものがk個以上あるような、最小のxを求める
        r = 0
        # 初期値は制約から考えられる最小値
        l = -10 ** 18
        # 二分探索
        while r - l > 1:
            x = (r + l) // 2
            # 最初の正の数のindex
            s = p_start
            # かけあわせた値のうちx以下のパターン数
            lower_x_cnt = 0
            # 負の数の最後まで
            for i in range(m_end):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (s < n) and (A[i]*A[s] > x):
                    s += 1
                # x以下の分を数えて、足し合わせていく
                lower_x_cnt += a_cnt_p - (s - p_start)
            # sが大きいとlower_x_cntが小さくなる
            # sが小さいととlower_x_cntが大きくなる
            # lower_x_cnt == kで最小のxを知りたい
            if lower_x_cnt >= k:
                # sを大きくする方向
                # xをより小さい数にしないといけない
                r = x
            else:
                # sを小さくする方向
                # xをより大きい数にしないといけない
                l = x
        print(r)
    # かけて０になる場合
    elif k <= cnt_m + cnt_0:
        print(0)
    # かけて正になる場合
    else:
        # kを掛け合わせて正の数になる値に変更する
        k -= cnt_m + cnt_0
        # x以下のものがk個以上あるような、最小のxを求める
        # 初期値は制約から考えられる最大値
        r = 10**18
        l = 0
        # 二分探索
        while (r - l) > 1:
            x = (r + l) // 2
            # 大きい値から考える
            s = n - 1
            # かけあわせた値のうちx以下のパターン数
            lower_x_cnt = 0
            # 正の数の掛け合わせ
            for i in range(p_start, n):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (i < s) and (A[i]*A[s] > x):
                    s -= 1
                # x以下の分を数えて、足し合わせていく
                # iがs以下の時だけ考える
                if i < s:
                    lower_x_cnt += s - i
            # 負の数の掛け合わせ
            # 負の値の最初のindexなので０
            t = 0
            # 負の最後の値から0まで-1ずつ回す
            for i in range(m_end - 1, -1, -1):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (t < i) and (A[i]*A[t] > x):
                    t += 1
                # x以下の分を数えて、足し合わせていく
                # iがt以上の時だけ考える
                if t < i:
                    lower_x_cnt += i - t
            if lower_x_cnt >= k:
                # sを大きくする方向
                # xをより小さい数にしないといけない
                r = x
            else:
                # sを小さくする方向
                # xをより大きい数にしないといけない
                l = x
        print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import numpy as np

def main():
    n, k = map(int, input().split())
    A = sorted([int(x) for x in input().split()])
    A_np = np.array(A, dtype=np.int64)
    A_np = np.sort(A)
    # 最初の0のindex(0未満（負）の個数)
    # m_end = bisect_left(A, 0)
    m_end = np.searchsorted(A_np, 0)
    a_cnt_m = m_end
    # 最初の正の数のindex(0以下の個数)
    # p_start = bisect_right(A, 0)
    p_start = np.searchsorted(A_np, 0, side='right')
    # 正の個数
    a_cnt_p = n - p_start
    # 0の個数
    a_cnt_0 = n - (a_cnt_m + a_cnt_p)
    # # 掛け算の結果負の数
    cnt_m = a_cnt_m * a_cnt_p
    # # 掛け算の結果0の数
    cnt_0 = a_cnt_0 * (a_cnt_m+a_cnt_p) + (a_cnt_0 * (a_cnt_0-1)) // 2    
    # かけて負になる場合
    if cnt_m >= k:
        # x以下のものがk個以上あるような、最小のxを求める
        r = 0
        # 初期値は制約から考えられる最小値
        l = -10 ** 18
        # 二分探索
        while r - l > 1:
            x = (r + l) // 2
            # 最初の正の数のindex
            s = p_start
            # かけあわせた値のうちx以下のパターン数
            lower_x_cnt = 0
            # 負の数の最後まで
            for i in range(m_end):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (s < n) and (A[i]*A[s] > x):
                    s += 1
                # x以下の分を数えて、足し合わせていく
                lower_x_cnt += a_cnt_p - (s - p_start)
            # sが大きいとlower_x_cntが小さくなる
            # sが小さいととlower_x_cntが大きくなる
            # lower_x_cnt == kで最小のxを知りたい
            if lower_x_cnt >= k:
                # sを大きくする方向
                # xをより小さい数にしないといけない
                r = x
            else:
                # sを小さくする方向
                # xをより大きい数にしないといけない
                l = x
        print(r)
    # かけて０になる場合
    elif k <= cnt_m + cnt_0:
        print(0)
    # かけて正になる場合
    else:
        # kを掛け合わせて正の数になる値に変更する
        k -= cnt_m + cnt_0
        # x以下のものがk個以上あるような、最小のxを求める
        # 初期値は制約から考えられる最大値
        r = 10**18
        l = 0
        # 二分探索
        while (r - l) > 1:
            x = (r + l) // 2
            # 大きい値から考える
            s = n - 1
            # かけあわせた値のうちx以下のパターン数
            lower_x_cnt = 0
            # 正の数の掛け合わせ
            for i in range(p_start, n):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (i < s) and (A[i]*A[s] > x):
                    s -= 1
                # x以下の分を数えて、足し合わせていく
                # iがs以下の時だけ考える
                if i < s:
                    lower_x_cnt += s - i
            # 負の数の掛け合わせ
            # 負の値の最初のindexなので０
            t = 0
            # 負の最後の値から0まで-1ずつ回す
            for i in range(m_end - 1, -1, -1):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (t < i) and (A[i]*A[t] > x):
                    t += 1
                # x以下の分を数えて、足し合わせていく
                # iがt以上の時だけ考える
                if t < i:
                    lower_x_cnt += i - t
            if lower_x_cnt >= k:
                # sを大きくする方向
                # xをより小さい数にしないといけない
                r = x
            else:
                # sを小さくする方向
                # xをより大きい数にしないといけない
                l = x
        print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

def main():
    n, k = map(int, input().split())
    A = sorted([int(x) for x in input().split()])
    # 最初の0のindex(0未満（負）の個数)
    m_end = bisect_left(A, 0)
    a_cnt_m = m_end
    # 最初の正の数のindex(0以下の個数)
    p_start = bisect_right(A, 0)
    # 正の個数
    a_cnt_p = n - p_start
    # 0の個数
    a_cnt_0 = n - (a_cnt_m + a_cnt_p)
    # # 掛け算の結果負の数
    cnt_m = a_cnt_m * a_cnt_p
    # # 掛け算の結果0の数
    cnt_0 = a_cnt_0 * (a_cnt_m+a_cnt_p) + (a_cnt_0 * (a_cnt_0-1)) // 2    
    # かけて負になる場合
    if cnt_m >= k:
        # x以下のものがk個以上あるような、最小のxを求める
        r = 0
        # 初期値は制約から考えられる最小値
        l = -10 ** 18
        # 二分探索
        while r - l > 1:
            x = (r + l) // 2
            # 最初の正の数のindex
            s = p_start
            # かけあわせた値のうちx以下のパターン数
            lower_x_cnt = 0
            # 負の数の最後まで
            for i in range(m_end):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (s < n) and (A[i]*A[s] > x):
                    s += 1
                # x以下の分を数えて、足し合わせていく
                lower_x_cnt += a_cnt_p - (s - p_start)
            # sが大きいとlower_x_cntが小さくなる
            # sが小さいととlower_x_cntが大きくなる
            # lower_x_cnt == kで最小のxを知りたい
            if lower_x_cnt >= k:
                # sを大きくする方向
                # xをより小さい数にしないといけない
                r = x
            else:
                # sを小さくする方向
                # xをより大きい数にしないといけない
                l = x
        print(r)
    # かけて０になる場合
    elif k <= cnt_m + cnt_0:
        print(0)
    # かけて正になる場合
    else:
        # kを掛け合わせて正の数になる値に変更する
        k -= cnt_m + cnt_0
        # x以下のものがk個以上あるような、最小のxを求める
        # 初期値は制約から考えられる最大値
        r = 10**18
        l = 0
        # 二分探索
        while (r - l) > 1:
            x = (r + l) // 2
            # 大きい値から考える
            s = n - 1
            # かけあわせた値のうちx以下のパターン数
            lower_x_cnt = 0
            # 正の数の掛け合わせ
            for i in range(p_start, n):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (i < s) and (A[i]*A[s] > x):
                    s -= 1
                # x以下の分を数えて、足し合わせていく
                # iがs以下の時だけ考える
                if i < s:
                    lower_x_cnt += s - i
            # 負の数の掛け合わせ
            # 負の値の最初のindexなので０
            t = 0
            # 負の最後の値から0まで-1ずつ回す
            for i in range(m_end - 1, -1, -1):
                # A[i]*A[s] > x で x超えちゃう分数えて
                while (t < i) and (A[i]*A[t] > x):
                    t += 1
                # x以下の分を数えて、足し合わせていく
                # iがt以上の時だけ考える
                if t < i:
                    lower_x_cnt += i - t
            if lower_x_cnt >= k:
                # sを大きくする方向
                # xをより小さい数にしないといけない
                r = x
            else:
                # sを小さくする方向
                # xをより大きい数にしないといけない
                l = x
        print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
am=[]
ap=[]
zc=0
for i in a:
  if i<0:
    am.append(i)
  elif i>0:
    ap.append(i)
  else:
    zc+=1
am.sort()
ap.sort()
#print(am,ap)
def count(n,m,p,z):
  mx=-10**20
  lm=len(m)
  lp=len(p)
  if n==0:
    if z or (lm and lp):
      return (lm*lp+(lm+lp)*z+(z*(z-1))//2,0 if z else m[-1]*p[0])
    else:
      return (0,0)
  elif n<0:
    r=0
    j=0
    for i in m:
      while j<len(p) and i*p[j]>n:
        j+=1
      if j<len(p) and mx<i*p[j]:
         mx=i*p[j]
      r+=len(p)-j
    return (r,mx)
  else:
    if z or (lm and lp):
      mx=0 if z else m[-1]*p[0]
    r=lm*lp+(lm+lp)*z+(z*(z-1))//2
    j=lp-1
    for i in range(lp):
      while j>i and p[i]*p[j]>n:
        j-=1
      if j>i and p[i]*p[j]>mx:
        mx=p[i]*p[j]
      r+=j-i
      if i==j:
        break
    j=lm-1
    for i in range(lm):
      while j>i and m[i]*m[j]<=n:
        j-=1
      if i>j:
        j=i
      if j<lm-1 and m[i]*m[j+1]>mx:
        mx=m[i]*m[j+1]
      r+=lm-j-1
    return (r,mx)

r=10**18
t=0
s=set()

while True:
  ret=count(t,am,ap,zc)
  #if r<100:
  #  print(t,ret)
  if ret[0]<k:
    s.add(t)
    t+=r
    r=(r+1)//2
  elif ret[0]==k:
    print(ret[1])
    break
  else:
    if t in s:
      print(ret[1])
      break
    s.add(t)
    t-=r
    r=(r+1)//2

Submission status: Time Limit Exceeded

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