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: Wrong Answer

Solution code:


"""
NTC here
""" 
import sys
inp= sys.stdin.readline
input = lambda : inp().strip()
flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))



def main():
    n, k = lin()
    a = lin()
    a.sort(key= lambda x: abs(x)) #sort by magnitude
    pv, ne = 0, 0
    a1 = [[0,0] for i in range(n)]
    a = a[::-1]
    for i in range(n):
        a1[i]=[pv, ne]
        if a[i]>0:
            pv+=1
        else:
            ne+=1
    a1, a = a1[::-1], a[::-1]
    q1, q2 = [], []
    for i in range(n):
        if a[i]>0:
            q1.append(a1[i][0])
            q2.append(a1[i][1])
        else:
            q1.append(a1[i][1])
            q2.append(a1[i][0])
    ans = 0
    # print(a, q1, q2)
    # check for negative
    for i in range(n-1, -1, -1):
        if q2[i] and q2[i] >= k:
            ans = [i, 1]
            break
        k -= q2[i]
    
    #check for positive now
    if not ans:
        for i in range(n):
            if q1[i] and q1[i] >= k:
                ans = [i, 0]
                break
            k -= q1[i]

    pv, ng= [], []
    for i in range(ans[0]+1, n):
        if a[i]>0:
            pv.append(a[i])
        else:
            ng.append(a[i])
    ch, ch1 = ans
    if a[ch]>0:pass
    else: ch1 = 1 if ch1==0 else 0
    if ch1:
        print(a[ch]*ng[k-1])
    else:
        print(a[ch]*pv[k-1])



    
    

main()

#threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A_m = np.array(sorted([abs(int(x)) for x in A if x < 0]), np.int64)
N_m = len(A_m)

A_p = np.array(sorted([int(x) for x in A if x > 0]), np.int64)
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = np.searchsorted(A_m, x / A_p, side="right").sum()
    return cnt

if K <= M:
    left = -1
    right = 10 ** 6
    
    left = -10 ** 18
    right = 10 ** 18
    while left + 1 < right:
        x = (left + right) // 2
        if cnt_M(x) >= K:
            right = x
        else:
            left = x
 
    print(-left)
    sys.exit()
K -= (M + Z)
def cnt_P(x):
    cnt = 0
    ng = 0
    cnt += np.searchsorted(A_m, x / A_m, side="right").sum()
    cnt += np.searchsorted(A_p, x / A_p, side="right").sum()
    ng = np.count_nonzero(A_m * A_m <= x) + np.count_nonzero(A_p * A_p <= x)
    return (cnt - ng) // 2

left = -1
right = 1 + 10 ** 18

left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if cnt_P(x) >= K:
        right = x
    else:
        left = x
 
print(right)

Submission status: Wrong Answer

Solution code:


"""
NTC here
""" 
import sys
inp= sys.stdin.readline
input = lambda : inp().strip()
flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))



def main():
    n, k = lin()
    a = lin()
    a.sort(key= lambda x: abs(x)) #sort by magnitude
    pv, ne = 0, 0
    a1 = [[0,0] for i in range(n)]
    a = a[::-1]
    for i in range(n):
        a1[i]=[pv, ne]
        if a[i]>0:
            pv+=1
        else:
            ne+=1
    a1, a = a1[::-1], a[::-1]
    q1, q2 = [], []
    for i in range(n):
        if a[i]>0:
            q1.append(a1[i][0])
            q2.append(a1[i][1])
        else:
            q1.append(a1[i][1])
            q2.append(a1[i][0])
    sm = 0 
    ans = 0
    # print(a, q1, q2)
    # check for negative
    for i in range(n-1, -1, -1):
        if sm + q2[i] >= k:
            k -= sm
            ans = [i, 1]
            break
        sm += q2[i]
    
    #check for positive now
    if not ans:
        for i in range(n):
            if sm + q1[i] >= k:
                k -= sm
                ans = [i, 0]
                break
            sm += q1[i]
    ch = 0
    if ans[1]:
        ch = 1
    ch1 = ans[0]
    ch2 = 0
    # print(sm, ans, k, q1, q2, a)

    if a[ch1]<=0:
        ch = 1 if ch==0 else 0
    pv, ng= [], []
    for i in range(ch1+1, n):
        if a[i]>0:
            pv.append(a[i])
        else:
            ng.append(a[i])
    if ch:
        print(a[ch1]*ng[k-1])
    else:
        print(a[ch1]*pv[k-1])



    
    

main()

#threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:


"""
NTC here
""" 
import sys
inp= sys.stdin.readline
input = lambda : inp().strip()
flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))



def main():
    n, k = lin()
    a = lin()
    a.sort(key= lambda x: abs(x)) #sort by magnitude
    pv, ne = 0, 0
    a1 = [[0,0] for i in range(n)]
    a = a[::-1]
    for i in range(n):
        a1[i]=[pv, ne]
        if a[i]>0:
            pv+=1
        else:
            ne+=1
    a1, a = a1[::-1], a[::-1]
    q1, q2 = [], []
    for i in range(n):
        if a[i]>0:
            q1.append(a1[i][0])
            q2.append(a1[i][1])
        else:
            q1.append(a1[i][1])
            q2.append(a1[i][0])
    sm = 0 
    ans = 0
    # print(a, q1, q2)
    # check for negative
    for i in range(n-1, -1, -1):
        if sm + q2[i] >= k:
            ans = [i, 1]
            break
        sm += q2[i]
    
    #check for positive now
    if not ans:
        for i in range(n):
            if sm + q1[i] >= k:
                ans = [i, 0]
                break
            sm += q1[i]
    ch = 0
    if ans[1]:
        ch = 1
    ch1 = ans[0]
    ch2 = 0
    k -= sm
    # print(sm, ans, k, q1, q2, a)

    if a[ch1]<=0:
        ch = 1 if ch==0 else 0
    for i in range(ch1+1, n):
        if a[i]>0:
            if ch==0:
                ch2+=1
                if ch2==k:
                    print(a[ch1]*a[i])
                    return
        else:
            if ch==1:
                ch2+=1
                if ch2==k:
                    print(a[ch1]*a[i])
                    return



    
    

main()

#threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:


"""
NTC here
""" 
import sys
inp= sys.stdin.readline
input = lambda : inp().strip()
flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))



def main():
    n, k = lin()
    a = lin()
    a.sort(key= lambda x: abs(x)) #sort by magnitude
    pv, ne = 0, 0
    a1 = [[0,0] for i in range(n)]
    a = a[::-1]
    for i in range(n):
        a1[i]=[pv, ne]
        if a[i]>0:
            pv+=1
        else:
            ne+=1
    a1, a = a1[::-1], a[::-1]
    q1, q2 = [], []
    for i in range(n):
        if a[i]>0:
            q1.append(a1[i][0])
            q2.append(a1[i][1])
        else:
            q1.append(a1[i][1])
            q2.append(a1[i][0])
    sm = 0 
    ans = 0
    # print(a, q1, q2)
    # check for negative
    for i in range(n-1, -1, -1):
        if sm + q2[i] >= k:
            ans = [i, 1]
            break
        sm += q2[i]
    
    #check for positive now
    if not ans:
        for i in range(n):
            if sm + q1[i] >= k:
                ans = [i, 0]
                break
            sm += q1[i]
    ch = 0
    if ans[1]:
        ch = 1
    ch1 = ans[0]
    ch2 = 0
    k -= sm
    # print(sm, ans, k, q1, q2, a)

    if a[ch1]<0:
        ch = 1 if ch==0 else 0
    for i in range(ch1+1, n):
        if a[i]>0:
            if ch==0:
                ch2+=1
                if ch2==k:
                    print(a[ch1]*a[i])
                    return
        else:
            if ch==1:
                ch2+=1
                if ch2==k:
                    print(a[ch1]*a[i])
                    return



    
    

main()

#threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A_m = np.array(sorted([abs(int(x)) for x in A if x < 0]), np.int64)
N_m = len(A_m)

A_p = np.array(sorted([int(x) for x in A if x > 0]), np.int64)
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = np.searchsorted(A_m, x / A_p, side="left").sum()
    return cnt < (M - K + 1)

if K <= M:
    left = -1
    right = 10 ** 6
    while True:
        mid = (left + right) // 2
        if cnt_M(mid):
            if cnt_M(mid + 1):
                left = mid
            else:
                ans = mid
                break
        else:
            if cnt_M(mid - 1):
                ans = mid - 1
                break
            else:
                right = mid
    print(-ans)
    sys.exit()

def cnt_P(x):
    cnt = 0
    ng = 0
    for i in A_m:
        cnt += np.searchsorted(A_m, x / i, side="left").sum()
        if i ** 2 < x:
            ng += 1
    for j in A_p:
        cnt += np.searchsorted(A_p, x / j, side="left").sum()
        if j ** 2 < x:
            ng += 1
    return (cnt - ng) // 2 < K - (M + Z)

left = -1
right = 1 + 10 ** 18
while True:
    mid = (left + right) // 2
    if cnt_P(mid):
        if cnt_P(mid + 1):
            left = mid
        else:
            ans = mid
            break
    else:
        if cnt_P(mid - 1):
            ans = mid - 1
            break
        else:
            right = mid

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import bisect

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A_m = [abs(int(x)) for x in A if x < 0]
A_m.sort()
N_m = len(A_m)

A_p = [int(x) for x in A if x > 0]
A_p.sort()
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = 0
    for i in A_m:
        cnt += bisect.bisect_right(A_p, x / i)
    '''for j in A_p:
        cnt += bisect.bisect_right(A_m, x / j)'''
    return cnt >= (M - K + 1)

if K <= M:
    left = -1
    right = 10 ** 6
    while True:
        mid = (left + right) // 2
        if cnt_M(mid):
            if cnt_M(mid - 1):
                right = mid
            else:
                ans = -mid
                break
        else:
            if cnt_M(mid + 1):
                ans = -(mid + 1)
                break
            else:
                left = mid
    print(ans)
    sys.exit()

sys.exit()
def cnt_P(x):
    cnt = 0
    ng = 0
    for i in A_m:
        cnt += bisect.bisect_left(A_m, x / i)
        if i ** 2 < x:
            ng += 1
    for j in A_p:
        cnt += bisect.bisect_left(A_p, x / j)
        if j ** 2 < x:
            ng += 1
    return (cnt - ng) // 2 < K - (M + Z)

left = -1
right = 1 + 10 ** 18
while True:
    mid = (left + right) // 2
    if cnt_P(mid):
        if cnt_P(mid + 1):
            left = mid
        else:
            ans = mid
            break
    else:
        if cnt_P(mid - 1):
            ans = mid - 1
            break
        else:
            right = mid

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import bisect

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A_m = [abs(int(x)) for x in A if x < 0]
A_m.sort()
N_m = len(A_m)

A_p = [int(x) for x in A if x > 0]
A_p.sort()
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = 0
    for i in A_m:
        cnt += bisect.bisect_right(A_p, x / i)
    '''for j in A_p:
        cnt += bisect.bisect_right(A_m, x / j)'''
    return cnt >= (M - K + 1)

if K <= M:
    left = -1
    right = 10 ** 6
    while True:
        mid = (left + right) // 2
        if cnt_M(mid):
            if cnt_M(mid - 1):
                right = mid
            else:
                ans = -mid
                break
        else:
            if cnt_M(mid + 1):
                ans = -(mid + 1)
                break
            else:
                left = mid
    print(ans)
    sys.exit()

def cnt_P(x):
    cnt = 0
    ng = 0
    for i in A_m:
        cnt += bisect.bisect_left(A_m, x / i)
        if i ** 2 < x:
            ng += 1
    for j in A_p:
        cnt += bisect.bisect_left(A_p, x / j)
        if j ** 2 < x:
            ng += 1
    return (cnt - ng) // 2 < K - (M + Z)

left = -1
right = 1 + 10 ** 18
while True:
    mid = (left + right) // 2
    if cnt_P(mid):
        if cnt_P(mid + 1):
            left = mid
        else:
            ans = mid
            break
    else:
        if cnt_P(mid - 1):
            ans = mid - 1
            break
        else:
            right = mid

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import bisect

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A_m = [abs(int(x)) for x in A if x < 0]
A_m.sort()
N_m = len(A_m)

A_p = [int(x) for x in A if x > 0]
A_p.sort()
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = 0
    for i in A_m:
        cnt += bisect.bisect_right(A_p, x / i)
    '''for j in A_p:
        cnt += bisect.bisect_right(A_m, x / j)'''
    return cnt >= (M - K + 1)

if K <= M:
    left = -1
    right = 10 ** 6
    while True:
        mid = (left + right) // 2
        if cnt_M(mid):
            if cnt_M(mid - 1):
                right = mid
            else:
                ans = -mid
                break
        else:
            if cnt_M(mid + 1):
                ans = -(mid + 1)
                break
            else:
                left = mid
    print(ans)
    sys.exit()

def cnt_P(x):
    cnt = 0
    ng = 0
    for i in A_m:
        cnt += bisect.bisect_right(A_m, x / i)
        if i ** 2 <= x:
            ng += 1
    for j in A_p:
        cnt += bisect.bisect_right(A_p, x / j)
        if j ** 2 <= x:
            ng += 1
    return (cnt - ng) // 2 >= K - (M + Z)

left = -1
right = 10 ** 19
while True:
    mid = (left + right) // 2
    if cnt_P(mid):
        if cnt_P(mid - 1):
            right = mid
        else:
            ans = mid
            break
    else:
        if cnt_P(mid + 1):
            ans = mid + 1
            break
        else:
            left = mid

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import bisect

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A_m = [abs(int(x)) for x in A if x < 0]
A_m.sort()
N_m = len(A_m)

A_p = [int(x) for x in A if x > 0]
A_p.sort()
N_p = len(A_p)

A_z = [int(x) for x in A if x == 0]
N_z = len(A_z)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = 0
    for i in A_m:
        cnt += bisect.bisect_right(A_p, x / i)
    for j in A_p:
        cnt += bisect.bisect_right(A_m, x / j)
    return cnt >= (M - K + 1)

if K <= M:
    left = -1
    right = 10 ** 6
    while True:
        mid = (left + right) // 2
        if cnt_M(mid):
            if cnt_M(mid - 1):
                right = mid
            else:
                ans = -mid
                break
        else:
            if cnt_M(mid + 1):
                ans = -(mid + 1)
                break
            else:
                left = mid
    print(ans)
    sys.exit()

def cnt_P(x):
    cnt = 0
    ng = 0
    for i in A_m:
        cnt += bisect.bisect_right(A_m, x / i)
        if i ** 2 <= x:
            ng += 1
    for j in A_p:
        cnt += bisect.bisect_right(A_p, x / j)
        if j ** 2 <= x:
            ng += 1
    return (cnt - ng) // 2 >= K - (M + Z)

left = -1
right = 10 ** 19
while True:
    mid = (left + right) // 2
    if cnt_P(mid):
        if cnt_P(mid - 1):
            right = mid
        else:
            ans = mid
            break
    else:
        if cnt_P(mid + 1):
            ans = mid + 1
            break
        else:
            left = mid

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import bisect
from collections import deque

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A_m = [abs(int(x)) for x in A if x < 0]
A_m.sort()
N_m = len(A_m)

A_p = [int(x) for x in A if x > 0]
A_p.sort()
N_p = len(A_p)

A_z = [int(x) for x in A if x == 0]
N_z = len(A_z)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = 0
    for i in A_m:
        cnt += bisect.bisect_right(A_p, x / i)
    for j in A_p:
        cnt += bisect.bisect_right(A_m, x / j)
    return cnt >= (M - K + 1)

if K <= M:
    left = -1
    right = 10 ** 6
    while True:
        mid = (left + right) // 2
        if cnt_M(mid):
            if cnt_M(mid - 1):
                right = mid
            else:
                ans = -mid
                break
        else:
            if cnt_M(mid + 1):
                ans = -(mid + 1)
                break
            else:
                left = mid
    print(ans)
    sys.exit()

def cnt_P(x):
    A_m_d = deque(A_m)
    A_p_d = deque(A_p)
    cnt = 0
    while A_m_d:
        i = A_m_d.popleft()
        cnt += bisect.bisect_right(A_m_d, x / i)
    while A_p_d:
        j = A_p_d.popleft()
        cnt += bisect.bisect_right(A_p_d, x / j)
    return cnt >= K - (M + Z)

left = -1
right = 10 ** 19
while True:
    mid = (left + right) // 2
    if cnt_P(mid):
        if cnt_P(mid - 1):
            right = mid
        else:
            ans = mid
            break
    else:
        if cnt_P(mid + 1):
            ans = mid + 1
            break
        else:
            left = mid

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import bisect

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A_m = [abs(int(x)) for x in A if x < 0]
A_m.sort()
N_m = len(A_m)

A_p = [int(x) for x in A if x > 0]
A_p.sort()
N_p = len(A_p)

A_z = [int(x) for x in A if x == 0]
N_z = len(A_z)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = 0
    for i in A_m:
        cnt += bisect.bisect_right(A_p, x / i)
    for j in A_p:
        cnt += bisect.bisect_right(A_m, x / j)
    return cnt >= (M - K + 1)

if K <= M:
    left = -1
    right = 10 ** 6
    while True:
        mid = (left + right) // 2
        if cnt_M(mid):
            if cnt_M(mid - 1):
                right = mid
            else:
                ans = -mid
                break
        else:
            if cnt_M(mid + 1):
                ans = -(mid + 1)
                break
            else:
                left = mid
    print(ans)
    sys.exit()

def cnt_P(x):
    cnt = 0
    for i in range(N_m):
        tmp = A_m[i + 1:]
        cnt += bisect.bisect_right(tmp, x / A_m[i])
    for j in range(N_p):
        tmp = A_p[j + 1:]
        cnt += bisect.bisect_right(tmp, x / A_p[j])
    return cnt >= K - (M + Z)

left = -1
right = 10 ** 19
while True:
    mid = (left + right) // 2
    if cnt_P(mid):
        if cnt_P(mid - 1):
            right = mid
        else:
            ans = mid
            break
    else:
        if cnt_P(mid + 1):
            ans = mid + 1
            break
        else:
            left = mid

print(ans)

Submission status: Wrong Answer

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

# 組み合わせの計算
def combination(x):
    return int((x * (x - 1)) / 2)

# 組み合わせのリストを作成
def list_conbination(l):
    list_c = []
    l_length = len(l)
    
    if l_length <= 1:
        return list_c
    
    for i in range(l_length):
        n = i + 1
        while n < l_length:
            list_c.append(l[i] * l[n])
            n += 1
    
    return list_c

# 負,0,正のリストを作成
minus = []
zero = []
plus = []
for i in a:
    if i < 0:
        minus.append(i)
    elif i == 0:
        zero.append(i)
    else:
        plus.append(i)

minus = sorted(minus, key=abs)
plus = sorted(plus, key=abs)

# 負,0,正の個数
minus_num = len(minus)
zero_num = len(zero)
plus_num = len(plus)

# 積が負,0,正になる個数
minus_ans_num = minus_num * plus_num
zero_ans_num = minus_num * zero_num + plus_num * zero_num + combination(zero_num)
plus_ans_num = combination(minus_num) + combination(plus_num)

# 小さい順に並べて、K番目の数値を出力(負,0,正の順番で判定)
if minus_ans_num >= k: #Kが負の範囲
    ans = []
    minus.reverse()
    plus.reverse()
    
    for m in minus:
        for p in plus:
            ans.append(m * p)
        
        if len([i for i in ans if i <= m * plus[0]]) >= k:
            ans.sort()
            print(ans[k - 1])        
elif minus_ans_num + zero_ans_num >= k: # Kが0の範囲
    print(0)
else: #Kが正の範囲
    ans = list_conbination(minus) + list_conbination(plus)
    ans.sort()
    print(ans[k - minus_ans_num - zero_ans_num - 1])

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A_minus,A_zero,A_plus=[],[],[]
    x=bisect_left(A,0)
    y=bisect_right(A,0)
    A_minus=A[:x]
    A_minus=list(reversed(list(map(lambda x: -x,A_minus))))
    A_zero=A[x:y]
    A_plus=A[y:]
    if K<=len(A_minus)*len(A_plus):
        def nibutan1(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve1(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve1(mid):
            c=0
            z=bisect_right(A_plus,mid//A_minus[0])
            c+=z
            for x in A_minus[1:]:
                if z<len(A_plus) and A_plus[z-1] < -(-mid//x):
                    while z<len(A_plus) and A_plus[z-1] < -(-mid//x):
                        z+=1
                c+=z
            if c>=K:
                return True
            else:
                return False
        
        print(-nibutan1(10**18+1,0))
    K-=len(A_minus)*len(A_plus)
    if 0<K<=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2:
        print(0)
    K-=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2
    if K>0:
        def nibutan2(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve2(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve2(mid):
            c=0
            if len(A_minus)>1:
                z=bisect_right(A_minus,mid//A_minus[0])
                c+=z
                if mid//A_minus[0]>=A_minus[0]:
                    c-=1
                for x in A_minus[1:]:
                    if z>0 and A_minus[z-1] > mid//x:
                        while z>0 and A_minus[z-1] > mid//x:
                            z-=1
                    c+=z
                    if mid//x>=x:
                        c-=1
            if len(A_plus)>1:
                z=bisect_right(A_plus,(mid//A_plus[0]))
                c+=z
                if (mid//A_plus[0])>=A_plus[0]:
                    c-=1
                for x in A_plus[1:]:
                    if z>0 and A_plus[z-1] > mid//x:
                        while z>0 and A_plus[z-1] > mid//x:
                            z-=1
                    c+=z
                    if mid//x>=x:
                        c-=1
            c//=2
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan2(10**18+1,0))

    
        
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A_minus,A_zero,A_plus=[],[],[]
    x=bisect_left(A,0)
    y=bisect_right(A,0)
    A_minus=A[:x]
    A_minus=list(reversed(list(map(lambda x: -x,A_minus))))
    A_zero=A[x:y]
    A_plus=A[y:]
    if K<=len(A_minus)*len(A_plus):
        def nibutan1(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve1(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve1(mid):
            c=0
            z=bisect_right(A_plus,mid//A_minus[0])
            c+=z
            for x in A_minus[1:]:
                if z<len(A_plus) and A_plus[z-1] < mid//x:
                    while z<len(A_plus) and A_plus[z-1] < mid//x:
                        z+=1
                c+=z
            if c>=K:
                return True
            else:
                return False
        
        print(-nibutan1(10**18+1,0))
    K-=len(A_minus)*len(A_plus)
    if 0<K<=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2:
        print(0)
    K-=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2
    if K>0:
        def nibutan2(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve2(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve2(mid):
            c=0
            if len(A_minus)>1:
                z=bisect_right(A_minus,mid//A_minus[0])
                c+=z
                if mid//A_minus[0]>=A_minus[0]:
                    c-=1
                for x in A_minus[1:]:
                    if z>0 and A_minus[z-1] > mid//x:
                        while z>0 and A_minus[z-1] > mid//x:
                            z-=1
                    c+=z
                    if mid//x>=x:
                        c-=1
            if len(A_plus)>1:
                z=bisect_right(A_plus,(mid//A_plus[0]))
                c+=z
                if (mid//A_plus[0])>=A_plus[0]:
                    c-=1
                for x in A_plus[1:]:
                    if z>0 and A_plus[z-1] > mid//x:
                        while z>0 and A_plus[z-1] > mid//x:
                            z-=1
                    c+=z
                    if mid//x>=x:
                        c-=1
            c//=2
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan2(10**18+1,0))

    
        
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.readline().split(),dtype=np.int64)

a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]

print(neg,zero,pos)
def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


left=-10**18
right=10**18

while left+1<right:
    x=(left+right)//2
    out=count(x)
    print(out)
    if out>=k:
        right=x
    if out<k:
        left=x

print(right)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.readline().split(),dtype=int)

a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]

print(neg,zero,pos)
def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


left=-10**18
right=10**18

while left+1<right:
    x=(left+right)//2
    out=count(x)
    print(out)
    if out>=k:
        right=x
    if out<k:
        left=x

print(right)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.readline().split(),dtype=int)

a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]

def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


left=-10**18
right=10**18

while left+1<right:
    x=(left+right)//2
    cnt=count(x)
    if cnt>=k:
        right=x
    if cnt<k:
        left=x

print(right)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
result = []
for i in range(len(l)):
  for j in range(len(l)-1):
    result.append(l[i]*l[j+1])
print(sorted(result)[k])