Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    a = np.array(a)
    l, r = 0, 0
    if k <= num_neg_pair:
        l = neg_a[0] * pos_a[cnt_pos-1]
        r = neg_a[cnt_neg-1] * pos_a[0]+1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        if cnt_neg >= 2 and cnt_pos >= 2:
            l = min(neg_a[cnt_neg-1]*neg_a[cnt_neg-2], pos_a[0]*pos_a[1])
        elif cnt_neg >= 2:
            l = neg_a[cnt_neg-1]*neg_a[cnt_neg-2]
        else:
            l = pos_a[0]*pos_a[1]
        if cnt_neg >= 2 and cnt_pos >= 2:
            r = max(neg_a[0]*neg_a[1], pos_a[cnt_pos-1]*pos_a[cnt_pos-2])+1
        elif cnt_neg >= 2:
            r = neg_a[0]*neg_a[1]+1
        else:
            r = pos_a[cnt_pos-1]*pos_a[cnt_pos-2]+1
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = 0
                if target < 0:
                    index = np.searchsorted(neg_a, target, side="riget")
                elif target == 0:
                    index = cnt_neg + cnt_zro
                else:
                    index = np.searchsorted(pos_a, target, side="right")
                    index += cnt_neg + cnt_zro
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = 0
                if target < 0:
                    index = np.searchsorted(neg_a, target, side="left")
                elif target == 0:
                    index = cnt_neg
                else:
                    index = np.searchsorted(pos_a, target, side="left")
                    index += cnt_neg + cnt_zro
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    for v in a:
        if v < 0:
            cnt_neg += 1
            neg_a.append(v)
        elif v == 0:
            cnt_zro += 1
            zro_a.append(v)
        else:
            cnt_pos += 1
            pos_a.append(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    a = np.array(a)
    l, r = 0, 0
    if k <= num_neg_pair:
        l = neg_a[0] * pos_a[cnt_pos-1]
        r = neg_a[cnt_neg-1] * pos_a[0]+1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        if cnt_neg >= 2 and cnt_pos >= 2:
            l = min(neg_a[cnt_neg-1]*neg_a[cnt_neg-2], pos_a[0]*pos_a[1])
        elif cnt_neg >= 2:
            l = neg_a[cnt_neg-1]*neg_a[cnt_neg-2]
        else:
            l = pos_a[0]*pos_a[1]
        if cnt_neg >= 2 and cnt_pos >= 2:
            r = max(neg_a[0]*neg_a[1], pos_a[cnt_pos-1]*pos_a[cnt_pos-2])+1
        elif cnt_neg >= 2:
            r = neg_a[0]*neg_a[1]+1
        else:
            r = pos_a[cnt_pos-1]*pos_a[cnt_pos-2]+1
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = np.searchsorted(a, target, side="right")
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = np.searchsorted(a, target, side="left")
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    for v in a:
        if v < 0:
            cnt_neg += 1
            neg_a.append(v)
        elif v == 0:
            cnt_zro += 1
            zro_a.append(v)
        else:
            cnt_pos += 1
            pos_a.append(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    a = np.array(a)
    l, r = 0, 0
    if k <= num_neg_pair:
        l = neg_a[0] * pos_a[cnt_pos-1]
        r = neg_a[cnt_neg-1] * pos_a[0]+1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        if cnt_neg >= 2 and cnt_pos >= 2:
            l = min(neg_a[cnt_neg-1]*neg_a[cnt_neg-2], pos_a[0]*pos_a[1])
        elif cnt_neg >= 2:
            l = neg_a[cnt_neg-1]*neg_a[cnt_neg-2]
        else:
            l = pos_a[0]*pos_a[1]
        if cnt_neg >= 2 and cnt_pos >= 2:
            r = max(neg_a[0]*neg_a[1], pos_a[cnt_pos-1]*pos_a[cnt_pos-2])+1
        elif cnt_neg >= 2:
            r = neg_a[0]*neg_a[1]+1
        else:
            r = pos_a[cnt_pos-1]*pos_a[cnt_pos-2]+1
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = np.searchsorted(a, target, side="right")
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = np.searchsorted(a, target, side="left")
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    l, r = 0, 0
    if k <= num_neg_pair:
        l = neg_a[0] * pos_a[cnt_pos-1]
        r = neg_a[cnt_neg-1] * pos_a[0]+1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        if cnt_neg >= 2 and cnt_pos >= 2:
            l = min(neg_a[cnt_neg-1]*neg_a[cnt_neg-2], pos_a[0]*pos_a[1])
        elif cnt_neg >= 2:
            l = neg_a[cnt_neg-1]*neg_a[cnt_neg-2]
        else:
            l = pos_a[0]*pos_a[1]
        if cnt_neg >= 2 and cnt_pos >= 2:
            r = max(neg_a[0]*neg_a[1], pos_a[cnt_pos-1]*pos_a[cnt_pos-2])+1
        elif cnt_neg >= 2:
            r = neg_a[0]*neg_a[1]+1
        else:
            r = pos_a[cnt_pos-1]*pos_a[cnt_pos-2]+1
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = 0
                if target < 0:
                    index = bisect_right(neg_a, target)
                elif target == 0:
                    index = cnt_neg + cnt_zro
                else:
                    index = bisect_right(pos_a, target)
                    index += cnt_neg + cnt_zro
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = 0
                if target < 0:
                    index = bisect_left(neg_a, target)
                elif target == 0:
                    index = cnt_neg + 1
                else:
                    index = bisect_left(pos_a, target)
                    index += cnt_neg + cnt_zro
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    for v in a:
        if v < 0:
            cnt_neg += 1
            neg_a.append(v)
        elif v == 0:
            cnt_zro += 1
            zro_a.append(v)
        else:
            cnt_pos += 1
            pos_a.append(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    l, r = 0, 0
    if k <= num_neg_pair:
        l = neg_a[0] * pos_a[cnt_pos-1]
        r = neg_a[cnt_neg-1] * pos_a[0]+1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        if cnt_neg >= 2 and cnt_pos >= 2:
            l = min(neg_a[cnt_neg-1]*neg_a[cnt_neg-2], pos_a[0]*pos_a[1])
        elif cnt_neg >= 2:
            l = neg_a[cnt_neg-1]*neg_a[cnt_neg-2]
        else:
            l = pos_a[0]*pos_a[1]
        if cnt_neg >= 2 and cnt_pos >= 2:
            r = max(neg_a[0]*neg_a[1], pos_a[cnt_pos-1]*pos_a[cnt_pos-2])+1
        elif cnt_neg >= 2:
            r = neg_a[0]*neg_a[1]+1
        else:
            r = pos_a[cnt_pos-1]*pos_a[cnt_pos-2]+1
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = bisect_right(a, target)
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = bisect_left(a, target)
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    for v in a:
        if v < 0:
            cnt_neg += 1
        elif v == 0:
            cnt_zro += 1
        else:
            cnt_pos += 1
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    l, r = 0, 0
    if k <= num_neg_pair:
        l = -1*10**18
        r = -1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        l = 1
        r = 10**18
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = bisect_right(a, target)
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = bisect_left(a, target)
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s = [0]*n
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = bisect_right(a, target)
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = bisect_left(a, target)
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        tot = 0
        for i in range(n):
            sl, sr = -1, n
            if a[i] < 0:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sr = sp
                    else:
                        sl = sp
                tot += n-sr
            else:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sl = sp
                    else:
                        sr = sp
                tot += sr
            if a[i]**2 < p:
                tot -= 1
        tot //= 2
        if tot < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s = [0]*n
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        for i in range(n):
            sl, sr = -1, n
            if a[i] < 0:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sr = sp
                    else:
                        sl = sp
                s[i] = n-sr
            else:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sl = sp
                    else:
                        sr = sp
                s[i] = sr
            if a[i]**2 < p:
                s[i] -= 1
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        tot = 0
        for i in range(n):
            sl, sr = -1, n
            if a[i] < 0:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sr = sp
                    else:
                        sl = sp
                tot += n-sr
            else:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sl = sp
                    else:
                        sr = sp
                tot += sr
            if a[i]**2 < p:
                tot -= 1
        tot //= 2
        if tot < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Fixed submission:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

if __name__ == "__main__":
    main()