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

def solve1(m, minus, plus):
    minus = np.sort(minus)
    plus = np.sort(plus)[::-1]
    # ２分探索
    lo = minus[0] * plus[0]
    hi = minus[-1] * plus[-1]
    while lo < hi:
        mid = (lo + hi) // 2
        num = 0
        j = minus.shape[0] - 1
        for i in range(plus.shape[0]):
            while minus[j] * plus[i] > mid:
                j -= 1
            num += j
        if num > m:
            hi = mid - 1
        elif num < m:
            lo = mid + 1
        else:
            lo = mid
            break

    j = minus.shape[0] - 1
    res = 0
    for i in range(plus.shape[0]):
        while minus[j] * plus[i] > lo:
            j -= 1
        res = min(res, minus[j] * plus[i])
    return res

def solve2(m, minus, plus):
    minus = np.sort(minus)[::-1]
    plus = np.sort(plus)
    # ２分探索
    lo = 0
    hi = plus[-1] * plus[-2] if len(plus) > 1 else 0
    hi += minus[-1] * minus[-2] if len(minus) > 1 else 0
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0

        j1 = plus.shape[0] - 1
        if j1 > 0:
            for i in range(plus.shape[0]):
                while j1 >= 0 and plus[j1] * plus[i] > mid:
                    j1 -= 1
                if j1 > i:
                    num += j1 - i

        j2 = minus.shape[0] - 1
        if j2 > 0:
            for i in range(minus.shape[0]):
                while minus[j2] * minus[i] > mid:
                    j2 -= 1
                if j2 > i:
                    num += j2 - i

        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j1 = plus.shape[0] - 1
    j2 = minus.shape[0] - 1
    res = 0
    if j1 > 0:
        for i in range(plus.shape[0]):
            while j1 >= 0 and plus[j1] * plus[i] > hi:
                j1 -= 1
            if j1 > i:
                res = max(res, plus[j1] * plus[i])
    if j2 > 0:
        for i in range(minus.shape[0]):
            while j2 >= 0 and minus[j2] * minus[i] > hi:
                j2 -= 1
            if j2 > i:
                res = max(res, minus[j2] * minus[i])
    return res


def main():
    N, K = [int(x) for x in input().split()]
    A = np.fromstring(input(), np.int64, sep=' ')
    minus = A[A < 0]
    zero = A[A == 0]
    plus = A[A > 0]

    n_minus = len(minus)
    n_zero = len(zero)
    n_plus = len(plus)

    p_minus = n_minus * n_plus
    p_zero = n_zero * (n_minus + n_plus) + n_zero * (n_zero - 1) // 2

    if K <= p_minus:
        ans = solve1(K, minus, plus)
        print(ans)
    elif K <= p_minus + p_zero:
        print(0)
    else:
        ans = solve2(K - p_minus - p_zero, minus, plus)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

import numpy as np


# 解がマイナスのとき
def solve1(k, ml, pl):
    left, right = -(10 ** 18) - 1, 0
    while right - left > 1:
        x = (left + right) // 2
        n = (len(pl) - np.searchsorted(pl, x / ml)).sum()
        if k <= n:
            right = x
        else:
            left = x
    return right


# 解がプラスのとき
def solve2(k, ml, pl):
    left, right = 0, 10 ** 18
    while right - left > 1:
        x = (left + right) // 2
        n = 0
        n += (len(ml) - np.searchsorted(ml, x / ml)).sum()
        n -= np.count_nonzero(ml ** 2 <= x)
        n += (np.searchsorted(pl, x // pl, side="right")).sum()
        n -= np.count_nonzero(pl ** 2 <= x)
        assert n % 2 == 0
        n //= 2
        if k <= n:
            right = x
        else:
            left = x
    return right


def main():
    N, K = list(map(int, input().split()))
    A = np.array(input().split(), dtype=int)
    A.sort()
    ml = A[A < 0]
    pl = A[A > 0]
    zl = A[A == 0]
    mn = len(ml) * len(pl)
    zn = sum([N - i - 1 for i in range(len(zl))])
    if K <= mn:
        ans = solve1(K, ml, pl)
    elif K <= mn + zn:
        ans = 0
    else:
        ans = solve2(K - mn - zn, ml, pl)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input=sys.stdin.redline
#aのリストの中で２つ選び積がb未満の組み合わせがいくつあるかを出力する
def ok(a,b):
    ans=0
    n=len(a)
    for i in range(n):
        l=0
        r=len(a)-1
        
        if(a[i]*a[i]<b):
            ans-=1
        
        if(a[i]<0):
            if(a[l]*a[i]<b):
                ans+=n
                
                continue
            if(a[r]*a[i]>=b):
                ans+=0
                continue
        
            while(l+1<r):
                middle=(l+r)//2
                if(a[i]*a[middle]<b):
                    r=middle
                else:
                    l=middle
            ans+=n-r
        else:
            
            if(a[r]*a[i]<b):
                ans+=n
                continue
            if(a[l]*a[i]>=b):
                ans+=0
                continue           
            while(l+1<r):
                middle=(l+r)//2
                if(a[i]*a[middle]<b):
                    l=middle
                else:
                    r=middle   
                    
            ans+=l+1

    ans/=2
    
    return ans


NK=list(map(int,input().split()))
N=NK[0]
K=NK[1]
A=np.array(list(map(int,input().split())))
A=sorted(A)
l=-10**18
r=10**18

while(l+1<r):

    middle=(l+r)//2
    if(ok(A,middle)<K):
        l=middle
    else:
        r=middle

print(l)

Submission status: Runtime Error

Solution code:
import sys
first_line = True
for line in sys.stdin:
  if first_line:
    N, K = line.split()
    N = int(N)
    K = int(K)
    first_line = False
  else:
    nums = list(map(int, line.split()))
    negative_count = 0
    positive_count = 0
    for num in nums:
      if num <0:
        negative_count += 1
      if num > 0:
        positive_count += 1
    zero_count = len(nums) - negative_count - positive_count
    n_res_count = negative_count  * positive_count
    p_res_count = negative_count * (negative_count-1)//2 + positive_count * (positive_count-1)//2
    z_res_count = N*(N-1)//2 - n_res_count - p_res_count
    if K <= n_res_count:
      # find in negative nums
      cands = []
      pos =[]
      neg = []
      for n in nums:
        if n>0:
          pos.append(n)
        elif n<0:
          neg.append(n)
      for p in pos:
        for n in neg:
          cands.append(p*n)
      print(sorted(cands)[K])
    elif K <= n_res_count + z_res_count:
      print(0)
    else:
      K -= (n_res_count + z_res_count)
      cands = []
      pos =[]
      neg = []
      for n in nums:
        if n>0:
          pos.append(n)
        elif n<0:
          neg.append(n)
      for i in range(len(pos)-1):
        for j in range(i+1, len(pos)):
          cands.append(pos[i]*pos[j])
      for i in range(len(neg)-1):
        for j in range(i+1, len(neg)):
          cands.append(neg[i]*neg[j])
      print(sorted(cands)[K])

Submission status: Runtime Error

Solution code:
import sys
first_line = True
for line in sys.stdin:
  if first_line:
    N, K = line.split()
    N = int(N)
    K = int(K)
    first_line = False
  else:
    nums = list(map(int, line.split()))
    negative_count = 0
    positive_count = 0
    for num in nums:
      if num <0:
        negative_count += 1
      if num > 0:
        positive_count += 1
    zero_count = len(nums) - negative_count - positive_count
    n_res_count = negative_count  * positive_count
    p_res_count = negative_count * (negative_count-1)//2 + positive_count * (positive_count-1)//2
    z_res_count = N*(N-1)//2 - n_res_count - p_res_count
    if K <= n_res_count:
      # find in negative nums
      cands = []
      pos =[]
      neg = []
      for n in nums:
        if n>0:
          pos.append(n)
        elif n<0:
          neg.append(n)
      for p in pos:
        for n in neg:
          cands.append(p*n)
      print(sorted(cands)[K])
    elif K <= n_res_count + z_res_count:
      print(0)
    else:
      K -= (n_res_count + z_res_count)
      cands = []
      pos =[]
      neg = []
      for n in nums:
        if n>0:
          pos.append(n)
        elif n<0:
          neg.append(n)
      for i in range(len(pos-1)):
        for j in range(i+1, len(pos)):
          cands.append(pos[i]*pos[j])
      for i in range(len(neg-1)):
        for j in range(i+1, len(neg)):
          cands.append(neg[i]*neg[j])
      print(sorted(cands)[K])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
ar=list(map(int,input().split( )))
for i in range(n):
  for j in range(i+1,n):
    arr.append(ar[i]+ar[j])
arr.sort()
print(arr[k])

Submission status: Runtime Error

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
    
    inf = 10**18+1
    u = inf
    l = -inf
    # 答えが負
    if num_negative * num_positive >= K:
        def g(i,x):
            up = N
            lp = num_negative + num_zero
            min_m = N
            mp = (up+lp)//2
            while up-lp > 1:
                mp = (up+lp)//2
                # print(A[i],A[mp],mp)
                if A[i] * A[mp] < x:
                    up = mp
                    
                    min_m = min(min_m,mp)
                else:
                    lp = mp
            mp = (up+lp)//2
            if A[i] * A[mp] < x:
                # print(A[i],A[mp],mp)
                min_m = min(min_m,mp)
            # if amm * A[mp] < x:
            #     max_m = max(max_m,mp)
            # print('i=',i,'A[i]=',A[i],min_m,N-min_m)
            #print('g(',i,',',x,')=',max_m - (num_negative + num_zero-1))
            return max(N-min_m,0)
            

        def f(x):
            ans = 0
            for i in range(num_negative):
                ans += g(i,x)
            return ans

        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)
        return max_m

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

    # 答えが正
    else:
        assert(False)
        K -= num_negative * num_positive +\
             num_negative * num_zero +\
             num_positive * num_zero + num_zero*(num_zero-1)//2

        def f(i,x):
            # u = num_negative
            u = i
            l = 0
            min_m = N
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    u = m
                    min_m = min(min_m,m)
                else:
                    l = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                    min_m = min(min_m,m)

            # ans = num_negative - min_m
            ans = i - min_m
            # if i >= min_m:
            #     ans -= 1 
            ans = max(ans,0)
            #print('f(',x,')=',ans, num_negative, min_m, i,A[0]*A[i]<x)
            return ans

        def g(i,x):
            u = N
            # l = num_negative + num_zero
            l = i+1
            max_m = num_negative + num_zero -1
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    l = m
                    max_m = max(max_m,m)
                else:
                    u = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                max_m = max(max_m,m)
            
            
            # ans = max_m - num_negative - num_zero +1
            ans = max_m - i
            
            # if i <=max_m :
            #     ans -= 1 
            ans = max(ans,0)
            #print('g(',x,')=',ans,max_m,num_negative+num_zero,'A[i]=',A[i])
            
            return ans
            
        def h(x):
            ans = 0
            for i in range(1,num_negative):
                ans += f(i,x)
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                ans += g(i,x)
            #print('h(',x,')=',ans,'K=',K)
            # print('neg*neg=',preans,'pos*pos=',ans-preans)
            return ans
        





        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if h(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        # m = (u+l)//2
        # if f(m) >= K:
        #     u = m
        # else:
        #     l = m
        #     max_m = max(max_m,m)
        #print('ans=',max_m,448283280358331064-max_m)
        # print(h(87940638538504704))
        print(max_m)
        return max_m




if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

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

neg = []
pos = []
zeros = []
for a in A:
    if a < 0:
        neg.append(a)
    elif a == 0:
        zeros.append(a)
    else:
        pos.append(a)
num_neg = len(neg) * len(pos)
num_zero = (len(neg) + len(pos)) * len(zeros) + len(zeros) * (len(zeros) - 1) // 2


if k <= num_neg:
    neg.sort()
    pos.sort(reverse=True)
    d = k // len(neg)
    s = k % len(pos)
    ans = neg[d] * pos[s]
elif num_neg < k <= num_neg + num_zero:
    ans = 0
else:
    k -= (num_neg + num_zero)
    neg = sorted([abs(i) for i in neg])
    pos.sort()
    neg.append(float('infinity'))
    pos.append(float('infinity'))
    while True:
        if neg[0] < pos[0]:
            if k > len(neg) - 2:
                k = k - len(neg) + 2
                neg = neg[1:]
            else:
                ans = neg[0] * neg[k]
                break
        else:
            if k > len(pos) - 2:
                k = k - len(pos) + 2
                pos = pos[1:]
            else:
                ans = ans = pos[0] * pos[k]
                break
print(ans)

Submission status: Runtime Error

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
    
    inf = 10**18+1
    u = inf
    l = -inf
    # 答えが負
    if num_negative * num_positive >= K:
        def g(i,x):
            up = N
            lp = num_negative + num_zero
            max_m = num_negative + num_zero -1
            mp = (up+lp)//2
            while up-lp > 1:
                mp = (up+lp)//2
                if A[i] * A[mp] < x:
                    lp = mp
                    max_m = max(max_m,mp)
                else:
                    up = mp
            mp = (up+lp)//2
            if A[i] * A[mp] < x:
                max_m = max(max_m,mp)
            # if amm * A[mp] < x:
            #     max_m = max(max_m,mp)
            return max(max_m - (num_negative + num_zero-1),0)
            

        def f(x):
            ans = 0
            for i in range(num_negative):
                ans += g(i,x)
            return ans

        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 max_m

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

    # 答えが正
    else:
        assert(False)
        K -= num_negative * num_positive +\
             num_negative * num_zero +\
             num_positive * num_zero + num_zero*(num_zero-1)//2

        def f(i,x):
            # u = num_negative
            u = i
            l = 0
            min_m = N
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    u = m
                    min_m = min(min_m,m)
                else:
                    l = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                    min_m = min(min_m,m)

            # ans = num_negative - min_m
            ans = i - min_m
            # if i >= min_m:
            #     ans -= 1 
            ans = max(ans,0)
            #print('f(',x,')=',ans, num_negative, min_m, i,A[0]*A[i]<x)
            return ans

        def g(i,x):
            u = N
            # l = num_negative + num_zero
            l = i+1
            max_m = num_negative + num_zero -1
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    l = m
                    max_m = max(max_m,m)
                else:
                    u = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                max_m = max(max_m,m)
            
            
            # ans = max_m - num_negative - num_zero +1
            ans = max_m - i
            
            # if i <=max_m :
            #     ans -= 1 
            ans = max(ans,0)
            #print('g(',x,')=',ans,max_m,num_negative+num_zero,'A[i]=',A[i])
            
            return ans
            
        def h(x):
            ans = 0
            for i in range(1,num_negative):
                ans += f(i,x)
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                ans += g(i,x)
            #print('h(',x,')=',ans,'K=',K)
            # print('neg*neg=',preans,'pos*pos=',ans-preans)
            return ans
        





        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if h(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        # m = (u+l)//2
        # if f(m) >= K:
        #     u = m
        # else:
        #     l = m
        #     max_m = max(max_m,m)
        #print('ans=',max_m,448283280358331064-max_m)
        # print(h(87940638538504704))
        print(max_m)
        return max_m




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
 
lines = [l for l in sys.stdin]
l = lines[0].split(' ')
N, K = int(l[0]), int(l[1])
 
nums = [int(s) for s in lines[1].split(' ')]
 
rets = []
for idx, n1 in enumerate(nums[:-1]):
  for idy, n2 in enumerate(nums[idx+1]):
    rets.append(n1 * n2)
rets.sort()
print(rets[K-1])

Submission status: Runtime Error

Solution code:
import sys

lines = [l for l in sys.stdin]
l = lines[0].split(' ')
N, K = int(l[0]), int(l[1])

nums = [int(s) for s in lines[1].split(' ')]

rets = []
for idx, n1 in enumerate(nums[:-1]):
  for idy, n2 in enumerate(nums[idx+1]):
    rets.append(n1 * n2)
rets.sort()
print(rets[K])

Submission status: Runtime Error

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
    
    inf = 10**18+1
    u = inf
    l = -inf
    # 答えが負
    if num_negative * num_positive >= K:
        def g(i,x):
            up = N
            lp = num_negative + num_zero
            max_m = num_negative + num_zero -1
            mp = (up+lp)//2
            while up-lp > 1:
                mp = (up+lp)//2
                if A[i] * A[mp] < x:
                    lp = mp
                    max_m = max(max_m,mp)
                else:
                    up = mp
            mp = (up+lp)//2
            if A[i] * A[mp] < x:
                max_m = max(max_m,mp)
            # if amm * A[mp] < x:
            #     max_m = max(max_m,mp)
            print(max_m - (num_negative + num_zero-1))
            return max(max_m - (num_negative + num_zero-1),0)
            

        def f(x):
            ans = 0
            for i in range(num_negative):
                ans += g(i,x)
            return ans

        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 max_m

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

    # 答えが正
    else:
        assert(False)
        K -= num_negative * num_positive +\
             num_negative * num_zero +\
             num_positive * num_zero + num_zero*(num_zero-1)//2

        def f(i,x):
            # u = num_negative
            u = i
            l = 0
            min_m = N
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    u = m
                    min_m = min(min_m,m)
                else:
                    l = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                    min_m = min(min_m,m)

            # ans = num_negative - min_m
            ans = i - min_m
            # if i >= min_m:
            #     ans -= 1 
            ans = max(ans,0)
            #print('f(',x,')=',ans, num_negative, min_m, i,A[0]*A[i]<x)
            return ans

        def g(i,x):
            u = N
            # l = num_negative + num_zero
            l = i+1
            max_m = num_negative + num_zero -1
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    l = m
                    max_m = max(max_m,m)
                else:
                    u = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                max_m = max(max_m,m)
            
            
            # ans = max_m - num_negative - num_zero +1
            ans = max_m - i
            
            # if i <=max_m :
            #     ans -= 1 
            ans = max(ans,0)
            #print('g(',x,')=',ans,max_m,num_negative+num_zero,'A[i]=',A[i])
            
            return ans
            
        def h(x):
            ans = 0
            for i in range(1,num_negative):
                ans += f(i,x)
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                ans += g(i,x)
            #print('h(',x,')=',ans,'K=',K)
            # print('neg*neg=',preans,'pos*pos=',ans-preans)
            return ans
        





        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if h(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        # m = (u+l)//2
        # if f(m) >= K:
        #     u = m
        # else:
        #     l = m
        #     max_m = max(max_m,m)
        #print('ans=',max_m,448283280358331064-max_m)
        # print(h(87940638538504704))
        print(max_m)
        return max_m




if __name__ == '__main__':
    main()

Submission status: Runtime Error

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
    
    inf = 10**18+1
    u = inf
    l = -inf
    # 答えが負
    if num_negative * num_positive >= K:
        def g(i,x):
            up = N
            lp = num_negative + num_zero
            max_m = -1
            mp = (up+lp)//2
            while up-lp > 1:
                mp = (up+lp)//2
                if A[i] * A[mp] < x:
                    lp = mp
                    max_m = max(max_m,mp)
                else:
                    up = mp
            mp = (up+lp)//2
            if A[i] * A[mp] < x:
                max_m = max(max_m,mp)
            # if amm * A[mp] < x:
            #     max_m = max(max_m,mp)
            # print(amm,x,max_m,num_negative + num_zero,mp)
            return max(max_m - (num_negative + num_zero-1),0)
            

        def f(x):
            ans = 0
            for i in range(num_negative):
                ans += g(i,x)
            return ans

        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)
        m = (u+l)//2
        if f(m) >= K:
            u = m
        else:
            l = m
            max_m = max(max_m,m)
        print(max_m)
        return max_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:
        assert(False)
        K -= num_negative * num_positive +\
             num_negative * num_zero +\
             num_positive * num_zero + num_zero*(num_zero-1)//2

        def f(i,x):
            # u = num_negative
            u = i
            l = 0
            min_m = N
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    u = m
                    min_m = min(min_m,m)
                else:
                    l = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                    min_m = min(min_m,m)

            # ans = num_negative - min_m
            ans = i - min_m
            # if i >= min_m:
            #     ans -= 1 
            ans = max(ans,0)
            #print('f(',x,')=',ans, num_negative, min_m, i,A[0]*A[i]<x)
            return ans

        def g(i,x):
            u = N
            # l = num_negative + num_zero
            l = i+1
            max_m = num_negative + num_zero -1
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    l = m
                    max_m = max(max_m,m)
                else:
                    u = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                max_m = max(max_m,m)
            
            
            # ans = max_m - num_negative - num_zero +1
            ans = max_m - i
            
            # if i <=max_m :
            #     ans -= 1 
            ans = max(ans,0)
            #print('g(',x,')=',ans,max_m,num_negative+num_zero,'A[i]=',A[i])
            
            return ans
            
        def h(x):
            ans = 0
            for i in range(1,num_negative):
                ans += f(i,x)
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                ans += g(i,x)
            #print('h(',x,')=',ans,'K=',K)
            # print('neg*neg=',preans,'pos*pos=',ans-preans)
            return ans
        





        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if h(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        # m = (u+l)//2
        # if f(m) >= K:
        #     u = m
        # else:
        #     l = m
        #     max_m = max(max_m,m)
        #print('ans=',max_m,448283280358331064-max_m)
        # print(h(87940638538504704))
        print(max_m)
        return max_m




if __name__ == '__main__':
    main()