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 bisect


def solve(mid):
    # mid以下の通り数を求める
    cnt = 0
    if mid > 0:
        # 正と正の組み合わせ
        for i, num in enumerate(plus):
            tmp = mid // num
            ind = bisect.bisect_right(plus, tmp, lo=i+1)
            cnt += ind - (i + 1)
        # 負と負の組み合わせ
        for i, num in enumerate(minus_plus):
            tmp = mid // num
            ind = bisect.bisect_right(minus_plus, tmp, lo=i+1)
            cnt += ind - (i + 1)
    #print(cnt)

    if mid >= 0:
        # 正と負の組み合わせ
        cnt += len(minus_plus) * len(plus)
    #print(cnt)

    if mid < 0:
        # 正と負の組み合わせ
        for i, num in enumerate(plus):
            tmp = -((mid) // num)
            ind = bisect.bisect_left(minus_plus, tmp)
            cnt += len(minus_plus) - ind
    #print(cnt)
    
    if mid >= 0:
        cnt += cnt_0
    #print(cnt)

    if cnt >= k:
        return True
    else:
        return False


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

plus = []
minus_plus = []
cnt0 = 0
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus_plus.append(-a[i])
    else:
        cnt0 += 1
plus = sorted(plus)
minus_plus = sorted(minus_plus)

# 答えが0になる場合
cnt_0 = (len(plus) + len(minus_plus)) * cnt0
cnt_0 += cnt0 * (cnt0 - 1) // 2


ng = -10**20
ok = 10**20

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)
"""
tmp = []
for i in range(n):
    for j in range(i + 1, n):
        tmp.append(a[i] * a[j])
tmp = sorted(tmp)
print(tmp[0:10])
print(tmp[10:20])
print(tmp[20:30])
print(tmp[30:40])
print(tmp[40:50])"""

Submission status: Time Limit Exceeded

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

N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = []
for i,num in enumerate(A):
    for j in range(i+1,N):
        ans.append(num * A[j])
ans.sort()
print(ans[K-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
N, K = input().split()
A = input().split()
N = int(N)
K = int(K)
A = list(map(int, A))
 
B = []
for i in range(N):
    for j in range(N):
        if i>j:
            B.append(np.dot(A[i], A[j]))
 
B.sort()
print(B[K-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=tuple(A)
    x=bisect_left(A,0)
    y=bisect_right(A,0)
    A_minus=tuple(A[:x])
    A_zero=tuple(A[x:y])
    A_plus=tuple(A[y:])
    if K<=len(A_minus)*len(A_plus):
        def nibutan1(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve1(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve1(mid):
            c=0
            for x in A_minus:
                c+=len(A_plus)-bisect_left(A_plus,-(-mid//x))
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan1(0,-10**18+1))
    K-=len(A_minus)*len(A_plus)
    if 0<K<=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2:
        print(0)
    K-=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2
    if K>0:
        def nibutan2(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve2(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve2(mid):
            c=0
            for x in A_minus:
                c+=len(A_minus)-bisect_left(A_minus,-(-mid//x))
                if -(-mid//x)<=x:
                    c-=1
            for x in A_plus:
                c+=bisect_right(A_plus,(mid//x))
                if (mid//x)>=x:
                    c-=1
            c//=2
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan2(10**18+1,0))

    
        
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from bisect import bisect_left, bisect_right

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

    As.sort()
    negAs = [-A for A in As[::-1]]
    A2s = [A*A for A in As]
    A2s.sort()

    pstvBs = []
    numB0= 0
    ngtvBs = []
    for A in As:
        if A > 0:
            pstvBs.append(A)
        elif A == 0:
            numB0 += 1
        else:
            ngtvBs.append(A)

    def isOK(x):
        if x >= 0:
            dire = 1
        else:
            dire = -1
        num = 0
        # 正
        iA = 0
        for B in pstvBs[::-dire]:
            key = x//B
            while iA < N and As[iA] <= key:
                iA += 1
            num += iA
        # ゼロ
        if x >= 0:
            num += N*numB0
        # 負
        iA = 0
        for B in ngtvBs[::dire]:
            key = x//(-B)
            while iA < N and negAs[iA] <= key:
                iA += 1
            num += iA
        i = bisect_right(A2s, x)
        num -= i
        num //= 2
        return num >= K

    ng, ok = -(10**18)-1, 10**18+1
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	n,k=map(int,input().split())
	A=list(map(int,input().split()))
	A.sort()
	h=10**18
	l=-10**18
	x=0
	while l+1<h:
		x=(h+l)//2
		cnt=0
		for i in A:
			if i<0:
				cnt+=n-bisect.bisect_left(A,-(-x//i))
			elif i>0:
				cnt+=bisect.bisect_right(A,x//i)
			else:
				if x>=0:
					cnt+=n
		
		if x>=0:
			for i in A:
				if i*i<=x:
					cnt-=1
		
		
		cnt//=2
		if cnt<k:
			l=x
		else:
			h=x
	print(h)
	
	
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main(n,k,a):
    minus = [i for i in a if i < 0]
    plus = [i for i in a if i >= 0]
    mpcount = len(minus) * len(plus)
    if k <= mpcount:
        lst = [i[0]*i[1] for i in itertools.product(minus,plus)]
        lst.sort()
        return lst[k-1]
    else:
        lst = ([i[0]*i[1] for i in itertools.combinations(minus,2)]
                + [i[0]*i[1] for i in itertools.combinations(plus,2)])
        lst.sort()
        return lst[k-1-mpcount]    

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

Submission status: Time Limit Exceeded

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


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

result = []
r_append = result.append

for i in range(0,n-1):
	for j in range(i,n-1):
		tem = a[i] * a[j+1]
		r_append(tem)

result.sort()

print(result[k-1])

Submission status: Time Limit Exceeded

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

result = [v[0] * v[1] for v in itertools.combinations(A, 2)]
result.sort()

print(result[K-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def check(num, input_list):
    multi_list = []
    
    for i in range(num):
        for j in range(num - i - 1):
            multi_list.append(input_list[i] * input_list[i + j + 1])

    multi_list.sort()
    return multi_list

if __name__ == '__main__':
    num, index = input().split()
    num = int(num)
    index = int(index)
    input_list = [int(a) for a in input().split()]

    print(check(num, input_list)[index - 1])

Submission status: Time Limit Exceeded

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

a.sort()
xlist = []
for i in range(N-1):
    for j in range(N-1,i,-1):
        xlist.append(a[i]*a[j])

xlist.sort()

print(xlist[K-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
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])
print(sorted(L)[K-1])

Submission status: Time Limit Exceeded

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

k -= 1
cnt = [0] * 3

li_minus = []
li_zero = []
li_plus = []

a.sort()
for val in a:
    if val < 0:
        cnt[0] += 1
        li_minus.append(val)
    elif val > 0:
        cnt[2] += 1
        li_plus.append(val)
    else:
        cnt[1] += 1
        li_zero.append(val)

x, z, y = cnt

minus = x * y
zero = (2*n-z-1)*z//2
plus = (x-1)*x//2 + (y-1)*y//2

if k < minus:
    li = []
    li_ot = li_zero + li_plus
    for i in range(len(li_minus)):
        for j in range(len(li_ot)):
            li.append(li_minus[i] * li_ot[j])
    li.sort()
    print(li[k])
elif minus <= k+1 <= minus + zero:
    print(0)
else:
    li = []
    for i in range(len(li_minus)-1):
        for j in range(i+1, len(li_minus)):
            li.append(li_minus[i] * li_minus[j])
    for i in range(len(li_plus)-1):
        for j in range(i+1, len(li_plus)):
            li.append(li_plus[i] * li_plus[j])
    li.sort()
    s = n*(n-1)//2
    print(li[-(s-(k))])

Submission status: Time Limit Exceeded

Solution code:
import bisect as bs
from decimal import Decimal
N, K = map(int,input().split())
a = sorted(list(map(int,input().split())))
INF = 10**18
l = -INF
r = INF
while (r - l > 1):
    mid = (l+r)//2
    cnt = 0
    for i in range(1,N):
        if a[i-1] < 0:
            cnt += N-i-bs.bisect_left(a[i:], Decimal(mid)/a[i-1])
        elif a[i-1] > 0:
            cnt += bs.bisect_right(a[i:], Decimal(mid)/a[i-1])
        else:
            if mid >= 0:
                cnt += N-i
    if cnt < K:
        l = mid
    else:
        r = mid
    
for p in range(l+1, r+1):
    cnt = 0
    for i in range(1,N):
        if a[i-1] < 0:
            cnt += N-i-bs.bisect_left(a[i:], Decimal(p/a[i-1]))
        elif a[i-1] > 0:
            cnt += bs.bisect_right(a[i:], Decimal(p/a[i-1]))
        else:
            if p >= 0:
                cnt += N-i
    if K <= cnt:
        print(p)
        exit(0)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	n,k=map(int,input().split())
	A=list(map(int,input().split()))
	A.sort()
	h=10**18
	l=-10**18
	x=0
	while l+1<h:
		x=(h+l)//2
		cnt=0
		for i in A:
			if i<0:
				cnt+=n-bisect.bisect_left(A,-(-x//i))
				if i>=-(-x//i):
					cnt-=1
			elif i>0:
				cnt+=bisect.bisect_right(A,x//i)
				if i<=x//i:
					cnt-=1
			else:
				if x>=0:
					cnt+=n-1
		cnt//=2
		if cnt<k:
			l=x
		else:
			h=x
	print(h)
	
	
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = list(map(int, input().split()))
A_N = list(map(int, input().split()))
B = []
b = 0
for i in range(N-1):
    for j in range(i, N-1):
        b = A_N[i] * A_N[j+1]
        B.append(b)
        b = 0
B = sorted(B)
# print(B)
print(B[K-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(x) for x in input().split()]
LL=[L[i]*L[i+j] for i in range(0,N) for j in range(1,N-i)]
print(sorted(LL)[K-1])

Submission status: Time Limit Exceeded

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

def calc(i,n):
    a = A[i]
    if a==0:
        return 0 if n<0 else N-i-1
    if a>0:
        ok = i
        ng = N
        while ng-ok > 1:
            m = (ok+ng)//2
            if m==i or a*A[m]<=n:
                ok = m
            else:
                ng = m
        return ok-i
    else:
        ok = N
        ng = i
        while ok-ng > 1:
            m = (ok+ng)//2
            if m==i or a*A[m]>n:
                ng = m
            else:
                ok = m
        return N-ok

def is_ok(m):
    k = 0
    for i in range(N-1):
        k += calc(i,m)
        if k >= K: return True
    return False

ng = -10**18-1
ok = 10**18+1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Time Limit Exceeded

Solution code:
N, K= map(int, input().split())
A = list(map(int, input().split()))
#A.sort()
seki = []
#print(A)
for i in range(len(A)):
    for j in range(i+1,len(A)):
        seki.append(A[i]*A[j])

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,k=map(int,input().split())
l=[int(i) for i in input().split()]
l.sort()
a=-1000000000000000001
b=1000000000000000001
while b-a>1:
    c=(a+b)//2
    cntl=0
    cntg=0
    lastcntl=0
    lastcntg=0
    for i in l:
        if i>0:
            x=c//i
            ind=bisect.bisect_left(l,x)
            if ind==n:
                cntl+=n-1
            else:
                if i*l[ind]==c:
                    cntl+=ind
                    ind=bisect.bisect_right(l,x)
                else:
                    ind=bisect.bisect_right(l,x)
                    cntl+=ind
                cntg+=n-ind
                if i*i>c:
                    cntg-=1
                elif i*i<c:
                    cntl-=1
        elif i==0:
            if c<0:
                cntg+=n-1
            elif c>0:
                cntl+=n-1
        else:
            x=c//i
            ind=bisect.bisect_left(l,x)
            if ind==n:
                cntg+=n-1
            else:
                if i*l[ind]==c:
                    cntg+=ind
                    ind=bisect.bisect_right(l,x)
                else:
                    ind=bisect.bisect_right(l,x)
                    cntg+=ind
                cntl+=n-ind
                if i*i>c:
                    cntg-=1
                elif i*i<c:
                    cntl-=1
        lastcntl=cntl
        lastcntg=cntg
    cntl//=2
    cntg//=2
    if cntl+cntg<n*(n-1)//2 and cntl+1<=k<=n*(n-1)//2-cntg:
        print(c)
        break
    if cntl>=k:
        b=c
    else:
        a=c

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import functools
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    @functools.lru_cache()
    def new_bisect_left(A,x):
        return bisect_left(A,x)
    
    @functools.lru_cache()
    def new_bisect_right(A,x):
        return bisect_right(A,x)
    
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=tuple(A)
    A_minus,A_zero,A_plus=[],[],[]
    x=new_bisect_left(A,0)
    y=new_bisect_right(A,0)
    A_minus=tuple(A[:x])
    A_zero=tuple(A[x:y])
    A_plus=tuple(A[y:])
    if K<=len(A_minus)*len(A_plus):
        def nibutan1(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve1(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve1(mid):
            c=0
            for x in A_minus:
                c+=len(A_plus)-new_bisect_left(A_plus,-(-mid//x))
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan1(0,-10**18-1))
    K-=len(A_minus)*len(A_plus)
    if 0<K<=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2:
        print(0)
    K-=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2
    if K>0:
        def nibutan2(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve2(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve2(mid):
            c=0
            for x in A_minus:
                c+=len(A_minus)-new_bisect_left(A_minus,-(-mid//x))
                if -(-mid//x)<=x:
                    c-=1
            for x in A_plus:
                c+=new_bisect_right(A_plus,(mid//x))
                if (mid//x)>=x:
                    c-=1
            c//=2
            if c>=K:
                return True
            else:
                return False
        print(nibutan2(10**18+1,0))

    
        
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

t=[]

for a,b in itertools.combinations(s,2):
  t.append(a*b)

t.sort()

print(t[k-1])

Submission status: Time Limit Exceeded

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

res = []

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

list.sort(res)

print(res[K-1])

Submission status: Time Limit Exceeded

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


a.sort()

nums=[a[0]]
counts=[1]
stop_posi=0
keep_same={}

for i in range(1,N):
    if a[i-1]==a[i]:
        counts[stop_posi]+=1
        if counts[stop_posi]==2:
            keep_same[a[i]]=2
        else:
            keep_same[a[i]]+=1
    else:
        nums.append(a[i])
        counts.append(1)
        stop_posi+=1

result_dic= {}
for i in range(0,len(nums)-1):
    for k in range(i+1,len(nums)):
        result_dic.setdefault(nums[i]*nums[k],0)
        result_dic[nums[i]*nums[k]]+=counts[i]*counts[k]
for same in keep_same:
  result_dic.setdefault(same**2,0)
  result_dic[same**2]+=int(keep_same[same]*(keep_same[same]-1)/2)

result_dic_sorted = sorted(result_dic.items(), key=lambda x:x[0])


total_num=0
for i in range(len(result_dic_sorted)):
    total_num+=result_dic_sorted[i][1]
    if total_num>=K:
        print(result_dic_sorted[i][0])
        break

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K= map(int, input().split())
A = list(map(int, input().split()))

A.sort()
Am = [i for i in A if i < 0]
Ap = [i for i in A if i >= 0]
Nm = len(Am)
Np = len(Ap)

Sm = Nm*Np
ans = []
if(K<=Sm):
  for i in Am:
    for j in Ap:
      ans.append(i*j)
  ans.sort()
  print(ans[K-1])
else:
  for i in range(Nm):
    for j in range(i+1, Nm):
      ans.append(Am[i]*Am[j])
  for i in range(Np):
    for j in range(i+1, Np):
      ans.append(Ap[i]*Ap[j])

  ans.sort()
  print(ans[K-Sm-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import os
import datetime

def main():
    a, b = map(int, input().split())
    val = list(map(lambda x: int(x), input().split()))

    result_dict = []

    for i in range(len(val)):
        for j in range(i+1, len(val)):
            result_dict.append(val[i] * val[j])

    min_list = sorted(result_dict)
    print(min_list[b-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N = 2*10**5
K = 10000
A = [10**9]*(N//2)+[-10**9]*(N//2)

A.sort()



def count(m):
    res = 0
    for i in range(N):
        a = A[i]
        if a==0:
            if m>=0:
                res += N
        elif a>0:
            r = m/a
            j = bisect(A,r)
            res += j
        else:
            r = m/a
            j = bisect_left(A,r)
            res += N-j
        if a**2<=m:
            res -= 1
    res //= 2
    return res

def count1(m):
    res = 0
    cand = -10**19
    for i in range(N):
        a = A[i]
        if a==0:
            if m>=0:
                res += N
        elif a>0:
            r = m/a
            j = bisect(A,r)
            res += j
            if j!= 0:
                cand = max(cand,a*A[j-1])
        else:
            r = m/a
            j = bisect_left(A,r)
            res += N-j
            if j != N:
                cand = max(cand,a*A[j])
        if a**2<=m:
            res -= 1
    res //= 2
    return res,cand


l = -10**18
r = 10**18
m = (l+r)/2
for i in range(65):
    k = count(m)
    if k < K:
        l = m
    else:
        r = m
    m = (l+r)/2
k,ans = count1(r)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import functools
import operator
n,k = map(int, input().split())
a = list(map(int, input().split()))
tmp = []
for i in itertools.combinations(a, 2):
    v = functools.reduce(operator.mul, list(i))
    tmp.append(v)
tmp = sorted(tmp)
print(tmp[k-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    c = []
    for i in range(len(a)):
        for j in range(i+1,len(a)):
            c.append(a[i]*a[j])
            c.sort()
    print(c[K-1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
list = list(map(int, input().split()))
len = len(list)
rlist = []
i=0

while(i<len):
  j=i+1
  while(j<len):
    rlist.append(list[i] * list[j])
    j+=1
  i+=1

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, K = list(map(int,input().split()))
    A = list(map(int,input().split()))
    A.sort()
    B = []
    minus = len(list(filter(lambda x:x<0, A)))
    for i in range(minus):
        for j in range(N-1,i,-1):
            B.append(A[i]*A[j])
    if minus*(N-minus)<K:
        for i in range(minus,min(N,minus+K)):
                #for j in range(i+1,min(i+int(math.sqrt(K))+2,N)):
                for j in range(i+1,N):
                    B.append(A[i]*A[j])
    B.sort()
    print(B[K-1])

solve()

Submission status: Time Limit Exceeded

Solution code:
import bisect

N,K = map(int,input().split())
L=list(map(int,input().split()))
L=sorted(L)
LIST=[]
c=0
for l in range(N-1):
    t=L[l]
    if t>0:
        for i in range(l+1,N):
            n=t*L[i]
            if c<K:
                index = bisect.bisect_left(LIST, n) # 2 最も左(前)の挿入箇所が返ってきている
                LIST.insert(index, n)
                c+=1
            else:
                if(LIST[K-1]>n):
                    index = bisect.bisect_left(LIST, n) # 2 最も左(前)の挿入箇所が返ってきている
                    LIST.insert(index, n)
                    c+=1
                else:
                    break
    else:
        for i in range(N-1,l,-1):
            n=t*L[i]
            if c<K:
                index = bisect.bisect_left(LIST, n) # 2 最も左(前)の挿入箇所が返ってきている
                LIST.insert(index, n)
                c+=1
            else:
                if(LIST[K-1]>n):
                    index = bisect.bisect_left(LIST, n) # 2 最も左(前)の挿入箇所が返ってきている
                    LIST.insert(index, n)
                    c+=1
                else:
                    break
print(LIST[K-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, bisect_right


TEST_INPUT = [
    """
    4 3
    3 3 -4 -2
    """,
    """
    10 40
    5 4 3 2 -1 0 0 0 0 0
    """,
    """
    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
    """
]
ANSWER = [
    "-6",
    "6",
    "448283280358331064"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


def query(a, n, a_list_s, k):
    res = 0

    for i in range(n - 1):
        p = a_list_s[i]
        if p > 0:
            q = (a + p - 1) // p
            res += min(n - bisect_left(a_list_s, q), n - i - 1)
        elif p == 0:
            if a <= 0:
                res += n - i - 1
        else:
            q = a // p
            res += max(bisect_right(a_list_s, q) - (i + 1), 0)
    if res < n * (n - 1) // 2 - k + 1:
        return False
    else:
        return True


def solve(n, k, a_list):

    a_list_s = list(sorted(a_list))

    left = - 10 ** 18 - 1
    right = 10 ** 18 + 1
    center = 0

    while right > left + 1:
        if query(center, n, a_list_s, k):
            left, center = center, (center + right) // 2
        else:
            center, right = (left + center) // 2, center

    return left


def input_and_solve(ih):
    n, k = map(int, ih.input().split())
    a_list = list(map(int, ih.input().split()))
    res = solve(n, k, a_list)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        assert str(res) == str(ans)


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

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

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

print(sorted(b)[k-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

# process
B = []
for x, y in itertools.combinations(A, 2):
    B.append(x*y)

B.sort()

# output
print(B[K-1])

Submission status: Time Limit Exceeded

Solution code:
import bisect as bs
from decimal import Decimal
N, K = map(int,input().split())
a = sorted(list(map(int,input().split())))
INF = 10**18
l = -INF
r = INF
while (r - l > 1):
    mid = (l+r)//2
    cnt = 0
    for i in range(1,N):
        if a[i-1] < 0:
            cnt += N-i-bs.bisect_left(a[i:], Decimal(mid)/a[i-1])
        elif a[i-1] > 0:
            cnt += bs.bisect_right(a[i:], Decimal(mid)/a[i-1])
        else:
            if mid >= 0:
                cnt += N-i
    if cnt < K:
        l = mid
    else:
        r = mid
    
for p in range(l+1, r+1):
    cnt = 0
    for i in range(1,N):
        if a[i-1] < 0:
            cnt += N-i-bs.bisect_left(a[i:], p/a[i-1])
        elif a[i-1] > 0:
            cnt += bs.bisect_right(a[i:], p/a[i-1])
        else:
            if p >= 0:
                cnt += N-i
    if K <= cnt:
        print(p)
        exit(0)

Submission status: Time Limit Exceeded

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

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

memo_p =[]
memo_m =[]

for i in range(N):
	for j in range(i+1,N):
		if A[i]*A[j]>0:
			memo_p.append(A[i]*A[j])
		else:
			memo_m.append(A[i]*A[j])
memo_m.sort()
if len(memo_m) >= K:
	print(memo_m[K-1])
else:
	memo_p.sort()
	K = K -len(memo_m)
	print(memo_p[K-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
A,B=map(int,input().split())
L=list(map(int,input().split()))
c = itertools.combinations(L, 2)
ans=[]
for i in c:
  ans.append(i[0]*i[1])
ans.sort()
print(ans[B-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
import bisect

n, k = map(int, raw_input().split())
seq = map(int, raw_input().split())

ls = []

memo = dict()

for n1, n2 in list(itertools.combinations(seq, 2)):
    try:
        r = memo[(n1, n2)]
        idx = bisect.bisect_left(ls, r)
        ls.insert(idx, r)
    except KeyError:
        r = n1 * n2
        memo[(n1, n2)] = r
        idx = bisect.bisect_left(ls, r)
        ls.insert(idx, r)
        
print ls[k-1]

Submission status: Time Limit Exceeded

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