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 numpy as np
stdin = open(0)

N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().split(), np.int64)


A = np.sort(A)
zero = A[A == 0]
pos = list(A[A > 0])
neg = list(A[A < 0])

neg_count = len(pos) * len(neg)
pos_count = len(pos) * (len(pos) - 1) // 2 + len(neg) * (len(neg) - 1) // 2
zero_count = N * (N - 1) // 2 - neg_count - pos_count

if K > neg_count and K <= neg_count + zero_count:
    print(0)
    exit(0)

def f(x):
    """x以下の積の組み合わせを数える(k番目が負の場合)"""
    count = 0
    pos_idx = None
    neg_idx = len(neg) - 1
    for idx, p in enumerate(reversed(pos)):
        if p * neg[neg_idx] <= x:
            pos_idx = len(pos) - idx - 1
        else:
            break
    # pos_idxに最大の負の値x正の値 <= xを満たす最小の正値のindexが入っている
    if pos_idx is not None:
        count += len(pos) - pos_idx
    else:
        pos_idx = 0
    while neg_idx > 0:
        neg_idx -= 1
        ans = None
        for i in reversed(range(pos_idx + 1)):
            if pos[i] * neg[neg_idx] <= x:
                ans = i
                break
        if ans is None:
            break
        # iにはneg_idxの位置の負数と掛けたときに<=xを満たす最小の正数のindexが入る
        # print(i)
        count += len(pos) - ans
        pos_idx = i
    return count

def g(x):
    """x以下の積の組み合わせを数える(k番目が正の場合)"""
    count = neg_count + zero_count
    # print('c1', count)
    l_idx = 0
    r_idx = 0
    # 正数 x 正数の場合
    for idx, p in enumerate(reversed(pos)):
        if p * pos[l_idx] <= x:
            r_idx = len(pos) - idx - 1
            break
    if r_idx > 0:
        count += (r_idx + 1) - 1  # index = 0の分は引く
        while r_idx - l_idx > 0:
            l_idx += 1
            ans = l_idx
            # print(l_idx, r_idx)
            for i in reversed(range(l_idx + 1, r_idx + 1)):
                # print(i, pos[i], l_idx, pos[l_idx])
                if pos[i] * pos[l_idx] <= x:
                    ans = i
                    break
            # print('ans', ans, l_idx)
            if ans > l_idx:
                count += ans - l_idx
                r_idx = ans
            else:
                break
    # print('c2', count)
    # 負数 x 負数の場合
    r_idx = len(neg) - 1
    l_idx = len(neg) - 1
    for idx, n in enumerate(neg):
        if n * neg[r_idx] <= x:
            l_idx = idx
            break
    # print(l_idx, r_idx)
    if l_idx < r_idx:
        count += len(neg) - l_idx - 1 # r_idxの分は引く
        # print('c3', count)
        while r_idx - l_idx > 0:
                r_idx -= 1
                ans = r_idx
                # print(l_idx, r_idx)
                for i in range(l_idx, r_idx):
                    # print(i, pos[i], l_idx, pos[l_idx])
                    if neg[i] * neg[r_idx] <= x:
                        ans = i
                        break
                # print(l_idx, r_idx, ans)
                # print('ans', ans, l_idx)
                if ans < r_idx:
                    count += r_idx - ans
                    l_idx = ans
                else:
                    break
    return count


def h(x):
    return f(x) if K <= neg_count else g(x)

# print(f(0)) # => 4になってほしい(01.inの場合)
# print(f(-6)) # => 4になってほしい(01.inの場合)
# print(f(-7)) # => 2になってほしい(01.inの場合)
# print(f(-12)) # => 2になってほしい(01.inの場合)
# print(f(-13)) # => 0になってほしい(01.inの場合)

# print(h(10)) # => 10になってほしい(04.inの場合)
# print(h(14)) # => 11になってほしい(04.inの場合)
# print(h(23)) # => 12になってほしい(04.inの場合)
# print(h(72)) # => 15になってほしい(04.inの場合)
# print(h(39)) # => 13になってほしい(04.inの場合)

# print(h(11)) # => 7になってほしい(05.inの場合)
# print(h(5)) # => 5になってほしい(05.inの場合)
# print(h(80)) # => 10になってほしい(05.inの場合)
# print(h(100)) # => 10になってほしい(05.inの場合)

l = -1 * 10 ** 18
r = 10 ** 18
while r - l > 1:
    mid = (l + r) // 2
    count = h(mid)
    # print(mid, count)
    if count >= K:
        r = mid
    else:
        l = mid
print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np
stdin = open(0)

N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().split(), np.int64)


A = np.sort(A)
zero = A[A == 0]
pos = list(A[A > 0])
neg = list(A[A < 0])

neg_count = len(pos) * len(neg)
pos_count = len(pos) * (len(pos) - 1) // 2 + len(neg) * (len(neg) - 1) // 2
zero_count = N * (N - 1) // 2 - neg_count - pos_count

if K > neg_count and K <= neg_count + zero_count:
    print(0)
    exit(0)

def f(x):
    """x以下の積の組み合わせを数える(k番目が負の場合)"""
    count = 0
    pos_idx = None
    neg_idx = len(neg) - 1
    for idx, p in enumerate(reversed(pos)):
        if p * neg[neg_idx] <= x:
            pos_idx = len(pos) - idx - 1
        else:
            break
    # pos_idxに最大の負の値x正の値 <= xを満たす最小の正値のindexが入っている
    if pos_idx is not None:
        count += len(pos) - pos_idx
    else:
        pos_idx = 0
    while neg_idx > 0:
        neg_idx -= 1
        ans = None
        for i in reversed(range(pos_idx + 1)):
            if pos[i] * neg[neg_idx] <= x:
                ans = i
                break
        if ans is None:
            break
        # iにはneg_idxの位置の負数と掛けたときに<=xを満たす最小の正数のindexが入る
        # print(i)
        count += len(pos) - ans
        pos_idx = i
    return count

def g(x):
    """x以下の積の組み合わせを数える(k番目が正の場合)"""
    count = neg_count + zero_count
    # print('c1', count)
    l_idx = 0
    r_idx = 0
    # 正数 x 正数の場合
    for idx, p in enumerate(reversed(pos)):
        if p * pos[l_idx] <= x:
            r_idx = len(pos) - idx - 1
            break
    if r_idx > 0:
        count += (r_idx + 1) - 1  # index = 0の分は引く
        while r_idx - l_idx > 0:
            l_idx += 1
            ans = l_idx
            # print(l_idx, r_idx)
            for i in reversed(range(l_idx + 1, r_idx + 1)):
                # print(i, pos[i], l_idx, pos[l_idx])
                if pos[i] * pos[l_idx] <= x:
                    ans = i
                    break
            # print('ans', ans, l_idx)
            if ans > l_idx:
                count += ans - l_idx
                r_idx = ans
            else:
                break
    # print('c2', count)
    # 負数 x 負数の場合
    r_idx = len(neg) - 1
    l_idx = len(neg) - 1
    for idx, n in enumerate(neg):
        if n * neg[r_idx] <= x:
            l_idx = idx
            break
    # print(l_idx, r_idx)
    if l_idx < r_idx:
        count += len(neg) - l_idx - 1 # r_idxの分は引く
        # print('c3', count)
        while r_idx - l_idx > 0:
                r_idx -= 1
                ans = r_idx
                # print(l_idx, r_idx)
                for i in range(l_idx, r_idx):
                    # print(i, pos[i], l_idx, pos[l_idx])
                    if neg[i] * neg[r_idx] <= x:
                        ans = i
                        break
                # print(l_idx, r_idx, ans)
                # print('ans', ans, l_idx)
                if ans < r_idx:
                    count += r_idx - ans
                    l_idx = ans
                else:
                    break
    return count


def h(x):
    return f(x) if K <= neg_count else g(x)

# print(f(0)) # => 4になってほしい(01.inの場合)
# print(f(-6)) # => 4になってほしい(01.inの場合)
# print(f(-7)) # => 2になってほしい(01.inの場合)
# print(f(-12)) # => 2になってほしい(01.inの場合)
# print(f(-13)) # => 0になってほしい(01.inの場合)

# print(h(10)) # => 10になってほしい(04.inの場合)
# print(h(14)) # => 11になってほしい(04.inの場合)
# print(h(23)) # => 12になってほしい(04.inの場合)
# print(h(72)) # => 15になってほしい(04.inの場合)
# print(h(39)) # => 13になってほしい(04.inの場合)

# print(h(11)) # => 7になってほしい(05.inの場合)
# print(h(5)) # => 5になってほしい(05.inの場合)
# print(h(80)) # => 10になってほしい(05.inの場合)
# print(h(100)) # => 10になってほしい(05.inの場合)

l = -1 * 10 ** 18
r = 10 ** 18
while r - l > 1:
    mid = (l + r) // 2
    count = h(mid)
    print(mid, count)
    if count >= K:
        r = mid
    else:
        l = mid
print(r)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_left 
def main():
    N, K = map(int, readline().split())
    A = [int(i) for i in readline().split()]
    A.sort()
    INF = int(1e18)+1
    def judge(x):
        cnt = 0
        for i in range(N):
            if A[i] < 0:
                idx = bisect_left(A, (x+A[i]-1)//A[i])
                cnt += N-idx
            elif A[i] == 0:  
                if 0 < x:
                    cnt += N
            else:
                idx = bisect_left(A, (x+A[i]-1)//A[i])
                cnt += idx  
            if A[i]*A[i]<x:
                cnt -= 1
        cnt //= 2
        return cnt

    mx = INF
    mi = -INF
    while mx-mi>1:
        md = (mx+mi)//2
        if judge(md)<K:
            mi = md
        else:
            mx = md
    print(mi)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

a.sort()

#2分探索
#負の数あるぞ

j = bisect.bisect_left(a,-0)##
l = bisect.bisect_right(a,0)#3
a1 = a[:j]
a2 = a[l:]
if j*(n-l)>=k:##負の数で揃う
    mx = 0
    mn = -max(a1[0]*a1[0],a2[-1]*a2[-1])-1##
    while mx-mn>1:
        md = (mx+mn)//2
        cnt = 0
        for t in range(j):
            tmp = bisect.bisect_left(a2,md//a1[t])
            cnt += n-l-tmp
        if cnt >=k:
            mx = md
        else:
            mn = md
    print(mx)
    exit()
k -= j*(n-l)

if k<=(l-j)*(l-j-1)//2+(n-l+j)*(l-j):
    print(0)
    exit()
#print(k,(n-l+j)*(l-j)+(l-j)*(l-j-1)//2)
k-=(l-j)*(l-j-1)//2+(n-l+j)*(l-j)
#print(k,k)
if a1 and a2:
    mx = max(a1[-1]*a1[-1],a2[-1]*a2[-1])+1##
elif a1:
    mx = a1[-1]**2+1
else:
    mx = a2[-1]**2+1
mn = -1
a1 = [-a1[j-i-1] for i in range(j)]
while mx-mn>1:
    md = (mx+mn)//2
    cnt = 0
    for t in range(j):
        tmp = bisect.bisect_right(a1,md//a1[t])
        cnt += tmp
        if tmp >=t+1:
            cnt-=1
    for t in range(n-l):
        tmp = bisect.bisect_right(a2,md//a2[t])
        cnt += tmp
        if tmp>=t+1:
            tmp-=1
    if cnt >= 2*k:
        mx = md
    else:
        mn = md
print(mx)

Submission status: Wrong Answer

Solution code:
# もう疲れたので判定にbisect使わないで自分でやります。
from bisect import bisect_left, bisect_right

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

zero_num = bisect_right(A, 0) - bisect_left(A, 0)
minus_num = bisect_left(A, 0)
plus_num = n - (zero_num + minus_num)
AP = A[zero_num + minus_num :]
AM = A[:minus_num]
plus = plus_num * (plus_num - 1) // 2 + minus_num * (minus_num - 1) // 2
zero = zero_num * (zero_num - 1) // 2 + zero_num * (n - zero_num)
minus = plus_num * minus_num

if k <= minus:
    ng = -(10 ** 20)
    ok = 0
    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0
        kouho = 0
        for i in range(plus_num):
            ookk = -1
            nngg = minus_num
            while nngg - ookk > 1:
                mmiidd = (ookk + nngg) // 2
                if AP[i] * AM[mmiidd] <= mid:
                    ookk = mmiidd
                else:
                    nngg = mmiidd
            cnt += ookk + 1
        for j in range(minus_num):
            ookk = 0
            nngg = plus_num
            while nngg - ookk > 1:
                mmiidd = (ookk + nngg) // 2
                if AM[j] * AP[mmiidd] <= mid:
                    ookk = mmiidd
                else:
                    nngg = mmiidd
            cnt += plus_num - ookk
        cnt //= 2
        if cnt < k:
            ng = mid
        else:
            ok = mid
    ans = ok
elif k <= minus + zero:
    ans = 0
else:
    # 下からk番目→上から(n-k)+1番目
    # x以上となる数がK個以上となる最大のk
    K = n * (n - 1) // 2 - k + 1
    ok = 0  # 全部OK
    ng = 10 ** 20  # 全部駄目
    while ng - ok > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for i in range(plus_num):
            ookk = plus_num
            nngg = -1
            while ookk - nngg > 1:
                mmiidd = (ookk + nngg) // 2
                if AP[i] * AP[mmiidd] >= mid:
                    ookk = mmiidd
                else:
                    nngg = mmiidd
            if AP[i] * AP[i] >= mid:
                cnt -= 1
            cnt += plus_num - ookk
        for i in range(minus_num):
            ookk = -1
            nngg = minus_num
            while nngg - ookk > 1:
                mmiidd = (ookk + nngg) // 2
                if AM[i] * AM[mmiidd] >= mid:
                    ookk = mmiidd
                else:
                    nngg = mmiidd
            if AM[i] * AM[i] >= mid:
                cnt -= 1
            cnt += ookk + 1
        cnt //= 2
        if cnt >= K:
            ok = mid
        else:
            ng = mid
    ans = ok
print(ans)

Submission status: Wrong Answer

Solution code:
# もう疲れたので判定にbisect使わないで自分でやります。
from bisect import bisect_left, bisect_right

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

zero_num = bisect_right(A, 0) - bisect_left(A, 0)
minus_num = bisect_left(A, 0)
plus_num = n - (zero_num + minus_num)
AP = A[zero_num + minus_num :]
AM = A[:minus_num]
plus = plus_num * (plus_num - 1) // 2 + minus_num * (minus_num - 1) // 2
zero = zero_num * (zero_num - 1) // 2 + zero_num * (n - zero_num)
minus = plus_num * minus_num

if k <= minus:
    ng = -(10 ** 20)
    ok = 0
    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0
        kouho = 0
        for i in range(plus_num):
            ookk = -1
            nngg = minus_num
            while nngg - ookk > 1:
                mmiidd = (ookk + nngg) // 2
                if AP[i] * AM[mmiidd] <= mid:
                    ookk = mmiidd
                else:
                    nngg = mmiidd
            cnt += ookk + 1
        for j in range(minus_num):
            ookk = 0
            nngg = plus_num
            while nngg - ookk > 1:
                mmiidd = (ookk + nngg) // 2
                if AM[j] * AP[mmiidd] <= mid:
                    ookk = mmiidd
                else:
                    nngg = mmiidd
            cnt += plus_num - ookk
        cnt //= 2
        if cnt < k:
            ng = mid
        else:
            ok = mid
    ans = ok
elif k <= minus + zero:
    ans = 0
else:
    # 下からk番目→上から(n-k)+1番目
    # x以上となる数がK個以上となる最大のk
    K = n * (n - 1) // 2 - k + 1
    ok = 0  # 全部OK
    ng = 10 ** 20  # 全部駄目
    while ng - ok > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for i in range(plus_num):
            ookk = plus_num
            nngg = -1
            while ookk - nngg > 1:
                mmiidd = (ookk + nngg) // 2
                if AP[i] * AP[mmiidd] >= mid:
                    ookk = mmiidd
                else:
                    nngg = mmiidd
            if AP[i] * AP[i] >= mid:
                cnt -= 1
            cnt += plus_num - ookk
        for i in range(minus_num):
            ookk = -1
            nngg = minus_num
            while nngg - ookk > 1:
                mmiidd = (ookk + nngg) // 2
                if AM[i] * AM[mmiidd] >= mid:
                    ookk = mmiidd
                else:
                    nngg = mmiidd
            if AM[i] * AM[i] >= mid:
                cnt -= 1
            cnt += ookk + 1
        cnt //= 2
        if cnt >= K:
            ok = mid
        else:
            ng = mid
        print(ok, ng)
    ans = ok
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3


# x 未満が k 個未満であるか
def f(x):
    cnt = 0
    for i in range(n):
        if a[i] < 0:
            ok = n - 1
            ng = -1
            while abs(ok - ng) > 1:
                m = (ok + ng) // 2
                if a[m] * a[i] < x:
                    ok = m
                else:
                    ng = m
            cnt += n - ok
        else:
            ok = 0
            ng = n
            while abs(ok - ng) > 1:
                m = (ok + ng) // 2
                if a[m] * a[i] < x:
                    ok = m
                else:
                    ng = m
            cnt += ok + 1
        if a[i] * a[i] < x:
            cnt -= 1
    cnt //= 2
    return cnt < k


def main():
    ok = -(10 ** 18)
    ng = 10 ** 18 + 1
    while abs(ok - ng) > 1:
        m = (ok + ng) // 2
        if f(m):
            ok = m
        else:
            ng = m
    print(ok)


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

pos_start = bisect_right(a, 0)
neg_end = bisect_left(a, 0)

pos_cnt = n - pos_start
neg_cnt = neg_end

pairs_cnt = n * (n - 1) // 2
pos_pairs_cnt = pos_cnt * (pos_cnt - 1) // 2 + neg_cnt * (neg_cnt - 1) // 2
neg_pairs_cnt = pos_cnt * neg_cnt

if k <= neg_pairs_cnt:
    high = 0
    low = -10 ** 18
    while abs(high - low) > 1:
        mid = (high + low) // 2
        cnt = 0
        r = pos_start
        for l in range(neg_end):
            while r < n and mid < a[r] * a[l]:
                r += 1
            cnt += pos_cnt - (r - pos_start)

        if cnt >= k:
            high = mid
        else:
            low = mid

    print(high)

elif pairs_cnt - pos_pairs_cnt <= k:
    k -= (pairs_cnt - pos_pairs_cnt)
    high = 10 ** 18
    low = 0
    while abs(high - low) > 1:
        mid = (high + low) // 2
        cnt = 0
        r = n - 1
        for l in range(pos_start, n):
            while l < r and mid < a[r] * a[l] and r < n:
                r -= 1
            cnt += max(0, r - l)
        
        l = 0
        for r in range(neg_end-1, -1, -1):
            while l < r and mid < a[r] * a[l] and l < n:
                l += 1
            cnt += max(0, r - l)

        if cnt >= k:
            high = mid
        else:
            low = mid

    print(high)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

pos_start = bisect_right(a, 0)
neg_end = bisect_left(a, 0)

pos_cnt = n - pos_start
neg_cnt = neg_end

pairs_cnt = n * (n - 1) // 2
pos_pairs_cnt = pos_cnt * (pos_cnt - 1) // 2 + neg_cnt * (neg_cnt - 1) // 2
neg_pairs_cnt = pos_cnt * neg_cnt

if k <= neg_pairs_cnt:
    high = 0
    low = -10 ** 18
    while abs(high - low) > 1:
        mid = (high + low) // 2
        cnt = 0
        r = pos_start
        for l in range(neg_end):
            while r < n and mid < a[r] * a[l]:
                r += 1
            cnt += pos_cnt - (r - pos_start)

        if cnt >= k:
            high = mid
        else:
            low = mid

    print(high)

elif pairs_cnt - pos_pairs_cnt <= k:
    k -= (pairs_cnt - pos_pairs_cnt)
    high = 10 ** 18
    low = 0
    while abs(high - low) > 1:
        mid = (high + low) // 2
        cnt = 0
        r = n - 1
        for l in range(pos_start, n):
            while l < r and mid < a[r] * a[l]:
                r -= 1
            cnt += max(0, r - l)
        
        l = 0
        for r in range(neg_end-1, -1, -1):
            while l < r and mid < a[r] * a[l]:
                l += 1
            cnt += max(0, r - l)

        if cnt >= k:
            high = mid
        else:
            low = mid

    print(high)

else:
    print(0)

Submission status: Wrong Answer

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

plus = []
minus = []
zero = 0

for a in A:
    if a > 0:
        plus.append(a)
    elif a < 0:
        minus.append(a)
    else:
        zero += 1

plus_cnt = len(plus) * (len(plus) - 1) // 2 + len(minus) * (len(minus) - 1) // 2
minus_cnt = len(minus) * len(plus)
zero_cnt = N * (N - 1) // 2 - minus_cnt - plus_cnt
#print(plus_cnt, minus_cnt, zero_cnt, sum([plus_cnt, minus_cnt, zero_cnt]))

if K <= minus_cnt:
    minus.sort()
    plus.sort(reverse = True)
    ok = 2 * 10 ** 18
    ng = -2 * 10 ** 18
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        mi, pi = len(minus) - 1, len(plus) - 1
        cnt = 0
        while mi >= 0 and pi >= 0:
            if minus[mi] * plus[pi] <= mid:
                cnt += pi + 1
                mi -= 1
            else:
                pi -= 1
        if cnt >= K:
            ok = mid
        else:
            ng = mid
    print(ok)
        
elif K <= minus_cnt + zero_cnt:
    print(0)
else:
    K -= minus_cnt + zero_cnt
    plus.sort()
    minus = [abs(m) for m in minus]
    minus.sort()
    #print(K, plus)
    ok = 10 ** 19
    ng = -10 ** 19
    len_plus = len(plus)
    len_minus = len(minus)
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2

        i1, i2 = 0, len_plus - 1
        cnt = 0
        while i1 < len_plus and i2 >= 0:
            if plus[i1] * plus[i2] <= mid:
                if i1 <= i2:
                    cnt += i2
                else:
                    cnt += i2 + 1
                i1 += 1
            else:
                i2 -= 1

        i1, i2 = 0, len_minus - 1
        while i1 < len_minus and i2 >= 0:
            if minus[i1] * minus[i2] <= mid:
                if i1 <= i2:
                    cnt += i2
                else:
                    cnt += i2 + 1
                i1 += 1
            else:
                i2 -= 1

        cnt //= 2
        #print("mid",  mid,"cnt", cnt, K)
        if cnt >= K:
            ok = mid
        else:
            ng = mid
    print(ok)

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left, bisect_right
    import numpy as np
    n, k, *a = map(int, open(0).read().split())
    a = sorted(a)
    l, r = bisect_left(a, 0), bisect_right(a, 0)
    ng, zs, ps = l, r - l, n - r
    print(ng, zs, ps)
    if ng * ps < k <= ng * ps + zs * (n - 1):
        print(0)
        exit()
    if ng * ps >= k:
        x = 0
        c = 0
        while 1:
            p, q = a[x], a[x + 1]
            s = a[n - 1]
            ll = p * np.array(a[r - 1:])
            i = bisect_left(ll, s * q)
            if i == 0:
                if c + n - r < k:
                    c += n - r
                    x += 1
                else:
                    j = k - c
                    ans = ll[-j]
                    print(ans)
                    exit()
            else:
                if c + n - r + i < k:
                    c += n - r
                    x += 1
                else:
                    if k - c <= n - i:
                        ans = ll[k - c]
                        print(ans)
                        exit()
                    else:
                        vv = q * np.array(a[-i:])
                        ll = np.concatenate([ll, vv])
                        ll.sort()
                        ans = ll[k - c]
                        print(ans)
                        exit()

    else:
        print("hello")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left, bisect_right
    import numpy as np
    n, k, *a = map(int, open(0).read().split())
    a = sorted(a)
    l, r = bisect_left(a, 0), bisect_right(a, 0)
    ng, zs, ps = l, r - l, n - r

    if ng * ps < k <= ng * ps + zs * (zs - 1):
        print(0)
        exit()
    if ng * ps >= k:
        x = 0
        c = 0
        while 1:
            p, q = a[x], a[x + 1]
            s = a[n - 1]
            ll = p * np.array(a[r - 1:])
            i = bisect_left(ll, s * q)
            if i == 0:
                if c + n - r < k:
                    c += n - r
                    x += 1
                else:
                    j = k - c
                    ans = ll[-j]
                    print(ans)
                    exit()
            else:
                if c + n - r + i < k:
                    c += n - r
                    x += 1
                else:
                    if k - c <= n - i:
                        ans = ll[k - c]
                        print(ans)
                        exit()
                    else:
                        vv = q * np.array(a[-i:])
                        ll = np.concatenate([ll, vv])
                        ll.sort()
                        ans = ll[k - c]
                        print(ans)
                        exit()

    else:
        print("hello")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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

kl = []
for i in range(n-1):
    for j in range(i,n):
        if i==j:
            pass
        else:
            kl.append(a[i]*a[j])
kl.sort()
print(kl[k-1])
print(kl)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

an = []
az = []
ap = []

for i in range(n):
    if a[i] < 0:
        an.append(a[i])
    elif a[i] == 0:
        az.append(a[i])
    else:
        ap.append(a[i])

an = sorted(an)
ap = sorted(ap)

an_rev = sorted(an, reverse=True)


def count(x):
    cnt = 0
    if x < 0:
        r = 0
        for t in ap[::-1]:
            while r < len(an) and t*an_rev[r] <= x:
                r += 1
            cnt += r
    elif x == 0:
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    else:
        r = 0
        for t in ap[::-1]:
            while r < len(ap) and t*ap[r] <= x:
                r += 1
            cnt += r
            if t*t <= x:
                cnt -= 1
        r = 0
        for t in an:
            while r < len(an) and t*an_rev[r] <= x:
                r += 1
            cnt += r
            if t*t <= x:
                cnt -= 1
        cnt //= 2
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    return cnt


bottom = -10**18-1
top = 10**18+1

while top - bottom > 1:
    mid = (top + bottom) // 2
    if count(mid) >= k:
        top = mid
    else:
        bottom = mid

print(top)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from bisect import bisect_right

n, k = map(int, input().split())
a = [int(x) for x in input().split()]

an = []
az = []
ap = []

for i in range(n):
    if a[i] < 0:
        an.append(a[i])
    elif a[i] == 0:
        az.append(a[i])
    else:
        ap.append(a[i])

an = sorted(an)
ap = sorted(ap)


def count(x):
    cnt = 0
    if x > 0:
        for t in ap:
            cnt += bisect_right(ap, x//t)
            if t*t <= x:
                cnt -= 1
        for t in an:
            cnt += len(an) - bisect_left(an, x//t)
            if t*t <= x:
                cnt -= 1
        cnt //= 2
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    elif x == 0:
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    else:
        for t in ap:
            cnt += bisect_right(an, x//t)
    return cnt


bottom = -10**18-1
top = 10**18+1

while top - bottom > 1:
    mid = (top + bottom) // 2
    if count(mid) >= k:
        top = mid
    else:
        bottom = mid

print(top)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from bisect import bisect_right

n, k = map(int, input().split())
a = [int(x) for x in input().split()]

an = []
az = []
ap = []

for i in range(n):
    if a[i] < 0:
        an.append(a[i])
    elif a[i] == 0:
        az.append(a[i])
    else:
        ap.append(a[i])

an = sorted(an)
ap = sorted(ap)


def count(x):
    cnt = 0
    if x > 0:
        for t in ap:
            cnt += bisect_right(ap, x/t)
            if t*t <= x:
                cnt -= 1
        for t in an:
            cnt += len(an) - bisect_left(an, x/t)
            if t*t <= x:
                cnt -= 1
        cnt //= 2
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    elif x == 0:
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    else:
        for t in ap:
            cnt += bisect_right(an, x/t)
    return cnt


bottom = -10**18-1
top = 10**18+1

while top - bottom > 1:
    mid = (top + bottom) // 2
    if count(mid) >= k:
        top = mid
    else:
        bottom = mid

print(top)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from bisect import bisect_right

n, k = map(int, input().split())
a = [int(x) for x in input().split()]

an = []
az = []
ap = []

for i in range(n):
    if a[i] < 0:
        an.append(a[i])
    elif a[i] == 0:
        az.append(a[i])
    else:
        ap.append(a[i])

an = sorted(an)
ap = sorted(ap)


def count(x):
    cnt = 0
    if x > 0:
        for t in ap:
            cnt += bisect_right(ap, x/t)
            if t*t <= x:
                cnt -= 1
        for t in an:
            cnt += len(an) - bisect_left(an, x/t)
            if t*t <= x:
                cnt -= 1
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    elif x == 0:
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    else:
        for t in ap:
            cnt += bisect_right(an, x/t)
    return cnt


bottom = -10**18-1
top = 10**18+1

while top - bottom > 1:
    mid = (top + bottom) // 2
    if count(mid) >= k:
        top = mid
    else:
        bottom = mid

print(top)

Submission status: Wrong Answer

Solution code:
import itertools, bisect, math
N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
il = bisect.bisect_left(A, 0)
ir = bisect.bisect_right(A, 0)
Am = [-a for a in A[:il]][::-1]
Ap = A[ir:]
nm = il
np = N - ir
n0 = ir - il
if K <= nm * np:
    lb = 0
    rb = 10**18 + 1
    while rb - lb > 1:
        mid = (rb + lb) // 2
        check = 0
        for a in Am:
            check += np - bisect.bisect_left(Ap, (mid - 1) // a + 1)
        if check <= K:
            rb = mid
        else:
            lb = mid
    ans = -lb
elif K <= N * (N - 1) // 2 - nm * (nm - 1) // 2 - np * (np - 1) // 2:
    ans = 0
else:
    K -= N * (N - 1) // 2 - nm * (nm - 1) // 2 - np * (np - 1) // 2
    lb = 0
    rb = 10**18 + 1
    while rb - lb > 1:
        mid = (rb + lb) // 2
        check = 0
        for i, a in enumerate(Am):
            b = (mid - 1) // a + 1
            check += bisect.bisect_left(Am[i + 1:], b)
        for i, a in enumerate(Ap):
            b = (mid - 1) // a + 1
            check += bisect.bisect_left(Ap[i + 1:], b)
        if check >= K:
            rb = mid
        else:
            lb = mid
    ans = lb
print(ans)