Problem:


Score: 400 points

Problem Statement

We have N integers A_1, A_2, ..., A_N.

There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \frac{N(N-1)}{2}

-10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 3
3 3 -4 -2

Sample Output 1

-6

There are six ways to form a pair. The products of those pairs are 9, -12, -6, -12, -6, 8.

Sorting those numbers in ascending order, we have -12, -12, -6, -6, 8, 9. The third number in this list is -6.

Sample Input 2

10 40
5 4 3 2 -1 0 0 0 0 0

Sample Output 2

6

Sample Input 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

Sample Output 3

448283280358331064



Sample input:
4 3
3 3 -4 -2


Sample output:
-6

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
INF=10**9+1
l=-INF
r=INF
 
def condition(x):
    tot=0
    for i in range(n):
        if(a[i]<0):
            ll=-1
            rr=n
            while(ll+1<rr):
                xx=(ll+rr)//2
                if(a[i]*a[xx]<x):
                    rr=xx
                else:
                    ll=xx
            tot+=n-rr
        else:
            ll=-1
            rr=n
            while(ll+1<rr):
                xx=(ll+rr)//2
                if(a[i]*a[xx]<x):
                    ll=xx
                else:
                    rr=xx
            tot+=rr
        if(a[i]*a[i]<x):tot-=1
    tot//=2
    return tot<k
 
while(l+1<r):
    x=(l+r)//2
    if(condition(x)):l=x
    else:r=x
print(l)

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:
    print("a")
    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:
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:
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-1)//p[i]+1)-i-1, 0)
            if count < 0:
                #continue
                break
        for i in range(len(m)):
            count -= max(bisect_right(m, (mid-1)//m[i]+1)-i-1, 0)
            if count < 0:
                #continue
                break

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

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.buffer.readline()

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

def evl(x):
    cnt = 0
    for i in range(n):
        if a[i] >= 0:
            l, r = -1, n
            while r-l > 1:
                mid = (l+r) // 2
                if x >= a[i] * a[mid]: l = mid
                else: r = mid
            cnt += max(0, l-i)
        else:
            l, r = -1, n
            while r-l > 1:
                mid = (l+r) // 2
                if x >= a[i] * a[mid]: r = mid
                else: l = mid
            cnt += n - max(i+1, r)
    return cnt >= k

b = [x for x in a if x]
r = 0 if len(b) < 2 else max(b[0] * b[1], b[-1] * b[-2])
l = 0 if len(b) < 2 else min(b[0] * b[1], b[0] * b[-1], b[-1] * b[-2])

while r-l > 1:
    x = (l+r) // 2
    if evl(x): r = x
    else: l = x
print(r)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.buffer.readline()

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

def evl(x):
    cnt = 0
    for i in range(n):
        if a[i] >= 0:
            l, r = -1, n
            while r-l > 1:
                mid = (l+r) // 2
                if x >= a[i] * a[mid]: l = mid
                else: r = mid
            cnt += max(0, l-i)
        else:
            l, r = -1, n
            while r-l > 1:
                mid = (l+r) // 2
                if x >= a[i] * a[mid]: r = mid
                else: l = mid
            cnt += n - max(i+1, r)
    return cnt >= k

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

Submission status: Wrong Answer

Solution code:
import collections
import heapq
n,k = map(int, raw_input().split(' '))
es = map(int, raw_input().split(' '))

es.sort()
m = -1

heap = [(es[i]*es[n-1],i,n-1) for i in range(n-1)]
heapq.heapify(heap)
while(k):
	v,i,j = heapq.heappop(heap)
	if j - 1 != i: heapq.heappush(heap, (es[i]*es[j-1],i,j-1))
	k-=1
print v

Submission status: Wrong Answer

Solution code:
#https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-02-16abc-155
import numpy as np
N,K=map(int,input().split())
A=np.array(list(map(int,input().split())))
A.sort()
G=A[A>0]
Z=A[A==0]
L=A[A<0]
 
ok=10**18+1
ng=-10**18-1
 
#x以下がK個以上であるxの最小値
 
while ok-ng>1:
  mid = (ng+ok)//2
  #mid以下のペアの個数を数える
  
  #正のもののうち、mid以下のペアの個数を数える
  cg=np.searchsorted(A,mid//G,side="right").sum()
  
  #負のもののうちmid以下のペアの個数を数える
  cl=(N-np.searchsorted(A,(-mid-1)//(-L),side="right")).sum()
  
  #同じ数字同士の積がmid以下のものを数える
  d = np.count_nonzero(A*A <= mid)
  
  #0がmid以下なら、それもプラスするために必要
  if mid<=0:
    z=len(Z)*N
  
  c=cg+cl+z-d
  
  #二重になっているので、割る
  c //=2
  
  #mid以下のペアの個数がK個以上のとき
  if c>=K:
    ok=mid
  else:
    ng=mid
    
print(ok)

Submission status: Wrong Answer

Solution code:
#https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-02-16abc-155
import numpy as np
N,K=map(int,input().split())
A=np.array(list(map(int,input().split())))
A.sort()
G=A[A>0]
Z=A[A==0]
L=A[A<0]

ok=10**18+1
ng=-10**18-1

#x以下がK個以上であるxの最小値

while ok-ng>1:
  mid = (ng+ok)//2
  #mid以下のペアの個数を数える
  
  #正のもののうち、mid以下のペアの個数を数える
  cg=np.searchsorted(A,mid//G,side="right").sum()
  
  #負のもののうちmid以下のペアの個数を数える
  cl=(N-np.searchsorted(A,(-mid-1)//(-L),side="right")).sum()
  
  #同じ数字同士の積がmid以下のものを数える
  d = np.count_nonzero(A*A <= mid)
  
  #0がmid以下なら、それもプラスするために必要
  if mid<=0:
    z=len(Z)*N
  
  c=cg+cl+z-d
  
  #二重になっているので、割る
  c //=2
  
  #mid以下のペアの個数がK個以上のとき
  if c>=K:
    ok=mid
  else:
    ng=mid
    
print(ok)

Submission status: Wrong Answer

Solution code:
#https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-02-16abc-155
import numpy as np
N,K=map(int,input().split())
A=np.array(list(map(int,input().split())))
A.sort()
G=A[A>0]
Z=A[A==0]
L=A[A<0]

ok=10**18+1
ng=-10**18-1

#x以下がK個以上であるxの最小値

while ok-ng>1:
  mid = (ng+ok)//2
  #mid以下のペアの個数を数える
  
  #正のもののうち、mid以下のペアの個数を数える
  cg=np.searchsorted(A,mid//G,side="right").sum()
  
  #負のもののうちmid以下のペアの個数を数える
  cl=(N-np.searchsorted(A,(-mid-1)//(-L),side="right")).sum()
  
  #同じ数字同士の積がmid以下のものを数える
  d = np.count_nonzero(A*A <= mid)
  
  #0がmid以下なら、それもプラスするために必要
  z=0
  if mid<=0:
    z+=len(Z)*N
  
  c=cg+cl+z-d
  
  #二重になっているので、割る
  c //=2
  
  #mid以下のペアの個数がK個以上のとき
  if c>=K:
    ok=mid
  else:
    ng=mid
    
print(ok)

Submission status: Wrong Answer

Solution code:
import bisect, sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

pl = []
mi = []
ze = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(-x)
    else:
        ze += 1

p, m = len(pl), len(mi)
res1 = p * m
res2 = (p + m) * ze + ze * (ze - 1) // 2

#K番目が負
if res1 >= k:
    pl.sort(reverse=True)
    mi.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = p * m
        tmp = 0
        for i in range(p):
            while tmp < m and pl[i] * mi[tmp] < x:
                tmp += 1
            cnt -= tmp
        if cnt < k:
            r = x
        else:
            l = x
    print(-l)

#K番目が0
elif res1 + res2 >= k:
    print(0)

#K番目が正
else:
    k = k - res1 - res2
    pl.sort(reverse=True)
    pl2 = pl[::-1]
    mi.sort(reverse=True)
    mi2 = mi[::-1]
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = 0
        tmp = 0
        for i in range(p):
            while tmp < p and pl[i] * pl2[tmp] <= x:
                tmp += 1
            cnt += tmp
        if cnt < k:
            r = x
        else:
            l = x
    print(r)

Submission status: Wrong Answer

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

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

from bisect import bisect_left, bisect_right

def count(x,i):
    if A[i]<0:
        l = bisect_left(A, x//A[i])
        return N-l
    elif A[i]>0:
        r = bisect_right(A, x//A[i])
        return r
    else:
        if x>=0:
            return N
        else:
            return 0

def is_ok(x):
    cnt = 0
    for i in range(N):
        cnt += count(x,i)
        if A[i]*A[i]<=x:
            cnt-=1
    cnt = cnt//2
    return cnt>=K

def main():
        #初期値設定
    ok = 10**18+1
    ng = -10**18-1
    while ok-ng > 1:
        mid = (ok+ng) // 2 # 平均(小数切り捨て)
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    print(ok)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
mi=[]
pu=[]
ze=[]
lp=0
lz=0
lm=0
for i in A:
    if i>0:
        pu.append(i)
        lp+=1
    elif i==0:
        ze.append(i)
        lz+=1
    else:
        mi.append(-i)
        lm+=1
P=lp*(lp-1)//2+lm*(lm-1)//2
Z=lz*(lp+lm)+lz*(lz-1)//2
M=lp*lm
mi.sort()
pu.sort()
if K<=M:
    l=0
    r=10**18
    K=M-K
    while r-l!=1:
        a=(l+r)//2
        numa=0
        pos=lp-1
        for i in range(lm):
            while pos!=-1:
                if pu[pos]>a//mi[i]:
                    pos-=1
                else:
                    break
            numa+=pos+1
        if numa>=K:
            r=a
        else:
            l=a
    print(-r)
elif K<=M+Z:
    print(0)
else:
    k=K-M-Z
    l=0
    r=10**18
    while r-l!=1:
        a=(l+r)//2
        cnt1=0
        cnt2=0
        pos1=lm-1
        pos2=lp-1
        for i in range(lm):
            tmp=0
            while pos1!=-1:
                if mi[pos1]>a//mi[i]:
                    pos1-=1
                else:
                    break
            tmp+=pos1+1
            if mi[i]**2<a:
                tmp-=1
            cnt1+=tmp
        for i in range(lp):
            tmp=0
            while pos2!=-1:
                if pu[pos2]>a//pu[i]:
                    pos2-=1
                else:
                    break
            tmp+=pos2+1
            if pu[i]**2<a:
                tmp-=1
            cnt2+=tmp
        numa=(cnt1+cnt2)//2
        if numa>=k:
            r=a
        else:
            l=a
    print(r)

Submission status: Wrong Answer

Solution code:
import bisect
N,K=map(int,input().split())
A=list(map(int,input().split()))
mi=[]
pu=[]
ze=[]
for i in A:
    if i>0:
        pu.append(i)
    elif i==0:
        ze.append(i)
    else:
        mi.append(i)
P=len(pu)*(len(pu)-1)//2+len(mi)*(len(mi)-1)//2
Z=len(ze)*(len(pu)+len(mi))+len(ze)*(len(ze)-1)//2
M=len(pu)*len(mi)
if K<=M:
    mi.sort()
    pu.sort()
    l=mi[0]*pu[-1]
    r=0
    while 1:
        a=(l+r)//2
        numa=0
        for i in mi:
            b=a//i
            if a%i==0:
                c=bisect.bisect_left(pu,b)
            else:
                c=bisect.bisect_right(pu,b)
            numa+=len(pu)-c
            if numa>K:
                break
        if numa>=K:
            r=a
        else:
            l=a
        if abs(l-r)<=1:
            break
    print(r)
elif K<=M+Z:
    print(0)
else:
    mi.sort()
    pu.sort()
    k=K-M-Z
    l=0
    r=10**18
    while 1:
        a=(l+r)//2
        numa=0
        if len(mi)>1:
            for i in range(len(mi)):
                b=a//mi[i]
                if a%mi[i]==0:
                    c=bisect.bisect_left(mi,b)
                else:
                    c=bisect.bisect_right(mi,b)
                if c>i:
                    numa+=len(mi)-c
                else:
                    numa+=len(mi)-c-i-1
                if c==len(mi):
                    break
                if numa>=k:
                    break
        if len(pu)>1:
            for j in range(len(pu)):
                if numa>=k:
                    break
                b=a//pu[j]
                c=bisect.bisect_right(pu,b)
                if c>=j+1:
                    numa+=c-j-1
                else:
                    break
        if numa>=k:
            r=a
        else:
            l=a
        if abs(l-r)<=1:
            break
    print(r)

Submission status: Wrong Answer

Solution code:
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
negative_number = []
positive_number = []
zero_cnt = 0
a.sort()
def binary_search(left, right,positive):
    if right - left <= 1:
        return right
    middle = (right + left) // 2
    if is_can(middle,positive):
        return binary_search(left, middle,positive)
    else:
        return binary_search(middle, right,positive)
def is_can(x,positive):
    #xよりも小さい値がk個あるかどうか？
    if positive:
        count = than_less_zero
        #正＊正
        r = len(positive_number)-1
        for l in range(len(positive_number)):
            while l < r and positive_number[l] * positive_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #負*負
        r = len(negative_number)-1
        for l in range(len(negative_number)):
            while l < r and r_negative_number[l] * r_negative_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #print("target:{} count:{}".format(x,count))
        if count >= k:
            return True
        else:
            return False
    else:
        count = 0
        l,r = 0,0
        for l in range(len(negative_number)):
            while r < len(positive_number) and positive_number[r] * negative_number[l] > x:
                r += 1
            count += len(positive_number) - r
        if count >= k:
            return True
        else:
            return False



for i in range(n):
    if a[i] > 0:
        positive_number.append(a[i])
    elif a[i] < 0:
        negative_number.append(a[i])
    else:
        zero_cnt += 1
than_less_zero = ( len(negative_number) * len(positive_number) ) + (zero_cnt * (zero_cnt-1)//2) + zero_cnt * (n-zero_cnt)
r_negative_number = [negative_number[i] for i in range(len(negative_number)-1,-1,-1)]

if than_less_zero < k:
    #答えが正になる
    print(binary_search(0,10**20,True))
elif ( len(negative_number) * len(positive_number) ) < k:
    #答えが0になる
    print(0)
else:
    #答えが負になる
    print(binary_search((-10)**20,5,False))

Submission status: Wrong Answer

Solution code:
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
negative_number_cnt = 0
positive_number_cnt = 0
negative_number = []
positive_number = []
zero_cnt = 0
a.sort()
def binary_search(left, right,positive):
    if right - left <= 1:
        return right
    middle = (right + left) // 2
    if is_can(middle,positive):
        return binary_search(left, middle,positive)
    else:
        return binary_search(middle, right,positive)
def is_can(x,positive):
    #xよりも小さい値がk個あるかどうか？
    if positive:
        count = than_less_zero
        #正＊正
        r = len(positive_number)-1
        for l in range(len(positive_number)):
            while l < r and positive_number[l] * positive_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #負*負
        r = len(negative_number)-1
        for l in range(len(negative_number)):
            while l < r and r_negative_number[l] * r_negative_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #print("target:{} count:{}".format(x,count))
        if count >= k:
            return True
        else:
            return False
    else:
        count = 0
        l,r = 0,0
        for l in range(len(negative_number)):
            while r < len(positive_number) and positive_number[r] * negative_number[l] > x:
                r += 1
            count += len(positive_number) - r
        if count >= k:
            return True
        else:
            return False



for i in range(n):
    if a[i] > 0:
        positive_number_cnt += 1
        positive_number.append(a[i])
    elif a[i] < 0:
        negative_number_cnt += 1
        negative_number.append(a[i])
    else:
        zero_cnt += 1
than_less_zero = ( negative_number_cnt * positive_number_cnt ) + (zero_cnt * (zero_cnt-1)//2) + zero_cnt * (n-zero_cnt)
r_negative_number = [negative_number[i] for i in range(len(negative_number)-1,-1,-1)]

if than_less_zero < k:
    #答えが正になる
    print(binary_search(0,10**20,True))
elif ( negative_number_cnt * positive_number_cnt ) < k:
    #答えが0になる
    print(0)
else:
    #答えが負になる
    print(binary_search((-10)*20,5,False))

Submission status: Wrong Answer

Solution code:
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
negative_number_cnt = 0
positive_number_cnt = 0
negative_number = []
positive_number = []
zero_cnt = 0
a.sort()
def binary_search(left, right,positive):
    if right - left <= 1:
        return right
    middle = (right + left) // 2
    if is_can(middle,positive):
        return binary_search(left, middle,positive)
    else:
        return binary_search(middle, right,positive)
def is_can(x,positive):
    #xよりも小さい値がk個あるかどうか？
    if positive:
        count = than_less_zero
        #正＊正
        r = len(positive_number)-1
        for l in range(len(positive_number)):
            while l < r and positive_number[l] * positive_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #負*負
        r = len(negative_number)-1
        for l in range(len(negative_number)):
            while l < r and r_negative_number[l] * r_negative_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #print("target:{} count:{}".format(x,count))
        if count >= k:
            return True
        else:
            return False
    else:
        count = 0
        l,r = 0,0
        for l in range(len(negative_number)):
            while r < len(positive_number) and positive_number[r] * negative_number[l] > x:
                r += 1
            count += len(positive_number) - r
        if count >= k:
            return True
        else:
            return False



for i in range(n):
    if a[i] > 0:
        positive_number_cnt += 1
        positive_number.append(a[i])
    elif a[i] < 0:
        negative_number_cnt += 1
        negative_number.append(a[i])
    else:
        zero_cnt += 1
than_less_zero = ( negative_number_cnt * positive_number_cnt ) + (zero_cnt * (zero_cnt-1)//2) + zero_cnt * (n-zero_cnt)
r_negative_number = [negative_number[i] for i in range(len(negative_number)-1,-1,-1)]

if than_less_zero < k:
    #答えが正になる
    print(binary_search(0,10**20,True))
elif ( negative_number_cnt * positive_number_cnt ) >= k:
    #答えが負になる
    print(binary_search(-10*20,0,False))
else:
    #答えが0になる
    print(0)

Submission status: Wrong Answer

Solution code:
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
negative_number_cnt = 0
positive_number_cnt = 0
negative_number = []
positive_number = []
zero_cnt = 0
a.sort()
def binary_search(left, right,positive):
    if right - left <= 1:
        return right
    middle = (right + left) // 2
    if is_can(middle,positive):
        return binary_search(left, middle,positive)
    else:
        return binary_search(middle, right,positive)
def is_can(x,positive):
    #xよりも小さい値がk個あるかどうか？
    if positive:
        count = than_less_zero
        #正＊正
        r = len(positive_number)-1
        for l in range(len(positive_number)):
            while l < r and positive_number[l] * positive_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #負*負
        r = len(negative_number)-1
        for l in range(len(negative_number)):
            while l < r and r_negative_number[l] * r_negative_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #print("target:{} count:{}".format(x,count))
        if count >= k:
            return True
        else:
            return False
    else:
        count = 0
        l,r = 0,0
        for l in range(len(positive_number)):
            while r < len(negative_number) and positive_number[l] * negative_number[r] <= x:
                r += 1
            count += r
        if count >= k:
            return True
        else:
            return False



for i in range(n):
    if a[i] > 0:
        positive_number_cnt += 1
        positive_number.append(a[i])
    elif a[i] < 0:
        negative_number_cnt += 1
        negative_number.append(a[i])
    else:
        zero_cnt += 1
than_less_zero = ( negative_number_cnt * positive_number_cnt ) + (zero_cnt * (zero_cnt-1)//2) + zero_cnt * (n-zero_cnt)
r_negative_number = [negative_number[i] for i in range(len(negative_number)-1,-1,-1)]

if than_less_zero < k:
    #答えが正になる
    print(binary_search(0,10**20,True))
elif ( negative_number_cnt * positive_number_cnt ) >= k:
    #答えが負になる
    print(binary_search(-10*20,0,False))
else:
    #答えが0になる
    print(0)

Submission status: Wrong Answer

Solution code:
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
negative_number_cnt = 0
positive_number_cnt = 0
negative_number = []
positive_number = []
zero_cnt = 0
a.sort()
def binary_search(left, right,positive):
    #print("left:{} right:{}".format(left,right))
    if right - left <= 1:
        return right
    middle = (right + left) // 2
    if is_can(middle,positive):
        return binary_search(left, middle,positive)
    else:
        return binary_search(middle, right,positive)
def is_can(x,positive):
    #xよりも小さい値がk個あるかどうか？
    if positive:
        count = than_less_zero
        p_p = 0
        n_n = 0
        #正＊正
        for i in range(len(positive_number)):
            index = bisect.bisect_right(positive_number,x / positive_number[i])
            if positive_number[i] <= x/positive_number[i]:
                p_p -= 1
            p_p += index
        p_p /= 2
        count += p_p
        #print(p_p)
        #負*負
        #print("target:{} count:{}".format(x,count))
        for i in range(len(negative_number)):
            index = bisect.bisect_right(inv_negative, x/inv_negative[i])
            if inv_negative[i] <= x/inv_negative[i]:
                n_n -= 1
            n_n += index
        n_n /= 2
        count += n_n
        #print("target:{} count:{}".format(x,count))
        if count >= k:
            return True
        else:
            return False
    else:
        count = 0
        for i in range(len(positive_number)-1,-1,-1):
            index = bisect.bisect_left(inv_negative, -x/positive_number[i])
            count += (negative_number_cnt - index)
        if count >= k:
            return True
        else:
            return False


for i in range(n):
    if a[i] > 0:
        positive_number_cnt += 1
        positive_number.append(a[i])
    elif a[i] < 0:
        negative_number_cnt += 1
        negative_number.append(a[i])
    else:
        zero_cnt += 1
than_less_zero = ( negative_number_cnt * positive_number_cnt ) + (zero_cnt * (zero_cnt-1)//2) + zero_cnt * (n-zero_cnt)
inv_negative = [-i for i in negative_number]
inv_negative.reverse()
if than_less_zero < k:
    #答えが正になる
    print(binary_search(0,10**20,True))
elif ( negative_number_cnt * positive_number_cnt ) >= k:
    #答えが負になる
    print(binary_search(-10*20,0,False))
else:
    #答えが0になる
    print(0)
#print(is_can(10**20,True))

Submission status: Wrong Answer

Solution code:
# inin=[list(map(int,i.split())) for i in Input.split('\n')]
# N,K=inin[0]
# A=inin[1]

N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
l_neglis=0
l_poslis=0
l_zerolis=0
A=sorted(A)
for i in A:
    if i>0:
        l_poslis+=1
    elif i<0:
        l_neglis+=1
    else:
        l_zerolis+=1
        
# l_neglis=len(neglis)
# l_poslis=len(poslis)
# l_zerolis=len(zerolis)
neg=l_neglis*l_poslis
pos=l_neglis*(l_neglis-1)//2+l_poslis*(l_poslis-1)//2
zero=l_zerolis*(l_neglis+l_poslis)+l_zerolis*(l_zerolis-1)//2
# neglis=neglis[::-1]

if K<=neg:
    poslis=[]
    neglis=[]
    zerolis=[]
    for i in A:
        if i>0:
            poslis.append(i)
        elif i<0:
            neglis.append(i)
        else:
            zerolis.append(i)
            
    r=-1
    l=neglis[0]*poslis[-1]
    while 1!=r-l:
        mid=(r+l)//2
        counter=0
        for i in range(l_neglis):
            for j in range(l_poslis):
                if neglis[i]*poslis[-1-j]>mid:
                    continue
                else:
                    counter+=(l_poslis-j)
                    break
        if counter>=K:
            r=mid
        else:
            l=mid 
    print(r)
elif K<=neg+zero:
    print(0)
else:
    poslis=[]
    neglis=[]
    zerolis=[]
    for i in A:
        if i>0:
            poslis.append(i)
        elif i<0:
            neglis.append(i)
        else:
            zerolis.append(i)
    l=0
    r=10**18+1
    K-=(neg+zero)
    while r-l!=1:
        mid=(r+l)//2
        counter=0
        for i in range(l_neglis-1):
            for j in range(i+1,l_neglis):
                if neglis[i]*neglis[j]>mid:
                    continue
                else:
                    counter+=(l_neglis-j)
                    break
        for i in range(l_poslis-1):
            for j in range(i+1,l_poslis):
                if poslis[-1-i]*poslis[-1-j]>mid:
                    continue
                else:
                    counter+=(l_poslis-j)
                    break
        if counter>=K:
            r=mid
        else:
            l=mid 
    print(r)

Submission status: Wrong Answer

Solution code:
# inin=[list(map(int,i.split())) for i in Input.split('\n')]
# N,K=inin[0]
# A=inin[1]

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

A=sorted(A)
poslis=[]
neglis=[]
zerolis=[]
for i in A:
    if i>0:
        poslis.append(i)
    elif i<0:
        neglis.append(i)
    else:
        zerolis.append(i)
l_neglis=len(neglis)
l_poslis=len(poslis)
l_zerolis=len(zerolis)
neg=l_neglis*l_poslis
pos=l_neglis*(l_neglis-1)//2+l_poslis*(l_poslis-1)//2
zero=l_zerolis*(l_neglis+l_poslis)+l_zerolis*(l_zerolis-1)//2
# neglis=neglis[::-1]

if K<=neg:
    r=-1
    l=neglis[0]*poslis[-1]
    while 1!=r-l:
        mid=(r+l)//2
        counter=0
        for i in range(l_neglis):
            for j in range(l_poslis):
                if neglis[i]*poslis[-1-j]>mid:
                    continue
                else:
                    counter+=(l_poslis-j)
                    break
        if counter>=K:
            r=mid
        else:
            l=mid 
    print(r)
elif K<=neg+zero:
    print(0)
else:
    l=0
    r=10**18+1
    K-=(neg+zero)
    while r-l!=1:
        mid=(r+l)//2
        counter=0
        for i in range(l_neglis-1):
            for j in range(i+1,l_neglis):
                if neglis[i]*neglis[j]>mid:
                    continue
                else:
                    counter+=(l_neglis-j)
                    break
        for i in range(l_poslis-1):
            for j in range(i+1,l_poslis):
                if poslis[-1-i]*poslis[-1-j]>mid:
                    continue
                else:
                    counter+=(l_poslis-j)
                    break
        if counter>=K:
            r=mid
        else:
            l=mid 
    print(r)