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
import bisect
def binary_search_m(i,a,A,mid_target):
    left_index=-1
    right_index=len(A)
    if len(A)==1:
        if a*A[i]>=mid_target:
            return 0
        else:
            return 1
    else:
        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 len(A)-(left_index+1)

def binary_search_p(i,a,A,mid_target):
    left_index=-1
    right_index=len(A)
    if len(A)==1:
        if a*A[0]<mid_target:
            return 1
        else:
            return 0
    else:
        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
        #print(mid_target)
        count=0
        for i in range(N-1):
            a=A[i]
            if a<0:
                count+=binary_search_m(i,a,A[i+1:],mid_target)
            elif a==0:
                if mid_target>0:
                    count+=(N-(i+1))
            elif a>0:
                count+=binary_search_p(i,a,A[i+1:],mid_target)
            #print("a:",a,"c",count)
        if count<K:
            left_target=mid_target
        else:
            right_target=mid_target
        #print(count)
    print(left_target)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import numpy as np
from bisect import bisect_right

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

    zero_count = np.count_nonzero(A==0)
    plus = A[A>0]
    minus = A[A<0]

    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
            for i in range(len(plus)):
                target = mid//plus[i]
                # target以下の数をminusから見つける
                count += bisect_right(minus,target)
            
            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
            for i in range(len(plus)):
                target = mid//plus[i]
                # target以下の数をplusから見つける
                count += bisect_right(plus,target)
                if plus[i] <= target:
                    count -= 1

            for i in range(len(minus)):
                target = mid//minus[i]
                # target以下の数をplusから見つける
                count += bisect_right(minus,target)
                if minus[i] <= target:
                    count -= 1
            if count//2 >= K:
                right = mid
            else:
                left = mid
        print(right)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k = [int(numb) for numb in input().split(" ")]
li = [int(num) for num in input().split(" ")]
test = []
for i in range(0,len(li)-1):
    for j in range(i+1,len(li)):
        test.append(li[i]*li[j])
test.sort()
print(test[k-1],end="")

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0
    j = 0
    for a in neg:
        d = m // a
        j = bisect(pos, d, lo=j)
        if len_pos == j:
            break
        less += len_pos - j
    return less < k


def get_bisect(pos):
    memo = {}

    def f(d, lo):
        if d not in memo:
            memo[d] = bisect(pos, d, lo)
        return memo[d]

    return f


def check_pos(m, k, pos, neg, len_pos, len_neg, bisect_pos, bisect_neg):
    less = 0
    j = 0
    for i in range(len_pos - 1, -1, -1):
        a = pos[i]
        d = m // a
        j = bisect_pos(d, j)
        if j == len_pos:
            less += len_pos * (i + 1)
            break
        less += j
    m_sqrt = int(m ** 0.5)
    less -= bisect(pos, m_sqrt)

    j = 0
    for i in range(len_neg - 1, -1, -1):
        a = neg[i]
        d = m // a
        j = bisect_neg(d, j)
        if j == len_neg:
            less += len_neg * (i + 1)
            break
        less += j
    less -= bisect(neg, m_sqrt)

    less //= 2

    return less < k


def solve(n, k, aaa):
    pos = [a for a in aaa if a > 0]
    neg = [a for a in aaa if a < 0]
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        bisect_pos = get_bisect(pos)
        bisect_neg = get_bisect(neg)
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg, bisect_pos, bisect_neg):
                l = m
            else:
                r = m
        return r


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(n, k, aaa))


def debug():
    mul = []
    for i in range(n):
        for j in range(i + 1, n):
            mul.append(aaa[i] * aaa[j])
    mul.sort()
    print(mul[k - 1], mul)

# debug()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0
    j = 0
    for a in neg:
        d = m // a
        j = bisect(pos, d, lo=j)
        if len_pos == j:
            break
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    less = 0
    j = 0
    for i in range(len_pos - 1, -1, -1):
        a = pos[i]
        d = m // a
        j = bisect(pos, d, lo=j)
        if j == len_pos:
            less += len_pos * (i + 1)
            break
        less += j
    m_sqrt = int(m ** 0.5)
    less -= bisect(pos, m_sqrt)

    j = 0
    for i in range(len_neg - 1, -1, -1):
        a = neg[i]
        d = m // a
        j = bisect(neg, d, lo=j)
        if j == len_neg:
            less += len_neg * (i + 1)
            break
        less += j
    less -= bisect(neg, m_sqrt)

    less //= 2

    return less < k


def solve(n, k, aaa):
    pos = [a for a in aaa if a > 0]
    neg = [a for a in aaa if a < 0]
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg):
                l = m
            else:
                r = m
        return r


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(n, k, aaa))


def debug():
    mul = []
    for i in range(n):
        for j in range(i + 1, n):
            mul.append(aaa[i] * aaa[j])
    mul.sort()
    print(mul[k - 1], mul)


# debug()

Submission status: Time Limit Exceeded

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

    S = []

    for i in range(N-1):
        for j in range(i+1, N):
            s = A[i]*A[j]
            S.append(s)
    
    Ns = len(S)
    flag = True
    k = 0

    while flag:
        flag = False
        for l in range(Ns-1, k, -1):
            if S[l] < S[l-1]:
                S[l], S[l-1] = S[l-1], S[l]
                flag = True
        k += 1
    
    print(S[K-1])

D()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0
    j = 0
    for a in neg:
        d = m // a
        j = bisect(pos, d, lo=j)
        if len_pos == j:
            break
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    less = 0
    for i in range(1, len_pos):
        a = pos[i]
        d = m // a
        j = bisect(pos, d, hi=i)
        less += j
    for i in range(1, len_neg):
        a = neg[i]
        d = m // a
        j = bisect(neg, d, hi=i)
        less += j
    return less < k


def solve(n, k, aaa):
    pos = [a for a in aaa if a > 0]
    neg = [a for a in aaa if a < 0]
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg):
                l = m
            else:
                r = m
        return r


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(n, k, aaa))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import bisect

n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
minuss = []
pluss = []
zeros = []
for item in a:
    if item > 0:
        pluss.append(item)
    elif item < 0:
        minuss.append(item)
    else:
        zeros.append(0)
pluss.sort()
minuss.sort()
a.sort()

p_len = len(pluss)
m_len = len(minuss)
z_len = len(zeros)

minus_num = p_len * m_len
zeros_num = z_len * (z_len - 1) // 2 + z_len * (m_len + p_len)

l = - 10**19; r = 10**19
while r - l > 1:
    mid = (l + r) // 2
    cnt = 0
    if mid > 0:
        # pluss
        ret = 0
        for item in pluss:
            ret += bisect.bisect_right(pluss, mid // item)
            if item * item <= mid:
                ret -= 1
        cnt += ret // 2
        ret = 0
        for item in minuss:
            ret += m_len - bisect.bisect_left(minuss, (mid + item + 1) // item)
            if item * item <= mid:
                ret -= 1
        cnt += ret // 2
        # minus
        cnt += minus_num
        # zeros
        cnt += zeros_num
    elif mid == 0:
        # minus
        cnt += minus_num
        # zeros
        cnt += zeros_num
    else:
        for item in pluss:
            cnt += bisect.bisect_right(minuss, mid // item)
    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 = 1001001001001001001
a.sort()
l=-INF
r=INF
while(l+1<r):
    x=(l+r)//2
    tot=0
    for i in range(n):
        if a[i]<0:
            l2=-1
            r2=n
            while l2+1<r2:
                c2=(l2+r2)//2
                if a[i]*a[c2]<x:
                    r2=c2
                else:
                    l2=c2
            tot+=n-r2
        else:
            l2=-1
            r2=n
            while l2+1<r2:
                c2=(l2+r2)//2
                if a[i]*a[c2]<x:
                    l2=c2
                else:
                    r2=c2
            tot+=r2
        if a[i]**2<x:
            tot-=1
    tot//=2
    if k>tot:
        l=x
    else:
        r=x

print(l)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

# x以下の数がK個以上かどうか
def check(x):
    # 各aについて、条件を満たす数を数える
    ans = 0
    # + * +
    for i, a in enumerate(A3):
        # 式変形： a * b <= x → b <= floor(x / a)
        # 重複カウントを避けるため、indexを調整
        ans += max(bisect_right(A3, x // a) - (i+1), 0)
    # - * - 
    for i, a in enumerate(A1b):
        ans += max(bisect_right(A1b, x // a) - (i+1), 0)
    # - * +
    for i, a in enumerate(A3):
        ans += bisect_right(A1, x // a)
    # 0 * -, 0 * +, 0 * 0
    cnt0 = N2 * N1 + N2 * N3 + N2 * (N2-1) // 2
    if x >= 0:
        ans += cnt0
    return ans >= K

N, K = MAP()
A = LIST()

A.sort()
# -, 0, + をそれぞれ別配列に分ける
A1, A1b, A2, A3 = [], [], [], []
for a in A:
    if a < 0:
        A1.append(a)
        A1b.append(-a)
    elif a == 0:
        A2.append(a)
    else:
        A3.append(a)
A1b = A1b[::-1]
N1 = len(A1)
N2 = len(A2)
N3 = len(A3)

print(bisearch_min(-INF, INF, check))

Submission status: Time Limit Exceeded

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

list2=[]
for i in range(0,n-1):
    for j in range(i+1,n):
        temp=list1[i]*list1[j]
        list2.append(temp)

list2.sort()
print(list2[k-1])

Submission status: Time Limit Exceeded

Solution code:
import sys, copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

INF = int(10e18) + 1

def main():
	n,k = MI()
	a = LI()
	a.sort()

	def bs_underx(x,k):
		tot = 0
		for i in range(n):
			l = -1
			r = n
			if a[i] < 0 :
				while (1+l<r) :
					c = (l+r)//2
					if(a[c]*a[i] < x) : r  = c
					else : l = c
				tot += n - r
			else:
				while (1+l<r) :
					c = (l+r)//2
					if(a[c]*a[i] < x) : l  = c
					else : r = c
				tot += r
			if a[i]*a[i] < x : tot-=1
		tot /= 2
		return tot < k

	l = -INF
	r = INF
	while l+1 < r:
		x = (l+r)//2
		if (bs_underx(x,k)) : l = x
		else: r = x
	print(l)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

# x以下の数がK個以上かどうか
def check(x):
    # 各aについて、条件を満たす数を数える
    ans = 0
    # + * +
    for i, a in enumerate(A3):
        # 式変形： a * b <= x → b <= floor(x / a)
        ans += bisect_right(A3[i+1:], x // a)
    # - * - 
    for i, a in enumerate(A1b):
        ans += bisect_right(A1b[i+1:], x // a)
    # - * +
    for i, a in enumerate(A3):
        ans += bisect_right(A1, x // a)
    # 0 * -, 0 * +, 0 * 0
    cnt0 = N2 * N1 + N2 * N3 + N2 * (N2-1) // 2
    if x >= 0:
        ans += cnt0
    return ans >= K

N, K = MAP()
A = LIST()

A.sort()
# -, 0, + をそれぞれ別配列に分ける
A1, A1b, A2, A3 = [], [], [], []
for a in A:
    if a < 0:
        A1.append(a)
        A1b.append(-a)
    elif a == 0:
        A2.append(a)
    else:
        A3.append(a)
A1b = A1b[::-1]
N1 = len(A1)
N2 = len(A2)
N3 = len(A3)

print(bisearch_min(-INF, INF, check))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left as bl
    from bisect import bisect_right as br

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

    inf = 10**18+1

    ok = -inf
    ng = inf
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        for i in a:
            if i < 0:
                if mid % i == 0:
                    cnt += n - br(a, mid//i)
                else:
                    cnt += n - br(a, mid//i + 0.5)
            elif i > 0:
                if mid % i == 0:
                    cnt += bl(a, mid//i)
                else:
                    cnt += bl(a, mid//i + 0.5)
            else:
                if mid > 0:
                    cnt += n
                else:
                    cnt += 0
        for i in a:
            if i*i < mid:
                cnt -= 1
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Submission status: Time Limit Exceeded

Solution code:
n, K = map(int, input().split())
a = sorted(list(map(int, input().split())))
inf = 10**18 + 1
l = -1 * inf
r = inf
while(l + 1 < r):
  c = (l + r)//2
  count = 0
  for i in range(n):
    #a[i]の符号で場合分け
    #a[i] < 0 の場合あるkが存在してk < jならばa[i]*a[j]はある値x未満になる。 
    if a[i] < 0:
      start = -1 #OUT
      end = n #OK
      while start + 1 < end:
        mid = (start + end) //2
        if a[i] * a[mid] < c:
          end = mid
        else:
          start = mid
      count += (n-end)
      if start < i:
        count -= 1
    else:#a[i]の符号が逆なので前と逆の操作を行えばよい。
      start = -1 #OK
      end = n #OUT
      while start + 1 < end:
        mid = (start + end)//2
        if a[i] * a[mid] < c:
          start = mid
        else:
          end = mid
      count += end
      if a[i] * a[i] < c:
        count -= 1
  count = (count // 2)
  if count < K:
    l = c
  else:
    r = c
print(l)

Submission status: Time Limit Exceeded

Solution code:
import sys, copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

INF = 10e18 + 1

def main():
	n,k = MI()
	a = LI()
	a.sort()

	def bs_underx(x,k):
		tot = 0
		for i in range(n):
			l = -1
			r = n
			if a[i] < 0 :
				while (1+l<r) :
					c = (l+r)//2
					if(a[c]*a[i] < x) : r  = c
					else : l = c
				tot += n - r
			else:
				while (1+l<r) :
					c = (l+r)//2
					if(a[c]*a[i] < x) : l  = c
					else : r = c
				tot += r
			if a[i]*a[i] < x : tot-=1
		tot /= 2
		return tot < k

	l = int(-INF)
	r = int(INF)
	while l+1 < r:
		x = (l+r)//2
		if (bs_underx(x,k)) : l = x
		else: r = x
	print(l)





if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left as bl
    from bisect import bisect_right as br

    def b_search(ok, ng, value):
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if value(mid):
                ok = mid
            else:
                ng = mid
        return ok

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

    inf = 10**18+1

    def check(x):
        cnt = 0
        for i in a:
            if i < 0:
                if x % i == 0:
                    cnt += n - br(a, x//i)
                else:
                    cnt += n - br(a, x//i + 0.1)
            elif i > 0:
                if x % i == 0:
                    cnt += bl(a, x//i)
                else:
                    cnt += bl(a, x//i + 0.1)
            else:
                if x > 0:
                    cnt += n
                else:
                    cnt += 0
        for i in a:
            if i*i < x:
                cnt -= 1
        return cnt//2 < k

    print(b_search(-inf, inf, check))


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# スペース区切りの整数入力
N,K = map(int, input().split())
# スペース区切りの整数をリストに入力
#a = []
am = []
az = []
ap = []

for x in list(map(int, input().split())):
    if x > 0:
        ap.append(x)
    elif x == 0:
        az.append(x)
    else:
        am.append(x)
    #a.append(x)

#n = len(a)*(len(a)-1) // 2
nm = len(am)*len(ap)
nz = len(az)*(len(az)-1) // 2 + len(az)*(len(am)+len(ap))
np = len(am)*(len(am)-1) // 2 + len(ap)*(len(ap)-1) // 2

xl = []
if K <= nm:
    for i in range(len(am)):
        for j in range(len(ap)):
            xl.append(am[i]*ap[j])
elif K - nm <= nz:
    print(0)
    sys.exit()
else:
    K = K - nm - nz
    for i in range(len(am)-1):
        for j in range(i+1,len(am)):
            xl.append(am[i]*am[j])
    for i in range(len(ap)-1):
        for j in range(i+1,len(ap)):
            xl.append(ap[i]*ap[j])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(i) for i in input().split()]
Pos,Zero,Neg=[],[],[]

for i in L:
    if i>0:
        Pos.append(i)
    elif i==0:
        Zero.append(i)
    else:
        Neg.append(i)

P=int(len(Pos)*(len(Pos)-1)/2+len(Neg)*(len(Neg)-1)/2)
Z=int(len(Zero)*(len(Zero)-1)/2+len(Zero)*(len(Pos)+len(Neg)))
Ne=int(len(Pos)*len(Neg))
A=int(N*(N-1)/2)

if K<=Ne:
    NeL=[Pos[i]*Neg[j] for i in range(len(Pos)) for j in range (len(Neg))]
    print(sorted(NeL)[K-1])

elif Ne<K<=Ne+Z:
    print(0)

else:
    if len(Pos)==1:
        PoL = [Neg[i] * Neg[i + j] for i in range(0, len(Neg) - 1) for j in range(1, len(Neg)-i)]
    elif len(Neg)==1:
        PoL = [Pos[i] * Pos[i + j] for i in range(0, len(Pos) - 1) for j in range(1, len(Pos)-i)]
    else:
        PoL=[Pos[i]*Pos[i+j] for i in range(0,len(Pos)-1) for j in range(1,len(Pos)-i)]
        PoL+=[Neg[i]*Neg[i+j] for i in range(0,len(Neg)-1) for j in range(1,len(Neg)-i)]
    print(sorted(PoL,reverse=True)[A-K])

Submission status: Time Limit Exceeded

Solution code:
import sys
# スペース区切りの整数入力
N,K = map(int, input().split())
# スペース区切りの整数をリストに入力
a = []
am = []
az = []
ap = []

for x in list(map(int, input().split())):
    if x > 0:
        ap.append(x)
    elif x == 0:
        az.append(x)
    else:
        am.append(x)
    a.append(x)

n = len(a)*(len(a)-1) // 2
nm = len(am)*len(ap)
nz = len(az)*(len(az)-1) // 2 + len(az)*(len(am)+len(ap))
np = len(am)*(len(am)-1) // 2 + len(ap)*(len(ap)-1) // 2

xl = []
if K <= nm:
    for i in range(len(am)):
        for j in range(len(ap)):
            xl.append(am[i]*ap[j])
elif K - nm <= nz:
    print(0)
    sys.exit()
else:
    K = K - nm - nz
    for i in range(len(am)-1):
        for j in range(i+1,len(am)):
            xl.append(am[i]*am[j])
    for i in range(len(ap)-1):
        for j in range(i+1,len(ap)):
            xl.append(ap[i]*ap[j])

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
minus = [-x for x in a if x < 0]
plus = [x for x in a if x >= 0]

minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        x = -x
        r = 0
        for num in minus[::-1]:
            while r < len(plus) and plus[r] * num < x:
                r += 1
            ans += len(plus) -  r
        return ans

    r = 0
    for num in minus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(minus) and minus[r] * num <= x:
            r += 1
        ans += r
    r = 0
    for num in plus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(plus) and plus[r] * num <= x:
            r += 1
        ans += r
    ans //= 2
    ans += len(minus) * len(plus)
    return ans

bottom = 0
top = 2*(10**18) + 2


while top - bottom > 1:
    mid = (top + bottom) // 2
    if cnt(mid - 10**18-1) < k:
        bottom = mid
    else:
        top = mid

print(int(top - 10**18-1))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product, combinations

N,K = map(int, input().split())
minus = 0
zero = 0
plus = 0
Amin,Azero,Aplu = [],[],[]
for i in input().split():
    i = int(i)
    if i < 0:
        minus += 1
        Amin.append(i)
    elif i == 0:
        zero += 1
        Azero.append(i)
    else:
        plus += 1
        Aplu.append(i)

pair_min = minus*plus
pair_zero = zero*(minus+plus)
if zero > 1:
    pair_zero += zero*(zero-1)//2
pair_plu = N*(N-1)//2 - pair_min - pair_zero

if K <= pair_min:
    lis = []
    for a1,a2 in product(Amin,Aplu):
        lis.append(a1*a2)
    lis.sort()
    print(lis[K-1])
elif K > pair_min and K <= (pair_min + pair_zero):
    print(0)
else:
    lis = []
    for a1,a2 in combinations(Amin,2):
        lis.append(a1*a2)
    for a1,a2 in combinations(Aplu,2):
        lis.append(a1*a2)
    lis.sort()
    print(lis[K-(pair_min + pair_zero)-1])

Submission status: Time Limit Exceeded

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

from itertools import combinations, starmap


multiple_list = tuple(combinations(A, 2))
multiple_result_list = tuple(starmap(lambda x, y: x*y, multiple_list))


result_sorted = sorted(multiple_result_list)

print(result_sorted[K-1])

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()))

    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])
    plus.sort()
    minus.sort()

    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
            for i in range(len(plus)):
                target = mid//plus[i]
                # target以下の数をminusから見つける
                count += bisect_right(minus,target)
            
            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
            for i in range(len(plus)):
                target = mid//plus[i]
                # target以下の数をplusから見つける
                count += bisect_right(plus,target)
                if plus[i] <= target:
                    count -= 1

            for i in range(len(minus)):
                target = mid//minus[i]
                # target以下の数をplusから見つける
                count += bisect_right(minus,target)
                if minus[i] <= target:
                    count -= 1
            if count//2 >= K:
                right = mid
            else:
                left = mid
        print(right)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
line = input().split(" ")
N, K = [int(i) for i in line]
line = input().split(" ")

pairs = sorted(combinations([int(a) for a in line], 2), key=lambda x: x[0] * x[1])

ans = pairs[K - 1]
print(ans[0] * ans[1])