Problem p02774 (python)

Fixed submission:
"""
ブチギレチューニングタイム
"""
#!/usr/bin/env python3

import sys
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]).



def main():
    def input(): return sys.stdin.readline().rstrip()
    def mi():    return map(int, input().split())
    def lmi():   return list(map(int, input().split()))


    def is_ok(pivot, k, L_positive, L_negative):
        cnt = 0
        ind = 0
        for positive_num in L_positive:
            target = pivot // positive_num
            # O(nlgn) -> O(2 * n) = O(n) に落ちている！
            while ind < len(L_negative):
                if L_negative[ind] <= target:
                    ind += 1
                else:
                    break
            cnt += ind
        # print(f"A pivot {pivot} cnt {cnt} k {k}")
        return cnt >= k


    def is_ok_handle_duplicate(pivot, k, L_positive, L_negative):
        pos_cnt = 0
        ind = len(L_positive)
        if len(L_positive) >= 2:
            for num in L_positive:
                target = pivot // num
                # target 以下の個数を求める
                # O(nlgn) -> O(2 * n) = O(n) に落ちている！
                while ind > 0:
                    if L_positive[ind - 1] > target:
                        ind -= 1
                    else:
                        break
                pos_cnt += ind
                if num ** 2 <= pivot:
                    pos_cnt -= 1
            pos_cnt //= 2
        neg_cnt = 0
        ind = len(L_negative)
        if len(L_negative) >= 2:
            for num in L_negative:
                target = pivot // num
                # target 以下の個数を求める
                # O(nlgn) -> O(2 * n) = O(n) に落ちている！
                while ind > 0:
                    if L_negative[ind - 1] > target:
                        ind -= 1
                    else:
                        break
                neg_cnt += ind
                if num ** 2 <= pivot:
                    neg_cnt -= 1
            neg_cnt //= 2
        cnt = pos_cnt + neg_cnt
        # print(f"B pivot {pivot} cnt {cnt} k {k}")
        return cnt >= k


    n, k = mi()
    L = lmi()
    L.sort()
    l_z = bisect_left(L, 0)
    r_z = bisect_right(L, 0)
    L_negative, L_zero, L_positive = L[:l_z], L[l_z:r_z], L[r_z:]

    num_pairs_negative = len(L_negative) * len(L_positive)
    num_pairs_zero = len(L_zero) * (len(L_zero) -1) // 2 + len(L_zero) * (n - len(L_zero))
    
    if k <= num_pairs_negative:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        # left = - 10 ** 18 - 1
        # 定数倍高速化
        left = L_negative[0] * L_positive[-1] - 1
        # right = 0
        # 定数倍高速化
        right = L_negative[-1] * L_positive[0] + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= num_pairs_negative + num_pairs_zero:
        print(0)
    else:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        k -= (num_pairs_negative + num_pairs_zero)
        L_negative = [- elm for elm in reversed(L_negative)]
        # left = 0
        # 定数倍高速化
        if L_negative and L_positive:
            left = min(L_negative[0] ** 2, L_positive[0] ** 2) - 1
        elif L_negative:
            left = L_negative[0] ** 2 - 1
        else:
            left = L_positive[0] ** 2 - 1
        # right = 10 ** 18 + 1
        # 定数倍高速化
        if L_negative and L_positive:
            right = max(L_negative[-1] ** 2, L_positive[-1] ** 2) + 1
        elif L_negative:
            right = L_negative[-1] ** 2 + 1
        else:
            right = L_positive[-1] ** 2 + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok_handle_duplicate(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    

if __name__ == "__main__":
    # import time
    # s = time.time()
    main()
    # print(f"elapsed {time.time() - s} sec" )


"""
ローカル環境だと PyPy くんが 1.0 秒くらいで通るケースたちがことごとく TLE なのですが...

トータルで O(60 * nlgn) -> O(60 * n) にしたところ... (lg(10^18) ~ 60)
cat sub1_02.in | pypy3 d.py
> elapsed 1.211238145828247 sec -> elapsed 0.307081937789917 sec
cat sub1_03.in | pypy3 d.py
> elapsed 1.6172709465026855 sec -> elapsed 0.41311001777648926 sec
cat sub1_04.in | pypy3 d.py
> elapsed 0.9529299736022949 sec -> elapsed 0.1954030990600586 sec
cat sub1_08.in | pypy3 d.py
> elapsed 0.7351880073547363 sec -> elapsed 0.19420194625854492 sec
爆速！
"""

Buggy submission (verdict: Runtime Error):
def main():
    def input(): return sys.stdin.readline().rstrip()
    def mi():    return map(int, input().split())
    def lmi():   return list(map(int, input().split()))


    def is_ok(pivot, k, L_positive, L_negative):
        cnt = 0
        for positive_num in L_positive:
            target = pivot // positive_num
            # target 以下の個数を求める
            cnt += bisect_right(L_negative, target)
            # 定数倍高速化
            if cnt >= k:
                return True
        return False    


    def is_ok_handle_duplicate(pivot, k, L_positive, L_negative):
        pos_cnt = 0
        if len(L_positive) >= 2:
            for num in L_positive:
                target = pivot // num
                # target 以下の個数を求める
                pos_cnt += bisect_right(L_positive, target)
                if num ** 2 <= pivot:
                    pos_cnt -= 1
            assert(pos_cnt % 2 == 0)
            pos_cnt //= 2
        # 定数倍高速化
        if pos_cnt >= k:
            return True
        neg_cnt = 0
        if len(L_negative) >= 2:
            for num in L_negative:
                target = pivot // num
                # target 以下の個数を求める
                neg_cnt += bisect_right(L_negative, target)
                if num ** 2 <= pivot:
                    neg_cnt -= 1
            assert(neg_cnt % 2 == 0)
            neg_cnt //= 2
        cnt = pos_cnt + neg_cnt
        # print(f"pivot {pivot} cnt {cnt}")
        return cnt >= k

    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()

    num_pairs_negative = len(L_negative) * len(L_positive)
    num_pairs_zero = len(L_zero) * (len(L_zero) -1) // 2 + len(L_zero) * (n - len(L_zero))

    
    if k <= num_pairs_negative:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        # left = - 10 ** 18 - 1
        # 定数倍高速化
        left = L_negative[0] * L_positive[-1] - 1
        # right = 0
        # 定数倍高速化
        right = L_negative[-1] * L_positive[0] + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= num_pairs_negative + num_pairs_zero:
        print(0)
    else:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        k -= (num_pairs_negative + num_pairs_zero)
        L_negative = [- elm for elm in reversed(L_negative)]        
        # left = 0
        # 定数倍高速化
        if L_negative and L_positive:
            left = min(L_negative[0] ** 2, L_positive[0] ** 2) - 1
        elif L_negative:
            left = L_negative[0] ** 2 - 1
        else:
            left = L_positive[0] ** 2 - 1
        # right = 10 ** 18 + 1
        # 定数倍高速化
        if L_negative and L_positive:
            right = max(L_negative[-1] ** 2, L_positive[-1] ** 2) + 1
        elif L_negative:
            right = L_negative[-1] ** 2 + 1
        else:
            right = L_positive[-1] ** 2 + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok_handle_duplicate(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()