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:
def main():
    import sys
    from math import ceil
    from bisect import bisect_left, bisect_right
    N, K = map(int, sys.stdin.readline().split())
    A = sorted(list(map(int, sys.stdin.readline().split())))

    positives = [a for a in A if a > 0]
    negatives = [a for a in A if a < 0]
    positive_cnt = len(positives)
    negative_cnt = len(negatives)
    zero_cnt = N - (positive_cnt + negative_cnt)

    negative_pairs_cnt = positive_cnt * negative_cnt
    zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

    # 考えにくいので、負の値も正になおしてソートしておく
    negatives = sorted([-a for a in negatives])

    if K <= negative_pairs_cnt:
        # にぶたん: X以上になるペアがK個以上あるか？
        ok, ng = 0, 10 ** 18 + 1
        while abs(ok - ng) > 1:
            X = float((ok + ng) // 2)
            or_higher_cnt = 0
            for a in negatives:
                or_higher_cnt += (positive_cnt - bisect_left(positives, ceil(X / a)))
                if or_higher_cnt >= K:
                    ok = X
                    break
            else:
                ng = X

        print(int(-ok))

    elif K <= negative_pairs_cnt + zero_pairs_cnt:
        print(0)

    else:
        # にぶたん: X以下になるペアがK個以上あるか？
        K -= (negative_pairs_cnt + zero_pairs_cnt)
        ok, ng = 10 ** 18, 0
        while abs(ok - ng) > 1:
            X = (ok + ng) // 2
            or_higher_cnt = 0

            for i, a in enumerate(positives):
                j = bisect_right(positives, X // a)
                if i > j:
                    or_higher_cnt += j
                else:
                    or_higher_cnt += i

            if or_higher_cnt >= K:
                ok = X
                continue

            for i, a in enumerate(negatives):
                j = bisect_right(negatives, X // a)
                if i > j:
                    or_higher_cnt += j
                else:
                    or_higher_cnt += i

            if or_higher_cnt >= K:
                ok = X
                continue

            ng = X

        print(ok)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

list = []
for _ in range(n):
  num = A.pop()
  for a in A:
    list.append(num * a)
    
list.sort()
print(list[k-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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

    result = []
    for i in range(N):
        for j in range(i + 1, N):
            result.append(A[i] * A[j])
    result.sort()
    print(result[K - 1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
"""
k 番目に来る数を求める ≡ 「x 未満の数が k 個未満」である x の最大値
小さい順にソートした上で自分自身を固定して
    x >= 0: 左端から x 個
    x < 0: 右端から x 個
で境界線を見つける
自分自身 (対角線) を引いて 2 で割る

"""

def innerBisection(a, k):
    """
    :param a: a list a in question
    :param k: kth in question
    :return: boolean (x 未満の数が k 個未満であるかどうか)
    """
    total = 0 # x 未満のペアが何個あるか
    for i in range(n):
        l, r = -1, n
        # a[i] が負のとき (右端から取る)
        if(a[i] < 0):
            while l+1 < r:
                c = (l + r) // 2
                if a[i] * a[c] < x:
                    r = c
                else:
                    l = c
            total += n-r
        # a[i] が正のとき (左端から取る)
        else: # a[i] => 0
            l, r = -1, n
            while l+1 < r:
                c = (l + r) // 2
                if a[i] * a[c] < x:
                    l = c
                else:
                    r = c
            total += r
        if a[i] * a[i] < x:
            total -= 1
    total /= 2
    return total < k


n,k = map(int, input().split())
a = list(map(int, input().split()))
# n, k = 4, 3
# a = [3, 3, -4, -2,]

a.sort()
INF = int(1e+18) + 1
"""
x を探す bisection search (outerBisection)
"""
l, r = -INF, INF
while l+1 < r:
    x = (l + r) // 2
    flag = innerBisection(a, k)
    if flag:
        l = x
    else:
        r = x
print(l)

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    N, K = map(int, f_i.readline().split())
    
    import numpy as np
    A = np.array(f_i.readline().split(), dtype=int)
    A.sort()
    
    INF = 10 ** 18 + 1
    l = -INF
    r = INF
    
    zero_num = len(A[A==0])
    tot_init = zero_num * (N - 1)
    
    mA = A[A<0]
    pA = A[A>0]
    
    while l + 1 < r:
        x = (l + r) // 2
        if x > 0:
            tot = tot_init
        else:
            tot = 0
        
        for a in mA:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * a < x:
                    right = mid
                else:
                    left = mid
            tot += (N - right)
            if a ** 2 < x:
                tot -= 1
        
        for a in pA:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * a < x:
                    left = mid
                else:
                    right = mid
            tot += right
            if a ** 2 < x:
                tot -= 1
        
        tot //= 2
        if tot < K:
            l = x
        else:
            r = x
    
    print(l)

solve()

Submission status: Time Limit Exceeded

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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)

val_set = []
if num_minus_pair >= K:
  for i in range(num_minus):
    for j in range(num_plus):
      val = A[i]*A[num_minus+num_zero+j]
      val_set.append(val)
  val_set = sorted(val_set)
  print(val_set[K-1])
elif num_minus_pair+num_zero_pair >= K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair >= K:
  K = K - (num_minus_pair+num_zero_pair)
  for i in range(num_minus-1):
    for j in range(i+1, num_minus):
      val = A[i]*A[j]
      val_set.append(val)
  for i in range(num_plus-1):
    for j in range(i+1, num_plus):
      val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
      val_set.append(val)
  val_set = sorted(val_set)
  print(val_set[K-1])

Submission status: Time Limit Exceeded

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


def main():
    n, k = map(int, input().split())
    arr = tuple(sorted(map(int, input().split())))
    minus_arr = tuple(sorted(-x for x in arr))

    ok = - 10 ** 18
    ng = 10 ** 18 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2

        smaller = 0
        smaller_or_same = 0
        for i, a in enumerate(arr, 1):
            if a > 0:
                b = mid // a
                smaller_or_same += max(0, bisect_right(arr, b) - i)
                if mid % a:
                    b += 1
                smaller += max(0, bisect_left(arr, b) - i)
            if a < 0:
                b = mid // (-a)
                smaller_or_same += min(n - i, bisect_right(minus_arr, b))
                if mid % a:
                    b += 1
                smaller += min(n - i, bisect_left(minus_arr, b))
            if a == 0:
                if mid >= 0:
                    smaller_or_same += n - i
                if mid > 0:
                    smaller += n - i
        if smaller < k and k <= smaller_or_same:
            print(mid)
            return
        elif smaller_or_same < k:
            ok = mid + 1
        else:
            ng = mid
    print(ok)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right


def main():
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    minus_arr = [-x for x in arr]
    arr.sort()
    minus_arr.sort()

    ok = - 10 ** 18
    ng = 10 ** 18 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        smaller = 0
        smaller_or_same = 0
        for i, a in enumerate(arr, 1):
            if a > 0:
                b = mid // a
                smaller_or_same += max(0, bisect_right(arr, b) - i)
                if mid % a:
                    b += 1
                smaller += max(0, bisect_left(arr, b) - i)
            if a < 0:
                b = mid // (-a)
                smaller_or_same += min(n - i, bisect_right(minus_arr, b))
                if mid % a:
                    b += 1
                smaller += min(n - i, bisect_left(minus_arr, b))
            if a == 0:
                if mid >= 0:
                    smaller_or_same += n - i
                if mid > 0:
                    smaller += n - i
        if smaller < k and k <= smaller_or_same:
            print(mid)
            return
        elif smaller_or_same < k:
            ok = mid + 1
        else:
            ng = mid
    print(ok)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def quick_sort(list):
    stand=list[0]
    over=[]
    same=[]
    under=[]
    for i in list:
        if(i>stand):
            over.append(i)
        elif(i<stand):
            under.append(i)
        else:
            same.append(i)
    if(len(over)>1):
        over=quick_sort(over)
    else:
        pass
    if(len(under)>1):
        under=quick_sort(under)
    else:
        pass

    return over+same+under

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, K = map(int, input().split())
A = [int(x) for x in input().split()]

# Aを正負で分け、「積が負、積が0、積が正」それぞれのペア数を求める
A_minus = sorted([a for a in A if a < 0])
A_plus = sorted([a for a in A if a > 0])
len_minus = len(A_minus)
len_plus = len(A_plus)
len_zero = N - len_minus - len_plus
pairs_num = (len_minus * len_plus,
             (len_minus + len_plus) * len_zero + len_zero * (len_zero - 1) // 2,
             len_minus * (len_minus - 1) // 2 + len_plus * (len_plus - 1) // 2)
assert sum(pairs_num) == N * (N - 1) // 2

if K <= pairs_num[0]:
    L = -10 ** 18
    R = -1
    while True:
        M = (L + R) // 2
        count = 0
        j = 0
        for i in range(len_plus):
            while j < len_minus and A_plus[i] * A_minus[j] <= M:
                j += 1
            count += j
        
        if count == K - 1 and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M
            
elif pairs_num[0] < K <= pairs_num[0] + pairs_num[1]:
    print(0)
    
else:
    K -= pairs_num[0] + pairs_num[1]
    A_minus = list(map(lambda x: -x, reversed(A_minus)))
    L = 1
    R = 10 ** 18
    while True:
        M = (L + R) // 2
        count = 0
        j = 0
        for i in range(len_minus-1, -1, -1):
            while j < len_minus and A_minus[i] * A_minus[j] <= M:
                j += 1
            count += max(0, j - i - 1)
        j = 0
        for i in range(len_plus-1, -1, -1):
            while j < len_plus and A_plus[i] * A_plus[j] <= M:
                j += 1
            count += max(0, j - i - 1)
            
        if count == K - 1 and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, K = map(int, input().split())
A = [int(x) for x in input().split()]

# Aを正負で分け、「積が負、積が0、積が正」それぞれのペア数を求める
A_minus = sorted([a for a in A if a < 0])
A_plus = sorted([a for a in A if a > 0])
len_minus = len(A_minus)
len_plus = len(A_plus)
len_zero = N - len_minus - len_plus
pairs_num = (len_minus * len_plus,
             (len_minus + len_plus) * len_zero + len_zero * (len_zero - 1) // 2,
             len_minus * (len_minus - 1) // 2 + len_plus * (len_plus - 1) // 2)
assert sum(pairs_num) == N * (N - 1) // 2

if K <= pairs_num[0]:
    L = -10 ** 18
    R = -1
    while True:
        M = (L + R) // 2
        count = 0
        for i in range(len_minus):
            count += len_plus - bisect.bisect_left(A_plus, -(M // -A_minus[i]))
#             count[1] += len_plus - bisect.bisect_left(A_plus, -(M[1] // -A_minus[i]))

        if count == K - 1 and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M
            
#         if count[0] < K <= count[1]:
#             print(M[1])
#             break
#         elif K <= count[0]:
#             R = M[0]
#         elif count[1] < K:
#             L = M[1]
#         else:
#             assert 0
elif pairs_num[0] < K <= pairs_num[0] + pairs_num[1]:
    print(0)
else:
    K -= pairs_num[0] + pairs_num[1]
    L = 1
    R = 10 ** 18
    while True:
        M = (L + R) // 2
        count = 0
        for i in range(len_minus):
            count += min(len_minus - i - 1, len_minus - bisect.bisect_left(A_minus, -(M // -A_minus[i])))
#             count[1] += min(len_minus - i - 1, len_minus - bisect.bisect_left(A_minus, -(M[1] // -A_minus[i])))
        for i in range(len_plus):
            count += max(0, bisect.bisect_right(A_plus, M // A_plus[i]) - i - 1)
#             count[1] += max(0, bisect.bisect_right(A_plus, M[1] // A_plus[i]) - i - 1)

        if count == K - 1 and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M
            
# #         if count[0] < K < count[1] or count[0] < K == count[1]:
#         if count[0] < K <= count[1]:
#             print(M[1])
#             break
# #         elif K == count[0] < count[1] or K == count[0] == count[1] or K < count[0] == count[1] or K < count[0] < count[1]:
# #         elif K <= count[0] <= count[1]:
#         elif K <= count[0]:
#             R = M[0]
# #         else:
# #         elif count[0] == count[1] < K or count[0] < count[1] < K:
#         elif count[1] < K:
#             L = M[1]
#         else:
#             assert 0

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, K = map(int, input().split())
A = [int(x) for x in input().split()]

# Aを正負で分け、「積が負、積が0、積が正」それぞれのペア数を求める
A_minus = sorted([a for a in A if a < 0])
A_plus = sorted([a for a in A if a > 0])
len_minus = len(A_minus)
len_plus = len(A_plus)
len_zero = N - len_minus - len_plus
pairs_num = (len_minus * len_plus,
             (len_minus + len_plus) * len_zero + len_zero * (len_zero - 1) // 2,
             len_minus * (len_minus - 1) // 2 + len_plus * (len_plus - 1) // 2)
assert sum(pairs_num) == N * (N - 1) // 2

if K <= pairs_num[0]:
    L = -10 ** 18
    R = -1
    while True:
        M = [(L + R) // 2, (L + R) // 2 + 1]
        count = [0, 0]
        for i in range(len_minus):
            count[0] += len_plus - bisect.bisect_left(A_plus, -(M[0] // -A_minus[i]))
            count[1] += len_plus - bisect.bisect_left(A_plus, -(M[1] // -A_minus[i]))
            
        if count[0] < K <= count[1]:
            print(M[1])
            break
        elif K <= count[0]:
            R = M[0]
        elif count[1] < K:
            L = M[1]
        else:
            assert 0
elif pairs_num[0] < K <= pairs_num[0] + pairs_num[1]:
    print(0)
else:
    K -= pairs_num[0] + pairs_num[1]
    L = 1
    R = 10 ** 18
    while True:
        M = [(L + R) // 2, (L + R) // 2 + 1]
        count = [0, 0]
        for i in range(len_minus):
            count[0] += min(len_minus - i - 1, len_minus - bisect.bisect_left(A_minus, -(M[0] // -A_minus[i])))
            count[1] += min(len_minus - i - 1, len_minus - bisect.bisect_left(A_minus, -(M[1] // -A_minus[i])))
        for i in range(len_plus):
            count[0] += max(0, bisect.bisect_right(A_plus, M[0] // A_plus[i]) - i - 1)
            count[1] += max(0, bisect.bisect_right(A_plus, M[1] // A_plus[i]) - i - 1)
            
#         if count[0] < K < count[1] or count[0] < K == count[1]:
        if count[0] < K <= count[1]:
            print(M[1])
            break
#         elif K == count[0] < count[1] or K == count[0] == count[1] or K < count[0] == count[1] or K < count[0] < count[1]:
#         elif K <= count[0] <= count[1]:
        elif K <= count[0]:
            R = M[0]
#         else:
#         elif count[0] == count[1] < K or count[0] < count[1] < K:
        elif count[1] < K:
            L = M[1]
        else:
            assert 0

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    N, K = map(int, f_i.readline().split())
    A = sorted(map(int, f_i.readline().split()))
    
    INF = 10 ** 18 + 1
    l = -INF
    r = INF
    
    from bisect import bisect_left, bisect_right
    
    zero_num = bisect_right(A, 0) - bisect_left(A, 0)
    tot_init = zero_num * (N - 1)
    
    mA = A[:bisect_left(A, 0)]
    pA = A[bisect_right(A, 0):]
    
    while l + 1 < r:
        x = (l + r) // 2
        if x > 0:
            tot = tot_init
        else:
            tot = 0
        
        for a in mA:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * a < x:
                    right = mid
                else:
                    left = mid
            tot += (N - right)
            if a ** 2 < x:
                tot -= 1
        
        for a in pA:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * a < x:
                    left = mid
                else:
                    right = mid
            tot += right
            if a ** 2 < x:
                tot -= 1
        
        tot //= 2
        if tot < K:
            l = x
        else:
            r = x
    
    print(l)

solve()

Submission status: Time Limit Exceeded

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

A.sort()
L=len(A)

minus=[]
zero=[]
plus=[]

for i in range(N):
    tem=A[i]
    if tem<0:
        minus.append(tem)
    elif tem==0:
        zero.append(tem)
    else:
        plus.append(tem)

Lminus=len(minus)
Lplus=len(plus)
Lzero=len(zero)
minus_No=Lminus*Lplus
plus_No=(Lminus*(Lminus-1))//2+(Lplus*(Lplus-1))//2
zero_No=(N*(N-1))//2-minus_No-plus_No

def chk(x):
    cnt=0
    d=0
    for i in range(L):
        A1=A[i]
        if A1>0:
            for j in range(Lminus):
                if A1*minus[j]<x:
                    cnt+=1
                else:                    break

        elif A1<0:
            for j in range(Lplus-1,-1,-1):
                if A1*plus[j] < x:
                    cnt+=1
                else:                    break
    temp=cnt//2
    if temp<K:
        return True
    else:
        return False

def chk2(x):
    cnt=0
    d=0
    for i in range(L):
        A1=A[i]
        if A1>0:
            for j in range(Lplus):
                if A1*plus[j]<x:
                    cnt+=1
                    if i == (Lminus+Lzero+j):
                        d += 1
                else:                    break

        elif A1<0:
            for j in range(Lminus-1,-1,-1):
                if A1*minus[j]<x:
                    cnt+=1
                    if j == i:
                        d += 1
                else:                    break
    temp=(cnt-d)//2+minus_No+zero_No
    if temp<K:
        return True
    else:
        return False

if K<=minus_No:
    l=-10**18-1
    r=0

    while l+1<r:
        mid=(r+l)//2
        if chk(mid):
            l=mid
        else:
            r=mid
    print(l)
elif K>(minus_No+zero_No):
    l=0
    r=10**18+1
    while l+1<r:
        mid=(r+l)//2
        if chk2(mid):
            l=mid
        else:
            r=mid
    print(l)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:

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

A.sort()
L=len(A)

minus=[]
zero=[]
plus=[]

for i in range(N):
    tem=A[i]
    if tem<0:
        minus.append(tem)
    elif tem==0:
        zero.append(tem)
    else:
        plus.append(tem)

Lminus=len(minus)
Lplus=len(plus)
Lzero=len(zero)
minus_No=Lminus*Lplus
plus_No=(Lminus*(Lminus-1))//2+(Lplus*(Lplus-1))//2
zero_No=(N*(N-1))//2-minus_No-plus_No

def chk(x):
    cnt=0
    d=0
    for i in range(L):
        A1=A[i]
        if A1>0:
            for j in range(Lminus):
                if A1*minus[j]<x:
                    cnt+=1
                else:                    break

        elif A1<0:
            for j in range(Lplus-1,-1,-1):
                if A1*plus[j] < x:
                    cnt+=1
                else:                    break
    temp=cnt//2
    if temp<K:
        return True
    else:
        return False

def chk2(x):
    cnt=0
    d=0
    for i in range(L):
        A1=A[i]
        if A1>0:
            for j in range(Lplus):
                if A1*plus[j]<x:
                    cnt+=1
                    if i == (Lminus+Lzero+j):
                        d += 1
                else:                    break

        elif A1<0:
            for j in range(Lminus-1,-1,-1):
                if A1*minus[j]<x:
                    cnt+=1
                    if j == i:
                        d += 1
                else:                    break
    temp=(cnt-d)//2+minus_No+zero_No
    if temp<K:
        return True
    else:
        return False

if K<=minus_No:
    l=-10**18-1
    r=0

    while l+1<r:
        mid=(r+l)//2
        if chk(mid):
            l=mid
        else:
            r=mid
    print(l)
elif K>(minus_No+zero_No):
    l=0
    r=10**18+1
    while l+1<r:
        mid=(r+l)//2
        if chk2(mid):
            l=mid
        else:
            r=mid
    print(l)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
# D - Pairs

import numpy as np

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

n_zero = len(A[A == 0])

def n_pairs_less_than_or_equal_to_border(product_border):
    n_pairs = -np.sum(A*A <= product_border) # i==jかつ条件を満たすペアの個数を先に引き、以降重複を許して数える
    n_pairs += n_zero * N * (product_border >= 0)

    for i in range(N):
        if A[i] > 0:
            n_pairs += np.searchsorted(A, product_border//A[i], side="right")
        elif A[i] < 0:
            n_pairs += N - np.searchsorted(A, -(-product_border//A[i]), side="left")

    n_pairs //= 2
    return n_pairs


lower = -(10**18)
upper = 10**18

while lower <= upper:
    x = (lower + upper) // 2
    if n_pairs_less_than_or_equal_to_border(x) >= K:
        ans = x
        upper = x - 1
    else:
        lower = x + 1

print(ans)

Submission status: Time Limit Exceeded

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

INF = 10**18 + 1
l = -INF
r = INF

while l+1 < r:
    x = (l+r)//2
    t = 0

    for i in range(n):
        kl = -1
        kr = n
        if alist[i] < 0:
            while kl+1 < kr:
                c = (kl+kr)//2
                if alist[c] * alist[i] < x:
                    kr = c
                else:
                    kl = c
            t += n - kr
        else:
            while kl+1 < kr:
                c = (kl+kr)//2
                if alist[c] * alist[i] < x:
                    kl = c
                else:
                    kr = c
            t += kr
        if alist[i] * alist[i] < x:
            t -= 1
    t = t//2
    if t < k:
        l = x
    else:
        r = x
ans = l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=(int(x) for x in input().split())
A=[int(x) for x in input().split()]
multi=[]
X=1

for i in range(N):
    multi=multi+[A[i]*A[k] for k in range(X,N)]
    X+=1

multi_sort=sorted(multi)
print(multi_sort[K-1])

Submission status: Time Limit Exceeded

Solution code:
N,K=(int(x) for x in input().split())
A=[int(x) for x in input().split()]
multi=[]
comb=int(N*(N-1)/2)
X=1

for i in range(N):
    multi=multi+[A[i]*A[k] for k in range(X,N)]
    X+=1

multi_sort=sorted(multi)
print(multi_sort[K-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

(n,k) = input().split()
k = int(k)
alist = list(map(int,input().split()))
alist.sort()
nalist = np.array(alist)

ans = 0
minus = np.count_nonzero(nalist<0)
zero  = np.count_nonzero(nalist==0)
plus  = np.count_nonzero(nalist>0)

mp = (minus*(minus-1) + plus*(plus-1))//2    # 正の数
mz = zero*(zero-1)//2 + zero*(plus+minus)    # 0の数
mm = minus*plus                              # 負の数

# 正解が0の場合
if mm < k <= mm + mz:
    ans = 0
else:
    INF = 10**18 + 1
    l = -INF
    r = INF
    x = 0
    c = 0
    cb = 0

    # 正解が負の場合
    if k <= mm:
        r = 0
        mlist = nalist[:minus]
        plist = nalist[:minus+zero-1:-1]
        while l+1 < r:
            x = (l+r)//2
            c = 0
            # 負×正
            for a1 in mlist:
                for a2 in plist:
                    if a1 * a2 < x:
                        c += 1
                    else:
                        break
            if c < k:
                l = x
            else:
                r = x
    # 正解が正の場合
    else:
        l = 0
        k -= mm + mz
        mlist = nalist[minus-1::-1]
        plist = nalist[minus+zero:]
        while l+1 < r:
            x = (l+r)//2
            c = 0
            i = 0
            # 負×負
            for a1 in mlist:
                j = 0
                for a2 in mlist:
                    if a1 * a2 < x:
                        if i != j:  # 自分自身は数えない
                            c += 1
                    else:
                        break
                    j += 1
                i += 1
            i = 0
            # 正×正
            for a1 in plist:
                j = 0
                for a2 in plist:
                    if a1 * a2 < x:
                        if i != j:  # 自分自身は数えない
                            c += 1
                    else:
                        break
                    j += 1
                i += 1
            # 2で割る(2回数えるので)
            c = c//2
            if c < k:
                l = x
            else:
                r = x
    ans = l

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def partsolve(As, x):
    """
    :param As:
    :param x:
    :return: Asの積のペアの中で、x未満となるペアの個数
    """
    count = 0
    for i, a in enumerate(As):
        if a >= 0:
            l = 0
            r = len(As) - 1
            if As[r] * a < x:
                count += len(As)
            elif As[l] * a >= x:
                count += 0
            else:
                while r - l > 1:
                    m = l + (r - l) // 2
                    if As[m] * a < x:
                        l = m
                    else:
                        r = m
                count += l + 1
            if a * a < x:
                count -= 1
        else:
            # a < 0
            l = 0
            r = len(As) - 1
            if As[l] * a < x:
                count += len(As)
            elif As[r] * a >= x:
                count += 0
            else:
                while r - l > 1:
                    m = l + (r - l) // 2
                    if As[m] * a < x:
                        r = m
                    else:
                        l = m
                count += len(As) - r
            if a * a < x:
                count -= 1
    return count // 2

def solve(N, K, As):
    As = sorted(As)
    left = -10**18 - 1
    right = 10**18 + 1
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(As, mid)
        if c < K:
            left = mid
        else:
            right = mid
    return left

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
ll,rr=10**(-18),10**18+1
while ll+1<rr:
  mm=(ll+rr)//2
  cnt=0
  for i,x in enumerate(a):
    l,r=i,n
    while l+1<r:
      m=(l+r)//2
      if x*a[m]>mm:
        r=m
    if l==i:
      if x*x<=mm:
        cnt+=1
    else:
      cnt+=n-i-1
  if cnt<k:
    ll=mm
  else:
    rr=mm
print(ll)