Problem p02774 (python)

Fixed submission:
import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), np.int64)

a = np.sort(a)

u = a[a > 0]
d = a[a < 0]
z = len(a[a == 0])

if len(u) * len(d) < k <= len(u) * len(d) + z * (n-z) + z * (z-1) // 2:
    print(0)
    exit()

L = - 10 ** 18
H = 10 ** 18

while H - L > 1:
    M = (H + L) // 2
    count = 0
    if M > 0:
        count += z * n
    count += np.searchsorted(a, M // u, side='right').sum()
    count += (n - np.searchsorted(a, (- M - 1) // (- d), side='right')).sum()
    count -= np.count_nonzero(a * a <= M)
    count //= 2
    #print(count)
    if count >= k:
        H = M
    else:
        L = M

print(H)

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left

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

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if k <= mc * pc:
    d = a[:mc]
    u = a[mc + z:]
    H = 0
    L = d[0] * u[-1]
    D = len(d)
    while H - L > 1:
        M = (H + L) // 2
        count = 0
        P = 0
        for x in u:
            while P < D:
                if d[P] > M // x:
                    break
                P += 1
            count += P
        if count == k:
            break
        elif count < k:
            L = M
        else:
            H = M
    print(H)
    exit()
elif k <= mc * pc + z * (n - z) + z * (z - 1) // 2:
    print(0)
    exit()

d = list(map(lambda x: -x, reversed(a[:mc])))
u = a[mc + z:]
D = len(d)
U = len(u)

k -= mc * pc + z * (n - z) + z * (z - 1) // 2
L = 0
H = max(d[-1] * d[-1], u[-1] * u[-1])

while H - L > 1:
    M = (H + L) // 2
    count = 0
    P = 0
    for i in range(U-1, -1, -1):
        x = u[i]
        while P < U:
            if u[P] * x > M:
                break
            P += 1
        count += P
    for i in range(U):
        if u[i] ** 2 <= M:
            count -= 1
        else:
            break
    P = 0
    for i in range(D-1, -1, -1):
        x = d[i]
        while P < D:
            if d[P] * x > M:
                break
            P += 1
        count += P
    for i in range(D):
        if d[i] ** 2 <= M:
            count -= 1
        else:
            break
    count //= 2
    if count < k:
        L = M
    else:
        H = M
print(H)

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left

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

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if k <= mc * pc:
    d = a[:mc]
    u = a[mc + z:]
    H = 0
    L = d[0] * u[-1]
    D = len(d)
    while H - L > 1:
        M = (H + L) // 2
        count = 0
        P = 0
        for x in u:
            while P < D:
                if d[P] > M // x:
                    break
                P += 1
            count += P
        if count == k:
            break
        elif count < k:
            L = M
        else:
            H = M
    if count == k:
        print(M)
    else:
        print(M+1)
    exit()
elif k <= mc * pc + z * (n - z) + z * (z - 1) // 2:
    print(0)
    exit()

d = list(map(lambda x: -x, reversed(a[:mc])))
u = a[mc + z:]
D = len(d)
U = len(u)

k -= mc * pc + z * (n - z) + z * (z - 1) // 2
#print(k, mc * pc, z * (n-z), z * (z-1) // 2)
#print(U, D, mc, pc, z)
#print(d)
# #print(u)

L = 0
H = max(d[-1] * d[-1], u[-1] * u[-1])

while H - L > 1:
    M = (H + L) // 2
    count = 0
    P = 0
    for i in range(U-1, -1, -1):
        x = u[i]
        while P < U:
            if u[P] * x > M:
                break
            P += 1
        count += P
    for i in range(U):
        if u[i] ** 2 <= M:
            count -= 1
        else:
            break
    P = 0
    for i in range(D-1, -1, -1):
        x = d[i]
        while P < D:
            #print(x, P)
            if d[P] * x > M:
                break
            P += 1
        count += P
    for i in range(D):
        if d[i] ** 2 <= M:
            count -= 1
        else:
            break
    count //= 2
    if count < k:
        L = M
    else:
        H = M
if count == k:
    print(M)
else:
    print(M+1)

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left

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

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if k <= mc * pc:
    d = a[:mc]
    u = a[mc + z:]
    H = 0
    L = d[0] * u[-1]
    D = len(d)
    while H - L > 1:
        M = (H + L) // 2
        count = 0
        P = 0
        for x in u:
            while P < D:
                if d[P] > M // x:
                    break
                P += 1
            count += P
        if count == k:
            break
        elif count < k:
            L = M
        else:
            H = M
    if count == k:
        print(M)
    else:
        print(M+1)
    exit()
elif k <= mc * pc + z * (n - z) + z * (z - 1) // 2:
    print(0)
    exit()

d = list(map(lambda x: -x, reversed(a[:mc])))
u = a[mc + z:]
D = len(d)
U = len(u)

k -= mc * pc + z * (n - z) + z * (z - 1) // 2
#print(k, mc * pc, z * (n-z), z * (z-1) // 2)
#print(U, D, mc, pc, z)
#print(d)
# #print(u)

L = 0
H = max(d[-1] * d[-1], u[-1] * u[-1])

while H - L > 1:
    M = (H + L) // 2
    count = 0
    P = 0
    for i in range(U-1, -1, -1):
        x = u[i]
        while P < U:
            if u[P] * x > M:
                break
            P += 1
        count += P
    for i in range(U):
        if u[i] ** 2 <= M:
            count -= 1
        else:
            break
    P = 0
    for i in range(D-1, -1, -1):
        x = d[i]
        while P < D:
            #print(x, P)
            if d[P] * x > M:
                break
            P += 1
        count += P
    for i in range(D):
        if d[i] ** 2 <= M:
            count -= 1
        else:
            break
    #print(M, count)
    if count < k:
        L = M
    else:
        H = M
if count == k:
    print(M)
else:
    print(M+1)

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right

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

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if k <= mc * pc:
    d = a[:mc]
    u = a[mc + z:]
    H = 0
    L = d[0] * u[-1]
    while H - L > 1:
        M = (H + L) // 2
        count = 0
        for x in u:
            #print(M, x, M // x)
            count += bisect_right(d, M // x)
        #print(L, H, count)
        if count == k:
            break
        elif count < k:
            L = M
        else:
            H = M
    if count == k:
        print(M)
    else:
        print(M+1)
    exit()
elif k <= mc * pc + z * (n - z):
    print(0)
    exit()
print(a[10 ** 6])