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:
# 解説を参考に作成
# 10170959 を参考に作成
# 一応出そうと思うけど遅すぎる.
# numpy じゃなきゃダメか？


# import sys
# sys.setrecursionlimit(10 ** 6)
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, As):
    As.sort()
    # print(As)
    ans = 0
    l = - 10 ** 18 + 1
    r = 10 ** 18 + 1
    while l <= r:
        m = (r + l) // 2
        c = 0
        # 答えが m 未満となる組み合わせを洗い出す
        for i in range(N):
            # すべての i に対して、i + 1 ～ N の間で2部探索
            ll = i + 1  # 下限を i + 1 とすることで重複をなくせる
            rr = N - 1
            cc = 0
            while ll <= rr:
                mm = (ll + rr) // 2
                if As[i] < 0:
                    # As[i] < 0 の場合、㎜ の増加で 単調減少する
                    # -> As[i] * As[mm] < m を満たす最小の mm を閾値に, mm 以上のすべてのが m 未満となる
                    if As[i] * As[mm] < m:
                        cc = N - mm
                        rr = mm - 1
                    else:
                        ll = mm + 1
                else:
                    # As[i] >= 0 の場合、㎜ の増加で 単調増加する
                    # -> As[i] * As[mm] < m を満たす最大の mm を閾値に, mm 以下のすべてのが m 未満となる
                    # ただし、重複を避けるため i + 1 ～ mm までの数のみを加算する
                    if As[i] * As[mm] < m:
                        cc = mm - i
                        ll = mm + 1
                    else:
                        rr = mm - 1
            # print('   ', i, mm, cc)
            c += cc
        # print(l, m, r, c, ans)
        # input()
        if c < K:
            # c < K を満たす最大の m が答えとなる.
            # ans となる K の値が複数ある場合, ans 超の場合は ans 自身をカウントするため c >= K となる.
            # よって収束の過程で必ず「c < K を満たす最大の m」がここで設定されることになる.
            ans = m
            l = m + 1
        else:
            r = m - 1

    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    As = [int(i) for i in input().split()]

    # N, K = 200000, 1000
    # As = [-200000 + i for i in range(200000)]
    # print(As[1], As[-1])
    solve(N, K, As)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a.sort()
p = []
for i in range(n):
   for j in range(i+1, n):
      p.append(a[i]*a[j])

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

N,K = map(int,input().split())
import sys
input = sys.stdin.readline
nums = list(map(int,input().split()))
import itertools
cmbs = itertools.combinations(nums,2)
ans=[cmb[0] * cmb[1] for cmb in cmbs]
ans.sort()
print(ans[K-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def count_pair(i, a, n, x):
    l = -1
    r = n
    if a[i] < 0:
        while l+1 < r:
            c = (l+r) // 2
            if a[c] * a[i] < x:
                r = c
            else:
                l = c
        return n-r
    else:
        while l+1 < r:
            c = (l+r) // 2
            if a[c] * a[i] < x:
                l = c
            else:
                r = c
        return r

n, k = map(int,input().split())
a = list(map(int,input().split()))
inf = 1+(10**18)

a = sorted(a)

l = -1*inf
r = inf

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

print(l)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    ap = []
    am = []
    for i in a:
        if i > 0:
            ap.append(i)
        elif i < 0:
            am.append(i)

    ap.sort(reverse=True)
    am.sort()
    hq = []
    if k <= len(ap)*len(am):
        done = [[-1]*len(am)+[1] for _ in [0]*len(ap)]
        done.append([1]*(len(am)+1))
        heapq.heappush(hq,(ap[0]*am[0],0,0))
        done[0][0] = 1
        for i in range(k-1):
            num,api,ami = heapq.heappop(hq)
            if done[api][ami+1] == -1:
                heapq.heappush(hq,(ap[api]*am[ami+1],api,ami+1))
                done[api][ami+1] = 1
            if done[api+1][ami] == -1:
                heapq.heappush(hq,(ap[api+1]*am[ami],api+1,ami))
                done[api+1][ami] = 1
        num,api,ami = heapq.heappop(hq)
        print(num)
    elif n*(n-1)//2-k+1 <= len(ap)*(len(ap)-1)//2+len(am)*(len(am)-1)//2:
        dop = [[-1]*len(ap)+[1] for _ in [0]*(len(ap)+1)]
        for i,di in enumerate(dop):
            di[i] = 1
        dom = [[-1]*len(am)+[1] for _ in [0]*(len(am)+1)]
        for i,di in enumerate(dom):
            di[i] = 1
        if len(ap) > 1:
            heapq.heappush(hq,(-ap[0]*ap[1],0,1,"p"))
            dop[0][1] = 1
        if len(am) > 1:
            heapq.heappush(hq,(-am[0]*am[1],0,1,"m"))
            dom[0][1] = 1
        for i in range(n*(n-1)//2-k):
            num,a0,a1,char = heapq.heappop(hq)
            if char == "p":
                ax = ap
                dx = dop
            else:
                ax = am
                dx = dom
            if dx[a0][a1+1] == -1:
                heapq.heappush(hq,(-ax[a0]*ax[a1+1],a0,a1+1,char))
                dx[a0][a1+1] = 1
            if dx[a0+1][a1] == -1:
                heapq.heappush(hq,(-ax[a0+1]*ax[a1],a0+1,a1,char))
                dx[a0+1][a1] = 1
        num,a0,a1,char = heapq.heappop(hq)
        print(-num)
    else:
        print(0)



    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=np.array(readline().strip().split(),dtype="int64")
    
    a.sort()
    neg=a[a<0]
    zero=a[a==0]
    pos=a[a>0]
    l=-10**18-1
    r=10**18
    while l<r-1:
        x=(l+r)//2
        cnt=0
        if len(neg)>0:
            cnt+=(len(a)-np.searchsorted(a,(x+neg+1)//neg)).sum()
            for i in range(len(neg)):
                if neg[i]**2<=x:
                    cnt-=1
        if len(zero)>0:
            if x>=0:
                cnt+=(len(a)-1)*len(zero)
        if len(pos)>0:
            cnt+=np.searchsorted(a,x//pos,side="right").sum()
            for i in range(len(pos)):
                if pos[i]**2<=x:
                    cnt-=1

        cnt//=2
        if cnt>=k: r=x
        else: l=x

    print(r)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

plus=0
minus=0
zero=0

for i in vec:
  if i>0 :
    plus+=1
  elif i<0:
    minus+=1
  else:
    zero+=1
    
vec=sorted(vec)
    
def calc(x):
  num = 0
  if(x>=0):
    num += zero*n
  for i in vec:
    if i*i<=x:
      num-=1
    
    if i>0:
      num += bisect.bisect_right(vec,x//i)
    elif i<0:
      num -= bisect.bisect_left(vec,-(-x//i))
  num += n*minus
  return num // 2
    

ok = 10**18
ng = -10**18-1
while ok - ng > 1:
  mid = (ok + ng) // 2
  if calc(mid) >= k:
    ok = mid
  else:
    ng = mid
    
print(ok)

Submission status: Time Limit Exceeded

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

# 負の個数
num_neg = bisect.bisect_left(A, 0)
# 0の個数
num_zero = bisect.bisect_right(A, 0) - num_neg
# 正の個数
num_pos = N - num_neg - num_zero

A_neg_rev = A[:num_neg] # 絶対値が大きいものからになるようにソート
A_pos = A[num_neg + num_zero:] # 絶対値が小さいものからになるようにソート

A_neg = A_neg_rev[::-1] # 絶対値が大きいものからになるようにソート
A_pos_rev = A_pos[::-1] # 絶対値が小さいものからになるようにソート

# 値が0になるペアの個数
cnt_zero = num_zero * (num_pos + num_neg) + (num_zero * (num_zero - 1) // 2)
# 値が負になるペアの個数
cnt_neg = num_pos * num_neg

# 値が正になるとき
def syakutori_pos(arr, mid):
    if len(arr) == 0:
        return 0
    cnt = 0
    l = 0
    r = len(arr) - 1
    while l < r:
        if arr[l] * arr[r] <= mid:
            cnt += r - l
            l += 1
        else:
            r -= 1
    return cnt

# 値が負になるとき
def syakutori_neg(arr_pos, arr_neg, mid):
    if len(arr_pos) == 0 or len(arr_neg) == 0:
        return 0
    arr = arr_neg + arr_pos
    cnt = 0
    l = 0
    r = len(arr) - 1
    while l < len(arr_neg) and r >= len(arr_neg):
        if arr[l] * arr[r] <= mid:
            cnt += r - len(arr_neg) + 1
            l += 1
        else:
            r -= 1
    return cnt

# 自分以下の数になるペアの個数がK個以上になる
ok = 10 ** 18
ng = -ok - 1
while ng + 1 < ok:
    mid = (ok + ng) // 2
    cnt = 0
    if mid > 0:
        cnt += cnt_zero
        cnt += cnt_neg
        cnt += syakutori_pos(A_pos, mid) + syakutori_pos(A_neg, mid)
    elif mid == 0:
        cnt += cnt_zero
        cnt += cnt_neg
    else:
        cnt += syakutori_neg(A_pos_rev, A_neg_rev, mid)
    if cnt >= K:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

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

# 負の個数
num_neg = bisect.bisect_left(A, 0)
# 0の個数
num_zero = bisect.bisect_right(A, 0) - num_neg
# 正の個数
num_pos = N - num_neg - num_zero

A_neg_rev = A[:num_neg] # 絶対値が小さいものからになるようにソート
A_pos = A[num_neg + num_zero:]

A_neg = A_neg_rev[::-1] # 絶対値が大きいものからになるようにソート
A_pos_rev = A_pos[::-1]

# 値が0になるペアの個数
cnt_zero = num_zero * (num_pos + num_neg) + (num_zero * (num_zero - 1) // 2)
# 値が負になるペアの個数
cnt_neg = num_pos * num_neg

# 値が正になるとき
def syakutori_pos(arr, mid):
    if len(arr) == 0:
        return 0
    cnt = 0
    l = 0
    r = len(arr) - 1
    while l < r:
        if arr[l] * arr[r] <= mid:
            cnt += r - l
            l += 1
        else:
            r -= 1
    return cnt

# 値が負になるとき
def bin_search_neg(arr_pos, arr_neg, mid):
    if len(arr_pos) == 0 or len(arr_neg) == 0:
        return 0
    if len(arr_pos) > len(arr_neg): # 小さい方をシードにする
        tmp = arr_neg
        arr_neg = arr_pos
        arr_pos = tmp
    cnt = 0
    for a in arr_pos:
        ok = 0
        ng = len(arr_neg) - 1
        if a * arr_neg[ok] > mid:
            return cnt
        elif a * arr_neg[ng] <= mid:
            cnt += ng + 1
        else:
            while ok + 1 < ng:
                c = (ok + ng) // 2
                if a * arr_neg[c] <= mid:
                    ok = c
                else:
                    ng = c
        
            cnt += ok + 1
    return cnt

# 自分以下の数になるペアの個数がK個以上になる
ok = 10 ** 18
ng = -ok - 1
while ng + 1 < ok:
    mid = (ok + ng) // 2
    cnt = 0
    if mid > 0:
        cnt += cnt_zero
        cnt += cnt_neg
        cnt += syakutori_pos(A_pos, mid) + syakutori_pos(A_neg, mid)
    elif mid == 0:
        cnt += cnt_zero
        cnt += cnt_neg
    else:
        cnt += bin_search_neg(A_pos_rev, A_neg_rev, mid)
    if cnt >= K:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

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

# 負の個数
num_neg = bisect.bisect_left(A, 0)
# 0の個数
num_zero = bisect.bisect_right(A, 0) - num_neg
# 正の個数
num_pos = N - num_neg - num_zero

A_neg_rev = A[:num_neg] # 絶対値が小さいものからになるようにソート
A_pos = A[num_neg + num_zero:]

A_neg = A_neg_rev[::-1] # 絶対値が大きいものからになるようにソート
A_pos_rev = A_pos[::-1]

# 値が0になるペアの個数
cnt_zero = num_zero * (num_pos + num_neg) + (num_zero * (num_zero - 1) // 2)
# 値が負になるペアの個数
cnt_neg = num_pos * num_neg

# 値が正になるとき
def bin_search_pos(arr, mid):
    if len(arr) == 0:
        return 0
    cnt = 0
    for i in range(len(arr) - 1):
        ok = i + 1
        ng = len(arr) - 1
        a = arr[i]
        if a * arr[ok] > mid:
            return cnt
        elif a * arr[ng] <= mid:
            cnt += ng - i
        else:
            while ok + 1 < ng:
                c = (ok + ng) // 2
                if a * arr[c] <= mid:
                    ok = c
                else:
                    ng = c
        
            cnt += ok - i
    return cnt

# 値が負になるとき
def bin_search_neg(arr_pos, arr_neg, mid):
    if len(arr_pos) == 0 or len(arr_neg) == 0:
        return 0
    if len(arr_pos) > len(arr_neg): # 小さい方をシードにする
        tmp = arr_neg
        arr_neg = arr_pos
        arr_pos = tmp
    cnt = 0
    for a in arr_pos:
        ok = 0
        ng = len(arr_neg) - 1
        if a * arr_neg[ok] > mid:
            return cnt
        elif a * arr_neg[ng] <= mid:
            cnt += ng + 1
        else:
            while ok + 1 < ng:
                c = (ok + ng) // 2
                if a * arr_neg[c] <= mid:
                    ok = c
                else:
                    ng = c
        
            cnt += ok + 1
    return cnt

# 自分以下の数になるペアの個数がK個以上になる
ok = 10 ** 18
ng = -ok - 1
while ng + 1 < ok:
    mid = (ok + ng) // 2
    cnt = 0
    if mid > 0:
        cnt += cnt_zero
        cnt += cnt_neg
        cnt += bin_search_pos(A_pos, mid) + bin_search_pos(A_neg, mid)
    elif mid == 0:
        cnt += cnt_zero
        cnt += cnt_neg
    else:
        cnt += bin_search_neg(A_pos_rev, A_neg_rev, mid)
    if cnt >= K:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

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

# 負の個数
num_neg = bisect.bisect_left(A, 0)
# 0の個数
num_zero = bisect.bisect_right(A, 0) - num_neg
# 正の個数
num_pos = N - num_neg - num_zero

A_neg = A[:num_neg][::-1] # 絶対値が小さいものからになるようにソート
A_pos = A[num_neg + num_zero:]

A_neg_rev = A_neg[::-1] # 絶対値が大きいものからになるようにソート
A_pos_rev = A_pos[::-1]

# 値が0になるペアの個数
cnt_zero = num_zero * (num_pos + num_neg) + (num_zero * (num_zero - 1) // 2)
# 値が負になるペアの個数
cnt_neg = num_pos * num_neg

# 値が正になるとき
def bin_search_pos(arr, mid):
    if len(arr) == 0:
        return 0
    cnt = 0
    for i in range(len(arr) - 1):
        ok = i + 1
        ng = len(arr) - 1
        a = arr[i]
        if a * arr[ok] > mid:
            return cnt
        elif a * arr[ng] <= mid:
            cnt += ng - i
        else:
            while ok + 1 < ng:
                c = (ok + ng) // 2
                if a * arr[c] <= mid:
                    ok = c
                else:
                    ng = c
        
            cnt += ok - i
    return cnt

# 値が負になるとき
def bin_search_neg(arr_pos, arr_neg, mid):
    if len(arr_pos) == 0 or len(arr_neg) == 0:
        return 0
    cnt = 0
    for a in arr_pos:
        ok = 0
        ng = len(arr_neg) - 1
        if a * arr_neg[ok] > mid:
            return cnt
        elif a * arr_neg[ng] <= mid:
            cnt += ng + 1
        else:
            while ok + 1 < ng:
                c = (ok + ng) // 2
                if a * arr_neg[c] <= mid:
                    ok = c
                else:
                    ng = c
        
            cnt += ok + 1
    return cnt

# 自分以下の数になるペアの個数がK個以上になる
ok = 10 ** 18
ng = -ok - 1
while ng + 1 < ok:
    mid = (ok + ng) // 2
    cnt = 0
    if mid > 0:
        cnt += cnt_zero
        cnt += cnt_neg
        cnt += bin_search_pos(A_pos, mid) + bin_search_pos(A_neg, mid)
    elif mid == 0:
        cnt += cnt_zero
        cnt += cnt_neg
    else:
        cnt += bin_search_neg(A_pos_rev, A_neg_rev, mid)
    if cnt >= K:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
def foo(A,x,N):
    count = 0
    for a1 in A:
        if a1>=0:
            (l,r) = (-1,N)
            while (l+1<r):
                center = round((l+r)/2)
                if a1*A[center]<x:
                    l = center
                else:
                    r = center
            count += r
        else:
            tmp = 0
            (l,r) = (-1,N)
            while (l+1<r):
                center = round((l+r)/2)
                if a1*A[center]<x:
                    r = center
                else:
                    l = center
            count += N-r
    # 自分同士を除く
    for a in A:
        if a*a<x:
            count -= 1
    # ダブり数え上げを除く
    count = int(count/2)

    return count

def main():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    A = sorted(A)
    # K番目の値 <=> x未満がK個未満である時のxの最大値
    # 二分探索でxを探す
    # 積がx未満であるペアが何個あるか調べる
    # 上の操作において、a*bのaを固定するが、
    # (1)a>=0:y=axは単調増加
    # (2)a<0:y=axは単調減少
    # であることに注意して最後にダブりと自分同士を除けばok

    # BSのl,r,xを初期化
    (l,r) = (0,0)
    if A[0]>=0: # 正の値のみ
        l = 0
        r = A[-1]*A[-1]
    elif A[-1]<=0: # 負の数のみ
        l = 0
        r = A[0]*A[0]
    else: # 正負混在
        l = A[0]*A[-1]
        r = max(A[0]*A[0], A[-1]*A[-1])

    while(l+1<r):
        x = int((l+r)/2)
        n = foo(A,x,N)
        if n>=K:
            r = x
        else:
            l = x
    print(l)


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
stdin = open(0)

N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().split(), np.int64)


A = np.sort(A)
zero = A[A == 0]
pos = list(A[A > 0])
neg = list(A[A < 0])

neg_count = len(pos) * len(neg)
pos_count = len(pos) * (len(pos) - 1) // 2 + len(neg) * (len(neg) - 1) // 2
zero_count = N * (N - 1) // 2 - neg_count - pos_count

if K > neg_count and K <= neg_count + zero_count:
    print(0)
    exit(0)

def f(x):
    """x以下の積の組み合わせを数える(k番目が負の場合)"""
    count = 0
    pos_idx = None
    neg_idx = 0
    for idx, p in enumerate(pos):
        if p * neg[neg_idx] <= x:
            pos_idx = idx
            break
    # pos_idxに最大の負の値x正の値 <= xを満たす最小の正値のindexが入っている
    if pos_idx is not None:
        count += len(pos) - pos_idx
        # print(pos_idx, count)
        while neg_idx < len(neg) - 1:
            neg_idx += 1
            ans = None
            for i in range(pos_idx, len(pos)):
                if pos[i] * neg[neg_idx] <= x:
                    ans = i
                    break
            if ans is None:
                break
            count += len(pos) - ans
            pos_idx = ans
    return count

def g(x):
    """x以下の積の組み合わせを数える(k番目が正の場合)"""
    count = neg_count + zero_count
    # print('c1', count)
    l_idx = 0
    r_idx = 0
    # 正数 x 正数の場合
    for idx, p in enumerate(reversed(pos)):
        if p * pos[l_idx] <= x:
            r_idx = len(pos) - idx - 1
            break
    if r_idx > 0:
        count += (r_idx + 1) - 1  # index = 0の分は引く
        while r_idx - l_idx > 0:
            l_idx += 1
            ans = l_idx
            # print(l_idx, r_idx)
            for i in reversed(range(l_idx + 1, r_idx + 1)):
                # print(i, pos[i], l_idx, pos[l_idx])
                if pos[i] * pos[l_idx] <= x:
                    ans = i
                    break
            # print('ans', ans, l_idx)
            if ans > l_idx:
                count += ans - l_idx
                r_idx = ans
            else:
                break
    # print('c2', count)
    # 負数 x 負数の場合
    r_idx = len(neg) - 1
    l_idx = len(neg) - 1
    for idx, n in enumerate(neg):
        if n * neg[r_idx] <= x:
            l_idx = idx
            break
    # print(l_idx, r_idx)
    if l_idx < r_idx:
        count += len(neg) - l_idx - 1 # r_idxの分は引く
        # print('c3', count)
        while r_idx - l_idx > 0:
                r_idx -= 1
                ans = r_idx
                # print(l_idx, r_idx)
                for i in range(l_idx, r_idx):
                    # print(i, pos[i], l_idx, pos[l_idx])
                    if neg[i] * neg[r_idx] <= x:
                        ans = i
                        break
                # print(l_idx, r_idx, ans)
                # print('ans', ans, l_idx)
                if ans < r_idx:
                    count += r_idx - ans
                    l_idx = ans
                else:
                    break
    return count


def h(x):
    return f(x) if K <= neg_count else g(x)


# print(h(-7))

l = -1 * 10 ** 18
r = 10 ** 18
if K <= neg_count:
    r = 0
    h = f
else:
    l = 0
    h = g

while l + 1 < r:
    mid = (l + r) // 2
    count = h(mid)
    # print(mid, count)
    if count >= K:
        r = mid
    else:
        l = mid
print(r)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
from itertools import *

class abc_155:
    
    def __init__(self):
        pass
    
    def A(self):
       pass
    def B(self):
        pass
        
    def C(self):
        N=int(input())
        S=[input() for i in range(N)]
        c=collections.Counter(S).most_common()
        ans=[]
        ans.append(c[0][0])
        roop=c[0][1]
        
        for i in range(1,len(c)):
            if roop==c[i][1]:ans.append(c[i][0])
            else:break
        ans.sort()
        for i in ans:print(i)
                
    def D(self):
        NK=list(map(int,input().split()))
        A=list(map(int,input().split()))
        
        #nCrのリスト
        dabur=list(combinations(A,2))
        ans=list(map(lambda i:i[0]*i[1],dabur))
        ans.sort()
        print(ans[NK[1]-1])
        
        
    def E(self):
        pass
    
    def F(self):
        pass
    
    
if __name__=='__main__':
    obj=abc_155()
    obj.D()

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    # aiについて、同じ数字は1つにまとめた時の数、つまりaiの種類数を求める
    # (積の数値:個数)の辞書を作成してK番目を求める
    collA = collections.Counter(A)
    mul = {}
    collAlist = list(collA.items())
    for i,(k1,v1) in enumerate(collAlist):
        if v1>1:
            if mul.get(k1*k1)==None:
                mul[k1*k1] = int(v1*(v1-1)/2)
            else:
                mul[k1*k1] += int(v1*(v1-1)/2)
        for (k2,v2) in collAlist[i+1:]:
            if mul.get(k1*k2)==None:
                mul[k1*k2] = v1*v2
            else:
                mul[k1*k2] += v1*v2
    mul_sorted = sorted(mul.items(), key=lambda x:x[0])
    tmp = 0
    for (k,v) in mul_sorted:
        tmp += v
        if tmp>=K:
            print(k)
            break

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_left 
def main():
    N, K = map(int, readline().split())
    A = [int(i) for i in readline().split()]
    A.sort()
    INF = int(1e18)+1


    def judge(x):
        cnt = 0
        for a in A:
            if a < 0:
                l = -1
                r = N
                while r-l>1:
                    c = (l+r)//2
                    if a*A[c]<x:
                        r = c
                    else:
                        l = c
                cnt += N-r 
            else:
                l = -1
                r = N 
                while r-l > 1:
                    c = (l+r)//2
                    if a*A[c]<x:
                        l = c
                    else:
                        r = c 
                cnt += r

            if a*a<x:
                cnt -= 1
        cnt //= 2
        return cnt

    mx = INF
    mi = -INF
    while mx-mi>1:
        md = (mx+mi)//2
        if judge(md)<K:
            mi = md
        else:
            mx = md
    print(mi)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_left 
def main():
    N, K = map(int, readline().split())
    A = [int(i) for i in readline().split()]
    A.sort()
    INF = int(1e18)+1


    def judge(x):
        cnt = 0
        for i in range(N):
            if A[i] < 0:
                l = -1
                r = N
                while r-l>1:
                    c = (l+r)//2
                    if A[i]*A[c]<x:
                        r = c
                    else:
                        l = c
                cnt += N-r 
            else:
                l = -1
                r = N 
                while r-l > 1:
                    c = (l+r)//2
                    if A[i]*A[c]<x:
                        l = c
                    else:
                        r = c 
                cnt += r

            if A[i]*A[i]<x:
                cnt -= 1
        cnt //= 2
        return cnt

    mx = INF
    mi = -INF
    while mx-mi>1:
        md = (mx+mi)//2
        if judge(md)<K:
            mi = md
        else:
            mx = md
    print(mi)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    r = 10 ** 18 + 1
    l = -10 ** 18 - 1
    while r - l > 1:
        m = (r + l) // 2
        count = 0
        for i in range(n):
            if a[i] > 0:
                x = m // a[i]
                y = bisect.bisect_right(a, x)
                if y <= i:
                    count += y
                else:
                    count += y - 1
            elif a[i] < 0:
                x = -(m // -a[i])
                y = bisect.bisect_left(a, x)
                if y > i:
                    count += n - y
                else:
                    count += n - y - 1
            else:
                if m >= 0:
                    count += n - 1
                else:
                    continue
        if count // 2 >= k:
            r = m
        else:
            l = m
    print(r)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import bisect
    import sys
    input = sys.stdin.readline

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    r = 10 ** 18 + 1
    l = -10 ** 18 - 1
    while r - l > 1:
        m = (r + l) // 2
        count = 0
        for i in range(n):
            if a[i] > 0:
                x = m // a[i]
                y = bisect.bisect_right(a, x)
                if y <= i:
                    count += y
                else:
                    count += y - 1
            elif a[i] < 0:
                x = -(m // -a[i])
                y = bisect.bisect_left(a, x)
                if y > i:
                    count += n - y
                else:
                    count += n - y - 1
            else:
                if m >= 0:
                    count += n - 1
                else:
                    continue
        if count // 2 >= k:
            r = m
        else:
            l = m
    print(r)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Am = []
A0 = []
Ap = []
for i in A:
    if i<0:
        Am.append(i)
    elif i ==0:
        A0.append(i)
    else:
        Ap.append(i)
        
D=[]
# -*+の方が小さい
if len(Am)*len(Ap)>=K:
    Am.sort()
    Ap.sort(reverse=True)
    for p in range(1,len(Am)+1):
        for q in range(1,len(Ap)+1):
            if p*q<=K:
                D.append(Am[p-1]*Ap[q-1])
            else:
                break
    D.sort()
    print(D[K-1])
elif len(Am)*len(Ap)<K<=len(Am)*len(Ap)+len(A0)*(len(Am)+len(Ap))+len(A0)*(len(A0)-1)//2:
    print(0)
else:
    l=K-len(Am)*len(Ap)-len(A0)*(len(Am)+len(Ap))-len(A0)*(len(A0)-1)//2
    Am.sort(reverse=True)
    Ap.sort()
    for p in range(1,len(Am)+1):
        for q in range(p+1,len(Am)+1):
            if p*q//2<=l:
                D.append(Am[p-1]*Am[q-1])
    for p in range(1,len(Ap)+1):
        for q in range(p+1,len(Ap)+1):
            if p*q//2<=l:
                D.append(Ap[p-1]*Ap[q-1])
    D.sort()
    print(D[l-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3


# x 未満が k 個未満であるか
def f(x):
    cnt = 0
    for i in range(n):
        if a[i] < 0:
            ok = n
            ng = -1
            while abs(ok - ng) > 1:
                m = (ok + ng) // 2
                if a[m] * a[i] < x:
                    ok = m
                else:
                    ng = m
            cnt += n - ok
        else:
            ok = -1
            ng = n
            while abs(ok - ng) > 1:
                m = (ok + ng) // 2
                if a[m] * a[i] < x:
                    ok = m
                else:
                    ng = m
            cnt += ok + 1
        if a[i] * a[i] < x:
            cnt -= 1
    cnt //= 2
    return cnt < k


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


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(2 ** n):
  bit_list = []
  for j in range(n):
    if (i >> j) & 1:
      bit_list.append(j)
    if len(bit_list) > 2:
      break
  if len(bit_list) == 2:
    res.append(a[bit_list[0]] * a[bit_list[1]])
print(sorted(res)[k - 1])

Submission status: Time Limit Exceeded

Solution code:
#155d
import itertools

n, k = map(int, input().split())
a = map(int, input().split())
c = itertools.combinations(a, 2)
res = []
for _c in c:
  res.append(_c[0] * _c[1])
print(sorted(res)[k - 1])