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 sys
import bisect
input = sys.stdin.readline

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

    minus, plus, zero = [], [], 0
    for i in range(n):
        if a[i] < 0:
            minus.append(a[i])
        elif a[i] > 0:
            plus.append(a[i])
        else:
            zero += 1
    
    minus_count = len(minus) * len(plus)
    zero_count = zero * (zero - 1) // 2 + zero * (len(minus) + len(plus))

    minus.sort()
    plus.sort()

    if k <= minus_count:
        l, r = -int(1e18), 0
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            for v in minus:
                border = 0
                while border < len(plus) and v * plus[len(plus)-border-1] <= value:
                    border += 1 
                count += border

            if count >= k:
                r = value
            else:
                l = value

        ans = r

    elif k <= zero_count + minus_count:
        ans = 0
        
    else:
        l, r = 0, int(1e18)
        count_default = minus_count + zero_count
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            
            border = 0
            for v in minus:
                while border < len(minus) and v * minus[-border-1] <= value:
                    border += 1
                count += border
                if border > 0 and v >= minus[-border]:
                    count -= 1
            
            border = 0
            for v in plus:
                while border < len(plus) and v * plus[-border-1] > value:
                    border += 1
                count += len(plus) - border
                if border < len(plus) and v <= plus[-border-1]:
                    count -= 1

            count //= 2
            count += count_default

            if count >= k:
                r = value
            else:
                l = value
        ans = r
    print(ans)
    #return ans

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

    minus, plus, zero = [], [], 0
    for i in range(n):
        if a[i] < 0:
            minus.append(a[i])
        elif a[i] > 0:
            plus.append(a[i])
        else:
            zero += 1
    
    minus_count = len(minus) * len(plus)
    zero_count = zero * (zero - 1) // 2 + zero * (len(minus) + len(plus))

    minus.sort()
    plus.sort()

    if k <= minus_count:
        l, r = -int(1e18), 0
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            for v in minus:
                border = (-value-1) // (-v) + 1
                count += len(plus) - bisect.bisect_left(plus, border)

            if count >= k:
                r = value
            else:
                l = value

        ans = r

    elif k <= zero_count + minus_count:
        ans = 0
        
    else:
        l, r = 0, int(1e18)
        count_default = minus_count + zero_count
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            
            edge = 0
            for v in minus:
                border = value // -v
                lo = bisect.bisect_left(minus, -border, lo=0)
                count += (len(minus) - lo)
                if -v <= border:
                    count -= 1
            
            edge = len(plus)
            for v in plus:
                border = value // v
                hi = bisect.bisect_right(plus, border, hi=edge)
                count += hi
                if v <= border:
                    count -= 1
            
            count //= 2
            count += count_default

            if count >= k:
                r = value
            else:
                l = value
        ans = r
    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

    minus, plus, zero = [], [], 0
    for i in range(n):
        if a[i] < 0:
            minus.append(a[i])
        elif a[i] > 0:
            plus.append(a[i])
        else:
            zero += 1
    
    minus_count = len(minus) * len(plus)
    zero_count = zero * (zero - 1) // 2 + zero * (len(minus) + len(plus))

    minus.sort()
    plus.sort()

    if k <= minus_count:
        l, r = -int(1e18), 0
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            for v in minus:
                border = (-value-1) // (-v) + 1
                count += len(plus) - bisect.bisect_left(plus, border)

            if count >= k:
                r = value
            else:
                l = value

        ans = r
    elif k <= zero_count + minus_count:
        ans = 0
    else:
        l, r = 0, int(1e18)
        count_default = minus_count + zero_count
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            
            for v in minus:
                border = value // -v
                count += (len(minus) - bisect.bisect_left(minus, -border))
                if -v <= border:
                    count -= 1

            for v in plus:
                border = value // v
                count += bisect.bisect_right(plus, border)
                if v <= border:
                    count -= 1
            
            count //= 2
            count += count_default

            if count >= k:
                r = value
            else:
                l = value
        ans = r
    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def binary_search(*, ok, ng, func):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    from bisect import bisect_left, bisect_right

    INF = 10 ** 18 + 1

    def count(x):
        # a*b<=x
        # a>=0
        #   b<=x//a
        # a<0
        #   (-a)*b>=(-x)
        #   (-a)*b<(-x)
        #   (-a)*b<=(-x-1)
        #   b<=(-x-1)//(-a)

        cnt = 0
        for i in range(n):
            # A[i] < 0
            key = (-x - 1) // (-A[i])
            cnt += N - bisect_right(A, key)
            if A[i] * A[i] <= x:
                cnt -= 1

        if x >= 0:
            cnt += (z - n) * (N - 1)

        for i in range(z, N):
            # A[i] > 0
            key = x // A[i]
            cnt += bisect_right(A, key)
            if A[i] * A[i] <= x:
                cnt -= 1

        return cnt // 2

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

    n = bisect_left(a=A, x=0)  # [0,n)=>負
    z = bisect_left(a=A, x=1)  # [n,z)=>0

    ans = binary_search(ok=INF, ng=-INF, func=lambda x: count(x) >= K)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

import numpy as np
n,k = inpl()
a = inpl()
mi = []
mi_ab = []
pl = []
ze = 0
for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(x)
        mi_ab.append(-x)
    else:
        ze += 1
mi_cnt = len(mi); pl_cnt = len(pl)
mi = np.array(mi)
mi_ab = np.array(mi_ab)
pl = np.array(pl)
mi.sort()
pl.sort()
mi_ab.sort()

def sol(x):
    cnt = 0
    if x >= 0:
        for y in pl:
            now = x//y
            cnt += bisect_right(pl,now)
            if y < now: cnt -= 1
        for y in mi_ab:
            now = x//y
            cnt += bisect_right(mi_ab,now)
            if y < now: cnt -= 1
        cnt //= 2
        cnt += ze*(n-1) - ze*(ze-1)//2
        cnt += mi_cnt*pl_cnt
    else:
        for y in pl:
            now = x//y
            cnt += bisect_right(mi,now)
    return True if cnt >= k else False

if k <= mi_cnt*pl_cnt:
    ok = -1; ng = -pow(10,18)-1
else:
    ok = pow(10,18)+1; ng = -1

while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    # print(mid,sol(mid))
    if sol(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
posi = []
nega = []
zero = []
for i in range(n):
    if a[i] < 0:
        nega.append(a[i] * -1)
    elif a[i] > 0:
        posi.append(a[i])
    else:
        zero.append(a[i])
zero = len(zero)
posi.sort()
nega.sort()
lp, ln = len(posi), len(nega)
if k <= lp * ln:
    l, r = 0, 10 ** 18
    while r - l > 1:
        m = (l + r) // 2
        cnt = lp * ln
        cur = 0
        for i in range(ln)[::-1]:
            while cur < lp and posi[cur] < (m + nega[i] - 1) // nega[i]:
                cur += 1
            cnt -= cur
        if cnt >= k:
            l = m
        else:
            r = m
    print(-1 * l)
elif k <= n * (n - 1) // 2 - (lp * (lp - 1) // 2) - (ln * (ln - 1) // 2):
    print(0)
else:
    k -= n * (n - 1) // 2 - (lp * (lp - 1) // 2) - (ln * (ln - 1) // 2)
    l, r = 0, 10 ** 18
    while r - l > 1:
        m = (l + r) // 2
        cnt = 0
        cur = ln - 1
        for i in range(ln):
            while cur and nega[cur] > m // nega[i]:
                cur -= 1
            if cur > i:
                cnt += cur - i
        cur2 = lp - 1
        for i in range(lp):
            while cur2 and posi[cur2] > m // posi[i]:
                cur2 -= 1
            if cur2 > i:
                cnt += cur2 - i
        if cnt >= k:
            r = m
        else:
            l = m
    print(r)

Submission status: Time Limit Exceeded

Solution code:
N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = max(A[0]**2,A[-1]**2)
ok = inf
ng = -inf

def is_ok(arg):
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] == 0:
            if arg > 0:
                ans += N
        elif A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    return K > ans

while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ng = mid
    else:
        ok = mid
print(ng)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = 10 **18 +1
ok = inf
ng = -inf

def is_ok(arg):
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] == 0:
            if arg > 0:
                ans += N
        elif A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    return K > ans

while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ng = mid
    else:
        ok = mid
print(ng)

Submission status: Time Limit Exceeded

Solution code:
N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = 10 **18 +1
ok = inf
ng = -inf

def is_ok(arg):
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    return K > ans

while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ng = mid
    else:
        ok = mid
print(ng)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N ,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    inf = 10 **18 +1
    ok = inf
    ng = -inf

    def is_ok(arg):
        ans = 0
        for i in range(N):
            if A[i] * A[i] < arg :
                ans -= 1
            ok = N
            ng = -1
            if A[i] == 0:
                if arg > 0:
                    ans += N
            elif A[i] > 0:
                while (abs(ok - ng) > 1):
                    mid = (ok + ng) // 2
                    if A[i] * A[mid] < arg:
                        ng = mid
                    else:
                        ok = mid
                ans += ok
            else: 
                while (abs(ok - ng) > 1):
                    mid = (ok + ng) // 2
                    if A[i] * A[mid] < arg:
                        ok = mid
                    else:
                        ng = mid       
                ans += N-ok   
        ans /= 2
        return K > ans

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ng = mid
        else:
            ok = mid
    print(ng)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = 10 **18 +1
ok = inf
ng = -inf

def is_ok(arg):
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] == 0:
            if arg > 0:
                ans += N
        elif A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    return K > ans

while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ng = mid
    else:
        ok = mid
print(ng)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = inpl()
mi = []
mi_ab = []
pl = []
ze = 0
for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(x)
        mi_ab.append(-x)
    else:
        ze += 1
mi_cnt = len(mi); pl_cnt = len(pl)
mi.sort(); mi_ab.sort(); pl.sort()

def sol(x):
    cnt = 0
    if x >= 0:
        for y in pl:
            now = x//y
            cnt += bisect_right(pl,now)
            if y < now: cnt -= 1
        for y in mi_ab:
            now = x//y
            cnt += bisect_right(mi_ab,now)
            if y < now: cnt -= 1
        cnt //= 2
        cnt += ze*(n-1) - ze*(ze-1)//2
        cnt += mi_cnt*pl_cnt
    else:
        for y in pl:
            now = x//y
            cnt += bisect_right(mi,now)
    return True if cnt >= k else False

if k <= mi_cnt*pl_cnt:
    ok = -1; ng = -pow(10,18)-1
else:
    ok = pow(10,18)+1; ng = -1

while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    # print(mid,sol(mid))
    if sol(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = inpl()
mi = []
mi_ab = []
pl = []
ze = 0
for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(x)
        mi_ab.append(-x)
    else:
        ze += 1
mi_cnt = len(mi); pl_cnt = len(pl)
mi.sort(); mi_ab.sort(); pl.sort()
ok = 10**18+1
ng = -10**18-1
def sol(x):
    cnt = 0
    if x >= 0:
        for y in pl:
            now = x//y
            cnt += bisect_right(pl,now)
            if y < now: cnt -= 1
        for y in mi_ab:
            now = x//y
            cnt += bisect_right(mi_ab,now)
            if y < now: cnt -= 1
        cnt //= 2
        cnt += ze*(n-1) - ze*(ze-1)//2
        cnt += mi_cnt*pl_cnt
    else:
        for y in pl:
            now = x//y
            cnt += bisect_right(mi,now)
    return True if cnt >= k else False

while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    # print(mid,sol(mid))
    if sol(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = inpl()
mi = []
mi_ab = []
pl = []
ze = 0
for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(x)
        mi_ab.append(-x)
    else:
        ze += 1
mi_cnt = len(mi); pl_cnt = len(pl)
mi.sort(); mi_ab.sort(); pl.sort()
ok = 10**19
ng = -10**19
def sol(x):
    cnt = 0
    if x >= 0:
        for y in pl:
            now = x//y
            cnt += bisect_right(pl,now)
            if y < now: cnt -= 1
        for y in mi_ab:
            now = x//y
            cnt += bisect_right(mi_ab,now)
            if y < now: cnt -= 1
        cnt //= 2
        cnt += ze*(n-1) - ze*(ze-1)//2
        cnt += mi_cnt*pl_cnt
    else:
        for y in pl:
            now = x//y
            cnt += bisect_right(mi,now)
    return True if cnt >= k else False
# print(sol(8))
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    # print(mid,sol(mid))
    if sol(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

def count(t):
    c = 0
    for x in a:
        if x == 0:
            c += len(a) - 1 if t >= 0 else 0
        elif x > 0:
            c += bisect.bisect_right(a, (t // x)) - (x * x <= t)
        else:
            c += len(a) - bisect.bisect_left(a, -(t // -x)) - (x * x <= t)
    return c

lo = -1000000000000000001
hi = 1000000000000000001
while hi - lo > 1:
    mid = (lo + hi) // 2
    if count(mid) < k * 2:
        lo = mid
    else:
        hi = mid
print(hi)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K= map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    l,r = -10**18+1,10**18+1
    while l+1 < r:
        mid = (l+r)//2
        if ok(N,K,A,mid):
            l = mid
        else:
            r = mid
    return l


def ok(N,K,A,mid):
    ans = 0
    for i in range(N):
        if A[i] < 0:
            l = -1
            r = N
            while l+1 < r:
                c = (l+r)//2
                if A[c]*A[i] < mid:
                    r = c
                else:
                    l = c
            ans += N-r
        else:
            l = -1
            r = N
            while l+1 < r:
                c = (l+r)//2
                if A[c]*A[i] < mid:
                    l = c
                else:
                    r = c
            ans += r
        if A[i]*A[i]< mid:
            ans += -1
    ans = ans//2
    return ans < K


print(main())

Submission status: Time Limit Exceeded

Solution code:
N,K= map(int,input().split())
A = list(map(int,input().split()))
ans = []
for i in range(N):
    for j in range(i+1,N):
        ans.append(A[i]*A[j])
ans.sort()
print(ans[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()
    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:
                aa = -((-arg) // a)
                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(- 10 ** 18 - 10, 10 ** 18 + 10)
    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()


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