Problem p02774 (python)

Fixed submission:
n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

import bisect
n_m = bisect.bisect_left(a, 0)
n_0 = bisect.bisect_left(a, 1) - n_m
n_p = n - (n_m + n_0)

nn_p = n - (n_m * n_p + n_0 * (n - n_0) + n_0*(n_0-1)//2)

if( n_m * n_p < k)&(k <= n - nn_p):
    print(0)
    exit()

def calc_m(a, b, len_a, len_b, x):
    i = len_a-1
    j = 0
    cnt = 0
    while(True):
        tmp = a[i] * b[j]
        if( tmp < x):
            cnt += i+1
            j += 1
        else:
            i -= 1

        if(i < 0)|(j >= len_b):
            break
    return cnt

def calc_p(a,len_a, x):
    if(len_a <= 1):
        return 0

    i = len_a - 1
    j = 0
    cnt = 0
    while(True):
        tmp = a[i] * a[j]
        if( tmp < x):
            cnt += i+1 - ( i >= j)
            j += 1
        else:
            i -= 1

        if(i < 0)|(j >= len_a):
            break
    return cnt//2

if( n_m * n_p >= k):
    a_m = tuple(a[:n_m])
    a_p = tuple(a[  :(n - n_p -1):-1])

    ul = [a_m[-1] * a_p[-1]+1, n_m*n_p]
    dl = [a_m[0] * a_p[0]-1, 0]

    while(True):
        if(ul[0] - dl[0] == 1):
            break
        mid = (dl[0] + ul[0])//2
        mid_cnt = calc_m(a_m,a_p,n_m,n_p, mid)

        if( mid_cnt < k):
            dl = [ mid, mid_cnt ]
        else:
            ul = [ mid, mid_cnt ]

    print(dl[0])

else:
    k = k - (n - nn_p)
    a_m = tuple(a[n_m - 1::-1])
    a_p = tuple(a[ (n - n_p) :])

    if(n_m <= 1):
        ul = [a_p[-1] * a_p[-2]+1, nn_p]
        dl = [a_p[0] * a_p[1]-1, 0]
    elif(n_p <= 1):
        ul = [a_m[-1] * a_m[-2]+1, nn_p]
        dl = [a_m[0] * a_m[1]-1, 0]
    else:
        ul = [max(a_m[-1] * a_m[-2]+1 ,a_p[-1] * a_p[-2]+1), nn_p]
        dl = [min(a_p[0] * a_p[1]-1 ,a_m[0] * a_m[1]-1), 0]

    while(True):
        if(ul[0] - dl[0] == 1):
            break
        mid = (dl[0] + ul[0])//2
        mid_cnt = calc_p(a_m,n_m, mid) + calc_p(a_p,n_p, mid)

        if( mid_cnt < k):
            dl = [ mid, mid_cnt ]
        else:
            ul = [ mid, mid_cnt ]

    print(dl[0])

Buggy submission (verdict: Runtime Error):
# 二分木
import bisect

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

a.sort()

len_m = bisect.bisect_left(a, 0)
len_0 = bisect.bisect_right(a, 0) - len_m
len_p = n - len_m - len_0

a_m = a[:len_m][::-1]
for i in range(len_m):
    a_m[i] = -1 * a_m[i]
a_p = a[(len_m + len_0):]

num_m = len_m * len_p
num_0 = len_0 * (n - len_0) + len_0*(len_0 - 1)//2

def calc(a1, a2, x):
    #a1[i]*a2[j]でX以上になるものの数を数える
    #a1,a2ともに正の値のみ、かつソートされているとする。
    ans = 0
    len_a2 = len(a2)
    tmp_j = len_a2
    for i in range(len(a1)):
        tmp = x/a1[i]
        tmp_j =  bisect.bisect_left(a2[:tmp_j] , tmp)
        ans += len_a2 - tmp_j
    return(ans)

def calc2(a1,a2, x):
    #a1[i]**2,a2[j]**2でX以上になるものの数を数える
    #a1,a2ともに正の値のみ、かつソートされているとする。
    ans = 0
    for ax in [a1,a2]:
        len_ax = len(ax)
        tmp_j = len_ax
        for i in range(len_ax):
            tmp = x/ax[i]
            tmp_j =  bisect.bisect_left(ax[(i+1):tmp_j] , tmp) + (i+1)
            ans += len_ax - max(tmp_j, i+1)
    return(ans)

def calc3(a1,x):
    ans = 0
    for ax in [a1]:
        len_ax = len(ax)
        tmp_j = len_ax
        for i in range(len_ax):
            tmp = x/ax[i]
            tmp_j =  bisect.bisect_left(ax[(i+1):tmp_j] , tmp) + (i+1)
            ans += len_ax - max(tmp_j, i+1)
    return(ans)


if( k <= num_m ):
    # minus
    min_ = a_m[0] * a_p[0]
    max_ = a_m[-1] * a_p[-1]
    ans = (min_ + max_)//2
    dic = {}
    count = 0
    while(count < 100000):
        # print(ans)
        # print("{} {}".format(max_, min_))
        x = calc(a_m, a_p, ans)
        x_b = calc(a_m, a_p, ans + 1)
        # print("{} {}".format(x, x_b))
        if(( x_b < k ) & ( k <= x )):
            print(ans)
            break
        elif(x_b >= k):
            min_ = max(ans, min_+1)
        else:
            max_ = ans
        ans = (min_ + max_)//2
        count += 1

elif(k <= num_m + num_0 ):
    # 0
    print(0)

else:
    # plus
    k = n*(n-1)//2 - k
    if( (len_m == 1) | (len_p == 1)):
        if(len_m == 1):
            a1 = a_p
        else:
            a1 = a_m
        min_ = a1[0] * a1[1]
        max_ = a1[-1] * a1[-2]
        ans = (min_ + max_)//2
        while(True):
            x = calc3(a1, ans)
            x_b = calc3(a1, ans+1)
            if(( x_b <= k ) & ( k < x )):
                print(ans)
                break
            elif(x_b > k):
                min_ = max(ans, min_+1)
            else:
                max_ = ans
            ans = (min_ + max_)//2
    else:
        min_ = min(a_m[0] * a_m[1], a_p[0] * a_p[1])
        max_ = max(a_m[-1] * a_m[-2], a_p[-1] * a_p[-2])
        ans = (min_ + max_)//2
        count = 0
        while(count < 100000):
            # print(ans)
            # print("{} {}".format(max_, min_))
            x = calc2(a_m, a_p, ans)
            x_b = calc2(a_m, a_p, ans+1)
            # print("{} {}".format(x, x_b))
            if(( x_b <= k ) & ( k < x )):
                print(ans)
                break
            elif(x_b > k):
                min_ = max(ans, min_+1)
            else:
                max_ = ans
            ans = (min_ + max_)//2
            count += 1