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:
def main():
    from bisect import bisect_left as bl

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

    inf = 10**18+1

    ok = -inf
    ng = inf
    start_0 = bl(a, 0)
    start_1 = bl(a, 1)

    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        if mid >= 0:
            now = 0
            for i in a[start_0-1::-1]:
                while now < n:
                    if i*a[now] >= mid:
                        now += 1
                    else:
                        break
                cnt += n - now
            now = n
            for i in a[start_1:]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        else:
            now = 0
            for i in a[:start_0]:
                while now < n:
                    if i*a[now] >= mid:
                        now += 1
                    else:
                        break
                cnt += n - now
            now = n
            for i in a[n-1:start_1-1:-1]:
                while now > 0:
                    if i*a[now-1] >= mid:
                        now -= 1
                    else:
                        break
                cnt += now
        if mid > 0:
            cnt += n * (start_1 - start_0)
        cnt -= len([None for i in a if i*i < mid])
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import numpy as np
from math import ceil


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            mid = ceil((left + right) / 2)
            a = (p - np.searchsorted(pluses, np.ceil(mid / minuses), side='left')).sum()
            if a < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:
        print(1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import numpy as np
from math import ceil


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2

    if K <= M:
        left = A[0] * A[-1] - 1
        right = 0
        minuses = np.array(A[:m], np.int64)
        pluses = np.array(A[-p:], np.int64)
        while left + 1 < right:
            mid = ceil((left + right) / 2)
            a = (p - np.searchsorted(pluses, np.ceil(mid / minuses), side='left')).sum()
            if a < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:
        print(1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# スペース区切りの整数入力
N,K = map(int, input().split())
# スペース区切りの整数をリストに入力
#a = []
am = []
az = []
ap = []
iam = []

for x in list(map(int, input().split())):
    if x > 0:
        ap.append(x)
    elif x == 0:
        az.append(x)
    else:
        am.append(x)
        iam.append(-x)
#    a.append(x)
ap.sort()
az.sort()
am.sort()
iam.sort()

#n = len(a)*(len(a)-1) // 2
nm = len(am)*len(ap)
nz = len(az)*(len(az)-1) // 2 + len(az)*(len(am)+len(ap))
np = len(am)*(len(am)-1) // 2 + len(ap)*(len(ap)-1) // 2

def cnt_func(x):
    '''
    res1 = 0
    for i in range(N-1):
        for j in range(i+1,N):
            if a[i]*a[j] <= x:
                res1 += 1
    '''
    res2 = 0
    if x < 0:
        nj = 0
        for i in range(len(am)-1,-1,-1):
            res2 += nj
            for j in range(nj,len(ap)):
                if am[i]*ap[j] <= x:
                    res2 += 1
                else:
                    #nj = j
                    nj = 0
                    break
        return res2
    elif x == 0:
        res2 += nm + nz
        return res2
    else:
        res2 += nm + nz
        nj = 0
        for i in range(len(iam)-1,0,-1):
            res2 += min(nj,i)
            for j in range(nj,i):
                if iam[i]*iam[j] <= x:
                    res2 += 1
                else:
                    #nj = j
                    nj = 0
                    break
        nj = 0
        for i in range(len(ap)-1,0,-1):
            res2 += min(nj,i)
            for j in range(nj,i):
                if ap[i]*ap[j] <= x:
                    res2 += 1
                else:
                    #nj = j
                    nj = 0
                    break
        return res2

l = -(10**18)
h = 10**18

while h > l+1:
    m = (l + h) // 2
    kk = cnt_func(m)
    if kk >= K:
        h = m
    else:
        l = m

print(h)

Submission status: Wrong Answer

Solution code:
# スペース区切りの整数入力
N,K = map(int, input().split())
# スペース区切りの整数をリストに入力
#a = []
am = []
az = []
ap = []
iam = []

for x in list(map(int, input().split())):
    if x > 0:
        ap.append(x)
    elif x == 0:
        az.append(x)
    else:
        am.append(x)
        iam.append(-x)
#    a.append(x)
ap.sort()
az.sort()
am.sort()
iam.sort()

#n = len(a)*(len(a)-1) // 2
nm = len(am)*len(ap)
nz = len(az)*(len(az)-1) // 2 + len(az)*(len(am)+len(ap))
np = len(am)*(len(am)-1) // 2 + len(ap)*(len(ap)-1) // 2

def cnt_func(x):
    '''
    res1 = 0
    for i in range(N-1):
        for j in range(i+1,N):
            if a[i]*a[j] <= x:
                res1 += 1
    '''
    res2 = 0
    if x < 0:
        nj = 0
        for i in range(len(am)-1,-1,-1):
            res2 += nj
            for j in range(nj,len(ap)):
                if am[i]*ap[j] <= x:
                    res2 += 1
                else:
                    #nj = j
                    nj = 0
                    break
        return res2
    elif x == 0:
        res2 += nm + nz
        return res2
    else:
        res2 += nm + nz
        nj = 0
        for i in range(len(iam)-1,0,-1):
            res2 += min(nj,i)
            for j in range(nj,i):
                if iam[i]*iam[j] <= x:
                    res2 += 1
                else:
                    nj = j
                    break
        nj = 0
        for i in range(len(ap)-1,0,-1):
            res2 += min(nj,i)
            for j in range(nj,i):
                if ap[i]*ap[j] <= x:
                    res2 += 1
                else:
                    nj = j
                    break
        return res2

l = -(10**18)
h = 10**18

while h > l+1:
    m = (l + h) // 2
    kk = cnt_func(m)
    if kk >= K:
        h = m
    else:
        l = m

print(h)

Submission status: Wrong Answer

Solution code:
# スペース区切りの整数入力
N,K = map(int, input().split())
# スペース区切りの整数をリストに入力
#a = []
am = []
az = []
ap = []
iam = []

for x in list(map(int, input().split())):
    if x > 0:
        ap.append(x)
    elif x == 0:
        az.append(x)
    else:
        am.append(x)
        iam.append(-x)
#    a.append(x)
ap.sort()
az.sort()
am.sort()
iam.sort()

#n = len(a)*(len(a)-1) // 2
nm = len(am)*len(ap)
nz = len(az)*(len(az)-1) // 2 + len(az)*(len(am)+len(ap))
np = len(am)*(len(am)-1) // 2 + len(ap)*(len(ap)-1) // 2

def cnt_func(x):
    '''
    res1 = 0
    for i in range(N-1):
        for j in range(i+1,N):
            if a[i]*a[j] <= x:
                res1 += 1
    '''
    res2 = 0
    if x < 0:
        nj = 0
        for i in range(len(am)-1,-1,-1):
            res2 += nj
            for j in range(nj,len(ap)):
                if am[i]*ap[j] <= x:
                    res2 += 1
                else:
                    nj = j
                    break
        return res2
    elif x == 0:
        res2 += nm + nz
        return res2
    else:
        res2 += nm + nz
        nj = 0
        for i in range(len(iam)-1,0,-1):
            res2 += min(nj,i)
            for j in range(nj,i):
                if iam[i]*iam[j] <= x:
                    res2 += 1
                else:
                    nj = j
                    break
        nj = 0
        for i in range(len(ap)-1,0,-1):
            res2 += min(nj,i)
            for j in range(nj,i):
                if ap[i]*ap[j] <= x:
                    res2 += 1
                else:
                    nj = j
                    break
        return res2

l = -(10**18)
h = 10**18

while h > l+1:
    m = (l + h) // 2
    kk = cnt_func(m)
    if kk >= K:
        h = m
    else:
        l = m

print(h)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

#積がx以下になる組み合わせの数
def f(x):
    ret=0
    if x<0:
        for na in nA:
            ret+=g2(pA,na,x)
        for pa in pA:
            ret+=g2(nA,pa,x)
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=len(L)
    t=x/n
    while over-l>1:
        m=(over+l)//2
        if L[m]<=t: l=m
        else: over=m
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=len(L)-1
    t=x/n
    while r-under>1:
        m=(under+r)//2
        if L[m]<=t: r=m
        else: under=m
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**19
r=10**19
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Wrong Answer

Solution code:

import bisect
import sys
input = sys.stdin.readline

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

#積がX未満になるものがK-1個以下になる最大のXを探す

ng=10**20
ok=-1*10**20

while abs(ng-ok)>1:
    X=(ok+ng)//2
    temp=0
    
    for i in range(N):
        if A[i]>0:
            b=X/A[i]
            #A[j]がb未満となるjの個数を数える
            th=bisect.bisect_left(A,b)
            if b>A[i]:
                th-=1
            temp+=th

        elif A[i]<0:
            b=X/A[i]
            #A[j]がbより大きくなるjの個数を数える
            th=bisect.bisect_right(A,b)
            if b<A[i]:
                temp-=1
            temp+=N-th
        else:
            if X>0:
                temp+=N-1
            
    temp=temp//2
    #print(ok,X,ng,temp)
    #print("---")
    
    if temp>=K:
        ng=X
    else:
        ok=X

print(ok)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ra = [-x for x in a[: : -1]]
ra.sort()
#print(a)
#print(ra)
def check(x):
  c = 0
  for y in a:
    i = 0
    if y > 0:
      t = x / y
      i = br(a, t)
      c += i - (i == N)
      if i < N: c -= (a[i] > int(y))
    elif y == 0:
      c += (N - 1) * (x >= 0)
    else:
      t = x / -y
      i = br(ra, t)
      c += i - (i == N)
      if i < N: c -= (ra[i] > -int(y))
    #print(y, t, i, c)
  #print(c, x)
  return c >= (2 * K)
ok = max(abs(a[-1]), abs(a[0])) ** 2
ng = -max(abs(a[-1]), abs(a[0])) ** 2
#print(ok)
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m
  #print(m, check(m))
print(ok)

Submission status: Wrong Answer

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

print(N,K,A)

A = np.sort(A)
posi = A[A>0]
zero = A[A==0]
nega = A[A<0]

def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    # count 0
    if x >= 0:
        cnt_tpl += len(zero) * N
    # count posi
    cnt_tpl += np.searchsorted(A, x//posi, side='right').sum()
    # count nega
    cnt_tpl += (N - np.searchsorted(A, (-x - 1) // (-nega), side='right')).sum()
    # remove a^2
    cnt_tpl -= np.count_nonzero(A*A <= x)
    return cnt_tpl // 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: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left as bl

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

    inf = 10**18+1

    ok = -inf
    ng = inf
    start_0 = bl(a, 0)
    start_1 = bl(a, 1)

    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        now = 0
        for i in a[start_0-1::-1]:
            while now < n:
                if i*a[now] >= mid:
                    now += 1
                else:
                    break
            cnt += n - now
        now = n
        for i in a[start_1:]:
            while now > 0:
                if i*a[now-1] >= mid:
                    now -= 1
                else:
                    break
            cnt += now
        if mid > 0:
            cnt += n * (start_1 - start_0)
        cnt -= len([None for i in a if i*i < mid])
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = A[-1]**2+10
l = A[0]*A[-1]-10
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu):
      while True:
        if cou>=plu-i-1:
          num+=plu-i-1
          break
        x = A_plu_rev[i]*A_plu[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    cou = 0
    for i in range(0,mi):
      while True:
        if cou>=mi-i-1:
          num+=mi-i-1
          break
        x = A_mi[i]*A_mi_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break

    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    cou = 0
    for a in A_mi_rev:
      while True:
        if cou==plu:
          num+=cou
          break
        x = a*A_plu_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r = m
    else:
      l = m
      
print(r)

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left as bl

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

    inf = 10**18+1

    ok = -inf
    ng = inf
    start_0 = bl(a, 0)
    start_1 = bl(a, 1)

    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        now = n
        for i in a[:start_0]:
            while now > 0:
                if i*a[now-1] < mid:
                    now -= 1
                else:
                    break
            cnt += n - now
        now = n
        for i in a[start_1:]:
            while now > 0:
                if i*a[now-1] >= mid:
                    now -= 1
                else:
                    break
            cnt += now
        if mid > 0:
            cnt += n * (start_1 - start_0)
        cnt -= len([None for i in a if i*i < mid])
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Submission status: Wrong Answer

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

pos = []
neg = []
zero = []

A.sort()

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] == 0:
        zero.append(A[i])
    else:
        neg.append(A[i])
        
import bisect


#条件に合うものを重複して数えて後から重複しない組み合わせに変換
def fun(x):
    count = 0
    #xが0より大きいとき、後ろにある0は何個あるか
    if x >= 0:
        count += len(zero)*N
    #xを正で割ったとき、Aの中に何個それより大きいものがあるか
    for i in range(len(pos)):
        count += bisect.bisect_right(A,x//pos[i])
    #xを負で割ったとき、Aの中に何個それより小さいものがあるか(符合が逆転)
    #x+1にする(同じ数字がAにあるから)
    for i in range(len(neg)):
        count += N - bisect.bisect_right(A,(x+1)//neg[i])
    #条件に合う同じ要素を選ぶものを除く    
    for i in range(len(pos)):
        if x >= pos[i]**2:
            count-=1
    for i in range(len(neg)):
        if x >= neg[i]**2:
            count-=1
    #半分にすれば重複しない組み合わせになる        
    return count//2

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

#二分探索する
while right - left > 1:
    mid = (left+right)//2
    
    if fun(mid) >= K:
        right = mid
    else:
        left = mid
        
print(right)

Submission status: Wrong Answer

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

A.sort()
        
pos = [A[i] for i in range(N) if A[i] > 0]
neg = [A[i] for i in range(N) if A[i] < 0]
zero = [A[i] for i in range(N) if A[i] == 0]

import bisect

def fun(x):
    count = 0
    
    if x >= 0:
        count += len(zero)*N
        
    for i in range(len(pos)):
        count += bisect.bisect_right(A,x//pos[i])
        
    for i in range(len(neg)):
        count += N*len(neg) - bisect.bisect_left(A,x//neg[i])
        
    for i in range(len(A)):
        if x >= A[i]**2:
            count-=1
            
    return count//2

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

while right - left > 1:
    mid = (left+right)//2
    
    if fun(mid) >= K:
        right = mid
    else:
        left = mid
        
print(right)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
num_list = [int(i) for i in input().split()]
num_list = np.array(num_list)
num_list.sort()

neg = num_list[num_list < 0]
pos = num_list[num_list > 0]
zero =  num_list[num_list == 0]

def count(x):
    ans = 0
    if x >= 0:
        ans += len(zero) * n
    ans += np.searchsorted(num_list, x // pos, side="right").sum()
    ans += n * len(neg) - np.searchsorted(num_list, -(-x // neg), side="right").sum()
    ans -= np.count_nonzero(num_list * num_list <= x)
    return ans // 2

left = -(10 ** 18)
right = 10 ** 18

while left + 1 < right:
    mid = (left + right) // 2
    if count(mid) >= k:
        right = mid
    else:
        left = mid

print(right)

Submission status: Wrong Answer

Solution code:
import bisect

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

INF = 10**18 + 1
def count(A, a, x):
    if a < 0:
        A = sorted(A, reverse=True)

    l = 0
    r = len(A)
    c = (l + r) // 2

    while(l + 1 < r):
        if A[c] * a < x:
            l = c
        else:
            r = c
        c = (l + r) // 2

    return l + 1

def allCount(A, x):
    cnt = 0
    notCnt = 0
    for a in A:
        cnt += count(A, a, x)
        if a * a < x:
            notCnt += 1
    cnt = (cnt - notCnt) / 2

    return cnt

l = -INF
r = INF
c = (l + r) // 2

while l + 1 < r:
    cnt = allCount(A, c)
    if cnt < K:
        l = c
    else:
        r = c

    c = (l + r) // 2

print(c)

Submission status: Wrong Answer

Solution code:
import bisect

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

INF = 10**20
def count(A, a, x):
    if a < 0:
        A = sorted(A, reverse=True)

    l = 0
    r = len(A)
    c = (l + r) // 2

    while(l + 1 < r):
        if A[c] * a < x:
            l = c
        else:
            r = c
        c = (l + r) // 2

    return l + 1

def allCount(A, x):
    cnt = 0
    notCnt = 0
    for a in A:
        cnt += count(A, a, x)
        if a * a < x:
            notCnt += 1
    cnt = (cnt - notCnt) / 2

    return cnt

l = -INF
r = INF
c = (l + r) // 2

while l + 1 < r:
    cnt = allCount(A, c)
    if cnt < K:
        l = c
    else:
        r = c

    c = (l + r) // 2

print(c)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mA, nA = [], []
for a in A:
    if a < 0:
        mA.append(a)
    else:
        nA.append(a)
mA = sorted(mA)[::-1]
nA = sorted(nA)
lnA = len(nA)
lmA = len(mA)


def F(k):
    # k以下の数
    # positive positive
    r = 0
    i, j = 0, lnA-1
    while i < lnA:
        while j >= 0 and nA[j]*nA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # negative negative
    i, j = 0, lmA-1
    while i < lmA:
        while j >= 0 and mA[j]*mA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # positive negative
    i, j = 0, lmA-1
    while i < lnA:
        while j >= 0 and mA[j]*nA[i] <= k:
            j -= 1
        r += 2*(lmA-j-1)
        i += 1
    for a in A:
        if a*a <= k:
            r -= 1
    return r//2


mx, mn = 2*10**18, -2*10**18
target = K
while mx-mn > 1:
    idx = (mx+mn)//2
    if F(idx) < target:
        mn = idx
    else:
        mx = idx
print(idx+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
zeros = 0
for a in A:
    if a > 0:
        pos.append(a)
    elif a < 0:
        neg.append(a)
    else:
        zeros += 1

pos.sort()
neg.sort(reverse=True)

minus_pattern = len(pos) * len(neg)
zero_pattern = zeros * (len(pos)+len(neg)) + (zeros*(zeros-1))//2

pos_length = len(pos)
neg_length = len(neg)

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

while left + 1 < right:
    num = (left+right)//2
    less_count = 0

    if num >= 0:
        pos_idx = pos_length-1
        for p in pos:
            while pos_idx >= 0 and p * pos[pos_idx] > num:
                pos_idx -= 1
            less_count += pos_idx + 1
            if p**2 <= num:
                less_count -= 1

        neg_idx = neg_length-1
        for m in neg:
            while neg_idx >= 0 and m * neg[neg_idx] > num:
                neg_idx -= 1
            less_count += neg_idx + 1
            if m**2 <= num:
                less_count -= 1

        less_count //= 2
        less_count += minus_pattern + zero_pattern

    elif num < 0:
        pos_idx = pos_length - 1
        for m in neg[::-1]:
            while pos_idx >= 0 and m * pos[pos_idx] > num:
                pos_idx -= 1
            less_count += pos_idx + 1

    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Wrong Answer

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

pos = []
neg = []
zero = []

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] == 0:
        zero.append(A[i])
    else:
        neg.append(A[i])
        
A.sort()

import bisect

def fun(x):
    count = 0
    
    if x >= 0:
        count += len(zero)*N
        
    for i in range(len(pos)):
        count += bisect.bisect_right(A,x//pos[i])
        
    for i in range(len(neg)):
        count += N - bisect.bisect_left(A,x//neg[i])
        
    for i in range(len(A)):
        if x >= A[i]**2:
            count-=1
            
    return count//2

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

while right - left > 1:
    mid = (left+right)//2
    
    if fun(mid) >= K:
        right = mid
    else:
        left = mid
        
print(right)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
zeros = 0
for a in A:
    if a > 0:
        pos.append(a)
    elif a < 0:
        neg.append(a)
    else:
        zeros += 1

pos.sort()
neg.sort(reverse=True)

minus_pattern = len(pos) * len(neg)
zero_pattern = zeros * (len(pos)+len(neg)) + (zeros*(zeros-1))//2

pos_length = len(pos)
neg_length = len(neg)

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

while left + 1 < right:
    num = (left+right)//2
    less_count = 0

    if num >= 0:
        pos_idx = pos_length-1
        for p in pos:
            limit_pair = num // p
            while pos_idx >= 0 and pos[pos_idx] > limit_pair:
                pos_idx -= 1
            less_count += pos_idx + 1
            if p**2 <= num:
                less_count -= 1

        neg_idx = neg_length-1
        for m in neg:
            limit_pair = num // m + bool(num % m)
            while neg_idx >= 0 and neg[neg_idx] < limit_pair:
                neg_idx -= 1
            less_count += neg_idx + 1
            if m**2 <= num:
                less_count -= 1

        less_count //= 2
        less_count += minus_pattern + zero_pattern

    elif num < 0:
        pos_idx = pos_length - 1
        for m in neg:
            limit_pair = num // m + bool(num % m)
            while pos_idx >= 0 and pos[pos_idx] < limit_pair:
                pos_idx -= 1
            less_count += pos_idx + 1

    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Wrong Answer

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

pos = []
neg = []
zero = []

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] == 0:
        zero.append(A[i])
    else:
        neg.append(A[i])
        
A.sort()

import bisect

def fun(x):
    count = 0
    
    if x >= 0:
        count += len(zero)*N
        
    for i in range(len(pos)):
        count += bisect.bisect_right(A,x//pos[i])
        
    for i in range(len(neg)):
        count += N - bisect.bisect_right(A,x//neg[i])
        
    for i in range(len(A)):
        if x >= A[i]**2:
            count-=1
            
    return count//2

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

while right - left > 1:
    mid = (left+right)//2
    
    if fun(mid) >= K:
        right = mid
    else:
        left = mid
        
print(right)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
zeros = 0
for a in A:
    if a > 0:
        pos.append(a)
    elif a < 0:
        neg.append(a)
    else:
        zeros += 1

pos.sort()
neg.sort(reverse=True)

minus_pattern = len(pos) * len(neg)
zero_pattern = zeros * (len(pos)+len(neg)) + (zeros*(zeros-1))//2

pos_length = len(pos)
neg_length = len(neg)

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

while left + 1 < right:
    num = (left+right)//2
    less_count = 0

    if num >= 0:
        pos_idx = pos_length-1
        for p in pos:
            while pos_idx >= 0 and p * pos[pos_idx] > num:
                pos_idx -= 1
            less_count += pos_idx + 1
            if p**2 <= num:
                less_count -= 1

        neg_idx = neg_length-1
        for m in neg:
            while neg_idx >= 0 and m * neg[neg_idx] > num:
                neg_idx -= 1
            less_count += neg_idx + 1
            if m**2 <= num:
                less_count -= 1

        less_count //= 2
        less_count += minus_pattern + zero_pattern

    elif num < 0:
        pos_idx = pos_length - 1
        for m in neg:
            while pos_idx >= 0 and m * pos[pos_idx] > num:
                pos_idx -= 1
            less_count += pos_idx + 1

    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
zeros = 0
for a in A:
    if a > 0:
        pos.append(a)
    elif a < 0:
        neg.append(a)
    else:
        zeros += 1

pos.sort()
neg.sort(reverse=True)

minus_pattern = len(pos) * len(neg)
zero_pattern = zeros * (len(pos)+len(neg)) + (zeros*(zeros-1))//2

pos_length = len(pos)
neg_length = len(neg)

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

while left + 1 < right:
    num = (left+right)//2
    less_count = 0

    if num >= 0:
        pos_idx = pos_length-1
        for p in pos:
            while pos_idx >= 0 and p * pos[pos_idx] > num:
                pos_idx -= 1
            less_count += pos_idx + 1
            if p**2 <= num:
                less_count -= 1

        neg_idx = neg_length-1
        for m in neg:
            while neg_idx >= 0 and m * neg[neg_idx] > num:
                neg_idx -= 1
            less_count += neg_idx + 1
            if m**2 <= num:
                less_count -= 1

        less_count //= 2
        less_count += minus_pattern + zero_pattern

    elif num < 0:
        pos_idx = pos_length - 1
        for m in neg:
            while pos_idx >= 0 and m * pos[pos_idx] > num:
                pos_idx -= 1
            less_count += pos_idx + 1

    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
A = np.array(input().split(), np.int64)

A.sort()

posA = A[A>0]
negA = A[A<0]
zeros = A[A==0]

def solve(x):
    less_count = 0
    
    if x > 0:
        less_count += len(zeros) * n
    less_count += np.searchsorted(A, x / posA, side='left').sum()
    less_count += (n - np.searchsorted(A, x / negA, side='right')).sum()
    less_count -= np.count_nonzero(A * A < x)
    
    return less_count // 2

const = 10**18 + 1
left = -const
right = const

while left + 1 < right:
    x = (left + right) // 2
    print(left, right, solve(x))
    if solve(x) < k:
        left = x
    else:
        right = x

print(left)