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: Wrong Answer

Solution code:
n,k = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()

# x未満の要素の個数を数える
def counter(lst, x):
    add = 0
    count = 0
    count_same = 0
    for i in range(len(lst)):
        left = 0
        right = len(lst)
        if lst[i]>=0:
            while left + 1 < right:
                center = (left + right)//2
                if lst[i]*lst[center] < x:
                    left = center
                else:
                    right = center
            add = left+1
        else:
            while left + 1 < right:
                center = (left + right)//2
                if lst[i]*lst[center] > x:
                    left = center
                else:
                    right = center
            add = len(lst)-left-1
        count += add
    for i in range(len(lst)):
        if lst[i]**2 < x:
            count_same += 1
    return (count - count_same)/2


# x未満の要素がk個未満である最大のxを求める
left = -10**18
right = 10**18
while left + 1 < right:
    center = (left + right)//2
    print("lst:",lst,"center:",center,"counter:",counter(lst,center))
    if counter(lst, center) <= k:
        left = center
    else:
        right = center

print(left)

Submission status: Wrong Answer

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

AP=[]
AN=[]
Z=0
for i in range(N):
  if A[i]>0:
    AP.append(A[i])
  elif A[i]<0:
    AN.append(A[i])
  else:
    Z+=1
    
AP.sort()
AN.sort()
p=len(AP)
q=len(AN)

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

def f(nums, x):
  return np.searchsorted(nums, x, side='right')

def g(nums, x):
    return len(nums)-np.searchsorted(nums, a, side='left')
  
if K<=a:
  x=AN[0]*AP[-1]
  y=AN[-1]*AP[0]
  if K==1:
    print(x)
    exit()
  if K==a:
    print(y)
    exit()
  while y-x>1:
    tmp=(y+x)//2
    counter=0
    for s in AP:
      counter+=f(AN, tmp/s)
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  K-=a+b
  if len(AP)>1 and len(AN)>1:
    x=min(AP[0]*AP[1], AN[-2]*AN[-1])
    y=max(AP[-2]*AP[-1], AN[0]*AN[1])
    while y-x>1:
      tmp=(y+x)//2
      counter1=0
      for s in AP:
        counter1+=g(AP, tmp/s)
      counter2=0
      for s in AN:
        counter2+=f(AN, tmp/s)
      counter=(counter1+1)//2+(counter2+1)//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
  elif len(AP)>1 and len(AN)<=1:
    x=AP[0]*AP[1]
    y=AP[-2]*AP[-1]
    while y-x>1:
      tmp=(y+x)//2
      counter=0
      for s in AP:
        counter+=g(AP, tmp/s)
      counter=(counter+1)//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
  else:
    x=AN[-2]*AN[-1]
    y=AN[0]*AN[1]
    while y-x>1:
      tmp=(y+x)//2
      counter=0
      for s in AN:
        counter+=f(AN, tmp/s)
      counter=(counter+1)//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
a.sort()
ll,rr=10**(-18),10**18+1
while ll+1<rr:
  mm=(ll+rr)//2
  cnt=0
  for i,x in enumerate(a):
    l,r=i,n
    while l+1<r:
      m=(l+r)//2
      if x*a[m]>mm:
        r=m
      else:
        l=m
    if l==i:
      if x*x<=mm:
        cnt+=1
    else:
      cnt+=n-i-1
  if cnt<k:
    ll=mm
  else:
    rr=mm
print(ll)

Submission status: Wrong Answer

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

ans = 0
minus = 0
zero = 0
plus = 0

for a in alist:
  if a < 0:
    minus += 1
  elif a == 0:
    zero += 1
  else:
    plus += 1

mp = minus*(minus-1)//2 + plus*(plus-1)//2   # 正の数
mz = zero*(zero-1)//2 + zero*(plus+minus)    # 0の数
mm = minus*plus                              # 負の数

# 正解が0の場合
if mm < k <= mm + mz:
    ans = 0
else:
    INF = int(10e+18) + 2
    l = -INF
    r = INF
    x = 0
    c = 0
    cb = 0

    # 正解が負の場合
    if k <= mm:
        l = alist[0]*alist[-1]+1
        r = 0
        mlist = alist[:minus]
        plist = alist[:minus+zero-1:-1]
        while l+1 < r:
            x = (l+r)//2
            c = 0
            # 負×正
            for a1 in mlist:
                for a2 in plist:
                    if a1 * a2 < x:
                        c += 1
                    else:
                        break
            if c < k:
                l = x
            else:
                r = x
    # 正解が正の場合
    else:
        l = 0
        k -= mm + mz
        mlist = alist[minus-1::-1]
        plist = alist[minus+zero:]
        while l+1 < r:
            x = (l+r)//2
            c = 0
            i = 0
            # 負×負
            for a1 in mlist:
                j = 0
                for a2 in mlist:
                    if a1 * a2 < x:
                        if i != j:  # 自分自身は数えない
                            c += 1
                    else:
                        break
                    j += 1
                i += 1
            i = 0
            # 正×正
            for a1 in plist:
                j = 0
                for a2 in plist:
                    if a1 * a2 < x:
                        if i != j:  # 自分自身は数えない
                            c += 1
                    else:
                        break
                    j += 1
                i += 1
            # 2で割る(2回数えるので)
            c = c//2
            if c < k:
                l = x
            else:
                r = x
    ans = l

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from bisect import bisect_left, bisect_right

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

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = np.array(A[:n], dtype = np.int64)
Positive = np.array(A[p:], dtype = np.int64)

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
    # print (x, tmp)
    return tmp

def Ncount1(x):
    tmp = 0
    for a in Negative:
        tmp += Number_Positive - np.searchsorted(Positive, (x + a + 1) // a) 
    return tmp

def Pcount(x): #x以下の数を数える(x > 0)
    tmp = 0
    for index, a in enumerate(Positive):
        tmp += bisect_right(Positive[index + 1:], x // a)
    for index, b in enumerate(Negative):
        tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
        # print (bisect_right(Negative[index + 1:], x / b))
    # print (x, tmp)
    return tmp

if Number_Negative >= K:
    # ここに二分探索を書く
    l = -10 ** 18
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount1(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = 10 ** 18
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount(mid):
            r = mid
        else:
            l = mid

    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)

Submission status: Wrong Answer

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

ans = 0
minus = 0
zero = 0
plus = 0

for a in alist:
  if a < 0:
    minus += 1
  elif a == 0:
    zero += 1
  else:
    plus += 1

mp = minus*(minus-1)//2 + plus*(plus-1)//2   # 正の数
mz = zero*(zero-1)//2 + zero*(plus+minus)    # 0の数
mm = minus*plus                              # 負の数

# 正解が0の場合
if mm < k <= mm + mz:
    ans = 0
else:
    INF = int(10e+18) + 2
    l = -INF
    r = INF
    x = 0
    c = 0
    cb = 0

    # 正解が負の場合
    if k <= mm:
        r = 0
        mlist = alist[:minus]
        plist = alist[:minus+zero-1:-1]
        while l+1 < r:
            x = int((l+r)//2)
            c = 0
            # 負×正
            for a1 in mlist:
                for a2 in plist:
                    if a1 * a2 < x:
                        c += 1
                    else:
                        break
                if cb == c:
                    break
                cb = c
            if c < k:
                l = x
            else:
                r = x
    # 正解が正の場合
    else:
        l = 0
        k -= mm + mz
        mlist = alist[minus-1::-1]
        plist = alist[minus+zero:]
        while l+1 < r:
            x = (l+r)//2
            c = 0
            i = 0
            # 負×負
            for a1 in mlist:
                j = 0
                for a2 in mlist:
                    if a1 * a2 < x:
                        if i != j:  # 自分自身は数えない
                            c += 1
                    else:
                        break
                    j += 1
                i += 1
                if cb == c:
                    break
                cb = c
            i = 0
            # 正×正
            for a1 in plist:
                j = 0
                for a2 in plist:
                    if a1 * a2 < x:
                        if i != j:  # 自分自身は数えない
                            c += 1
                    else:
                        break
                    j += 1
                i += 1
                if cb == c:
                    break
                cb = c
            # 2で割る(2回数えるので)
            c = c//2
            if c < k:
                l = x
            else:
                r = x
    ans = l

print(ans)

Submission status: Wrong Answer

Solution code:
from subprocess import*
call(("pypy3","-c","""
from bisect import bisect_left, bisect_right

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

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = A[:n]
Positive = A[p:]

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
    # print (x, tmp)
    return tmp

# def Pcount(x): #x以下の数を数える(x > 0)
#     tmp = 0
#     for index, a in enumerate(Positive):
#         tmp += bisect_right(Positive[index + 1:], x // a)
#     for index, b in enumerate(Negative):
#         tmp += len(Negative) - (index + 1) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
#         # print (bisect_right(Negative[index + 1:], x / b))
#     # print (x, tmp)
#     return tmp

def Pcount(x): #x以下の数を数える(x > 0)
    tmp = 0
    for p in Positive:
        tmp += bisect_right(Positive, x // p)
        if p ** 2 <= x:
            tmp -= 1
    # print (tmp)
    for n in Negative:
        tmp += len(Negative) - bisect_left(Negative, (x + n + 1) // n)
        if n ** 2 <= x:
            tmp -= 1
    # print (x, tmp)
    return tmp // 2

if Number_Negative >= K:
    # ここに二分探索を書く
    l = Negative[0] * Positive[-1]
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = max(Negative[0] ** 2, Positive[-1] ** 2)
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount(mid):
            r = mid
        else:
            l = mid

    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)
"""))

Submission status: Wrong Answer

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

seki = []
for i in range(n-1):
    for j in range(i+1,n):
        ans = a[i] * a[j]
        seki.append(ans)
ans2 = sorted(seki)
print(ans2)
print(ans2[k-1])

Submission status: Wrong Answer

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

seki = []
for i in range(n):
    for j in range(i+1,n):
        ans = a[i] * a[j]
        seki.append(ans)
ans2 = sorted(seki)
print(ans2)
print(ans2[k-1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = A[:n]
Positive = A[p:]

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, x / a)
    # print (x, tmp)
    return tmp

def Pcount(x): #x以下の数を数える(x > 0)
    tmp = 0
    for index, a in enumerate(Positive):
        tmp += bisect_right(Positive[index + 1:], x // a)
    for index, b in enumerate(Negative):
        tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b - 1) // b)
        # print (bisect_right(Negative[index + 1:], x / b))
    # print (x, tmp)
    return tmp

if Number_Negative >= K:
    # ここに二分探索を書く
    l = -10 ** 18
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = 10 ** 18
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount(mid):
            r = mid
        else:
            l = mid
    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = A[:n]
Positive = A[p:]

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, (x + a - 1) // a)
    # print (x, tmp)
    return tmp

def Pcount(x): #x以下の数を数える(x > 0)
    tmp = 0
    for index, a in enumerate(Positive):
        tmp += bisect_right(Positive[index + 1:], x // a)
    for index, b in enumerate(Negative):
        tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b - 1) // b)
        # print (bisect_right(Negative[index + 1:], x / b))
    # print (x, tmp)
    return tmp

if Number_Negative >= K:
    # ここに二分探索を書く
    l = -10 ** 18
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = 10 ** 18
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount(mid):
            r = mid
        else:
            l = mid
    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

AA =[]
for i in range(N):
    for j in range(i + 1, N):
        AA.append(A[i] * A[j])
#print(sorted(AA))

P, M, Z = [], [], []
for a in A:
    if a > 0:
        P.append(a)
    elif a < 0:
        M.append(a)
    else:
        Z.append(a)
            
plus, minus, zero = 0, 0, 0
lenP = len(P)
lenM = len(M)
lenZ = len(Z)

if P:
    plus += lenP * (lenP - 1) // 2
if M:
    plus += lenM * (lenM - 1) // 2
minus += lenP * lenM
zero = N * (N - 1) // 2 - plus - minus
#print(plus, minus, zero)

P.sort()
M = [abs(m) for m in M]
M.sort()
#print(P, M)

if K <= minus:
    
    # mid 以上になる個数cntがK以上になる最大のleft
    left, right = 0, 10 ** 20
    while left + 1 < right:
        mid = (left + right) // 2
        cnt = 0
        for p in P:
            cnt += lenM - bisect_left(M, mid / p)
        if cnt >= K:
            left = mid
        else:
            right = mid
    print(-left)
elif K <= minus + zero:
    print(0)
else:
    K = K - minus - zero
    #print(K)
    #print(M)
    # mid 以下になる個数cntがK'以上になる最小のright
    left, right = 0, 10 ** 20
    while left + 1 < right:
        mid = (left + right) // 2
        cntp, cntm, cnt = 0, 0, 0
        for p in P:
            cntp += bisect_right(P, mid / p)
            if p ** 2 <= mid:
                cntp -= 1
        cntp //= 2
        for m in M:
            cntm += bisect_right(M, mid / m)
            if m ** 2 <= mid:
                cntm -= 1
        cntm //= 2
        cnt = cntp + cntm
        #print(mid, cntp, cntm)
        if cnt >= K:
            right = mid
        else:
            left = mid
    print(right)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(map(int, args[1].split())))
    N = A[A < 0]
    P = A[0 < A]

    count = 0
    left, right = -10**18, 10**18
    while left+1 < right:
        x = (left+right)//2
        count = 0

        if k < len(N)*len(P):
            count += (len(P)-np.searchsorted(P, -(-x//N), side='left')).sum()

        elif (n*(n-1) - len(N)*(len(N)-1) - len(P)*(len(P)-1))//2 < k:
            for D in (-(N[::-1]), P):
                count += np.searchsorted(D, x//D, side='right').sum()
                count -= len(D[D*D <= x])
            count //= 2
            count += (n*(n-1) - len(N)*(len(N)-1) - len(P)*(len(P)-1))//2

        else:
            right = 0
            break

        if count < k:
            left = x
        else:
            right = x

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right

from numpy import searchsorted


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = sorted(map(int, args[1].split()))

    nega = bisect_left(A, 0)
    posi = bisect_right(A, 0)

    count = 0
    left, right = -10**18, 10**18
    while left+1 < right:
        x = (left+right)//2
        count = 0

        if k < nega*(n-posi):
            for l in A[:nega]:
                r = searchsorted(A, -(-x//l), side='left')
                count += n-r

        elif (n*(n-1) - nega*(nega-1) - (n-posi)*(n-posi-1))//2 < k:
            count = (n*(n-1) - nega*(nega-1) - (n-posi)*(n-posi-1))//2
            for D in ([-a for a in A[:nega][::-1]], A[posi:]):
                for i, l in enumerate(D):
                    r = searchsorted(D, x//l, side='right')
                    count += max(0, r-i-1)

        else:
            right = 0
            break

        if count < k:
            left = x
        else:
            right = x

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

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

A.sort()

iplus = bisect.bisect_right(A,0)
izeros = bisect.bisect_left(A,0)

pluss = A[iplus:]
zeros = A[izeros:iplus]
minuss = A[:izeros]

nplus = len(pluss)
nzero = len(zeros)
nminus = len(minuss)

npminus = nplus * nminus
npzeros = nzero * (nplus + nminus) + nzero * (nzero-1)//2

if npminus < K <= npminus + npzeros:
    print( 0)
elif K <= npminus:
    mn = minuss[0] * pluss[-1]
    mx = minuss[-1] * pluss[0]+1
    while mx-mn > 1:
        mid = (mn+mx)//2
        cnt = 1
        for m in minuss:
            x = -(-mid//m)
            k = bisect.bisect_right(pluss,x)
            #print(m,x,pluss,k)
            cnt += (nplus-k)
            if cnt > K:
                break
        if cnt <= K:
            mn = mid
        else:
            mx = mid
    print(mn)
else:
    nK = K - npminus - npzeros
    pluss2 = [-m for m in minuss][::-1]
    mn = A[-1]**2
    mx = -1
    if len(pluss) > 1:
        mn = min(mn, pluss[0] * pluss[1] - 1)
        mx = max(mx, pluss[-1] * pluss[-2])
    if len(pluss2) > 1:
        mn = min(mn, pluss2[0] * pluss2[1] - 1)
        mx = max(mx, pluss2[-1] * pluss2[-2])
    while mx-mn > 1:
        mid = (mn+mx)//2
        cnt = 1
        for m in pluss:
            x = mid//m
            k = bisect.bisect_right(pluss,x)
            cnt += k - (m**2 <= mid)
            if cnt >= 2*nK:
                break
        for m in pluss2:
            x = mid//m
            k = bisect.bisect_right(pluss2,x)
            cnt += k - (m**2 <= mid)
            if cnt >= 2*nK:
                break
        cnt = cnt //2
        #print(mn,mid,mx,cnt)
        if cnt >= nK:
            mx = mid
        else:
            mn = mid
    print(mx)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = sorted(map(int, args[1].split()))

    nega = bisect_left(A, 0)
    posi = bisect_right(A, 0)

    count = 0
    left, right = -10**18, 10**18
    while left+1 < right:
        x = (left+right)//2
        count = 0

        if k < nega*(n-posi):
            for l in A[:nega]:
                r = bisect_left(A, -(-x//l))
                count += n-r

        elif (n*(n-1) - nega*(nega-1) - (n-posi)*(n-posi-1))//2 < k:
            count = (n*(n-1) - nega*(nega-1) - (n-posi)*(n-posi-1))//2
            for D in ([-a for a in A[:nega][::-1]], A[posi:]):
                for i, l in enumerate(D):
                    r = bisect_right(D, x//l, i+1)
                    count += r-i-1

        else:
            right = 0
            break

        if count < k:
            left = x
        else:
            right = x

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
import sys
import itertools
N, K = map(int, input().split())
arr = list(map(int, input().split()))


v =[v1 * v2
	for v1, v2 in itertools.combinations(arr, 2)
   ][K - 1]

print(v)

Submission status: Wrong Answer

Solution code:
import itertools
N, K = map(int,input().split())
A = list(map(int,input().split()))
l = list(itertools.combinations(A,2))
ans = [k*v for k,v in l]
sorted(ans)[K-1]

Submission status: Wrong Answer

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:
  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+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
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: Wrong Answer

Solution code:
import bisect
import time

time0 = time.time()
Mtime = 1.5
N, K = map(int, input().split())
A = [int(x) for x in input().split()]

Am = sorted([a for a in A if a < 0])
Ap = sorted([a for a in A if a > 0])
Lm = len(Am)
Lp = len(Ap)
L0 = N - Lm - Lp
Cm = Lm * Lp
Cp = Lm * (Lm - 1) // 2 + Lp * (Lp - 1) // 2
C0 = N * (N - 1) // 2 - Cm - Cp

if K <= Cm:
    L = -10 ** 18
    R = 0
    while time.time() - time0 < Mtime:
        M = (L + R) / 2
        count = 0
        for i in range(Lm):
            count += Lp - bisect.bisect_left(Ap, M / Am[i])
        if count > K:
            R = M
        elif count < K:
            L = M
        elif count == K:
            break
    M2 = []
    if Lm > 0:
        Ap_L = Ap[-1]
    for i in range(Lm):
        if Ap_L >= M / Am[i]:
            M2.append(Ap[bisect.bisect_left(Ap, M / Am[i])] * Am[i])
#     print(M, count, M2)
    print(max(M2))
elif Cm + 1 <= K <= Cm + C0:
    print(0)
else:
    K = K - Cm - C0
    L = 0
    R = 10 ** 18
    while time.time() - time0 < Mtime:
        M = (L + R) / 2
        count = 0
        for i in range(Lm):
            count += min(Lm - i - 1, Lm - bisect.bisect_left(Am, M / Am[i]))
        for i in range(Lp):
            count += max(0, bisect.bisect_right(Ap, M / Ap[i]) - i - 1)

        if count > K:
            R = M
        elif count < K:
            L = M
        elif count == K:
            break
    M2 = []
    if Lm > 0:
        Am_L = Am[-1]
    for i in range(Lm):
        if Am_L >= M / Am[i]:
            M2.append(Am[bisect.bisect_left(Am, M / Am[i])] * Am[i])
    if Lp > 0:
        Ap_0 = Ap[0]
    for i in range(Lp):
        if Ap_0 <= M / Ap[i]:
            M2.append(Ap[bisect.bisect_right(Ap, M / Ap[i]) - 1] * Ap[i])
#     print(M, count, M2)
    print(max(M2))

Submission status: Wrong Answer

Solution code:
import numpy as np
 
k = input().split()
alist = np.array(input().split())
 
muls = []

r1 = int(k[0])-1
for i in range(r1):
  a1 = int(alist[i])
  na = np.array(alist[i+1:])
  for a2 in na:
    muls.append( int(a1) * int(a2) )
np.sort(muls)
print(muls[int(k[1])-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int,input().split())
a = np.array(input().split(),np.int64)
zero = a[a==0]
pos = a[a>0]
neg = a[a<0]

def f(x):
    count = 0
    c = x // pos
    count += np.searchsorted(a, c, side='right').sum()
    count += N*len(zero) if x >= 0 else 0
    c = -(-x // neg)
    count += (N - np.searchsorted(a, c, side='left')).sum()
    count -= a[a*a <= x].size
    count //= 2
    return count

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

Submission status: Wrong Answer

Solution code:
import bisect
n,k = map(int, input().split())
a= list(map(int, input().split()))
a.sort()
r=10**18+1
l=-10**18-1
while r-l>1:
    m = (r + l) // 2
    count=0
    for i in range(n):
        if a[i]>0:
            x=m//a[i]
            y=bisect.bisect_right(a,x)
            if y<=i:
                count+=y
            else:
                count+=y-1
        elif a[i]<0:
            x=m//a[i]
            y=bisect.bisect_right(a,x)
            y1=n-y
            if y>i:
                count+=y1
            else:
                count+=y1-1
        else:
            if m>=0:
                count+=n-1
    if count//2>=k:
        r=m
    else:
        l=m
print(r)

Submission status: Wrong Answer

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

L = np.sort(L)
pos = L[0<L]
neg = L[0>L]
zero = len(L[L==0])

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

l, r = -10**18, 10**18
while l<r-1:
  m = (l+r)//2
  count = f(m)
  if count >= K:
    r = m
  else:
    l = m

print(r)

Submission status: Wrong Answer

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

L = np.sort(L)
pos = L[0<L]
neg = L[0>L]
zero = len(L[L==0])

def f(x):
  tmp = 0
  if x>=0:
    tmp += zero*N
  tmp += np.searchsorted(L, x//pos, side='right').sum()
  tmp += (N - np.searchsorted(L, x//neg, side='left')).sum()
  tmp -= np.count_nonzero(L*L<=x)
  return tmp//2

l, r = -10**18, 10**18
while l<r-1:
  m = (l+r)//2
  count = f(m)
  if count >= K:
    r = m
  else:
    l = m

print(r)