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: Runtime Error

Solution code:
import numpy as np

from bisect import bisect

DEBUG = False


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

A = np.array(A, dtype=np.int64)
A.sort()
neg = A[A < 0]
zero = A[A == 0]
pos = A[A > 0]

# Only keep the abs value of the negatives and flip so it's sorted
revAbsNeg = np.flip(-neg)


def countDistinctPairsLessThan(arr, prod):
    # Given a sorted array find the number of distinct pairs that are < prod
    # O(N * log(N)) where N = len(arr)

    N = arr.shape[0]
    assert arr.shape == (N,)
    count3 = np.sum(
        np.minimum(np.arange(N), np.searchsorted(arr, (prod - 1) // arr, side="right"))
    )

    if DEBUG:
        count = 0
        for i, x in enumerate(arr):
            count += bisect(arr, (prod - 1) // x, 0, i)

        count2 = 0
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                if arr[i] * arr[j] < prod:
                    count2 += 1
        assert count == count2 == count3
    return count3


def countPairsLessThanOrEqual(arr1, arr2, prod):
    # Given two sorted arrays containing *positive* numbers only,
    # find the number of pairs between the two arrays that are <= prod
    # O(N * log(M)) where N = len(arr1), M = len(arr2)
    if len(arr1) > len(arr2):
        arr1, arr2 = arr2, arr1

    count3 = np.sum(np.searchsorted(arr2, prod // arr1, side="right"))

    if DEBUG:
        count = 0
        for x in arr1:
            count += bisect(arr2, prod // x)
        count2 = 0
        for x in arr1:
            for y in arr2:
                if x * y <= prod:
                    count2 += 1
        assert count == count2 == count3
    return count3


def getIndex(prod):
    # Count number of pairs strictly less than prod
    count = 0
    if prod < 0:
        # All negatives except for the negatives with abs value less than or equal -prod
        count += len(pos) * len(neg)
        count -= countPairsLessThanOrEqual(pos, revAbsNeg, -prod)
    elif prod >= 0:
        # All negatives
        count += len(pos) * len(neg)
        if prod > 0:
            # All zeroes
            count += len(zero) * len(neg)
            count += (len(zero) * (len(zero) - 1)) // 2
            count += len(zero) * len(pos)
            # Positives with positives
            count += countDistinctPairsLessThan(pos, prod)
            # Negatives with negatives
            count += countDistinctPairsLessThan(revAbsNeg, prod)

    if DEBUG:
        count2 = 0
        for i in range(N):
            for j in range(i + 1, N):
                if A[i] * A[j] < prod:
                    count2 += 1
        assert count == count2
    return count


def bisect_f(f, lo, hi):
    if DEBUG:
        assert f(lo) and not f(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if f(mid):
            lo = mid
        else:
            hi = mid
        if DEBUG:
            assert f(lo) and not f(hi)
    if DEBUG:
        assert hi - lo == 1
        assert f(lo) and not f(hi)
    return lo


def solve(K):
    lo = -10 ** 18
    hi = 10 ** 18 + 1
    if DEBUG:
        assert getIndex(lo) <= K < getIndex(hi)
    prod = bisect_f(lambda prod: getIndex(prod) <= K, lo, hi)
    if DEBUG:
        assert getIndex(prod) <= K < getIndex(prod + 1)
    return prod


if DEBUG:
    for k in range((N * (N - 1)) // 2):
        print("k", k, solve(k))

print(solve(K - 1))  # K is 1-indexed

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = tuple(map(int, input().split()))
a.sort()


def check(x):
    # k番目の数がx以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    for i, ai in enumerate(a):
        if ai > 0:
            idx = bisect_right(a, x // ai)
            cnt += max(idx - i - 1, 0)
        elif ai < 0:
            idx = bisect_left(a, -(x // abs(ai)))
            # cnt += n - idx
            cnt += n - max(idx, i + 1)
        else:
            # ai == 0
            if x >= 0:
                cnt += n - i - 1

        if cnt >= k:
            return True
    # print('check', x, cnt)
    return cnt >= k


lb = -10**18  # False
ub = +10**18  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    # print(lb, ub)
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Submission status: Runtime Error

Solution code:
import itertools

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

print(sorted(list(combi[0]*combi[1] for combi in itertools.combinations(A,2)))[K])

Submission status: Runtime Error

Solution code:
import heapq

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

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

A.sort()

index_left=bisect.bisect_left(A,0)
index_right=bisect.bisect_right(A,0)

n_plus=n-index_right
n_minus=index_left

P=A[-n_plus:]
M=A[:n_minus]

S=[]
heapq.heapify(S)
ANS=[]

def get_count(lim):
    c=0
    for i in range(len(P)-1):
        for j in range(i+1,len(P)):
            if P[i]*P[j]<=lim:
                c+=1
    for i in range(len(M)-1):
        for j in range(i+1,len(M)):
            if M[i]*M[j]<=lim:
                c+=1
    return c

if k<=n_plus*n_minus:
    cnt=0
    heapq.heappush(S,(P[-1]*M[0],-1,0))
    while cnt<=k:
        s,p,m=heapq.heappop(S)
        m+=1
        if m<len(M):
            heapq.heappush(S,(P[p]*M[m],p,m))
        m-=1
        p-=1
        if p>=-1*len(P):
            heapq.heappush(S,(P[p]*M[m],p,m))
        cnt+=1
        ANS.append(s)
    print(ANS[k-1])
    
    
elif k<=n*(n-1)//2-(n_plus*(n_plus-1)//2)-(n_minus*(n_minus-1)//2):
    print(0)
else:
    k-=n*(n-1)//2-(n_plus*(n_plus-1)//2)-(n_minus*(n_minus-1)//2)
    left=0
    right=10**18
    while left+1!=right:
        mid=(right+left)//2
        if k<=get_count(mid):
            right=mid
        else:
            left=mid
    print(right)

Submission status: Runtime Error

Solution code:
from ABC155_D2 import *



import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 3
3 3 -4 -2"""
        output = """-6"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """10 40
5 4 3 2 -1 0 0 0 0 0"""
        output = """6"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """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"""
        output = """448283280358331064"""
        self.assertIO(input, output)

if __name__ == "__main__":
    unittest.main()

Submission status: Runtime Error

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

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.flip(-A_neg)
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)

Submission status: Runtime Error

Solution code:


import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg)

np=len(A_pos)
nn=len(A_neg)
nz=N-np-nn
n_post=np*(np-1)//2+(nn*(nn-1))//2
n_zero=nz*(np+nn)+nz*(nz-1)//2
n_neg=np*nn

#array内で積がx未満になるペアの数
def syakutori_pos1(x):
    res=0
    j=n-1
    for i in range(n_pos):
        tmp=0
#         j=n-1
        y=-(-x//A_pos[i])
        while j!=-1:
            
            if A_pos[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if A_pos[i]**2<x:
            tmp-=1

        res+=tmp
    res=res//2
    return res

def syakutori_pos2(x):
    res=0
    j=n-1
    for i in range(n_neg):
        tmp=0
#         j=n-1
        y=-(-x//A_neg2[i])
        while j!=-1:
            
            if A_neg2[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if A_neg2[i]**2<x:
            tmp-=1

        res+=tmp
    res=res//2
    return res


#array内で積がx未満になるペアの数
def syakutori_neg(x):
    y=x//A_neg
#     print(A_pos,y)
    res=0
    i=0
    j=np-1
    for z in reversed(y):
        while(j!=-1):
            if z<A_pos[j]:
                j-=1
            else:
                break
#         print(z,j+1)
        res+=j+1
    return np*nn-res



def syakutori(x):
    if x>0:
        return syakutori_pos1(x)+syakutori_pos2(x)+n_neg+n_zero
    elif x==0:
        return n_neg
    else:
        return syakutori_neg(x)




r=10**18
l=-10**18
while(r-l>1):
    mid=(l+r)//2
    z=syakutori(mid)
#     z= count_pair(mid)
#     print(l,r)
    if z < K:
        l=mid
    else:
        r=mid
print(l)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
p = []
z = []
m = []
for i in range(n):
    if a[i] > 0:
        p.append(a[i])
    elif a[i] == 0:
        z.append(a[i])
    else:
        m.append(a[i])
nb1 = 10**18+1
nb2 = -10**18-1
p1 = len(p)
z1 = len(z)
m1 = len(m)
#print(p,m)
#print(p1,z1,m1)
def sytr(x,p,z,m,p1,z1,m1):
    ans = 0
    ans2 = 0
    ans3 = -10**18
    if x > 0:
        m.sort(reverse=True)
        p.sort()
        ans += p1*m1 + (p1+m1)*z1 + (z1-1)*z1//2
        ans2 += ans
        now = 0
        #print(p)
        now1 = p1-1
        now2 = 0
        now3 = p1-1
        if p1 > 1:
            while now < now1:
                if p[now]*p[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,p[now]*p[now1])
                    ans += now1-now
                    now += 1
            while now2 < now3:
                if p[now2]*p[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3 - now2
                    now2 += 1
        if m1 > 1:
            now = 0
            now1 = m1-1
            now2 = 0
            now3 = m1-1
            while now < now1:
                if m[now]*m[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,m[now]*m[now1])
                    ans += now1 - now
                    now += 1
            while now2 < now3:
                if m[now2]*m[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3 - now2
                    now2 += 1
    elif x == 0:
        p.sort()
        m.sort()
        if p1 > 0 and m1 > 0:
            ans3 = p[0]*m[m1-1]
        if z1 > 0:
            ans3 = 0
        ans += p1*m1
        ans2 += (p1+m1)*z1 + ans
    else:
        p.sort(reverse=True)
        m.sort()
        now = 0
        now1 = m1-1
        now2 = 0
        now3 = m1-1
        if p1 > 0 and m1 > 0:
            while now < p1 and now1 >= 0:
                if p[now]*m[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,p[now]*m[now1])
                    ans += now1+1
                    now += 1
            while now2 < p1 and now3 >= 0:
                if p[now2]*m[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3+1
                    now2 += 1
    return [ans,ans2,ans3]
while nb1 + 1 < nb2:
    #print(nb1,nb2)
    x = (nb1+nb2)//2
    #print(sytr(x,p,z,m,p1,z1,m1))
    if max(sytr(x,p,z,m,p1,z1,m1)[0],sytr(x,p,z,m,p1,z1,m1)[1]) < k:
        nb1 = x
    elif min(sytr(x,p,z,m,p1,z1,m1)[0],sytr(x,p,z,m,p1,z1,m1)[1]) > k:
        nb2 = x
    else:
        if abs(sytr(x,p,z,m,p1,z1,m1)[1]-sytr(x,p,z,m,p1,z1,m1)[0]) == 0:
            x = sytr(x,p,z,m,p1,z1,m1)[2]
            break
        else:
            break
print(x)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
p = []
z = []
m = []
for i in range(n):
    if a[i] > 0:
        p.append(a[i])
    elif a[i] == 0:
        z.append(a[i])
    else:
        m.append(a[i])
nb1 = a[0]*a[n-1]
nb2 = max(a[0]*a[1],a[n-1]*a[n-2])
p1 = len(p)
z1 = len(z)
m1 = len(m)
#print(p,m)
#print(p1,z1,m1)
def sytr(x,p,z,m,p1,z1,m1):
    ans = 0
    ans2 = 0
    ans3 = -10**18
    if x > 0:
        m.sort(reverse=True)
        p.sort()
        ans += p1*m1 + (p1+m1)*z1 + (z1-1)*z1//2
        ans2 += ans
        now = 0
        #print(p)
        now1 = p1-1
        now2 = 0
        now3 = p1-1
        if p1 > 1:
            while now < now1:
                if p[now]*p[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,p[now]*p[now1])
                    ans += now1-now
                    now += 1
            while now2 < now3:
                if p[now2]*p[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3 - now2
                    now2 += 1
        if m1 > 1:
            now = 0
            now1 = m1-1
            now2 = 0
            now3 = m1-1
            while now < now1:
                if m[now]*m[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,m[now]*m[now1])
                    ans += now1 - now
                    now += 1
            while now2 < now3:
                if m[now2]*m[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3 - now2
                    now2 += 1
    elif x == 0:
        p.sort()
        m.sort()
        if p1 > 0 and m1 > 0:
            ans3 = p[0]*m[m1-1]
        if z1 > 0:
            ans3 = 0
        ans += p1*m1
        ans2 += (p1+m1)*z1 + ans
    else:
        p.sort(reverse=True)
        m.sort()
        now = 0
        now1 = m1-1
        now2 = 0
        now3 = m1-1
        if p1 > 0 and m1 > 0:
            while now < p1 and now1 >= 0:
                if p[now]*m[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,p[now]*m[now1])
                    ans += now1+1
                    now += 1
            while now2 < p1 and now3 >= 0:
                if p[now2]*m[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3+1
                    now2 += 1
    return [ans,ans2,ans3]
while nb1 + 1 < nb2:
    #print(nb1,nb2)
    x = (nb1+nb2)//2
    #print(sytr(x,p,z,m,p1,z1,m1))
    if max(sytr(x,p,z,m,p1,z1,m1)[0],sytr(x,p,z,m,p1,z1,m1)[1]) < k:
        nb1 = x
    elif min(sytr(x,p,z,m,p1,z1,m1)[0],sytr(x,p,z,m,p1,z1,m1)[1]) > k:
        nb2 = x
    else:
        if abs(sytr(x,p,z,m,p1,z1,m1)[1]-sytr(x,p,z,m,p1,z1,m1)[0]) == 0:
            x = sytr(x,p,z,m,p1,z1,m1)[2]
            break
        else:
            break
print(x)

Submission status: Runtime Error

Solution code:
import bisect
n,k=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
x=bisect.bisect_left(A,0,lo=0,hi=len(A))
y=bisect.bisect_right(A,0,lo=0,hi=len(A))
AN=x
A0=y-x
AP=n-y
if x!=0:
  An=A[:x]
else:
  An=[]
Ann=An[::-1]
Annn=[0]*AN
for i in range(AN):
  Annn[i]=Ann[i]*(-1)
if y!=n:
  App=A[-n+y:]
  Ap=App[::-1]
else:
  Ap=[]
if k<=AN*AP:
  ok=An[0]*Ap[0]-1
  ng=0
  while ng-ok>1:
    mid=(ok+ng)//2
    c=0
    for i in range(AN):
      c=c+AP-bisect.bisect_left(App,((-1)*mid+(-1)*An[i]-1)//((-1)*An[i]),lo=0,hi=AP)
    if c<k:
      ok=mid
    else:
      ng=mid
  ans=ok+1
  print(ans)
elif k<=n*(n-1)//2-AN*(AN-1)//2-AP*(AP-1)//2:
  print(0)
else:
  k=n*(n-1)//2-k+1
  ok=max(An[0]**2,Ap[0]**2)
  ng=0
  while ok-ng>1:
    mid=(ok+ng)//2
    c=0
    for i in range(AN):
      c=c+max(0,AN-i-1-bisect.bisect_left(Annn,(mid+Annn[AN-i-1]-1)//Annn[AN-i-1],lo=0,hi=AN))
    for i in range(AP):
      c=c+max(0,AP-i-1-bisect.bisect_left(App,(mid+App[AP-i-1]-1)//App[AP-i-1],lo=0,hi=AP))
    if c<k:
      ok=mid
    else:
      ng=mid
  ans=ok-1
  print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


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

A = list(map(int,input().split(' ')))
A = np.array(A)
A.sort()

#print(A)

l = -10**18
r = 10**18
#l=-100
#r = 100

num_pos = np.count_nonzero(A>0)
num_zero = np.count_nonzero(A==0)
num_neg = np.count_nonzero(A<0)

def count(mid):
    cnt = 0
    #print(f'mimdn:{mid}')
    for a in A:
        if a>0:
            cnt += np.searchsorted(A,mid//a,side="right")
            #print('search',end=" ")
            #print(mid//a)
        elif a==0:
            if mid>0:
                cnt += N 
        else:
            cnt += (N-np.searchsorted(A,(-mid-1)//(-a),side="right"))
            #print('search',end=" ")
            #print(mid//a)
        #print(cnt,end=" ")
    cnt -= np.count_nonzero(A*A<mid)
    #print('a',end=" ")
    #print(cnt,end=" ")
    cnt = cnt//2
    #print(cnt)
    return cnt



while l+1<r:
    mid = (r+l)//2
    cnt = count(mid)
    if cnt < K:
        l = mid
    else:
        r = mid
    #print(f'mid:{mid}: cnt{cnt}')
print(r)

Submission status: Runtime Error

Solution code:
import numpy as np


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

A = np.array(list(map(int,input().split(' '))))

A.sort()

#print(A)

l = -10**18
r = 10**18
#l=-100
#r = 100

num_pos = np.count_nonzero(A>0)
num_zero = np.count_nonzero(A==0)
num_neg = np.count_nonzero(A<0)

def count(mid):
    cnt = 0
    #print(f'mimdn:{mid}')
    for a in A:
        if a>0:
            cnt += np.searchsorted(A,mid//a,side="right")
            #print('search',end=" ")
            #print(mid//a)
        elif a==0:
            if mid>0:
                cnt += N 
        else:
            cnt += (N-np.searchsorted(A,(-mid-1)//(-a),side="right"))
            #print('search',end=" ")
            #print(mid//a)
        #print(cnt,end=" ")
    cnt -= np.count_nonzero(A*A<mid)
    #print('a',end=" ")
    #print(cnt,end=" ")
    cnt = cnt//2
    #print(cnt)
    return cnt



while l+1<r:
    mid = (r+l)//2
    cnt = count(mid)
    if cnt < K:
        l = mid
    else:
        r = mid
    print(f'mid:{mid}: cnt{cnt}')
print(r)

Submission status: Runtime Error

Solution code:
import numpy as np


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

A = np.array(list(map(int,input().split(' '))))

A.sort()

#print(A)

l = -10**18
r = 10**18
#l=-100
#r = 100

num_pos = np.count_nonzero(A>0)
num_zero = np.count_nonzero(A==0)
num_neg = np.count_nonzero(A<0)

def count(mid):
    cnt = 0
    #print(f'mimdn:{mid}')
    for a in A:
        if a>0:
            cnt += np.searchsorted(A,mid//a,side="right")
            #print('search',end=" ")
            #print(mid//a)
        elif a==0:
            if mid>0:
                cnt += N 
        else:
            cnt += (N-np.searchsorted(A,(-mid-1)//(-a),side="right"))
            #print('search',end=" ")
            #print(mid//a)
        #print(cnt,end=" ")
    cnt -= np.count_nonzero(A*A<mid)
    #print('a',end=" ")
    #print(cnt,end=" ")
    cnt = cnt//2
    #print(cnt)
    return cnt



while l+1<r:
    mid = (r+l)//2
    cnt = count(mid)
    if cnt < K:
        l = mid
    else:
        r = mid
    print(f'mid:{mid}: cnt{cnt}')
print(r)

Submission status: Runtime Error

Solution code:
import numpy as np


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

A = np.array(list(map(int,input().split(' '))))

A.sort()

#print(A)

l = -10**18
r = 10**18
#l=-100
#r = 100

num_pos = np.count_nonzero(A>0)
num_zero = np.count_nonzero(A==0)
num_neg = np.count_nonzero(A<0)

def count(mid):
    cnt = 0
    #print(f'mimdn:{mid}')
    for a in A:
        if a>0:
            cnt += np.searchsorted(A,mid//a,side="right")
            #print('search',end=" ")
            #print(mid//a)
        elif a==0:
            if mid>0:
                cnt += N 
        else:
            cnt += (N-np.searchsorted(A,(-mid-1)//(-a),side="right"))
            #print('search',end=" ")
            #print(mid//a)
        #print(cnt,end=" ")
    cnt -= np.count_nonzero(A*A<mid)
    #print('a',end=" ")
    #print(cnt,end=" ")
    cnt = cnt//2
    #print(cnt)
    return cnt



while l+1<r:
    mid = (r+l)//2
    cnt = count(mid)
    if cnt < K:
        l = mid
    else:
        r = mid
    print(f'mid:{mid}: cnt{cnt}')
print(l,r)

Submission status: Runtime Error

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

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

plus, minus, zero = [], [], 0
for a in A:
    if a > 0:
        plus.append(a)
    elif a < 0:
        minus.append(a)
    else:
        zero += 1
        
len_plus = len(plus)
len_minus = len(minus)

plus_cnt = len_plus * (len_plus - 1) // 2 + len_minus * (len_minus - 1) // 2
minus_cnt = len_plus * len_minus
zero_cnt = N * (N - 1) // 2 - plus_cnt - minus_cnt
print(plus_cnt, minus_cnt, zero_cnt)

# 小さい順に K 番目に来る数字を求める
if K <= minus_cnt:
    # plus(4, 2, 1), minus(-1, -2, -3)
    # 4, -2, 2, -3
    plus.sort(reverse = True)
    minus.sort(reverse = True)
    plus.append(-10 ** 18)
    minus.append(10 ** 18)

    ok, ng = 10 ** 19, -10 ** 19
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        l, r = 0, 0
        v = plus[l] * minus[r]
        cnt = 0
        while l < len_plus and r < len_minus:
            if v <= mid:
                cnt += len_minus - r
                l += 1
            else:
                r += 1
            v = plus[l] * minus[r]
        if cnt >= K:
            ok = mid
        else:
            ng = mid
    print(ok)
elif minus_cnt < K <= minus_cnt + zero_cnt:
    print(0)
else:
    1
    """
    # plus(3, 2, 1), minus(5, 4, 2)
    minus = [abs(m) for m in minus]
    plus.sort(reverse = True)
    minus.sort(reverse = True)
    plus.append(-10 ** 18)
    minus.append(-10 ** 18)

    ok, ng = 10 ** 19, -10 ** 19
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        l, r = 0, 0
        v = plus[l] * plus[r]
        cnt = 0
        while l < len_plus:
            if v <= mid:
                cnt += (len_minus - r)
                l += 1
            else:
                r += 1
            v = plus[l] * minus[r]
        if cnt >= K:
            ok = mid
        else:
    """
            ng = mid
    print(ok)

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.array([int(x) for x in input().split()])
ans = np.zeros(N*(N-1)//2, dtype=np.int)

s = 0
e = N-1

for i in range(N-1):
    ans[s:e] = A[i] * A[i+1:]
    s += N-1-i
    e += N-1-(i+1)

ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:

import time

n, k = (int(x) for x in input().split())
list = list(int(x) for x in input().split())
mul_list = []



plus_list = [n for n in list if n > 0]
zero_list = [n for n in list if n == 0]
minus_list = [n for n in list if n < 0]


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


def mul(list):
    list_len = len(list)
    for i in range(list_len):
        for j in range(i + 1, list_len):
            mul_list.append(list[i] * list[j])


def mul_minus(list1, list2):
    for num_1 in list1:
        for num_2 in list2:
            mul_list.append(num_1 * num_2)


n_len = mul_n(n)

z_len = len(zero_list)
p_len = len(plus_list)
m_len = len(minus_list)

num_0 = int(z_len * (p_len + m_len) + mul_n(z_len))
num_minus = p_len * m_len
num_plus = (mul_n(p_len) + mul_n(m_len))


if(k <= num_minus):
    mul_minus(plus_list, minus_list)
    mul_list.sort()


    print(mul_list[k])
elif(k <= num_minus + num_0):
    print(0)

else:
    mul(minus_list)
    mul(plus_list)
    mul_list.sort()
    print(mul_list[k - (num_0 + num_minus) - 1])

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

a,b=map(int,input().split())
c=np.array(input().split()).astype(int)
cc=list(itertools.combinations(c,2))
dd=np.sum(cc,1)
r_dd=np.argsort(dd)
print(int(dd[r_dd==b]))

Submission status: Runtime Error

Solution code:
#abc_155_d
#versions of not using numpy
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = np.array(a)
a.sort()

left = -10**18
right = 10**18

while left+1 < right:
    mid = (left+right)//2
    cnt = 0
    
    #run about each element as the first choice
    for i in range(n):
        #count possible pairs that satisfies the condition      
        if(a[i] >= 0):
            #hold the sorted order
            l = -1 
            r = n
            while l+1<r:
                m = (l+r)//2
                if(a[i]*a[m] <= mid):
                    l = m
                else:
                    r = m
            
            cnt += l+1
        
        if(a[i] < 0):
            #reverse the sorted order
            l = -1 
            r = n
            while l+1<r:
                m = (l+r)//2
                if(a[i]*a[m] <= mid):
                    r = m
                else:
                    l = m
                    
            cnt += n - r
        
        if(a[i]**2 <= mid):
            cnt -= 1
        
    cnt /= 2
        
            
    
    """
    if mid >=0:
        cnt += len(zero) * n
    
    cnt += a.searchsorted(mid//plus, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//minus), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt /= 2
    """
    
    if cnt >= k:
        right = mid
    if cnt < k:
        left=mid
   
        
print(right)

Submission status: Runtime Error

Solution code:
import numpy as np
def f(nums, a):
  return 0  if nums.size<=1 else (np.searchsorted(nums, a//nums, side='right').sum()-np.searchsorted(nums, int(pow(a, 1/2)), side='right'))//2

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:] if p>0 else np.array([])
AN=A[:q] if q>0 else np.array([])

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  if q>1:
    AN=-AN[::-1]
  x=0
  y=max(AN[-2]*AN[-1], AP[-2]*AP[-1])
  K=K-a-b
  while y-x>1:
    tmp=(y+x)//2
    if f(AP, tmp)+f(AN, tmp)<K:
      x=tmp
    else:
      y=tmp
  print(y)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

A.sort()

product = []
for i in range(len(A)):
    if ((K <= len(product)) and (product[K-1] <= A[i]*A[i+1])):
        break
    for j in range(i+1, len(A)):
        product.append(A[i]*A[j])
    product.sort()

print(product[K-1])

Submission status: Runtime Error

Solution code:

n, k = (int(x) for x in input().split())
list = list(int(x) for x in input().split())
mul_list = []

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

def mul(list):
    list_len = len(list)
    for i in range(list_len):
        for j in range(i + 1, list_len):
            mul_list.append(list[i] * list[j])

def mul_minus(list1, list2):
    for num_1 in list1:
        for num_2 in list2:
            mul_list.append(num_1 * num_2)

            

plus_list = [n for n in list if n > 0]
zero_list = [n for n in list if n == 0]
minus_list = [n for n in list if n < 0]

count_0 = len(zero_list)
n_num = mul_n(n)

num_0 = int(count_0 * (2 * n - count_0 - 1) / 2)
num_minus = len(plus_list) * len(minus_list)
num_plus = n_num - (num_0 + num_minus)

if(k <= num_minus):
    mul_minus(plus_list, minus_list)
    mul_list.sort()
    print(mul_list[k])

elif(k <= num_minus + num_0):
    print(0)

else:
    mul(minus_list)
    mul(plus_list)
    mul_list.sort()
    print(mul_list[k - (num_0 + num_minus) - 1])

Submission status: Runtime Error

Solution code:
n, k = (int(x) for x in input().split())
list = list(int(x) for x in input().split())

minus_mul_list = []
plus_mul_list = []


def mul(txt, *list):
    for i in range(len(list) - 1):
        for j in range(i + 1, n):
            (txt + '_mul_list').append(list[i] * list[j])
            print(txt)


plus_list = [n for n in list if n >= 0]
zero_list = [n for n in list if n == 0]
minus_list = [n for n in list if n <= 0]


count_0 = len(zero_list)
n_limit = n * (n - 1) / 2

num_0 = int(count_0 * (2 * n - count_0 - 1) / 2)
num_minus = len(plus_list) * len(minus_list)
num_plus = n_limit - (num_0 + num_minus)


k_num = k * (k - 1) / 2
if(k_num <= num_minus):
    mul('minus', *minus_list)
    print(minus_mul_list[k])

elif(k_num <= num_minus + num_0):
    print(0)

else:
    mul('plus', *plus_list)
    print(plus_mul_list[k - (num_0 + num_minus)])

Submission status: Runtime Error

Solution code:
import numpy as np

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:]
if q>0:
  AN=A[:q]

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  K=K-a-b
  x=0
  y=10**18
  AN=AN[::-1]
  AN=-AN
  while y-x>1:
    tmp=(y+x)//2
    counter1=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
    counter2=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)