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

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)

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, pow(tmp, 1/2), side='right'))//2
    counter2=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, pow(tmp, 1/2), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)

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_1 = []
mul_2 = []


list.sort()
count_0 = list.count(0)
for cnt in range(count_0):
    list.remove(0)


count = int(count_0 * (2 * n - count_0 - 1) / 2)

for i in range(count):
    mul_1.append(0)


for i in range(count_0, n - 1):
    for j in range(i + 1, n):
        mul_2.append(list[i] * list[j])


mul_2.sort()
mul_1.extend(mul_2)
print(mul_1[k - 1])

Submission status: Runtime Error

Solution code:
import sys

N, K = map(int, input().split())
a = sorted(list(map(int, input().split())))
l = -(((1e18)+1)
r=(1e18)+1
while(l + 1 < r):
    x=(l + r) / 2
    total=0
    for i in range(N):
        if a[i] < 0:
            l=-1
            r=N
            while(l + 1 < r):
                c=(l + r) / 2
                if a[c] * a[i] < x:
                    r=c
                else:
                    l=c
            total += n - r
        else:
            l=-1
            r=N
            while(l + 1 < r):
                c=(l + r) / 2
                if a[c] * a[i] < x:
                    l=c
                else:
                    r=c
            total += r
        if a[i] * a[i] < x:
            total -= 1
    total /= 2
    if total < K:
        l=x
    else:
        r=x
print(l)

Submission status: Runtime Error

Solution code:
import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

t = n*(n-1)//2

import bisect
import math
def ok(x):
    # x以上になる組み合わせがt-k+1個以上ある
    cnt = 0
    for a in A:
        if a > 0:
            b = math.ceil(x/a)
            c = n - bisect.bisect_left(A, b)
            if a*a >= x:
                c -= 1
        elif a == 0:
            if x <= 0:
                c = n-1
        else:
            b = math.floor(x/a)
            c = bisect.bisect_right(A, b)
            if a*a >= x:
                c -= 1
        cnt += c
    cnt //= 2
    if cnt >= t-k+1:
        return True
    else:
        return False

l = -10**18-1
r = 10**18+1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

t = n*(n-1)//2

import bisect
import math
def ok(x):
    # x以上になる組み合わせがt-k+1個以上ある
    cnt = 0
    for a in A:
        if a > 0:
            b = math.ceil(x/a)
            c = n - bisect.bisect_left(A, b)
            if a >= b:
                c -= 1
        elif a == 0:
            if x <= 0:
                c = n-1
        else:
            b = math.floor(x/a)
            c = bisect.bisect_right(A, b)
            if a <= b:
                c -= 1
        cnt += c
    cnt //= 2
    if cnt >= t-k+1:
        return True
    else:
        return False

l = -10**18-1
r = 10**18+1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)

Submission status: Runtime Error

Solution code:
N, K = input().split(' ')
nums = input().split(' ')

products = []
for i in num:
  for j in num:
    products.append(i*j)
    
ranking = sorted(products)
print(ranking[K-1])

Submission status: Runtime Error

Solution code:
import itertools
import time
import sys
sys.setrecursionlimit(5000)

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

minus=[x for x in A if x < 0]
zero=[x for x in A if x == 0]
plus=[x for x in A if x > 0]

minus_num = len(minus)*len(plus)
zero_num = len(zero)*(len(minus)+len(plus)) + len(zero)*(len(zero)-1)//2

minus_products=[]
plus_products=[]

#再帰　実装途中　return しない場合がある。　
def binary_search(data,target):
    #print(len(data))
    searching = True
    #for i in range(100000000000000):
    while True:
        pivot = data[int(len(data)//2)]
        min = [i for i in data if i <pivot]
        max = [i for i in data if i >=pivot]
        #for i in data:
        #    if i < pivot:
        #        min.append(i)
        #    else:
        #        max.append(i)
        #print(f"minの数：{len(min)}")
        #print(f"maxの数：{len(max)}")
        #print(f"target：{target}")
        if len(min) == target:
            break
        if len(min) < target:
            if len(min)==0:
                #print(len(data))
                data.sort()
                return data[target-1]
            data = max
            target= target-len(min)
        else:
            data = min
    return min[target-1]


if K <= minus_num:
    #負×正=負のリスト
    for m in minus:
        for j in plus:
            minus_products.append(m*j)
    print(binary_search(minus_products,K))
elif K <= (minus_num+zero_num):
    print(0)
else:
    #負＊負=正のリストと正＊正＝正のリストを合算して、正のリストを作る

    minus_by_minus=list(itertools.combinations(minus, 2))
    plus_by_plus=list(itertools.combinations(plus, 2))
    for m in minus_by_minus:
        plus_products.append(m[0]*m[1])
    for p in plus_by_plus:
        plus_products.append(p[0]*p[1])
    #start = time.time()
    #print(binary_search(plus_products,K-minus_num-zero_num))
    elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

if K <= negative_pairs_cnt:
    # にぶたん: X以下になるペアがK個以上あるか？
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_cnt
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

else:
    print(1 / 0)
    # # にぶたん: X以下になるペアがK個以上あるか？
    # K -= (negative_pairs_cnt + zero_pairs_cnt)
    # ok, ng = 10 ** 18, 0
    # while abs(ok - ng) > 1:
    #     X = (ok + ng) // 2
    #     or_higher_cnt = 0
    #     continue_flg = False
    # print(ok)

Submission status: Runtime Error

Solution code:
import itertools

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

#minus=list(map(lambda x: x if x<0, A))
#zero=list(map(lambda x: x if x==0, A))
#plus=list(map(lambda x: x if x>0, A))

minus=[x for x in A if x < 0]
zero=[x for x in A if x == 0]
plus=[x for x in A if x > 0]

minus_num = len(minus)*len(plus)
zero_num = len(zero)*(len(minus)+len(plus)) + len(zero)*(len(zero)-1)//2

minus_products=[]
plus_products=[]

def binary_search(data,target):
    min=[]
    max=[]
    pivot = data[len(data)//2]
    for i in data:
        if i <= pivot:
            min.append[i]
        else:
            max.append[i]
    if len(min) == target:
        return min[target-1]
    if len(min) < target:
        binary_search_loop(max,target-len(min))
    else:
        binary_search_loop(min,target)

if K <= minus_num:
    #負×正=負のリスト
    for m in minus:
        for j in plus:
            minus_products.append(m*j)
    print(binary_search(minus_products,K))
elif K <= (minus_num+zero_num):
    print(0)
else:
    #負＊負=正のリストと正＊正＝正のリストを合算して、正のリストを作る
    minus_by_minus=list(itertools.combinations(minus, 2))
    plus_by_plus=list(itertools.combinations(plus, 2))
    for m in minus_by_minus:
        plus_products.append(m[0]*m[1])
    for p in plus_by_plus:
        plus_products.append(p[0]*p[1])
    print(binary_search(plus_products,K-minus_num-zero_num))

Submission status: Runtime Error

Solution code:
import itertools

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

#minus=list(map(lambda x: x if x<0, A))
#zero=list(map(lambda x: x if x==0, A))
#plus=list(map(lambda x: x if x>0, A))

minus=[x for x in A if x < 0]
zero=[x for x in A if x == 0]
plus=[x for x in A if x > 0]

minus_num = len(minus)*len(plus)
zero_num = len(zero)*(len(minus)+len(plus)) + len(zero)*(len(zero)-1)//2

minus_products=[]
plus_products=[]

def binary_search(data,target):
    min=[]
    max=[]
    pivot = data[len(data)//2]
    for i in data:
        if i <= pivot:
            min.append[i]
        else:
            max.append[i]
    if len(min) == target:
        return min[target-1]
    if len(min) < target:
        binary_search_loop(max,target-len(min))
    else:
        binary_search_loop(min,target)

if K <= minus_num:
    #負×正=負のリスト
    for m in minus:
        for j in plus:
            minus_products.append(m*j)
    print(binary_search(minus_products,K))
elif K <= (minus_num+zero_num):
    print(0)
else:a
    #負＊負=正のリストと正＊正＝正のリストを合算して、正のリストを作る
    minus_by_minus=list(itertools.combinations(minus, 2))
    plus_by_plus=list(itertools.combinations(plus, 2))
    for m in minus_by_minus:
        plus_products.append(m[0]*m[1])
    for p in plus_by_plus:
        plus_products.append(p[0]*p[1])
    print(binary_search(plus_products,K))

Submission status: Runtime Error

Solution code:
import itertools

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

#minus=list(map(lambda x: x if x<0, A))
#zero=list(map(lambda x: x if x==0, A))
#plus=list(map(lambda x: x if x>0, A))

minus=[x for x in A if x < 0]
zero=[x for x in A if x == 0]
plus=[x for x in A if x > 0]

minus_num = len(minus)*len(plus)
zero_num = len(zero)*(len(minus)+len(plus)) + len(zero)*(len(zero)-1)//2

minus_products=[]
plus_products=[]

#負×正=負のリスト
for m in minus:
    for j in plus:
        minus_products.append(m*j)


#負＊負=正のリストと正＊正＝正のリストを合算して、正のリストを作る
minus_by_minus=list(itertools.combinations(minus, 2))
plus_by_plus=list(itertools.combinations(plus, 2))
for m in minus_by_minus:
    plus_products.append(m[0]*m[1])
for p in plus_by_plus:
    plus_products.append(p[0]*p[1])

def binary_search(data,target):
    min=[]
    max=[]
    pivot = data[len(data)//2]
    for i in data:
        if i <= pivot:
            min.append[i]
        else:
            max.append[i]
    if len(min) == target:
        return min[target-1]
    if len(min) < target:
        binary_search_loop(max,target-len(min))
    else:
        binary_search_loop(min,target)

def get_plus():
    return 1

if K <= minus_num:
    print(binary_search(minus_products,K))
elif K <= (minus_num+zero_num):
    print(0)
else:
    print(get_plus())

Submission status: Runtime Error

Solution code:
import itertools

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

#minus=list(map(lambda x: x if x<0, A))
#zero=list(map(lambda x: x if x==0, A))
#plus=list(map(lambda x: x if x>0, A))

minus=sorted([x for x in A if x < 0])
zero=[x for x in A if x == 0]
plus=sorted([x for x in A if x > 0])

minus_products=[]

#負×正=負のリスト
for m in minus:
    for j in plus:
        minus_products.append(m*j)
minus_products.sort()

plus_products=[]

#負＊負=正のリストと正＊正＝正のリストを合算して、正のリストを作る
minus_by_minus=list(itertools.combinations(minus, 2))
plus_by_plus=list(itertools.combinations(plus, 2))
for m in minus_by_minus:
    plus_products.append(m[0]*m[1])
for p in plus_by_plus:
    plus_products.append(p[0]*p[1])
plus_products.sort()

minus_num = len(minus)*len(plus)
zero_num = len(zero)*(len(minus)+len(plus)) + len(zero)*(len(zero)-1)//2

if K <= minus_num:
    print(minus_products[K])
elif K <= (minus_num+zero_num):
    print(0)
else:
    print(plus_products[K-minus_num-zero_num-1])

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, pow(tmp, 1/2), side='right'))//2
    counter2=(np.searchsorted(AN, tmp/AN, side='right').sum()-np.searchsorted(AN, pow(tmp, 1/2), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)

Submission status: Runtime Error

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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)

val_set = []
if num_minus_pair >= K:
  th0 = A[0]*A[num_minus+num_zero+num_plus]
  th1 = th0/2
  while 1:
    for i in range(num_minus):
      for j in range(num_plus):
        val = A[i]*A[num_minus+num_zero-1-j]
        if th0 <= val < th1:
          val_set.append(val)
        else:
          break
    if len(val_set) >= K:
      val_set = sorted(val_set)
      print(val_set[K-1])
      break
    else:
      th0 = th1
      th1 /= 2
elif num_minus_pair+num_zero_pair >= K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair >= K:
  th0, th1 = 0.0, 0.0
  val0 = A[0]*A[1]
  val1 = A[num_minus+num_zero+num_plus-2]*A[num_minus+num_zero+num_plus-1]
  if val0 > val1:
    th1 = val0/2+0.5
    val_bigger = val0
  elif val0 == val1:
    th0 = val0
    th1 = val0+1
    val_bigger = val0
  else:
    th1 = val1/2
    val_bigger = val1
  K = K - (num_minus_pair + num_zero_pair)
  val_set = []
  while 1:
    for i in range(num_minus-1):
      for j in range(i+1, num_minus):
        val = A[num_minus-1-i]*A[num_minus-1-j]
        if th0 <= val < th1:
          val_set.append(val)
        else:
          break
    for i in range(num_plus-1):
      for j in range(i+1,num_plus):
        val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
        if th0 <= val < th1:
          val_set.append(val)
        else:
          break
    if len(val_set) >= K:
      val_set = sorted(val_set)
      print(val_set[K-1])
      break
    elif len(val_set) < K:
      th0 = th1
      th1 = th1 + (val_bigger-th1)/2

Submission status: Runtime Error

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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)

val_set = []
if num_minus_pair >= K:
  th0 = A[0]*A[num_minus+num_zero]
  th1 = th0/2
  while 1:
    for i in range(num_minus):
      for j in range(num_plus):
        val = A[i]*A[num_minus+num_zero-1-j]
        if th0 <= val < th1:
          val_set.append(val)
        else:
          break
    if len(val_set) >= K:
      val_set = sorted(val_set)
      print(val_set[K-1])
      break
    else:
      th0 = th1
      th1 /= 2
elif num_minus_pair+num_zero_pair >= K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair >= K:
  th0 = 0.0
  th1 = 0.0
  val0 = A[0]*A[1]
  val1 = A[num_minus+num_zero+num_plus-2]*A[num_minus+num_zero+num_plus-1]
  if val0 > val1:    th1 = float(val0/2)
  else:              th1 = float(val1/2)
  K = K - (num_minus_pair + num_zero_pair)
  val_set = []
  while 1:
    for i in range(num_minus-1):
      for j in range(i+1, num_minus):
        val = A[num_minus-1-i]*A[num_minus-1-j]
        if th0 <= val < th1:
          val_set.append(val)
        else:
          break
    for i in range(num_plus-1):
      for j in range(i+1,num_plus):
        val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
        if th0 <= val < th1:
          val_set.append(val)
        else:
          break
    if len(val_set) >= K:
      val_set = sorted(val_set)
      print(val_set[K-1])
      break
    elif len(pair_val_set) < K:
      th0 = th1
      th1 = th1 + (val0-th1)/2

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]
  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=1
  y=10**18
  AN*=-1
  AN=AN[::-1]
  while y-x>1:
    tmp=(y+x)//2
    counter1=(np.searchsorted(AP, tmp/AP, side='right').sum()-np.searchsorted(AP, tmp**(1/2), side='right'))/2
    counter2=(np.searchsorted(AN, tmp/AN, side='right').sum()-np.searchsorted(AN, tmp**(1/2), side='right'))/2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)

Submission status: Runtime Error

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

A = [A[i] for i in range(N) if A[i]!=0]
c = (N+len(A)-1)*(N-len(A))
N = len(A)
A.sort()
B = A[::-1]

def count(m):
    res = 0
    if m>=0:
        res += c
        j = N
        for i in range(N):
            if A[i]>0:
                break
            while j>0:
                if A[i]*A[j-1]<=m:
                    j -= 1
                else:
                    break
            res += N-j
        if A[i]>0:
            j = N-1
            for i in range(i,N):
                while j>=0:
                    if A[i]*A[j]>m:
                        j -= 1
                    else:
                        break
                res += j+1
    else:
        j = N
        for i in range(N):
            if B[i]<0:
                break
            while j>0:
                if B[i]*B[j-1]<=m:
                    j -= 1
                else:
                    break
            res += N-j
        if B[i]<0:
            j = -1
            for i in range(i,N):
                while j<N-1:
                    if B[i]*B[j+1]<=m:
                        j += 1
                    else:
                        break
                res += j+1
    for i in range(N):
        if A[i]*A[i]<=m:
            res -= 1
    res //= 2
    return res

ng = -10**18
ok = 10**18
m = (ng+ok)//2
for n in range(100):
    if count(m)<K:
        ng = m
    else:
        ok = m
    m = (ng+ok)//2
ans = int(ok)
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
#f_i = stdin
f_i = open('test_in_3')#

import numpy as np

N, K = map(int, f_i.readline().split())
A = np.array(f_i.read().split(), dtype=int)

A = np.sort(A)
zero_left = A.searchsorted(0, side='left')
zero_right = A.searchsorted(0, side='right')
zero_cnt = zero_right - zero_left
pos = A[zero_right:]
neg = A[:zero_left]

def f(x):
    cnt = 0
    
    if x >= 0:
        cnt += zero_cnt * N
    
    cnt += np.searchsorted(A, x // pos, side='right').sum()
    cnt += (N - np.searchsorted(A, (-x - 1) // (-neg), side='right')).sum()
    
    cnt -= np.count_nonzero(A ** 2 <= x)
    return cnt // 2


left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x

print(right)

Submission status: Runtime Error

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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)

val_set = []
if num_minus_pair >= K:
  for i in range(num_minus):
    for j in range(num_plus):
      val = A[i]*A[num_minus+num_zero+j]
      val_set.append(val)
elif num_minus_pair+num_zero_pair >= K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair >= K:
  K = K - (num_minus_pair+num_zero_pair)
  for i in range(num_minus-1):
    for j in range(i+1, num_minus):
      val = A[i]*A[j]
      val_set.append(val)
  for i in range(num_plus-1):
    for j in range(i+1, num_plus):
      val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
      val_set.append(val)
val_set = sorted(val_set)
print(val_set[K-1])

Submission status: Runtime Error

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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)
pair_val_set = []
if num_minus_pair >= K:
  th0, th1 = min(A)*max(A), min(A)*max(A)/2
  while 1:
    for i in range(num_minus):
      for j in range(num_plus):
        val = A[i]*A[num_minus+num_zero+num_plus-1-j]
        if th0 <= val < th1:
          pair_val_set.append(val)
        else:
          break
    if len(pair_val_set) >= K:
      break
    elif len(pair_val_set) < K:
      th0 = th1
      th1 = th1 + float((0-th1)/2)#int(th1/2)
elif num_minus_pair+num_zero_pair >= K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair >= K:
  th0, th1 = 0.0, 0.0
  val0 = A[0]*A[1]
  val1 = A[num_minus+num_zero+num_plus-2]*A[num_minus+num_zero+num_plus-1]
  if val0 > val1:    th1 = float(val0/2)
  else:              th1 = float(val1/2)
  K = K - (num_minus_pair + num_zero_pair)
  #print('K:', K)
  while 1:
    for i in range(num_minus-1):
      for j in range(i+1, num_minus):
        val = A[num_minus-1-i]*A[num_minus-1-j]
        if th0 <= val < th1:
          pair_val_set.append(val)
        else:
          break
    for i in range(num_plus-1):
      for j in range(i+1,num_plus):
        val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
        if th0 <= val < th1:
          pair_val_set.append(val)
        else:
          break
    if len(pair_val_set) >= K:
      break
    elif len(pair_val_set) < K:
      th0 = th1
      th1 = th1 + float((val0-th1)/2)
pair_val_set = sorted(pair_val_set)
print(pair_val_set[K-1])

Submission status: Runtime Error

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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)
if num_minus_pair >= K:
  ratio = K/num_minus_pair
  if ratio <= 0.5:
    th0, th1 = min(A)*max(A), min(A)*max(A)/2
    pair_val_set = []
    while 1:
      for i in range(num_minus):
        for j in range(num_plus):
          val = A[i]*A[num_minus+num_zero+num_plus-1-j]
          if th0 <= val < th1:
            pair_val_set.append(val)
          else:
            break
      if len(pair_val_set) >= K:
        pair_val_set = sorted(pair_val_set)
        print(pair_val_set[K-1])
        break
      elif len(pair_val_set) < K:
        th0 = th1
        th1 /= 2
  else:
    K = num_minus_pair - K
    th0, th1 = A[num_minus-1]*A[num_minus]*2, A[num_minus-1]*A[num_minus]
    pair_val_set = []
    while 1:
      for i in range(num_minus):
        for j in range(num_plus):
          val = A[num_minus-1-i]*A[num_minus+j]
          if th0 < val <= th1:
            pair_val_set.append(val)
          else:
            break
      if len(pair_val_set) >= K:
        pair_val_set = sorted(pair_val_set)
        print(pair_val_set[K-1])
        break
      else:
        th1 = th0
        th0 *= 2
elif num_minus_pair+num_zero_pair >= K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair >= K:
  th0 = 0.0
  th1 = 0.0
  val0 = A[0]*A[1]
  val1 = A[num_minus+num_zero+num_plus-2]*A[num_minus+num_zero+num_plus-1]
  if val0 > val1:    th1 = float(val0/2)
  else:              th1 = float(val1/2)
  K = K - (num_minus_pair + num_zero_pair)
  #print('K:', K)
  pair_val_set = []
  while 1:
    for i in range(num_minus-1):
      for j in range(i+1, num_minus):
        val = A[num_minus-1-i]*A[num_minus-1-j]
        if th0 <= val < th1:
          pair_val_set.append(val)
        else:
          break
    for i in range(num_plus-1):
      for j in range(i+1,num_plus):
        val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
        if th0 <= val < th1:
          pair_val_set.append(val)
        else:
          break
    if len(pair_val_set) >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif len(pair_val_set) < K:
      th0 = th1
      th1 = th1 + float((val0-th1)/2)

Submission status: Runtime Error

Solution code:
import bisect
N,K = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
An.sort()
idx = bisect.bisect_left(An,0)
positive = An[idx:] 
negative = An[:idx]


max_candidate = 10**18 + 1
min_candidate = -1 * (10**18) - 1

while True:
    middle = (max_candidate + min_candidate)//2
    if 0 <= middle:
        current_length = len(positive) * len(negative)
        candidate_list = []
        #正 * 正
        for i,n1 in enumerate(positive):
            n2_list = positive[i+1:]
            if n1 != 0:
                n2_candidate = middle / n1
                n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            else:
                n2_idx = len(n2_list)
            current_length += n2_idx
            if 0 < n2_idx:
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
            else:
                break
        #負 * 負
        for i,n1 in enumerate(negative):
            n2_list = negative[i+1:]
            n2_candidate = middle / n1
            n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            if n2_idx < len(n2_list):
                current_length += len(n2_list) - n2_idx - 1
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
            else:
                break
    else:
        current_length = 0
        candidate_list = []
        #正 * 負
        for i,n1 in enumerate(negative): 
            n2_list = positive
            n2_candidate = middle / n1
            n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            #current_length += n2_idx
            if n2_idx < len(n2_list):
                current_length += len(n2_list) - n2_idx
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
            else:
                break
    if min_candidate+1 == max_candidate:
        break
    if current_length == K:
        print(max(candidate_list))
        exit(0)
    elif current_length < K:
        min_candidate = middle
    else:
        max_candidate = middle
print(max(candidate_list))