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:
# 解説放送の改変
# aを負0正に分けて処理

def bs_kth_lt_0():
    inf = 10 ** 18 + 1

    def negative(e):
        ok, ng = len(p), -1
        while abs(ng - ok) > 1:
            mid = (ng + ok) // 2
            if p[mid] * e < cand:
                ok = mid
            else:
                ng = mid
        return len(p) - ok
        # [ok,n)の区間が
        # a[ok] * e < cand を満たす
        # 区間の長さ n - ok = 積がcand未満という条件を満たす候補数になる
        # 同じもの同士のペアやペアの二重計上があるので、あとで減らす

    def is_ok():
        tot = 0
        for e in m:
            tot += negative(e)
        return tot < k

    ok, ng = -inf, 0
    while abs(ng - ok) > 1:
        cand = (ng + ok) // 2
        if is_ok():
            ok = cand
        else:
            ng = cand
    return ok


def bs_kth_gt_0():
    inf = 10 ** 18 + 1

    def positive(e, lis):
        ok, ng = -1, len(lis)
        while abs(ng - ok) > 1:
            mid = (ng + ok) // 2
            if lis[mid] * e < cand:
                ok = mid
            else:
                ng = mid
        return ok + 1
        # [0,ok]の区間が
        # a[ok] * e < cand を満たす
        # ok は 0-indexed なので 1-indexed に直すと、
        # 区間の長さ = 積がcand未満という条件を満たす候補数になる
        # 同じもの同士のペアやペアの二重計上があるので、あとで減らす

    def is_ok(cand):
        tot = 0
        for lis in (m, p):
            for e in lis:
                tot += positive(e, lis)
                if e * e < cand:
                    tot -= 1  # 同じもの同士のペアを減らす
        tot //= 2  # (1,2),(2,1)のような同一ペアの二重計上を減らす
        return tot < k

    ok, ng = 0, inf
    while abs(ng - ok) > 1:
        cand = (ng + ok) // 2
        if is_ok(cand):
            ok = cand
        else:
            ng = cand
    return ok


def main():
    from bisect import bisect_left

    global n, k, a, m, z, p

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

    i = bisect_left(a, 0)
    j = bisect_left(a, 1)
    m, z, p = a[:i], a[i:j], a[j:]

    def combi(n, r):
        if r == 0:
            return 1
        return n * combi(n - 1, r - 1) // r

    cnt_m = len(m) * len(p)
    cnt_z = combi(len(z), 2) + len(z) * (n - len(z))
    # cnt_p = combi(n, 2) - cnt_m - cnt_z

    if k <= cnt_m:
        # k番目の値は負
        ans = bs_kth_lt_0()
        print(ans)
        return

    elif k <= cnt_m + cnt_z:
        # k番目の値は0
        print(0)
        return
    else:
        # k番目の値は正
        k -= cnt_m + cnt_z  # 正の値の中での順位に直す

        *m, = sorted(-x for x in m)  # 正に符号変換して昇順ソート
        ans = bs_kth_gt_0()
        print(ans)
        return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#大きな数の割り算は計算重いかも，for文内も掛け算の二分探索に


import bisect
import sys
input = sys.stdin.readline

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

#積がX未満になるものがK-1個以下になる最大のXを探す

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

while abs(ng-ok)>1:
    X=(ok+ng)//2
    temp=0
    
    for i in range(N):
        if A[i]>0:
            #A[i]*A[j]がX未満となるjの個数を数える
            l=-1
            r=N
            while r-l>1:
                med=(l+r)//2
                if A[i]*A[med]<X:
                    l=med
                else:
                    r=med
            temp+=r

        elif A[i]<0:
            #A[i]*A[j]がX未満となるjの個数を数える
            l=-1
            r=N
            while r-l>1:
                med=(l+r)//2
                if A[i]*A[med]<X:
                    r=med
                else:
                    l=med
            temp+=N-r
            
        else:
            if X>0:
                temp+=N
        if A[i]*A[i]<X:
            temp-=1
            
    temp=temp//2
    if temp>=K:
        ng=X
    else:
        ok=X

print(ok)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**20

# 一方をpに固定したとき、積がx未満になるペアの個数
def f(p, x, n, a):
    if p > 0:
        l = -1
        r = n
        while l + 1 < r:
            mid = (l + r) // 2
            if p * a[mid] < x:
                l = mid
            else:
                r = mid
        return l+1
    else:
        l = -1
        r = n
        while l + 1 < r:
            mid = (l + r)//2
            if p * a[mid] < x:
                r = mid
            else:
                l = mid
        return n-r

# x未満になる組み合わせ数がk未満ならTrue
def is_under(x, k, n, a):
    ans = 0
    for c in a:
        ans += f(c, x, n, a)
        if c**2 < x:
            ans -= 1
    ans /= 2
    if ans < k:
        return True
    return False

def main():
    n, k = list(map(int, input().strip().split()))
    a = sorted(list(map(int, input().strip().split())))
    l = -INF
    r = INF
    while l + 1 < r:
        mid = (l+r)//2
        if is_under(mid, k, n, a):
            l = mid
        else:
            r = mid
    print(l)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

# 一方をpに固定したとき、積がx未満になるペアの個数
def f(p, x, n, a):
    if p > 0:
        l = -1
        r = n
        while l + 1 < r:
            mid = (l + r) // 2
            if p * a[mid] < x:
                l = mid
            else:
                r = mid
        return l+1
    else:
        l = -1
        r = n
        while l + 1 < r:
            mid = (l + r)//2
            if p * a[mid] < x:
                r = mid
            else:
                l = mid
        return n-r

# x未満になる組み合わせ数がk未満ならTrue
def is_under(x, k, n, a):
    ans = 0
    for c in a:
        ans += f(c, x, n, a)
        if c**2 < x:
            ans -= 1
    ans /= 2
    if ans < k:
        return True
    return False

def main():
    n, k = list(map(int, input().strip().split()))
    a = sorted(list(map(int, input().strip().split())))
    l = -INF
    r = INF
    while l + 1 < r:
        mid = (l+r)//2
        if is_under(mid, k, n, a):
            l = mid
        else:
            r = mid
    print(l)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説放送
# 関数を切り分けたものはTLEした

def main():
    inf = 10 ** 18 + 1

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

    def is_ok(x):
        """x未満の値はk個未満か"""
        tot = 0
        for a_ in a:
            if a_ < 0:
                l, r = -1, n
                while (r - l) > 1:
                    c = (l + r) // 2
                    if a[c] * a_ < x:
                        r = c
                    else:
                        l = c
                tot += n - r
            else:
                l, r = -1, n
                while (r - l) > 1:
                    c = (l + r) // 2
                    if a[c] * a_ < x:
                        l = c
                    else:
                        r = c
                tot += r
            if a_ * a_ < x:
                tot -= 1
        tot //= 2
        return tot < k

    l, r = -inf, inf
    while (r - l) > 1:
        x = (l + r) // 2
        if is_ok(x):  # x未満の値はk個未満か？
            l = x
        else:
            r = x
        # 「x未満がk個未満」であるxの最大値
    print(l)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説放送
# 写経

def binary_search():
    """ok未満にk個未満の数があるようなokの最大値=k番目"""
    inf = 10 ** 18 + 1

    def positive(e):
        ok, ng = -1, n
        while abs(ng - ok) > 1:
            mid = (ng + ok) // 2
            if a[mid] * e < cand:
                ok = mid
            else:
                ng = mid
        return ok + 1
        # [0,ok]の区間が
        # a[ok] * e < cand を満たす
        # ok は 0-indexed なので 1-indexed に直すと、
        # 区間の長さ = 積がcand未満という条件を満たす候補数になる
        # 同じもの同士のペアやペアの二重計上があるので、あとで減らす

    def negative(e):
        ok, ng = n, -1
        while abs(ng - ok) > 1:
            mid = (ng + ok) // 2
            if a[mid] * e < cand:
                ok = mid
            else:
                ng = mid
        return n - ok
        # [ok,n)の区間が
        # a[ok] * e < cand を満たす
        # 区間の長さ n - ok = 積がcand未満という条件を満たす候補数になる
        # 同じもの同士のペアやペアの二重計上があるので、あとで減らす

    def is_ok(cand):
        tot = 0
        for e in a:
            if e < 0:
                tot += negative(e)
            else:
                tot += positive(e)
            if e * e < cand:
                tot -= 1  # 同じもの同士のペアを減らす
        tot //= 2  # (1,2),(2,1)のような同一ペアの二重計上を減らす
        return tot < k

    ok, ng = -inf, inf
    while abs(ng - ok) > 1:
        cand = (ng + ok) // 2
        if is_ok(cand):
            ok = cand
        else:
            ng = cand
    return ok


def main():
    global n, k, a

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

    ans = binary_search()
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def num_search(l,r,mid):
  total = 0
  for i in range(N):
    if(A[i] < 0):
      l=-1
      r=N
      while l+1 < r:
        c = (l+r)//2
        if(A[c]*A[i]<mid):
          r=c
        else:
          l=c
        #print(str(i)+'[m] l='+str(l)+' r='+str(r))
      total += N-r
    else:
      l=-1
      r = N
      while l+1 < r:
        c = (l+r)//2
        if(A[c]*A[i]<mid):
          l=c
        else:
          r=c
        #print(str(i)+'[p] l='+str(l)+' r='+str(r))
      total += r
    if(A[i]*A[i] < mid):
      total-=1
  total = total//2
  #print('total = '+str(total))
  return total < K

low = -1000000000000000000
high = 1000000000000000000
while low+1 < high:
  mid = (low + high) // 2
  ok = num_search(low,high,mid)
  #print(str(low)+' '+str(high))
  if(ok):
    low = mid
  else:
    high = mid
print(low)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
nega=[i for i in a if i<0]
zera=[i for i in a if i==0]
posa=[i for i in a if i>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  
  for i in posa:
    y+=len([j for j in a if j*i<=x])
  
  for i in nega:
    y+=len([j for j in a if j*i<=x])
  
  y-=len([j for j in a if j*j<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]

#積がx以下になる組み合わせの数
def f(x):
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            ret+=g2(pA,na,x)*2
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        for a in A:
            if a<0:
                ret+=g2(A,a,x)-(1 if a*a<=x else 0)
            else:
                ret+=g1(A,a,x)-(1 if a*a<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=len(L)
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=len(L)-1
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
nega=[i for i in a if i<0]
zera=[i for i in a if i==0]
posa=[i for i in a if i>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  
  for i in posa:
    y+=len([j for j in a if j*i<=x])
  
  y+=n*len(nega)
  
  for i in nega:
    y-=len([j for j in a if j*i>x])
  
  y-=len([j for j in a if j*j<=x])
  return y//2

r=10**18
l=-r-1
while r-l>1:
  c=(r+l)//2
  if cnt(c)>=k:
    r=c
  else:
    l=c
print(r)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            ret+=g2(pA,na,x)*2
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        pR=len(nA)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        pR=len(pA)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=pR
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    pR=over
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=pR
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    pR=r
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
A.sort()
plus = 0
minus = 0
zero = 0
plus_lis = []
minus_lis = []

for n in A:
	if n == 0:
		zero += 1
	elif n > 0:
		plus += 1
		plus_lis.append(n)
	else:
		minus += 1
		minus_lis.append(n)

plus, minus, zero = plus*(plus-1)//2+minus*(minus-1)//2, plus*minus, plus*zero+minus*zero+zero*(zero-1)//2

if K <= minus:  # 答えは負
	l = -10**18-1
	r = 0

	def count(x):  # xより小さいペアの数を返す
		total = 0
		idx = 0
		for i in range(len(plus_lis)):
			while idx < len(minus_lis):
				if plus_lis[i] * minus_lis[idx] < x:
					idx += 1
				else:
					total += idx
					break
			else:
				total += idx

		return total

	while l+1 != r:
		m = (l+r)//2
		if count(m) >= K:
			r = m
		else:
			l = m
	print(l)

elif minus <= K <= minus+zero:
	print(0)

else:  # 答えは正
	l = 0
	r = 10**18+1

	def count(x):  # xより小さいペアの数を返す
		total = minus+zero
		tmp = 0
		idx = 0

		### プラスとマイナスを別々に数え上げる
		for i in range(len(plus_lis))[::-1]:
			while idx < len(plus_lis):
				if plus_lis[i] * plus_lis[idx] < x:
					idx += 1
				else:
					tmp += idx
					break
			else:
				tmp += idx
			if plus_lis[i] * plus_lis[i] < x: tmp -= 1  # 重複してる分引く
		tmp //= 2
		total += tmp
		tmp = 0
		idx = 0 
		for i in range(len(minus_lis)):
			while idx < len(minus_lis):
				if minus_lis[i] * minus_lis[-idx-1] < x:
					idx += 1
				else:
					tmp += idx
					break
			else:
				tmp += idx
			if minus_lis[i] * minus_lis[i] < x: tmp -= 1
		tmp //= 2
		total += tmp

		return total

	while l+1 != r:
		m = (l+r)//2
		if count(m) >= K:
			r = m
		else:
			l = m
	print(l)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            ret+=g2(pA,na,x)
        pR=len(nA)-1
        for pa in pA:
            ret+=g2(nA,pa,x)
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        pR=len(nA)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        pR=len(pA)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=pR
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    pR=over
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=pR
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    pR=r
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Time Limit Exceeded

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

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()
  
  def count(l, r, a, x):
    while True:
      mid = (l+r)//2
      if a > 0:
        if r - l <=1:
          return r - (1 if a**2 <= x else 0)
        if a * As[mid] <= x:
          l = mid
        else:
          r = mid
      else:
        if r - l <=1:
          return n - r - (1 if a**2 <= x else 0)
        if a * As[mid] <= x:
          r = mid
        else:
          l = mid

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      tot = sum([count(-1, n, A, mid) for A in As]) // 2
      if tot < k:
        l = mid
      else:
        r = mid
  print(bs(MIN-1, MAX+1))
    
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=pL=0

#積がx以下になる組み合わせの数
def f(x):
    global pR,pL
    ret=0
    if x<0:
        pR=len(pA)
        for na in nA:
            ret+=g2(pA,na,x)
        pR=len(nA)
        for pa in pA:
            ret+=g2(nA,pa,x)
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        pR=len(nA)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        pR=len(pA)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=pR
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    pR=over
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    global pL
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=pR
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    pL=under
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left as bl

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

    inf = 10**18+1

    ok = -inf
    ng = inf
    start_0 = bl(a, 0)
    start_1 = bl(a, 1)

    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        if mid >= 0:
            now = 0
            if start_0 > 0:
                for i in a[start_0-1::-1]:
                    while now < n:
                        if i*a[now] >= mid:
                            now += 1
                        else:
                            break
                    cnt += n - now
            now = n
            for i in a[start_1:]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        else:
            now = 0
            for i in a[:start_0]:
                while now < n:
                    if i*a[now] >= mid:
                        now += 1
                    else:
                        break
                cnt += n - now
            now = n
            for i in a[n-1:start_1-1:-1]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        if mid > 0:
            cnt += n * (start_1 - start_0)
        cnt -= len([None for i in a if i*i < mid])
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Submission status: Time Limit Exceeded

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

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()
  
  def count(l, r, a, x):
    while True:
      mid = (l+r)//2
      if a > 0:
        if r - l <=1:
          return r - (1 if a**2 <= x else 0)
        if a * As[mid] <= x:
          l = mid
        else:
          r = mid
      else:
        if r - l <=1:
          return n - r - (1 if a**2 <= x else 0)
        if a * As[mid] <= x:
          r = mid
        else:
          l = mid

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      tot = 0
      for A in As:
        tot += count(-1, n, A, mid)
      tot //= 2
      if tot < k:
        l = mid
      else:
        r = mid
  print(bs(MIN-1, MAX+1))
    
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()
  
  def count(l, r, a, x):
    mid = (l+r)//2
    if a > 0:
      if r - l <=1:
        return r - (1 if a**2 <= x else 0)
      if a * As[mid] <= x:
        return count(mid, r, a, x)
      else:
        return count(l, mid, a, x)
    else:
      if r - l <=1:
        return n - r - (1 if a**2 <= x else 0)
      if a * As[mid] <= x:
        return count(l, mid, a, x)
      else:
        return count(mid, r, a, x)
      
  def bs(l, r):
    mid = (l+r) // 2
    if r - l <= 1:
      return r
    tot = 0
    for A in As:
      tot += count(-1, n, A, mid)
    tot //= 2
    if tot < k:
      return bs(mid, r)
    else:
      return bs(l, mid)
  print(bs(MIN-1, MAX+1))
    
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

MAX = 10**18
MIN = -MAX

import numpy as np

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()
  
  def count(l, r, a, x):
    mid = (l+r)//2
    if a > 0:
      if r - l <=1:
        return r - (1 if a**2 <= x else 0)
      if a * As[mid] <= x:
        return count(mid, r, a, x)
      else:
        return count(l, mid, a, x)
    else:
      if r - l <=1:
        return n - r - (1 if a**2 <= x else 0)
      if a * As[mid] <= x:
        return count(l, mid, a, x)
      else:
        return count(mid, r, a, x)
      
  def bs(l, r):
    mid = (l+r) // 2
    if r - l <= 1:
      return r
    tot = 0
    for A in As:
      tot += count(-1, n, A, mid)
    tot //= 2
    if tot < k:
      return bs(mid, r)
    else:
      return bs(l, mid)
  print(bs(MIN-1, MAX+1))
    
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

#積がx以下になる組み合わせの数
def f(x):
    ret=0
    if x<0:
        for na in nA:
            ret+=g2(pA,na,x)
        for pa in pA:
            ret+=g2(nA,pa,x)
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=len(L)
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=len(L)-1
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18+1
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Time Limit Exceeded

Solution code:
#大きな数の割り算は計算重いかも，for文内も二分探索に


import bisect
import sys
input = sys.stdin.readline

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

#積がX未満になるものがK-1個以下になる最大のXを探す

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

while abs(ng-ok)>1:
    X=(ok+ng)//2
    temp=0
    
    for i in range(N):
        if A[i]>0:
            #A[i]*A[j]がX未満となるjの個数を数える
            l=-1
            r=N
            while r-l>1:
                med=(l+r)//2
                if A[i]*A[med]<X:
                    l=med
                else:
                    r=med
            temp+=r

        elif A[i]<0:
            #A[i]*A[j]がX未満となるjの個数を数える
            l=-1
            r=N
            while r-l>1:
                med=(l+r)//2
                if A[i]*A[med]<X:
                    r=med
                else:
                    l=med
            temp+=N-r
            
        else:
            if X>0:
                temp+=N
        if A[i]*A[i]<X:
            temp-=1
            
    temp=temp//2
    #print(ok,X,ng,temp)
    #print("---")
    
    if temp>=K:
        ng=X
    else:
        ok=X

print(ok)

Submission status: Time Limit Exceeded

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

result = []
for i in range(len(A)):
    for o in range(i+1,len(A)):
        if i != o:
            result.append(A[i] * A[o])
print(sorted(result)[K - 1])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
plst = []
nlst = []
p = 0
z = 0
n = 0
for i in map(int,input().split()):
    if i > 0:
        p += 1
        plst.append(i)
    elif i == 0:
        z += 1
    else:
        n += 1
        nlst.append(i)
plst.sort()
nlst.sort()
zp = (p+n)*z + z*(z-1)//2
np = p*n
if K <= np:
    l = -10**18-1
    r = 0
    while l+1 < r:
        m = (l+r)//2
        total = 0
        idx = 0
        for i in range(p):
            while idx < n:
                if plst[i] * nlst[idx] < m:
                    idx += 1
                else:
                    total += idx
                    break
            else:
                total += idx
        if total < K:
            l = m
        else:
            r = m
    ans = l
elif K <= np+zp:
    ans = 0
else:
    l = 0
    r = 10**18+1
    while l+1 < r:
        m = (l+r)//2
        total = np+zp
        tmp = 0
        idx = 0
        for i in range(p)[::-1]:
            while idx < p:
                if plst[i] * plst[idx] < m:
                    idx += 1
                else:
                    tmp += idx
                    break
            else:
                tmp += idx
            if plst[i] * plst[i] < m: tmp -= 1
        tmp //= 2
        total += tmp
        tmp = 0
        idx = 0 
        for i in range(n):
            while idx < n:
                if nlst[i] * nlst[-idx-1] < m:
                    idx += 1
                else:
                    tmp += idx
                    break
            else:
                tmp += idx
            if nlst[i] * nlst[i] < m: tmp -= 1
        tmp //= 2
        total += tmp
        if total < K:
            l = m      
        else:
            r = m
    ans = l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

#積がx以下になる組み合わせの数
def f(x):
    ret=0
    if x<0:
        for na in nA:
            ret+=g2(pA,na,x)
        for pa in pA:
            ret+=g2(nA,pa,x)
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=len(L)
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=len(L)-1
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**19
r=10**19
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)