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:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    ans = - 10**18

    from bisect import bisect_left, bisect_right


    N, K = LMIIS()
    A = LMIIS()
    A.sort()
    num_negative = bisect_left(A,0)
    num_zero = bisect_right(A,0) - num_negative
    num_positive = N - num_negative - num_zero
    
    inf = 10**18+1
    u = inf
    l = -inf
    # 答えが負
    if num_negative * num_positive >= K:
        def g(i,x):
            up = N
            lp = num_negative + num_zero
            min_m = N
            mp = (up+lp)//2
            while up-lp > 1:
                mp = (up+lp)//2
                # print(A[i],A[mp],mp)
                if A[i] * A[mp] < x:
                    up = mp
                    
                    min_m = min(min_m,mp)
                else:
                    lp = mp
            mp = (up+lp)//2
            if A[i] * A[mp] < x:
                # print(A[i],A[mp],mp)
                min_m = min(min_m,mp)
            # if amm * A[mp] < x:
            #     max_m = max(max_m,mp)
            # print('i=',i,'A[i]=',A[i],min_m,N-min_m)
            #print('g(',i,',',x,')=',max_m - (num_negative + num_zero-1))
            return max(N-min_m,0)
            

        def f(x):
            ans = 0
            for i in range(num_negative):
                ans += g(i,x)
            return ans

        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if f(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        return max_m

    # 答えがゼロ
    elif num_negative * num_positive + num_negative * num_zero + num_positive * num_zero + num_zero*(num_zero-1)//2 >= K:
        return 0

    # 答えが正
    else:
        K -= num_negative * num_positive +\
             num_negative * num_zero +\
             num_positive * num_zero + num_zero*(num_zero-1)//2

        def f(i,x):
            # u = num_negative
            u = i
            l = 0
            min_m = N
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    u = m
                    min_m = min(min_m,m)
                else:
                    l = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                    min_m = min(min_m,m)

            # ans = num_negative - min_m
            ans = i - min_m
            # if i >= min_m:
            #     ans -= 1 
            ans = max(ans,0)
            #print('f(',x,')=',ans, num_negative, min_m, i,A[0]*A[i]<x)
            return ans

        def g(i,x):
            u = N
            # l = num_negative + num_zero
            l = i+1
            max_m = num_negative + num_zero -1
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    l = m
                    max_m = max(max_m,m)
                else:
                    u = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                max_m = max(max_m,m)
            
            
            # ans = max_m - num_negative - num_zero +1
            ans = max_m - i
            
            # if i <=max_m :
            #     ans -= 1 
            ans = max(ans,0)
            #print('g(',x,')=',ans,max_m,num_negative+num_zero,'A[i]=',A[i])
            
            return ans
            
        def h(x):
            ans = 0
            for i in range(1,num_negative):
                ans += f(i,x)
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                ans += g(i,x)
            #print('h(',x,')=',ans,'K=',K)
            # print('neg*neg=',preans,'pos*pos=',ans-preans)
            return ans
        





        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if h(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        # m = (u+l)//2
        # if f(m) >= K:
        #     u = m
        # else:
        #     l = m
        #     max_m = max(max_m,m)
        #print('ans=',max_m,448283280358331064-max_m)
        # print(h(87940638538504704))
        print(max_m)
        return max_m




if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:

import numpy as np


# 解がマイナスのとき
def solve1(k, ml, pl):
    left, right = -(10 ** 18) - 1, 0
    while right - left > 1:
        x = (left + right) // 2
        n = (len(pl) - np.searchsorted(pl, np.ceil(x / ml))).sum()
        if k <= n:
            right = x
        else:
            left = x
    return right


# 解がプラスのとき
def solve2(k, ml, pl):
    left, right = 0, 10 ** 18
    while right - left > 1:
        x = (left + right) // 2
        n = 0
        n += (len(ml) - np.searchsorted(ml, np.ceil(x / ml))).sum()
        n -= np.count_nonzero(ml ** 2 <= x)
        n += (np.searchsorted(pl, x // pl, side="right")).sum()
        n -= np.count_nonzero(pl ** 2 <= x)
        n //= 2
        if k <= n:
            right = x
        else:
            left = x
    return right
        

def main():
    N, K = list(map(int, input().split()))
    A = np.array(input().split(), dtype=int)
    A.sort()
    ml = A[A < 0]
    pl = A[A > 0]
    zl = A[A == 0]
    mn = len(ml) * len(pl)
    zn = sum([N - i - 1 for i in range(len(zl))])
    if K <= mn:
        ans = solve1(K, ml, pl)
    elif K <= mn + zn:
        ans = 0
    else:
        ans = solve2(K - mn - zn, ml, pl)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

import numpy as np


# 解がマイナスのとき
def solve1(k, ml, pl):
    left, right = -(10 ** 18) - 1, 0
    while right - left > 1:
        x = (left + right) // 2
        n = (len(ml) - np.searchsorted(pl, np.ceil(x / ml))).sum()
        if k <= n:
            right = x
        else:
            left = x
    return right


# 解がプラスのとき
def solve2(k, ml, pl):
    left, right = 0, 10 ** 18
    while right - left > 1:
        x = (left + right) // 2
        n = 0
        n += (len(ml) - np.searchsorted(ml, x // ml)).sum()
        n -= np.count_nonzero(ml * ml <= x)
        n += (np.searchsorted(pl, x // pl, side="right")).sum()
        n -= np.count_nonzero(pl * pl <= x)
        n //= 2
        if k <= n:
            right = x
        else:
            left = x
    return right
        

def main():
    N, K = list(map(int, input().split()))
    A = np.array(input().split(), dtype=int)
    A.sort()
    ml = A[A < 0]
    pl = A[A > 0]
    zl = A[A == 0]
    mn = len(ml) * len(pl)
    zn = sum([N - i for i in range(1, len(zl) + 1)])
    if K <= mn:
        ans = solve1(K, ml, pl)
    elif K <= mn + zn:
        ans = 0
    else:
        ans = solve2(K - mn - zn, ml, pl)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

lines = [l for l in sys.stdin]
l = lines[0].split(' ')
N, K = int(l[0]), int(l[1])

nums = [int(s) for s in lines[1].split(' ')]

rets = []
for idx, n1 in enumerate(nums):
  for idy, n2 in enumerate(nums):
    if idx == idy: continue
    rets.append(n1 * n2)
rets.sort()
print(rets[K-1])

Submission status: Wrong Answer

Solution code:
import sys

lines = [l for l in sys.stdin]
l = lines[0].split(' ')
N, K = int(l[0]), int(l[1])

nums = [int(s) for s in lines[1].split(' ')]

rets = []
for idx, n1 in enumerate(nums):
  for idy, n2 in enumerate(nums):
    if idx == idy: continue
    rets.append(n1 * n2)
rets.sort()
print(rets[K])

Submission status: Wrong Answer

Solution code:

import numpy as np


# 解がマイナスのとき
def solve1(k, ml, pl):
    left, right = -(10 ** 18) - 1, 0
    while right - left > 1:
        c = (left + right) // 2
        n = 0
        for x in ml:
            y = np.ceil(c / x)
            n += len(pl) - np.searchsorted(pl, y)
        if k <= n:
            right = c
        else:
            left = c
    return right


# 解がプラスのとき
def solve2(k, ml, pl):
    left, right = 0, 10 ** 18
    while right - left > 1:
        c = (left + right) // 2
        n = 0
        for x in ml:
            y = c // x
            n += len(ml) - np.searchsorted(ml, y)
            if y <= x:
                n -= 1
        for x in pl:
            y = c // x
            n += np.searchsorted(pl, y, side="right")
            if x <= y:
                n -= 1
        n /= 2
        if k <= n:
            right = c
        else:
            left = c
    return right
        

def main():
    N, K = list(map(int, input().split()))
    A = np.array(input().split(), dtype=int)
    A.sort()
    ml = A[A < 0]
    pl = A[A > 0]
    zl = A[A == 0]
    mn = len(ml) * len(pl)
    zn = sum([N - i for i in range(1, len(zl) + 1)])
    if K <= mn:
        ans = solve1(K, ml, pl)
    elif K <= mn + zn:
        ans = 0
    else:
        ans = solve2(K - mn - zn, ml, pl)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    ans = - 10**18

    from bisect import bisect_left, bisect_right


    N, K = LMIIS()
    A = LMIIS()
    A.sort()
    num_negative = bisect_left(A,0)
    num_zero = bisect_right(A,0) - num_negative
    num_positive = N - num_negative - num_zero
    
    inf = 10**18+1
    u = inf
    l = -inf
    # 答えが負
    if num_negative * num_positive >= K:
        def g(i,x):
            up = N
            lp = num_negative + num_zero
            max_m = -1
            mp = (up+lp)//2
            while up-lp > 1:
                mp = (up+lp)//2
                if A[i] * A[mp] < x:
                    lp = mp
                    max_m = max(max_m,mp)
                else:
                    up = mp
            # if amm * A[mp] < x:
            #     max_m = max(max_m,mp)
            # print(amm,x,max_m,num_negative + num_zero,mp)
            return max(max_m - (num_negative + num_zero-1),0)
            

        def f(x):
            ans = 0
            for i in range(num_negative):
                ans += g(i,x)
            return ans

        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if f(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        m = (u+l)//2
        if f(m) >= K:
            u = m
        else:
            l = m
            max_m = max(max_m,m)
        print(max_m)
        return max_m

    # 答えがゼロ
    elif num_negative * num_positive + num_negative * num_zero + num_positive * num_zero + num_zero*(num_zero-1)//2 >= K:
        print(0)
        return

    # 答えが正
    else:
        return
        K -= num_negative * num_positive +\
             num_negative * num_zero +\
             num_positive * num_zero + num_zero*(num_zero-1)//2

        def f(i,x):
            # u = num_negative
            u = i
            l = 0
            min_m = N
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    u = m
                    min_m = min(min_m,m)
                else:
                    l = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                    min_m = min(min_m,m)

            # ans = num_negative - min_m
            ans = i - min_m
            # if i >= min_m:
            #     ans -= 1 
            ans = max(ans,0)
            #print('f(',x,')=',ans, num_negative, min_m, i,A[0]*A[i]<x)
            return ans

        def g(i,x):
            u = N
            # l = num_negative + num_zero
            l = i+1
            max_m = num_negative + num_zero -1
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    l = m
                    max_m = max(max_m,m)
                else:
                    u = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                max_m = max(max_m,m)
            
            
            # ans = max_m - num_negative - num_zero +1
            ans = max_m - i
            
            # if i <=max_m :
            #     ans -= 1 
            ans = max(ans,0)
            #print('g(',x,')=',ans,max_m,num_negative+num_zero,'A[i]=',A[i])
            
            return ans
            
        def h(x):
            ans = 0
            for i in range(1,num_negative):
                ans += f(i,x)
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                ans += g(i,x)
            #print('h(',x,')=',ans,'K=',K)
            # print('neg*neg=',preans,'pos*pos=',ans-preans)
            return ans
        





        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if h(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        # m = (u+l)//2
        # if f(m) >= K:
        #     u = m
        # else:
        #     l = m
        #     max_m = max(max_m,m)
        #print('ans=',max_m,448283280358331064-max_m)
        # print(h(87940638538504704))
        print(max_m)
        return max_m




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    ans = - 10**18

    from bisect import bisect_left, bisect_right


    N, K = LMIIS()
    A = LMIIS()
    A.sort()
    num_negative = bisect_left(A,0)
    num_zero = bisect_right(A,0) - num_negative
    num_positive = N - num_negative - num_zero
    
    inf = 10**18+1
    u = inf
    l = -inf
    # 答えが負
    if num_negative * num_positive >= K:
        def g(i,x):
            up = N
            lp = num_negative + num_zero
            max_m = -1
            mp = (up+lp)//2
            while up-lp > 1:
                mp = (up+lp)//2
                if A[i] * A[mp] < x:
                    lp = mp
                    max_m = max(max_m,mp)
                else:
                    up = mp
            # if amm * A[mp] < x:
            #     max_m = max(max_m,mp)
            # print(amm,x,max_m,num_negative + num_zero,mp)
            return max(max_m - (num_negative + num_zero-1),0)
            

        def f(x):
            ans = 0
            for i in range(num_negative):
                ans += g(i,x)
            return ans

        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if f(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        # m = (u+l)//2
        # if f(m) >= K:
        #     u = m
        # else:
        #     l = m
        #     max_m = max(max_m,m)
        print(max_m)
        return max_m

    # 答えがゼロ
    elif num_negative * num_positive + num_negative * num_zero + num_positive * num_zero + num_zero*(num_zero-1)//2 >= K:
        print(0)
        return

    # 答えが正
    else:
        K -= num_negative * num_positive +\
             num_negative * num_zero +\
             num_positive * num_zero + num_zero*(num_zero-1)//2

        def f(i,x):
            # u = num_negative
            u = i
            l = 0
            min_m = N
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    u = m
                    min_m = min(min_m,m)
                else:
                    l = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                    min_m = min(min_m,m)

            # ans = num_negative - min_m
            ans = i - min_m
            # if i >= min_m:
            #     ans -= 1 
            ans = max(ans,0)
            #print('f(',x,')=',ans, num_negative, min_m, i,A[0]*A[i]<x)
            return ans

        def g(i,x):
            u = N
            # l = num_negative + num_zero
            l = i+1
            max_m = num_negative + num_zero -1
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    l = m
                    max_m = max(max_m,m)
                else:
                    u = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                max_m = max(max_m,m)
            
            
            # ans = max_m - num_negative - num_zero +1
            ans = max_m - i
            
            # if i <=max_m :
            #     ans -= 1 
            ans = max(ans,0)
            #print('g(',x,')=',ans,max_m,num_negative+num_zero,'A[i]=',A[i])
            
            return ans
            
        def h(x):
            ans = 0
            for i in range(1,num_negative):
                ans += f(i,x)
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                ans += g(i,x)
            #print('h(',x,')=',ans,'K=',K)
            # print('neg*neg=',preans,'pos*pos=',ans-preans)
            return ans
        





        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if h(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        # m = (u+l)//2
        # if f(m) >= K:
        #     u = m
        # else:
        #     l = m
        #     max_m = max(max_m,m)
        #print('ans=',max_m,448283280358331064-max_m)
        # print(h(87940638538504704))
        print(max_m)
        return max_m




if __name__ == '__main__':
    main()

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 >= M - K + 1

if K <= M:
    left = -1 -10 ** 18
    right = 1 + 10 ** 18
    while right - left> 1:
        mid = (left + right) // 2
        if cnt_M(mid):
            right = mid
        else:
            left = mid
 
    print(-right)
    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)
    cnt = (cnt - ng) // 2
    return cnt >= K

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

while right - left > 1:
    mid = (left + right) // 2
    if cnt_P(mid):
        right = mid
    else:
        left = mid
print(right)

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 >= M - K + 1

if K <= M:
    left = -1 -10 ** 18
    right = 1 + 10 ** 18
    while True:
        mid = (left + right) // 2
        if cnt_M(mid):
            if not cnt_M(mid):
                ans = mid
                break
            else:
                right = mid
        else:
            if cnt_M(mid + 1):
                ans = mid + 1
                break
            else:
                left = mid
 
    print(-ans)
    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)
    cnt = (cnt - ng) // 2
    return cnt >= K

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

while True:
    mid = (left + right) // 2
    if cnt_P(mid):
        if not cnt_P(mid - 1):
            ans = mid
            break
        else:
            right = mid
    else:
        if cnt_P(mid + 1):
            ans = mid + 1
            break
        else:
            left = mid
print(ans)

Submission status: Wrong Answer

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


def main():
    N,K = map(int, input().split())
    A = np.array(sorted([int(i) for i in input().split()]))

    zero_left = np.searchsorted(A, 0, side='left')
    zero_right = np.searchsorted(A, 0, side='right')

    negative = zero_left
    positive = N - zero_right
    zero = zero_right - zero_left
    non_posi = negative * positive + zero * (N - zero) + zero * (zero - 1) // 2

    if K <= negative * positive:
        Nega = A[:zero_left]
        Posi = A[zero_right:]

        left = -(A[0]**2)
        right = 0
        while right - left > 1:
            x = (left + right) // 2
            count = np.searchsorted(Nega, x // Posi, side='right').sum()

            if count < K:
                left = x
            else:
                right = x

        print(right)

    elif K <= non_posi:
        print(0)

    else:
        Nega = np.sort(np.abs(A[:zero_left]))
        Posi = A[zero_right:]

        left = 0
        right = 10**18
        while right - left > 1:
            x = (left + right) // 2
            count = 0
            count += np.searchsorted(Nega, x // Nega, side='right').sum()
            count += np.searchsorted(Posi, x // Posi, side='right').sum()
            count -= np.int_(np.where(np.searchsorted(Nega, x // Nega) >= np.arange(1,negative+1), True, False)).sum()
            count -= np.int_(np.where(np.searchsorted(Posi, x // Posi) >= np.arange(1,positive+1), True, False)).sum()
            count //= 2

            if count + non_posi < K:
                left = x
            else:
                right = x

            print(left, right, count + non_posi)

        #print(right)


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_left(A_plus,-(-mid//A_minus[0]))
            c+=len(A_plus)-z
            for x in A_minus[1:]:
                if z>0 and A_plus[z-1] >= -(-mid//x):
                    while z>0 and A_plus[z-1] >= -(-mid//x):
                        z-=1
                c+=len(A_plus)-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:


"""
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]
    if a[ans[0]]==0:
        print(0)
        return
    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:


"""
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]
    if ans[0]==0:
        print(0)
        return
    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()