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:
N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            #index = bisect_right(As, t//A, lo = i+1) - (i+1)
            l = i
            r = N
            while r - l > 1:
                mid = (l + r) // 2
                if As[mid] <= t//A:
                    l = mid
                else:
                    r = mid
            index = r - (i+1)
        elif A < 0:
            #index = N - bisect_left(As, -((-t)//A), lo = i+1)
            l = i
            r = N
            while r - l > 1:
                mid = (l + r) // 2
                if As[mid] < -((-t)//A):
                    l = mid
                else:
                    r = mid
            index = N - r
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    return (count < K)
        

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count > K:
            return False
    return (count < K)

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = 0
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)

Submission status: Time Limit Exceeded

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

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count > K:
            return False
    return (count < K)

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = 0
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)

Submission status: Time Limit Exceeded

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

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return (count < K)
        

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

print(r)

Submission status: Time Limit Exceeded

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

def check(t, As):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            #index = bisect_right(As, t//A, lo = i+1) - (i+1)
            l = i
            r = N
            while r - l > 1:
                mid = (l + r) // 2
                if As[mid] <= t//A:
                    l = mid
                else:
                    r = mid
            index = r - (i+1)
        elif A < 0:
            #index = N - bisect_left(As, -((-t)//A), lo = i+1)
            l = i
            r = N
            while r - l > 1:
                mid = (l + r) // 2
                if As[mid] < -((-t)//A):
                    l = mid
                else:
                    r = mid
            index = N - r
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    return (count < K)
        

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
from numba import njit
input = sys.stdin.buffer.readline

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

@njit
def check(t, As):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            #index = bisect_right(As, t//A, lo = i+1) - (i+1)
            l = i
            r = N
            while r - l > 1:
                mid = (l + r) // 2
                if As[mid] <= t//A:
                    l = mid
                else:
                    r = mid
            index = r - (i+1)
        elif A < 0:
            #index = N - bisect_left(As, -((-t)//A), lo = i+1)
            l = i
            r = N
            while r - l > 1:
                mid = (l + r) // 2
                if As[mid] < -((-t)//A):
                    l = mid
                else:
                    r = mid
            index = N - r
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    return (count < K)
        

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count > K:
            return False
    return (count < K)
        

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -((-t)//A), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count > K:
            return False
    return (count < K)
        

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

print(r)

Submission status: Time Limit Exceeded

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

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -((-t)//A), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count > K:
            return False
    return (count < K)
        

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -((-t)//A), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    return (count < K)
        


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

print(r)

Submission status: Time Limit Exceeded

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

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -((-t)//A), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    return (count < K)
        


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

print(r)

Submission status: Time Limit Exceeded

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

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            r_index = bisect_left(As, -((-t)//A), lo = i+1) - (i+1)
            index = (N - i - 1) - r_index
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    if count < K:
        return True
    else:
        return False


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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            r_index = bisect_left(As, -((-t)//A), lo = i+1) - (i+1)
            index = (N - i - 1) - r_index
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    if count < K:
        return True
    else:
        return False


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

print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As[i+1:], t//A)
        elif A < 0:
            r_index = bisect_left(As[i+1:], -((-t)//A))
            index = (N - i - 1) - r_index
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
    if count < K:
        return True
    else:
        return False


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

print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

left = -INF
right = INF
while right - left > 1:
    x = (left + right) // 2
    s = 0 # num of less than or equal to x
    t = 0 # duplication
    for a in A:
        if a > 0:
            l = -1
            r = N
            while r - l > 1:
                m = (l + r) // 2
                if A[m] * a <= x:
                    l = m
                else:
                    r = m
            s += r
        elif a < 0:
            l = -1
            r = N
            while r - l > 1:
                m = (l + r) // 2
                if A[m] * a <= x:
                    r = m
                else:
                    l = m
            s += N - r
        elif a == 0 and x >= 0:
            s += N

        if a * a <= x:
            t += 1
    count = (s - t) // 2
    if count >= K:
        right = x
    else:
        left = x
print(right)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k = [int(x) for x in input().rstrip().split(" ")]
numbers = [int(x) for x in input().rstrip().split(" ")]

result = sorted([x[0] * x[1] for x in itertools.combinations(numbers, 2)])

print(result[k - 1])

Submission status: Time Limit Exceeded

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

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
# A = [1, 2, 3, -1]
# N = len(A)
A.sort()


def calc_cnt(k):
    res = 0
    for i in range(N):
        if A[i] > 0:
            l2 = -1
            r2 = N
            while l2 < r2 - 1:
                m2 = (l2 + r2) // 2
                if A[m2] * A[i] <= k:
                    l2 = m2
                else:
                    r2 = m2
            res += l2 + 1
        elif A[i]< 0:
            l2 = -1
            r2 = N
            while l2 < r2 - 1:
                m2 = (l2 + r2) // 2
                if A[m2] * A[i] <= k:
                    r2 = m2
                else:
                    l2 = m2
            res += (N - r2)
        elif k>=0:
            res+=N

        if A[i] * A[i] <= k:
            res -= 1
    return res // 2


def main():
    INF = 10 ** 18 + 10
    l = -INF
    r = INF
    while l < r - 1:
        m = (l + r) // 2
        # print(m,calc_cnt(m))
        if calc_cnt(m) < K:
            l = m
        else:
            r = m
    print(l+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
# A = [1, 2, 3, -1]
# N = len(A)
A.sort()


def calc_cnt(k):
    calc_cnt = 0
    for i in range(N):
        if A[i] > 0:
            l2 = -1
            r2 = N
            while l2 < r2 - 1:
                m2 = (l2 + r2) // 2
                if A[m2] * A[i] <= k:
                    l2 = m2
                else:
                    r2 = m2
            calc_cnt += l2 + 1
        elif A[i]< 0:
            l2 = -1
            r2 = N
            while l2 < r2 - 1:
                m2 = (l2 + r2) // 2
                if A[m2] * A[i] <= k:
                    r2 = m2
                else:
                    l2 = m2
            calc_cnt += (N - r2)
        elif k>=0:
            calc_cnt+=N

        if A[i] * A[i] <= k:
            calc_cnt -= 1
    return calc_cnt // 2


def main():
    INF = 10 ** 18 + 10
    l = -INF
    r = INF
    while l < r - 1:
        m = (l + r) // 2
        # print(m,calc_cnt(m))
        if calc_cnt(m) < K:
            l = m
        else:
            r = m
    print(l+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
# A = [1, 2, 3, -1]
# N = len(A)
A.sort()


def calc_cnt(k):
    calc_cnt = 0
    for a in A:
        if a > 0:
            l2 = -1
            r2 = N
            while l2 < r2 - 1:
                m2 = (l2 + r2) // 2
                if A[m2] * a <= k:
                    l2 = m2
                else:
                    r2 = m2
            calc_cnt += l2 + 1
        elif a< 0:
            l2 = -1
            r2 = N
            while l2 < r2 - 1:
                m2 = (l2 + r2) // 2
                if A[m2] * a <= k:
                    r2 = m2
                else:
                    l2 = m2
            calc_cnt += (N - r2)
        elif k>=0:
            calc_cnt+=N

        if a * a <= k:
            calc_cnt -= 1
    return calc_cnt // 2


def main():
    INF = 10 ** 18 + 10
    l = -INF
    r = INF
    while l < r - 1:
        m = (l + r) // 2
        # print(m,calc_cnt(m))
        if calc_cnt(m) < K:
            l = m
        else:
            r = m
    print(l+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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




def main():
    N, K = [int(_) for _ in input().split()]
    A = sorted([int(_) for _ in input().split()])
    INF = 10 ** 18 + 10
    l = -INF
    r = INF
    while l < r - 1:
        m = (l + r) // 2
        # print(m,calc_cnt(m))
        calc_cnt = 0
        _k=m
        for _a in A:
            if _a > 0:
                l2 = -1
                r2 = N
                while l2 < r2 - 1:
                    m2 = (l2 + r2) // 2
                    if A[m2] * _a <= _k:
                        l2 = m2
                    else:
                        r2 = m2
                calc_cnt += l2 + 1
            elif _a <0:
                l2 = -1
                r2 = N
                while l2 < r2 - 1:
                    m2 = (l2 + r2) // 2
                    if A[m2] * _a <= _k:
                        r2 = m2
                    else:
                        l2 = m2
                calc_cnt += (N - r2)
            elif _k>=0:
                calc_cnt +=N

            if _a * _a <= _k:
                calc_cnt -= 1
        calc_cnt //= 2

        if calc_cnt < K:
            l = m
        else:
            r = m
    print(l+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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




def main():
    N, K = [int(_) for _ in input().split()]
    A = sorted([int(_) for _ in input().split()])
    INF = 10 ** 18 + 10
    l = -INF
    r = INF
    while l < r - 1:
        m = (l + r) // 2
        # print(m,calc_cnt(m))
        calc_cnt = 0
        _k=m
        for _a in A:
            if _a >= 0:
                l2 = -1
                r2 = N
                while l2 < r2 - 1:
                    m2 = (l2 + r2) // 2
                    if A[m2] * _a <= _k:
                        l2 = m2
                    else:
                        r2 = m2
                calc_cnt += l2 + 1
            else:
                l2 = -1
                r2 = N
                while l2 < r2 - 1:
                    m2 = (l2 + r2) // 2
                    if A[m2] * _a <= _k:
                        r2 = m2
                    else:
                        l2 = m2
                calc_cnt += (N - r2)

            if _a * _a <= _k:
                calc_cnt -= 1
        calc_cnt //= 2

        if calc_cnt < K:
            l = m
        else:
            r = m
    print(l+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
# A = [1, 2, 3, -1]
# N = len(A)
A.sort()


def calc_cnt(k):
    calc_cnt = 0
    for a in A:
        if a >= 0:
            l2 = -1
            r2 = N
            while l2 < r2 - 1:
                m2 = (l2 + r2) // 2
                if A[m2] * a <= k:
                    l2 = m2
                else:
                    r2 = m2
            calc_cnt += l2 + 1
        else:
            l2 = -1
            r2 = N
            while l2 < r2 - 1:
                m2 = (l2 + r2) // 2
                if A[m2] * a <= k:
                    r2 = m2
                else:
                    l2 = m2
            calc_cnt += (N - r2)

        if a * a <= k:
            calc_cnt -= 1
    return calc_cnt // 2


def main():
    INF = 10 ** 18 + 10
    l = -INF
    r = INF
    while l < r - 1:
        m = (l + r) // 2
        # print(m,calc_cnt(m))
        if calc_cnt(m) < K:
            l = m
        else:
            r = m
    print(l+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
# A = [1, 2, 3, -1]
# N = len(A)
A.sort()


def calc_cnt(k):
    cnt = 0
    for i, a in enumerate(A):
        if a >= 0:
            l = -1
            r = N
            while l < r - 1:
                m = (l + r) // 2
                if A[m] * a <= k:
                    l = m
                else:
                    r = m
            cnt += l + 1
        else:
            l = -1
            r = N
            while l < r - 1:
                m = (l + r) // 2
                if A[m] * a <= k:
                    r = m
                else:
                    l = m
            cnt += (N - r)

        if a * a <= k:
            cnt -= 1
    return cnt // 2


def main():
    INF = 10 ** 18 + 10
    l = -INF
    r = INF
    while l < r - 1:
        m = (l + r) // 2
        # print(m,calc_cnt(m))
        if calc_cnt(m) < K:
            l = m
        else:
            r = m
    print(l+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
# A = [1, 2, 3, -1]
# N = len(A)
A.sort()


def calc_cnt(k):
    cnt = 0
    for i, a in enumerate(A):
        if a >= 0:
            l = -1
            r = N
            while l < r - 1:
                m = (l + r) // 2
                if A[m] * a <= k:
                    l = m
                else:
                    r = m
            cnt += l + 1
        else:
            l = -1
            r = N
            while l < r - 1:
                m = (l + r) // 2
                if A[m] * a <= k:
                    r = m
                else:
                    l = m
            cnt += (N - r)

        if a * a <= k:
            cnt -= 1
    return cnt // 2


def main():
    INF = 10 ** 18 + 10
    l = -INF
    r = INF
    while l < r - 1:
        m = (l + r) // 2
        # print(m,calc_cnt(m))
        if calc_cnt(m) < K:
            l = m
        else:
            r = m
    print(l+1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':

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

	A = list(map(int,input().split()))
	B = [A[x]*A[y] for x in range(n) for y in range(x+1,n)]
	C = sorted(B)

	print(C[m-1])

Submission status: Time Limit Exceeded

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

zero=[]
mainasu=[]
purasu=[]

for aa in a:
    if aa<0:
        mainasu.append(aa)
    elif aa==0:
        zero.append(aa)
    else:
        purasu.append(aa)

#答えがマイナスになる数：len(purasu)*len(mainasu)
#答えがゼロ：len(zero)*(len(purasu)+len(mainasu))
#答えがプラス：(len(purasu)*(len(purasu)-1))//2+(len(mainasu)*(len(mainasu)-1))//2

lenm=(len(purasu)*len(mainasu))
lenz=(len(zero)*(len(purasu)+len(mainasu))+(len(zero)*(len(zero)-1))//2)
lenp=((len(purasu)*(len(purasu)-1))//2+(len(mainasu)*(len(mainasu)-1))//2)

if k<=lenm:
    tmp=[]
    for i in range(len(purasu)):
        for j in range(len(mainasu)):
            tmp.append(purasu[i]*mainasu[j])
    tmp.sort()
    print(tmp[k-1])

elif k<=lenm+lenz:
    print(0)

else:
    tmp=[]
    for i in range(len(purasu)):
        for j in range(i+1,len(purasu)):
            tmp.append(purasu[i]*purasu[j])
    
    for i in range(len(mainasu)):
        for j in range(i+1,len(mainasu)):
            tmp.append(mainasu[i]*mainasu[j])

    tmp.sort()
    #print(tmp)
    print(tmp[k-(lenm+lenz)-1])

#print(lenm,lenz)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys

input = sys.stdin.readline

def main(args):
    def is_ok_minus(x):
        cnt = 0
        f = False
        for i in range(len(mA)):
            if f:
                break
            for j in range(len(pA)):
                if mA[i]*pA[-(j+1)] <= x:
                    cnt += 1
                else:
                    if j == 0:
                        f = True
                    break
        if cnt >= k:
            return True
        return False
    
    def meguru_bisect_minus(ng, ok):
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok_minus(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    
    def is_ok_plus(x):
        cnt = leq0
        f = False
        for i in range(len(mA)):
            if f:
                break
            for j in range(i+1,len(mA)):
                if mA[-(i+1)]*mA[-(j+1)] <= x:
                    cnt += 1
                else:
                    if j == 0:
                        f = True
                    break
        
        for i in range(len(pA)):
            for j in range(i+1,len(pA)):
                if pA[i]*pA[j] <= x:
                    cnt += 1
                else:
                    break
        
        if cnt >= k:
            return True
        return False
    
    def meguru_bisect_plus(ng, ok):
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok_plus(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    n, k = map(int,input().split())
    A = list(map(int,input().split()))
    
    A.sort()
    
    minus = bisect.bisect_right(A, -1)
    zeros = bisect.bisect_right(A, 0) - minus
    plus = n - (minus+zeros)
    
    #0以下になるペアの個数　is_ok_plusで使う
    leq0 = minus*plus + zeros*(minus+plus) + zeros*(zeros-1)//2
    
    mA = A[:minus]
    zA = A[minus:minus+zeros]
    pA = A[minus+zeros:]
    
    minus_pair = minus*plus
    zero_pair = zeros*(n-zeros) + zeros*(zeros-1)//2
    plus_pair = n*(n-1)//2-(minus_pair+zero_pair)
    
    #print("minus",minus*plus)
    #print("0",zeros*(minus+plus))
    
    if k <= minus_pair:
        print(meguru_bisect_minus(-10**18,10**18))
    elif minus_pair+1 <= k <= minus_pair+zero_pair:
        print(0)
    else:
        print(meguru_bisect_plus(-10**18,10**18))
        
if __name__ == '__main__':
    main(sys.argv[1:])