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: Runtime Error

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = lmi()
    L_negative, L_zero, L_positive = [], [], []
    for elm in L:
        if elm < 0:
            L_negative.append(elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)

    L_negative.sort()
    L_positive.sort()

    
    if k <= len(L_negative) * len(L_positive):
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        left = - 10 ** 18 - 1
        right = 0
        def is_ok(pivot):
            cnt = 0
            for positive_num in L_positive:
                target = pivot // positive_num
                # 小数徐算でいくと (丸め誤差の問題で -738602795.0000000486... のような値が -738602795.0 と評価されてしまいバグる)
                # if bisect_right(L_negative, pivot // positive_num) != bisect_right(L_negative, pivot / positive_num):
                #     print(f"!!! pivot {pivot} pos {positive_num} {pivot // positive_num} {pivot / positive_num}")
                # target 以下の個数を求める
                cnt += bisect_right(L_negative, target)
            # print(f"pivot {pivot} cnt {cnt} k {k}")
            return cnt >= k
        while right - left > 1:
            # print(f"left {left} right {right}")
            mid = (left + right) // 2
            if is_ok(mid):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= len(L_negative) * len(L_positive) + len(L_zero) * (n - len(L_zero)):
        print(0)
    else:
        raise RuntimeError
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = lmi()
    L_negative, L_zero, L_positive = [], [], []
    for elm in L:
        if elm < 0:
            L_negative.append(elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)

    L_negative.sort()
    L_positive.sort()

    
    if k <= len(L_negative) * len(L_positive):
        """
        積が x 以下となるペアの個数が k 個以下となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        left = L_negative[0] * L_positive[-1] - 1
        right = L_negative[-1] * L_positive[0] + 1
        def is_ok(pivot):
            cnt = 0
            for positive_num in L_positive:
                target = pivot / positive_num
                # target 以下の個数を求める
                cnt += bisect_right(L_negative, target)
            # print(f"pivot {pivot} cnt {cnt}")
            return cnt >= k
        while right - left > 1:
            mid = left + (right - left) // 2
            if is_ok(mid):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= len(L_negative) * len(L_positive) + len(L_zero) * (n - len(L_zero)):
        print(0)
    else:
        raise RuntimeError
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = lmi()
    L_negative, L_zero, L_positive = [], [], []
    for elm in L:
        if elm < 0:
            L_negative.append(elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)

    L_negative.sort()
    L_positive.sort()

    
    if k <= len(L_negative) * len(L_positive):
        """
        積が x 以下となるペアの個数が k 個以下となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        left = L_negative[-1] * L_positive[0] - 1
        right = L_negative[0] * L_positive[-1] + 1
        def is_ok(pivot):
            cnt = 0
            for negative_num in L_negative:
                target = pivot / negative_num
                cnt += bisect_right(L_positive, target)
            return cnt >= k
        while right - left > 1:
            mid = left + (right - left) // 2
            if is_ok(mid):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= len(L_negative) * len(L_positive) + len(L_zero) * (n - len(L_zero)):
        print(0)
    else:
        raise RuntimeError
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = lmi()
    L_negative = []
    L_zero = []
    L_positive = []
    for elm in L:
        if elm < 0:
            L_negative.append(- elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)
    # 正、昇順
    L_negative.sort()
    L_positive.sort()
    
    if k <= len(L_negative) * len(L_positive):
        raise RuntimeError
    elif k <= len(L_negative) * len(L_positive) + len(L_zero) * (n - len(L_zero)):
        print(0)
    else:
        raise RuntimeError
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = lmi()
    L.sort()
    L_negative = []
    L_zero = []
    L_positive = []    
    for elm in L:
        if elm < 0:
            L_negative.append(elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)
    negative_pair_num = len(L_negative) * len(L_positive)
    zero_pair_num = len(L_zero) * (len(L_negative) + len(L_positive))
    positive_pair_num = n * (n - 1) // 2 - (negative_pair_num + zero_pair_num)

    accum_negative = [1 if i == 0 else elm / L_negative[i-1] for i, elm in enumerate(L_negative)]
    accum_positive = [1 if i == 0 else elm / L_positive[i-1] for i, elm in enumerate(L_positive)]

    L_negative = [- elm for elm in reversed(L_negative)]    # 正、昇順

    if k <= negative_pair_num:
        intervals = [(L_positive[0] * elm, L_positive[-1] * elm) for elm in L_negative]    # [正, 正]
        # 条件「積が x 以上のペアは k 個以上存在する」(正負反転を行っているので)
        # [left, right) left は常に満たし right は常に満たさないようにする
        left = intervals[0][0] - 1
        right = intervals[-1][1] + 1
        while right - left > 1:
            mid = left + (right - left) // 2
            # print(f"mid {mid}")
            cnt = 0
            for begin, end in intervals:
                if mid <= begin:
                    cnt += len(L_positive)
                elif end < mid:
                    continue
                else:
                    mul = mid / begin
                    num = bisect_left(accum_positive, mul)
                    # assert(1 <= num <= len(L_positive) - 1)
                    cnt += (len(L_positive) - num)
            if cnt >= k:
                left = mid
            else:
                right = mid
            # print(f"cnt {cnt}")
        print(- left)
    elif negative_pair_num < k <= negative_pair_num + zero_pair_num:
        print(0)
    else:
        L_negative = list(reversed([-elm for elm in L_negative]))
        k -= (negative_pair_num + zero_pair_num)
        raise RuntimeError    


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = lmi()
    L.sort()
    L_negative = []
    L_zero = []
    L_positive = []    
    for elm in L:
        if elm < 0:
            L_negative.append(elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)
    negative_pair_num = len(L_negative) * len(L_positive)
    zero_pair_num = len(L_zero) * (len(L_negative) + len(L_positive))
    positive_pair_num = n * (n - 1) // 2 - (negative_pair_num + zero_pair_num)

    accum_negative = [1 if i == 0 else elm / L_negative[i-1] for i, elm in enumerate(L_negative)]
    accum_positive = [1 if i == 0 else elm / L_positive[i-1] for i, elm in enumerate(L_positive)]

    if k <= negative_pair_num:
        intervals = [(L_positive[-1] * elm, L_positive[0] * elm) for elm in L_negative]    # [負, 負]
        # 条件「積が x 以下のペアは k 個以上存在する」
        # [left, right) left は常に満たさず right は常に満たすようにする
        left = intervals[0][0] - 1
        right = intervals[-1][1] + 1
        while right - left > 1:
            mid = left + (right - left) // 2
            # print(f"mid {mid}")
            cnt = 0
            for begin, end in intervals:
                if mid < begin:
                    continue
                elif end <= mid:
                    cnt += len(L_positive)
                else:
                    mul = mid / begin
                    num = bisect_right(accum_positive, mul)
                    # assert(1 <= num <= len(L_positive) - 1)
                    cnt += num
            if cnt >= k:
                right = mid
            else:
                left = mid
            # print(f"cnt {cnt}")
        print(right)
    elif negative_pair_num < k <= negative_pair_num + zero_pair_num:
        print(0)
    else:
        L_negative = list(reversed([-elm for elm in L_negative]))
        k -= (negative_pair_num + zero_pair_num)
        raise RuntimeError    


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = lmi()
    L.sort()
    L_negative = []
    L_zero = []
    L_positive = []    
    for elm in L:
        if elm < 0:
            L_negative.append(elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)
    negative_pair_num = len(L_negative) * len(L_positive)
    zero_pair_num = len(L_zero) * (len(L_negative) + len(L_positive))
    positive_pair_num = n * (n - 1) // 2 - (negative_pair_num + zero_pair_num)

    accum_negative = [1 if i == 0 else elm / L_negative[i-1] for i, elm in enumerate(L_negative)]
    accum_positive = [1 if i == 0 else elm / L_negative[i-1] for i, elm in enumerate(L_positive)]

    if k <= negative_pair_num:
        intervals = [(L_positive[-1] * elm, L_positive[0] * elm) for elm in L_negative]    # [負, 負]
        # 条件「積が x 以下のペアは k 個以上存在する」
        # [left, right) left は常に満たさず right は常に満たすようにする
        left = intervals[0][0] - 1
        right = intervals[-1][1] + 1
        while right - left > 1:
            mid = left + (right - left) // 2
            # print(f"mid {mid}")
            cnt = 0
            for begin, end in intervals:
                if mid < begin:
                    continue
                elif end <= mid:
                    cnt += len(L_positive)
                else:
                    mul = mid / begin
                    num = bisect_right(accum_positive, mul)
                    # assert(1 <= num <= len(L_positive) - 1)
                    cnt += num
            if cnt >= k:
                right = mid
            else:
                left = mid
            # print(f"cnt {cnt}")
        print(right)
    elif negative_pair_num < k <= negative_pair_num + zero_pair_num:
        print(0)
    else:
        L_negative = list(reversed([-elm for elm in L_negative]))
        k -= (negative_pair_num + zero_pair_num)
        raise RuntimeError    


if __name__ == "__main__":
    main()