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 = [int(a) for a in input().split()]

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

P.sort()
M.sort()

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

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

Submission status: Wrong Answer

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

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

P.sort()
M.sort()

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

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

Submission status: Wrong Answer

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

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

P.sort()
M.sort()

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

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

Submission status: Wrong Answer

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

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

P.sort()
M.sort()

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

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

Submission status: Wrong Answer

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

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

P.sort()
M.sort()

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

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

print(l)

Submission status: Wrong Answer

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

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

P.sort()
M.sort()

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

A.sort()
l = min(A[0]*A[1], A[0]*A[-1])
r = max(A[0]*A[1], A[-1]*A[-2])
while r-l > 1:
    num = (l+r)//2
    k = f(num)
    if k < K:
        l = num
    else:
        r = num

if f(l) < K <= f(r):
    print(l)
else:
    print(r)

Submission status: Wrong Answer

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

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

P.sort()
M.sort()
M2.sort()

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

A.sort()
l = min(A[0]*A[1], A[0]*A[-1])
r = max(A[0]*A[1], A[-1]*A[-2])
if f(0) >= K:
    while f(r)-f(l) > 0:
        num = (l+r)//2
        k = f(num)
        if k <= K:
            l = num
        else:
            r = num
else:
    while r-l > 1:
        num = (l+r)//2
        k = f(num)
        if k < K:
            l = num
        else:
            r = num

if f(l) == K:
    print(l)
else:
    print(r)

Submission status: Wrong Answer

Solution code:
import bisect

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

a.sort()

ub = 10**18
lb = -10**18-1

while ub - lb > 1:
    x = (ub + lb) // 2
    cnt = 0
    for i in range(n):
        if a[i] > 0:
            cx = x // a[i]
            if cx >= a[i]:
                cnt -= 1
            cnt += bisect.bisect_right(a, cx)
        elif a[i] < 0:
            cx = x // a[i]
            if cx < a[i]:
                cnt -= 1
            cnt += n - bisect.bisect_right(a, cx)
        else: # a[i] == 0
            if x >= 0:
                cnt += n - 1
    cnt //= 2     
    if cnt >= k:
        ub = x
    else:
        lb = x
print(ub)

Submission status: Wrong Answer

Solution code:
import bisect

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

a.sort()

ub = 10**18
lb = -10**18-1

while ub - lb > 1:
    x = (ub + lb) // 2
    cnt = 0
    for i in range(n):
        if a[i] > 0:
            cx = x // a[i]
            if cx >= a[i]:
                cnt -= 1
            cnt += bisect.bisect_right(a, cx)
        elif a[i] < 0:
            cx = x // a[i]
            if cx < a[i]:
                cnt -= 1
            cnt += n - bisect.bisect_left(a, cx)
        else: # a[i] == 0
            if x >= 0:
                cnt += n - 1
    cnt //= 2     
    if cnt >= k:
        ub = x
    else:
        lb = x
print(ub)

Submission status: Wrong Answer

Solution code:
import bisect

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

a.sort()

ub = 10**18
lb = -10**18-1

while ub - lb > 1:
    x = (ub + lb) // 2
    cnt = 0
    for i in range(n):
        if a[i] > 0:
            cx = x / a[i]
            if cx >= a[i]:
                cnt -= 1
            cnt += bisect.bisect_right(a, cx)
        elif a[i] < 0:
            cx = x / a[i]
            if cx < a[i]:
                cnt -= 1
            cnt += n - bisect.bisect_left(a, cx)
        else: # a[i] == 0
            if x >= 0:
                cnt += n - 1
    cnt //= 2     
    if cnt >= k:
        ub = x
    else:
        lb = x
print(ub)

Submission status: Wrong Answer

Solution code:
from bisect import *

def binary_search_int(ok, ng, test):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ng

def get_count1(k, A):
    """ K番目の要素が正の場合 """
    l, r = 0, len(A)-1
    res = 0
    while l < r:
        if A[l]*A[r] > k:
            r -= 1
            continue
        res += r-l
        l += 1
    return res

def get_count2(k, B, C):
    """ K番目の要素が負の場合 """
    l, r = 0, len(C)-1
    res = 0
    while True:
        if l > len(B)-1 or r < 0:
            break
        if B[l]*C[r] < -k:
            l += 1
            continue
        res += len(B)-l
        r -= 1
    return res

def test1(k):
    return get_count1(k, B) + get_count1(k, C) + count_negative < K

def test2(k):
    return get_count2(k, B, C) < K


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

at_zero = bisect_left(A,0)
B = A[:at_zero]
B = list(map(lambda x: -x, B))
B = list(reversed(B))   # 負の要素
C = A[at_zero:]         # 正の要素
count_positive = (len(B)*(len(B)-1)//2 + len(C)*(len(C)-1)//2)
count_negative = N*(N-1)//2 - count_positive
if K > count_negative:
    print(binary_search_int(-1, 10**18+1, test1))
else:
    print(binary_search_int(-10**2, 1, test2))

Submission status: Wrong Answer

Solution code:
from bisect import *

def binary_search_int(ok, ng, test):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ng

def get_count1(k, A):
    """ K番目の要素が正の場合 """
    l, r = 0, len(A)-1
    res = 0
    while l < r:
        if A[l]*A[r] > k:
            r -= 1
            continue
        res += r-l
        l += 1
    return res

def get_count2(k, B, C):
    """ K番目の要素が負の場合 """
    l, r = 0, len(C)-1
    res = 0
    while True:
        if l > len(B)-1 or r < 0:
            break
        if B[l]*C[r] < -k:
            l += 1
            continue
        res += len(C)-l
        r -= 1
    return res

def test1(k):
    return get_count1(k, B) + get_count1(k, C) + count_negative < K

def test2(k):
    return get_count2(k, B, C) < K


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

at_zero = bisect_left(A,0)
B = A[:at_zero]
B = list(map(lambda x: -x, B))
B = list(reversed(B))   # 負の要素
C = A[at_zero:]         # 正の要素
count_positive = (len(B)*(len(B)-1)//2 + len(C)*(len(C)-1)//2)
count_negative = N*(N-1)//2 - count_positive
if K >= count_negative:
    print(binary_search_int(-1, 10**18, test1))
else:
    print(binary_search_int(-10**18, 1, test2))

Submission status: Wrong Answer

Solution code:
from bisect import *

def binary_search_int(ok, ng, test):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ng

def get_count1(k, A):
    """ K番目の要素が正の場合 """
    l, r = 0, len(A)-1
    res = 0
    while l < r:
        if A[l]*A[r] > k:
            r -= 1
            continue
        res += r-l
        l += 1
    return res

def get_count2(k, B, C):
    """ K番目の要素が負の場合 """
    l, r = 0, len(C)-1
    res = 0
    while True:
        if l > len(B)-1 or r < 0:
            break
        if B[l]*C[r] < -k:
            l += 1
            continue
        res += len(C)-l
        r -= 1
    return res

def test1(k):
    print(k, get_count1(k, C))
    return get_count1(k, B) + get_count1(k, C) + count_negative < K

def test2(k):
    return get_count2(k, B, C) < K


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

at_zero = bisect_left(A,0)
B = A[:at_zero]
B = list(map(lambda x: -x, B))
B = list(reversed(B))   # 負の要素
C = A[at_zero:]         # 正の要素
count_positive = (len(B)*(len(B)-1)//2 + len(C)*(len(C)-1)//2)
count_negative = N*(N-1)//2 - count_positive
if K >= count_negative:
    print(binary_search_int(-1, 10**18, test1))
else:
    print(binary_search_int(-10**18, 1, test2))

Submission status: Wrong Answer

Solution code:
from bisect import *

def binary_search_int(ok, ng, test):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ng

def get_count1(k, A):
    """ K番目の要素が正の場合 """
    l, r = 0, len(A)-1
    res = 0
    while l < r:
        if A[l]*A[r] > k:
            r -= 1
            continue
        res += r-l
        l += 1
    return res

def get_count2(k, B, C):
    """ K番目の要素が負の場合 """
    l, r = 0, len(C)-1
    res = 0
    while True:
        if l > len(B)-1 or r < 0:
            break
        if B[l]*C[r] < -k:
            l += 1
            continue
        res += len(C)-l
        r -= 1
    return res

def test1(k):
    return get_count1(k, B) + get_count1(k, C) + count_negative < K

def test2(k):
    return get_count2(k, B, C) < K


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

at_zero = bisect_left(A,0)
B = A[:at_zero]
B = list(map(lambda x: -x, B))
B = list(reversed(B))   # 負の要素
C = A[at_zero:]         # 正の要素
count_positive = (len(B)*(len(B)-1)//2 + len(C)*(len(C)-1)//2)
count_negative = N*(N-1)//2 - count_positive
if K > count_negative:
    print(binary_search_int(0, 10**18, test1))
else:
    print(binary_search_int(-10**18, 0, test2))

Submission status: Wrong Answer

Solution code:
import bisect
import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()


@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,0- (-target)//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = As[0] * As[-1] - 1
    r = 100
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = 100
    r = max(As[-1] * As[-2], As[0] * As[1])
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
        if count >= K:
            r = mid
            break
    else:
        l = mid

print(r)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = As[0] * As[-1]
r = max(As[0] * As[1], As[-1] * As[-2])
while r - l > 1:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
        if count >= K:
            r = mid
            break
    else:
        l = mid

print(r)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            count -= bisect_left(As, -((-t)//A), lo = i+1)
        else:
            if t >= 0:
                count += N - i - 1
    return (count < K)
        


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

print(r)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count > K:
            return False
    return True

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = 0
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

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

print(r)

Submission status: Wrong Answer

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

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count > K:
            return False
    return (count < K)

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2:
    l = 0
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

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

print(r)

Submission status: Wrong Answer

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

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count > K:
            return False
    return (count < K)

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = - (10 ** 18 + 10)
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count) // 2:
    l = 0
    r = 10 ** 18 + 10
else:
    print(0)
    exit()

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

print(r)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
m,p=[],[]
for a in A:
    if a<0:
        m.append(a)
    elif a>0:
        p.append(a)
M,P=len(m),len(p)
Z=N-M-P
m.sort(reverse=1)
p.sort()
if M*P<K<=N*(N-1)//2-M*(M-1)//2-P*(P-1)//2:
    print(0)
elif K<=M*P:
    l,r=-10**18-1,0
    while l+1<r:
        t=(l+r)//2
        x=0
        mi=0
        for pi in range(P-1,-1,-1):
            while mi<M and m[mi]*p[pi]<=t:
                mi+=1
            x+=mi
        if K<=x:
            r=t
        else:
            l=t
    print(r)
else:
    l,r=0,10**18+1
    K-=M*P+Z*(Z-1)//2+Z*(M+P)
    while l+1<r:
        t=(l+r)//2
        x=0
        mi,pi=0,0
        for mj in range(M-1,-1,-1):
            while mi<M and m[mi]*m[mj]<=t:
                mi+=1
            x+=mi-(1 if mj<mi else 0)
        for pj in range(P-1,-1,-1):
            while pi<P and p[pi]*p[pj]<=t:
                pi+=1
            x+=pi-(1 if pj<pi else 0)
        if K<=x//2:
            r=t
        else:
            l=t
    print(r)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

N, K, *A = map(int, open(0).read().split())

l_pos = sorted(v for v in A if v > 0)
l_neg = sorted(v for v in A if v < 0)

cnt_pos = len(l_pos)
cnt_neg = len(l_neg)

pair_pos = cnt_pos * (cnt_pos - 1) // 2 + cnt_neg * (cnt_neg - 1) // 2
pair_neg = cnt_pos * cnt_neg
pair_zro = N * (N - 1) // 2 - pair_pos - pair_neg


def solve_neg(n):
    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        cnt = 0
        mid = (ub + lb) // 2
        for v in l_neg:
            cnt += bisect_left(l_pos, mid // v)

        if cnt > n:
            lb = mid
        else:
            ub = mid

    return lb


def solve_pos(n):
    lb = 0
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        cnt = 0
        mid = (ub + lb) // 2
        for v in l_pos:
            cnt += bisect_left(l_pos, mid // v)

        for v in l_neg:
            cnt += bisect_left(l_neg, mid // v)

        if cnt > n:
            ub = mid
        else:
            lb = mid

    return lb


if K <= pair_neg:
    ans = solve_neg(K)
elif K <= pair_neg + pair_zro:
    ans = 0
else:
    ans = solve_pos(K - pair_neg - pair_zro)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import bisect

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

INF = 10**18


def binary_search(min_n, max_n, judge):

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if judge(tn):
            max_n = tn
        else:
            min_n = tn

    return max_n


def main():
    N, K = in_nn()
    A = in_nl()

    Ap = []
    Am = []
    Nz = 0

    for i in range(N):
        if A[i] > 0:
            Ap.append(A[i])
        elif A[i] == 0:
            Nz += 1
        else:
            Am.append(A[i])

    Np = len(Ap)
    Nm = len(Am)

    m_count = Np * Nm
    z_count = Nz * (Np + Nm) + Nz * (Nz - 1) // 2
    # p_count = Np * (Np - 1) // 2 + Nm * (Nm - 1) // 2

    tmp = []
    for i in range(N):
        for j in range(i + 1, N):
            tmp.append(A[i] * A[j])

    print(sorted(tmp)[K - 1])

    if K <= m_count:

        Ap.sort()
        Am.sort()

        def judge(tn):

            count = 0
            for i in range(Nm):
                search = -(-tn // Am[i])
                j = bisect.bisect_left(Ap, search)
                count += Np - j

            return count >= K

        ans = binary_search(-INF, -1, judge)

    elif K <= m_count + z_count:
        ans = 0
    else:

        Ap.sort()
        Am = sorted([-a for a in Am])

        def judge(tn):

            count = 0
            for i in range(Np):
                search = tn // Ap[i]
                j = bisect.bisect_right(Ap, search)
                count += max(0, j - i - 1)

            for i in range(Nm):
                search = tn // Am[i]
                j = bisect.bisect_right(Am, search)
                count += max(0, j - i - 1)

            return count >= (K - m_count - z_count)

        ans = binary_search(1, INF, judge)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import math

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

INF = 10**19


def binary_search(min_n, max_n, judge):

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if judge(tn):
            max_n = tn
        else:
            min_n = tn

    return max_n


def main():
    N, K = in_nn()
    A = in_nl()

    Ap = []
    Am = []
    Nz = 0

    for i in range(N):
        if A[i] > 0:
            Ap.append(A[i])
        elif A[i] == 0:
            Nz += 1
        else:
            Am.append(A[i])

    Np = len(Ap)
    Nm = len(Am)

    m_count = Np * Nm
    z_count = Nz * (Np + Nm) + Nz * (Nz - 1) // 2
    # p_count = Np * (Np - 1) // 2 + Nm * (Nm - 1) // 2

    if K <= m_count:

        Ap.sort()
        Am.sort()

        def judge(tn):

            count = 0
            for i in range(Nm):
                search = math.ceil(tn / Am[i])
                j = bisect.bisect_left(Ap, search)
                count += Np - j

            #print(tn, count, K)
            return count >= K

        ans = binary_search(-INF, -1, judge)

    elif K <= m_count + z_count:
        ans = 0
    else:

        Ap.sort()
        Am = sorted([-a for a in Am])

        def judge(tn):

            count = 0
            for i in range(Np):
                search = tn // Ap[i]
                j = bisect.bisect_right(Ap, search)
                count += max(0, j - i - 1)

            for i in range(Nm):
                search = tn // Am[i]
                j = bisect.bisect_right(Am, search)
                count += max(0, j - i - 1)

            #print(tn, count, K - m_count - z_count)
            return count >= (K - m_count - z_count)

        ans = binary_search(1, INF, judge)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def comb(li):
    return len(li) * (len(li) - 1) // 2


def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()

    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg) + count_large(m, pos)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)


# k-th is 0
else:
    print(0)