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())
numbers = list(map(int, input().split()))
minus = [v for v in numbers if v < 0]
zero = [v for v in numbers if v == 0]
plus = [v for v in numbers if v > 0]

minus_count = len(minus) * len(plus)
zero_count = (len(zero) * (len(zero) - 1) / 2) + (len(zero) * len(minus)) + (len(zero) * len(plus))
plus_count = (len(minus) * (len(minus) - 1) / 2) + (len(plus) * (len(plus) - 1) / 2)

if minus_count < k <= minus_count + zero_count:
    print(0)
elif k <= minus_count:
    m_list = []
    for i in minus:
        for j in plus:
            m_list.append(i*j)
    m_list.sort()
    print(m_list[k-1])
else:
    p_list = []
    index = int(k - minus_count - zero_count)
    for i in range(0, len(minus)):
        for j in range(i + 1, len(minus)):
            p_list.append(minus[i] * minus[j])
    
    for i in range(0, len(plus)):
        for j in range(i + 1, len(plus)):
            p_list.append(plus[i] * plus[j])
    p_list.sort()
    print(p_list[index-1])

Submission status: Time Limit Exceeded

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

import itertools
times = []
for i in itertools.combinations(A, 2):
    times.append(i[0]* i[1])

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, K = map(int, input().split(' '))
lst = input().split(' ')
lst = [int(v) for v in lst]
c = itertools.combinations(lst, 2)
mul = sorted([v[0] * v[1] for v in c])
print(mul[K-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

positive = []
negative = []
zero = 0

for combi in itertools.combinations(A, 2):
    c = combi[0]
    n = combi[1]
    if c*n > 0:
        positive.append(c*n)
    elif c*n < 0 :
        negative.append(c*n)
    else:
        zero += 1

if K <= len(negative):
    negative.sort()
    print(negative[K-1])
elif K <= len(negative)+zero:
    print(0)
else:
    positive.sort()
    k = K - len(negative) - zero
    print(positive[k-1])

Submission status: Time Limit Exceeded

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

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

    def check(x):
        count = 0
        if x > 0:
            for i in range(N):
                if a[i] < 0:
                    num = -(-x//a[i])
                    count += N-max(i+1,bisect.bisect_left(a,num))
                elif a[i] > 0:
                    num = x//a[i]
                    count += max(0,bisect.bisect_right(a,num)-i-1)
                else:
                    count += N-(i+1)
        elif x == 0:
            for i in range(N):
                if a[i] < 0:
                    num = 0
                    count += N-max(i+1,bisect.bisect_left(a,num))
                elif a[i] > 0:
                    continue
                else:
                    count += N-(i+1)
        else:
            for i in range(N):
                if a[i] < 0:
                    num = -(-x//a[i])
                    count += N-bisect.bisect_left(a,num)
                else:
                    continue
        return count
    
    left,right = -10**18-1,10**18+1
    while right-left > 1:
        mid = (left+right)//2
        if check(mid) >= K:
            right = mid
        else:
            left = mid
            
    print(right)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def pairing(n, k, a):
    next = n - 1
    pairs = []

    while next != 0:
        for i in range(0, n - next):
            pairs.append(a[i] * a[i + next])
        next -= 1
    pairs = sorted(pairs)
    print(pairs[k - 1])

pairing(n[0], n[1], a)

Submission status: Time Limit Exceeded

Solution code:
n = list(map(int, input().rstrip().split(" ")))
ar = list(map(int, input().rstrip().split(" ")))

def pairing(n, k, a):
    next = n - 1
    pairs = []

    while next != 0:
        for i in range(0, n - next):
            pairs.append(a[i] * a[i + next])
        next -= 1
    pairs = sorted(pairs)
    print(pairs[k - 1])

pairing(n[0], n[1], ar)

Submission status: Time Limit Exceeded

Solution code:
n = list(map(int, input().rstrip().split(" ")))
ar = list(map(int, input().rstrip().split(" ")))

def pairing(n, k, a):
    next = 1
    pairs = []

    while next != n:
        for i in range(0, n - next):
            pairs.append(a[i] * a[i + next])
        next += 1
    pairs = sorted(pairs)
    print(pairs[k - 1])

pairing(n[0], n[1], ar)

Submission status: Time Limit Exceeded

Solution code:
w = list(map(int , input().split()))
n = w[0]
m = w[1]
p  =[]
l = list(map(int , input().split()))
from itertools import combinations 
import numpy as np
r =  list(combinations(l, 2)) 
for i in r:
  p.append(np.product(np.array(i)))
print(sorted(p)[m-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
m,n=map(int,input().split())
a=list(map(int,input().split()))
op=[]
lp=[]
comb = list(combinations(a,2))

for i in comb:
    j=list(i)
    op.append(j)

for i in range(len(op)):
    k=op[i][0]*op[i][1]
    lp.append(k)
lp.sort()

print(lp[n-1])

Submission status: Time Limit Exceeded

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


b=list()
for i in range(len(a)):
    c=a[i]
    for j in range(i):
        b.append(a[j]*c)
b.sort()

print(b[k-1])

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import bisect
stdin = sys.stdin

def bisectf_left(f,val,start,end):
    fs = f(start)
    if val <= fs:
        return start
    fe = f(end-1)
    if fe < val:
        return end    
    # Now fs < val and val <= fe

    while True:
        if (end - start) <= 2:
            return end - 1
        mid = (start + end )// 2 
        fm = f(mid)
        if val <= fm :
            end = mid + 1
        else: 
            start = mid
        continue

def bisectf_right(f,val,start,end):
    fs = f(start)
    if val < fs:
        return start
    fe = f(end-1)
    if fe <= val:
        return end
    # Now fs <= val and val < fe 
    while True:
        # print(start,end)
        if (end - start) <= 2:
            return end - 1
        mid = (start + end )// 2 
        fm = f(mid)
        if fm > val:
            end = mid + 1
        else:
            start = mid
        continue

def bisectf_bool(f,start,end):
    fs = f(start)
    if fs == True:
        return start
    fe = f(end-1)
    if fe == False:
        return end
    # Now fs == False and  fe == True 
    while True:
        # print(start,end)
        if (end - start) <= 2:
            return end - 1
        mid = (start + end )// 2 
        fm = f(mid)
        if fm == True:
            end = mid + 1
        else:    
            start = mid
        continue



ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
mod = 10**9 + 7 
sys.setrecursionlimit(1000010)

N,K = nm()
A  = nl()
A.sort()
# print(N,K,A)

zeroleft=bisect.bisect_left(A,0)
zeroright=bisect.bisect_right(A,0)
( nminus,nzero,nplus ) = (zeroleft,zeroright-zeroleft,len(A)-zeroright)
# print(nminus,nzero,nplus)

cminus = nminus * nplus
czero = nzero * (nminus + nplus ) + nzero * (nzero-1) // 2 
cplus = (nplus * (nplus - 1) + nminus * (nminus -1 ))//2

if K <= cminus:
    group = "minus"
    k = K
elif K <= czero + cminus:
    print(0)
    exit(0)
else:
    group = "plus"
    k = K - (czero + cminus)

def is_number_of_multiple_LE_Z_is_ME_K(z,k):
    if z == -1:
        return (True if cminus >= k else False)
    elif z == 0 :
        return (True if cminus + czero >= k else False)
    if z > 0:
        count = cminus + czero
        if count >=k:
            return True
        for i in range(zeroright+1,N):
            x = A[i]
            limit = z // x
            j = max(min(bisect.bisect_right(A,limit,zeroright),i),zeroright)
            count += (j - zeroright)
            # print("A",i,k,"limit=",limit,j,zeroright,j-zeroright)
            if count >=k: 
                return True
        for i in range(1,zeroleft):
            x = A[i]
            limit = - (-z // x )
            j = min(bisect.bisect_left(A,limit,0,i),i)
            count += (i-j)
            if count >= k:
                return True
        # return False
    else: # z is negavite and smaller than -1
        count = 0
        for i in range(zeroright,N):
            x = A[i]
            limit = z // x
            j = min(bisect.bisect_right(A,limit,0,zeroleft),zeroleft)
            count += j
            if count >=k: 
                return True
    return False

#for i in range(0,17):
#    for j in range(-7,5):
#        print(i,j,is_number_of_multiple_LE_K_is_ME_Z(j,i))  
        
if nminus == 0: 
    nmax = A[N-2]* A[N-1]
    nmin = A[0] * A[1]
elif nplus == 0:
    nmin = A[N-2]* A[N-1]
    nmax = A[0] * A[1]
else:
    nmax = max(A[N-2]* A[N-1],A[0] * A[1])
    nmin = A[0]* A[N-1]
        
def F(x):
    global K
    # print("K=",K)
    return is_number_of_multiple_LE_Z_is_ME_K(x,K)

# for i in range(-7,5):
#    print(i,F(i))

print(bisectf_bool(F,nmin,nmax + 1))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
S=[]
import itertools
for a1,a2 in itertools.combinations(A,2):
    S.append(a1*a2)
s=sorted(S)
print(s[K-1])

Submission status: Time Limit Exceeded

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

negative = []
zero = []
positive = []
for i in map(int, input().split()):
    if i < 0:
        negative.append(i)
    elif i > 0:
        positive.append(i)
    else:
        zero.append(i)

count_negative = len(negative) * len(positive)
count_zero = len(negative)*len(zero) + len(zero)*len(positive) + (len(zero)*(len(zero)-1))//2
count_positive = (len(positive)*(len(positive)-1))//2 + (len(negative)*(len(negative)-1))//2

values = []
if K <= count_negative:
    for i in negative:
        for j in positive:
            values.append(i * j)
    values.sort()
    print(values[K-1])
elif count_negative < K <= count_negative + count_zero:
    print(0)
else:
    for i in range(len(negative)):
        for j in range(i+1, len(negative)):
            values.append(negative[i] * negative[j])
    for i in range(len(positive)):
        for j in range(i+1, len(positive)):
            values.append(positive[i] * positive[j])
    values.sort()
    print(values[K-1-count_negative-count_zero])

Submission status: Time Limit Exceeded

Solution code:
n,k=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
a.sort()
lm=[]
lp=[]
lz=[]
for i in a:
    if i<0:
        lm.append(i)
    elif i==0:
        lz.append(i)
    else:
        lp.append(i)
np=len(lp)
nm=len(lm)
nz=len(lz)
import bisect
import math
def f(x):
    c=0
    if x>=0:
        c+=nz*n
    for i in lp:
        c+=bisect.bisect_right(a,x//i)
    for i in lm:
        c+=n-bisect.bisect_right(a,(-x-1)//(-i))
    for i in a:
        if i**2<=x:
            c-=1
    return c//2

left=-10**20
right=10**20
while right-left>1:
    mid=(left+right)//2
    if f(mid)>=k:
        right=mid
    else:
        left=mid
print(right)

Submission status: Time Limit Exceeded

Solution code:
def pair(n):
  return int(n * (n-1) / 2)

m,z,p = [],[],[]
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))

for i in a:
  if i > 0:
    p.append(i)
  elif i == 0:
    z.append(i)
  elif i < 0:
    m.append(i)

a = len(m)*len(p) #マイナス
b = len(m)*len(z)+len(z)*len(p)+pair(len(z)) #ゼロ
c = pair(len(m))+pair(len(p)) #プラス

if k <= a:
  #print('マイナス')
  tmp = []
  for i in m:
    for j in p:
      tmp.append(i*j)
  tmp.sort()
  print(tmp[k-1])
elif a < k and k <= a+b:
  #print('ゼロ')
  print(0)
else:
  #print('プラス')
  tmp = []
  for i in range(len(m)):
    for j in range(len(m)):
      if i < j:
        tmp.append(m[i] * m[j])
  for i in range(len(p)):
    for j in range(len(p)):
      if i < j:
        tmp.append(p[i] * p[j])
  tmp.sort()
  print(tmp[k-a-b-1])

Submission status: Time Limit Exceeded

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

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

a_minus = a_zero = a_plus = 0
for i in range(n):
    if a[i] > 0:
        a_plus += 1
    elif a[i] == 0:
        a_zero += 1
    else:
        a_minus += 1

aa_minus = a_minus * a_plus
aa_zero = a_zero * (n - a_zero) + a_zero * (a_zero - 1) // 2


def check_minus(x):
    # k番目の数がx(<0)以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    j = a_minus + a_zero
    for i in range(a_minus):
        # a[i] < 0
        while j < n and a[i] * a[j] > x:
            j += 1
        cnt += n - j

    return cnt >= k


def check_plus(x):
    # k番目の数がx(>0)以下であるか
    # x以下の数字がk個以上あるか

    def func(b, m):
        # 昇順ソート済みの数列b (長さm)
        # 掛け算してx以下となる数を求める
        c = 0
        j = m - 1
        for i in range(m):
            while j > 0 and b[i] * b[j] > x:
                j -= 1
            c += max(j - i, 0)
        return c

    cnt = aa_minus + aa_zero
    cnt += func(a[-a_plus:], a_plus)
    cnt += func(list(reversed(a[:a_minus])), a_minus)
    return cnt >= k


if k <= aa_minus:
    # k番目の数は負の数
    lb = a[0] * a[-1] - 1  # False
    ub = 0  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_minus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub
elif k <= aa_minus + aa_zero:
    # k番目の数は0
    ans = 0
else:
    # k番目の数はプラス
    lb = 0  # False
    ub = max(a[0]**2, a[-1]**2) + 1  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_plus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, K = [int(_) for _ in raw_input().split()]
    A = [int(_) for _ in raw_input().split()]
    A.sort()
    l = -10**18 - 1; r = 10**18 + 1
    while (l < r - 1):
        mid = (l + r) / 2
        total = 0
        for i in range(N):
            if A[i] < 0:
                _left = -1; _right = N
                while (_left < _right - 1):
                    _mid = (_left + _right)/2
                    if A[_mid] * A[i] < mid:
                        _right = _mid
                    else:
                        _left = _mid
                total += N - _right
            else:
                _left = -1; _right = N
                while (_left < _right - 1):
                    _mid = (_left + _right)/2
                    if A[_mid] * A[i] < mid:
                        _left = _mid
                    else:
                        _right = _mid
                total += _right
            if A[i] * A[i] < mid:
                total -= 1
        total /= 2
        if total < K:
            l = mid
        else:
            r = mid
    print l

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k=map(int,input().split())
a=np.array([int(i) for i in input().split()])
a=[a[i]*a[-j-1] for i in range(n) for j in range(n-i-1)]
def linked_merge_sort(lst):
    if len(lst) == 1:
        return
    q, r = divmod(len(lst), 2)
    left = [lst.pop() for _ in range(q)]
    right = [lst.pop() for _ in range(q + r)]
   
    linked_merge_sort(left)
    linked_merge_sort(right)
    
    left.reverse()  # 補足
    right.reverse()
    while left and right:
        if left[-1] <= right[-1]:
            lst.append(left.pop())
        else:
            lst.append(right.pop())
    while left:
        lst.append(left.pop())
    while right:
        lst.append(right.pop())
linked_merge_sort(a)
print(a[k-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k=map(int,input().split())
a=np.array([int(i) for i in input().split()])
tmp=int((n*(n-1))/2)
b=np.array([0 for i in range(tmp)])
b=[a[i]*a[-j-1] for i in range(n) for j in range(n-i-1)]
print(sorted(b)[k-1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect, bisect_left, bisect_right

DEBUG = False


def bisect_f(f, lo, hi):
    if DEBUG:
        assert f(lo) and not f(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if f(mid):
            lo = mid
        else:
            hi = mid
        if DEBUG:
            assert f(lo) and not f(hi)
    if DEBUG:
        assert hi - lo == 1
        assert f(lo) and not f(hi)
    return lo


N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
neg = []
zero = []
pos = []
for x in A:
    if x < 0:
        neg.append(x)
    elif x == 0:
        zero.append(x)
    else:
        assert x > 0
        pos.append(x)
revAbsNeg = [-x for x in reversed(neg)]  # Reverse neg and keep magnitude only

posSq = [x ** 2 for x in pos]
negSq = [x ** 2 for x in revAbsNeg]


def countDistinctPairsLessThan(arr, prod):
    count = 0
    for i, x in enumerate(arr):
        count += bisect(arr, (prod - 1) // x, 0, i)

    if DEBUG:
        count2 = 0
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                if arr[i] * arr[j] < prod:
                    count2 += 1
        assert count == count2
    return count


def countPairsLessThanOrEqual(arr1, arr2, prod):
    # Given sorted two arrays containing *positive* numbers only,
    # find the number of pairs between the two arrays that are <= prod
    # O(N * log(M)) where N = len(arr1), M = len(arr2)
    if len(arr1) > len(arr2):
        arr1, arr2 = arr2, arr1
    # TODO: np.searchsorted can do vectorized binary search
    count = 0
    for x in arr1:
        count += bisect(arr2, prod // x)
    if DEBUG:
        count2 = 0
        for x in arr1:
            for y in arr2:
                if x * y <= prod:
                    count2 += 1
        assert count == count2
    return count


def getIndex(prod):
    # Count number of pairs strictly less than prod
    count = 0
    if prod < 0:
        # All negatives except for the negatives with abs value less than or equal -prod
        count += len(pos) * len(neg)
        count -= countPairsLessThanOrEqual(pos, revAbsNeg, -prod)
    elif prod >= 0:
        # All negatives
        count += len(pos) * len(neg)
        if prod > 0:
            # All zeroes
            count += len(zero) * len(neg)
            count += (len(zero) * (len(zero) - 1)) // 2
            count += len(zero) * len(pos)
            # Positives with positives
            count += countDistinctPairsLessThan(pos, prod)
            # Negatives with negatives
            count += countDistinctPairsLessThan(revAbsNeg, prod)

    if DEBUG:
        count2 = 0
        for i in range(N):
            for j in range(i + 1, N):
                if A[i] * A[j] < prod:
                    count2 += 1
        assert count == count2
    return count


def solve(K):
    lo = -10 ** 18
    hi = 10 ** 18 + 1
    if DEBUG:
        assert getIndex(lo) <= K < getIndex(hi)
    prod = bisect_f(lambda prod: getIndex(prod) <= K, lo, hi)
    if DEBUG:
        assert getIndex(prod) <= K < getIndex(prod + 1)
    return prod


if DEBUG:
    for k in range((N * (N - 1)) // 2):
        print("k", k, solve(k))

print(solve(K - 1))  # K is 1-indexed

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k=map(int,input().split())
a=np.array([int(i) for i in input().split()])
b=np.array([a[i]*a[-j-1] for i in range(n) for j in range(n-i-1)])
c=sorted(b)
print(c[k-1])

Submission status: Time Limit Exceeded

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

values = []
for i in range(len(aa)):
    for j in range(i + 1, len(aa)):
        values.append(aa[i] * aa[j])
values.sort()
print(values[k - 1])

Submission status: Time Limit Exceeded

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

for i in range(n - 1):
    for j in range(i + 1, n):
        r.append(a[i] * a[j])

r.sort()

print(str(r[k-1]))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys


def main():
    input = sys.stdin.readline

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

    def check(x):
        # k番目の数がx以下であるか
        # x以下の数字がk個以上あるか
        cnt = 0
        for i, ai in enumerate(a):
            if ai > 0:
                idx = bisect_right(a, x // ai)
                cnt += max(idx - i - 1, 0)
            elif ai < 0:
                idx = bisect_left(a, -(x // abs(ai)))
                # cnt += n - idx
                cnt += n - max(idx, i + 1)
            else:
                # ai == 0
                if x >= 0:
                    cnt += n - i - 1

            if cnt >= k:
                return True
        # print('check', x, cnt)
        return cnt >= k

    # lb = -10**18  # False
    # ub = +10**18  # True
    lb = min(a[0]**2, a[0] * a[-1], a[-1]**2) - 1  # False
    ub = max(a[0]**2, a[0] * a[-1], a[-1]**2) + 1  # True

    while ub - lb > 1:
        mid = (ub + lb) // 2
        # print(lb, ub)
        if check(mid):
            ub = mid
        else:
            lb = mid

    print(ub)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


def check(x):
    # k番目の数がx以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    for i, ai in enumerate(a):
        if ai > 0:
            idx = bisect_right(a, x // ai)
            cnt += max(idx - i - 1, 0)
        elif ai < 0:
            idx = bisect_left(a, -(x // abs(ai)))
            # cnt += n - idx
            cnt += n - max(idx, i + 1)
        else:
            # ai == 0
            if x >= 0:
                cnt += n - i - 1

        if cnt >= k:
            return True
    # print('check', x, cnt)
    return cnt >= k


# lb = -10**18  # False
# ub = +10**18  # True
lb = min(a[0]**2, a[0] * a[-1], a[-1]**2) - 1  # False
ub = max(a[0]**2, a[0] * a[-1], a[-1]**2) + 1  # True

while ub - lb > 1:
    mid = (ub + lb) // 2
    # print(lb, ub)
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from functools import reduce

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

p = list(itertools.combinations(a, 2))
x = []

for i in range(n * (n - 1) // 2):
    x.append(reduce(lambda x, y: x * y, list(p[i])))
x.sort()

print(x[k-1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()


def check(x):
    # k番目の数がx以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    for i, ai in enumerate(a):
        if ai > 0:
            idx = bisect_right(a, x // ai)
            cnt += max(idx - i - 1, 0)
        elif ai < 0:
            idx = bisect_left(a, -(x // abs(ai)))
            # cnt += n - idx
            cnt += n - max(idx, i + 1)
        else:
            # ai == 0
            if x >= 0:
                cnt += n - i - 1

        if cnt >= k:
            return True
    # print('check', x, cnt)
    return cnt >= k


# lb = -10**18  # False
# ub = +10**18  # True
lb = min(a[0]**2, a[0] * a[-1], a[-1]**2) - 1  # False
ub = max(a[0]**2, a[0] * a[-1], a[-1]**2) + 1  # True

while ub - lb > 1:
    mid = (ub + lb) // 2
    # print(lb, ub)
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()


def check(x):
    # k番目の数がx以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    for i, ai in enumerate(a):
        if ai > 0:
            idx = bisect_right(a, x // ai)
            cnt += max(idx - i - 1, 0)
        elif ai < 0:
            idx = bisect_left(a, -(x // abs(ai)))
            # cnt += n - idx
            cnt += n - max(idx, i + 1)
        else:
            # ai == 0
            if x >= 0:
                cnt += n - i - 1

        if cnt >= k:
            return True
    # print('check', x, cnt)
    return cnt >= k


lb = -10**18  # False
ub = +10**18  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    # print(lb, ub)
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()


def check(x):
    # k番目の数がx以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    for i in range(n):
        if a[i] > 0:
            idx = bisect_right(a, x // a[i])
            cnt += max(idx - i - 1, 0)
        elif a[i] < 0:
            idx = bisect_left(a, -(x // abs(a[i])))
            # cnt += n - idx
            cnt += n - max(idx, i + 1)
        else:
            # a[i] == 0
            if x >= 0:
                cnt += n - i - 1

        if cnt >= k:
            return True
    # print('check', x, cnt)
    return cnt >= k


lb = -10**18  # False
ub = +10**18  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    # print(lb, ub)
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()


def check(x):
    # k番目の数がx以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    for i in range(n):
        if a[i] > 0:
            idx = bisect_right(a, x // a[i])
            cnt += max(idx - i - 1, 0)
        elif a[i] < 0:
            idx = bisect_left(a, -(x // abs(a[i])))
            # cnt += n - idx
            cnt += n - max(idx, i + 1)
        else:
            # a[i] == 0
            if x >= 0:
                cnt += n - i - 1

        if cnt >= k:
            return True
    # print('check', x, cnt)
    return cnt >= k


lb = -10**19  # False
ub = +10**19  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    # print(lb, ub)
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Submission status: Time Limit Exceeded

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

def binary_search2(N, K, m, A):
    # m以下となる個数がK未満かどうかを判定する
    total = 0
    for i, a in enumerate(A):
        if a < 0:
            l, r = -1, N
            while l+1 < r:
                c = (l+r) // 2
                if A[c] * A[i] < m:
                    r = c
                else:
                    l = c
            total += N - r
        else:
            l, r = -1, N
            while l+1 < r:
                c = (l+r) // 2
                if A[c] * A[i] < m:
                    l = c
                else:
                    r = c
            total += r
        if A[i] * A[i] < m: total -= 1
    total /= 2
    return total < K

def binary_search1(N,K,A):
    # binary_search2に二分探索の論理をまとめたので、こっちは単純な二分探索
    l, r = -(10**18+1), 10**18+1
    while l+1 < r:
        m = (l+r) // 2
        if binary_search2(N,K,m,A): l = m
        else: r = m
    return l

print(binary_search1(N,K,A))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
for i in range(n): #負数の数(nc)、0の数(zc)、正数の数(pc)を数える
 if arr[i]<0:
   nc+=1
 elif arr[i]==0:
   zc+=1
 else:
   pc+=1
ncc=nc*pc #積が負となるペアの個数を求める
zcc=zc*(nc+pc)+(zc*(zc-1))//2 #積が0となるペアの個数を求める
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2 #積が正となるペアの個数を求める
if k<=ncc: #K番目の値が負の場合
 arr1=[]
 arr2=[]
 for i in range(n): #負数、正数をそれぞれ昇順に並べる
   if arr[i]<0:
     arr1.append(-arr[i])
   elif arr[i]>0:
     arr2.append(arr[i])
 arr1=arr1[::-1]
 c1=len(arr1)
 c2=len(arr2)
 l=0
 r=10**18+1
 k=ncc-k #負数のマイナスを取って計算しているため積の大小が逆転するので、大きなほうからK番目、すなわち、小さなほうから(積が負となるペアの個数-K)番目の値を求める
 while r-l!=1:
   mid=(l+r)//2
   cnt=0
   pos=c2-1
   for i in range(c1): #各負数ごとに積が勝手に決めた値midよりも小さくなる正数の個数を求め足し合わせる(しゃくとり法)
     while pos!=-1:
       if arr2[pos]>mid//arr1[i]:
         pos-=1
       else:
         break
     cnt+=pos+1
   if cnt>k: #勝手に決めた値mid以下の個数が(積が負となるペアの個数-K)個以上であれば真の値はmid以下
     r=mid
   else: #そうでなければ真の値はmid以上
     l=mid
 print(-r) #負数のマイナスを取って計算したので最後にマイナスを付けて出力する
elif k<=(ncc+zcc): #K番目の値が0の場合
 print(0)
else: #K番目の値が正の場合
 arr1=[]
 arr2=[]
 for i in range(n): #負数、正数をそれぞれ昇順に並べる
   if arr[i]<0:
     arr1.append(-arr[i])
   elif arr[i]>0:
     arr2.append(arr[i])
 arr1=arr1[::-1]
 c1=len(arr1)
 c2=len(arr2)
 l=0
 r=10**18+1
 k-=(ncc+zcc) #正数の中で小さい順にK番目の数を調べたいので負数、0の数を取り除く
 while r-l!=1:
   mid=(l+r)//2
   cnt1=0
   pos1=c1-1
   for i in range(c1): #各負数ごとに積が勝手に決めた値midよりも小さくなる負数の個数を求め足し合わせる(しゃくとり法)
     tmp=0
     while pos1!=-1:
       if arr1[pos1]>mid//arr1[i]:
         pos1-=1
       else:
         break
     tmp+=pos1+1
     if arr1[i]**2<mid: #各要素について、自身を2回選んだ場合の積が勝手に決めた値mid以下なら条件を満たすペアの個数を1減らす
       tmp-=1
     cnt1+=tmp
   cnt1=cnt1//2 #上記の処理では同じペアが2回数えられているので個数を半分にする
   cnt2=0
   pos2=c2-1
   for i in range(c2): #各正数ごとに積が勝手に決めた値midよりも小さくなる正数の個数を求め足し合わせる(しゃくとり法)
     tmp=0
     while pos2!=-1:
       if arr2[pos2]>mid//arr2[i]:
         pos2-=1
       else:
         break
     tmp+=pos2+1
     if arr2[i]**2<mid:
       tmp-=1 #各要素について、自身を2回選んだ場合の積が勝手に決めた値mid以下なら条件を満たすペアの個数を1減らす
     cnt2+=tmp
   cnt2=cnt2//2 #上記の処理では同じペアが2回数えられているので個数を半分にする
   cnt=cnt1+cnt2
   if cnt>=k: #勝手に決めた値mid以下の個数がK個以上であれば真の値はmid以下
     r=mid
   else: #そうでなければ真の値はmid以上
     l=mid
 print(r)