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:
from heapq import heappush,heappop
N,K=map(int,input().split())
A=list(map(int,input().split()))

Am = []
A0 = []
Ap = []
for i in A:
    if i<0:
        Am.append(i)
    elif i ==0:
        A0.append(i)
    else:
        Ap.append(i)
        
D=[]
# -*+の方が小さい
if len(Am)*len(Ap)>=K:
    Am.sort()
    Ap.sort(reverse=True)
    hq = []
    arg_hash = {}
    val = Am[0]*Ap[0]
    heappush(hq,(val,0,0))
    
    ans=0
    for i in range(K):
        ans,m,p = heappop(hq)
        arg_m = (m+1,p)
        arg_p = (m,p+1)
        if m<len(Am)-1 and arg_m not in arg_hash:
            arg_hash[arg_p]=1
            heappush(hq,(Am[m+1]*Ap[p],)+arg_m)
        if p<len(Ap)-1 and arg_p not in arg_hash:
            arg_hash[arg_p]=1
            heappush(hq,(Am[m]*Ap[p+1],)+arg_p)
    print(ans)
elif len(Am)*len(Ap)<K<=len(Am)*len(Ap)+len(A0)*(len(Am)+len(Ap))+len(A0)*(len(A0)-1)//2:
    print(0)
else:
    l=K-len(Am)*len(Ap)-len(A0)*(len(Am)+len(Ap))-len(A0)*(len(A0)-1)//2
    Am.sort(reverse=True)
    Ap.sort()
    for p in range(1,len(Am)+1):
        for q in range(p+1,len(Am)+1):
            if p*q//2<=l:
                D.append(Am[p-1]*Am[q-1])
    for p in range(1,len(Ap)+1):
        for q in range(p+1,len(Ap)+1):
            if p*q//2<=l:
                D.append(Ap[p-1]*Ap[q-1])
    D.sort()
    print(D[l-1])from heapq import heappush,heappop
N,K=map(int,input().split())
A=list(map(int,input().split()))

Am = []
A0 = []
Ap = []
for i in A:
    if i<0:
        Am.append(i)
    elif i ==0:
        A0.append(i)
    else:
        Ap.append(i)
        
D=[]
# -*+の方が小さい
if len(Am)*len(Ap)>=K:
    Am.sort()
    Ap.sort(reverse=True)
    hq = []
    arg_hash = {}
    val = Am[0]*Ap[0]
    heappush(hq,(val,0,0))
    
    ans=0
    for i in range(K):
        ans,m,p = heappop(hq)
        arg_m = (m+1,p)
        arg_p = (m,p+1)
        if m<len(Am)-1 and arg_m not in arg_hash:
            arg_hash[arg_p]=1
            heappush(hq,(Am[m+1]*Ap[p],)+arg_m)
        if p<len(Ap)-1 and arg_p not in arg_hash:
            arg_hash[arg_p]=1
            heappush(hq,(Am[m]*Ap[p+1],)+arg_p)
    print(ans)
elif len(Am)*len(Ap)<K<=len(Am)*len(Ap)+len(A0)*(len(Am)+len(Ap))+len(A0)*(len(A0)-1)//2:
    print(0)
else:
    l=K-len(Am)*len(Ap)-len(A0)*(len(Am)+len(Ap))-len(A0)*(len(A0)-1)//2
    Am.sort(reverse=True)
    Ap.sort()
    for p in range(1,len(Am)+1):
        for q in range(p+1,len(Am)+1):
            if p*q//2<=l:
                D.append(Am[p-1]*Am[q-1])
    for p in range(1,len(Ap)+1):
        for q in range(p+1,len(Ap)+1):
            if p*q//2<=l:
                D.append(Ap[p-1]*Ap[q-1])
    D.sort()
    print(D[l-1])

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop
N,K=map(int,input().split())
A=list(map(int,input().split()))

Am = []
A0 = []
Ap = []
for i in A:
    if i<0:
        Am.append(i)
    elif i ==0:
        A0.append(i)
    else:
        Ap.append(i)
        
D=[]
# -*+の方が小さい
if len(Am)*len(Ap)>=K:
    Am.sort()
    Ap.sort(reverse=True)
    hq = []
    arg_hash = {}
    val = Am[0]*Ap[0]
    heappush(hq,(val,0,0))
    
    for i in range(K):
        ans,m,p = heappop(hq)
        arg_m = (m+1,p)
        arg_p = (m,p+1)
        if m<len(Am)-1 and arg_m not in arg_hash:
            arg_hash[arg_p]=1
            heappush(hq,(Am[m+1]*Ap[p],)+arg_m)
        if p<len(Ap)-1 and arg_p not in arg_hash:
            arg_hash[arg_p]=1
            heappush(hq,(Am[m]*Ap[p+1],)+arg_p)
    print(ans)
elif len(Am)*len(Ap)<K<=len(Am)*len(Ap)+len(A0)*(len(Am)+len(Ap))+len(A0)*(len(A0)-1)//2:
    print(0)
else:
    l=K-len(Am)*len(Ap)-len(A0)*(len(Am)+len(Ap))-len(A0)*(len(A0)-1)//2
    Am.sort(reverse=True)
    Ap.sort()
    for p in range(1,len(Am)+1):
        for q in range(p+1,len(Am)+1):
            if p*q//2<=l:
                D.append(Am[p-1]*Am[q-1])
    for p in range(1,len(Ap)+1):
        for q in range(p+1,len(Ap)+1):
            if p*q//2<=l:
                D.append(Ap[p-1]*Ap[q-1])
    D.sort()
    print(D[l-1])

Submission status: Runtime Error

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

a_m=[]
a_p=[]

for aa in a:
    if aa<0:
        a_m.append(aa)
    else:
        a_p.append(aa)

len_m=len(a_m)*len(a_p)
len_p=len(a_m)*len(a_m)+len(a_p)*len(a_p)

#kがマイナスエリア
if k<len_m:
    #kがより小さい
    if k<len_m//2:
        a_m.sort()
        a_p.sort(reverse=True)
        cnt=1
        i=0
        j=0
        while cnt<k:
            if a_p[i+1]*a_m[j]<a_p[i]*a_m[j+1]:
                i+=1
            else:
                j+=1
            cnt+=1
        print(a_p[i]*a_m[j])
        exit()

    else:
        a_m.sort(reverse=True)
        a_p.sort()
        cnt=len(a_m)*len(a_p)
        i=len(a_p)-1
        j=len(a_m)-1
        while cnt>k:
            if a_p[i-1]*a_m[j]<a_p[i]*a_m[j-1]:
                j-=1
            else:
                i-=1
            cnt-=1
        print(a_p[i]*a_m[j])
        exit()

else:
    aa_m=[]
    for index,item in enumerate(a_m):
        for item2 in a_m[index+1:]:
            aa_m.append(item*item2)
    aa_p=[]

    for index,item in enumerate(a_p):
        for item2 in a_p[index+1:]:
            aa_p.append(item*item2)
    aa_m.sort()
    aa_p.sort()
    #print(aa_p,aa_m)

    if len(aa_p)==0:
        print(aa_m[k-len_m-1])
        exit()
    if len(aa_m)==0:
        print(aa_p[k-len_m-1])
        exit()


    #kが0以上で小さい側
    if k<len_m+len_p//2:

        

        i=0
        j=0
        cnt=len_m+1
        while cnt<k:
            #print(i,j)
            if aa_m[i]<aa_p[j]:
                i+=1
            else:
                j+=1
            cnt+=1
        print(min(aa_m[i],aa_p[j]))

    else:
        aa_m.sort(reverse=True)
        aa_p.sort(reverse=True)

        i=len(aa_m)-1
        j=len(aa_p)-1
        cnt=len_m+len_p

        while cnt>k:
            if aa_m[i]<aa_p[j]:
                j-=1
            else:
                i-=1
            cnt-=1

        print(max(aa_m[i],aa_p[j]))

Submission status: Runtime Error

Solution code:
def main():
    from bisect import bisect_left, bisect_right
    import numpy as np
    n, k, *a = map(int, open(0).read().split())
    a = sorted(a)
    l, r = bisect_left(a, 0), bisect_right(a, 0)
    ng, zs, ps = l, r - l, n - r

    if ng * ps < k <= ng * ps + zs * (zs - 1):
        print(0)
        exit()
    if ng * ps >= k:
        x = 0
        c = 0
        while 1:
            p, q = a[x], a[x + 1]
            r, s = a[r], a[n - 1]
            ll = p * np.array(a[r - 1:])
            i = bisect_left(ll, s * q)
            if i == 0:
                if c + n - r < k:
                    c += n - r
                    x += 1
                else:
                    j = k - c
                    ans = ll[-j]
                    print(ans)
                    exit()
            else:
                if c + n - r + i < k:
                    c += n - r
                    x += 1
                else:
                    if k - c <= n - i:
                        ans = ll[k - c]
                        print(ans)
                        exit()
                    else:
                        vv = q * np.array(a[-i:])
                        ll = np.concatenate([ll, vv])
                        ll.sort()
                        ans = ll[k - c]
                        print(ans)
                        exit()

    else:
        print("hello")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from bisect import bisect_left, bisect_right
    import numpy as np
    n, k, *a = map(int, open(0).read().split())
    a = sorted(a)
    l, r = bisect_left(a, 0), bisect_right(a, 0)
    ng, zs, ps = l, r - l, n - r

    if ng * ps < k <= ng * ps + zs * (zs - 1):
        ans = 0
    if ng * ps >= k:
        x = 0
        c = 0
        while 1:
            p, q = a[x], a[x + 1]
            r, s = a[r], a[n - 1]
            ll = p * np.array(a[r - 1:])
            i = bisect_left(ll, s * q)
            if i == 0:
                if c + n - r < k:
                    c += n - r
                    x += 1
                else:
                    j = k - c
                    ans = ll[-j]
                    print(ans)
                    break
            else:
                if c + n - r + i < k:
                    c += n - r
                    x += 1
                else:
                    if k - c <= n - i:
                        ans = ll[k - c]
                        print(ans)
                        break
                    else:
                        vv = q * np.array(a[-i:])
                        ll = np.concatenate([ll, vv])
                        ll.sort()
                        ans = ll[k - c]
                        print(ans)
                        break

    else:
        print("hello")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from bisect import bisect_left, bisect_right
    import numpy as np
    n, k, *a = map(int, open(0).read().split())
    a = sorted(a)
    l, r = bisect_left(a, 0), bisect_right(a, 0)
    ng, zs, ps = l, r - l, n - r

    print(a)
    print(ng, zs, ps)

    if ng * ps < k <= ng * ps + zs * (zs - 1):
        ans = 0
    if ng * ps >= k:
        x = 0
        c = 0
        while 1:
            p, q = a[x], a[x + 1]
            r, s = a[r], a[n - 1]
            ll = p * np.array(a[r - 1:])
            i = bisect_left(ll, s * q)
            if i == 0:
                if c + n - r < k:
                    c += n - r
                    x += 1
                else:
                    j = k - c
                    ans = ll[-j]
                    print(ans)
                    break
            else:
                if c + n - r + i < k:
                    c += n - r
                    x += 1
                else:
                    if k - c <= n - i:
                        ans = ll[k - c]
                        print(ans)
                        break
                    else:
                        vv = q * np.array(a[-i:])
                        ll = np.concatenate([ll, vv])
                        ll.sort()
                        ans = ll[k - c]
                        print(ans)
                        break

    else:
        break


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

posi = 0
nega = 0
zero = 0
p = []
m = []

for i in range(n):
    if a[i] > 0:
        p.append(a[i])
        posi += 1
    elif a[i] < 0:
        nega += 1
        m.append(-a[i])
    else:
        zero += 1

p.sort()
m.sort()

if k <= posi*nega:
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)-1, -1, -1):
            count -= posi-bisect_left(m, (mid-1)//p[i]+1)
            if count <= 0:
                break
        if count <= 0:
            l = mid
        else:
            r = mid
        #print(r, l)

    print(-l)

elif k <= posi*nega+zero*(zero-1)//2+zero*(posi+nega):
    print(0)

else:
    o
    k -= posi*nega+zero*(zero-1)//2+zero*(posi+nega)
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)):
            count -= max(bisect_right(p, (mid)//p[i])-i-1, 0)
            if count < 0:
                #continue
                break
        for i in range(len(m)):
            count -= max(bisect_right(m, (mid)//m[i])-i-1, 0)
            if count < 0:
                #continue
                break

        if count > 0:
            l = mid
        else:
            r = mid
    print(r)

Submission status: Runtime Error

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

posi = 0
nega = 0
zero = 0
p = []
m = []

for i in range(n):
    if a[i] > 0:
        p.append(a[i])
        posi += 1
    elif a[i] < 0:
        nega += 1
        m.append(-a[i])
    else:
        zero += 1

p.sort()
m.sort()

if k <= posi*nega:
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)-1, -1, -1):
            count -= posi-bisect_left(m, (mid-1)//p[i]+1)
            if count <= 0:
                break
        if count <= 0:
            l = mid
        else:
            r = mid
        #print(r, l)

    print(-l)

elif k <= posi*nega+zero*(zero-1)//2+zero*(posi+nega):
    print(0)

else:
	print("aa")
    k -= posi*nega+zero*(zero-1)//2+zero*(posi+nega)
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)):
            count -= max(bisect_right(p, (mid)//p[i])-i-1, 0)
            if count < 0:
                #continue
                break
        for i in range(len(m)):
            count -= max(bisect_right(m, (mid)//m[i])-i-1, 0)
            if count < 0:
                #continue
                break

        if count > 0:
            l = mid
        else:
            r = mid
    print(r)

Submission status: Runtime Error

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

posi = 0
nega = 0
zero = 0
p = []
m = []

for i in range(n):
    if a[i] > 0:
        p.append(a[i])
        posi += 1
    elif a[i] < 0:
        nega += 1
        m.append(-a[i])
    else:
        zero += 1

p.sort()
m.sort()

if k <= posi*nega:
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)-1, -1, -1):
            count -= posi-bisect_left(m, (mid-1)//p[i]+1)
            if count <= 0:
                break
        if count <= 0:
            l = mid
        else:
            r = mid
        #print(r, l)

    print(-l)

elif k <= posi*nega+zero*(zero-1)//2+zero*(posi+nega):
    print(0)

else:
  	print("aa")
    k -= posi*nega+zero*(zero-1)//2+zero*(posi+nega)
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)):
            count -= max(bisect_right(p, (mid)//p[i])-i-1, 0)
            if count < 0:
                #continue
                break
        for i in range(len(m)):
            count -= max(bisect_right(m, (mid)//m[i])-i-1, 0)
            if count < 0:
                #continue
                break

        if count > 0:
            l = mid
        else:
            r = mid
    print(r)

Submission status: Runtime Error

Solution code:
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
negative_number_cnt = 0
positive_number_cnt = 0
negative_number = []
positive_number = []
zero_cnt = 0
a.sort()
def binary_search(left, right,positive):
    if right - left <= 1:
        return right
    middle = (right + left) // 2
    if is_can(middle,positive):
        return binary_search(left, middle,positive)
    else:
        return binary_search(middle, right,positive)
def is_can(x,positive):
    #xよりも小さい値がk個あるかどうか？
    if positive:
        count = than_less_zero
        #正＊正
        r = len(positive_number)-1
        for l in range(len(positive_number)):
            while l < r and positive_number[l] * positive_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #負*負
        r = len(negative_number)-1
        for l in range(len(negative_number)):
            while l < r and r_negative_number[l] * r_negative_number[r] > x:
                r -= 1
            count += r - l
            if l >= r:
                break
        #print("target:{} count:{}".format(x,count))
        if count >= k:
            return True
        else:
            return False
    else:
        assert(0 == 1)
        count = 0
        l,r = 0,0
        for l in range(len(positive_number)):
            while r < len(negative_number) and positive_number[l] * negative_number[r] <= x:
                r += 1
            count += r
        if count >= k:
            return True
        else:
            return False



for i in range(n):
    if a[i] > 0:
        positive_number_cnt += 1
        positive_number.append(a[i])
    elif a[i] < 0:
        negative_number_cnt += 1
        negative_number.append(a[i])
    else:
        zero_cnt += 1
than_less_zero = ( negative_number_cnt * positive_number_cnt ) + (zero_cnt * (zero_cnt-1)//2) + zero_cnt * (n-zero_cnt)
r_negative_number = [negative_number[i] for i in range(len(negative_number)-1,-1,-1)]

if than_less_zero < k:
    #答えが正になる
    print(binary_search(0,10**20,True))
elif ( negative_number_cnt * positive_number_cnt ) >= k:
    #答えが負になる
    print(binary_search(-10*20,0,False))
else:
    #答えが0になる
    print(0)

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_m = bisect_left(a, 0)  # a[i] < 0 の数
n_0 = bisect_right(a, 0) - n_m  # a[i] = 0 の数
n_p = n - n_m - n_0  # a[i] > 0 の数

nn_m = n_m * n_p  # 積が負になるペア数
nn_0 = n_0 * (n - n_0) + n_0 * (n_0 - 1) // 2  # 積が0になるペア数
nn_p = n * (n - 1) // 2 - nn_m - nn_0  # 積が正になるペア数

if k <= nn_m:
    # k番目の値は負

    def check_minus(x):
        # k番目の値がx(<0)以下

        # a[i] * a[j] <= x

        # a[i]   * a[j] <= x  : a[j] >= abs(x) / abs(a[i])
        # a[i+1] * a[j] <= x  : a[j] >= abs(x) / abs(a[i+1])
        #     a[i]  <=     a[i+1] < 0
        # abs(a[i]) >= abs(a[i+1])
        # a: [-------00000+++++++]
        #     i             jjjjj
        #      i             jjjj
        #       i              jj

        # a[i] * a[j] <= -7
        # n_m = 4
        # n_0 = 3
        # a = [-5, -3, -2, -1, 0, 0, 0, 1, 2, 3, 4, 5]
        #       i                          j (j  j  j)
        #           i                         j (j  j)
        #               i                        j
        #                   i                          j
        # a[i] * a[j] = -5
        #  -2  *   4  = -6

        cnt = 0
        j = n_m + n_0
        for i in range(n_m):
            while a[i] * a[j] > x and j < n:
                j += 1
            # a[i] * a[j] <= x
            # [j, n)
            cnt += n - j

        return cnt >= k

    # a[i] * a[j] <= x
    lb = -10**18  # False
    ub = -1  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_minus(mid):
            ub = mid
        else:
            lb = mid
    ans = ub
elif k <= nn_m + nn_0:
    # k番目の値は0
    ans = 0
else:
    # k番目の値は正
    a_p = a[n_m + n_0:]
    a_m = [-a[i] for i in reversed(range(n_m))]

    def check_plus(x):
        # k番目の値がx(>=0)以下
        def func(b):
            # b [++++++++++++++]
            #    ijjjjjjjjjjj
            #     ijjjjjjjj
            #      ijjjj
            #       ij

            # b[i] * b[j] <= x
            # b[i]   * b[j] <= x : b[j]  <= x / b[i]
            # b[i+1] * b[j] <= x : b[j]  <= x / b[i+1]

            c = 0
            j = len(b) - 1
            for i in range(len(b)):
                if i >= j:
                    break
                # i < j
                while i < j and b[i] * b[j] > x:
                    j -= 1
                # b[i] * b[j] <= x
                # (i, j]
                c += j - i
            return c

        cnt = nn_m + nn_0
        cnt += func(a_p)
        cnt += func(a_m)
        return cnt >= k

    # a[i] * a[j] <= x
    lb = 0  # False
    ub = 10**18 + 1  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_plus(mid):
            ub = mid
        else:
            lb = mid
    ans = ub
print(ans)

Submission status: Runtime Error

Solution code:
inin=[list(map(int,i.split())) for i in Input.split('\n')]
N,K=inin[0]
A=inin[1]

# N,K=list(map(int,input().split()))
# A=list(map(int,input().split()))
l_neglis=0
l_poslis=0
l_zerolis=0
A=sorted(A)
for i in A:
    if i>0:
        l_poslis+=1
    elif i<0:
        l_neglis+=1
    else:
        l_zerolis+=1
        
# l_neglis=len(neglis)
# l_poslis=len(poslis)
# l_zerolis=len(zerolis)
neg=l_neglis*l_poslis
pos=l_neglis*(l_neglis-1)//2+l_poslis*(l_poslis-1)//2
zero=l_zerolis*(l_neglis+l_poslis)+l_zerolis*(l_zerolis-1)//2
# neglis=neglis[::-1]

if K<=neg:
    poslis=[]
    neglis=[]
    zerolis=[]
    for i in A:
        if i>0:
            poslis.append(i)
        elif i<0:
            neglis.append(i)
        else:
            zerolis.append(i)
            
    r=-1
    l=neglis[0]*poslis[-1]
    while 1!=r-l:
        mid=(r+l)//2
        counter=0
        for i in range(l_neglis):
            for j in range(l_poslis):
                if neglis[i]*poslis[-1-j]>mid:
                    continue
                else:
                    counter+=(l_poslis-j)
                    break
        if counter>=K:
            r=mid
        else:
            l=mid 
    print(r)
elif K<=neg+zero:
    print(0)
else:
    poslis=[]
    neglis=[]
    zerolis=[]
    for i in A:
        if i>0:
            poslis.append(i)
        elif i<0:
            neglis.append(i)
        else:
            zerolis.append(i)
    l=0
    r=10**18+1
    K-=(neg+zero)
    while r-l!=1:
        mid=(r+l)//2
        counter=0
        for i in range(l_neglis-1):
            for j in range(i+1,l_neglis):
                if neglis[i]*neglis[j]>mid:
                    continue
                else:
                    counter+=(l_neglis-j)
                    break
        for i in range(l_poslis-1):
            for j in range(i+1,l_poslis):
                if poslis[-1-i]*poslis[-1-j]>mid:
                    continue
                else:
                    counter+=(l_poslis-j)
                    break
        if counter>=K:
            r=mid
        else:
            l=mid 
    print(r)

Submission status: Runtime Error

Solution code:
# inin=[list(map(int,i.split())) for i in Input.split('\n')]
# N,K=inin[0]
# A=inin[1]

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

A=sorted(A)

# neglis=neglis[::-1]

if K<=neg:
    poslis=[]
    neglis=[]
    zerolis=[]
    for i in A:
        if i>0:
            poslis.append(i)
        elif i<0:
            neglis.append(i)
        else:
            zerolis.append(i)
    neg=len(neglis)*len(poslis)
    pos=len(neglis)*(len(neglis)-1)//2+len(poslis)*(len(poslis)-1)//2
    zero=len(neglis)*len(zerolis)+len(poslis)*len(zerolis)+len(zerolis)*(len(zerolis)-1)//2
    l_neglis=len(neglis)
    l_poslis=len(poslis)
    r=-1
    l=neglis[0]*poslis[-1]
    while 1!=r-l:
        mid=(r+l)//2
        counter=0
        for i in range(l_neglis):
            for j in range(l_poslis):
                if neglis[i]*poslis[-1-j]>mid:
                    continue
                else:
                    counter+=(l_poslis-j)
                    break
        if counter>=K:
            r=mid
        else:
            l=mid 
    print(r)
elif K<=neg+zero:
    print(0)
else:
    poslis=[]
    neglis=[]
    zerolis=[]
    for i in A:
        if i>0:
            poslis.append(i)
        elif i<0:
            neglis.append(i)
        else:
            zerolis.append(i)
    neg=len(neglis)*len(poslis)
    pos=len(neglis)*(len(neglis)-1)//2+len(poslis)*(len(poslis)-1)//2
    zero=len(neglis)*len(zerolis)+len(poslis)*len(zerolis)+len(zerolis)*(len(zerolis)-1)//2
    l_neglis=len(neglis)
    l_poslis=len(poslis)
    l=0
    r=10**18+1
    K-=(neg+zero)
    while r-l!=1:
        mid=(r+l)//2
        counter=0
        for i in range(l_neglis-1):
            for j in range(i+1,l_neglis):
                if neglis[i]*neglis[j]>mid:
                    continue
                else:
                    counter+=(l_neglis-j)
                    break
        for i in range(l_poslis-1):
            for j in range(i+1,l_poslis):
                if poslis[-1-i]*poslis[-1-j]>mid:
                    continue
                else:
                    counter+=(l_poslis-j)
                    break
        if counter>=K:
            r=mid
        else:
            l=mid 
    print(r)

Submission status: Runtime Error

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

def find_nega(k,nega,posi):
    resu = [0]*(len(nega)*(len(posi)))
    a = 0
    for i in nega:
        for j in posi:
            resu[a]  = i*j
            a+=1

    resu = sorted(resu)
    return resu[k-1]

def find_posi(k,nega,posi):
    resu = [0] *(len(posi)*(len(posi)-1)//2+len(nega)*(len(nega)-1)//2)
    a = 0
    for i in range(len(posi)):
        for j in range(i+1,len(posi)):
            resu[a]  = posi[i]*posi[j]
            a+=1

    for i in range(len(nega)):
        for j in range(i+1,len(nega)):
            resu[a]  = nega[i]*nega[j]
            a+=1
    resu = sorted(resu)
    
    return resu[k-1]
flag = -1

nega_point = 0
posi_point = N
for i in range(len(lis)):
    if lis[i]>=0 and flag ==-1:
        nega_point = i
        flag = -2
    if lis[i] >= 1 and flag <0:
        posi_point = i
        flag = 1
        break
nega = lis[0:nega_point]
zero = lis[nega_point:posi_point]
posi = lis[posi_point:N]

nega_num = len(nega)*len(posi)
zero_num = (len(nega)+len(posi))*len(zero)  + len(zero)*(len(zero)-1)//2
posi_num = len(posi)*(len(posi)-1)//2+ len(nega)*(len(nega)-1)//2

if K <= nega_num :
    result = find_nega(K,nega,posi)
elif K<= nega_num+zero_num :
    result = 0
else:
    result = find_posi(K-nega_num-zero_num,nega,posi)
print(result)

Submission status: Runtime Error

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

def find_nega(k,nega,posi):
    resu = [0]*(len(nega)*(len(posi)))
    a = 0
    for i in nega:
        for j in posi:
            resu[a]  = i*j
            a+=1

    resu = sorted(resu)
    return resu[k-1]

def find_posi(k,nega,posi):
    resu = [0] *(len(posi)*(len(posi)-1)//2+len(nega)*(len(nega)-1)//2)
    a = 0
    for i in range(len(posi)):
        for j in range(i+1,len(posi)):
            resu[a]  = posi[i]*posi[j]
            a+=1

    for i in range(len(nega)):
        for j in range(i+1,len(nega)):
            resu[a]  = nega[i]*nega[j]
            a+=1
    resu = sorted(resu)
    
    return resu[k-1]
flag = -1

nega_point = 0
posi_point = N
for i in range(len(lis)):
    if lis[i]>=0 and flag ==-1:
        nega_point = i
        flag = -2
    if lis[i] >= 1 and flag <0:
        posi_point = i
        flag = 1
        break
nega = lis[0:nega_point]
zero = lis[nega_point:posi_point]
posi = lis[posi_point:N]

nega_num = len(nega)*len(posi)
zero_num = (len(nega)+len(posi))*len(zero)  + len(zero)*(len(zero)-1)//2
posi_num = len(posi)*(len(posi)-1)//2+ len(nega)*(len(nega)-1)//2

if K <= nega_num:
    result = find_nega(K,nega,posi)
elif K<= nega_num+zero_num:
    result = 0
else:
    result = find_posi(K-nega_num-zero_num,nega,posi)
print(int(result))

Submission status: Runtime Error

Solution code:
def main():
    def input(): return sys.stdin.readline().rstrip()
    def mi():    return map(int, input().split())
    def lmi():   return list(map(int, input().split()))


    def is_ok(pivot, k, L_positive, L_negative):
        cnt = 0
        for positive_num in L_positive:
            target = pivot // positive_num
            # target 以下の個数を求める
            cnt += bisect_right(L_negative, target)
            # 定数倍高速化
            if cnt >= k:
                return True
        return False    


    def is_ok_handle_duplicate(pivot, k, L_positive, L_negative):
        pos_cnt = 0
        if len(L_positive) >= 2:
            for num in L_positive:
                target = pivot // num
                # target 以下の個数を求める
                pos_cnt += bisect_right(L_positive, target)
                if num ** 2 <= pivot:
                    pos_cnt -= 1
            assert(pos_cnt % 2 == 0)
            pos_cnt //= 2
        # 定数倍高速化
        if pos_cnt >= k:
            return True
        neg_cnt = 0
        if len(L_negative) >= 2:
            for num in L_negative:
                target = pivot // num
                # target 以下の個数を求める
                neg_cnt += bisect_right(L_negative, target)
                if num ** 2 <= pivot:
                    neg_cnt -= 1
            assert(neg_cnt % 2 == 0)
            neg_cnt //= 2
        cnt = pos_cnt + neg_cnt
        # print(f"pivot {pivot} cnt {cnt}")
        return cnt >= k

    n, k = mi()
    L = lmi()
    L_negative, L_zero, L_positive = [], [], []
    for elm in L:
        if elm < 0:
            L_negative.append(elm)
        elif elm == 0:
            L_zero.append(elm)
        else:
            L_positive.append(elm)

    L_negative.sort()
    L_positive.sort()

    num_pairs_negative = len(L_negative) * len(L_positive)
    num_pairs_zero = len(L_zero) * (len(L_zero) -1) // 2 + len(L_zero) * (n - len(L_zero))

    
    if k <= num_pairs_negative:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        # left = - 10 ** 18 - 1
        # 定数倍高速化
        left = L_negative[0] * L_positive[-1] - 1
        # right = 0
        # 定数倍高速化
        right = L_negative[-1] * L_positive[0] + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    elif k <= num_pairs_negative + num_pairs_zero:
        print(0)
    else:
        """
        積が x 以下となるペアの個数が k 個以上となるような x の範囲が定まる。
        left はその範囲外、right はその範囲内とする。
        """
        k -= (num_pairs_negative + num_pairs_zero)
        L_negative = [- elm for elm in reversed(L_negative)]        
        # left = 0
        # 定数倍高速化
        if L_negative and L_positive:
            left = min(L_negative[0] ** 2, L_positive[0] ** 2) - 1
        elif L_negative:
            left = L_negative[0] ** 2 - 1
        else:
            left = L_positive[0] ** 2 - 1
        # right = 10 ** 18 + 1
        # 定数倍高速化
        if L_negative and L_positive:
            right = max(L_negative[-1] ** 2, L_positive[-1] ** 2) + 1
        elif L_negative:
            right = L_negative[-1] ** 2 + 1
        else:
            right = L_positive[-1] ** 2 + 1
        while right - left > 1:
            mid = (left + right) // 2
            if is_ok_handle_duplicate(mid, k, L_positive, L_negative):
                right = mid
            else:
                left = mid
        print(right)
    

if __name__ == "__main__":
    main()