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: Runtime Error

Solution code:
import bisect
N,K = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
An.sort()
idx = bisect.bisect_left(An,0)
positive = An[idx:] 
negative = An[:idx]


max_candidate = 10**18 + 1
min_candidate = -1 * (10**18) - 1

while True:
    middle = (max_candidate + min_candidate)//2
    if 0 <= middle:
        current_length = len(positive) * len(negative)
        candidate_list = []
        #正 * 正
        for i,n1 in enumerate(positive):
            n2_list = positive[i+1:]
            if n1 != 0:
                n2_candidate = middle / n1
                n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            else:
                n2_idx = len(n2_list)
            current_length += n2_idx
            if 0 < n2_idx:
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
        #負 * 負
        for i,n1 in enumerate(negative):
            n2_list = negative[i+1:]
            n2_candidate = middle / n1
            n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            if n2_idx < len(n2_list):
                current_length += len(n2_list) - n2_idx - 1
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
    else:
        current_length = 0
        candidate_list = []
        #正 * 負
        for i,n1 in enumerate(negative): 
            n2_list = positive
            n2_candidate = middle / n1
            n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            #current_length += n2_idx
            if n2_idx < len(n2_list):
                current_length += len(n2_list) - n2_idx
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
    if min_candidate+1 == max_candidate:
        break
    if current_length == K:
        print(max(candidate_list))
        exit(0)
    elif current_length < K:
        min_candidate = middle
    else:
        max_candidate = middle
print(max(candidate_list))

Submission status: Runtime Error

Solution code:
import bisect
N,K = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
An.sort()
idx = bisect.bisect_left(An,0)
positive = An[idx:] 
negative = An[:idx]


max_candidate = 101 #10**18 + 1
min_candidate = -100 #-1 * (10**18) - 1

while True:
    middle = (max_candidate + min_candidate)//2
    if 0 <= middle:
        current_length = len(positive) * len(negative)
        candidate_list = []
        #正 * 正
        for i,n1 in enumerate(positive):
            n2_list = positive[i+1:]
            if n1 != 0:
                n2_candidate = middle / n1
                n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            else:
                n2_idx = len(n2_list)
            current_length += n2_idx
            if 0 < n2_idx:
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
        #負 * 負
        for i,n1 in enumerate(negative):
            n2_list = negative[i+1:]
            n2_candidate = middle / n1
            n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            if n2_idx < len(n2_list):
                current_length += len(n2_list) - n2_idx - 1
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
    else:
        current_length = 0
        candidate_list = []
        #正 * 負
        for i,n1 in enumerate(negative): 
            n2_list = positive
            n2_candidate = middle / n1
            n2_idx = bisect.bisect_right(n2_list,n2_candidate)
            #current_length += n2_idx
            if n2_idx < len(n2_list):
                current_length += len(n2_list) - n2_idx
                n2 = n2_list[n2_idx-1]
                candidate_list.append(n1 * n2)
    if min_candidate+1 == max_candidate:
        break
    if current_length == K:
        print(max(candidate_list))
        exit(0)
    elif current_length < K:
        min_candidate = middle
    else:
        max_candidate = middle
print(max(candidate_list))

Submission status: Runtime Error

Solution code:
import math
import sys
import bisect

def bisectf_left(f,val,start,end):
    fs = f(start)
    if val <= fs:
        return start
    fe = f(end-1)
    if fe < val:
        return end    
    # Now fs < val and val <= fe

    while True:
        if (end - start) <= 2:
            return end - 1
        mid = (start + end )// 2 
        fm = f(mid)
        if val <= fm :
            end = mid + 1
        else: 
            start = mid
        continue

def bisectf_right(f,val,start,end):
    if start == end:
        return start 
    fs = f(start)
    if val < fs:
        return start
    fe = f(end-1)
    if fe <= val:
        return end
    # Now fs <= val and val < fe 
    while True:
        # print(start,end)
        if (end - start) <= 2:
            return end - 1
        mid = (start + end )// 2 
        fm = f(mid)
        if fm > val:
            end = mid + 1
        else:
            start = mid
        continue

def bisectf_bool(f,start,end):
    if start == end:
        return start 
    fs = f(start)
    if fs == True:
        return start
    fe = f(end-1)
    if fe == False:
        return end
    # Now fs == False and  fe == True 
    while True:
        # print(start,end)
        if (end - start) <= 2:
            return end - 1
        mid = (start + end )// 2 
        fm = f(mid)
        if fm == True:
            end = mid + 1
        else:    
            start = mid
        continue

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

pm = bisect.bisect_left(A,0)
pz = bisect.bisect_right(A,0)
# print(pm,pz)

minus = list(map(lambda x: -x,A[0:pm]))
minus.sort()
plus = A[pz:]

numminus = pm 
numzero = pz - pm 
numplus = len(A) - pz 

# print(numzero,minus,plus)


def larger(ii):
    global basenum
    # global limit
    return limit < basenum * A[ii] 

def smaller_or_equal(ii):
    global basenum
    global limit
    return limit >= basenum * A[ii] 

limit = 0 

def count(u):
    # Count combination whose muliply is less than equal x 
    global limit
    global basenum
    ans = 0
    # print("count",u)
    for i in range(0,len(A)):
        # print("count",u,i)
        global basenum    
        if A[i] < 0:
            limit = u
            basenum = A[i]
            x = bisectf_bool(smaller_or_equal,0,i)
            #for j in range(x,i):
            #    print(x)
            #    print(A[i],"*",A[j])
            ans = ans + i - x 
        elif A[i] == 0:
            if x>= 0:
                ans = ans + i
        else:
            # global limit
            limit = u
            # print("set limit",limit,i)
            basenum = A[i]
            x = bisectf_bool(larger,0,i)
            #for j in range(0,x):
            #    print(A[i],"*",A[j])
            # print("basenum",basenum,x,i-x)
            ans = ans + x
    return ans

def fl(x):
    global kk
    return count(x) >= kk

kk = K

#for i in range(-13,11):
#    print(i,count(i))
hoge = bisectf_bool(fl,-10**18,10**18)
print(hoge)

Submission status: Runtime Error

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

ans = [0] * ((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: Runtime Error

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

ans = [0] * int((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: Runtime Error

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 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 = Negative[0] * Positive[-1]
    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 = max(Negative[0] ** 2, Positive[-1] ** 2)
    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: Runtime Error

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 = Negative[0] * Positive[-1]
        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 = max(Negative[0] ** 2, Positive[-1] ** 2)
        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: Runtime Error

Solution code:
(n,k) = input().split()
k = int(k)
alist.sort()

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

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

mp = minus*(minus-1)//2 + plus*(plus-1)//2   # 正の数
mz = 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 = (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 = c//2
            if c < k:
                l = x
            else:
                r = x
    ans = l

print(ans)

Submission status: Runtime Error

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:
    aaa
    # ここに二分探索を書く
    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: Runtime Error

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
    aaa
    print (r)
    # exit()

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

Submission status: Runtime Error

Solution code:
# 二分木
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

Submission status: Runtime Error

Solution code:
import numpy as np

n, k = [int(m) for m in input().split()]
a = [int(m) for m in input().split()]

x = np.array(a, dtype='i8')
y = x.reshape(-1,1)
z = np.triu(x*y, k=1)

l = np.zeros(0, dtype='i8')
for i in range(n-1):
    l = np.append(l, np.diag(z, k=i+1))
m = np.sort(l)
print(m[k-1])

Submission status: Runtime Error

Solution code:
import numpy as np

# ---

n, k = [int(m) for m in input().split()]
a = [int(m) for m in input().split()]

x = np.array(a, dtype=np.int64)
y = x.reshape(-1,1)
z = np.triu(x*y, k=1)

l = np.zeros(0, dtype=np.int64)
for i in range(int(n)-1):
    l = np.append(l, np.diag(z, k=i+1))
m = np.sort(l)
print(m[k-1])

Submission status: Runtime Error

Solution code:
import numpy as np

# ---

n, k = [int(m) for m in input().split()]
a = [int(m) for m in input().split()]

x = np.array(a, dtype=np.int64)
y = x.reshape(-1,1)

z = np.triu(x*y, k=1)

#print(z)
l = np.zeros(0, dtype=np.int64)
for i in range(int(n)-1):
    #print(np.diag(z, k=i+1))
    l = np.append(l, np.diag(z, k=i+1))
m = np.sort(l)
print(int(m[k-1]))

Submission status: Runtime Error

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

plus, zero, minus = [], 0, []
for i in a:
    if i > 0:
        plus.append(i)
    elif i == 0:
        zero += 1
    else:
        minus.append(i)
plus.sort()
minus.sort()
plus_reverse = plus[::-1]
minus_reverse = minus[::-1]

n_plus = len(plus) * (len(plus)-1) // 2 + len(minus) * (len(minus)-1) // 2
n_zero = zero * (n-zero) + zero * (zero-1) // 2
n_minus = len(plus) * len(minus)

if k <= n_minus:
    left = -10**18 # 答えじゃない
    right = -1 # 答え
    while right - left > 1:
        mid = (left + right) // 2
        l = 0
        cnt = 0
        for i in range(n_plus):
            if l == len(minus):
                cnt += l
                continue
            while l < len(minus) and plus[i]*minus[l] <= mid:
                l += 1
                if l == len(minus): break
            cnt += l
        if cnt >= k:
            right = mid
        else:
            left = mid
    print(right)

elif k <= n_minus + n_zero:
    print(0)

else:
    k -= n_minus + n_zero
    left = 1
    right = 10**18
    while right - left > 1:
        mid = (left + right) // 2
        cnt = 0
        # plus
        l, r = 0, len(plus)-1
        while l < r:
            while l < r and plus[l] * plus[r] > mid:
                r -= 1
            cnt += r - l
            l += 1
        # minus
        l, r = 0, len(minus_reverse)-1
        while l < r:
            while l < r and minus_reverse[l] * minus_reverse[r] > mid:
                r -= 1
            cnt += r - l
            l += 1
        if cnt >= k:
            right = mid
        else:
            left = mid
    print(right)

Submission status: Runtime Error

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

plus, zero, minus = [], 0, []
for i in a:
    if i > 0:
        plus.append(i)
    elif i == 0:
        zero += 1
    else:
        minus.append(i)
plus.sort()
minus.sort()
plus_reverse = plus[::-1]
minus_reverse = minus[::-1]

n_plus = len(plus) * (len(plus)-1) // 2 + len(minus) * (len(minus)-1) // 2
n_zero = zero * (n-zero) + zero * (zero-1) // 2
n_minus = len(plus) * len(minus)

if k <= n_minus:
    left = -10**18 # 答えじゃない
    right = -1 # 答え
    while right - left > 1:
        mid = (left + right) // 2
        l = 0
        cnt = 0
        for i in range(n_plus):
            if l == len(minus):
                cnt += l
                break
            while l < len(minus) and plus[i]*minus[l] <= mid:
                l += 1
                if l == len(minus): break
            cnt += l
        if cnt >= k:
            right = mid
        else:
            left = mid
    print(right)

elif k <= n_minus + n_zero:
    print(0)

else:
    k -= n_minus + n_zero
    left = 1
    right = 10**18
    while right - left > 1:
        mid = (left + right) // 2
        cnt = 0
        # plus
        l, r = 0, len(plus)-1
        while l < r:
            while l < r and plus[l] * plus[r] > mid:
                r -= 1
            cnt += r - l
            l += 1
        # minus
        l, r = 0, len(minus_reverse)-1
        while l < r:
            while l < r and minus_reverse[l] * minus_reverse[r] > mid:
                r -= 1
            cnt += r - l
            l += 1
        if cnt >= k:
            right = mid
        else:
            left = mid
    print(right)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# TLEする

def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    a_list.append(0)
    a_list = sorted(a_list)
    m_num = p_num = 0
    m_idx = p_idx = -1

    z_num = a_list.count(0) - 1
    z_idx = a_list.index(0)
    m_num = z_idx
    p_num = n - (z_num + m_num)
    if m_num != 0: m_idx = 0
    if p_num != 0: p_idx = z_idx + z_num
    del(a_list[z_idx])
    if z_num == 0: z_idx = -1

    k_p_num = int((m_num * (m_num - 1) + p_num * (p_num - 1)) / 2)
    # k_z_num = z_num * (n - z_num) + (z_num * (z_num - 1)) / 2
    k_z_num = int(z_num * ((n - z_num) + (z_num - 1) / 2))
    k_m_num = m_num * p_num

    if k < k_m_num:
        ans_kind = 'minus'
        ans_idx = k - 1
    elif k < k_m_num + k_z_num:
        ans_kind = 'zero'
        ans_idx = k - k_m_num - 1
    else:
        ans_kind = 'plus'
        ans_idx = k - (k_m_num + k_z_num) - 1

    # print("{}\nm_idx:{}, z_idx:{}, p_idx:{}".format(a_list, m_idx, z_idx, p_idx))
    # print("k_m_num:{}, k_z_num:{}, k_p_num:{}".format(k_m_num, k_z_num, k_p_num))
    # print("k:{}, ans_kind:{}, ans_idx:{}".format(k, ans_kind, ans_idx))

    if ans_kind == 'zero':
        ans = 0
    elif ans_kind == 'minus':
        k_list = list()
        for i in a_list[m_idx:m_num]:
            for j in a_list[p_idx:n]:
                k_list.append(i*j)
        
        ans = sorted(k_list)[ans_idx]
    else:
        k_list = list()
        if m_num != 0:
            for i in range(m_num):
                for j in range(i+1, m_num):
                    k_list.append(a_list[i]*a_list[j])
        if p_num != 0:
            for i in range(p_num):
                for j in range(i+1, p_num):
                    k_list.append(a_list[p_idx + i]*a_list[p_idx + j])

        ans = sorted(k_list)[ans_idx]

    # print("k_list_length:{}".format(len(k_list)))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

A.sort()

iplus = bisect.bisect_right(A,0)
izeros = bisect.bisect_left(A,0)

pluss = A[iplus:]
zeros = A[izeros:iplus]
minuss = A[:izeros]

nplus = len(pluss)
nzero = len(zeros)
nminus = len(minuss)

npminus = nplus * nminus
npzeros = nzero * (nplus + nminus) + nzero * (nzero-1)//2

if npminus < K <= npminus + npzeros:
    print(0)
elif K <= npminus:
    mn = minuss[0] * pluss[-1] - 1
    mx = minuss[-1] * pluss[0]
    while mx-mn > 1:
        mid = (mn+mx)//2
        cnt = 0
        for m in minuss:
            x = -(-mid//m)
            k = bisect.bisect_left(pluss,x)
            #print(m,x,pluss,k)
            cnt += (nplus-k)
            if cnt >= K:
                break
        if cnt >= K:
            mx = mid
        else:
            mn = mid
    print(mx)
else:
    K -= npminus + npzeros
    pluss2 = [-m for m in minuss][::-1]
    mn = pluss[0] * pluss[1] - 1
    mx = pluss[-1] * pluss[-2]
    if len(pluss2) > 1:
        mn = min(mn, pluss2[0] * pluss2[1] - 1)
        mx = max(mx, pluss2[-1] * pluss2[-2])

    while mx-mn > 1:
        mid = (mn+mx)//2
        cnt = 0
        for m in pluss:
            x = mid//m
            k = bisect.bisect_right(pluss,x)
            cnt += k - (m**2 <= mid)
        for m in pluss2:
            x = mid//m
            k = bisect.bisect_left(pluss2,x)
            cnt += k - (m**2 <= mid)
        cnt = cnt //2
        #print(mn,mid,mx,cnt)
        if cnt >= K:
            mx = mid
        else:
            mn = mid
    print(mx)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import math

def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    a_list.append(0)
    a_list = sorted(a_list)
    m_num = p_num = 0
    m_idx = p_idx = -1

    z_num = a_list.count(0) - 1
    z_idx = a_list.index(0)
    m_num = z_idx
    p_num = n - (z_num + m_num)
    if m_num != 0: m_idx = 0
    if p_num != 0: p_idx = z_idx + z_num
    del(a_list[z_idx])
    if z_num == 0: z_idx = -1

    k_p_num = int((m_num * (m_num - 1) + p_num * (p_num - 1)) / 2)
    # k_z_num = z_num * (n - z_num) + (z_num * (z_num - 1)) / 2
    k_z_num = int(z_num * ((n - z_num) + (z_num - 1) / 2))
    k_m_num = m_num * p_num

    if k < k_m_num:
        ans_kind = 'minus'
        ans_idx = k
    elif k < k_m_num + k_z_num:
        ans_kind = 'zero'
        ans_idx = k - k_m_num
    else:
        ans_kind = 'plus'
        ans_idx = k - (k_m_num + k_z_num)

    # print("{}\nm_idx:{}, z_idx:{}, p_idx:{}".format(a_list, m_idx, z_idx, p_idx))
    # print("k_m_num:{}, k_z_num:{}, k_p_num:{}".format(k_m_num, k_z_num, k_p_num))
    # print("k:{}, ans_kind:{}, ans_idx:{}".format(k, ans_kind, ans_idx))

    if ans_kind == 'zero':
        ans = 0
    elif ans_kind == 'minus':
        k_list = list()
        for i in a_list[m_idx:m_num]:
            for j in a_list[p_idx:n]:
                k_list.append(i*j)
        
        ans = sorted(k_list)[ans_idx]
    else:
        k_list = list()
        if m_num != 0:
            for i in range(m_num):
                for j in range(i+1, m_num):
                    k_list.append(a_list[i]*a_list[j])
        if p_num != 0:
            for i in range(p_num):
                for j in range(i+1, p_num):
                    k_list.append(a_list[p_idx + i]*a_list[p_idx + j])

        ans = sorted(k_list)[ans_idx-1]

    # print("k_list_length:{}".format(len(k_list)))
    print(ans)

if __name__ == "__main__":
    main()