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():
    import numpy as np
    from bisect import bisect_left,bisect_right
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=np.array(A)
    A=np.sort(A)
    Ap=A[A>0]
    Az=A[A==0]
    Am=A[A<0]   
    lm,lz,lp=len(Am),len(Az),len(Ap)
    Ap2=Ap**2
    Am2=Am**2
    #print(Ap,Am,Az,Ap2,Am2)
    def cnt_product(x): #ある数字の組であってその積がx以下となるものの数
        if x<0:
            X=np.searchsorted(Am,x/Ap,side='right')
            #print(X)
            return X.sum()
        
        else:
            ans=lz*(n-lz)+lz*(lz-1)//2+lp*lm

            X=np.searchsorted(Ap,x//Ap,side='right')
            Xd=np.count_nonzero(Ap2<=x)

            Y=np.searchsorted(Am,(-x-1)//(-Am))
            Yd=np.count_nonzero(Am2<=x)
            
            ans+=(X.sum()-Xd+lm**2-Y.sum()-Yd)//2
            return ans
    #print(cnt_product(448283280358331042))
    left=-10**18
    right=10**18
    while right-left>1:
        mid=(left+right)//2
        if cnt_product(mid)<k:
            left=mid
        else:
            right=mid
    print(right)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,k=LI()
a=LI()
neg,pos=[],[]
cz=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        cz+=1
pos=sorted(pos)#[::-1]
neg=sorted(neg)#[::-1]

pn=len(pos)
nn=len(neg)
show(pos,neg)
def check(z):
    e=-10**-2
    c=0
    if z>0:
        for i in pos:
            x=z/i
            c+=bisect.bisect(pos,x-e)
            if x-e<=z:c-=1
            show((i,x,z),c,bisect.bisect(pos,x-e),pos)
        for i in neg:
            x=z/i
            c+=bisect.bisect(neg,x-e)
            if x-e<=z:c-=1
            show((i,x,z),c,bisect.bisect(neg,x-e),neg)
        c+=pn*nn*2
    elif z<=0:
        for i in pos:
            x=-z/i
            c+=nn-bisect.bisect(neg,x+e)
            #if x-e<=z:c-=1
            #show((i,x,z),c,bisect.bisect(neg,x-e),neg)
        for i in neg:
            x=-z/i
            c+=pn-bisect.bisect(pos,x+e)
            #if x-e<=z:c-=1
    
    if z>=0:
        c+=cz*(cz-1)+cz*(n-cz)*2
    return c//2

for i in range(-30,50):
    print(i,check(i))
l,r=-10**18-1,10**18+1

while r-l>1:
    mid=(r+l)//2
    if check(mid)>=k-1:
        r=mid
    else:
        l=mid


print(r)

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    from bisect import bisect_left,bisect_right
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=np.array(A)
    A=np.sort(A)
    Ap=A[A>0]
    Az=A[A==0]
    Am=A[A<0]   
    lm,lz,lp=len(Am),len(Az),len(Ap)
    Ap2=Ap**2
    Am2=Am**2
    #print(Ap,Am,Az,Ap2,Am2)
    def cnt_product(x): #ある数字の組であってその積がx以下となるものの数
        if x<0:
            X=np.searchsorted(Am,x/Ap,side='right')
            #print(X)
            return X.sum()
        
        else:
            ans=lz*(n-lz)+lz*(lz-1)//2+lp*lm

            X=np.searchsorted(Ap,x//Ap,side='right')
            Xd=np.count_nonzero(Ap2<=x)

            Y=np.searchsorted(Am,x//Am)
            Yd=np.count_nonzero(Am2<=x)
            
            ans+=(X.sum()-Xd+lm**2-Y.sum()-Yd)//2
            return ans
    #print(cnt_product(448283280358331042))
    left=-10**18
    right=10**18
    while right-left>1:
        mid=(left+right)//2
        if cnt_product(mid)<k:
            left=mid
        else:
            right=mid
    print(right)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    from bisect import bisect_left,bisect_right
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=np.array(A)
    A=np.sort(A)
    Ap=A[A>0]
    Az=A[A==0]
    Am=A[A<0]   
    lm,lz,lp=len(Am),len(Az),len(Ap)
    Ap2=Ap**2
    Am2=Am**2
    #print(Ap,Am,Az,Ap2,Am2)
    def cnt_product(x): #ある数字の組であってその積がx以下となるものの数
        if x<0:
            X=np.searchsorted(Am,x/Ap,side='right')
            #print(X)
            return X.sum()
        
        else:
            ans=lz*(n-lz)+lz*(lz-1)//2+lp*lm

            X=np.searchsorted(Ap,x/Ap,side='right')
            Xd=np.count_nonzero(Ap2<=x)

            Y=np.searchsorted(Am,x/Am)
            Yd=np.count_nonzero(Am2<=x)
            
            ans+=(X.sum()-Xd+lm**2-Y.sum()-Yd)//2
            return ans

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

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left,bisect_right
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    Am,Az,Ap=[],[],[]
    for num in A:
        if num<0:
            Am.append(num)
        elif num==0:
            Az.append(num)
        else:
            Ap.append(num)
    
    Am.sort()
    Az.sort()
    Ap.sort()
    lm,lz,lp=len(Am),len(Az),len(Ap)
    print(Am,Az,Ap)
    def cnt_product(x): #ある数字の組であってその積がx以下となるものの数
        if x<0:
            ans=0
            for p in Ap:
                ans+=bisect_right(Am,x/p)
            return ans
        
        else:
            ans=lz*(n-lz)+lz*(lz-1)//2+lp*lm
            a=0
            for p in Ap:
                a+=bisect_right(Ap,x/p)
                if p**2<=x:
                    a-=1
                    
            for m in Am:
                a+=lm-bisect_left(Am,x/m)
                if m**2<=x:
                    a-=1

            return ans+a//2
    print(cnt_product(0))
    
    left=-10**18-1
    right=10**18+1
    while right-left>1:
        mid=(left+right)//2
        if cnt_product(mid)<k:
            left=mid
        else:
            right=mid
    print(right)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect


def count_lower(A, x):
    # Aの要素のうちxより小さいものの個数
    return bisect.bisect_left(A, x)


def count_higher(A, x):
    # Aの要素のうちxより大きいものの個数
    return len(A)-bisect.bisect_right(A, x)


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x / A[n]
            # n+1番以降でyより大きいものの個数
            cnt += count_higher(A[n+1:], y)
        elif A[n] > 0:
            y = x / A[n]
            # n+1番以降でyより小さいものの個数
            cnt += count_lower(A[n+1:], y)
        else:
            if x > 0:
                cnt += N - n - 1
    return cnt


def count_ans(A, x):
    N = len(A)
    cnt = 0
    for n in range(N-1):
        for m in range(n + 1, N):
            if A[n] * A[m] < x:
                cnt += 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10 ** 19
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
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)
nAr=list(reversed(nA))
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

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

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

import bisect
def g1_2(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    if L[-1]*n<=x: return len(L)
    l=bisect.bisect_right(L,x//n,0,min(len(L)-1,pR))
    pR=l+1
    return l

def g1_3(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    if L[0]*n<=x: return len(L)
    l=bisect.bisect_right(L,(x+n+1)//n,0,min(len(L)-1,pR))
    pR=l+1
    return len(L)-l

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

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
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 sys
input = sys.stdin.readline
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)
nAr=list(reversed(nA))
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

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

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

import bisect
def g1_2(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    if L[-1]*n<=x: return len(L)
    l=bisect.bisect_right(L,x//n,0,min(len(L)-1,pR))
    pR=l+1
    return l

def g1_3(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    if L[0]*n<=x: return len(L)
    l=bisect.bisect_right(L,(x+n+1)//n,0,min(len(L)-1,pR))
    pR=l+1
    return len(L)-l

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

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
print(nA)
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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  Ans, Aps, A0s = [], [], []
  
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      A0s.append(A)
    else:
      Ans.append(A)
  Aps.sort()
  A0s.sort()
  Ans.sort()
  As.sort()
  
  cp, c0, cn = (len(Aps)*(len(Aps)-1) + len(Ans)*(len(Ans)-1))//2, len(A0s) * (len(Ans) + len(Aps) + (len(A0s)-1)//2), len(Ans) * len(Aps)
  
  if k <= cn:
    flag = 0
  elif k <= cn + c0:
    print(0)
    return
  else:
    flag = 1
    
  def count(xs, ys, ub):
    c = 0
    r = len(ys) - 1
    for l in range(len(xs)):
      while xs[l] * ys[r] > ub and r >= 0:
        r -= 1
      c += r+1
    return c 
  
  def bs(l, r, xs, ys, k):
    if flag == 1:
      while True:
        mid = (l+r) // 2
        if r - l <= 1:
          return r
        tot = count(xs, xs, mid)
        tot += count(ys, ys, mid)
        tot -= sum([1 for x in xs+ys if x*x <= mid])
        tot //= 2
        if tot < k:
          l = mid
        else:
          r = mid
    else:
      while True:
        mid = (l+r) // 2
        if r - l <= 1:
          return r
        tot = count(xs, ys, mid)
        if tot < k:
          l = mid
        else:
          r = mid
        
  if flag == 1:
    print(bs(0, MAX, Aps, Ans[::-1], k - cn - c0))
  else:
    print(bs(MIN-1, -1, Aps[::-1], Ans, k))
    
    
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  Ans, Aps, A0s = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      A0s.append(A)
    else:
      Ans.append(A)
  Aps.sort()
  A0s.sort()
  Ans.sort()
  
  cp, c0, cn = (len(Aps)*(len(Aps)-1) + len(Ans)*(len(Ans)-1))//2, len(A0s) * (len(Ans) + len(Aps) + (len(A0s)-1)//2), len(Ans) * len(Aps)
  
  if k <= cn:
    flag = 0
  elif k <= cn + c0:
    print(0)
    return
  else:
    flag = 1
  
  def count(l, r, x, ub, xs):
    while True:
      mid = (l+r)//2
      if x > 0:
        if r - l <=1:
          return r - (1 if x**2 <= ub else 0) * flag
        if x * xs[mid] <= ub:
          l = mid
        else:
          r = mid
      else:
        if r - l <=1:
          return len(xs) - r - (1 if x**2 <= ub else 0) * flag
        if x * xs[mid] <= ub:
          r = mid
        else:
          l = mid
            
  def county(xs, ys, lb):
    c = 0
    r = len(ys) - 1
    for l in range(len(xs)):
      while xs[l] * ys[r] > lb and r >= 0:
        r -= 1
      c += r+1
    return c 

  def bs(l, r, xs, ys, k):
    if flag == 1:
      while True:
        mid = (l+r) // 2
        if r - l <= 1:
          return r
        tot = county(xs, xs, mid)
        tot += county(ys[::-1], ys[::-1], mid)
        tot -= sum([1 for x in xs+ys if x*x <= mid])
        tot //= 2
        if tot < k:
          l = mid
        else:
          r = mid
    else:
      while True:
        mid = (l+r) // 2
        if r - l <= 1:
          return r
        tot = county(xs, ys, mid)
        if tot < k:
          l = mid
        else:
          r = mid
        
  if flag == 1:
    print(bs(0, MAX+1, Aps, Ans, k - cn - c0))
  else:
    print(bs(MIN-1, 0, Aps, Ans, k))

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  Ans, Aps, A0s = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      A0s.append(A)
    else:
      Ans.append(A)
  Aps.sort()
  A0s.sort()
  Ans.sort()
  
  cp, c0, cn = (len(Aps)*(len(Aps)-1) + len(Ans)*(len(Ans)-1))//2, len(A0s) * (len(Ans) + len(Aps) + (len(A0s)-1)//2), len(Ans) * len(Aps)
  
  if k <= cn:
    flag = 0
  elif k <= cn + c0:
    print(0)
    return
  else:
    flag = 1
  
  def count(l, r, x, ub, xs):
    while True:
      mid = (l+r)//2
      if x > 0:
        if r - l <=1:
          return r - (1 if x**2 <= ub else 0) * flag
        if x * xs[mid] <= ub:
          l = mid
        else:
          r = mid
      else:
        if r - l <=1:
          return len(xs) - r - (1 if x**2 <= ub else 0) * flag
        if x * xs[mid] <= ub:
          r = mid
        else:
          l = mid
            
  def county(xs, ys, lb):
    c = 0
    r = len(ys) - 1
    for l in range(len(xs)):
      while xs[l] * ys[r] > lb and r >= 0:
        r -= 1
      c += r+1
    return c - sum([1 for x in xs if x*x <= lb])

  def bs(l, r, xs, ys, k):
    if flag == 1:
      while True:
        mid = (l+r) // 2
        if r - l <= 1:
          return r
        tot = county(xs, xs, mid)
        tot += county(ys[::-1], ys[::-1], mid)
        tot //= 2
        if tot < k:
          l = mid
        else:
          r = mid
    else:
      while True:
        mid = (l+r) // 2
        if r - l <= 1:
          return r
        tot = county(xs, ys, mid)
        if tot < k:
          l = mid
        else:
          r = mid
        
  if flag == 1:
    print(bs(0, MAX+1, Aps, Ans, k - cn - c0))
  else:
    print(bs(MIN-1, 0, Aps, Ans, k))
    
    
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  Ans, Aps, A0s = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      A0s.append(A)
    else:
      Ans.append(A)
  Aps.sort()
  A0s.sort()
  Ans.sort()
  
  cp, c0, cn = (len(Aps)*(len(Aps)-1) + len(Ans)*(len(Ans)-1))//2, len(A0s) * (len(Ans) + len(Aps) + (len(A0s)-1)//2), len(Ans) * len(Aps)
  
  if k <= cn:
    flag = 0
  elif k <= cn + c0:
    print(0)
    return
  else:
    flag = 1
  
  def count(l, r, x, ub, xs):
    while True:
      mid = (l+r)//2
      if x > 0:
        if r - l <=1:
          return r - (1 if x**2 <= ub else 0) * flag
        if x * xs[mid] <= ub:
          l = mid
        else:
          r = mid
      else:
        if r - l <=1:
          return len(xs) - r - (1 if x**2 <= ub else 0) * flag
        if x * xs[mid] <= ub:
          r = mid
        else:
          l = mid
          
  def countx(xs, ys, ub):
    l, r = 0, len(xs) - 1
    c = 0 
    while l < r:
      while xs[l] * xs[r] > ub and l < r:
        r -= 1
      c += r - l
      l += 1
    return (c)
  
  def county(xs, ys, lb):
    l, r = 0, len(ys) - 1
    c = 0
    while 0 <= l < len(xs):
      while xs[l] * ys[r] < lb and r >= 0:
        r -= 1
      c += r+1
      l += 1
    return c

  def bs(l, r, xs, ys, k):
    if flag == 1:
      while True:
        mid = (l+r) // 2
        if r - l <= 1:
          return r
        tot = countx(xs, xs, mid)
        tot += countx(ys[::-1], ys[::-1], mid)
        if tot < k:
          l = mid
        else:
          r = mid
    else:
      while True:
        mid = (l+r) // 2
        if r - l <= 1:
          return r
        tot = county(xs[::-1], list(map(abs, ys)), -mid)
        if tot < k:
          l = mid
        else:
          r = mid
        
  if flag == 1:
    print(bs(0, MAX+1, Aps, Ans, k - cn - c0))
  else:
    print(bs(MIN-1, 0, Aps, Ans, k))
#   print(countx(xs, xs, ub=200))
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
# 解説放送の改変
# 尺取り?
# https://atcoder.jp/contests/abc155/submissions/10156587

def main():
    inf = 10 ** 18 + 1

    def bs_kth_lt_0():
        def shakutori(cand):
            ret = 0
            cand_pos = -cand  # 正に変換
            r = len_p - 1
            for l in range(len_m):
                while r > 0 and m[l] * p[r] <= cand_pos:
                    r -= 1
                if m[l] * p[r] <= cand_pos: continue
                ret += r + 1
            return ret

        ok, ng = -inf, 0
        while ng - ok > 1:
            cand = (ng + ok) // 2
            tot = shakutori(cand)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

    def bs_kth_gt_0():
        def shakutori(lis, length):
            ret = 0
            r = length - 1
            for l in range(length):
                while r - l > 0 and lis[l] * lis[r] >= cand:
                    r -= 1
                # r==l または lis[l]*lis[r]<candを満たすl,r
                if l == r: break
                ret += r - l
            return ret

        ok, ng = 0, inf
        while ng - ok > 1:
            cand = (ng + ok) // 2
            tot = shakutori(m, len_m) + shakutori(p, len_p)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

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

    m, z, p = [], [], []
    for x in a:
        if x < 0:
            m.append(x)
        elif x == 0:
            z.append(x)
        else:
            p.append(x)

    *m, = sorted(-x for x in m)  # 正に符号変換して昇順ソート
    p.sort()
    # 正数昇順にしておく

    len_m, len_z, len_p = len(m), len(z), len(p)

    cnt_m = len_m * len_p
    cnt_z = len_z * (len_z - 1) // 2 + len_z * (n - len_z)

    if k <= cnt_m:
        # k番目の値は負
        ans = bs_kth_lt_0()
        print(ans)
        return

    elif k <= cnt_m + cnt_z:
        # k番目の値は0
        print(0)
        return
    else:
        # k番目の値は正
        k -= cnt_m + cnt_z  # 正の値の中での順位に直す
        ans = bs_kth_gt_0()
        print(ans)
        return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

posi = 0
nega = 0
zero = 0
p = []
m = []

for i in range(n):
    if a[i] > 0:
        p.append(a[i])
        posi += 1
    elif a[i] < 0:
        nega += 1
        m.append(-a[i])
    else:
        zero += 1

p.sort()
m.sort()

if k <= posi*nega:
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)-1, -1, -1):
            count -= posi-bisect_left(m, (mid-1)//p[i]+1)
            if count <= 0:
                break
        if count <= 0:
            l = mid
        else:
            r = mid
        #print(r, l)

    print(l)

elif k <= posi*nega+zero*(zero-1)//2+zero*(posi+nega):
    print(0)

else:
    k -= posi*nega+zero*(zero-1)//2+zero*(posi+nega)
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)):
            count -= max(bisect_right(p, (mid)//p[i])-i-1, 0)
            if count < 0:
                #continue
                break
        for i in range(len(m)):
            count -= max(bisect_right(m, (mid)//m[i])-i-1, 0)
            if count < 0:
                #continue
                break

        if count > 0:
            l = mid
        else:
            r = mid
    print(r)

Submission status: Wrong Answer

Solution code:
# 解説放送の改変
# aを負0正に分けて処理
# 尺取り?

def main():
    inf = 10 ** 18 + 1

    def bs_kth_lt_0():
        def shakutori(cand):
            ret = 0
            cand_pos = -cand  # 正に変換
            r = len_p - 1
            for l in range(len_m):
                while r > 0 and m[l] * p[r] <= cand_pos:
                    r -= 1
                if m[l] * p[r] <= cand_pos: break
                ret += r + 1
            return ret

        ok, ng = -inf, 0
        while ng - ok > 1:
            cand = (ng + ok) // 2
            tot = shakutori(cand)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

    def bs_kth_gt_0():
        def shakutori(lis, length):
            ret = 0
            r = length - 1
            for l in range(length):
                while r - l > 0 and lis[l] * lis[r] >= cand:
                    r -= 1
                # r==l または lis[l]*lis[r]<candを満たすl,r
                if l == r: break
                ret += r - l
            return ret

        ok, ng = 0, inf
        while ng - ok > 1:
            cand = (ng + ok) // 2
            tot = shakutori(m, len_m) + shakutori(p, len_p)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

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

    m, z, p = [], [], []
    for x in a:
        if x < 0:
            m.append(x)
        elif x == 0:
            z.append(x)
        else:
            p.append(x)

    *m, = sorted(-x for x in m)  # 正に符号変換して昇順ソート
    p.sort()
    # 正数昇順にしておく

    len_m, len_z, len_p = len(m), len(z), len(p)

    cnt_m = len_m * len_p
    cnt_z = len_z * (len_z - 1) // 2 + len_z * (n - len_z)

    if k <= cnt_m:
        # k番目の値は負
        ans = bs_kth_lt_0()
        print(ans)
        return

    elif k <= cnt_m + cnt_z:
        # k番目の値は0
        print(0)
        return
    else:
        # k番目の値は正
        k -= cnt_m + cnt_z  # 正の値の中での順位に直す
        ans = bs_kth_gt_0()
        print(ans)
        return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

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

A.sort()

left=-10**18
right=10**18
count=0

a=bisect.bisect_left(A,0)
b=bisect.bisect_right(A,0)

if b*(n-a)-(b-a)>=k:
    right=0
else:
    left=1

while right!=left:
    pos=(left+right)//2
    count=0
    for a in A:
        if a==0:
            if pos>=0:
                count+=n-1
        elif a<0:
            i=bisect.bisect_right(A,(-1-pos)//(-a))
            count+=n-i + (-1 if a*a<=pos else 0)
        else:
            i=bisect.bisect_right(A,pos//a)
            count+=i + (-1 if a*a<=pos else 0)
    if count>=2*k:
        right=pos
    else:
        left=pos+1

print(left)

Submission status: Wrong Answer

Solution code:
# 解説放送の改変
# aを負0正に分けて処理
# 尺取り?

def main():
    inf = 10 ** 18 + 1

    def bs_kth_lt_0():
        def shakutori(cand):
            ret = 0
            cand_pos = -cand  # 正に変換
            r = len_p - 1
            for l in range(len_m):
                while r > 0 and m[l] * p[r] <= cand_pos:
                    r -= 1
                if r == 0 and m[l] * p[r] <= cand_pos: break
                ret += r + 1
            return ret

        ok, ng = -inf, 0
        while ng - ok > 1:
            cand = (ng + ok) // 2
            tot = shakutori(cand)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

    def bs_kth_gt_0():
        def shakutori(lis, length):
            ret = 0
            r = length - 1
            for l in range(length):
                while r - l > 0 and lis[l] * lis[r] >= cand:
                    r -= 1
                # r==l または lis[l]*lis[r]<candを満たすl,r
                if l == r: break
                ret += r - l
            return ret

        ok, ng = 0, inf
        while ng - ok > 1:
            cand = (ng + ok) // 2
            tot = shakutori(m, len_m) + shakutori(p, len_p)
            if tot < k:
                ok = cand
            else:
                ng = cand
        return ok

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

    m, z, p = [], [], []
    for x in a:
        if x < 0:
            m.append(x)
        elif x == 0:
            z.append(x)
        else:
            p.append(x)

    *m, = sorted(-x for x in m)  # 正に符号変換して昇順ソート
    p.sort()
    # 正数昇順にしておく

    len_m, len_z, len_p = len(m), len(z), len(p)

    cnt_m = len_m * len_p
    cnt_z = len_z * (len_z - 1) // 2 + len_z * (n - len_z)

    if k <= cnt_m:
        # k番目の値は負
        ans = bs_kth_lt_0()
        print(ans)
        return

    elif k <= cnt_m + cnt_z:
        # k番目の値は0
        print(0)
        return
    else:
        # k番目の値は正
        k -= cnt_m + cnt_z  # 正の値の中での順位に直す
        ans = bs_kth_gt_0()
        print(ans)
        return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

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

A.sort()

left=-10**18
right=10**18
count=0

a=bisect.bisect_left(A,0)
b=bisect.bisect_right(A,0)

if b*(n-a)-(b-a)>=2*k:
    right=0
else:
    left=1

while right!=left:
    pos=(left+right)//2
    count=0
    for a in A:
        if a==0:
            if pos>=0:
                count+=n-1
        elif a<0:
            i=bisect.bisect_right(A,(-1-pos)//(-a))
            count+=n-i + (-1 if a*a<=pos else 0)
        else:
            i=bisect.bisect_right(A,pos//a)
            count+=i + (-1 if a*a<=pos else 0)
    if count>=2*k:
        right=pos
    else:
        left=pos+1

print(left)