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: Time Limit Exceeded

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
ok, ng = 10**18, -10**18

# 判定条件の実装「数列から２個選んだ積がx以下のものがK個以上ある」
def is_ok(x, A, N, K):
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    for i in range(N):
        if A[i] >= 0:
            # 固定したA[i]が正の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列は単調増加
            # j=JOKの時が「x以下」という条件を満たす最大値とすると、条件を満たす個数はJNG個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ JNG個 --------------><----------- N - JNG個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        if A[i] < 0:
            # 固定したA[i]が負の場合、積の数列
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # は単調減少。
            # j=JOKの時が、「x以下」という条件を満たす最小のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # xより大きい(NG), xより大きい(NG), ..., xより大きい(NG), x以下(OK),...,x以下(OK)
            # <--------------------- JOK個 ---------------------><----- N-JOK個 ------->
            jng, jok = -1, N
            while jok - jng > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += (N - jok)
    t = 0
    for i in range(N):
        if A[i] * A[i] <= x:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) / 2
    # それがK個以上あるかを判定する
    return total >= K

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
ok, ng = 10**18, -10**18

def is_ok(x, A, N, K):
    s = 0
    for i in range(N):
        if A[i] >= 0:
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        if A[i] < 0:
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[N-1-jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
    t = 0
    for i in range(N):
        if A[i] * A[i] <= x:
            t += 1
    total = (s - t) / 2
    return total >= K

while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
ok, ng = 10**18, -10**18

# 判定条件の実装「数列から２個選んだ積がx以下のものがK個以上ある」
def is_ok(x, A, N, K):
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    for i in range(N):
        if A[i] >= 0:
            # 固定したA[i]が正の場合、積の数列を小さい順に並べると
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列になる
            # j=Jの時が、「x以下」という条件を満たす最大のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ J+1個 --------------><----------- N-J-1個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        if A[i] < 0:
            # 固定したA[i]が正の場合、積の数列を小さい順に並べると
            # A[i]*A[n-1], A[i]*A[n-2], ... , A[i]*A[0]
            # つまり、{A[i]*A[N-1-j]} j=0~N-1 という数列になる
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[N-1-jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
    t = 0
    for i in range(N):
        if A[i] * A[i] <= x:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) / 2
    # それがK個以上あるかを判定する
    return total >= K

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 単純な組み合わせだと計算量がO(n**2)となってしまうので工夫が必要
# 小さい順にK番目の値を求めよ
# ⇄ 判定条件「x以下のものがK個以上ある」を満たす最小のxを求めよ
# ⇄ ・判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
# 　 ・「数列から２個選んだ積がx以下のものが何個あるかを数えて、K個以下か判定せよ」：片方を固定して2分探索で数えていく
import itertools

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
ok, ng = 10**18, -10**18

# 判定条件の実装「数列から２個選んだ積がx以下のものがK個以上ある」
def is_ok(x, A, N, K):
    # 数列から２個選んだ積がx以下のものが何個あるかを数える
    s = 0
    for i in range(N):
        if A[i] >= 0:
            # 固定したA[i]が正の場合、積の数列を小さい順に並べると
            # A[i]*A[0], A[i]*A[1], ... , A[i]*A[n-1]
            # つまり、{A[i]*A[j]} j=0~n-1 という数列になる
            # j=Jの時が、「x以下」という条件を満たす最大のJだとすると、条件を満たす個数はJ+1個である
            # 図解すると、
            # x以下(OK), x以下(OK), ..., x以下(OK), xより大きい(NG),...,xより大きい(NG)
            # <------------ J+1個 --------------><----------- N-J-1個 ----------->
            # 二分探索でこの境界値Jを求めにいく
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
        if A[i] < 0:
            # 固定したA[i]が正の場合、積の数列を小さい順に並べると
            # A[i]*A[n-1], A[i]*A[n-2], ... , A[i]*A[0]
            # つまり、{A[i]*A[N-1-j]} j=0~N-1 という数列になる
            jok, jng = -1, N
            while jng - jok > 1:
                jmid = (jok + jng) // 2
                if A[i] * A[N-1-jmid] <= x:
                    jok = jmid
                else:
                    jng = jmid
            s += jok + 1
    t = 0
    for i in range(N):
        if A[i] * A[i] <= x:
            t += 1
    # 求めたsは条件を満たす順列の個数なので、組み合わせの個数にするために/2する
    total = (s - t) / 2
    # それがK個以上あるかを判定する
    return total >= K

# 判定条件を満たす最小のx：2分探索 (-10**18 ~ 10**18)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, A, N, K):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

C = list(itertools.combinations(A, 2))
CX = [x[0] * x[1] for x in C]
CX.sort()
print(CX[k-1])

Submission status: Time Limit Exceeded

Solution code:
N,K= map(int, input().split())
A=list(map(int,input().split()))
ans_list =[]
for i in range(N):
    for j in range(i+1,N):
        ans_list.append(A[i]*A[j])
ans_list=sorted(ans_list)
print(ans_list[K-1])

Submission status: Time Limit Exceeded

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,j in enumerate(a):
        if j > 0:
            x = m // j
            y = bisect.bisect_right(a, x)
            if y <= i:
                count += y
            else:
                count += y - 1
        elif j < 0:
            x = -(m // -j)
            y = bisect.bisect_left(a, x)
            if y > i:
                count += n - y
            else:
                count += n - y - 1
        else:
            if m >= 0:
                count += n - 1
            else:
                continue
    if count // 2 >= k:
        r = m
    else:
        l = m
print(r)

Submission status: Time Limit Exceeded

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
while r - l > 1:
    m = (r + l) // 2
    count = 0
    for i,j in enumerate(a):
        if j > 0:
            x = m // j
            y = bisect.bisect_right(a, x)
            if y <= i:
                count += y
            else:
                count += y - 1
        elif j < 0:
            x = -(m // -j)
            y = bisect.bisect_left(a, x)
            if y > i:
                count += n - y
            else:
                count += n - y - 1
        else:
            if m >= 0:
                count += n - 1
            else:
                continue
    if count // 2 >= k:
        r = m
    else:
        l = m
print(r)

Submission status: Time Limit Exceeded

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
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
            else:
                count += y - 1
        elif a[i] < 0:
            x = -(m // -a[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
            else:
                continue
    if count // 2 >= k:
        r = m
    else:
        l = m
print(r)

Submission status: Time Limit Exceeded

Solution code:
def main():
    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
                else:
                    count += y - 1
            elif a[i] < 0:
                x = -(m // -a[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
                else:
                    continue
        if count // 2 >= k:
            r = m
        else:
            l = m
    print(r)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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
            else:
                count+=y-1
        elif a[i]<0:
            x=-(m//-a[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
            else:
                continue
    if count//2>=k:
        r=m
    else:
        l=m
print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from math import ceil

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

n_cnt = bisect_right(al,-1)
p_cnt = n-bisect_left(al,1)
zero_cnt = n-p_cnt-n_cnt
al_n = al[:n_cnt]
al_p = al[n-p_cnt:]
al_n_p = [-1*v for v in al_n]
al_n_p = al_n_p[::-1]

# print(al_p)

m_n_cnt = n_cnt*p_cnt
m_p_cnt = n_cnt*(n_cnt-1)//2 + p_cnt*(p_cnt-1)//2
m_zero_cnt = zero_cnt*(n_cnt+p_cnt) + zero_cnt*(zero_cnt-1)//2

# print(m_n_cnt, m_p_cnt, m_zero_cnt)


if k <= m_n_cnt:
    left = (-1)*(10**18)
    right = -1
    while right-left>1:
        curr_num = left + (right-left)//2
        curr_cnt = 0
        num_exist = False
        for an in al_n:
            targt_p = abs(curr_num)//abs(an)
            p_ind = bisect_right(al_p,targt_p)
            ok_p_cnt = len(al_p) - p_ind
            curr_cnt += ok_p_cnt
            if p_ind > 0 and al_p[p_ind-1]*an == curr_num:
                num_exist = True
        
        if curr_cnt > k-1:
            right = curr_num
        elif curr_cnt < k-1:
            left = curr_num
        else:
            if num_exist:
                print(curr_num)
                exit()
            else:
                left = curr_num


elif m_n_cnt < k <= m_n_cnt+m_zero_cnt:
    print(0)
    exit()

else:
    k = k - m_n_cnt - m_zero_cnt # 1-index
    right = (10**18)
    left = 0
    while right-left > 1:
        cnt = k
        # print(f'k:{k}')
        # print('----')
        curr_num = left + (right-left)//2
        curr_cnt = 0
        num_exist = False
        # curr_num = 6
        # print(curr_num, left, right)
        for i, an in enumerate(al_n_p):
            targt_p = abs(curr_num)//abs(an)
            ok_p_cnt = max(bisect_right(al_n_p,targt_p)-i-1, 0)
            cnt -= ok_p_cnt
        
        for i, an in enumerate(al_p):
            # print(f'----- {an} -----')
            targt_p = abs(curr_num)//abs(an)
            
            ok_p_cnt = max(bisect_right(al_p,targt_p)-i-1, 0)
            cnt -= ok_p_cnt
            # print(ok_p_cnt)

        if cnt > 0:
            left = curr_num
        else:
            right = curr_num

    print(right)

Submission status: Time Limit Exceeded

Solution code:
# 小さい方からk番目がx
# x以下がk個以上となる最小のx
# 負の数のところでバグってそう
from bisect import bisect_left, bisect_right

import sys

input = sys.stdin.buffer.readline


# a = "741 18295"
# b = "0 -944604971 163850760 -827469336 0 0 -567306763 -539557168 -668117519 -292165078 -473024712 619911708 469512645 -509527159 557226680 343170465 632157591 967554158 504453921 -373413032 -481024329 790180891 -915613113 0 -736270693 -610724937 313212702 -825980196 -511433631 0 -73003526 556921685 -674073325 540326700 226569243 750843585 0 -876569485 194464476 352358500 -924793067 -262188798 737902336 -814375754 -765816988 -751999182 474994777 627485128 538809282 -540999707 835048049 -507238187 -335743110 783445780 0 863185652 961347691 -729691353 -36464643 0 687200797 562804136 512837657 38470649 -396521334 1055537 480925646 -159885657 967284206 567001310 627582457 443859969 -233421845 0 -197566446 -655433696 457745299 -976460305 511266544 -632081106 -633576360 674087426 -692273586 -952015422 672433704 -487881699 -358216620 -929025323 655267646 0 285012259 114525673 140537143 284754636 35666722 -448619054 0 -54681909 -949366577 0 895203953 -885689301 387221463 0 -20040181 0 -293349382 0 -638089978 -72892329 530125410 877165207 67006005 139085790 180550757 856610842 -32703032 807567663 -939969500 -994479848 892140554 -479563688 71423548 -63617349 -161534891 766849703 -528926971 0 -481863095 -589145043 0 876416878 -43951911 -513502389 743571442 879410975 646452261 419813042 517856396 -23117399 -700971910 886969690 823977751 0 -807903085 980900226 0 -892513253 975108732 73963607 -505682572 740578661 -70623025 0 700889390 -640055074 642773682 -131712204 -480212612 -182466624 -725743035 -318626445 0 827268789 -276685512 -119660752 0 100796043 -396484472 0 -846999662 244395677 -813360771 794185827 0 -603624171 -28149489 579573779 838151548 -147625503 -149255441 -462131556 -822520414 0 -430121187 -149906952 0 498452983 301955741 -864882218 0 -4653076 170268522 620905464 597912591 5953098 0 835766287 -624231736 63054509 -441228606 -944089940 955750287 -295465544 846359331 420142518 -665700347 0 -553629559 395484971 0 781527156 -717286491 327052812 472254359 -414846234 262596365 959419364 -913266879 -21048747 0 -976832480 108172954 0 -905847678 -744891786 0 -584849412 969549845 -614049666 -61140287 -190519824 -294254920 261967812 406344153 923535467 346959337 -332655725 889593029 -858799360 457563451 -542211309 -812014769 -233295680 422985391 496621893 -356065450 7695042 -912895181 -10057863 880124709 -658232655 927784204 682042201 4939894 -409980735 0 -944835547 -382450480 797627065 168837269 27057276 -946483531 226722845 -112888586 899614742 -271875315 -468542718 -621425356 141629501 -484296269 22548698 367346609 -442957229 -949986924 -902128982 -539417609 971168746 -821875417 531772085 572540056 -803900351 -5800801 0 0 82621185 -447916433 497150043 -401756678 846979091 0 927601788 153213925 378926831 984099051 -831314734 -941096372 890361249 292570039 689834998 0 -44230769 0 -22397109 -408285606 -495794851 -737232026 0 607191664 0 -376118281 -558330604 -80592679 -94436734 945922704 361660687 0 -818214797 321363646 314235491 0 432889174 892617791 -244204723 -168202141 565982216 -547818442 432531174 461022234 243610027 0 -16576371 -268369543 395683623 -667108611 -174011649 -396639226 0 -962431425 391405155 187807118 101375719 0 730999200 707215086 -908789821 -716462633 -958693752 0 -593684603 394156182 -351128792 730720853 94876138 1815081 359855830 102912726 -819745426 -225305180 285157338 0 -926470985 0 830055498 -435501098 749612894 22645127 953406518 0 584921947 -300310045 -227724990 -84575937 916847586 513364539 576043344 988774131 -485986790 0 -515784818 438562968 740413485 218224389 446603913 25610907 0 -679769281 576472324 -138922882 883548751 -689783820 579068628 494729760 980936358 588070346 -646655994 35237791 0 821835484 783982928 752424725 791473956 -375197855 -726353611 -832614864 100268555 -43763344 -361897521 -782596016 -589663695 -468807230 -167905473 -965112201 370024944 -962801521 867031846 314284540 -941774513 -318774963 798589112 635175698 -781375632 -565586693 -193430841 992884142 486475538 672620109 624227475 584173260 -143526982 472114435 -984334949 0 73957169 635166940 61245559 -49830041 905588071 0 191162857 -823376405 -539634181 -913999368 877689662 -610600114 293510 0 0 0 624383905 719173499 -709316951 92750812 373141226 -667699567 -50666309 119217712 995449598 918696106 0 206341999 334400777 -962089869 857693082 653584457 450520629 294948967 -823813787 -185307531 -704619055 -314883423 -882046674 312027655 -779069276 588555192 0 -866646065 -650153884 447977035 -836127502 0 0 756756109 -757180731 450188479 0 468774036 0 858704256 254876591 641888020 28664564 331434870 -447595997 203993718 476886332 335749513 450968901 362813438 0 380696203 351758262 -669619199 -314118301 445563156 -22648320 -907366660 267172605 0 -462126229 0 -649798250 -290421592 691271508 0 -617507283 444088835 -202589368 0 956892218 0 548691212 478800012 0 -684691812 508252851 -992525165 -175608410 927069397 164000739 172129785 315419070 -756168852 97189416 0 -49021149 220954428 993268503 531147244 411064222 328739625 -745130857 -412683549 -821867104 467751061 306336744 823456327 -128258507 903961864 856193785 943839490 0 65998168 414460670 -534104777 -704745004 -498089192 -453398252 -790319652 151699473 41160544 714164425 971355380 -585224030 -663718660 380185368 -924739649 -750255491 -657212141 -433060872 725797173 -117878479 -563871342 258275442 96041025 0 132634395 898410047 453111755 46978505 -967224209 483288939 833675813 292529832 -968574609 -848845118 854179952 -242844625 0 303999832 860011202 62318789 -470111180 910716653 521304550 959486483 -332194428 600201899 63548755 719966624 -77082567 -556855462 408858101 191120890 739217171 -532601651 978716434 -187832237 0 -87730630 796838136 -826118218 -159297019 0 -30966363 -689195811 -650199018 702008135 -624133748 -795766502 0 0 445340936 -157836564 -555044674 -792793581 -368718137 -731420898 673635029 660729345 71241370 161642360 -420784573 239773067 1923203 -843341566 -724395064 228029545 -440889284 738907608 178046556 -156538177 183199906 34908378 962982022 103763236 362013393 351273920 495917956 -678820463 0 328416395 -430072811 201288277 409996000 952711858 0 190660608 -984913537 -954795430 -249641295 612727537 546403703 -927680719 -542039708 660184484 6973348 -195863546 -455574942 -309429937 -434905940 733083847 321861722 -291889385 0 -913654120 169564367 -708322888 151533835 280484198 23341399 0 -286762271 -329248490 387585092 358239528 -290246246 -180667870 0 -82881504 916016386 -9016315 706907186 -519929490 322108840 -148074634 565300074 -405484196 159232988 -522814351 29823158 0 861305894 -307234892 178044015 17084083 695457272 409943147 -659372091 612664126 -238100341 0 -948691193 725206741 -961090744 233522937 368326432 -506835491 0 641159373 982378286 868978100 -355868558 883247416 0 -521140724 -10020067 -755443674 227112115 -971621319 -61164629 -945833908 -944717768 -507539440 -108790636 -194959882 753585064 -440813178 636561695 917744785 656086515"
# n, k = map(int, a.split())
# A = list(map(int, b.split()))
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
minusA = bisect_left(A, 0)
mA = A[:minusA]

zeroA = bisect_right(A, 0) - bisect_left(A, 0)
plusA = n - minusA - zeroA
pA = A[-plusA:]
minus = minusA * plusA
plus = plusA * (plusA - 1) // 2 + minusA * (minusA - 1) // 2
zero = zeroA * (zeroA - 1) // 2 + (n - zeroA) * zeroA


# x以下の数を数える
def calc(x):
    mmA = mA[::-1]
    res = 0
    if x > 0:
        lim = plusA - 1
        for i in range(plusA):
            while lim >= 0:
                if pA[i] * pA[lim] > x:
                    lim -= 1
                else:
                    break
            res += lim + 1
            if lim >= i:
                res -= 1
        lim = minusA - 1
        mmA = mA[::-1]
        for i in range(minusA):
            while lim >= 0:
                if mmA[i] * mmA[lim] > x:
                    lim -= 1
                else:
                    break
            res += lim + 1
            if lim >= i:
                res -= 1
        res //= 2
        res += minus + zero
    elif x == 0:
        res += minus + zero
    else:
        # 正の数、左絶対値小さい
        # 負の数、左絶対値大きい
        lim = minusA - 1
        for i in range(plusA):
            while lim >= 0:
                if pA[i] * mmA[lim] <= x:
                    lim -= 1
                else:
                    break
            res += minusA - (lim + 1)
    return res


ng = -(10 ** 20)
ok = 10 ** 20
while ok - ng > 1:
    mid = (ok + ng) // 2
    if calc(mid) >= k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  import bisect

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

  A_m = [abs(int(x)) for x in A if x < 0]
  A_m.sort()
  N_m = len(A_m)

  A_p = [int(x) for x in A if x > 0]
  A_p.sort()
  N_p = len(A_p)

  M = N_m * N_p
  P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
  Z = (1 / 2) * N * (N - 1) - (M + P)

  if M < K <= M + Z:
      print(0)
      sys.exit()

  def cnt_M(x):
      cnt = 0
      for i in A_m:
          cnt += bisect.bisect_right(A_p, x // i)
      return cnt >= (M - K + 1)

  if K <= M:
      left = -1 - 10**18
      right = 1 + 10**18 
      while right - left > 1:
          mid = (left + right) // 2
          if cnt_M(mid):
              right = mid
          else:
              left = mid
      print(-right)
      sys.exit()
  K -= (M + Z)
  def cnt_P(x):
      cnt = 0
      ng = 0
      for i in A_m:
          cnt += bisect.bisect_right(A_m, x // i)
          if i ** 2 <= x:
              ng += 1
      for j in A_p:
          cnt += bisect.bisect_right(A_p, x // j)
          if j ** 2 <= x:
              ng += 1
      return (cnt - ng) // 2 >= K

  left = -1 - 10**18
  right = 1 + 10**18
  while right - left > 1:
      mid = (left + right) // 2
      if cnt_P(mid):
         right = mid
      else:
          left = mid

  print(right)
main()

Submission status: Time Limit Exceeded

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

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

A_m = [abs(int(x)) for x in A if x < 0]
A_m.sort()
N_m = len(A_m)

A_p = [int(x) for x in A if x > 0]
A_p.sort()
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = 0
    for i in A_m:
        cnt += bisect.bisect_right(A_p, x // i)
    return cnt >= (M - K + 1)

if K <= M:
    left = -1 - 10**18
    right = 1 + 10**18 
    while right - left > 1:
        mid = (left + right) // 2
        if cnt_M(mid):
            right = mid
        else:
            left = mid
    print(-right)
    sys.exit()
K -= (M + Z)
def cnt_P(x):
    cnt = 0
    ng = 0
    for i in A_m:
        cnt += bisect.bisect_right(A_m, x // i)
        if i ** 2 <= x:
            ng += 1
    for j in A_p:
        cnt += bisect.bisect_right(A_p, x // j)
        if j ** 2 <= x:
            ng += 1
    return (cnt - ng) // 2 >= K

left = -1 - 10**18
right = 1 + 10**18
while right - left > 1:
    mid = (left + right) // 2
    if cnt_P(mid):
       right = mid
    else:
        left = mid

print(right)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
 
negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)
 
positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)
 
negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)


# 答えが負の場合
if K <= negative_pairs_cnt:
    # にぶたん: X以下になるペアがK個以上あるか？
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)
 
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X
 
    print(ok)

# 答えが0の場合
elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)
# 答えが正の場合
else:
    # にぶたん: X以下になるペアがK個以上あるか？
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0
 
        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)
 
        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1
 
            or_higher_cnt += max(0, r - l)
 
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X
 
    print(ok)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,K=map(int,input().split())
  A=list(map(int,input().split()))
  B=[]
  C=[]
  z=0
  for i in range(N):
    if A[i]==0:z+=1
    elif A[i]<0:B.append(A[i])
    else:C.append(A[i])
  nb=len(B)
  nc=len(C)
  f0=nb*nc
  f1=f0+z*(nb+nc)+int(z*(z-1)//2)
  B.sort()
  C.sort()
  if K<=f0:
    l=-10**18
    r=0
    while 1<r-l:
      mid=(l+r)//2
      sum=0
      j=nc-1
      for i in range(nb-1,-1,-1):
        while 0<=j and B[i]*C[j]<=mid:j-=1
        sum+=nc-1-j
      if sum<K:l=mid
      else:r=mid
    print(r)
  elif K<=f1:
    print(0)
  else:
    l=0
    r=10**18+1
    while 1<r-l:
      mid=(l+r)//2
      sum=f1
      j=nb-1
      for i in range(nb-1):
        while 0<=j and B[i]*B[j]<=mid:j-=1
        sum+=min(nb-j-1,nb-i-1)
      j=0
      for i in range(nc-1,0,-1):
        while j<nc and C[i]*C[j]<=mid:j+=1
        sum+=min(i,j)
      if sum<K:l=mid
      else:r=mid
    print(r)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    M, P = [], []
    Z = 0
    for a in A:
        if a < 0: M.append(a)
        elif a == 0: Z += 1
        else: P.append(a)
    M.sort(reverse = True)
    P.sort()
    mL, pL = len(M), len(P)

    minusT = mL * pL
    zeroT = Z * (mL + pL)

    if K <= minusT: #K番目の数が負の値
        P.sort(reverse = True)
        P.append(0)
        low, high = - 10 ** 18 - 1, 0
        while high - low > 1:
            mid = (low + high) // 2
            pi = 0
            count = 0
            for i in range(mL):
                while M[i] * P[pi] <= mid: pi += 1
                count += pi
            #print(mid, count)
            if count >= K: high = mid
            else: low = mid
        print(high)

    elif K <= minusT + zeroT: #K番目の数が0
        print(0)

    else: #正の数の内、K番目の数は何か
        T = N * (N - 1) // 2
        low, high = 0, 10 ** 18 + 1
        while high - low > 1:
            mid = (high + low) // 2
            count = 0
            for i in range(pL):
                l, h = i, pL
                while h - l > 1:
                    m = (l + h) // 2
                    if P[i] * P[m] >= mid: h = m
                    else: l = m
                count += pL - h
            
            for i in range(mL):
                l, h = i, mL
                while h - l > 1:
                    m = (l + h) // 2
                    if M[i] * M[m] >= mid: h = m
                    else: l = m
                count += mL - h

            #midよりも大きい数字がcount個ある
  
            if T - count >= K: high = mid
            else: low = mid
        print(low)
   
    return 0

if __name__ == "__main__":
    solve()