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 sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect
def resolve():
    n, k = map(int,input().split())
    A = list(map(int,input().split()))
    pos_A = []
    neg_A = []
    pos = neg = zero = 0
    for a in A:
        if a > 0:
            pos += 1
            pos_A.append(a)
        elif a < 0:
            neg += 1
            neg_A.append(-a)
        else:
            zero += 1
    pos_A.sort()
    neg_A.sort()

    pair_pos = pos * (pos - 1) // 2 + neg * (neg - 1) // 2
    pair_neg = pos * neg
    pair_zero = zero * (pos + neg) + zero * (zero - 1) // 2

    # 答えが 0
    if pair_neg < k <= pair_neg + pair_zero:
        print(0)
        return

    # 答えが negative
    if k <= pair_neg:
        def count(x): # A[i] * A[j] <= x
            res = 0
            for a in pos_A:
                res += bisect(neg_A, x // a)
            for a in neg_A:
                res += bisect(pos_A, x // a)
            return res

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

    # 答えが positive
    def count(x, A):
        res = 0
        for i in range(1, len(A)):
            target = x // A[i] # 0 ... i - 1 で x // a 以下のものの個数
            if A[i - 1] <= target:
                res += i
                continue
            elif A[0] > target:
                continue
            left = 0
            right = i - 1
            while right - left > 1:
                mid = (left + right) // 2
                if A[mid] <= target:
                    left = mid
                else:
                    right = mid
            res += left + 1
        return res

    k -= pair_neg + pair_zero
    left = 0
    right = 10 ** 18 + 1
    while right - left > 1:
        mid = (left + right) // 2
        if count(mid, pos_A) + count(mid, neg_A) < k:
            left = mid
        else:
            right = mid
    print(right)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect
def resolve():
    n, k = map(int,input().split())
    A = list(map(int,input().split()))
    pos_A = []
    neg_A = []
    pos = neg = zero = 0
    for a in A:
        if a > 0:
            pos += 1
            pos_A.append(a)
        elif a < 0:
            neg += 1
            neg_A.append(-a)
        else:
            zero += 1
    pos_A.sort()
    neg_A.sort()

    pair_pos = pos * (pos - 1) // 2 + neg * (neg - 1) // 2
    pair_neg = pos * neg
    pair_zero = zero * (pos + neg) + zero * (zero - 1) // 2

    # 答えが 0
    if pair_neg < k <= pair_neg + pair_zero:
        print(0)
        return

    # 答えが negative
    if k <= pair_neg:
        def count(x): # A[i] * A[j] <= x
            res = 0
            for a in pos_A:
                res += bisect(neg_A, x // a)
            for a in neg_A:
                res += bisect(pos_A, x // a)
            return res

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

    # 答えが positive
    def count(x, A):
        res = 0
        for i in range(1, len(A)):
            target = x // A[i] # 0 ... i - 1 で x // a 以下のものの個数
            if A[i - 1] <= target:
                res += i
                continue
            elif A[0] > target:
                continue
            left = 0
            right = i - 1
            while right - left > 1:
                mid = (left + right) // 2
                if A[mid] <= target:
                    left = mid
                else:
                    right = mid
            res += left + 1
        return res

    k -= pair_neg + pair_zero
    left = 0
    right = 10 ** 18 + 1
    while right - left > 1:
        mid = (left + right) // 2
        if count(mid, pos_A) + count(mid, neg_A) < k:
            left = mid
        else:
            right = mid
    print(right)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect
def resolve():
    n, k = map(int,input().split())
    A = list(map(int,input().split()))
    pos_A = []
    neg_A = []
    pos = neg = zero = 0
    for a in A:
        if a > 0:
            pos += 1
            pos_A.append(a)
        elif a < 0:
            neg += 1
            neg_A.append(-a)
        else:
            zero += 1
    pos_A.sort()
    neg_A.sort()

    pair_pos = pos * (pos - 1) // 2 + neg * (neg - 1) // 2
    pair_neg = pos * neg
    pair_zero = zero * (pos + neg) + zero * (zero - 1) // 2

    # 答えが 0
    if pair_neg < k <= pair_neg + pair_pos:
        print(0)
        return

    # 答えが negative
    if k <= pair_neg:
        def count(x): # A[i] * A[j] <= x
            res = 0
            for a in pos_A:
                res += bisect(neg_A, x // a)
            for a in neg_A:
                res += bisect(pos_A, x // a)
            return res

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

    # 答えが positive
    def count(x, A):
        res = 0
        for i in range(1, len(A)):
            target = x // A[i] # 0 ... i - 1 で x // a 以下のものの個数
            if A[i - 1] <= target:
                res += i
                continue
            elif A[0] > target:
                continue
            left = 0
            right = i - 1
            while right - left > 1:
                mid = (left + right) // 2
                if A[mid] <= target:
                    left = mid
                else:
                    right = mid
            res += left + 1
        return res

    k -= pair_neg + pair_zero
    left = 0
    right = 10 ** 18 + 1
    while right - left > 1:
        mid = (left + right) // 2
        if count(mid, pos_A) + count(mid, neg_A) < k:
            left = mid
        else:
            right = mid
    print(right)
resolve()

Submission status: Wrong Answer

Solution code:
def examA():
    C = [SI()for _ in range(3)]
    ans = C[0][0]+C[1][1]+C[2][2]
    print(ans)
    return

def examB():
    N, M = LI()
    P = [0]*N
    S = [LSI()for _ in range(M)]
    pena = 0
    ac = set()
    for p,s in S:
        p = int(p)-1
        if s=="WA":
            P[p] += 1
        else:
            if p in ac:
                continue
            ac.add(p)
            pena += P[p]

    print(len(ac),pena)
    return

def examC():
    W, H, N = LI()
    lx, rx, ly, ry = 0, W, 0, H
    A = [LI()for _ in range(N)]
    for x,y,a in A:
        if a==1:
            lx = max(lx,x)
        elif a==2:
            rx = min(rx,x)
        elif a==3:
            ly = max(ly,y)
        elif a==4:
            ry = min(ry,y)
    ans = max(0,rx-lx)*max(0,ry-ly)
    print(ans)
    return

def examD():
    N, H = LI()
    B = [0]*N
    maxa = 0
    ans = 0
    for i in range(N):
        a, B[i] = LI()
        if a>maxa:
            maxa = a
    B.sort(reverse=True)
    for b in B:
        if b<maxa:
            break
        H -= b
        ans += 1
        if H<=0:
            print(ans)
            return
    ans += -(-H//maxa)
    print(ans)
    return

def examE():
    A, B = LI()
    ans = [["#"]*100 for _ in range(50)] + [["."]*100 for _ in range(50)]
    i = 0; j = 0
    for _ in range(A-1):
        ans[i][j] = "."
        j += 2
        if j>=100:
            j = 0; i += 2
    i = 0; j = 0
    for _ in range(B-1):
        ans[99-i][j] = "#"
        j += 2
        if j>=100:
            j = 0; i += 2
    print(100,100)
    for v in ans:
        print("".join(map(str,v)))
    return

def examF():
    def search_1(need):
        l = 0; r = inf+1
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            cur += shakutori(neg,pos,now)
            #print(cur,now)
            if cur>=need:
                l = now
            else:
                r = now
            #print(cur)
        return -l
    def shakutori(A,B,k):
        n = len(A)
        m = len(B)
        rep = 0
        r = 0
        for l in range(n)[::-1]:
            while(r<m-1 and A[l]*B[r]<k):
                r += 1
            if (A[l]*B[r]>=k):
                rep += m-r
        return rep
    def search_2(need):
        need *= 2
        #print(need)
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            cur += shakutori_2(neg,now)
            cur += shakutori_2(pos,now)
            if cur>=need:
                r = now
            else:
                l = now
            #print(cur,now)
        return r
    def shakutori_2(C,k):
        n = len(C)
        rep = 0
        r = n-1
        for l in range(n):
            while(r>0 and C[l]*C[r]>k):
                r -= 1
            if (C[l]*C[r]<=k):
                rep += r+1
            if r>=l:
                rep -= 1
        return rep
    N, K = LI()
    A = LI()
    neg = []; pos = []; arr_0 = 0
    for a in A:
        if a<0:
            neg.append(-a)
        elif a==0:
            arr_0 += 1
        else:
            pos.append(a)
    neg.sort(); pos.sort()
    #print(pos)
    if len(neg)*len(pos)>=K:
        ans = search_1(K)
    elif len(neg)*len(pos)+arr_0*(len(neg)+len(pos))+arr_0*(arr_0-1)//2>=K:
        ans = 0
    else:
        ans = search_2(K-len(neg)*len(pos)-arr_0*(len(neg)+len(pos))-arr_0*(arr_0-1)//2)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,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)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
87940638538504699
448283280358331064
"""

Submission status: Wrong Answer

Solution code:
def examA():
    C = [SI()for _ in range(3)]
    ans = C[0][0]+C[1][1]+C[2][2]
    print(ans)
    return

def examB():
    N, M = LI()
    P = [0]*N
    S = [LSI()for _ in range(M)]
    pena = 0
    ac = set()
    for p,s in S:
        p = int(p)-1
        if s=="WA":
            P[p] += 1
        else:
            if p in ac:
                continue
            ac.add(p)
            pena += P[p]

    print(len(ac),pena)
    return

def examC():
    W, H, N = LI()
    lx, rx, ly, ry = 0, W, 0, H
    A = [LI()for _ in range(N)]
    for x,y,a in A:
        if a==1:
            lx = max(lx,x)
        elif a==2:
            rx = min(rx,x)
        elif a==3:
            ly = max(ly,y)
        elif a==4:
            ry = min(ry,y)
    ans = max(0,rx-lx)*max(0,ry-ly)
    print(ans)
    return

def examD():
    N, H = LI()
    B = [0]*N
    maxa = 0
    ans = 0
    for i in range(N):
        a, B[i] = LI()
        if a>maxa:
            maxa = a
    B.sort(reverse=True)
    for b in B:
        if b<maxa:
            break
        H -= b
        ans += 1
        if H<=0:
            print(ans)
            return
    ans += -(-H//maxa)
    print(ans)
    return

def examE():
    A, B = LI()
    ans = [["#"]*100 for _ in range(50)] + [["."]*100 for _ in range(50)]
    i = 0; j = 0
    for _ in range(A-1):
        ans[i][j] = "."
        j += 2
        if j>=100:
            j = 0; i += 2
    i = 0; j = 0
    for _ in range(B-1):
        ans[99-i][j] = "#"
        j += 2
        if j>=100:
            j = 0; i += 2
    print(100,100)
    for v in ans:
        print("".join(map(str,v)))
    return

def examF():
    def search_1(need):
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            cur += shakutori(neg,pos,now)
            #print(cur,now)
            if cur>=need:
                l = now
            else:
                r = now
            #print(cur)
        return l
    def shakutori(A,B,k):
        n = len(A)
        m = len(B)
        rep = 0
        r = 0
        for l in range(n)[::-1]:
            while(r<m-1 and A[l]*B[r]<k):
                r += 1
            if (A[l]*B[r]>=k):
                rep += m-r
        return rep
    def search_2(need):
        need *= 2
        #print(need)
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            cur += shakutori_2(neg,now)
            cur += shakutori_2(pos,now)
            if cur>=need:
                r = now
            else:
                l = now
            #print(cur,now)
        return r
    def shakutori_2(C,k):
        n = len(C)
        rep = 0
        r = n-1
        for l in range(n):
            while(r>0 and C[l]*C[r]>k):
                r -= 1
            if (C[l]*C[r]<=k):
                rep += r+1
            if r>=l:
                rep -= 1
        return rep
    N, K = LI()
    A = LI()
    neg = []; pos = []; arr_0 = 0
    for a in A:
        if a<0:
            neg.append(-a)
        elif a==0:
            arr_0 += 1
        else:
            pos.append(a)
    neg.sort(); pos.sort()
    #print(pos)
    if len(neg)*len(pos)>=K:
        ans = -search_1(K)
    elif len(neg)*len(pos)+arr_0*(len(neg)+len(pos))+arr_0*(arr_0-1)//2>=K:
        ans = 0
    else:
        ans = search_2(K-len(neg)*len(pos)-arr_0*(len(neg)+len(pos))-arr_0*(arr_0-1)//2)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,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)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
87940638538504699
448283280358331064
"""

Submission status: Wrong Answer

Solution code:
def examA():
    C = [SI()for _ in range(3)]
    ans = C[0][0]+C[1][1]+C[2][2]
    print(ans)
    return

def examB():
    N, M = LI()
    P = [0]*N
    S = [LSI()for _ in range(M)]
    pena = 0
    ac = set()
    for p,s in S:
        p = int(p)-1
        if s=="WA":
            P[p] += 1
        else:
            if p in ac:
                continue
            ac.add(p)
            pena += P[p]

    print(len(ac),pena)
    return

def examC():
    W, H, N = LI()
    lx, rx, ly, ry = 0, W, 0, H
    A = [LI()for _ in range(N)]
    for x,y,a in A:
        if a==1:
            lx = max(lx,x)
        elif a==2:
            rx = min(rx,x)
        elif a==3:
            ly = max(ly,y)
        elif a==4:
            ry = min(ry,y)
    ans = max(0,rx-lx)*max(0,ry-ly)
    print(ans)
    return

def examD():
    N, H = LI()
    B = [0]*N
    maxa = 0
    ans = 0
    for i in range(N):
        a, B[i] = LI()
        if a>maxa:
            maxa = a
    B.sort(reverse=True)
    for b in B:
        if b<maxa:
            break
        H -= b
        ans += 1
        if H<=0:
            print(ans)
            return
    ans += -(-H//maxa)
    print(ans)
    return

def examE():
    A, B = LI()
    ans = [["#"]*100 for _ in range(50)] + [["."]*100 for _ in range(50)]
    i = 0; j = 0
    for _ in range(A-1):
        ans[i][j] = "."
        j += 2
        if j>=100:
            j = 0; i += 2
    i = 0; j = 0
    for _ in range(B-1):
        ans[99-i][j] = "#"
        j += 2
        if j>=100:
            j = 0; i += 2
    print(100,100)
    for v in ans:
        print("".join(map(str,v)))
    return

def examF():
    def search_1(need):
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            for b in neg:
                cur += len(pos)-bisect.bisect_right(pos, now//b)
            if cur>=need:
                l = now
            else:
                r = now
            #print(cur)
        return r
    def search_2(need):
        need *= 2
        #print(need)
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            cur += shakutori(neg,now)
            cur += shakutori(pos,now)
            if cur>=need:
                r = now
            else:
                l = now
            #print(cur,now)
        return r
    def shakutori(C,k):
        n = len(C)
        rep = 0
        r = n-1
        for l in range(n):
            while(r>0 and C[l]*C[r]>k):
                r -= 1
            if (C[l]*C[r]<=k):
                rep += r+1
            if r>=l:
                rep -= 1
        return rep
    N, K = LI()
    A = LI()
    neg = []; pos = []; arr_0 = 0
    for a in A:
        if a<0:
            neg.append(-a)
        elif a==0:
            arr_0 += 1
        else:
            pos.append(a)
    neg.sort(); pos.sort()
    #print(pos)
    if len(neg)*len(pos)>=K:
        ans = -search_1(K)
    elif len(neg)*len(pos)+arr_0*(len(neg)+len(pos))+arr_0*(arr_0-1)//2>=K:
        ans = 0
    else:
        ans = search_2(K-len(neg)*len(pos)-arr_0*(len(neg)+len(pos))-arr_0*(arr_0-1)//2)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,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)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
87940638538504699
448283280358331064
"""

Submission status: Wrong Answer

Solution code:
def examA():
    C = [SI()for _ in range(3)]
    ans = C[0][0]+C[1][1]+C[2][2]
    print(ans)
    return

def examB():
    N, M = LI()
    P = [0]*N
    S = [LSI()for _ in range(M)]
    pena = 0
    ac = set()
    for p,s in S:
        p = int(p)-1
        if s=="WA":
            P[p] += 1
        else:
            if p in ac:
                continue
            ac.add(p)
            pena += P[p]

    print(len(ac),pena)
    return

def examC():
    W, H, N = LI()
    lx, rx, ly, ry = 0, W, 0, H
    A = [LI()for _ in range(N)]
    for x,y,a in A:
        if a==1:
            lx = max(lx,x)
        elif a==2:
            rx = min(rx,x)
        elif a==3:
            ly = max(ly,y)
        elif a==4:
            ry = min(ry,y)
    ans = max(0,rx-lx)*max(0,ry-ly)
    print(ans)
    return

def examD():
    N, H = LI()
    B = [0]*N
    maxa = 0
    ans = 0
    for i in range(N):
        a, B[i] = LI()
        if a>maxa:
            maxa = a
    B.sort(reverse=True)
    for b in B:
        if b<maxa:
            break
        H -= b
        ans += 1
        if H<=0:
            print(ans)
            return
    ans += -(-H//maxa)
    print(ans)
    return

def examE():
    A, B = LI()
    ans = [["#"]*100 for _ in range(50)] + [["."]*100 for _ in range(50)]
    i = 0; j = 0
    for _ in range(A-1):
        ans[i][j] = "."
        j += 2
        if j>=100:
            j = 0; i += 2
    i = 0; j = 0
    for _ in range(B-1):
        ans[99-i][j] = "#"
        j += 2
        if j>=100:
            j = 0; i += 2
    print(100,100)
    for v in ans:
        print("".join(map(str,v)))
    return

def examF():
    def search_1(need):
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            for b in neg:
                cur += len(pos)-bisect.bisect_right(pos, now//b)
            if cur>=need:
                l = now
            else:
                r = now
            #print(cur)
        return r
    def search_2(need):
        need *= 2
        #print(need)
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            cur += shakutori(neg,now)
            cur += shakutori(pos,now)
            if cur>=need:
                r = now
            else:
                l = now
            #print(cur,now)
        return r
    def shakutori(C,k):
        n = len(C)
        rep = 0
        r = n-1
        for l in range(n):
            while(r>0 and C[l]*C[r]>k):
                r -= 1
            if (C[l]*C[r]<=k):
                rep += r+1
            if r>l:
                rep -= 1
        return rep
    N, K = LI()
    A = LI()
    neg = []; pos = []; arr_0 = 0
    for a in A:
        if a<0:
            neg.append(-a)
        elif a==0:
            arr_0 += 1
        else:
            pos.append(a)
    neg.sort(); pos.sort()
    #print(pos)
    if len(neg)*len(pos)>=K:
        ans = -search_1(K)
    elif len(neg)*len(pos)+arr_0*(len(neg)+len(pos))+arr_0*(arr_0-1)//2>=K:
        ans = 0
    else:
        ans = search_2(K-len(neg)*len(pos)-arr_0*(len(neg)+len(pos))-arr_0*(arr_0-1)//2)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,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)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
87940638538504699
448283280358331064
"""

Submission status: Wrong Answer

Solution code:
def examA():
    C = [SI()for _ in range(3)]
    ans = C[0][0]+C[1][1]+C[2][2]
    print(ans)
    return

def examB():
    N, M = LI()
    P = [0]*N
    S = [LSI()for _ in range(M)]
    pena = 0
    ac = set()
    for p,s in S:
        p = int(p)-1
        if s=="WA":
            P[p] += 1
        else:
            if p in ac:
                continue
            ac.add(p)
            pena += P[p]

    print(len(ac),pena)
    return

def examC():
    W, H, N = LI()
    lx, rx, ly, ry = 0, W, 0, H
    A = [LI()for _ in range(N)]
    for x,y,a in A:
        if a==1:
            lx = max(lx,x)
        elif a==2:
            rx = min(rx,x)
        elif a==3:
            ly = max(ly,y)
        elif a==4:
            ry = min(ry,y)
    ans = max(0,rx-lx)*max(0,ry-ly)
    print(ans)
    return

def examD():
    N, H = LI()
    B = [0]*N
    maxa = 0
    ans = 0
    for i in range(N):
        a, B[i] = LI()
        if a>maxa:
            maxa = a
    B.sort(reverse=True)
    for b in B:
        if b<maxa:
            break
        H -= b
        ans += 1
        if H<=0:
            print(ans)
            return
    ans += -(-H//maxa)
    print(ans)
    return

def examE():
    A, B = LI()
    ans = [["#"]*100 for _ in range(50)] + [["."]*100 for _ in range(50)]
    i = 0; j = 0
    for _ in range(A-1):
        ans[i][j] = "."
        j += 2
        if j>=100:
            j = 0; i += 2
    i = 0; j = 0
    for _ in range(B-1):
        ans[99-i][j] = "#"
        j += 2
        if j>=100:
            j = 0; i += 2
    print(100,100)
    for v in ans:
        print("".join(map(str,v)))
    return

def examF():
    def search_1(need):
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            for b in neg:
                cur += len(pos)-bisect.bisect_right(pos, _ep+now/b)
            if cur>=need:
                l = now
            else:
                r = now
            #print(cur)
        return r
    def search_2(need):
        need *= 2
        #print(need)
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            for b in neg:
                cur += bisect.bisect_right(neg, now/b)
                if now>=b**2:
                    cur -= 1
            #print("途中",cur,now)
            for b in pos:
                cur += bisect.bisect_right(pos, now/b)
                if now>=b**2:
                    cur -= 1
            if cur>=need:
                r = now
            else:
                l = now
            #print(cur,now)
        return r
    N, K = LI()
    A = LI()
    neg = []; pos = []; arr_0 = 0
    for a in A:
        if a<0:
            neg.append(-a)
        elif a==0:
            arr_0 += 1
        else:
            pos.append(a)
    neg.sort(); pos.sort()
    #print(pos)
    if len(neg)*len(pos)>=K:
        ans = -search_1(K)
    elif len(neg)*len(pos)+arr_0*(len(neg)+len(pos))+arr_0*(arr_0-1)//2>=K:
        ans = 0
    else:
        ans = search_2(K-len(neg)*len(pos)-arr_0*(len(neg)+len(pos))-arr_0*(arr_0-1)//2)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,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)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
87940638538504699
448283280358331064
"""

Submission status: Wrong Answer

Solution code:
#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################
import itertools
ans = []
N,K =  map(int,input().split())	
l = list(map(int,input().split()))	
for v in itertools.combinations(l, 2):
    #print(list(v)[1])
    #print(list(v)[0])
    ans.append(list(v)[1]*list(v)[0])
#print(ans)
b = sorted(ans)
print(b[2])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# neg, zero, posに分けて、二分探索
N, K = lr()
A = np.array(lr()); A.sort()
neg = A[A<0]
zero = A[A==0]
pos = A[A>0]

def check(x):
    '''x以下の積がK個以上あるならTrueを返す'''
    cnt = 0  # 最後に２でわる
    if x >= 0:
        cnt += len(zero) * N
    cnt += (np.searchsorted(A, x//pos, side='right')).sum()
    cnt += (N - np.searchsorted(A, (-x-1)//(-neg), side='right')).sum()
    cnt -= np.count_nonzero(A*A <= x)
    assert cnt % 2 == 0
    return (cnt//2) >= K

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

print(ok)
# 30

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline

n,k = map(int, input().split())
a= list(map(int, input().split()))
a.sort()
r=10**18+1
l=-10**18-1
while r-l>1:
    m = (r + l) // 2
    count=0
    for i in range(n):
        if a[i]>0:
            x=m//a[i]
            y=bisect.bisect_right(a,x)
            if y<=i:
                count+=y

        elif a[i]<0:
            x=-(m//-a[i])
            y=bisect.bisect_left(a,x)
            if y>i:
                count+=n-y


    if count//2>=k:
        r=m
    else:
        l=m
print(r)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline

n,k = map(int, input().split())
a= list(map(int, input().split()))
a.sort()
r=pow(10,18)+1
l=-pow(10,18)-1
# r:常にNG、l：常にOK max(l):l未満がk個のうち最大の値
while r-l>1:
    m = (r + l) // 2
    count=0
    for i in a:
        if i>0:
            x=m//i
            y=bisect.bisect_right(a,x)
            if y<=i:
                count+=y
            else:
                count+=y-1
        elif i<0:
            x=-(m//-i)
            y=bisect.bisect_left(a,x)
            if y>i:
                count+=n-y
            else:
                count+=n-y-1
        else:
            if m>=0:
                count+=n-1

    if count//2>=k:
        r=m
    else:
        l=m
print(r)