Problem:


Score: 400 points

Problem Statement

We have N integers A_1, A_2, ..., A_N.

There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \frac{N(N-1)}{2}

-10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 3
3 3 -4 -2

Sample Output 1

-6

There are six ways to form a pair. The products of those pairs are 9, -12, -6, -12, -6, 8.

Sorting those numbers in ascending order, we have -12, -12, -6, -6, 8, 9. The third number in this list is -6.

Sample Input 2

10 40
5 4 3 2 -1 0 0 0 0 0

Sample Output 2

6

Sample Input 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

Sample Output 3

448283280358331064



Sample input:
4 3
3 3 -4 -2


Sample output:
-6

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    from bisect import bisect_left, bisect_right

    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()

    n = bisect_left(A, 0)
    p = bisect_right(A, 0)

    Negative = np.array(A[:n], dtype = np.int64)
    Positive = np.array(A[p:], dtype = np.int64)

    Number_Negative = len(Negative) * len(Positive)
    Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
    Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

    # print (Number_Negative)
    # print (Negative)
    # print (Number_Positive)
    # print (Positive)
    # print (Number_Zero)

    def Ncount(x): #x以下の数を数える(x < 0)
        tmp = 0
        for a in Negative:
            tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
        # print (x, tmp)
        return tmp

    def Ncount1(x):
        tmp = 0
        for a in Negative:
            tmp += len(Positive) - np.searchsorted(Positive, (-x - 1) // (-a), side = 'right') 
        return tmp 

    def Pcount(x): #x以下の数を数える(x > 0)
        tmp = 0
        for index, a in enumerate(Positive):
            tmp += bisect_right(Positive[index + 1:], x // a)
        for index, b in enumerate(Negative):
            tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
            # print (bisect_right(Negative[index + 1:], x / b))
        # print (x, tmp)
        return tmp

    def Pcount1(x):
        tmp = 0
        tmp += np.searchsorted(Positive, x // Positive, side = 'right').sum()
        tmp += (len(Negative) - np.searchsorted(Negative, (-x - 1) // (-Negative), side = 'rigth')).sum()
        tmp -= np.count_nonzero(Positive * Positive <= x)
        tmp -= np.count_nonzero(Negative * Negative <= x)
        return tmp // 2

    if Number_Negative >= K:
        # ここに二分探索を書く
        l = -10 ** 18
        r = 0
        while r - l > 1:
            mid = (l + r) // 2
            if K <= Ncount1(mid):
                r = mid
            else:
                l = mid
        print (r)
        exit()
            

    elif Number_Negative < K <= Number_Negative + Number_Zero:
        print (0)
        exit()

    else:
        # ここに二分探索を書く
        l = 0
        r = 10 ** 18
        K -= (Number_Negative + Number_Zero)
        while r - l > 1:
            mid = (l + r) // 2
            if K <= Pcount1(mid):
                r = mid
            else:
                l = mid

        print (r)
        # exit()

    # print (Pcount(l) + Number_Negative + Number_Zero)
    # print (Pcount(r) + Number_Negative + Number_Zero)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = []
for i, j in list(itertools.combinations(a, 2)):
    ans.append(i * j)
ans.sort()
print(ans[k - 1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = np.array(A[:n], dtype = np.int64)
Positive = np.array(A[p:], dtype = np.int64)

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
    # print (x, tmp)
    return tmp

def Ncount1(x):
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - np.searchsorted(Positive, (-x - 1) // (-a), side = 'right') 
    return tmp 

def Pcount(x): #x以下の数を数える(x > 0)
    tmp = 0
    for index, a in enumerate(Positive):
        tmp += bisect_right(Positive[index + 1:], x // a)
    for index, b in enumerate(Negative):
        tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
        # print (bisect_right(Negative[index + 1:], x / b))
    # print (x, tmp)
    return tmp

def Pcount1(x):
    tmp = 0
    tmp += np.searchsorted(Positive, x // Positive, side = 'right').sum()
    tmp += (len(Negative) - np.searchsorted(Negative, (-x - 1) // (-Negative), side = 'rigth')).sum()
    tmp -= np.count_nonzero(Positive * Positive <= x)
    tmp -= np.count_nonzero(Negative * Negative <= x)
    return tmp // 2

if Number_Negative >= K:
    # ここに二分探索を書く
    l = -10 ** 18
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount1(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = 10 ** 18
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount1(mid):
            r = mid
        else:
            l = mid

    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)

Submission status: Time Limit Exceeded

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

p = []
for i in range(n):
  for j in range(i+1, n):
    p.append(a[i]*a[j])
    
p.sort()
print(p[k-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = np.array(A[:n], dtype = np.int64)
Positive = np.array(A[p:], dtype = np.int64)

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
    # print (x, tmp)
    return tmp

def Ncount1(x):
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - np.searchsorted(Positive, (-x - 1) // (-a), side = 'right') 
    return tmp 

def Pcount(x): #x以下の数を数える(x > 0)
    tmp = 0
    for index, a in enumerate(Positive):
        tmp += bisect_right(Positive[index + 1:], x // a)
    for index, b in enumerate(Negative):
        tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
        # print (bisect_right(Negative[index + 1:], x / b))
    # print (x, tmp)
    return tmp

def Pcount1(x):
    tmp = 0
    for p in Positive:
        tmp += np.searchsorted(Positive, x // p, side = 'right')
        if p ** 2 <= x:
            tmp -= 1
    for n in Negative:
        tmp += len(Negative) - np.searchsorted(Negative, (-x - 1) // (-n), side = 'rigth')
        if n ** 2 <= x:
            tmp -= 1
    # print (x, tmp)
    return tmp // 2

if Number_Negative >= K:
    # ここに二分探索を書く
    l = -10 ** 18
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount1(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = 10 ** 18
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount1(mid):
            r = mid
        else:
            l = mid

    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = np.array(A[:n], dtype = np.int64)
Positive = np.array(A[p:], dtype = np.int64)

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
    # print (x, tmp)
    return tmp

def Ncount1(x):
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - np.searchsorted(Positive, (x + a + 1) // a) 
    return tmp

def Pcount(x): #x以下の数を数える(x > 0)
    tmp = 0
    for index, a in enumerate(Positive):
        tmp += bisect_right(Positive[index + 1:], x // a)
    for index, b in enumerate(Negative):
        tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
        # print (bisect_right(Negative[index + 1:], x / b))
    # print (x, tmp)
    return tmp

def Pcount1(x):
    tmp = 0
    for p in Positive:
        tmp += np.searchsorted(Positive, x // p, side = 'right')
        if p ** 2 <= x:
            tmp -= 1
    for n in Negative:
        tmp += len(Negative) - np.searchsorted(Negative, (x + n + 1) // n)
        if n ** 2 <= x:
            tmp -= 1
    # print (x, tmp)
    return tmp // 2

if Number_Negative >= K:
    # ここに二分探索を書く
    l = -10 ** 18
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount1(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = 10 ** 18
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount1(mid):
            r = mid
        else:
            l = mid

    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = np.array(A[:n], dtype = np.int64)
Positive = np.array(A[p:], dtype = np.int64)

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
    # print (x, tmp)
    return tmp

def Ncount1(x):
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - np.searchsorted(Positive, (x + a + 1) // a) 
    return tmp

def Pcount(x): #x以下の数を数える(x > 0)
    tmp = 0
    for index, a in enumerate(Positive):
        tmp += bisect_right(Positive[index + 1:], x // a)
    for index, b in enumerate(Negative):
        tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
        # print (bisect_right(Negative[index + 1:], x / b))
    # print (x, tmp)
    return tmp

if Number_Negative >= K:
    # ここに二分探索を書く
    l = -10 ** 18
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount1(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = 10 ** 18
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount(mid):
            r = mid
        else:
            l = mid

    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)

Submission status: Time Limit Exceeded

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

ans = [0 for i in range(((n*(n-1))//2))]

idx = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans[idx] = a[i] * a[j]
        idx += 1

ans.sort()
print(ans[k-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left, bisect_right

    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()

    n = bisect_left(A, 0)
    p = bisect_right(A, 0)

    Negative = A[:n]
    Positive = A[p:]

    Number_Negative = len(Negative) * len(Positive)
    Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
    Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

    # print (Number_Negative)
    # print (Negative)
    # print (Number_Positive)
    # print (Positive)
    # print (Number_Zero)

    def Ncount(x): #x以下の数を数える(x < 0)
        tmp = 0
        for a in Negative:
            tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
        # print (x, tmp)
        return tmp

    def Pcount(x): #x以下の数を数える(x > 0)
        tmp = 0
        for p in Positive:
            tmp += bisect_right(Positive, x // p)
            if p ** 2 <= x:
                tmp -= 1
        # print (tmp)
        for n in Negative:
            tmp += len(Negative) - bisect_left(Negative, (x + n + 1) // n)
            if n ** 2 <= x:
                tmp -= 1
        # print (x, tmp)
        return tmp // 2

    if Number_Negative >= K:
        # ここに二分探索を書く
        l = -10 ** 18
        r = 0
        while r - l > 1:
            mid = (l + r) // 2
            if K <= Ncount(mid):
                r = mid
            else:
                l = mid
        print (r)
        exit()
            

    elif Number_Negative < K <= Number_Negative + Number_Zero:
        print (0)
        exit()

    else:
        # ここに二分探索を書く
        l = 0
        r = 10 ** 18
        K -= (Number_Negative + Number_Zero)
        while r - l > 1:
            mid = (l + r) // 2
            if K <= Pcount(mid):
                r = mid
            else:
                l = mid

        print (r)
        exit()

    # print (Pcount(l) + Number_Negative + Number_Zero)
    # print (Pcount(r) + Number_Negative + Number_Zero)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))

A.sort()
L=len(A)

def chk(x):
    cnt=0
    d=0
    for i in range(L):
        A1=A[i]
        if A1>=0:
            for j in range(L):
                if A1*A[j]<x:
                    cnt+=1
                    if j == i:
                        d += 1
                else:

                    break
        else:
            for j in range(L-1,-1,-1):
                if A1*A[j]<x:
                    cnt+=1
                    if j == i:
                        d += 1
                else:
                    break
    temp=(cnt-d)//2
    if temp<K:
        return True
    else:
        return False

l=-10**18-1
r=10**18+1

while l+1<r:
    mid=(r+l)//2
    if chk(mid):
        l=mid
    else:
        r=mid

print(l)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = A[:n]
Positive = A[p:]

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
    # print (x, tmp)
    return tmp

# def Pcount(x): #x以下の数を数える(x > 0)
#     tmp = 0
#     for index, a in enumerate(Positive):
#         tmp += bisect_right(Positive[index + 1:], x // a)
#     for index, b in enumerate(Negative):
#         tmp += len(Negative) - (index + 1) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
#         # print (bisect_right(Negative[index + 1:], x / b))
#     # print (x, tmp)
#     return tmp

def Pcount(x):
    tmp = 0
    for p in Positive:
        tmp += bisect_right(Positive, x // p)
        if p ** 2 <= x:
            tmp -= 1
    # print (tmp)
    for n in Negative:
        tmp += len(Negative) - bisect_left(Negative, (x + n + 1) // n)
        if n ** 2 <= x:
            tmp -= 1
    # print (x, tmp)
    return tmp // 2

if Number_Negative >= K:
    # ここに二分探索を書く
    l = -10 ** 18
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = 10 ** 18
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount(mid):
            r = mid
        else:
            l = mid

    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = A[:n]
Positive = A[p:]

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
    # print (x, tmp)
    return tmp

def Pcount(x): #x以下の数を数える(x > 0)
    tmp = 0
    for index, a in enumerate(Positive):
        tmp += bisect_right(Positive[index + 1:], x // a)
    for index, b in enumerate(Negative):
        tmp += len(Negative) - (index + 1) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
        # print (bisect_right(Negative[index + 1:], x / b))
    # print (x, tmp)
    return tmp

# def Pcount(x):
#     tmp = 0
#     for p in Positive:
#         tmp += bisect_right(Positive, x // p)
#     for n in Negative:
#         tmp += len(Negative) - bisect_left(Negative, (x + n + 1) // n)
#     print (x, tmp)
#     return tmp // 2

if Number_Negative >= K:
    # ここに二分探索を書く
    l = -10 ** 18
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = 10 ** 18
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount(mid):
            r = mid
        else:
            l = mid

    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

n = bisect_left(A, 0)
p = bisect_right(A, 0)

Negative = A[:n]
Positive = A[p:]

Number_Negative = len(Negative) * len(Positive)
Number_Positive = len(Negative) * (len(Negative) - 1) // 2 + len(Positive) * (len(Positive) - 1) // 2
Number_Zero = N * (N - 1) // 2 - Number_Negative - Number_Positive

# print (Number_Negative)
# print (Negative)
# print (Number_Positive)
# print (Positive)
# print (Number_Zero)

def Ncount(x): #x以下の数を数える(x < 0)
    tmp = 0
    for a in Negative:
        tmp += len(Positive) - bisect_left(Positive, (x + a + 1) // a)
    # print (x, tmp)
    return tmp

def Pcount(x): #x以下の数を数える(x > 0)
    tmp = 0
    for index, a in enumerate(Positive):
        tmp += bisect_right(Positive[index + 1:], x // a)
    for index, b in enumerate(Negative):
        tmp += len(Negative[index + 1:]) - bisect_left(Negative[index + 1:], (x + b + 1) // b)
        # print (bisect_right(Negative[index + 1:], x / b))
    # print (x, tmp)
    return tmp

if Number_Negative >= K:
    # ここに二分探索を書く
    l = -10 ** 18
    r = 0
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Ncount(mid):
            r = mid
        else:
            l = mid
    print (r)
    exit()
        

elif Number_Negative < K <= Number_Negative + Number_Zero:
    print (0)
    exit()

else:
    # ここに二分探索を書く
    l = 0
    r = 10 ** 18
    K -= (Number_Negative + Number_Zero)
    while r - l > 1:
        mid = (l + r) // 2
        if K <= Pcount(mid):
            r = mid
        else:
            l = mid

    print (r)
    # exit()

# print (Pcount(l) + Number_Negative + Number_Zero)
# print (Pcount(r) + Number_Negative + Number_Zero)

Submission status: Time Limit Exceeded

Solution code:
(n,k) = input().split()
k = int(k)
alist = [int(x) for x in input().split()]
alist.sort()

ans = 0
minus = 0
zero = 0
plus = 0

for a in alist:
  if a < 0:
    minus += 1
  elif a == 0:
    zero += 1
  else:
    plus += 1

mp = int(minus*(minus-1)/2 + plus*(plus-1)/2)   # 正の数
mz = int(zero*(zero-1)/2 + zero*(plus+minus))   # 0の数
mm = minus*plus                                 # 負の数

# 正解が0の場合
if mm < k <= mm + mz:
    ans = 0
else:
    INF = int(10e+18) + 2
    l = -INF
    r = INF
    x = 0
    c = 0

    # 正解が負の場合
    if k <= mm:
        r = 0
        mlist = alist[:minus]
        plist = alist[:minus+zero-1:-1]
        while l+1 < r:
            x = int((l+r)//2)
            c = 0
            # 負×正
            for a1 in mlist:
                for a2 in plist:
                    if a1 * a2 < x:
                        c += 1
                    else:
                        break
            if c < k:
                l = x
            else:
                r = x
    # 正解が正の場合
    else:
        l = 0
        k -= mm + mz
        mlist = alist[minus-1::-1]
        plist = alist[minus+zero:]
        while l+1 < r:
            x = int((l+r)//2)
            c = 0
            i = 0
            # 負×負
            for a1 in mlist:
                j = 0
                for a2 in mlist:
                    if a1 * a2 < x:
                        if i != j:  # 自分自身は数えない
                            c += 1
                    else:
                        break
                    j += 1
                i += 1
            i = 0
            # 正×正
            for a1 in plist:
                j = 0
                for a2 in plist:
                    if a1 * a2 < x:
                        if i != j:  # 自分自身は数えない
                            c += 1
                    else:
                        break
                    j += 1
                i += 1
            # 2で割る(2回数えるので)
            c = int(c/2)
            if c < k:
                l = x
            else:
                r = x
    ans = l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
(n,k) = input().split()
k = int(k)
alist = [int(x) for x in input().split()]
alist.sort()

ans = 0
minus = 0
zero = 0
plus = 0

for a in alist:
  if a < 0:
    minus += 1
  elif a == 0:
    zero += 1
  else:
    plus += 1

mp = int(minus*(minus-1)/2 + plus*(plus-1)/2)   # 正の数
mz = int(zero*(zero-1)/2 + zero*(plus+minus))   # 0の数
mm = minus*plus                                 # 負の数

# 正解が0の場合
if mm < k <= mm + mz:
    ans = 0
else:
    INF = int(10e+18) + 2
    l = -INF
    r = INF
    x = 0
    c = 0

    # 正解が負の場合
    if k <= mm:
        r = 0
        while l+1 < r:
            x = int((l+r)//2)
            c = 0
            # 負×正
            for a1 in alist[:minus]:
                for a2 in alist[:minus+zero-1:-1]:
                    if a1 * a2 < x:
                        c += 1
                    else:
                        break
            if c < k:
                l = x
            else:
                r = x
    # 正解が正の場合
    else:
        l = 0
        k -= mm + mz
        while l+1 < r:
            x = int((l+r)//2)
            c = 0
            i = 0
            # 負×負
            for a1 in alist[minus-1::-1]:
                j = 0
                for a2 in alist[minus-1::-1]:
                    if a1 * a2 < x:
                        if i != j:  # 自分自身は数えない
                            c += 1
                    else:
                        break
                    j += 1
                i += 1
            i = 0
            # 正×正
            for a1 in alist[minus+zero:]:
                j = 0
                for a2 in alist[minus+zero:]:
                    if a1 * a2 < x:
                        if i != j:  # 自分自身は数えない
                            c += 1
                    else:
                        break
                    j += 1
                i += 1
            # 2で割る(2回数えるので)
            c = int(c/2)
            if c < k:
                l = x
            else:
                r = x
    ans = l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N,K=map(int,input().split())
A=list(map(int,input().split()))

A.sort()

def chk(x):
    cnt=0
    d=0
    for i in range(len(A)):
        A1=A[i]
        if A1>=0:
            l =- 1
            r = len(A)
            while l+1<r:
                mid=(l+r)//2
                if A[mid]*A1<x:
                    l=mid
                else:
                    r=mid
            cnt+=r
            if i<r:d+=1
        else:
            l = -1
            r = len(A)
            while l+1<r:
                mid=(l+r)//2
                if A[mid]*A1<x:
                    r=mid
                else:
                    l=mid
            cnt+=len(A)-r
            if i>r:d+=1
    cnt=(cnt-d)//2
    if cnt<K:
        return True
    else:
        return False

l=-10**18-1
r=10**18+1

while l+1<r:
    mid=(r+l)//2
    if chk(mid):
        l=mid
    else:
        r=mid

print(l)