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())
A = list(map(int,input().split()))

A.sort()
neg = []
rev_neg= []
zero = []
pos = []
rev_pos = []
for i in A:
    if i<0:
        neg.append(-1*i)
        rev_neg.append(-1*i)
    elif i==0:
        zero.append(i)
    else:
        pos.append(i)
        rev_pos.append(i)

neg.sort()
rev_neg.sort()
rev_neg.reverse()
pos.sort()
rev_pos.sort()
rev_pos.reverse()

#print(len(neg),"neg",neg)
#print(len(pos),"pos",pos)
#print(len(zero),"zero",zero)

def cul_zero(a):
    if a > 0:
        return int(len(zero) * (len(pos)+ len(neg)) + (len(zero)*(len(zero)-1))/2)
    else:
        return 0

def rev_index(l,i):
    return len(l)-i-1

def cul_pos2(a,l):
    res = 0
    right = -1
    for i in range(len(l)):
        while(right+1<len(l) and l[rev_index(l,i)]*l[right + 1]<a):
            right = right + 1
        
        if rev_index(l,i) <= right:
            res = res + rev_index(l,i)
        else:
            res = res + (right + 1)

    return res

def cul_pos(a):
    if a <= 0:
        return 0

    #negative * negative < a
    res1 = cul_pos2(a,neg)
    #print(res1)
    #positive * positive < a
    res2 =  cul_pos2(a,pos)
    #print(res2)
    return res1+res2

def cul_neg(a):
    if a >= 0:
        return len(neg)*len(pos)
    
    res = 0
    right = -1
    for i in range(len(neg)):
        while(right+1 != len(pos) and -1 * rev_neg[i] * pos[right+1] >= a ):
            right = right + 1
    
        res = res + (right+1)
    return len(neg)*len(pos) - res

def get_under_a_num(a):
    c_neg = cul_neg(a)
    c_pos = cul_pos(a)
    c_zero = cul_zero(a)
    c_sum = c_neg + c_pos + c_zero
    #print("(get under a:",a,")",c_neg,c_zero,c_pos,c_sum)
    return c_sum


def binary_search(left,right,k):
    mid = int((left+right)//2)
    k_mid = get_under_a_num(mid)
    #print("(l,r,m=",left,right,mid,")",k_mid)
    if (left==right or left+1==right):
        return left
    if(k_mid < k):
        return binary_search(mid,right,k)
    if(k <= k_mid):
        return binary_search(left,mid,k)


def solve1():
    l = []
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            l.append(A[i]*A[j])

    l.sort()

    print(l[K-1])
    return l

def solve2():
    res = binary_search(-1*(10**9+1)**2,(10**9+1)**2,K)
    #print("K,",K,res)
    #print("K-1",binary_search(-1*(10**20)-1,10**20,K-1))
    return res

if __name__=="__main__":
    print(solve2())

Submission status: Time Limit Exceeded

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

A.sort()
neg = []
rev_neg= []
zero = []
pos = []
rev_pos = []
for i in A:
    if i<0:
        neg.append(-1*i)
        rev_neg.append(-1*i)
    elif i==0:
        zero.append(i)
    else:
        pos.append(i)
        rev_pos.append(i)

neg.sort()
rev_neg.sort()
rev_neg.reverse()
pos.sort()
rev_pos.sort()
rev_pos.reverse()

#print(len(neg),"neg",neg)
#print(len(pos),"pos",pos)
#print(len(zero),"zero",zero)

def cul_zero(a):
    if a > 0:
        return int(len(zero) * (len(pos)+ len(neg)) + (len(zero)*(len(zero)-1))/2)
    else:
        return 0

def rev_index(l,i):
    return len(l)-i-1

def cul_pos2(a,l):
    res = 0
    right = -1
    for i in range(len(l)):
        while(right+1<len(l) and l[rev_index(l,i)]*l[right + 1]<a):
            right = right + 1
        
        if rev_index(l,i) <= right:
            res = res + rev_index(l,i)
        else:
            res = res + (right + 1)

    return res

def cul_pos(a):
    if a <= 0:
        return 0

    #negative * negative < a
    res1 = cul_pos2(a,neg)
    #print(res1)
    #positive * positive < a
    res2 =  cul_pos2(a,pos)
    #print(res2)
    return res1+res2

def cul_neg(a):
    if a >= 0:
        return len(neg)*len(pos)
    
    res = 0
    right = -1
    for i in range(len(neg)):
        while(right+1 != len(pos) and -1 * rev_neg[i] * pos[right+1] >= a ):
            right = right + 1
    
        res = res + (right+1)
    return len(neg)*len(pos) - res

def get_under_a_num(a):
    c_neg = cul_neg(a)
    c_pos = cul_pos(a)
    c_zero = cul_zero(a)
    c_sum = c_neg + c_pos + c_zero
    #print("(get under a:",a,")",c_neg,c_zero,c_pos,c_sum)
    return c_sum


def binary_search(left,right,k):
    mid = int((left+right)//2)
    k_mid = get_under_a_num(mid)
    #print("(l,r,m=",left,right,mid,")",k_mid)
    if (left==right or left+1==right):
        return left
    if(k_mid < k):
        return binary_search(mid,right,k)
    if(k <= k_mid):
        return binary_search(left,mid,k)


def solve1():
    l = []
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            l.append(A[i]*A[j])

    l.sort()

    print(l[K-1])
    return l

def solve2():
    res = binary_search(-1*(10**20)-1,10**20,K)
    #print("K,",K,res)
    #print("K-1",binary_search(-1*(10**20)-1,10**20,K-1))
    return res

if __name__=="__main__":
    print(solve2())

Submission status: Time Limit Exceeded

Solution code:
import sys
 
lines = [l for l in sys.stdin]
l = lines[0].split(' ')
N, K = int(l[0]), int(l[1])
 
nums = [int(s) for s in lines[1].split(' ')]
 
rets = []
for idx, n1 in enumerate(nums[:-1]):
  for idy, n2 in enumerate(nums[idx+1:]):
    rets.append(n1 * n2)
rets.sort()
print(rets[K-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
import operator

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

print(sorted(itertools.starmap(operator.mul, itertools.combinations(A, 2)))[K - 1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, k = map(int, input().split())
li = list(map(int,input().split()))
c = itertools.combinations(li, 2)
ans = []
for i in c:
    ans.append(i[0] * i[1])
s_ans = sorted(ans)
print(s_ans[k - 1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    N,K = map(int, input().split())
    A = np.array(sorted([int(i) for i in input().split()]))

    zero_left = np.searchsorted(A, 0, side='left')
    zero_right = np.searchsorted(A, 0, side='right')

    negative = zero_left
    positive = N - zero_right
    zero = zero_right - zero_left
    non_posi = negative * positive + zero * (N - zero) + zero * (zero - 1) // 2

    if K <= negative * positive:
        Nega = A[:zero_left]
        Posi = A[zero_right:]

        left = -(A[0]**2)
        right = 0
        while right - left > 1:
            x = (left + right) // 2
            count = np.searchsorted(Nega, x // Posi, side='right').sum()

            if count < K:
                left = x
            else:
                right = x

        print(right)

    elif K <= non_posi:
        print(0)

    else:
        Nega = np.sort(np.abs(A[:zero_left]))
        Posi = A[zero_right:]

        left = 0
        right = 10**18
        while right - left > 1:
            x = (left + right) // 2
            count = 0
            count += np.searchsorted(Nega, x // Nega, side='right').sum()
            count += np.searchsorted(Posi, x // Posi, side='right').sum()
            count -= np.int_(np.where(np.searchsorted(Nega, x // Nega) >= np.arange(1,negative+1), True, False)).sum()
            count -= np.int_(np.where(np.searchsorted(Posi, x // Posi) >= np.arange(1,positive+1), True, False)).sum()
            count //= 2

            if count + non_posi < K:
                left = x
            else:
                right = x

        print(right)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

"""
for num1 in range(K):
    for num2 in range(K):
        mylist.append(A[num1] * A[(num1 + 1) + num2])
"""

for num1 in range(N-1):
    for num2 in range(N-(num1+1)):
        mylist.append(A[num1] * A[num1 + (num2 + 1)])

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

Submission status: Time Limit Exceeded

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

"""
for num1 in range(K):
    for num2 in range(K):
        mylist.append(A[num1] * A[(num1 + 1) + num2])
"""

for num1 in range(N-1):
    for num2 in range(N-(num1+1)):
        mylist.append(A[num1] * A[num1 + (num2 + 1)])

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

Submission status: Time Limit Exceeded

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

b = [a[i]*a[j] for i in range(n) for j in range(i+1, n)]
#list.sort(b)
print(sorted(b)[k-1])

Submission status: Time Limit Exceeded

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

b = [a[i]*a[j] for i in range(n) for j in range(i+1, n)]
list.sort(b)
print(b[k-1])

Submission status: Time Limit Exceeded

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

b = [a[i]*a[j] for i in range(n) for j in range(i+1, n)]
list.sort(b)
print(b[k-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = list(map(int, input().split()))
p = []
for a in range(n-1):
    for b in range(a+1, n):
        p.append(s[a]*s[b])
print(sorted(p)[k-1])

Submission status: Time Limit Exceeded

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

# 組み合わせの計算
def combination(x):
    return int((x * (x - 1)) / 2)

# 組み合わせのリストを作成
def list_conbination(l):
    list_c = []
    l_length = len(l)
    
    if l_length <= 1:
        return list_c
    
    for i in range(l_length):
        n = i + 1
        while n < l_length:
            list_c.append(l[i] * l[n])
            n += 1
    
    return list_c

# 負,0,正のリストを作成
minus = []
zero = []
plus = []
for i in a:
    if i < 0:
        minus.append(i)
    elif i == 0:
        zero.append(i)
    else:
        plus.append(i)

# 負,0,正の個数
minus_num = len(minus)
zero_num = len(zero)
plus_num = len(plus)

# 積が負,0,正になる個数
minus_ans_num = minus_num * plus_num
zero_ans_num = minus_num * zero_num + plus_num * zero_num + combination(zero_num)
plus_ans_num = combination(minus_num) + combination(plus_num)

# 小さい順に並べて、K番目の数値を出力(負,0,正の順番で判定)
if minus_ans_num >= k: #Kが負の範囲
    ans = []
    for m in minus:
        for p in plus:
            ans.append(m * p)
    ans.sort()
    print(ans[k - 1])
elif minus_ans_num + zero_ans_num >= k: # Kが0の範囲
    print(0)
else: #Kが正の範囲
    ans = list_conbination(minus) + list_conbination(plus)
    ans.sort()
    print(ans[k - minus_ans_num - zero_ans_num - 1])

Submission status: Time Limit Exceeded

Solution code:
def count_pair(A, x, K):
    # A内のペアで積がxより小さいものの個数がK未満ならTrueを返す
    cnt = 0
    N = len(A)
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            m = N-1
            while m > n and A[m] > y:
                cnt += 1
                m -= 1
                if cnt >= K:
                    return False
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            m = n + 1
            while m < N and A[m] < y:
                cnt += 1
                m += 1
                if cnt >= K:
                    return False
        elif x > 0:
            cnt += N - (n + 1)
            if cnt >= K:
                return False
    return True


def main():
    # count_pair(x)<Kをみたすxの最大値を求める
    N, K = map(int, input().split())
    * A, = map(int, input().split())
    A.sort()
    inf = 10**18+1
    l, r = -inf, inf
    for _ in range(inf):
        if r - l <= 1:
            print(l)
            exit()
        c = (l + r) // 2
        if count_pair(A, c, K):
            l = c
        else:
            r = c


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


def sub_count(A, N, n, x):
    if A[n] < 0:
        y = x // A[n]
        # A内のペアで積がyより大きいものの個数
        return N - max(n + 1, bisect.bisect_right(A, y))
    elif A[n] > 0:
        y = -(-x // A[n])
        # A内のペアで積がyより小さいものの個数
        return max(n + 1, bisect.bisect_left(A, y)) - (n + 1)
    elif x > 0:
        return N - (n + 1)
    else:
        return 0


def count_pair(A, N, x):
    return sum([sub_count(A, N, n, x) for n in range(N)])


def main():
    # count_pair(x)<Kをみたすxの最大値を求める
    N, K = map(int, input().split())
    * A, = map(int, input().split())
    A.sort()
    inf = 10**18+1
    l, r = -inf, inf
    for _ in range(inf):
        if r - l <= 1:
            print(l)
            exit()
        c = (l + r) // 2
        if count_pair(A, N, c) < K:
            l = c
        else:
            r = c


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n, k = map(int, input().split())
li = list(map(int, input().split()))
li2 = list(combinations(li, 2))
res = []
for i in li2:
    res.append(i[0]*i[1])
res.sort()
print(res[k-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#import sys; sys.stdin=open('input_file.txt')
#------------------------------------------
import numpy as np

N,K = map(int,input().split())
A = np.array(list(map(int,input().split())),dtype=np.int64)

A = np.sort(A)

hi = 10**18+1
lo = -10**18-1

while hi-lo > 1:
    mid = (hi+lo)//2
    under_mid = 0

    for i in range(N):
        if A[i] == 0:
            if mid > 0:
                under_mid += N
        elif A[i] > 0:
            under_mid += np.searchsorted(A,-(-mid//A[i]),side='left')
            #under_mid += bisect_left(A,-(-mid//A[i]))
        else:
            under_mid += N-np.searchsorted(A,mid//A[i],side='right')
            #under_mid += N-bisect_right(A,mid//A[i])
        if A[i]*A[i] < mid:
            under_mid -= 1
    under_mid //= 2

    if under_mid < K:
        lo = mid
    else:
        hi = mid

print(lo)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

S = input()
SS = input()

L = int(list(S.split())[1]) - 1

A = list(SS.split()) 
A_INT = [int(n) for n in A]

O = [None] * len(list(itertools.combinations(A_INT, 2)))

# 6C2の羅列
O = []
for x in itertools.combinations(A_INT, 2):
    O.append(x[0] * x[1])

O.sort()

print(O[L])

Submission status: Time Limit Exceeded

Solution code:
import itertools

S = input()
SS = input()

L = int(list(S.split())[1]) - 1

A = list(SS.split()) 
A_INT = [int(n) for n in A]

xs = ['one', 'two', 'three', 'four', 'five', 'six']

# 6C2の羅列
O = []
for x in itertools.combinations(A_INT, 2):
    O.append(x[0] * x[1])

O.sort()

print(O[L])

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, bisect_right

readline = sys.stdin.readline
N, K = map(int, readline().split())
A = sorted(map(int, readline().split()))
neg = bisect_left(A, 0)
pos = bisect_right(A, 0)


def f(x):
    '''
    x以下のペアの個数を返す
    '''
    # ペアの片方を固定してもう片方の個数を数える
    cnt = 0
    for i in range(0, neg):
        cnt += N - bisect_right(A, (x + 1) // A[i])
    if x >= 0:
        cnt += (pos - neg) * N
    for i in range(pos, N):
        cnt += bisect_right(A, x // A[i])
    for i in range(N):
        if A[i] ** 2 <= x:
            cnt -= 1

    return cnt // 2


def main():
    INF = 10 ** 18 + 1
    left, right = -INF, INF
    while right - left > 1:
        mid = (left + right) // 2
        if f(mid) < K:
            left = mid
        else:
            right = mid

    print(right)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

neg = bisect_left(A, 0)
pos = bisect_right(A, 0)

def less(x):
    res = 0
    b = 0
    for i in range(0, neg):
        while b != N and A[i] * A[b] >= x:
            b += 1
        while b != 0 and A[i] * A[b - 1] < x:
            b -= 1
        res += max(i - b, 0)
    for i in range(neg, pos):
        if x > 0:
            res += i
    for i in range(pos, N):
        while b != N and A[i] * A[b] < x:
            b += 1
        while b != 0 and A[i] * A[b - 1] >= x:
            b -= 1
        res += min(b, i)
    return res

l = - (10 ** 18 + 1)
r = - l
while l + 1 < r:
    m = (l + r) // 2
    if less(m) < K:
        l = m
    else:
        r = m
print(l)

Submission status: Time Limit Exceeded

Solution code:
def merge(array):
    mid = len(array)
    if mid > 1:
        left = merge(array[:(mid//2)])
        right = merge(array[(mid//2):])
        array = []
        while len(left) != 0 and len(right) != 0:
            if left[0] < right[0]:
                array.append(left.pop(0))
            else:
                array.append(right.pop(0))
        if len(left) != 0:
            array.extend(left)
        elif len(right) != 0:
            array.extend(right)
    return array

N, K = [int(e) for e in input().split()]
A = [int(e) for e in input().split()]
ans = []

length = len(A)

ans = [A[i] * A[j] for i in range(length-1) for j in range(i+1,length)]

ans = merge(ans)

print(ans[K - 1])

Submission status: Time Limit Exceeded

Solution code:
def merge(array):
    mid = len(array)
    if mid > 1:
        left = merge(array[:(mid//2)])
        right = merge(array[(mid//2):])
        array = []
        while len(left) != 0 and len(right) != 0:
            if left[0] < right[0]:
                array.append(left.pop(0))
            else:
                array.append(right.pop(0))
        if len(left) != 0:
            array.extend(left)
        elif len(right) != 0:
            array.extend(right)
    return array

N, K = [int(e) for e in input().split()]
A = [int(e) for e in input().split()]
ans = []

for i in range(len(A) - 1):
    for j in range(i+1, len(A)):
        ans.append(A[i] * A[j])

ans = merge(ans)

print(ans[K - 1])

Submission status: Time Limit Exceeded

Solution code:
# Problem_name : Otoshidama
'''
story_is_true = False
bills = [0, 0, 0]

N = int(input())
Y = int(input())

if story_is_true:
    print('10000円札{0}枚，5000円札{1}枚，1000円札{2}枚'.format(bills[0],bills[1],bills[2]))
'''

# Problem_name : C-Poll
# This program need too much time. So you have to make it smarter!
'''
N = int(input())
S = []
for i in range(N):
    S.append(input())
check_whether_in_S = list(set(S))

count = []
for i in range(len(check_whether_in_S)):
    count.append(0)
for s in S:
    for i in range(len(check_whether_in_S)):
        if s == check_whether_in_S[i]:
            count[i] += 1
            break

# get max
max = -1
for c in count:
    if max < c:
        max = c

name_list = []
for i in range(len(check_whether_in_S)):
    if count[i] == max:
        name_list.append(check_whether_in_S[i])

print()
name_list = sorted(name_list)
for n in name_list:
    print(n)
'''

# Problem Name : D-Pairs
N, K = [int(e) for e in input().split()]
A = [int(e) for e in input().split()]
ans = []

for i in range(len(A) - 1):
    for j in range(i+1, len(A)):
        ans.append(A[i] * A[j])

ans = sorted(ans)

print(ans[K - 1])

Submission status: Time Limit Exceeded

Solution code:
S = input()
SS = input()

L = list(S.split())
A = list(SS.split()) 
N = L[0]
K = int(L[1])
M = len(A) - 1

P = []
O = []
A_INT = [int(n) for n in A]

for i in range(M):
    AA = A_INT[i + 1:]
    
    R = len(AA) - K - 1
    P = [int(n) * A_INT[i] for n in AA]
    O.append(P)

D = sum(O, [])
D.sort()
print(D[K - 1])

Submission status: Time Limit Exceeded

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

INF = 10**19
N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)
pos.sort()
neg.sort()
p, n = len(pos), len(neg)
if K <= p * n:
    lb, ub = -INF, INF
    while ub - lb > 1:
        mid = (lb + ub) // 2
        cnt = 0

        s, t = 0, 0
        while s < p:
            while t < n and pos[s] * neg[t] <= mid:
                t += 1
            cnt += t
            s += 1

        if cnt < K:
            lb = mid
        else:
            ub = mid
    print(ub)
else:
    K -= p * n
    neg = neg[::-1]
    lb, ub = -INF, INF
    while ub - lb > 1:
        mid = (lb + ub) // 2
        cnt = 0

        s, t = p-1, 0
        while s >= 0:
            while t < s and pos[s] * pos[t] <= mid:
                t += 1
            cnt += min(s, t)
            s -= 1

        s, t = n-1, 0
        while s >= 0:
            while t < s and neg[s] * neg[t] <= mid:
                t += 1
            cnt += min(s, t)
            s -= 1

        if cnt < K:
            lb = mid
        else:
            ub = mid
    print(ub)

Submission status: Time Limit Exceeded

Solution code:
def bisect_left(A, x):
    l, r = -1, len(A)
    while r - l > 1:
        m = (l + r) // 2
        if A[m] >= x:
            r = m
        else:
            l = m
    return r


def bisect_right(A, x):
    l, r = -1, len(A)
    while r - l > 1:
        m = (l + r) // 2
        if A[m] > x:
            r = m
        else:
            l = m
    return r


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += N-max(n+1, bisect_right(A, y))
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += max(n+1, bisect_left(A, y)) - (n + 1)
        else:  # A[n]==0
            if x > 0:
                cnt += N - n - 1
    return cnt


# A = [0, 0, 0, 1, 1, 2, 2, 2]
# print(bisect_left(A, 0))
# print(bisect_left(A, 1))
# print(bisect_left(A, 2))
# print(bisect_right(A, 0))
# print(bisect_right(A, 1))
# print(bisect_right(A, 2))
# exit()

# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  from bisect import bisect
  n,k,*a=map(int,open(0).read().split())
  a.sort()
  i=bisect(a,0)
  a,b=a[i:],a[i-1::-1]
  n,m=len(a),len(b)
  ok=10**18
  ng=-ok
  while ok-ng>1:
    x=(ok+ng)//2
    s=0
    if x>=0:
      i=n
      for y in a:
        while i and a[i-1]*y>x:i-=1   
        s+=i
        if y*y<=x:s-=1
      i=m
      for y in b:
        while i and b[i-1]*y>x:i-=1
        s+=i
        if y*y<=x:s-=1
      s=s//2+n*m
    else:
      i=m
      for y in a:
        while i and b[i-1]*y<=x:i-=1
        s+=m-i
    if s>=k:ok=x
    else:ng=x
  print(ok)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from bisect import bisect
  n,k,*a=map(int,open(0).read().split())
  a.sort()
  i=bisect(a,0)
  a,b,c=a[i:],a[:i],a[i-1::-1]
  n,m=len(a),len(b)
  ok=10**18
  ng=-ok
  while ok-ng>1:
    x=(ok+ng)//2
    s=t=0
    i=n
    j=-1
    for y in a:
      while i and a[i-1]*y>x:i-=1
      while j+1<m and b[j+1]*y<=x:j+=1
      s+=j+1
      t+=i
      if y*y<=x:t-=1
    s+=t//2
    t=0
    i=m
    for y in c:
      while i and c[i-1]*y>x:i-=1
      t+=i
      if y*y<=x:t-=1
    s+=t//2
    if s>=k:ok=x
    else:ng=x
  print(ok)
main()

Submission status: Time Limit Exceeded

Solution code:
def bound2(a,y,x):
  ok=-1
  ng=len(a)
  while ng-ok>1:
    mid=(ok+ng)//2
    if a[mid]*y<=x:ok=mid
    else:ng=mid
  return ok
def bound1(x):
  s=t=0
  for y in a:
    s+=bound2(b,y,x)+1
    t+=bound2(a,y,x)
    if y*y>x:t+=1
  s+=t//2
  t=0
  for y in c:
    t+=bound2(c,y,x)
    if y*y>x:t+=1
  return s+t//2
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bound2(t,1,0)+1
a,b,c=t[i:],t[:i],t[i-1::-1]
ok=10**18+1
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if bound1(mid)>=k:ok=mid
  else:ng=mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
def bound2(a,y,x):
  ok=-1
  ng=len(a)
  while ng-ok>1:
    mid=(ok+ng)//2
    if a[mid]*y<=x:ok=mid
    else:ng=mid
  return ok
def bound1(x):
  s=t=0
  for y in a:
    s+=bound2(b,y,x)+1
    t+=bound2(a,y,x)
    if y*y>x:t+=1
  s+=t//2
  t=0
  for y in c:
    t+=bound2(c,y,x)
    if y*y>x:t+=1
  return s+t//2
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bound2(t,1,0)+1
a,b,c=t[i:],t[:i],t[i-1::-1]
ok=10**19
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if bound1(mid)>=k:ok=mid
  else:ng=mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
c=0
ans=[]
for i in range(n):
    for j in range(i+1,n):
        if i!=j:
            ans.append(l[i]*l[j])
ans.sort()
print(ans[k-1])

Submission status: Time Limit Exceeded

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

r = max(a[0] ** 2, a[-1] ** 2) + 1
l = min(a[0] * a[-1], a[0] ** 2, a[-1] ** 2) - 1
def judge():
    tot = 0
    for i in range(n):
        if a[i] < 0:
            l = -1
            r = n
            while l + 1 < r:
                c = (l + r) // 2
                if a[c] * a[i] < x:
                    r = c
                else:
                    l = c
            tot += n - r
        else:
            l = -1
            r = n
            while l + 1 < 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

while l + 1 < r:
    x = (l + r) // 2
    if judge():
        l = x
    else:
        r = x
print(l)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]

A.sort()

# 積がx未満となる組み合わせの数を求める
def n_comb_lt(x):
    n_comb = 0
    for i in range(n - 1): # A[0], A[1], ..., A[n-2]について
        # i < jであるjのうち、A[i] * A[j] < xとなるjの数を求める
        if A[i] > 0:
            if A[i] * A[i + 1] >= x:
                n_partner = 0
            elif A[i] * A[n - 1] < x:
                n_partner = n - 1 - i
            else:
                ok = i + 1
                ng = n - 1

                # ok >= 1, ng <= 200000 - 1
                # log2(200000) < 18
                # for _ in range(18):
                while ng - ok > 1:
                    mid = (ng + ok) // 2
                    if A[i] * A[mid] < x:
                        ok = mid
                    else:
                        ng = mid
                n_partner = ok - i
        else:
            if A[i] * A[i + 1] < x:
                n_partner = n - 1 - i
            elif A[i] * A[n - 1] >= x:
                n_partner = 0
            else:
                ng = i + 1
                ok = n - 1
                # ok >= 1, ng <= 200000 - 1
                # log2(200000) < 18
                # for _ in range(18):
                while ok - ng > 1:
                    mid = (ng + ok) // 2
                    if A[i] * A[mid] < x:
                        ok = mid
                    else:
                        ng = mid
                n_partner = n - 1 - ng
        n_comb += n_partner

    return n_comb


ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

# for _ in range(62):
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid) < k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]

A.sort()

# 積がx未満となる組み合わせの数を求める
def n_comb_lt(x):
    n_comb = 0
    for i in range(n - 1): # A[0], A[1], ..., A[n-2]について
        # i < jであるjのうち、A[i] * A[j] < xとなるjの数を求める
        if A[i] > 0:
            if A[i] * A[i + 1] >= x:
                n_partner = 0
            elif A[i] * A[n - 1] < x:
                n_partner = n - 1 - i
            else:
                ok = i + 1
                ng = n - 1

                # ok >= 1, ng <= 200000 - 1
                # log2(200000) < 18
                for _ in range(18):
                # while ng - ok > 1:
                    mid = (ng + ok) // 2
                    if A[i] * A[mid] < x:
                        ok = mid
                    else:
                        ng = mid
                n_partner = ok - i
        else:
            if A[i] * A[i + 1] < x:
                n_partner = n - 1 - i
            elif A[i] * A[n - 1] >= x:
                n_partner = 0
            else:
                ng = i + 1
                ok = n - 1
                # ok >= 1, ng <= 200000 - 1
                # log2(200000) < 18
                for _ in range(18):
                # while ok - ng > 1:
                    mid = (ng + ok) // 2
                    if A[i] * A[mid] < x:
                        ok = mid
                    else:
                        ng = mid
                n_partner = n - 1 - ng
        n_comb += n_partner

    return n_comb


ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

for _ in range(62):
# while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid) < k:
        ok = mid
    else:
        ng = mid

print(ok)