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 comb(li):
    return len(li) * (len(li) - 1) // 2


def count_small(x, li):
    cnt = 0
    j = len(li)
    for i, e in enumerate(li[1:], 1):
        while li[j-1] * e > x:
            j -= 1
        cnt += min(i - 1, j - 1)

    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n - comb(pos) - comb(neg) + 1:
    k -= len(pos) * len(neg)
    cnt0 = a.count(0)
    k -= cnt0 * (n - 1) - cnt0 * (cnt0 - 1) // 2
    neg = [-e for e in neg]
    neg.sort()
    neg.insert(0, 0)
    pos.sort()
    pos.insert(0, 0)

    lb = 0
    ub = 10 ** 18
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_small(m, neg) + count_small(m, pos)
        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is 0
else:
    print(0)

Submission status: Wrong Answer

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

A.sort()
left = -10**9
right = 10**9

while right - left > 1:
    x = (right + left) // 2
    S = 0
    T = 0
    for i in range(N):
        if A[i] > 0:
            l2 = -1
            r2 = N
            while r2 - l2 > 1:
                m = (r2 + l2) // 2
                if A[i] * A[m] <= x:
                    l2 = m
                else:
                    r2 = m
            S += r2
        elif A[i] < 0:
            l2 = -1
            r2 = N
            while r2 - l2 > 1:
                m = (r2 + l2) // 2
                if A[i] * A[m] <= x:
                    r2 = m
                else:
                    l2 = m
            S += N - r2
        elif x >= 0:
            S += N
            
        if A[i]**2 <= x:
            T += 1
    num = (S - T) // 2
    if num >= K:
        right = x
    else:
        left = x
        
print(right)

Submission status: Wrong Answer

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

A.sort()
print(A)
left = -10**9
right = 10**9

while right - left > 1:
    x = (right + left) // 2
    print(x)
    S = 0
    T = 0
    for i in range(N):
        if A[i] > 0:
            l2 = -1
            r2 = N
            while r2 - l2 > 1:
                m = (r2 + l2) // 2
                if A[i] * A[m] <= x:
                    l2 = m
                else:
                    r2 = m
            S += r2
        elif A[i] < 0:
            l2 = -1
            r2 = N
            while r2 - l2 > 1:
                m = (r2 + l2) // 2
                if A[i] * A[m] <= x:
                    r2 = m
                else:
                    l2 = m
            S += N - r2
        elif x >= 0:
            S += N
            
        if A[i]**2 <= x:
            T += 1
    num = (S - T) // 2
    if num >= K:
        right = x
    else:
        left = x
        
print(right)

Submission status: Wrong Answer

Solution code:
# 親の顔より見たPairs
# 小さい順に見てk番目
# x以下の数がk個以上となる最小のxを求める
# x以下の数がk個以上かつx−1以下の数はk個未満
from bisect import bisect_left, bisect_right
import sys

input = sys.stdin.buffer.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

minus_num = bisect_left(A, 0)
zero_num = bisect_right(A, 0) - minus_num
plus_num = n - (minus_num + zero_num)

seki_minus = plus_num * minus_num
seki_plus = plus_num * (plus_num - 1) // 2 + minus_num * (minus_num - 1) // 2
seki_zero = zero_num * (plus_num + minus_num) + zero_num * (zero_num - 1) // 2
assert seki_minus + seki_plus + seki_zero == n * (n - 1) // 2

mA = A[:minus_num]
pA = A[-plus_num:]


# ある数以下のものが何個有るかを返す関数
def calc(num):
    res = 0
    if num < 0:
        lim = minus_num - 1
        for i in range(plus_num):
            while lim >= 0:
                if mA[lim] * pA[i] > num:
                    lim -= 1
                else:
                    break
            res += lim + 1
    elif num == 0:
        res = seki_zero + seki_minus
    else:
        # pA
        lim = plus_num - 1
        for i in range(plus_num):
            while lim >= 0:
                if pA[lim] * pA[i] > num:
                    lim -= 1
                else:
                    break
            if lim >= i:
                res -= 1
            res += lim + 1
        # mA
        lim = minus_num - 1
        mmA = mA[::-1]
        for i in range(minus_num):
            while lim >= 0:
                if mmA[lim] * mmA[i] > num:
                    lim -= 1
                else:
                    break
            if lim >= i:
                res -= 1
            res += lim + 1
        assert res % 2 == 0
        res //= 2
        res += seki_minus
        res += seki_zero
    return res


ok = 10 ** 20
ng = -(10 ** 20)

while ok - ng > 1:
    mid = (ok + ng) // 2
    if calc(mid) >= k:
        ok = mid
    else:
        ng = mid
    # print(ok, ng)


print(ok)

Submission status: Wrong Answer

Solution code:
import bisect
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
P = sorted(a for a in A if a > 0)
M = sorted(-a for a in A if a < 0)
lp = len(P)
lm = len(M)
lz = N - lp - lm
if K < lp * lm:
    #PとMの積でmid以上のものがK個以上あるかどうか
    def check(x):
        a = 0
        for p in P:
            a += lm - bisect.bisect_left(M, (x - 1) // p + 1)
        return a <= K

    lb = 0
    rb = 10**18 + 1
    # Min x for check(x) == True
    while rb - lb > 1:
        mid = (rb + lb) // 2
        if check(mid):
            rb = mid
        else:
            lb = mid
    print(-lb)

elif K < N * (N - 1) // 2 - lp * (lp - 1) // 2 - lm * (lm - 1) // 2:
    print(0)
else:
    K -= N * (N - 1) // 2 - lp * (lp - 1) // 2 - lm * (lm - 1) // 2

    #P*P or M*M でmid以下のものがK個以上あるかどうか
    def check(x):
        a = 0
        for i, p in enumerate(P):
            a += max(i + 1, bisect.bisect_left(P, (x - 1) // p + 1)) - i - 1
        for i, m in enumerate(M):
            a += max(i + 1, bisect.bisect_left(M, (x - 1) // m + 1)) - i - 1
        return a >= K

    lb = 0
    rb = 10**18 + 1
    # Min x for check(x) == True
    while rb - lb > 1:
        mid = (rb + lb) // 2
        if check(mid):
            rb = mid
        else:
            lb = mid
    print(lb)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def solve():
    def max2(x, y): return x if x >= y else y

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

    As.sort()

    iGE0 = bisect_left(As, 0)
    iGT0 = bisect_right(As, 0)

    ANegs = As[:iGE0]
    APoss = As[iGT0:]
    num0 = iGT0 - iGE0
    numNeg = len(ANegs)
    numPos = len(APoss)

    def isOK(X):
        if X == 0:
            num = (num0+numNeg) * (num0+numPos) - num0*(num0+1)//2
        elif X < 0:
            num = 0
            for A in ANegs:
                j = bisect_left(APoss, -(-X // A))
                num += numNeg-j
        else:
            num = (num0+numNeg) * (num0+numPos) - num0*(num0+1)//2
            for i, A in enumerate(APoss):
                j = bisect_right(APoss, X//A)
                if j > i:
                    num += j-i-1
            for i, A in enumerate(ANegs):
                j = bisect_left(ANegs, -(-X // A))
                num += numNeg-max2(i+1, j)
        return num >= K

    ng, ok = -10**18-1, 10**18+1
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def solve():
    def max2(x, y): return x if x >= y else y

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

    As.sort()

    iGE0 = bisect_left(As, 0)
    iGT0 = bisect_right(As, 0)

    ANegs = As[:iGE0]
    APoss = As[iGT0:]
    num0 = iGT0 - iGE0
    numNeg = len(ANegs)
    numPos = len(APoss)

    def isOK(X):
        if X == 0:
            num = (num0+numNeg) * (num0+numPos) - num0*(num0+1)//2
        elif X < 0:
            num = 0
            for A in ANegs:
                j = bisect_left(APoss, -(-X // A))
                num += numNeg-j
        else:
            num = (num0+numNeg) * (num0+numPos) - num0*(num0+1)//2
            for i, A in enumerate(APoss):
                j = bisect_right(APoss, X//A)
                if j > i:
                    num += j-i-1
            for i, A in enumerate(ANegs):
                j = bisect_right(ANegs, -(-X // A))
                num += numNeg-max2(i+1, j)
        return num >= K

    ng, ok = -10**18-1, 10**18+1
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()

Submission status: Wrong Answer

Solution code:
from bisect import *
N,K=map(int,input().split())
A=list(map(int,input().split()))
X=[0]*3
Y=[0]*3
Z=[[],[],[]]
for i in range(N):
  if A[i]<0:
    X[0]+=1
    Z[0].append(A[i])
  elif A[i]==0:
    X[1]+=1
    Z[1].append(0)
  else:
    X[2]+=1
    Z[2].append(A[i])
Y[1]=X[1]*(N-1)-((X[1]-1)*X[1])//2
Y[0]=X[0]*X[2]
Y[2]=(N*(N-1))//2-Y[1]-Y[0]
A.sort()
if Y[0]<K and Y[0]+Y[1]>=K:
  print(0)
  exit()
L,R,M,C,l,r,m=-(10**18),10**18,0,0,0,0,0
if Y[0]>=K:
  R=-1
else:
  L=1
while R>L:
  M=(L+R+1)//2
  C=0
  if M:
    for i in range(N):
      if A[i]==0:
        continue
      if A[i]>0:
        l,r,m=0,N,0
        while l<r:
          m=(l+r)//2
          if A[i]*A[m]<M:
            l=max(m,l+1)
          else:
            r=m
        C+=N-l
      if A[i]<0:
        l,r,m=0,N,0
        while l<r:
          m=(l+r)//2
          if A[i]*A[m]<M:
            r=m
          else:
            l=max(m,l+1)
        C+=l
      if A[i]**2>=M:
        C-=1
  else:
    C=(Y[1]+Y[0])*2
  C=C//2
  if (N*(N-1)//2)-C>=K:
    R=min(M,R-1)
  else:
    L=M
print(L)

Submission status: Wrong Answer

Solution code:
from bisect import *
N,K=map(int,input().split())
A=list(map(int,input().split()))
X=[0]*3
Y=[0]*3
Z=[[],[],[]]
for i in range(N):
  if A[i]<0:
    X[0]+=1
    Z[0].append(A[i])
  elif A[i]==0:
    X[1]+=1
    Z[1].append(0)
  else:
    X[2]+=1
    Z[2].append(A[i])
Y[1]=X[1]*(N-1)-((X[1]-1)*X[1])//2
Y[0]=X[0]*X[2]
Y[2]=(N*(N-1))//2-Y[1]-Y[0]
A.sort()
if Y[0]<K and Y[0]+Y[1]>=K:
  print(0)
  exit()
L,R,M,C,l,r,m=-(10**18),10**18,0,0,0,0,0
while R>L:
  M=(L+R+1)//2
  C=0
  if M:
    for i in range(N):
      if A[i]==0:
        continue
      if A[i]>0:
        l,r,m=0,N,0
        while l<r:
          m=(l+r)//2
          if A[i]*A[m]<M:
            l=max(m,l+1)
          else:
            r=m
        C+=N-l
      if A[i]<0:
        l,r,m=0,N,0
        while l<r:
          m=(l+r)//2
          if A[i]*A[m]<M:
            r=m
          else:
            l=max(m,l+1)
        C+=l
      if A[i]**2>=M:
        C-=1
  else:
    C=(Y[1]+Y[0])*2
  C=C//2
  if (N*(N-1)//2)-C>=K:
    R=min(M,R-1)
  else:
    L=M
print(L)

Submission status: Wrong Answer

Solution code:
from bisect import *
N,K=map(int,input().split())
A=list(map(int,input().split()))
X=[0]*3
Y=[0]*3
Z=[[],[],[]]
for i in range(N):
  if A[i]<0:
    X[0]+=1
    Z[0].append(A[i])
  elif A[i]==0:
    X[1]+=1
    Z[1].append(0)
  else:
    X[2]+=1
    Z[2].append(A[i])
Y[1]=X[1]*(N-1)-((X[1]-1)*X[1])//2
Y[0]=X[0]*X[2]
Y[2]=(N*(N-1))//2-Y[1]-Y[0]
A.sort()
if Y[0]<K and Y[0]+Y[1]>=K:
  print(0)
  exit()
L,R,M,C,l,r,m=-(10**18),10**18,0,0,0,0,0
while R>L:
  M=(L+R+1)//2
  C=0
  if M:
    for i in range(N):
      if A[i]==0:
        continue
      if A[i]>0:
        l,r,m=0,N,0
        while l<r:
          m=(l+r)//2
          if A[i]*A[m]<M:
            l=max(m,l+1)
          else:
            r=m
        C+=N-l
      if A[i]<0:
        l,r,m=0,N,0
        while l<r:
          m=(l+r)//2
          if A[i]*A[m]<M:
            r=m
          else:
            l=max(m,l+1)
        C+=l
      if A[i]**2>=M:
        C-=1
  else:
    C=Y[1]*2
  C=C//2
  if (N*(N-1)//2)-C>=K:
    R=min(M,R-1)
  else:
    L=M
print(L)

Submission status: Wrong Answer

Solution code:
from bisect import *
N,K=map(int,input().split())
A=list(map(int,input().split()))
X=[0]*3
Y=[0]*3
Z=[[],[],[]]
for i in range(N):
  if A[i]<0:
    X[0]+=1
    Z[0].append(A[i])
  elif A[i]==0:
    X[1]+=1
    Z[1].append(0)
  else:
    X[2]+=1
    Z[2].append(A[i])
Y[1]=X[1]*(N-1)-((X[1]-1)*X[1])//2
Y[0]=X[0]*X[2]
Y[2]=(N*(N-1))//2-Y[1]-Y[0]
A.sort()
if Y[0]<K and Y[0]+Y[1]>=K:
  print(0)
L,R,M,C,l,r,m=-(10**18),10**18,0,0,0,0,0
while R>L:
  M=(L+R+1)//2
  C=0
  if M:
    for i in range(N):
      if A[i]==0:
        continue
      if A[i]>0:
        l,r,m=0,N,0
        while l<r:
          m=(l+r)//2
          if A[i]*A[m]<M:
            l=max(m,l+1)
          else:
            r=m
        C+=N-l
      if A[i]<0:
        l,r,m=0,N,0
        while l<r:
          m=(l+r)//2
          if A[i]*A[m]<M:
            r=m
          else:
            l=max(m,l+1)
        C+=l
      if A[i]**2>=M:
        C-=1
  else:
    C=Y[1]*2
  C=C//2
  if (N*(N-1)//2)-C>=K:
    R=min(M,R-1)
  else:
    L=M
print(L)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
squ = [a**2 for a in A]

def is_ok(x):
    cnt = 0
    for i in range(N):
        if A[i] == 0:
            if x >= 0:
                cnt += N
        elif A[i] > 0:
            cnt += bisect_right(A, x//A[i]) + 1
        else:
            cnt += N - bisect_left(A, x//A[i])
    cnt -= bisect_left(squ, x) + 1
    if cnt >= K:
        return True
    else:
        return False

ok = 10**18
ng = -10**18
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

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

def check(x):
    cnt = 0
    for a in A:
        if a == 0:
            if x >= 0:
                cnt += n
        elif a > 0:
            cnt += bisect.bisect_right(A, x//a)
        elif a < 0:
            cnt += n - bisect.bisect_left(A, (x+a-1)//a)
        if a*a < x:
            cnt -= 1
    return cnt < k*2

l, r = -10**18-10, 10**18+10
while (r-l)>1:
    m = (l+r)//2
    if check(m):
        l = m
    else:
        r = m
print(r)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
import bisect
A=list(map(int,input().split()))
A.sort()
plus,minus,zero=0,0,0
D=[[] for i in range(2)]
for i in range(N):
    if A[i]>0:
        plus+=1
        D[0].append(A[i])
    elif A[i]==0:
        zero+=1        
    else:
        minus+=1
        D[1].append(A[i])
        
D[0].sort()
D[1].sort()

# <0 =0 >0
def count(X):
    cnt=0
    #X以下の数を探す
    if X>=0:
        cnt+=zero*(plus+minus)
        cnt+=plus*minus
        cnt+=zero*(zero-1)//2
        if X==0:
            return cnt          
        for i in range(len(D[0])):         
                cnt+=max(0,bisect.bisect_right(D[0],X/D[0][i]+10**(-9))-i-1)                
        for i in range(len(D[1])):
                cnt+=len(D[1])-max(i+1,bisect.bisect_right(D[1],X/D[1][i]-10**(-9)))
        return cnt
    elif X<0:
        for  a in D[0]:
            cnt+=bisect.bisect_right(D[1],X/a+10**(-9))
        return cnt
l=-10**18
r=10**18

#count(r)>=K,count(l)<K
while r-l>1:
    M=(l+r)//2
    if count(M)>=K:
        r=M
    else:
        l=M

print(r)

Submission status: Wrong Answer

Solution code:
# 小さい方からk番目がx
# x以下がk個以上となる最小のx
from bisect import bisect_left, bisect_right

import sys

input = sys.stdin.buffer.readline

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

A.sort()
minusA = bisect_left(A, 0)
mA = A[:minusA]
mmA = mA[::-1]
zeroA = bisect_right(A, 0) - bisect_left(A, 0)
plusA = n - minusA - zeroA
pA = A[-plusA:]
minus = minusA * plusA
zero = zeroA * (zeroA - 1) // 2 + (n - zeroA) * zeroA
plus = n * (n - 1) // 2 - zero - minus


# x以下の数を数える
def calc(x):
    global mmA
    res = 0
    if x > 0:
        lim = plusA - 1
        for i in range(plusA):
            while lim >= 0:
                if pA[i] * pA[lim] > x:
                    lim -= 1
                else:
                    break
            res += lim + 1
            if lim >= i:
                res -= 1
        lim = minusA - 1
        mmA = mA[::-1]
        for i in range(minusA):
            while lim >= 0:
                if mmA[i] * mmA[lim] > x:
                    lim -= 1
                else:
                    break
            res += lim + 1
            if lim >= i:
                res -= 1
        res //= 2
        res += minus + zero
    elif x == 0:
        res += minus + zero
    else:
        # 正の数、左絶対値小さい
        # 負の数、左絶対値大きい
        lim = 0
        for i in range(plusA):
            while lim < minusA:
                if pA[i] * mmA[lim] <= x:
                    lim += 1
                else:
                    break
            res += lim
    return res


ng = -(10 ** 20)
ok = 10 ** 20
while ok - ng > 1:
    mid = (ok + ng) // 2
    if calc(mid) >= k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Wrong Answer

Solution code:
# 小さい方からk番目がx
# x以下がk個以上となる最小のx
from bisect import bisect_left, bisect_right

import sys

input = sys.stdin.buffer.readline

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

A.sort()
minusA = bisect_left(A, 0)
mA = A[:minusA]
mmA = mA[::-1]
zeroA = bisect_right(A, 0) - bisect_left(A, 0)
plusA = n - minusA - zeroA
pA = A[-plusA:]
minus = minusA * plusA
zero = zeroA * (zeroA - 1) // 2 + (n - zeroA) * zeroA
plus = n * (n - 1) // 2 - zero - minus


# x以下の数を数える
def calc(x):
    global mmA
    res = 0
    if x > 0:
        lim = plusA - 1
        for i in range(plusA):
            while lim >= 0:
                if pA[i] * pA[lim] > x:
                    lim -= 1
                else:
                    break
            res += lim + 1
            if lim >= i:
                res -= 1
        lim = minusA - 1
        mmA = mA[::-1]
        for i in range(minusA):
            while lim >= 0:
                if mmA[i] * mmA[lim] > x:
                    lim -= 1
                else:
                    break
            res += lim + 1
            if lim >= i:
                res -= 1
        res //= 2
        res += minus + zero
    elif x == 0:
        res += minus + zero
    else:
        # 正の数、左絶対値小さい
        # 負の数、左絶対値大きい
        lim = 0
        for i in range(plusA):
            while lim < minusA:
                if pA[i] * mmA[lim] <= x:
                    lim += 1
                else:
                    break
            res += lim
    return res


ng = -(10 ** 20)
ok = 10 ** 20
while ok - ng > 1:
    mid = (ok + ng) // 2
    if calc(mid) >= k:
        ok = mid
    else:
        ng = mid
    print(mid)
    print(calc(mid))
print(ok)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    nA=[]

    zcount=0
    for a in A:
        if a!=0:
            nA.append(a)
        else:
            zcount+=1
    A=nA
    A.sort()
    smin=-10**18-1
    smax=10**18
    la=len(A)
    
    def f(n):
        tot=0
        
        for a in A:  
            if a>0:
                tot+=bisect_right(A,math.floor(n/a))
                if a*a<=n:
                    tot-=1
            else:
                tot+=la-bisect_left(A,math.ceil(n/a))
                if a*a<=n:
                    tot-=1

        #print(n,tot,tot*0.5, n/a)
        tot=tot//2
        if n>=0:
            tot+=(zcount*(zcount-1))//2+zcount*la
        
        return tot>=K



    while smax-smin>1:
        mid=int((smin+smax)//2)
        flag=f(mid)
        #print(mid,flag)
        if flag:
            smax=mid
        else:
            smin=mid
        #print(mid,flag)
    print(smax)
    #print(f(448283280358331063))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 解説を参考に作成


# import sys
# sys.setrecursionlimit(10 ** 6)
def cmb(n, r):
    import math
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, K, As):
    As.sort()  # 破壊的～
    # -X, 0, +X に分類
    minus = []
    zero = []
    plus = []
    for A in As:
        if A > 0:
            plus.append(A)
        elif A < 0:
            minus.append(A)
        else:
            zero.append(A)
    # -X, 0, +X のパターンの数を算出
    under_zero = len(minus) * len(plus)
    just_zero = len(zero) * (len(minus) + len(plus)) + cmb(len(zero), 2)
    over_zero = cmb(len(minus), 2) + cmb(len(plus), 2)
    # -X, ..., 0, ..., + X の順番に並んでいることになるので、3パターンで場合分け
    ans = 0
    # print(minus)
    # print(zero)
    # print(plus)
    # print(under_zero, just_zero, over_zero)
    # 場合分け① 0 の番号なら0を出力
    if under_zero < K <= under_zero + just_zero:
        ans = 0
    # 場合分け② -X の番号なら、負の数となる組み合わせから二部探索
    elif K <= under_zero:
        upper = -1
        lower = - 10 ** 18
        while True:
            middle = (upper + lower) // 2
            c = 0
            p = 1
            sub = - float('inf')
            for m in minus:
                while p < len(plus) - 1 and plus[p] * m > middle:
                    p += 1
                # print(p, m)
                if plus[p] * m <= middle:
                    c += len(plus) - (p - 1)
                    sub = max(sub, plus[p] * m)
            # print(c, lower, middle, upper)
            # input()
            if c < K:
                if abs(lower - middle) == 0:
                    upper = upper + 1
                lower = middle
            elif c > K:
                if abs(upper - middle) == 1:
                    ans = sub
                    break
                upper = middle
            else:
                ans = sub
                break
    # 場合分け③ +X の番号なら、正の数となる組み合わせから二部探索
    else:
        upper = 10 ** 18
        lower = 1
        minus = sorted([- i for i in minus])
        re_plus = list(reversed(plus))
        re_minus = list(reversed(minus))
        while True:
            middle = (upper + lower) // 2
            c = 0
            cm = 0
            sub = - float('inf')
            # 正 * 正
            p2 = 0
            for p in re_plus:
                while p2 < len(plus) - 1 and plus[p2 + 1] * p <= middle:
                    p2 += 1
                if plus[p2] * p <= middle:
                    cm += p2 + 1
                    sub = max(sub, plus[p2 if plus[p2] != p else p2 - 1] * p)
                    if p ** 2 <= middle:
                        cm -= 1  # 重複分を削除
            c += cm // 2
            # 負 * 負
            cm = 0
            m2 = 0
            for m in re_minus:
                while m2 < len(minus) - 1 and minus[m2 + 1] * m <= middle:
                    m2 += 1
                if minus[m2] * m <= middle:
                    cm += m2 + 1
                    sub = max(sub, minus[m2 if minus[m2] != m else m2 - 1] * m)
                    if m ** 2 <= middle:
                        cm -= 1  # 重複分を削除
            c += cm // 2
            # print(c, lower, middle, upper)
            # print(K - under_zero - just_zero)
            # input()
            # 個数判定
            if c < K - under_zero - just_zero:
                if abs(lower - middle) == 0:
                    upper = upper + 1
                lower = middle
            elif c > K - under_zero - just_zero:
                if abs(upper - middle) == 1:
                    ans = sub
                    break
                upper = middle
            else:
                ans = sub
                break
    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    As = [int(i) for i in input().split()]
    solve(N, K, As)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = map(int, input().split())
a = list(map(int, input().split()))
ma = []
pa = []
zc = 0
for num in a:
    if num<0:
        ma.append(num)
    elif num>0:
        pa.append(num)
    else:
        zc += 1
mn = len(ma)*len(pa)
ma.sort()
pa.sort()
ma =ma[::-1]

def _sub(m, l1):
    lp = len(l1)
    t = lp-1
    ans = 0
    for s in range(lp):
        if t<=s:
            break
        while l1[s]*l1[t]>m and t>s+1:
            t -= 1
        if l1[s]*l1[t]>m:
            break
        ans += (t-s)
    return ans

def sub1(m):
    # 0以上m以下の値の個数
    ans = 0
    ans += _sub(m, pa)
    ans += _sub(m, ma)
    return ans

def sub2(m):
    # 0以下、m以下の値の個数
    ans = 0
    lp = len(pa)
    lm = len(ma)
    t = 0
    for s in range(lp):
        while pa[s]*ma[t]>m and t<lm-1:
            t += 1
        if pa[s]*ma[t]>m:
            break
        ans += lm - t
    return ans

znum = zc*(len(ma)+len(pa)) + (zc-1)*zc//2
if k>mn:
    k -= mn
    if znum>=k:
        ans = 0
    else:
        k -= znum
        l = 0
        r = 10**18+1
        while l<r-1:
            m = (l+r)//2
            v = sub1(m)
            if v>=k:
                r = m
            else:
                l = m
        ans = l+1
else:
    l = -10**18-1
    r = 0
    while l<r-1:
        m = (l+r)//2
        v = sub2(m)
        if v>=k:
            r = m
        else:
            l = m
    ans = l+1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = map(int, input().split())
a = list(map(int, input().split()))
ma = []
pa = []
zc = 0
for num in a:
    if num<0:
        ma.append(num)
    elif num>0:
        pa.append(num)
    else:
        zc += 1
mn = len(ma)*len(pa)
ma.sort()
pa.sort()

from bisect import bisect_right as br, bisect_left as bl
def sub1(m):
    # 0以上m以下の値の個数
    ans = 0
    lm = len(ma)
    for num in pa:
        ans += br(pa, m//num)
        if num*num<=m:
            ans -= 1
    for num in ma:
        ans += (lm - bl(ma, m//num))
        if num*num<=m:
            ans -= 1
    return ans//2
def sub2(m):
    # 0以下、m以下の値の個数
    ans = 0
    lp = len(pa)
    for num in ma:
        ans += (lp - bl(pa, m/num))
    return ans
znum = zc*(len(ma)+len(pa)) + (zc-1)*zc//2
if k>mn:
    k -= mn
    if znum>=k:
        ans = 0
    else:
        k -= znum
        l = 0
        r = 10**18+1
        while l<r-1:
            m = (l+r)//2
            v = sub1(m)
            if v>=k:
                r = m
            else:
                l = m
        ans = l+1
else:
    sub = sub2
    l = -10**18-1
    r = 0
    while l<r-1:
        m = (l+r)//2
        v = sub2(m)
        if v>=k:
            r = m
        else:
            l = m
    ans = l+1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = map(int, input().split())
a = list(map(int, input().split()))
ma = []
pa = []
for num in a:
    if num<0:
        ma.append(num)
    else:
        pa.append(num)
mn = len(ma)*len(pa)
ma.sort()
pa.sort()

from bisect import bisect_right as br, bisect_left as bl
def sub1(m):
    # 0以上m以下の値の個数
    ans = 0
    for num in pa:
        if num==0:
            ans+=len(pa)
        else:
            ans += br(pa, m//num)
        if num*num<=m:
            ans -= 1
    for num in ma:
        ans += (len(ma) - bl(ma, m//num))
        if num*num<=m:
            ans -= 1
    return ans//2
def sub2(m):
    # 0以下、m以下の値の個数
    ans = 0
    for num in ma:
        ans += (len(pa) - bl(pa, m/num))
    return ans
    
if k>mn:
    k -= mn
    l = 0
    r = 10**18+1
    while l<r-1:
        m = (l+r)//2
        v = sub1(m)
        if v>=k:
            r = m
        else:
            l = m
        
else:
    sub = sub2
    l = -10**18-1
    r = 0
    while l<r-1:
        m = (l+r)//2
        v = sub2(m)
        if v>=k:
            r = m
        else:
            l = m

print(l+1)