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:
import bisect

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
# 積がx未満となるペアの個数totがK個未満となるxの最大値を二分探索で求める
# lがOK,rがNG
l_x = -10**19
r_x = 10**19
while l_x + 1 < r_x:
    x = (l_x + r_x)//2
    tot = 0
    # 積がx未満となるペアの個数を求めてtotに追加する
    for i in range(N):
        a = A[i]
        if a > 0:
            n = bisect.bisect_left(A, (x+a-1)//a)
            tot += n
            if a*a < x:
                tot -= 1
        elif a < 0:
            n = bisect.bisect_right(A, (x+a-1)//a)
            tot += N-n
            if a*a < x:
                tot-= 1
        else:
            if x > 0:
                tot += N - 1
    tot /= 2
    if tot < K:
        l_x = x
    else:
        r_x = x
print(l_x)

Submission status: Wrong Answer

Solution code:
import itertools,collections
a,b=map(int,input().split(" "))
l1=map(int,input().split(" "))
l1=list(sorted(l1))

cp=list(itertools.combinations(l1,2))
we=list(sorted([i*j for i,j in cp]))
print(we[2])

Submission status: Wrong Answer

Solution code:
import itertools,collections
a,b=map(int,input().split(" "))
l1=map(int,input().split(" "))
l1=list(sorted(l1))

cp=list(itertools.combinations(l1,2))
we=[i*j for i,j in cp]
print(we[2])

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K = (int(x) for x in input().split())
A = np.array([int(x) for x in input().split()])
A.sort()

zero = len(A[A==0]) #0の数
pos = A[A > 0]
neg = A[A < 0]

p_cnt = len(pos)  #正の数
n_cnt = len(neg)  #負の数

#積の個数
p__cnt = (n_cnt * (n_cnt-1))//2 + (p_cnt * (p_cnt-1))//2
z__cnt = zero*(p_cnt+n_cnt) + (zero * (zero-1))//2
n__cnt = p_cnt*n_cnt

#K番目の値が負の場合
if K <= n__cnt:
    
    #二分探索の準備
    r = 0
    l = -pow(10,18)-1

    #二分探索
    while r-l != 1:
        mid = (l+r)//2
        cnt = 0
        cnt_p = p_cnt - 1

        '''
        尺取り法
        ある数が条件を満たさなくなった時点で次の数に変える
        '''
        
        for i in range(n_cnt):
            while cnt_p != -1:
                if pos[cnt_p] > mid//neg[i]:
                    cnt_p -= 1
                    cnt += 1
                else:
                    break

            #cnt_p = 0になっているので元に戻す
            cnt_p = p_cnt - 1
                    
        if cnt > K:
            r = mid
        else:
            l = mid

    print(l)
            

#K番目の値が0のとき
elif K <= n__cnt + z__cnt:
    print(0)
    
#K番目の値が正の数の時
else:

    #Kから負と0になる組み合わせを引く
    K -= (z__cnt + n__cnt)
    
    #二分探索の準備
    r = pow(10,18)+1
    l = 0
    cnt = 0

    #二分探索
    while r-l != 1:
        mid = (l+r)//2
        cnt1 = 0

        #尺取り法で、ある数より下回る数を数える
        for i in range(p_cnt):
            
            for j in range(p_cnt):
                if pos[j] <= mid//pos[i]:
                    cnt1 += 1
                else:
                    break

            #同じやつを引く
            if pos[i] <= mid//pos[i]:
                cnt1 -= 1

        cnt1 = cnt1 // 2 #同じ組み合わせがあるので削除
        cnt2 = 0
        cnt_n = n_cnt - 1

        #尺取り法で、ある数より下回る数を数える
        for i in range(n_cnt-1,-1,-1):
            
            while cnt_n != -1:
                if neg[cnt_n] >= mid//neg[i]:
                    cnt_n -= 1
                    cnt2 += 1
                else:
                    break

            #同じやつを引く
            if neg[i] >= mid//neg[i]:
                cnt2 -= 1

            cnt_n = n_cnt - 1

        cnt2 = cnt2 // 2
        cnt = cnt1 + cnt2

        if cnt >= K:
            r = mid
        else:
            l = mid

    print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K = (int(x) for x in input().split())
A = np.array([int(x) for x in input().split()])
A.sort()

zero = len(A[A==0]) #0の数
pos = A[A > 0]
neg = A[A < 0]

p_cnt = len(pos)  #正の数
n_cnt = len(neg)  #負の数

#積の個数
p__cnt = (n_cnt * (n_cnt-1))//2 + (p_cnt * (p_cnt-1))//2
z__cnt = zero*(p_cnt+n_cnt) + (zero * (zero-1))//2
n__cnt = p_cnt*n_cnt

#K番目の値が負の場合
if K <= n__cnt:
    
    #二分探索の準備
    r = 0
    l = -pow(10,18)-1

    #二分探索
    while r-l != 1:
        mid = (l+r)//2
        cnt = 0
        cnt_p = p_cnt - 1

        '''
        尺取り法
        ある数が条件を満たさなくなった時点で次の数に変える
        '''
        
        for i in range(n_cnt):
            while cnt_p != -1:
                if pos[cnt_p] > mid//neg[i]:
                    cnt_p -= 1
                    cnt += 1
                else:
                    break

            #cnt_p = 0になっているので元に戻す
            cnt_p = p_cnt - 1
                    
        if cnt > K:
            r = mid
        else:
            l = mid

    print(l)
            

#K番目の値が0のとき
elif K <= n__cnt + z__cnt:
    print(0)
    
#K番目の値が正の数の時
else:

    #Kから負と0になる組み合わせを引く
    K -= (z__cnt + n__cnt)
    
    #二分探索の準備
    r = pow(10,18)+1
    l = 0
    cnt = 0

    #二分探索
    while r-l != 1:
        mid = (l+r)//2
        cnt1 = 0

        #尺取り法で、ある数より下回る数を数える
        for i in range(p_cnt):
            tmp = 0
            
            for j in range(p_cnt):
                if pos[j] <= mid//pos[i]:
                    tmp += 1
                else:
                    break

            #同じやつを引く
            if pos[i] <= mid//pos[i]:
                tmp -= 1

            cnt1 += tmp

        cnt1 = cnt1 // 2 #同じ組み合わせがあるので削除
        cnt2 = 0
        cnt_n = n_cnt - 1

        #尺取り法で、ある数より下回る数を数える
        for i in range(n_cnt-1,-1,-1):
            tmp = 0
            
            while cnt_n != -1:
                if neg[cnt_n] >= mid//neg[i]:
                    cnt_n -= 1
                    tmp += 1
                else:
                    break

            #同じやつを引く
            if neg[i] >= mid//neg[i]:
                tmp -= 1

            cnt2 += tmp
            cnt_n = n_cnt - 1

        cnt2 = cnt2 // 2
        cnt = cnt1 + cnt2

        if cnt >= K:
            r = mid
        else:
            l = mid

    print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K = (int(x) for x in input().split())
A = np.array([int(x) for x in input().split()])
A.sort()
str = 'ok'

zero = len(A[A==0]) #0の数
pos = A[A > 0]
neg = A[A < 0]

p_cnt = len(pos)  #正の数
n_cnt = len(neg)  #負の数

#積の個数
p__cnt = (n_cnt * (n_cnt-1))//2 + (p_cnt * (p_cnt-1))//2
z__cnt = zero*(p_cnt+n_cnt) + (zero * (zero-1))//2
n__cnt = p_cnt*n_cnt

#K番目の値が負の場合
if K <= n__cnt:
    
    #二分探索の準備
    r = 0
    l = -pow(10,18)-1

    #二分探索
    while r-l != 1:
        mid = (l+r)//2
        cnt = 0
        cnt_p = p_cnt - 1

        '''
        尺取り法
        ある数が条件を満たさなくなった時点で次の数に変える
        '''
        
        for i in range(n_cnt):
            while cnt_p != -1:
                if pos[cnt_p] > mid//neg[i]:
                    cnt_p -= 1
                    cnt += 1
                else:
                    break

            #cnt_p = 0になっているので元に戻す
            cnt_p = p_cnt - 1
                    
        if cnt > K:
            r = mid
        else:
            l = mid

    print(l)
            

#K番目の値が0のとき
elif K <= n__cnt + z__cnt:
    print(0)
    
#K番目の値が正の数の時
else:

    #Kから負と0になる組み合わせを引く
    K -= (z__cnt + n__cnt)
    
    #二分探索の準備
    r = pow(10,18)+1
    l = 0
    cnt = 0

    #二分探索
    while r-l != 1:
        mid = (l+r)//2
        cnt1 = 0

        #尺取り法で、ある数より下回る数を数える
        for i in range(p_cnt):
            tmp = 0
            
            for j in range(p_cnt):
                if pos[j] <= mid//pos[i]:
                    tmp += 1
                else:
                    break

            #同じやつを引く
            if pos[i]**2 <= mid:
                tmp -= 1

            cnt1 += tmp

        cnt1 = cnt1 // 2 #同じ組み合わせがあるので削除
        cnt2 = 0
        cnt_n = n_cnt - 1

        #尺取り法で、ある数より下回る数を数える
        for i in range(n_cnt-1,-1,-1):
            tmp = 0
            
            while cnt_n != -1:
                if neg[cnt_n] >= mid//neg[i]:
                    cnt_n -= 1
                    tmp += 1
                else:
                    break

            #同じやつを引く
            if neg[i]**2 <= mid:
                tmp -= 1

            cnt2 += tmp
            cnt_n = n_cnt - 1

        cnt2 = cnt2 // 2
        cnt = cnt1 + cnt2

        if cnt >= K:
            r = mid
        else:
            l = mid

    print(r)

Submission status: Wrong Answer

Solution code:
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    ans = 0
    A_neg.sort()
    A_pos.sort()
    #print(A_neg)
    #print(neg,pos,num_0)
    if neg*pos>K:
        l = 1 ; r = A_neg[-1]*A_pos[-1]+1
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            for a in A_neg:
                next = bisect.bisect_left(A_pos,-(-now//a))
                cur += (pos-next)
                #print(next,now//a)
            if cur<K:
                r = now
            else:
                l = now
            #print(now,cur)
        ans = -l
    elif (N-num_0)*num_0+num_0*(num_0-1)//2+neg*pos>=K:
        ans = 0
    else:
        need = K-((pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos)
        #print(need)
        l = 0; r = 1
        if neg>=2:
            r = A_neg[-1]*A_neg[-2]
        if pos>=2:
            r = max(r,A_pos[-1]*A_pos[-2])
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            if neg>=2:
                for a in A_neg:
                    next = bisect.bisect_right(A_neg, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            if pos>=2:
                for a in A_pos:
                    next = bisect.bisect_right(A_pos, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            cur //= 2
            if cur<need:
                l = now
            else:
                r = now
            #print(now,cur,need)
        ans = r
    print(ans)
    return
"""
10 43
5 4 3 2 -1 0 0 0 0 0
"""

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    for i in range(N-1,-1,-1):
        #print(ans)
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    #print(dp)
    ans = min(dp[-1][0],dp[-1][1])
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""
4396817
"""

Submission status: Wrong Answer

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

A=np.array(A)

A_pos=A[A>0]
A_neg=A[A<0]
A_neg2=np.sort(-A_neg)
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_neg-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=0
    for v in A_pos:
        if v**2<x:
            tmp+=1
    z=(z.sum()-tmp)//2
    tmp=0
    for v in A_neg:
        if v**2<x:
            tmp+=1
    w=(w.sum()-tmp)//2
    return z+w

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)

Submission status: Wrong Answer

Solution code:
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    ans = 0
    A_neg.sort()
    A_pos.sort()
    #print(A_neg)
    #print(neg,pos,num_0)
    if neg*pos>=K:
        l = 1 ; r = A_neg[-1]*A_pos[-1]+1
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            for a in A_neg:
                next = bisect.bisect_left(A_pos,-(-now//a))
                cur += (pos-next)
                #print(next,now//a)
            if cur<K:
                r = now
            else:
                l = now
            #print(now,cur)
        ans = -l
    elif (N-num_0)*num_0+num_0*(num_0-1)//2+neg*pos>=K:
        ans = 0
    else:
        return
        need = K-((pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos)
        #print(need)
        l = 0; r = 1
        if neg>=2:
            r = A_neg[-1]*A_neg[-2]+1
        if pos>=2:
            r = max(r,A_pos[-1]*A_pos[-2]+1)
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            if neg>=2:
                for a in A_neg:
                    next = bisect.bisect_right(A_neg, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            if pos>=2:
                for a in A_pos:
                    next = bisect.bisect_right(A_pos, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            cur //= 2
            if cur<need:
                l = now
            else:
                r = now
            #print(now,cur,need)
        ans = r
    print(ans)
    return
"""
10 43
5 4 3 2 -1 0 0 0 0 0
"""

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    for i in range(N-1,-1,-1):
        #print(ans)
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    #print(dp)
    ans = min(dp[-1][0],dp[-1][1])
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""
4396817
"""

Submission status: Wrong Answer

Solution code:
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    ans = 0
    A_neg.sort()
    A_pos.sort()
    #print(A_neg)
    #print(neg,pos,num_0)
    if neg*pos>=K:
        l = 1 ; r = A_neg[-1]*A_pos[-1]+1
        while(r-l>2):
            now = (l+r)//2
            cur = 0
            for a in A_neg:
                next = bisect.bisect_left(A_pos,-(-now//a))
                cur += (pos-next)
                #print(next,now//a)
            if cur<K:
                r = now
            else:
                l = now
            #print(now,cur)
        ans = -l
    elif (N-num_0)*num_0+num_0*(num_0-1)//2+neg*pos>=K:
        ans = 0
    else:
        need = K-((pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos)
        #print(need)
        l = 0; r = 1
        if neg>=2:
            r = A_neg[-1]*A_neg[-2]+1
        if pos>=2:
            r = max(r,A_pos[-1]*A_pos[-2]+1)
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            if neg>=2:
                for a in A_neg:
                    next = bisect.bisect_right(A_neg, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            if pos>=2:
                for a in A_pos:
                    next = bisect.bisect_right(A_pos, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            cur //= 2
            if cur<need:
                l = now
            else:
                r = now
            #print(now,cur,need)
        ans = r
    print(ans)
    return
"""
10 43
5 4 3 2 -1 0 0 0 0 0
"""

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    for i in range(N-1,-1,-1):
        #print(ans)
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    #print(dp)
    ans = min(dp[-1][0],dp[-1][1])
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""
4396817
"""

Submission status: Wrong Answer

Solution code:
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    ans = 0
    A_neg.sort()
    A_pos.sort()
    #print(A_neg)
    #print(neg,pos,num_0)
    if neg*pos>=K:
        l = 0 ; r = A_neg[-1]*A_pos[-1]+1
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            for a in A_neg:
                next = bisect.bisect_left(A_pos,now/a)
                cur += (pos-next)
                #print(next,now//a)
            if cur<K:
                r = now
            else:
                l = now
            #print(now,cur)
        ans = -l
    elif (N-num_0)*num_0+num_0*(num_0-1)//2+neg*pos>=K:
        ans = 0
    else:
        need = K-((pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos)
        #print(need)
        l = 0; r = 1
        if neg>=2:
            r = A_neg[-1]*A_neg[-2]+1
        if pos>=2:
            r = max(r,A_pos[-1]*A_pos[-2]+1)
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            if neg>=2:
                for a in A_neg:
                    next = bisect.bisect_right(A_neg, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            if pos>=2:
                for a in A_pos:
                    next = bisect.bisect_right(A_pos, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            cur //= 2
            if cur<need:
                l = now
            else:
                r = now
            #print(now,cur,need)
        ans = r
    print(ans)
    return
"""
10 43
5 4 3 2 -1 0 0 0 0 0
"""

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    for i in range(N-1,-1,-1):
        #print(ans)
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    #print(dp)
    ans = min(dp[-1][0],dp[-1][1])
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""
4396817
"""

Submission status: Wrong Answer

Solution code:
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()
    A_neg = []; neg = 0
    A_0 = []; num_0 = 0
    A_pos = []; pos = 0
    for a in A:
        if a<0:
            A_neg.append(-a)
            neg += 1
        elif a==0:
            A_0.append(a)
            num_0 += 1
        else:
            A_pos.append(a)
            pos += 1
    ans = 0
    A_neg.sort()
    A_pos.sort()
    #print(A_neg)
    #print(neg,pos,num_0)
    if neg*pos>=K:
        l = 1 ; r = A_neg[-1]*A_pos[-1]+1
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            for a in A_neg:
                next = bisect.bisect_left(A_pos,now/a)
                cur += (pos-next)
                #print(next,now//a)
            if cur<K:
                r = now
            else:
                l = now
            #print(now,cur)
        ans = -l
    elif (N-num_0)*num_0+num_0*(num_0-1)//2+neg*pos>=K:
        ans = 0
    else:
        need = K-((pos+neg)*num_0 + num_0*(num_0-1)//2 + neg*pos)
        #print(need)
        l = 0; r = 1
        if neg>=2:
            r = A_neg[-1]*A_neg[-2]+1
        if pos>=2:
            r = max(r,A_pos[-1]*A_pos[-2]+1)
        while(r-l>1):
            now = (l+r)//2
            cur = 0
            if neg>=2:
                for a in A_neg:
                    next = bisect.bisect_right(A_neg, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            if pos>=2:
                for a in A_pos:
                    next = bisect.bisect_right(A_pos, now//a)
                    if a ** 2 <= now:
                        next -= 1
                    cur += next
            cur //= 2
            if cur<need:
                l = now
            else:
                r = now
            #print(now,cur,need)
        ans = r
    print(ans)
    return
"""
10 43
5 4 3 2 -1 0 0 0 0 0
"""

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    for i in range(N-1,-1,-1):
        #print(ans)
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    #print(dp)
    ans = min(dp[-1][0],dp[-1][1])
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""
4396817
"""