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:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("YES") if fl else print("NO")
import collections
import math
import itertools
import heapq as hq
def isok1(x,ls1,ls2,cnt=0):
    ##ls1 :minus -1,-2  ls2 :plus 1,2,..
    l1,l2=0,0
    while l1<len(ls1) and l2<len(ls2):
        if ls1[l1]*ls2[l2] <= x:
            cnt+=len(ls2) -l2
            l1+=1
        else:
            l2+=1
    return cnt<k
def isok2(x,ls1,ls2,cnt=0):
    ##ls1 :minus -2,-1,  ls2 :plus 2,1,..
    l,r=0,0
    tmp=0
    while r<len(ls1) and l<len(ls1):
        if ls1[-l-1]*ls1[r] <=x:
            tmp+=len(ls1)-r
            l+=1
        else:
            r+=1
    for i in range(len(ls1)):
        if ls1[i]**2 <=x:tmp-=1
    cnt+=tmp//2
    l,r=0,0
    tmp=0
    while r<len(ls2) and l<len(ls2):
        #print(ls2[-l-1]*ls2[r],l,r)
        if ls2[-l-1]*ls2[r] <=x:
            tmp+=len(ls2)-r
            #print(tmp,ls2[-l-1]*ls2[r],l,r)
            l+=1
        else:
            r+=1
    for i in range(len(ls2)):
        if ls2[i]**2 <=x:tmp-=1
    cnt+=tmp//2
    #print(x,cnt)
    return cnt<k



n,k = ma()
A = lma()
pA = [a for a in A if a>0]
mA = [a for a in A if a<0]
pn = len(mA)*(len(mA)-1)//2 +len(pA)*(len(pA)-1)//2
mn = len(pA) *len(mA)
z = n*(n-1)//2 -pn -mn
if k<=mn:
    f=True
    pA.sort()
    mA.sort(reverse=True)
    print("a")
    exit()
elif k>mn+z:
    f=False
    pA.sort(reverse=True)
    mA.sort()
else:
    print(0)
    exit()
#print(isok2(6,mA,pA,cnt=mn+z))
ok = -10**18-2
ng = 10**18+2
x = (ok+ng)//2

while ng-ok>1:
    if f:
        if isok1(x,mA,pA):
            ok = x
        else:
            ng=x
        x = (ok+ng)//2
    else:
        if isok2(x,mA,pA,cnt=mn+z):
            ok = x
        else:
            ng=x
        x = (ok+ng)//2
print(ng)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("YES") if fl else print("NO")
import collections
import math
import itertools
import heapq as hq
def isok1(x,ls1,ls2,cnt=0):
    ##ls1 :minus -1,-2  ls2 :plus 1,2,..
    l1,l2=0,0
    while l1<len(ls1) and l2<len(ls2):
        if ls1[l1]*ls2[l2] <= x:
            cnt+=len(ls2) -l2
            l1+=1
        else:
            l2+=1
    return cnt<k
def isok2(x,ls1,ls2,cnt=0):
    ##ls1 :minus -2,-1,  ls2 :plus 2,1,..
    l,r=0,0
    tmp=0
    while r<len(ls1) and l<len(ls1):
        if ls1[-l-1]*ls1[r] <=x:
            tmp+=len(ls1)-r
            l+=1
        else:
            r+=1
    for i in range(len(ls1)):
        if ls1[i]**2 <=x:tmp-=1
    cnt+=tmp//2
    l,r=0,0
    tmp=0
    while r<len(ls2) and l<len(ls2):
        #print(ls2[-l-1]*ls2[r],l,r)
        if ls2[-l-1]*ls2[r] <=x:
            tmp+=len(ls2)-r
            #print(tmp,ls2[-l-1]*ls2[r],l,r)
            l+=1
        else:
            r+=1
    for i in range(len(ls2)):
        if ls2[i]**2 <=x:tmp-=1
    cnt+=tmp//2
    #print(x,cnt)
    return cnt<k



n,k = ma()
A = lma()
pA = [a for a in A if a>0]
mA = [a for a in A if a<0]
pn = len(mA)*(len(mA)-1)//2 +len(pA)*(len(pA)-1)//2
mn = len(pA) *len(mA)
z = n*(n-1)//2 -pn -mn
if k<=mn:
    f=True
    pA.sort()
    mA.sort(reverse=True)
elif k>mn+z:
    f=False
    pA.sort(reverse=True)
    mA.sort()
else:
    print(0)
    exit()
#print(isok2(6,mA,pA,cnt=mn+z))
ok = -10**18-2
ng = 10**18+2
x = (ok+ng)//2

while ng-ok>1:
    if f:
        if isok1(x,mA,pA):
            ok = x
        else:
            ng=x
        x = (ok+ng)//2
    else:
        if isok2(x,mA,pA,cnt=mn+z):
            ok = x
        else:
            ng=x
        x = (ok+ng)//2
print(ng)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
xl = - 10**9 - 1
xr = 10**9 + 1
while xl + 1 < xr:
  xc = (xl + xr) // 2
  an = 0
  for a in A:
    if a < 0:
      l = -1
      r = N
      while l + 1 < r:
        c = (l + r) // 2
        if a * A[c] < xc:
          r = c
        else:
          l = c
      an += N - r
    else:
      l = -1
      r = N
      while l + 1 < r:
        c = (l + r) // 2
        if a * A[c] < xc:
          l = c
        else:
          r = c
      an += r
    if a * a < xc:
      an -= 1
  an //= 2
  if an < K:
    xl = xc
  else:
    xr = xc
print(xl)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
from math import log2
from bisect import bisect_left,bisect_right
a.sort()
# 0未満の個数
mn=bisect_left(a,0)
# 0の個数
zn=bisect_right(a,0)-mn
# 0より大きい個数
pn=n-mn-zn
am=a[:mn]
am=[-x for x in am[::-1]]
ap=a[mn+zn:]
# 自分より小さい数字がk個未満のうち最大の値を求める
# 自分より小さい数字がk個未満ならTrue
def func(x):
    cnt=0
    if x>0:
        cnt+=mn*pn
        cnt+=(zn*(n-1+n-zn))//2
        cnt1=0
        for y in ap:
            cnt1+=bisect_left(ap,(x+y-1)//y)
            if y**2<x:cnt1-=1
        for y in am:
            cnt1+=bisect_left(am,(x+y-1)//y)
            if y**2<x:cnt1-=1
        cnt+=cnt1//2
    elif x<0:
        x=abs(x)
        for y in ap:
            cnt+=mn-bisect_right(am,(x+y-1)//y)
    elif x==0:
        cnt+=mn*pn
    return cnt<k

maxaa=max(abs(a[0]),abs(a[-1]))**2
l,r=-maxaa,maxaa
while r-l>1:
    x=(l+r)//2
    if func(x):
        l,r=x,r
    else:
        l,r=l,x
print(r if func(r) else l)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
from math import log2
from bisect import bisect_left,bisect_right
a.sort()
# 0未満の個数
mn=bisect_left(a,0)
# 0の個数
zn=bisect_right(a,0)-mn
# 0より大きい個数
pn=n-mn-zn
am=a[:mn]
am=[-x for x in am[::-1]]
ap=a[mn+zn:]
# 自分より小さい数字がk個未満のうち最大の値を求める
# 自分より小さい数字がk個未満ならTrue
def func(x):
    cnt=0
    if x>0:
        cnt+=mn*pn
        cnt+=(zn*(n-1+n-zn))//2
        cnt1=0
        for y in ap:
            cnt1+=bisect_left(ap,(x+y-1)//y)
            if y**2<x:cnt1-=1
        for y in am:
            cnt1+=bisect_left(am,(x+y-1)//y)
            if y**2<x:cnt1-=1
        cnt+=cnt1//2
    elif x<0:
        x=abs(x)
        for y in ap:
            cnt+=mn-bisect_right(am,(x+y-1)//y)
    elif x==0:
        cnt+=mn*pn
    return cnt<k

maxaa=max(abs(a[0]),abs(a[-1]))**2
l,r=-maxaa,maxaa
while r-l>1:
    x=(l+r)//2
    if func(x):
        l,r=x,r
    else:
        l,r=l,x
print(r if func(r) else l)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n,k=MI()
    lis=LI()
    p,z,m=0,0,0
    plus=[]
    minus=[]
    for i in range(n):
        if lis[i]>0:
            p+=1
            plus.append(lis[i])
        elif lis[i]==0:
            z+=1
        else:
            m+=1
            minus.append(lis[i])
    plus.sort()
    minus.sort()
    print(plus)
    print(minus)
    #plus,minus,sort
    resm=p*m
    resz=z*p+z*m+p*m+z*(z-1)//2
    if k<=resm:
        left=-10**18-1
        right=-1
        while left+1<right:
            x=(left+right)//2
            i=0
            ans=0
            j=0
            while i<p:
                while j<m:
                    if plus[i]*minus[j]<=x:
                        if j==m-1:
                            ans+=m
                            i+=1
                            break
                        j+=1
                    else:
                        i+=1
                        ans+=j
                        break
            #print(left,right,x,ans)
            if ans>=k:
                right=x
            else:
                left=x
        print(right)
    
    elif k<=resz:
        print(0)
        sys.exit()
    else:
        k=k-resz
        print(k)
        left=0
        right=10**18
        square=[]
        for i in range(p):
            square.append(plus[i]**2)
        for i in range(m):
            minus[i]*=(-1)
            square.append(minus[i]**2)
        square.sort()
        plus.sort()
        minus.sort()
        plus2=sorted(plus,reverse=True)  
        minus2=sorted(minus,reverse=True)
        while left+1<right:
            x=(left+right)//2
            i=0
            ans=0
            j=0
            zure=bisect_right(square,x)-1
            while i<p:
                while j<p:
                    if plus2[i]*plus[j]<=x:
                        if j==p-1:
                            ans+=p
                            i+=1
                            break
                        j+=1
                    else:
                        i+=1
                        ans+=j
                        break
            i=0
            j=0
            while i<m:
                while j<m:
                    if minus2[i]*minus[j]<=x:
                        if j==m-1:
                            ans+=m
                            i+=1
                            break
                        j+=1
                    else:
                        i+=1
                        ans+=j
                        break
            print(left,right,x,ans,zure,(ans-zure)//2)
            if (ans-zure)//2>=k:
                right=x
            else:
                left=x
        print(right)
            
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

N,K=map(int,input().split())
A=sorted(map(int,input().split()))
for i in range(N):
    if A[i]>=0:
        break
minus=i
for i in range(i,N):
    if A[i]>0:
        break
zero=i-minus
plus=N-zero-minus

x=0
top=10**18+1
under=-(10**18)
while 1:
    k=0
    if x>=0:
        k+=minus*(N-minus)
        i=minus-1
        j=i-1
        while i>0 and j<i:
            while j>-1 and x>A[i]*A[j]:
                j-=1
            k+=i-j-1
            i-=1
        if x!=0:
            k+=zero*plus
            for i in range(zero):
                k+=i
            i=minus+zero
            j=i+1
            while i<N and j>i:
                while j<N and x>A[i]*A[j]:
                    j+=1
                k+=j-1-i
                i+=1
    else:
        i=minus-1
        j=N-1
        while i>-1:
            while j>N-plus-1 and x>A[i]*A[j]:
                j-=1
            k+=(N-1)-j
            i-=1
    if k<K:
        under=x
        x=math.ceil((under+top)/2)
        if top==under+1:
          break
    else:
        top=x
        x=(under+top)//2
print(under)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

def main():
    n, k = map(int, input().split())
    A = [int(x) for x in input().split()]
    A = sorted(A)
    # A をソートし、負／0／正にわける
    M = [i for i in A if i < 0]
    Z = [i for i in A if i == 0]
    P = [i for i in A if i > 0]

    def x_or_less(x, List):
        cnt = 0
        # 一方が負の場合
        cnt += sum([n - bisect_left(List, x//m) if x%m == 0 \
            else n - bisect_right(List, x//m) for m in M])
        # 一方が0の場合
        cnt += len(Z) * n
        # 一方が正の場合
        cnt += sum([bisect_right(List, x//p) for p in P])
        # 自分同士がx以下なら引く
        cnt -= sum([1 for i in List if i*i <= x])
        cnt //= 2
        return cnt 

    l = -10 ** 18
    r = 10 ** 18
    while r - l > 1:
        x = (r+l) // 2
        if x_or_less(x, A) >= k:
            r = x
        else:
            l = x
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import count

def f(plus, minus, zero, val):
    t = 0
    if val > 0:
        t += len(plus) * len(minus) + zero * (len(plus) + len(minus)) + zero * (zero - 1) // 2
        # print(f'    zero {len(plus) * len(minus) + zero * (len(plus) + len(minus)) + zero * (zero - 1) // 2=}')
        if len(plus) >= 2:
            right_index = len(plus) -1
            for left_index, left in enumerate(plus):
                while left_index < right_index and left * plus[right_index] > val:
                    right_index -= 1
                if left_index < right_index:
                    break
                t += right_index - left_index
                # print(f'    plus {right_index-left_index=}')
        if len(minus) >= 2:
            left_index = 0
            for right_index, right in zip(count(len(minus) - 1, -1), reversed(minus)):
                while left_index < right_index and minus[left_index] * right > val:
                    left_index += 1
                if left_index < right_index:
                    break
                t += right_index - left_index
                # print(f'    minus {right_index-left_index=} {right_index=} {right=}')
    elif val < 0:
        if plus:
            plus_index = 0
            for m in minus:
                while plus_index < len(plus) and plus[plus_index] * m > val:
                    plus_index += 1
                if plus_index < len(plus):
                    break
                t += len(plus) - plus_index
                # print(f'    mix {len(plus) - plus_index=}')
    else:
        t += len(plus) * len(minus) + zero * (len(plus) + len(minus)) + zero * (zero - 1) // 2
        # print(f'    zero {len(plus) * len(minus) + zero * (len(plus) + len(minus)) + zero * (zero - 1) // 2=}')
    # print(f'  {val=}, {t=}')
    return t


def resolve(in_):
    N, K = map(int, in_.readline().split())
    plus = []
    minus = []
    zero = 0
    for a in map(int, in_.readline().split()):
        if a > 0:
            plus.append(a)
        elif a < 0:
            minus.append(a)
        else:
            zero += 1

    plus.sort()
    minus.sort()

    ng = -(10 ** 18) - 1
    ok = 10 ** 18
    while ok - ng > 1:
        mid = (ok + ng) // 2
        # print(f'{ok=} {ng=} {mid=}')

        if f(plus, minus, zero, mid) >= K:
            ok = mid
        else:
            ng = mid

    # print(f'{ok=} {ng=} {mid=}')
    return ok


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main(N, K, A):
  cp = 0
  cn = 0
  cz = 0
  An = []
  Anp = []
  Ap = []
  for a in A:
    cp += a > 0
    cn += a < 0
    cz += a == 0
    if a > 0:
      Ap.append(a)
    if a < 0:
      An.append(a)
      Anp.append(-a)
  Anp = sorted(Anp)
	
  if K <= cn * cp:
    # negative 
    #print(K)
    
    ok = -10**20  # There are <= K pairs <= ok
    ng = 0
    # x, count

    while ok + 1 < ng:
      x = (ok + ng) //2
      count = 0
      i_an = -1
      for i, a in enumerate(Ap): # a: increasing -> x // a increasing
        while i_an + 1 < len(An) and An[i_an + 1]* a <= x:
          i_an += 1

        count += i_an + 1
        #print(x, a, count)
      #print(x, count)
      if count < K:
        ok = x
      else:
        ng = x
    return ng
  elif K <= cn * cp + cz * (cp + cn) + (cz - 1 )* cz //2:
    
    return 0
  else:
    # positive
    #print(K)
    K -=  cn * cp + cz * (cp + cn) + (cz - 1 )* cz //2
    #print(K)
    ok = 0
    ng = 10**20  # There are <= K pairs <= ok
    # x, count

    while ok + 1 < ng:
      x = (ok + ng) //2
      count = 0
      for Aa in [Ap, Anp]:
        i_ap = -1
        for i, a in zip(range(len(Aa)-1, -1, -1), Aa[::-1]):
          # a: decreasing -> x // a increasing
          while i_ap+1 < len(Aa) and Aa[i_ap+1] * a <= x:
            i_ap += 1
          count += i_ap + 1
          count -= i <= i_ap
          #print(x, a, count, i, i_ap, Aa)
      count //= 2
      #print(x, count)
      if count < K:
        ok = x
      else:
        ng = x
    return ng

N, K = map(int, input().split())
A = sorted(map(int, input().split()))
pairs = []
for i in range(len(A)):
  for j in range(i + 1, len(A)):
    pairs.append(A[i]*A[j])
pairs.sort()
for K, p in zip(range(1, N*(N+1)//2+1), pairs):
  
  result = main(N, K, A)
  if result != p:
    print(K, p, result)
print('done')

Submission status: Wrong Answer

Solution code:
def main():
  N, K = map(int, input().split())
  A = sorted(map(int, input().split()))
  cp = 0
  cn = 0
  cz = 0
  An = []
  Anp = []
  Ap = []
  for a in A:
    cp += a > 0
    cn += a < 0
    cz += a == 0
    if a > 0:
      Ap.append(a)
    if a < 0:
      An.append(a)
      Anp.append(-a)
  Anp = sorted(Anp)
	
  if K <= cn * cp:
    # negative 
    #print(K)
    
    ok = -10**20  # There are <= K pairs <= ok
    ng = 0
    # x, count

    while ok + 1 < ng:
      x = (ok + ng) //2
      count = 0
      i_an = -1
      for i, a in enumerate(Ap): # a: increasing -> x // a increasing
        while i_an + 1 < len(An) and An[i_an + 1] <= x / a:
          i_an += 1

        count += i_an + 1
        #print(x, a, count)
      #print(x, count)
      if count < K:
        ok = x
      else:
        ng = x
    print(ng)
    return
  elif K <= cn * cp + cz * (cp + cn) + (cz - 1 )* cz //2:
    print(0)
    return
  else:
    # positive
    #print(K)
    K -=  cn * cp + cz * (cp + cn) + (cz - 1 )* cz //2
    #print(K)
    ok = 0
    ng = 10**20  # There are <= K pairs <= ok
    # x, count

    while ok + 1 < ng:
      x = (ok + ng) //2
      count = 0
      for Aa in [Ap, Anp]:
        i_ap = -1
        for i, a in zip(range(len(Aa)-1, -1, -1), Aa[::-1]):
          # a: decreasing -> x // a increasing
          while i_ap+1 < len(Aa) and Aa[i_ap+1] * a <= x:
            i_ap += 1
          count += i_ap + 1
          count -= i <= i_ap
          #print(x, a, count, i, i_ap, Aa)
      count //= 2
      #print(x, count)
      if count < K:
        ok = x
      else:
        ng = x
    print(ng)
    return

main()

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

P = []
M = []
z = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        z += 1

P.sort()
M.sort()

def f(n):
    res = 0
    if n < 0 and len(P) > 0 and len(M) > 0:
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(P) and M[i]*P[j] > n:
                j += 1
            res += len(P)-j
    elif n == 0:
        res = len(M)*len(P)+z*(N-z)+z*(z-1)//2
    else:
        res = len(M)*len(P)+z*(N-z)+z*(z-1)//2
        j = len(P)-1
        for i in range(len(P)):
            while j >= 0 and P[i]*P[j] > n:
                j -= 1
            if i >= j:
                break
            res += j-i
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(M) and M[i]*M[j] > n:
                j += 1
            if j >= i:
                break
            res += i-j
    return res

l = -10**18
r = 10**18
while True:
    num = (l+r)//2
    if f(num) < K:
        l = num
    else:
        r = num
    if r-l <= 1:
        print(r)
        break

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

P = []
M = []
z = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        z += 1

P.sort()
M.sort()

def f(n):
    res = 0
    if n < 0 and len(P) > 0 and len(M) > 0:
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(P) and M[i]*P[j] >= n:
                j += 1
            res += len(P)-j
    elif n == 0:
        res = len(M)*len(P)
    else:
        res = len(M)*len(P)+z*(N-z)+z*(z-1)//2
        j = len(P)-1
        for i in range(len(P)):
            while j >= 0 and P[i]*P[j] >= n:
                j -= 1
            if i >= j:
                break
            res += j-i
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(M) and M[i]*M[j] >= n:
                j += 1
            if j >= i:
                break
            res += i-j
    return res

l = -10**18
r = 10**18
while True:
    num = (l+r)//2
    if f(num) < K:
        l = num
    else:
        r = num
    if r-l <= 1:
        print(l)
        break

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

P = []
M = []
z = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        z += 1

P.sort()
M.sort()

def f(n):
    res = 0
    if n < 0 and len(P) > 0 and len(M) > 0:
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(P) and M[i]*P[j] >= n:
                j += 1
            res += len(P)-j
    elif n == 0:
        res = len(M)*len(P)
    else:
        res = len(M)*len(P)+z*(N-z)+z*(z-1)//2
        if len(P) > 1:
            i = len(P)-1
            for j in range(len(P)):
                while i > j and P[j]*P[i] >= n:
                    i -= 1
                res += max(0, i-j)
        if len(M) > 1:
            i = 0
            for j in range(len(M)-1, -1, -1):
                while i < j and M[j]*M[i] >= n:
                    i += 1
                res += max(0, j-i)
    return res

l = -10**18
r = 10**18
while True:
    num = (l+r)//2
    if f(num) < K:
        l = num
    else:
        r = num
    if r-l <= 1:
        print(l-1)
        break

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

P = []
M = []
z = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        z += 1

P.sort()
M.sort()

def f(n):
    res = 0
    if n < 0 and len(P) > 0 and len(M) > 0:
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(P) and M[i]*P[j] >= n:
                j += 1
            res += len(P)-j
    elif n == 0:
        res = len(M)*len(P)
    else:
        res = len(M)*len(P)+z*(N-z)+z*(z-1)//2
        if len(P) > 1:
            i = len(P)-1
            for j in range(len(P)):
                while i > j and P[j]*P[i] >= n:
                    i -= 1
                res += max(0, i-j)
        if len(M) > 1:
            i = 0
            for j in range(len(M)-1, -1, -1):
                while i < j and M[j]*M[i] >= n:
                    i += 1
                res += max(0, j-i)
    return res

l = -10**18
r = 10**18
while True:
    num = (l+r)//2
    if f(num) < K:
        l = num
    else:
        r = num
    if r-l <= 1:
        print(r)
        break

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

P = []
M = []
z = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        z += 1

P.sort()
M.sort()

def f(n):
    res = 0
    if n < 0 and len(P) > 0 and len(M) > 0:
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(P) and M[i]*P[j] >= n:
                j += 1
            res += len(P)-j
    elif n == 0:
        res = len(M)*len(P)
    else:
        res = len(M)*len(P)+z*(N-z)+z*(z-1)//2
        if len(P) > 1:
            i = len(P)-1
            for j in range(len(P)):
                while i > j and P[j]*P[i] >= n:
                    i -= 1
                res += max(0, i-j)
        if len(M) > 1:
            i = 0
            for j in range(len(M)-1, -1, -1):
                while i < j and M[j]*M[i] >= n:
                    i += 1
                res += max(0, j-i)
    return res

l = -10**18
r = 10**18
while True:
    num = (l+r)//2
    if f(num) < K:
        l = num
    else:
        r = num
    if r-l <= 1:
        print(l)
        break

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

P = []
M = []
z = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        z += 1

P.sort()
M.sort()

def f(n):
    res = 0
    if n < 0 and len(P) > 0 and len(M) > 0:
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(P) and M[i]*P[j] >= n:
                j += 1
            res += len(P)-j
    elif n == 0:
        res = len(M)*len(P)
    else:
        res = len(M)*len(P)+z*(N-z)+z*(z-1)//2
        if len(P) > 1:
            i = len(P)-1
            for j in range(len(P)):
                while i > j and P[j]*P[i] >= n:
                    i -= 1
                res += max(0, i-j)
        if len(M) > 1:
            i = 0
            for j in range(len(M)-1, -1, -1):
                while i < j and M[j]*M[i] >= n:
                    i += 1
                res += max(0, j-i)
    return res

l = -10**18
r = 10**18
while True:
    num = (l+r)//2
    if f(num) < K:
        l = num
    else:
        r = num
    if r-l <= 1:
        if f(l) == K-1:
            print(l)
        elif f(r) == K-1:
            print(r)
        elif f(l) < K-1 and f(r) > K-1:
            print(l)
        break

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

P = []
M = []
z = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        z += 1

P.sort()
M.sort()

def f(n):
    res = 0
    if n < 0 and len(P) > 0 and len(M) > 0:
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(P) and M[i]*P[j] >= n:
                j += 1
            res += len(P)-j
    elif n == 0:
        res = len(M)*len(P)
    else:
        res = len(M)*len(P)+z*(N-z)+z*(z-1)//2
        if len(P) > 1:
            i = len(P)-1
            for j in range(len(P)):
                while i > j and P[j]*P[i] >= n:
                    i -= 1
                res += max(0, i-j)
        if len(M) > 1:
            i = 0
            for j in range(len(M)-1, -1, -1):
                while i < j and M[j]*M[i] >= n:
                    i += 1
                res += max(0, j-i)
    return res

l = -10**18
r = 10**18
while True:
    num = (l+r)//2
    if f(num) < K:
        l = num
    else:
        r = num
    if r-l == 1:
        if f(l) < K-1 and f(r) >= K-1:
            print(r)
        elif f(l) == K-1 and f(r) >= K:
            print(l)
        break
    elif r == l:
        print(r)
        break

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

P = []
M = []
z = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        z += 1

P.sort()
M.sort()

def f(n):
    res = 0
    if n < 0 and len(P) > 0 and len(M) > 0:
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(P) and M[i]*P[j] >= n:
                j += 1
            res += len(P)-j
    elif n == 0:
        res = len(M)*len(P)
    else:
        res = len(M)*len(P)+z*(N-z)+z*(z-1)//2
        if len(P) > 1:
            i = len(P)-1
            for j in range(len(P)):
                while i > j and P[j]*P[i] >= n:
                    i -= 1
                res += max(0, i-j)
        if len(M) > 1:
            i = 0
            for j in range(len(M)-1, -1, -1):
                while i < j and M[j]*M[i] >= n:
                    i += 1
                res += max(0, j-i)
    return res

A.sort()
l = (-1)*(max(abs(A[0]), abs(A[-1]))**2)
r = max(abs(A[0]), abs(A[-1]))**2
while True:
    num = (l+r)//2
    if f(num) < K:
        l = num
    else:
        r = num
    if r-l == 1:
        if f(l) < K-1 and f(r) >= K-1:
            print(r)
        elif f(l) == K-1 and f(r) >= K:
            print(l)
        break
    elif r == l:
        print(r)
        break

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

P = []
M = []
z = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        z += 1

P.sort()
M.sort()

def f(n):
    res = 0
    if n < 0 and len(P) > 0 and len(M) > 0:
        j = 0
        for i in range(len(M)-1, -1, -1):
            while j < len(P) and M[i]*P[j] >= n:
                j += 1
            res += len(P)-j
    elif n == 0:
        res = len(M)*len(P)
    else:
        res = len(M)*len(P)+z*(N-z)+z*(z-1)//2
        if len(P) > 1:
            i = len(P)-1
            for j in range(len(P)):
                while i > j and P[j]*P[i] >= n:
                    i -= 1
                res += max(0, i-j)
        if len(M) > 1:
            i = 0
            for j in range(len(M)-1, -1, -1):
                while i < j and M[j]*M[i] >= n:
                    i += 1
                res += max(0, j-i)
    return res

A.sort()
l = (-1)*(max(abs(A[0]), abs(A[-1]))**2)
r = max(abs(A[0]), abs(A[-1]))**2
while True:
    num = (l+r)//2
    if f(num) < K:
        l = num
    else:
        r = num
    if r-l <= 1:
        if f(l) < K-1 and f(r) >= K-1:
            print(r)
        elif f(l) == K-1 and f(r) >= K:
            print(l)
        break