Problem p02774 (python)

Fixed submission:
import sys
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])


def main():
    read = sys.stdin.read

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

    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    A = np.array(A, np.int64)
    negative = A[A < 0]
    positive = A[A > 0]
    m = len(negative)
    p = len(positive)
    z = N - m - p

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = -negative[::-1]
    # 負の数の操作(pythonの挙動)は頭がこんがらがるので正の数にして考える

    if K <= M:
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, (mid + negative - 1) // negative, side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        left = 0
        right = max(A[0] * A[1], A[-1] * A[-2])
        positive2 = positive ** 2
        negative2 = negative ** 2
        while left + 1 < right:
            mid = (left + right) // 2
            a = np.searchsorted(negative, mid // negative, side='right').sum() - (mid >= negative2).sum()
            b = np.searchsorted(positive, mid // positive, side='right').sum() - (mid >= positive2).sum()

            if (a + b) // 2 < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer)
    print(answer[K - 1])


def main():
    read = sys.stdin.read

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

    # test(A, K)
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = np.array(A[:m], np.int64)
    positive = np.array(A[-p:], np.int64)

    if K <= M:
        negative = -negative[::-1]
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, (mid + negative - 1) // negative, side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        print(CE)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer)
    print(answer[K - 1])


def main():
    read = sys.stdin.read

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

    # test(A, K)
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            # mid以下の積はK個未満か？ left以下の積は常にK個未満
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses).astype(int), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:
        K -= M+Z
        left = 0
        right = max(minuses[0] ** 2, pluses[-1] ** 2)
        while left + 1 < right:
            mid = (left + right) // 2
            a = mid // minuses
            b = (m - np.searchsorted(minuses, a, side='left')).sum() - (mid >= minuses ** 2).sum()
            b //= 2

            d = mid // pluses
            e = np.searchsorted(pluses, d, side='right').sum() - (mid >= pluses ** 2).sum()
            e //= 2

            if b + e < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer)
    print(answer[K - 1])


def main():
    read = sys.stdin.read

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

    test(A, K)
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            # mid以下の積はK個未満か？ left以下の積は常にK個未満
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses).astype(int), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:

        K -= M+Z
        left = 0
        right = max(minuses[0] ** 2, pluses[-1] ** 2)
        while left + 1 < right:
            mid = (left + right) // 2
            a = mid // minuses
            b = (m - np.searchsorted(minuses, a, side='left')).sum() - (mid >= minuses ** 2).sum()
            b //= 2

            d = mid // pluses
            e = np.searchsorted(pluses, d, side='right').sum() - (mid >= pluses ** 2).sum()
            e //= 2

            if b + e < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_left
import numpy as np


def main():
    read = sys.stdin.read

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

    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses).astype(int), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:
        print(n)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_left
import numpy as np


def main():
    read = sys.stdin.read

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

    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:
        print(n)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_left
import numpy as np
from math import ceil


def main():
    read = sys.stdin.read

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

    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2

    if K <= M:
        left = A[0] * A[-1] - 1
        right = 0
        minuses = np.array(A[:m], np.int64)
        pluses = np.array(A[-p:], np.int64)
        while left + 1 < right:
            mid = ceil((left + right) / 2)
            a = (p-np.searchsorted(pluses, np.ceil(mid / minuses), side='left')).sum()
            if a < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:
        print(n)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_left
import numpy as np
from math import ceil

read = sys.stdin.read

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

A.sort()
m = bisect_left(A, 0)
z = bisect_left(A, 1) - m
p = N - m - z

M = m * p
Z = z * (N - z) + z * (z - 1) // 2

if K <= M:
    left = A[0] * A[-1] - 1
    right = 0
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)
    while left + 1 < right:
        mid = ceil((left + right) / 2)
        a = (p-np.searchsorted(pluses, np.ceil(mid / minuses), side='left')).sum()
        if a < K:
            left = mid
        else:
            right = mid

    print(right)
else:
    print(n)

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_left, bisect_right
import numpy as np


def cmb(n):
    if n == 0:
        return 0
    over = n * (n - 1)
    return over // 2


read = sys.stdin.read

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

A.sort()
minus = bisect_left(A, 0)
plus = N - bisect_right(A, 0)
zero = N - minus - plus

A_minus = np.array(A[:minus], np.int64)
A_plus = np.array(A[-plus:], np.int64)

minus_pair = minus * plus
zero_pair = cmb(zero) + zero * (N - zero)
plus_pair = cmb(N) - zero_pair - minus_pair

if K <= minus_pair:
    left = A_minus[0] * A_plus[-1] - 1
    right = -1

    while left + 1 < right:
        mid = (left + right) // 2
        a = np.ceil(mid / A_minus)
        b = (plus - np.searchsorted(A_plus, a, side='left')).sum()

        if b < K:
            left = mid
        else:
            right = mid

    print(right)

elif minus_pair < K <= minus_pair + zero_pair:
    print(0)
else:
    K -= minus_pair + zero_pair
    left = 0
    right = max(A_minus[0] ** 2, A_plus[-1] ** 2)
    while left + 1 < right:
        mid = (left + right) // 2
        a = mid // A_minus
        b = (minus - np.searchsorted(A_minus, a, side='left')).sum() - (mid >= A_minus ** 2).sum()
        b //= 2

        d = mid // A_plus
        e = np.searchsorted(A_plus, d, side='right').sum() - (mid >= A_plus ** 2).sum()
        e //= 2

        if b + e < K:
            left = mid
        else:
            right = mid

    print(right)