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

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

A.sort()

hi = 10**18+1
lo = -10**18-1

def solve(N,K,A,hi,lo):
    
    while hi-lo > 1:
        mid = (hi+lo)//2
        under_mid = 0
    
        for a in A:
            if a == 0:
                if mid > 0:
                    under_mid += N
            elif a > 0:
                under_mid += bisect_left(A,-(-mid//a))
            else:
                under_mid += N-bisect_right(A,mid//a)
            if a**2 < mid:
                under_mid -= 1
        under_mid //= 2
    
        if under_mid < K:
            lo = mid
        else:
            hi = mid
    return lo

print(solve(N,K,A,hi,lo))

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]

A.sort()

# 積がx未満となる組み合わせの数を求める
def n_comb_lt(x):
    n_comb = 0
    for i in range(n - 1): # A[0], A[1], ..., A[n-2]について
        # i < jであるjのうち、A[i] * A[j] < xとなるjの数を求める
        if A[i] > 0:
            if A[i] * A[i + 1] >= x:
                n_partner = 0
            elif A[i] * A[n - 1] < x:
                n_partner = n - 1 - i
            else:
                ok = i + 1
                ng = n - 1

                # ok >= 1, ng <= 200000 - 1
                # log2(200000) < 18
                # for _ in range(18):
                while ng - ok > 1:
                    mid = (ng + ok) // 2
                    if A[i] * A[mid] < x:
                        ok = mid
                    else:
                        ng = mid
                n_partner = ok - i
        else:
            if A[i] * A[i + 1] < x:
                n_partner = n - 1 - i
            elif A[i] * A[n - 1] >= x:
                n_partner = 0
            else:
                ng = i + 1
                ok = n - 1
                # ok >= 1, ng <= 200000 - 1
                # log2(200000) < 18
                # for _ in range(18):
                while ok - ng > 1:
                    mid = (ng + ok) // 2
                    if A[i] * A[mid] < x:
                        ok = mid
                    else:
                        ng = mid
                n_partner = n - 1 - ng
        n_comb += n_partner

    return n_comb


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

while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid) < k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
a = raw_input()
n, k = a.split()
n = int(n)
k = int(k)
b = raw_input()
data = [int(one) for one in b.split()]
res = []
for i in range(len(data) - 1):
  for j in range(i+1, len(data)):
    res.append(data[i]*data[j])
res = sorted(res)
print(res[k-1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right

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

A.sort()

hi = 10**18+1
lo = -10**18-1

while hi-lo > 1:
    mid = (hi+lo)//2
    under_mid = 0

    for i in range(N):
        if A[i] == 0:
            if mid > 0:
                under_mid += N
        elif A[i] > 0:
            under_mid += bisect_left(A,-(-mid//A[i]))
        else:
            under_mid += N-bisect_right(A,mid//A[i])
        if A[i]*A[i] < mid:
            under_mid -= 1
    under_mid //= 2

    if under_mid < K:
        lo = mid
    else:
        hi = mid

print(lo)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#import sys; sys.stdin=open('input_file.txt')
#------------------------------------------
from bisect import bisect_left,bisect_right

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

A.sort()

hi = 10**18+1
lo = -10**18-1

while hi-lo > 1:
    mid = (hi+lo)//2
    under_mid = 0

    for i in range(N):
        if A[i] == 0:
            if mid > 0:
                under_mid += N
        elif A[i] > 0:
            under_mid += bisect_left(A,-(-mid//A[i]))
        else:
            under_mid += N-bisect_right(A,mid//A[i])
        if A[i]*A[i] < mid:
            under_mid -= 1
    under_mid //= 2

    if under_mid < K:
        lo = mid
    else:
        hi = mid

print(lo)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def nC2(n):
    return n * (n-1) // 2

n,k = get_nums_l()
aaa = get_nums_l()

negatives = []
zeros = 0
positives = []

for a in aaa:
    if a == 0:
        zeros += 1
    elif a > 0:
        positives.append(a)
    else:
        negatives.append(a)

# 絶対値小さい順
positives.sort()
negatives.sort(reverse=True)

len_positives = len(positives)
len_negatives = len(negatives)

p_zeros = zeros*(len_negatives+len_positives) + nC2(zeros)
p_positives = nC2(len_positives) + nC2(len_negatives)
p_negatives = len_positives * len_negatives

log(len_negatives, zeros, len_positives)
log(p_negatives, p_zeros, p_positives)

if p_negatives < k <= (p_negatives+p_zeros):
    print(0)
    exit()

if k <= p_negatives:
    # 負の場合
    nokori = k
    log("nokori", nokori)

    left = -1 * ((10**9)**2 + 1)
    right = -1

    # 積がcenter未満になるペアがnokori個未満になる最大のcenterを探す
    while left < right:
        center = (left+right+1) // 2
        log("center", center)

        left2 = len_positives-1
        right2 = len_negatives-1

        count = 0

        while right2 > 0 and positives[left2] * negatives[right2] < center:
            right2 -= 1
        
        log("right2", right2)

        while 0<=left2<len_positives and 0<=right2<len_negatives:
            log(positives[left2] * negatives[right2])
            if positives[left2] * negatives[right2] < center:
                count += len_negatives - right2
                left2 -= 1
            else:
                right2 += 1

        # left2 = len_positives-1
        # right2 = len_negatives-1

        # while left2 > 0 and positives[left2] * negatives[right2] < center:
        #     left2 -= 1
        # while right2 >= 0 and left2 < len_positives and (len_positives-left2 < len_negatives-right2):
        #     log(positives[left2] * negatives[right2])
        #     if positives[left2] * negatives[right2] < center:
        #         count += len_positives - left2
        #         right2 -= 1
        #     else:
        #         left2 += 1
        
        log("count", count)
        if count < nokori:
            left = center
        else:
            right = center - 1
    print(left)
    exit()

# 正の場合
nokori = k - p_negatives - p_zeros
log("nokori", nokori)

left = 1
right = (10**9)**2 + 1

# 積がcenter未満になるペアがnokori個未満になる最大のcenterを探す
while left < right:
    center = (left+right+1) // 2
    # log("center", center)

    left2 = 0
    right2 = len_positives-1

    count = 0

    while left2 < right2:
        if positives[left2] * positives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    left2 = 0
    right2 = len_negatives-1

    while left2 < right2:
        if negatives[left2] * negatives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1
    
    log("center", center, "count", count)

    if count < nokori:
        left = center
    else:
        right = center-1
print(left)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,k=map(int,input().split())
a=list(map(int, input().split()))
a=sorted(a)
mlist=[]
zlist=[]
plist=[]
for i in a:
  if i<0:
    mlist.append(i)
  elif i==0:
    zlist.append(i)
  else:
    plist.append(i)
mnum=len(mlist)
znum=len(zlist)
pnum=len(plist)
mans=mnum*pnum
zans=znum*(pnum+mnum)
if znum>=2:
  zans+=combinations_count(znum,2)
pans=0
if pnum>=2:
  pans+=combinations_count(pnum,2)
if mnum>=2:
  pans+=combinations_count(mnum,2)

if k<=mans:
  ans=[]
  for m in mlist:
    for p in plist:
      ans.append(m*p)
  ans=sorted(ans)
  print(ans[k-1])
elif k<=mans+zans:
  print(0)
else:
  k=k-(mans+zans)
  ans=[]
  for i in itertools.combinations(plist, 2):
    ans.append(i[0]*i[1])
  for i in itertools.combinations(mlist, 2):
    ans.append(i[0]*i[1])
  ans=sorted(ans)
  print(ans[k-1])

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:
    lower=0
    higher=(1e+9)**2+1
    nnegs=[-negs[i] for i in range(len(negs))]
    nnegs=sorted(nnegs)
    for _ in range(60):
        newnegs=deque(nnegs)
        possc=deque(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:
#!/usr/bin/env python3
import sys
INF = float("inf")


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

    A.sort()

    # 負数、 0数、 正数
    neg, zero, pos = [], [], []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a == 0:
            zero.append(a)
        else:
            pos.append(a)
    neg.sort()
    pos.sort()

    prod_neg = len(neg) * len(pos)
    prod_zero = len(zero) * (len(neg)+len(pos))+len(zero)*(len(zero)-1)//2
    prod_pos = len(neg)*(len(neg)-1)//2 + len(pos)*(len(pos)-1)//2
    # print(prod_neg, prod_zero, prod_pos)
    # print(prod_neg+prod_zero+prod_pos)
    # print(N*(N-1)//2)

    if prod_neg >= K:
        # 二分探索
        left = neg[0]*pos[-1]-1
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            # しゃくとり法
            counter = 0
            ns, ps = 0, 0
            for ns in range(len(neg)):
                while ps < len(pos) and neg[ns]*pos[ps] > mid:
                    ps += 1
                if ps == len(pos):
                    break
                counter += len(pos)-ps
            # print("{} in [{}, {}]  => {}".format(mid, left, right, counter))
            if counter < K:
                left = mid
            else:
                right = mid
        print(right)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        neg.sort(reverse=True)
        # 二分探索
        left = 0
        right = 0
        if len(neg) > 0:
            right = max(neg[-1]**2, right)
        if len(pos) > 0:
            right = max(pos[-1]**2, right)
        right += 1
        while right - left > 1:
            mid = (left + right)//2
            # しゃくとり法
            counter = 0
            start, end = 0, len(pos)-1
            # print("{} in [{}, {}]".format(mid, left, right))
            for start in range(len(pos)):
                while end >= start and pos[start]*pos[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
                # print("addA: ", end-start)
            start, end = 0, len(neg)-1
            for start in range(len(neg)):
                while end >= start and neg[start]*neg[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
                # print("addB: ", end-start)
            # print("counter: {}".format(counter))
            if counter < K-prod_neg-prod_zero:
                left = mid
            else:
                right = mid
        print(left)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
from copy import deepcopy

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:
    lower=0
    higher=(1e+9)**2+1
    nnegs=[-negs[i] for i in range(len(negs))]
    nnegs=sorted(nnegs)
    for _ in range(60):
        newnegs=deepcopy(nnegs)
        possc=deepcopy(poss)
        cnt=0
        mid=int((higher+lower)//2)
        while newnegs:
            nn=newnegs.pop()
            idx1=bisect.bisect_left(newnegs, -(-mid//nn))
            cnt+=idx1
        while possc:
            pp=possc.pop()
            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:
import bisect
from copy import deepcopy

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
    while abs(higher-lower)>1:
        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:
    lower=0
    higher=(1e+9)**2+1
    nnegs=[-negs[i] for i in range(len(negs))]
    nnegs=sorted(nnegs)
    for _ in range(60):
        newnegs=deepcopy(nnegs)
        possc=deepcopy(poss)
        cnt=0
        mid=int((higher+lower)//2)
        while newnegs:
            nn=newnegs.pop()
            idx1=bisect.bisect_left(newnegs, -(-mid//nn))
            cnt+=idx1
        while possc:
            pp=possc.pop()
            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:
import bisect
from copy import deepcopy

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
    while abs(higher-lower)>1:
        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:
    lower=0
    higher=(1e+9)**2+1
    nnegs=[-negs[i] for i in range(len(negs))]
    nnegs=sorted(nnegs)
    while abs(higher-lower)>1:
        newnegs=deepcopy(nnegs)
        possc=deepcopy(poss)
        cnt=0
        mid=int((higher+lower)//2)
        while newnegs:
            nn=newnegs.pop()
            idx1=bisect.bisect_left(newnegs, -(-mid//nn))
            cnt+=idx1
        while possc:
            pp=possc.pop()
            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=map(int,input().split())
a=list(map(int,input().split()))
#b1,b3はそれぞれ絶対値の大きい順に並ぶ
b1=sorted([i for i in a if i<0])
l1=len(b1)
b2=sorted([i for i in a if i==0])
l2=len(b2)
b3=sorted([i for i in a if i>0],reverse=True)
l3=len(b3)
def countk1(x,b11,b13):#x以下になるものの個数
    ret=0
    for i in range(l1):
        lx,rx=0,l3-1
        while lx+1<rx:
            if b13[(lx+rx)//2]*b11[i]<=x:
                lx=(lx+rx)//2
            else:
                rx=(lx+rx)//2
        if b13[rx]*b11[i]<=x:
            ret+=(rx+1)
        elif b13[lx]*b11[i]<=x:
            ret+=(lx+1)
    return ret

def countk2(x,b21,b23):
    #ここ数えすぎ
    ret=0
    for i in range(l1-1):
        lx,rx=i+1,l1-1
        while lx+1<rx:
            if b21[(lx+rx)//2]*b21[i]<=x:
                lx=(lx+rx)//2
            else:
                rx=(lx+rx)//2
        if b21[rx]*b21[i]<=x:
            ret+=(rx-i)
        elif b21[lx]*b21[i]<=x:
            ret+=(lx-i)
    for i in range(l3-1):
        lx,rx=i+1,l3-1
        while lx+1<rx:
            if b23[(lx+rx)//2]*b23[i]<=x:
                lx=(lx+rx)//2
            else:
                rx=(lx+rx)//2
        if b23[rx]*b23[i]<=x:
            ret+=(rx-i)
        elif b23[lx]*b23[i]<=x:
            ret+=(lx-i)
    return ret

if k<=l1*l3:
    l,r=b1[0]*b3[0],-1
    while l+1<r:
        if countk1((l+r)//2,b1,b3)>=k: #k以上、数が存在するかどうか
            r=(l+r)//2
        else:
            l=(l+r)//2
    if countk1(l,b1,b3)==k:
        print(l)
    else:
        print(r)
elif k<=l1*l3+l2*(l1+l3)+(l2*(l2-1))//2:
    print(0)
else:
    k-=(l1*l3+l2*(l1+l3)+(l2*(l2-1))//2)
    l=1
    if l1>=2 and l3<2:
        r=b1[0]*b1[1]
    elif l1<2 and l3>=2:
        r=b3[0]*b3[1]
    else:
        r=max(b1[0]*b1[1],b3[0]*b3[1])
    while l+1<r:
        if countk2((l+r)//2,sorted(b1,reverse=True),sorted(b3))>=k: #k以上、数が存在するかどうか
            r=(l+r)//2
        else:
            l=(l+r)//2
    if countk2(l,sorted(b1,reverse=True),sorted(b3))==k:
        print(l)
    else:
        print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

readline = sys.stdin.readline
N, K = map(int, readline().split())
A = sorted(map(int, readline().split()))


def f(x):
    '''
    x以下のペアの個数を返す
    '''
    # ペアの片方を固定してもう片方の個数を数える
    cnt = 0
    for i, a in enumerate(A):
        if a >= 0:
            left, right = i, N
        else:
            left, right = N, i

        while abs(right - left) > 1:
            mid = (left + right) // 2
            if a * A[mid] <= x:
                left = mid
            else:
                right = mid

        if a >= 0:
            cnt += (right - 1) - i
        else:
            cnt += (N - 1) - right

    return cnt


def main():
    INF = 10 ** 18 + 1
    left, right = -INF, INF
    while right - left > 1:
        mid = (left + right) // 2
        if f(mid) < K:
            left = mid
        else:
            right = mid
        # print(f'f({mid})= {f(mid)}')
        # print(f'{left=} {right=}')

    print(right)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

results = []
for i in range(N):
  for j in range(i+1, N):
    results.append(items[i]*items[j])
    
print(sorted(results)[K-1])

Submission status: Time Limit Exceeded

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

    A.sort()
    INF = 10**18 + 1

    # 「積がx未満となるペアの個数がK個未満」となる最大のxを求める
    l =  -INF  # OK
    r = INF  # NG

    # loop
    def loop():
        total = 0
        for i in range(N):
            if A[i] < 0:
                l = -1
                r = N
                while l < r - 1:
                    center = (l + r) // 2
                    if A[center] * A[i] < x:
                        r = center
                    else:
                        l = center
                total += N - r
            else:
                l = -1
                r = N
                while l < r - 1:
                    center = (l + r) // 2
                    if A[center] * A[i] < x:
                        l = center
                    else:
                        r = center
                total += r
            if A[i] * A[i] < x:
                total -= 1
        total /= 2
        return total < K
        
    while l < r - 1:
        x = (l + r) // 2
        if loop():
            l = x
        else:
            r = x
    print(l)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

    A.sort()
    INF = 10**18 + 1

    # 「積がx未満となるペアの個数がK個未満」となる最大のxを求める
    l =  -INF  # OK
    r = INF  # NG
    while l < r - 1:
        x = (l + r) // 2

        # loop
        def loop():
            total = 0
            for i in range(N):
                if A[i] < 0:
                    l = -1
                    r = N
                    while l < r - 1:
                        center = (l + r) // 2
                        if A[center] * A[i] < x:
                            r = center
                        else:
                            l = center
                    total += N - r
                else:
                    l = -1
                    r = N
                    while l < r - 1:
                        center = (l + r) // 2
                        if A[center] * A[i] < x:
                            l = center
                        else:
                            r = center
                    total += r
                if A[i] * A[i] < x:
                    total -= 1
            total /= 2
            return total < K
        if loop():
            l = x
        else:
            r = x
    print(l)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

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

def less(x):
    res = 0
    for i in range(N):
        e = A[i]
        if e < 0:
            d = x // e
            l = 0
            r = i
            while l != r:
                m = (l + r) // 2
                if A[m] <= d:
                    l = m + 1
                else:
                    r = m
            res += i - l
        elif e > 0:
            d = - (- x // e)
            l = 0
            r = i
            while l != r:
                m = (l + r) // 2
                if A[m] < d:
                    l = m + 1
                else:
                    r = m
            res += l
        elif x > 0:
            res += i
    return res

l = - (10 ** 18 + 1)
r = - l
while l + 1 < r:
    m = (l + r) // 2
    if less(m) < K:
        l = m
    else:
        r = m
print(l)

Submission status: Time Limit Exceeded

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

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

def less(x):
    res = 0
    for i in range(N):
        e = A[i]
        if e < 0:
            res += i - bisect_right(A, x // e, 0, i)
        elif e > 0:
            res += bisect_left(A, - (- x // e), 0, i)
        elif x > 0:
            res += i
    return res

l = - (10 ** 18 + 1)
r = - l
while l + 1 < r:
    m = (l + r) // 2
    if less(m) < K:
        l = m
    else:
        r = m
print(l)

Submission status: Time Limit Exceeded

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

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

def less(x):
    res = 0
    for i in range(N):
        e = A[i]
        if e < 0:
            res += i - bisect_right(A, x // e, 0, i)
        elif e > 0:
            res += bisect_left(A, - (- x // e), 0, i)
        elif x > 0:
            res += i
    return res

l = - (10 ** 18 + 1)
r = - l
while l + 1 < r:
    m = (l + r) // 2
    if less(m) < K:
        l = m
    else:
        r = m
print(l)

Submission status: Time Limit Exceeded

Solution code:
S = input()
SS = input()

L = list(S.split())
A = list(SS.split()) 
N = L[0]
K = int(L[1])
# S = list(int, input().split())
# A = list(int, input().split())

M = len(A) - 1
O = []

for i in range(M):
    if i + 1 > M:
        continue
    for j in range(M):
        if j + 1 > M or j < i:
            continue
        e = int(A[i]) * int(A[j + 1])
        O.append(e)

O.sort()

print(O[K-1])

Submission status: Time Limit Exceeded

Solution code:
NandK = input()
NandK = NandK.split(' ')
N = int(NandK[0]) ; K = int(NandK[1])
anslist = []
A = input()
A = A.split(' ')
for k in range(len(A)):
    for j in range(k+1, len(A)):
        anslist.append(int(A[k]) * int(A[j]))
anslist.sort()
print(anslist[K-1])

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    ans = - 10**18

    from bisect import bisect_left, bisect_right


    N, K = LMIIS()
    A = LMIIS()
    A.sort()
    num_negative = bisect_left(A,0)
    num_zero = bisect_right(A,0) - num_negative
    num_positive = N - num_negative - num_zero
    B = A[:num_negative]
    

    
    inf = 10**18+1
    u = inf
    l = -inf
    # 答えが負
    if num_negative * num_positive >= K:
        def f(x):
            ans = 0
            for i in range(num_negative):
                for j in range(N-1,num_negative+num_zero-1,-1):
                    if A[i]*A[j] < x:
                        ans += 1
                    else:
                        break
            return ans
        # prev = m = (u+l)//2
        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if f(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        print(max_m)
        return m

    # 答えがゼロ
    elif num_negative * num_positive + num_negative * num_zero + num_positive * num_zero + num_zero*(num_zero-1)//2 >= K:
        print(0)
        return

    # 答えが正
    else:
        K-=num_negative * num_positive + num_negative * num_zero + num_positive * num_zero + num_zero*(num_zero-1)//2
        def f(x):
            ans = 0
            for i in range(num_negative-1,0,-1):
                for j in range(i-1,-1,-1):
                    
                    if A[i]*A[j] < x:
                        ans += 1
                    else:
                        break
            for i in range(num_negative+num_zero,N-1):
                for j in range(i+1,N):
                    if A[i]*A[j] < x:
                        ans += 1
                    else:
                        break
            return ans
        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            fm = f(m)
            if fm >= K:
                u = m
            else:
                max_m = max(max_m,m)
                l = m
        print(max_m)
        return
        




if __name__ == '__main__':
    main()