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:
import sys
input=sys.stdin.readline
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
from bisect import bisect, bisect_left, bisect_right, insort_left
n,k=NM()
l=L()
hu=[-i for i in l if i<0]
sei=[i for i in l if i>0]
hu.sort()
sei.sort()
zero=l.count(0)
def f(mi):
    tmp=0
    if mi>=0:
        tmp+=len(hu)*len(sei)+zero*(len(hu)+len(sei))+zero*(zero-1)//2
        for i,j in enumerate(hu):
            tmp+=min(bisect_right(hu,mi//j),i)
        for i,j in enumerate(sei):
            tmp+=min(bisect_right(sei,mi//j),i)
    else:
        for i,j in enumerate(hu):
            tmp+=len(sei)-bisect_left(sei,(-mi+j-1)//j)
    if tmp>=k:
        return 1
    return 0
hi=10**18
lo=-10**18
while hi>=lo:
    mi=(hi+lo)//2
    if f(mi):
        hi=mi-1
    else:
        lo=mi+1
print(lo)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
INF=10**18+1
l=-INF
r=INF
 
def condition(x):
    tot=0
    for i in range(n):
        if(a[i]<0):
            ll=-1
            rr=n
            while(ll+1<rr):
                xx=(ll+rr)//2
                if(a[i]*a[xx]<x):
                    rr=xx
                else:
                    ll=xx
            tot+=n-rr
        else:
            ll=-1
            rr=n
            while(ll+1<rr):
                xx=(ll+rr)//2
                if(a[i]*a[xx]<x):
                    ll=xx
                else:
                    rr=xx
            tot+=rr
        if(a[i]*a[i]<x):tot-=1
    tot//=2
    return tot<k
 
while(l+1<r):
    x=(l+r)//2
    if(condition(x)):l=x
    else:r=x
print(l)

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:
from bisect import bisect, bisect_left

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = a[::-1]

ok, ng = -10**19, 10**19
while abs(ng-ok) > 1:
	x = (ng+ok)//2
	res = 0
	for c in a:
		if c*c < x:
			res -= 1
		if c == 0:
			if x > 0:
				res += n
		elif c > 0:
			#res += bisect(a, x/c - 1e-18)
			if c * a[0] >= x:
				pass
			else:
				l, r = 0, n
				while r-l > 1:
					y = (l+r)//2
					if a[y]*c < x:
						l = y
					else:
						r = y
				res += l+1
		else:
			#res += n - bisect(a, x/c + 1e-18)
			if c * b[0] >= x:
				pass
			else:
				l, r = 0, n
				while r-l > 1:
					y = (l+r)//2
					if b[y]*c < x:
						l = y
					else:
						r = y
				res += l+1
	res //= 2
	#print(x, res)
	if res < k:
		ok = x
	else:
		ng = x

print(ng-1)

Submission status: Time Limit Exceeded

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

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

MAX=max(abs(A[0]),abs(A[-1]))
OK=-MAX**2-1
NG=MAX**2+1

import bisect

while NG-OK>1:
    mid=(OK+NG)//2
    SC=0
    for i in range(N):
        if A[i]>0:
            x=bisect.bisect_left(A,-(-mid//A[i]))
            SC+=max(0,x-i-1)

        elif A[i]<0:
            x=bisect.bisect_right(A,mid//A[i])
            SC+=min(N-i-1,N-x)
        else:
            if mid>0:
                SC+=N-i-1
            else:
                SC+=0
                
        if SC>=K:
            NG=mid
            break
    else:
        OK=mid
        
print(OK)

Submission status: Time Limit Exceeded

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

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

MAX=max(abs(A[0]),abs(A[-1]))
OK=-MAX**2-1
NG=MAX**2+1

import bisect

while NG-OK>1:
    mid=(OK+NG)//2
    SC=0
    for i in range(N):
        if A[i]>0:
            x=bisect.bisect_left(A,-(-mid//A[i]))
            SC+=max(0,x-i-1)

        elif A[i]<0:
            x=bisect.bisect_right(A,mid//A[i])
            SC+=min(N-i-1,N-x)
        else:
            if mid>0:
                SC+=N-i-1
            else:
                SC+=0
                
        if SC>=K:
            NG=mid
            break
    else:
        OK=mid
        
print(OK)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.buffer.readline()

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

def evl(x):
    cnt = 0
    for i in range(n):
        if a[i] >= 0:
            l, r = -1, n
            while r-l > 1:
                mid = (l+r) // 2
                if x >= a[i] * a[mid]: l = mid
                else: r = mid
            cnt += max(0, l-i)
        else:
            l, r = -1, n
            while r-l > 1:
                mid = (l+r) // 2
                if x >= a[i] * a[mid]: r = mid
                else: l = mid
            cnt += n - max(i+1, r)
    return cnt >= k

r = 10**18+1
l = -r
while r-l > 1:
    x = (l+r) // 2
    if evl(x): r = x
    else: l = x
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline()

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

def evl(x):
    cnt = 0
    for i in range(n):
        if a[i] >= 0:
            l, r = -1, n
            while r-l > 1:
                mid = (l+r) // 2
                if x >= a[i] * a[mid]: l = mid
                else: r = mid
            cnt += max(0, l-i)
        else:
            l, r = -1, n
            while r-l > 1:
                mid = (l+r) // 2
                if x >= a[i] * a[mid]: r = mid
                else: l = mid
            cnt += n - max(i+1, r)
    return cnt >= k

r = 10**18*2
l = -r
while r-l > 1:
    x = (l+r) // 2
    if evl(x): r = x
    else: l = x
print(r)

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq
n,k = map(int, raw_input().split(' '))
es = map(int, raw_input().split(' '))
es.sort()


#-5     1 234567
#			  ^
#-5  -3 -2 -1 0 1 1 3 4 5 6 7
#
#   15 10 5 0 -5 -5 -15 -20 -25  
heap = []
for i in range(n-1):
	if es[i] >= 0:
		heapq.heappush(heap, (es[i] * es[i + 1], i, i + 1, +1))
	elif es[i] < 0:
		heapq.heappush(heap, (es[i] * es[n - 1], i, n - 1, -1))

while(k):
	v,i,j,delta = heapq.heappop(heap)
	
	jj = j+ delta
	
	if i < jj < n :  
		heapq.heappush(heap, (es[i]*es[jj],i,jj, delta))
	k-=1
print v

Submission status: Time Limit Exceeded

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

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

    minus = []
    plus = []
    zero = 0
    for a in A:
        if a > 0:
            plus.append(a)
        elif a < 0:
            minus.append(-a)
        else:
            zero += 1
    plus.sort()
    minus.sort()
    ok = -10 ** 18 - 1
    ng = 10 ** 18 + 1
    mid = 0
    while ng - ok > 1:
        cnt = 0
        if mid == 0:
            if len(plus) * len(minus) < K:
                ok = mid
            else:
                ng = mid
        elif mid > 0:
            for a in A:
                #if mid == 27:
                #    print(a, cnt)
                if a < 0:
                    j = bisect_left(minus, (mid-1) // (-a) + 1)
                    cnt += N - len(minus) + j
                    if a * a < mid:
                        cnt -= 1
                elif a == 0:
                    cnt += N - 1
                else:
                    j = bisect_left(plus, (mid-1) // a + 1)
                    cnt += N - len(plus) + j
                    #if mid == 27:
                    #    print(j, mid // a)
                    if a * a < mid:
                        cnt -= 1
            #print(cnt, mid)
            assert cnt%2 == 0
            cnt //= 2
            if cnt < K:
                ok = mid
            else:
                ng = mid
        else:
            for a in A:
                if a < 0:
                    j = bisect_left(plus, (-mid) // (-a) + 1)
                    cnt += len(plus) - j
                elif a > 0:
                    j = bisect_left(minus, (-mid) // a + 1)
                    cnt += len(minus) - j
            assert cnt %2 == 0
            cnt //= 2
            if cnt < K:
                ok = mid
            else:
                ng = mid
        mid = (ok+ng)//2

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

pl = []
mi = []
ze = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(x)
    else:
        ze += 1

p, m = len(pl), len(mi)
res1 = p * m
res2 = (p + m) * ze + ze * (ze - 1) // 2
if res1 >= k:
    pl.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        tmp = 0
        for mm in mi:
            mm = abs(mm)
            y = -(-x // mm)
            tmp += p - bisect.bisect_left(pl, y)

        if tmp < k:
            r = x
        else:
            l = x
    print(-l)

elif res1 + res2 >= k:
    print(0)
else:
    k = k - res1 - res2
    pl.sort()
    mi = [abs(mi[i]) for i in range(m)]
    mi.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        tmp = 0
        for i in range(p):
            y = x // pl[i]
            tmp += max(0, bisect.bisect_right(pl, y) - i - 1)
        for i in range(m):
            y = x // mi[i]
            tmp += max(0, bisect.bisect_right(mi, y) - i - 1)

        if tmp < k:
            l = x
        else:
            r = x
    print(r)

Submission status: Time Limit Exceeded

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

pl = []
mi = []
ze = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(x)
    else:
        ze += 1

p, m = len(pl), len(mi)
res1 = p * m
res2 = (p + m) * ze + ze * (ze - 1) // 2
if res1 >= k:
    pl.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        tmp = 0
        for mm in mi:
            mm = abs(mm)
            y = -(-x // mm)
            tmp += p - bisect.bisect_left(pl, y)

        if tmp < k:
            r = x
        else:
            l = x
    print(-l)

elif res1 + res2 >= k:
    print(0)
else:
    k = k - res1 - res2
    pl.sort()
    mi = [abs(mi[i]) for i in range(m)]
    mi.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        tmp = 0
        for i in range(p):
            y = x // pl[i]
            tmp += max(0, bisect.bisect_right(pl, y) - i - 1)
        for i in range(m):
            y = x // mi[i]
            tmp += max(0, bisect.bisect_right(mi, y) - i - 1)

        if tmp < k:
            l = x
        else:
            r = x
    print(r)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

num=itertools.combinations(a,2)
by=[]

for i in list(num):
  by.append(i[0]*i[1])
  
by.sort()
print(by[k-1])

Submission status: Time Limit Exceeded

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

posilist=[]
negalist=[]
zeronum=0

for a in alist:
    if a == 0:
        zeronum+=1
    elif a > 0:
        posilist.append(a)
    else:
        negalist.append(-a)
posilist.sort()
negalist.sort()

posinum=len(posilist)
neganum=len(negalist)

def shakutori(x,alist,blist,flag):
    sum=0
    alen=len(alist)
    blen=len(blist)

    a=0
    b=blen-1

    while a <= alen-1 and b >= 0:
        if flag and a == b:
            return sum
        if alist[a]*blist[b] <= x:
            if flag:
            	sum+= (b+1)-(a+1)
            else:
            	sum+= (b+1)
            a += 1
        else:
            b -=1
    return sum

if k <= posinum*neganum:
    k=posinum*neganum+1-k
    pnflag=False
elif k > n*(n-1)/2-posinum*(posinum-1)/2-neganum*(neganum-1)/2:
    k=k-(n*(n-1)/2-posinum*(posinum-1)/2-neganum*(neganum-1)/2)
    pnflag=True
else:
    print(0)
    sys.exit()

llim=0
ulim=10**19+1


while True:
    mid=(llim+ulim)//2
    if pnflag:
        d1=shakutori(mid,posilist,posilist,True)+shakutori(mid,negalist,negalist,True)
        d2=shakutori(mid+1,posilist,posilist,True)+shakutori(mid+1,negalist,negalist,True)
    else:
        d1=shakutori(mid,posilist,negalist,False)
        d2=shakutori(mid+1,posilist,negalist,False)
    if d1 < k <= d2:
        if pnflag:
            print(mid+1)
        else:
            print(-(mid+1))
        sys.exit()
    elif k <= d1:
        ulim = mid
    else:
        llim = mid

Submission status: Time Limit Exceeded

Solution code:
N,K,*A = map(int, open(0).read().split())
Ap = []
An = []
Az = []
for c in A:
  if c>0:
    Ap.append(c)
  elif c<0:
    An.append(c)
  else:
    Az.append(c)
l = -10**20
r = 10**20
Ap.sort(reverse=True)
An.sort()
while l+1<r:
  s = (l+r)//2
  cnt = 0
  j = len(Ap)-1
  for i in range(len(Ap)):
    while j>-1 and Ap[i]*Ap[j]<s:
      j -= 1
    cnt += len(Ap)-1-j
  for i in range(len(Ap)):
    if Ap[i]*Ap[i]<s:
      cnt -= 1
  j = len(An)-1
  for i in range(len(An)):
    while j>-1 and An[i]*An[j]<s:
      j -= 1
    cnt += len(An)-1-j
  for i in range(len(An)):
    if An[i]*An[i]<s:
      cnt -= 1
  cnt //= 2
  if s>0:
    cnt += len(Az)*(len(Az)-1)//2 + len(Az)*(len(Ap)+len(An)) + len(Ap)*len(An)
  else:
    j = 0
    for i in range(len(Ap)-1,-1,-1):
      while j<len(An) and Ap[i]*An[j]<s:
        j += 1
      cnt += j
  if cnt>=K:
    r = s
  else:
    l = s
print(l)

Submission status: Time Limit Exceeded

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

import sys
from heapq import heapify, heappop, heappush, heappushpop

def main():
    N, K = map(int, input().split())
    A = list(map(int,input().split()))
    A.sort()
    M = []
    P = []
    Z = []
    for i in A:
        if i<0:
            M.append(i)
        elif i>0:
            P.append(i)
        else:
            Z.append(i)
    Ml, Zl, Pl = len(M), len(Z), len(P)
    if K <= Ml*Pl:
        #答えがマイナス
        hp = []
        heapify(hp)
        tp = (1, 1)
        heappush(hp, (M[tp[0]-1]*P[-tp[1]],)+tp)
        hist = {tp}
        for k in range(K):
        #最下位をpop
            rec = heappop(hp)
        # 次の順位を登録する
        # Mを次の配列
            tp = (rec[1]+1, rec[2])
            if tp[0]<=Ml and not tp in hist:
                heappush(hp, (M[tp[0]-1]*P[-tp[1]],)+tp)
                hist.add(tp)
        # Pを次の配列
            tp = (rec[1], rec[2]+1)
            if tp[1]<=Pl and not tp in hist:
                heappush(hp, (M[tp[0]-1]*P[-tp[1]],)+tp)
                hist.add(tp)
        print(rec[0])

    elif K<=Ml * Pl + Zl * (N-Zl) + Zl * (Zl-1)//2:
        #答えがzero
        print(0)
    else:
        K -= Ml * Pl + Zl * (N-Zl) + Zl * (Zl-1)//2
        #答えがプラス
        hp = []
        heapify(hp)

        hist = set()
        if Ml>=2:
            tp = (1, 2, 0)
            heappush(hp, (M[-tp[0]]*M[-tp[1]],)+tp)
            hist.add(tp)
        if Pl>=2:
            tp = (1, 2, 1)
            heappush(hp, (P[tp[0]-1]*P[tp[1]-1],)+tp)
            hist.add(tp)
        rec = 0
        for k in range(K-1):
        #最下位をpop
            rec = heappop(hp)
        # 次の順位を登録する
        # Mを次の配列
            if rec[3] == 0: #Mの場合
                tp = (rec[1]+1, rec[2], rec[3])
                if (not tp in hist) and tp[0]<tp[1]:
                    heappush(hp, (M[-tp[0]]*M[-tp[1]],)+tp)
                    hist.add(tp)
                tp = (rec[1], rec[2]+1, rec[3])
                if (not tp in hist) and tp[1]<=Ml:
                    heappush(hp, (M[-tp[0]]*M[-tp[1]],)+tp)
                    hist.add(tp)
        # Pを次の配列
            if rec[3] == 1: #Mの場合
                tp = (rec[1]+1, rec[2], rec[3])
                if (not tp in hist) and tp[0]<tp[1]:
                    heappush(hp, (P[tp[0]-1]*P[tp[1]-1],)+tp)
                    hist.add(tp)
                tp = (rec[1], rec[2]+1, rec[3])
                if (not tp in hist) and tp[1]<=Pl:
                    heappush(hp, (P[tp[0]-1]*P[tp[1]-1],)+tp)
                    hist.add(tp)
        rec = heappop(hp)
        print(rec[0])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

from queue import PriorityQueue

que = PriorityQueue()

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

for i in range(n):
    for j in range(i+1,n):
        que.put(a[i]*a[j])

for _ in range(k-1):
    que.get()
    
print(que.get())

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import deque

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

negs=[]
poss=[]
zers=[]
for i in range(n):
    if A[i]<0:
        negs.append(A[i])
    elif A[i]>0:
        poss.append(A[i])
    else: zers.append(A[i])

pairedpos=len(negs)*(len(negs)-1)//2+len(poss)*(len(poss)-1)//2
pairedneg=len(negs)*len(poss)
pairedzero=(len(negs)+len(poss))*len(zers)+len(zers)*(len(zers)-1)//2

ans=0
flg=0
if k<=pairedneg:
    flg=1
elif pairedneg<k<=pairedneg+pairedzero:
    ans=0
else: flg=2 

if flg==1:
    higher=0
    lower=-10**18
    for _ in range(60):
        cnt=0
        mid=(higher+lower)//2
        for i in range(len(poss)):
            idx=bisect_left(negs, -(-mid//poss[i]))
            cnt+=idx
        if cnt<=k-1:
            lower=mid
        else:
            higher=mid
    ans=lower

elif flg==2:
    from copy import deepcopy
    lower=0
    higher=10**18
    nnegs=[-negs[i] for i in range(len(negs))]
    nnegs=sorted(nnegs)
    nnegs=deque(nnegs)
    poss=deque(poss)
    for _ in range(60):
        newnegs=deepcopy(nnegs)
        possc=deepcopy(poss)
        cnt=0
        mid=(higher+lower)//2
        while newnegs:
            nn=newnegs.popleft()
            idx1=bisect_left(newnegs, -(-mid//nn))
            cnt+=idx1
        while possc:
            pp=possc.popleft()
            idx2=bisect_left(possc, -(-mid//pp))
            cnt+=idx2
        if cnt<=(k-pairedneg-pairedzero)-1:
            lower=mid
        else:
            higher=mid
    ans=lower
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import deque

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

negs=[]
poss=[]
zers=[]
for i in range(n):
    if A[i]<0:
        negs.append(A[i])
    elif A[i]>0:
        poss.append(A[i])
    else: zers.append(A[i])

pairedpos=len(negs)*(len(negs)-1)/2+len(poss)*(len(poss)-1)/2
pairedneg=len(negs)*len(poss)
pairedzero=(len(negs)+len(poss))*len(zers)+len(zers)*(len(zers)-1)/2

ans=0
flg=0
if k<=pairedneg:
    flg=1
elif pairedneg<k<=pairedneg+pairedzero:
    ans=0
else: flg=2 

if flg==1:
    higher=0
    lower=-(1e+9)**2+1
    for _ in range(60):
        cnt=0
        mid=int((higher+lower)//2)
        for i in range(len(poss)):
            idx=bisect_left(negs, -(-mid//poss[i]))
            cnt+=idx
        if cnt<=k-1:
            lower=mid
        else:
            higher=mid
    ans=lower

elif flg==2:
    from copy import deepcopy
    lower=0
    higher=(1e+9)**2+1
    nnegs=[-negs[i] for i in range(len(negs))]
    nnegs=sorted(nnegs)
    nnegs=deque(nnegs)
    poss=deque(poss)
    for _ in range(60):
        newnegs=deepcopy(nnegs)
        possc=deepcopy(poss)
        cnt=0
        mid=int((higher+lower)//2)
        while newnegs:
            nn=newnegs.popleft()
            idx1=bisect_left(newnegs, -(-mid//nn))
            cnt+=idx1
        while possc:
            pp=possc.popleft()
            idx2=bisect_left(possc, -(-mid//pp))
            cnt+=idx2
        if cnt<=(k-pairedneg-pairedzero)-1:
            lower=mid
        else:
            higher=mid
    ans=lower
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import deque

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

negs=[]
poss=[]
zers=[]
for i in range(n):
    if A[i]<0:
        negs.append(A[i])
    elif A[i]>0:
        poss.append(A[i])
    else: zers.append(A[i])

pairedpos=len(negs)*(len(negs)-1)/2+len(poss)*(len(poss)-1)/2
pairedneg=len(negs)*len(poss)
pairedzero=(len(negs)+len(poss))*len(zers)+len(zers)*(len(zers)-1)/2

ans=0
flg=0
if k<=pairedneg:
    flg=1
elif pairedneg<k<=pairedneg+pairedzero:
    ans=0
else: flg=2 

if flg==1:
    higher=0
    lower=-(1e+9)**2+1
    for _ in range(60):
        cnt=0
        mid=int((higher+lower)//2)
        for i in range(len(poss)):
            idx=bisect.bisect_left(negs, -(-mid//poss[i]))
            cnt+=idx
        if cnt<=k-1:
            lower=mid
        else:
            higher=mid
    ans=lower

elif flg==2:
    from copy import deepcopy
    lower=0
    higher=(1e+9)**2+1
    nnegs=[-negs[i] for i in range(len(negs))]
    nnegs=sorted(nnegs)
    nnegs=deque(nnegs)
    poss=deque(poss)
    for _ in range(60):
        newnegs=deepcopy(nnegs)
        possc=deepcopy(poss)
        cnt=0
        mid=int((higher+lower)//2)
        while newnegs:
            nn=newnegs.popleft()
            idx1=bisect.bisect_left(newnegs, -(-mid//nn))
            cnt+=idx1
        while possc:
            pp=possc.popleft()
            idx2=bisect.bisect_left(possc, -(-mid//pp))
            cnt+=idx2
        if cnt<=(k-pairedneg-pairedzero)-1:
            lower=mid
        else:
            higher=mid
    ans=lower
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
import sys
hu=[i for i in A if i<0]
sei=[i for i in A if i>0]
zero=[i for i in A if i==0]
C=[]
for i in hu:
    for j in sei:
        C.append(i*j)
if len(C)>=K:
    print(sorted(C)[K-1])
    sys.exit()
for i in (sei+hu):
    for j in zero:
        C.append(0)
if len(C)>=K:
    print(sorted(C)[K-1])
    sys.exit()
for k in [zero,hu,sei]:
    for i in range(len(k)):
        for j in range(i+1,len(k)):
            C.append(k[i]*k[j])
if len(C)>=K:
    print(sorted(C)[K-1])
    sys.exit()

Submission status: Time Limit Exceeded

Solution code:
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
from itertools import combinations as c
C=[]
for i in c(A,2):
    C.append(i[0]*i[1])
print(sorted(C)[K-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
#import bisect# lower_bound etc
import numpy as np
def run():
    N, K, *A = list(map(int, read().split()))
    B = [a for a in A if a>0]
    C = [a for a in A if a<0]
    C_abs = [-c for c in C]
    O = A.count(0)
    B = np.array(sorted(B), dtype= np.int64)
    C = np.array(sorted(C), dtype = np.int64)
    C_abs = np.array(sorted(C_abs), dtype = np.int64)
    n_neg = len(B) * len(C)
    n_0 = O * (O - 1) // 2 + O * (len(B) + len(C))

    def find(x):
        ret = 0
        if x < 0:
            ret += np.searchsorted(C, x//B, side='right').sum()

        elif x == 0:
            ret += n_0 + n_neg
        else:
            ret += n_neg + n_0
            b_count = 0
            for b in B:
                if b ** 2 <= x:
                    b_count += 1
            c_count = 0
            for c in C_abs:
                if c ** 2 <= x:
                    c_count += 1
            ret += (np.searchsorted(B, x//B, side='right').sum() - b_count) // 2

            ret += (np.searchsorted(C_abs, x//C_abs, side='right').sum() - c_count) // 2
        return ret





    high = 10 ** 18
    low = -high
    current = 0
    while high - low > 1:
        tmp = find(current)
        if tmp < K:
            low = current
        else:
            high = current

        current = (low + high) // 2

    print(high)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
#import bisect# lower_bound etc
import numpy as np
def run():
    N, K, *A = list(map(int, read().split()))
    B = [a for a in A if a>0]
    C = [a for a in A if a<0]
    C_abs = [-c for c in C]
    O = A.count(0)
    B = sorted(B)
    C = sorted(C)
    C_abs = sorted(C_abs)
    n_neg = len(B) * len(C)
    n_0 = O * (O - 1) // 2 + O * (len(B) + len(C))

    def find(x):
        ret = 0
        if x < 0:
            for b in B:
                ret += np.searchsorted(C, x//b, side='right')

        elif x == 0:
            ret += n_0 + n_neg
        else:
            ret += n_neg + n_0
            for i, b in enumerate(B):
                ret += np.searchsorted(B[i+1:], x//b, side='right')

            for i, c in enumerate(C_abs):
                ret += np.searchsorted(C_abs[i+1:], x//c, side='right')
        return ret





    high = 10 ** 18
    low = -high
    current = 0
    while high - low > 1:
        tmp = find(current)
        if tmp < K:
            low = current
        else:
            high = current

        current = (low + high) // 2

    print(high)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
#import bisect# lower_bound etc
def run():
    N, K, *A = list(map(int, read().split()))
    B = [a for a in A if a>0]
    C = [a for a in A if a<0]
    C_abs = [-c for c in C]
    O = A.count(0)
    B = sorted(B)
    C = sorted(C)
    C_abs = sorted(C_abs)
    n_neg = len(B) * len(C)
    n_0 = O * (O - 1) // 2 + O * (len(B) + len(C))

    def find(x):
        ret = 0
        if x < 0:
            for b in B:
                ret += upper_bound(C, x, b)

        elif x == 0:
            ret += n_0 + n_neg
        else:
            ret += n_neg + n_0
            for i, b in enumerate(B):
                ret += upper_bound(B[i+1:], x, b)

            c_val = 0
            for i, c in enumerate(C_abs):
                ret += upper_bound(C_abs[i+1:], x, c)
        return ret

    def upper_bound(arr, x, prod):
        low = 0
        high = len(arr)
        if arr == []:
            return 0
        if arr[0] * prod > x:
            return 0
        while high - low > 1:
            current = (high + low) // 2
            tmp = arr[current] * prod
            if tmp > x:
                high = current
            else:
                low = current
        return high



    high = 10 ** 18
    low = -high
    current = 0
    while high - low > 1:
        tmp = find(current)
        if tmp < K:
            low = current
        else:
            high = current

        current = (low + high) // 2

    print(high)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
#import bisect# lower_bound etc
def run():
    N, K, *A = list(map(int, read().split()))
    B = [a for a in A if a>0]
    C = [a for a in A if a<0]
    C_abs = [-c for c in C]
    O = A.count(0)
    B = sorted(B)
    C = sorted(C)
    C_abs = sorted(C_abs)
    n_neg = len(B) * len(C)
    n_0 = O * (O - 1) // 2 + O * (len(B) + len(C))

    def find(x):
        ret = 0
        if x < 0:
            for b in B:
                ret += upper_bound(C, x, b)

        elif x == 0:
            ret += n_0 + n_neg
        else:
            ret += n_neg + n_0
            b_val = 0
            for i, b in enumerate(B):
                b_val += upper_bound(B[i+1:], x, b)

            c_val = 0
            for i, c in enumerate(C_abs):
                c_val += upper_bound(C_abs[i+1:], x, c)
            ret += (b_val + c_val)
        return ret

    def upper_bound(arr, x, prod):
        low = 0
        high = len(arr)
        if arr == []:
            return 0
        if arr[0] * prod > x:
            return 0
        while high - low > 1:
            current = (high + low) // 2
            tmp = arr[current] * prod
            if tmp > x:
                high = current
            else:
                low = current
        return high



    high = 10 ** 18
    low = -high
    current = 0
    while high - low > 1:
        tmp = find(current)
        if tmp < K:
            low = current
        if tmp >= K:
            high = current

        current = (low + high) // 2

    print(high)

if __name__ == "__main__":
    run()