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:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect

def main():
    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        if arg >= 0:
            cnt = 0
            for a in A:
                if a == 0:
                    if arg >= 0:
                        cnt += N - 1
                    else:
                        cnt += 0
                elif a < 0:
                    d = divmod(arg, a)
                    if d[1] == 0:
                        aa = d[0]
                    else:
                        aa = d[0] + 1
                    cnt += N - bisect.bisect_left(A, aa)
                    if aa <= a:
                        cnt -= 1
                else:
                    aa = arg // a
                    cnt += bisect.bisect_right(A, aa)
                    if aa >= a:
                        cnt -= 1
            cnt //= 2
        else:
            cnt = 0
            num_pos = len(A_pos)
            for a_neg in A_neg:
                d = divmod(arg, a_neg)
                if d[1] == 0:
                    aa = d[0]
                else:
                    aa = d[0] + 1
                cnt += num_pos - bisect.bisect_left(A_pos, aa)
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    N, K = MI()
    A = LI()
    A.sort()
    A_neg = []
    A_pos = []
    for a in A:
        if a < 0:
            A_neg.append(a)
        elif a > 0 :
            A_pos.append(a)

    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)
    cnt_neg = bisect.bisect_left(A, 0)
    cnt_pos = N - bisect.bisect_right(A, 0)
    cnt_zer = N - cnt_pos - cnt_neg
    neg_pair = cnt_neg * cnt_pos

    if K <= neg_pair:
        ng = p_min - 1
        ok = 1
        ans = meguru_bisect(ng, ok)
        print(ans)
    elif K <= neg_pair + cnt_zer * (N - 1) - cnt_zer * (cnt_zer - 1) // 2:
        print(0)
    else:
        ng = -1
        ok = p_max + 1
        ans = meguru_bisect(ng, ok)
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect

def main():
    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0
        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            elif a < 0:
                d = divmod(arg, a)
                if d[1] == 0:
                    aa = d[0]
                else:
                    aa = d[0] + 1
                cnt += N - bisect.bisect_left(A, aa)
                if aa <= a:
                    cnt -= 1
            else:
                aa = arg // a
                cnt += bisect.bisect_right(A, aa)
                if aa >= a:
                    cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    N, K = MI()
    A = LI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)
    cnt_neg = bisect.bisect_left(A, 0)
    cnt_pos = N - bisect.bisect_right(A, 0)
    cnt_zer = N - cnt_pos - cnt_neg
    neg_pair = cnt_neg * cnt_pos

    if K <= neg_pair:
        ng = p_min - 1
        ok = 1
        ans = meguru_bisect(ng, ok)
        print(ans)
    elif K <= neg_pair + cnt_zer * (N - 1) - cnt_zer * (cnt_zer - 1) // 2:
        print(0)
    else:
        ng = -1
        ok = p_max + 1
        ans = meguru_bisect(ng, ok)
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect



def main():
    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0
        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            elif a < 0:
                d = divmod(arg, a)
                if d[1] == 0:
                    aa = d[0]
                else:
                    aa = d[0] + 1
                cnt += N - bisect.bisect_left(A, aa)
                if aa <= a:
                    cnt -= 1
            else:
                aa = arg // a
                cnt += bisect.bisect_right(A, aa)
                if aa >= a:
                    cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    N, K = MI()
    A = LI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)
    cnt_neg = bisect.bisect_left(A, 0)
    cnt_pos = N - bisect.bisect_right(A, 0)
    cnt_zer = N - cnt_pos - cnt_neg

    if K <= cnt_neg * cnt_pos:
        ng = p_min - 1
        ok = 1
        ans = meguru_bisect(ng, ok)
        print(ans)
    elif K <= cnt_neg * cnt_pos + cnt_zer * (N - 1) - cnt_zer * (cnt_zer - 1) // 2:
        print(0)
    else:
        ng = -1
        ok = p_max + 1
        ans = meguru_bisect(ng, ok)
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

from  collections import defaultdict
from collections import Counter
import bisect
def main():
    N, K = NMI()
    A = NLI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)

    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0
        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            elif a < 0:
                d = divmod(arg, a)
                if d[1] == 0:
                    aa = d[0]
                else:
                    aa = d[0] + 1
                cnt += N - bisect.bisect_left(A, aa)
                if aa <= a:
                    cnt -= 1
            else:
                aa = arg // a
                cnt += bisect.bisect_right(A, aa)
                if aa >= a:
                    cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    ans = meguru_bisect(p_min - 1, p_max + 1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
def main():
    N, K = MI()
    A = LI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)

    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0
        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            elif a < 0:
                d = divmod(arg, a)
                if d[1] == 0:
                    aa = d[0]
                else:
                    aa = d[0] + 1
                cnt += N - bisect.bisect_left(A, aa)
                if aa <= a:
                    cnt -= 1
            else:
                aa = arg // a
                cnt += bisect.bisect_right(A, aa)
                if aa >= a:
                    cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    ans = meguru_bisect(p_min - 1, p_max + 1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import os, sys, re, math

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

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

M = sorted(M)
print(M[K - 1])

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
def main():
    N, K = MI()
    A = LI()
    A.sort()
    a = A[0] * A[1]
    b = A[-1] * A[-2]
    c = A[0] * A[-1]
    p_max = max(a, b)
    p_min = min(a, b, c)

    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0
        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            elif a < 0:
                if arg % a == 0:
                    aa = arg // a
                else:
                    aa = arg // a + 1
                cnt += N - bisect.bisect_left(A, aa)
                if aa <= a:
                    cnt -= 1
            else:
                aa = arg // a
                cnt += bisect.bisect_right(A, aa)
                if aa >= a:
                    cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    ans = meguru_bisect(p_min - 1, p_max + 1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def count(x): # x未満の組み合わせを数える
    cnt = 0
    for i in a:
        if i < 0:
            left = -1
            right = len(a)
            while left + 1 < right:
                mid = left + right
                mid //= 2
                if i * a[mid] < x:
                    right = mid
                else:
                    left = mid
            cnt += n - right

        else:
            left = -1
            right = len(a)
            while left + 1 < right:
                mid = left + right
                mid //= 2
                if i * a[mid] < x:
                    left = mid
                else:
                    right = mid
            cnt += right
        if i * i < x:
            cnt -= 1
    cnt //= 2
    return cnt < k

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

a.sort()

mini = min(a)
maxi = max(a)
left = min(mini*mini, mini*maxi, maxi*maxi) - 1
right = max(mini*mini, mini*maxi, maxi*maxi) + 1

while left + 1 < right:
    mid = left + right
    mid //= 2
    if count(mid):
        left = mid
    else:
        right = mid

print(left)

Submission status: Time Limit Exceeded

Solution code:
def count(x): # x未満の組み合わせを数える
    cnt = 0
    for i in a:
        if i < 0:
            left = -1
            right = len(a)
            while left + 1 < right:
                mid = left + right
                mid //= 2
                if i * a[mid] < x:
                    right = mid
                else:
                    left = mid
            cnt += n - right

        else:
            left = -1
            right = len(a)
            while left + 1 < right:
                mid = left + right
                mid //= 2
                if i * a[mid] < x:
                    left = mid
                else:
                    right = mid
            cnt += right
        if i * i < x:
            cnt -= 1
    cnt //= 2
    return cnt < k

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

a.sort()

left = -10**18-1
right = 10**18+1

while left + 1 < right:
    mid = left + right
    mid //= 2
    if count(mid):
        left = mid
    else:
        right = mid

print(left)

Submission status: Time Limit Exceeded

Solution code:
def count(x): # x未満の組み合わせを数える
    cnt = 0
    for i in a:
        if i < 0:
            left = -1
            right = len(a)
            while left + 1 < right:
                mid = left + right
                mid //= 2
                if i * a[mid] < x:
                    right = mid
                else:
                    left = mid
            cnt += n - right

        else:
            left = -1
            right = len(a)
            while left + 1 < right:
                mid = left + right
                mid //= 2
                if i * a[mid] < x:
                    left = mid
                else:
                    right = mid
            cnt += right
        if i * i < x:
            cnt -= 1
    cnt //= 2
    return cnt < k

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

a.sort()

left = -10**20
right = 10**20

while left + 1 < right:
    mid = left + right
    mid //= 2
    if count(mid):
        left = mid
    else:
        right = mid

print(left)

Submission status: Time Limit Exceeded

Solution code:
def General_Binary_Increase_Search(L,R,cond,Integer=True,ep=1/(1<<20)):
    """条件式が単調増加であるとき,一般的な二部探索を行う.
    L:解の下限
    R:解の上限
    cond:条件(1変数関数,広義単調減少 or 広義単調減少を満たす)
    Integer:解を整数に制限するか?
    ep:Integer=Falseのとき,解の許容する誤差
    """
    if not(cond(R)):
        return False

    if Integer:
        R+=1
        while R-L>1:
            C=L+(R-L)//2
            if cond(C):
                R=C
            else:
                L=C
        return R
    else:
        while (R-L)>=ep:
            C=L+(R-L)/2
            if cond(C):
                R=C
            else:
                L=C
        return R

def Binary_Search_Small_Count(A,x,equal=False,sort=False):
    """2分探索によって,x未満の要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"未満"がx"以下"になる
    """
    if sort:
        A.sort()

    if A[0]>x or ((not equal) and A[0]==x):
        return 0

    L,R=0,len(A)
    while R-L>1:
        C=L+(R-L)//2
        if A[C]<x or (equal and A[C]==x):
            L=C
        else:
            R=C

    return L+1

def Binary_Search_Big_Count(A,x,equal=False,sort=False):
    """2分探索によって,xを超える要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"を超える"がx"以上"になる
    """

    if sort:
        A.sort()

    if A[-1]<x or ((not equal) and A[-1]==x):
        return 0

    L,R=-1,len(A)-1
    while R-L>1:
        C=L+(R-L)//2
        if A[C]>x or (equal and A[C]==x):
            R=C
        else:
            L=C
    return len(A)-R

def h(x):
    S=0
    for a in A:
        if a>0:
            S+=Binary_Search_Small_Count(A,x//a,True)
        elif a<0:
            S+=Binary_Search_Big_Count(A,(-x-a-1)//(-a),True)
        else:
            if x>=0:
                S+=N

    if x>=0:
        T=Binary_Search_Small_Count(B,x,True)
    else:
        T=0

    return (S-T)//2
#================================================
N,K=map(int,input().split())

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

Positive=Zero=Negative=0
for a in A:
    if a>0:
        Positive+=1
    elif a==0:
        Zero+=1
    else:
        Negative+=1

X=(Positive*(Positive-1))//2+(Negative*(Negative-1))//2
Z=Positive*Negative
Y=(N*(N-1))//2-(X+Z)

B=[a*a for a in A]
B.sort()

H=max(A,key=lambda a:abs(a))
H=H*H

if K<=Z:
    print(General_Binary_Increase_Search(-H,0,lambda x:h(x)>=K))
elif Z<=K<=Z+Y:
    print(0)
else:
    print(General_Binary_Increase_Search(0,H,lambda x:h(x)>=K))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    from itertools import combinations

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

    lst = []
    for a, b in combinations(A, 2):
        lst.append(a * b)
    lst = sorted(lst)
    print(lst[K - 1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().rstrip().split())
a = list(map(int,input().rstrip().split()))
a.sort()
zero = [a[i] for i in range(n) if a[i]==0]
posi = [a[i] for i in range(n) if a[i]>0]
nega = [a[i] for i in range(n) if a[i]<0]
zero_l = len(zero)
posi_l = len(posi)
nega_l = len(nega)
zero_pair = zero_l*(n-zero_l) + zero_l*(zero_l-1)//2
posi_pair = posi_l*(posi_l-1)//2 + nega_l*(nega_l-1)//2
nega_pair = posi_l*nega_l

if k <= nega_pair:
    l = []
    for n in nega:
        for p in posi:
            l.append(n*p)
    l.sort()
    print(l[k-1])
elif k <= nega_pair+zero_pair:
    print(0)
else:
    l = []
    for i in range(posi_l-1):
        for j in range(i+1,posi_l):
            l.append(posi[i]*posi[j])
    for i in range(nega_l-1):
        for j in range(i+1,nega_l):
            l.append(nega[i]*nega[j])
    l.sort()
    print(l[k-1-nega_pair-zero_pair])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import bisect
#負の数がa個、0がb-a個
a=bisect.bisect_left(A,0)
b=bisect.bisect_right(A,0)
Z=A[a:b]
H=A[:a]
S=A[b:]
#print(H,Z,S,A)
l=-10**19
r=10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  #正×正・負×負が該当
  if mid>0:
    for i in S:
      d=bisect.bisect_right(S,mid//i)
      cnt+=d
  if mid>0:
    for i in H:
      d=bisect.bisect_right(H,(-mid-1)//(-i))
      cnt+=len(H)-d
  for i in A:
    if i!=0 and i**2<=mid:
      cnt-=1
  cnt//=2
  #0が含まれる計算が該当
  if mid>=0:
    e=len(S)+len(H)
    d=N*(N-1)//2-e*(e-1)//2
    cnt+=d
  
  #正×負の計算
  for i in S:
    d=bisect.bisect_right(H,mid//i)
    cnt+=d
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()
 
 
def is_ok(arg, sei, hu, k):
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    for index, NN in enumerate(sei, 1):
        if NN==0:
            count+=len(sei)-index
        else:
            if NN**2 >= arg:
                break
            count += bisect.bisect_right(sei, ((arg)//NN))-index  # n以下の個数を数える
    for index, NN in enumerate(hu, 1):
        if NN**2 >= arg:
            break
        count += bisect.bisect_right(hu, ((arg)//NN))-index  # n以下の個数を数える
    return count >= k
 
 
def meguru_bisect(ng, ok, sei, hu, k):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, sei, hu, k):
            ok = mid
        else:
            ng = mid
    return ok
 
 
def is_ok2(arg, sei, hu, k):#seiとhuの組み合わせで-arg以上の数がk個あるか？
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    hulen=len(sei)
    for NN in hu:
        count += hulen-bisect.bisect_right(sei, ((-arg)-1)//NN)#n未満の個数を数える
    return count >= k
 
def meguru_bisect2(ng, ok, sei, hu, k):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok2(mid, sei, hu, k):
            ok = mid
        else:
            ng = mid
    return ok
 
def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    sei = []
    hu = []
    for AA in A:
        if AA >= 0:
            sei.append(AA)
        else:
            hu.append(-AA)
    sei.sort()
    hu.sort()
    seinum = len(sei)
    hunum = len(hu)
    if seinum*hunum < k:
        ans=meguru_bisect(-1, 10**18, sei, hu, k-seinum*hunum)
    else:
        ans=meguru_bisect2(-1*10**18, 0, sei, hu, k)
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
alst = list(map(int, input().split()))
plus = []
zero = []
minus = []
for a in alst:
    if a > 0:
        plus.append(a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(-1 * a)
p = len(plus)
z = len(zero)
m = len(minus)
p_cnt = p * (p - 1) // 2 + m * (m - 1) // 2
z_cnt = p * z + m * z + z * (z - 1) // 2
m_cnt = p * m
minus.sort()
plus.sort()
if m_cnt >= k: # 答えがマイナス
    l = 0
    r = 10 ** 20
    while r - l > 1:
        num = (r + l) // 2
        p_pos = p - 1
        cnt = 0
        for m_pos in range(m):
            while minus[m_pos] * plus[p_pos] >= num and p_pos >= 0:
                p_pos -= 1
            cnt += p - p_pos - 1
        if cnt >= k:
            l = num
        else:
            r = num
    ans = l * -1
elif m_cnt + z_cnt >= k: # 答えがゼロ
    ans = 0

else: # 答えがプラス
    k -= (z_cnt + m_cnt)
    l = 0
    r = 10 ** 20
    while r - l > 1:
        num = (r + l) // 2
        m_r = m - 1
        cnt = 0
        cnt_sub = 0
        for m_l in range(m):
            while minus[m_l] * minus[m_r] > num and m_r >= 0:
                m_r -= 1
            cnt += m_r + 1
            if minus[m_l] * minus[m_l] <= num:
                cnt -= 1
        p_r = p - 1
        for p_l in range(p):
            while plus[p_l] * plus[p_r] > num and p_r >= 0:
                p_r -= 1
            cnt += p_r + 1
            if plus[p_l] * plus[p_l] <= num:
                cnt -= 1
        cnt //= 2
        if cnt >= k:
            r = num
        else:
            l = num
    ans = r
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
from math import log2
from bisect import bisect_left,bisect_right
a.sort()
# 0未満の個数
mn=bisect_left(a,0)
# 0の個数
zn=bisect_right(a,0)-mn
# 0より大きい個数
pn=n-mn-zn
am=a[:mn]
am=[-x for x in am[::-1]]
ap=a[mn+zn:]
# 自分より小さい数字がk個未満のうち最大の値を求める
# 自分より小さい数字がk個未満ならTrue
def func(x):
    cnt=0
    if x>0:
        cnt+=mn*pn
        cnt+=(zn*(n-1+n-zn))//2
        cnt1=0
        for y in ap:
            cnt1+=bisect_left(ap,(x+y-1)//y)
            if y**2<x:cnt1-=1
        for y in am:
            cnt1+=bisect_left(am,(x+y-1)//y)
            if y**2<x:cnt1-=1
        cnt+=cnt1//2
    elif x<0:
        x=abs(x)
        for y in ap:
            cnt+=mn-bisect_right(am,x//y)
    elif x==0:
        cnt+=mn*pn
    return cnt<k

if mn*pn<k:
    l,r=0,max(a[0]*a[1],a[-1]*a[-2])+1
else:
    l,r=a[0]*a[-1]-1,0
while r-l>1:
    x=(l+r)//2
    if func(x):
        l,r=x,r
    else:
        l,r=l,x
print(l)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
from math import log2
from bisect import bisect_left,bisect_right
a.sort()
# 0未満の個数
mn=bisect_left(a,0)
# 0の個数
zn=bisect_right(a,0)-mn
# 0より大きい個数
pn=n-mn-zn
am=a[:mn]
am=[-x for x in am[::-1]]
ap=a[mn+zn:]
# 自分より小さい数字がk個未満のうち最大の値を求める
# 自分より小さい数字がk個未満ならTrue
def func(x):
    cnt=0
    if x>0:
        cnt+=mn*pn
        cnt+=(zn*(n-1+n-zn))//2
        cnt1=0
        for y in ap:
            cnt1+=bisect_left(ap,(x+y-1)//y)
            if y**2<x:cnt1-=1
        for y in am:
            cnt1+=bisect_left(am,(x+y-1)//y)
            if y**2<x:cnt1-=1
        cnt+=cnt1//2
    elif x<0:
        x=abs(x)
        for y in ap:
            cnt+=mn-bisect_right(am,x//y)
    elif x==0:
        cnt+=mn*pn
    return cnt<k

if mn*pn<k:
    l,r=0,max(a[0]*a[1],a[-1]*a[-2])
else:
    l,r=a[0]*a[-1],0
while r-l>1:
    x=(l+r)//2
    if func(x):
        l,r=x,r
    else:
        l,r=l,x
print(r if func(r) else l)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
from math import log2
from bisect import bisect_left,bisect_right
a.sort()
# 0未満の個数
mn=bisect_left(a,0)
# 0の個数
zn=bisect_right(a,0)-mn
# 0より大きい個数
pn=n-mn-zn
am=a[:mn]
am=[-x for x in am[::-1]]
ap=a[mn+zn:]
# 自分より小さい数字がk個未満のうち最大の値を求める
# 自分より小さい数字がk個未満ならTrue
def func(x):
    cnt=0
    if x>0:
        cnt+=mn*pn
        cnt+=(zn*(n-1+n-zn))//2
        cnt1=0
        for y in ap:
            cnt1+=bisect_left(ap,(x+y-1)//y)
            if y**2<x:cnt1-=1
        for y in am:
            cnt1+=bisect_left(am,(x+y-1)//y)
            if y**2<x:cnt1-=1
        cnt+=cnt1//2
    elif x<0:
        x=abs(x)
        for y in ap:
            cnt+=mn-bisect_right(am,x//y)
    elif x==0:
        cnt+=mn*pn
    return cnt<k

maxaa=max(abs(a[0]),abs(a[-1]))**2
l,r=-maxaa,maxaa
while r-l>1:
    x=(l+r)//2
    if func(x):
        l,r=x,r
    else:
        l,r=l,x
print(r if func(r) else l)

Submission status: Time Limit Exceeded

Solution code:
import itertools
  
a,b = map(int, input().split())
num_list = list(map(int, input().split()))
c = list(itertools.combinations(num_list, 2))
#print(c)
d = [n*m for n,m in c]
#print(sorted(d))
print(sorted(d)[b-1])

Submission status: Time Limit Exceeded

Solution code:
import decimal


def solve_gutyoku(N, K, A):
    A_combinations = []
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            A_combinations.append(A[i] * A[j])
    ans = sorted(A_combinations)[K-1]
    return ans


def solve(N, K, A):
    for i, a in enumerate(A):
        if a >= 0:
            break
    for j, a in enumerate(A):
        if a > 0:
            break
    A_hu = A[:i]
    A_0 = A[i:j]
    A_sei = A[j:]
    n_hu = len(A_hu)*len(A_sei)
    n_0 = len(A_0)*(len(A)-1) - len(A_0)*(len(A_0)-1)//2
    n_sei = (len(A_sei) - 1) * len(A_sei) // 2 + \
        (len(A_hu) - 1) * len(A_hu) // 2
    if K > n_hu and K <= n_hu + n_0:
        return 0
    elif K <= n_hu:
        left, right = int(-1 * 1e18), 0
        while right - left > 1:
            piv = (left + right) // 2
            cnt = 0
            i = 0
            for a in A_sei:
                while i < len(A_hu) and A_hu[i] * a <= piv:
                    i += 1
                cnt += i
            if cnt >= K:
                right = piv
            else:
                left = piv
        return right
    else:
        A_hu = [-1 * a for a in A_hu[::-1]]
        K -= n_hu + n_0
        left, right = 0, int(1e18) + 1
        while right - left > 1:
            piv = (left + right) // 2
            cnt = 0
            i = 0
            for a in A_sei[::-1]:
                while i < len(A_sei) and A_sei[i] * a <= piv:
                    i += 1
                cnt += i - (a * a <= piv)
            i = 0
            for a in A_hu[::-1]:
                while i < len(A_hu) and A_hu[i] * a <= piv:
                    i += 1
                cnt += i - (a * a <= piv)
            cnt = cnt // 2
            if cnt >= K:
                right = piv
            else:
                left = piv
        return right


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    ans = solve(N, K, A)
    print(ans)
    A_combinations = []
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            A_combinations.append(A[i] * A[j])


main()