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:
# 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)
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)
# neglis=neglis[::-1]

if K<=neg:
    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:
    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: Wrong Answer

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)
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

# neglis=neglis[::-1]

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

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache
from bisect import bisect


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,K = inputIL()
A = inputIL()

A.sort()

s = bisect(A,-1)
t = bisect(A,0)

M = A[:s]
Z = A[s:t]
P = A[t:]
M_rev = [i*(-1) for i in M[::-1]]

m = len(M)
z = len(Z)
p = len(P)

n_Z = z*(m+p) + z*(z-1)//2
n_P = p*(p-1)//2 + m*(m-1)//2
n_M = p * m

def count(n):
  ret = 0
  for i in P:
    ret += bisect(M,n/i)
  return ret

def count_p(n):
  ret = 0
  for i in P:
    ret += bisect(P,n/i)
    if i*i <= n:
      ret -= 1
  for i in M_rev:
    ret += bisect(M_rev,n/i)
    if i*i <= n:
      ret -= 1
  return ret//2


if n_M < K <= n_M+n_Z:
  print(0)
  exit()
  
if n_M >= K:
  l = -10**18
  r = -1
  while True:
    c = (l+r)//2
    if count(c) < K and count(c+1) >=K:
      break
    if count(c) >= K:
      r = c
    else:
      l = c+1
  print(c+1)
  exit()
  
else:
  K = K-(n_M+n_Z)
  l = 1
  r = 10**18
  while True:
    c = (l+r)//2
    if count_p(c) < K and count_p(c+1) >=K:
      break
    if count_p(c) >= K:
      r = c
    else:
      l = c+1
  print(c+1)
  exit()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
def countA(x):
    S, T = 0, 0
    for i in range(n):
        l, r = -1, n
        if A[i] > 0:
            while r - l > 1:
                mid = (r + l) // 2
                if A[i] * A[mid] <= x:
                    l = mid
                else:
                    r = mid
            S += l + 1
        elif A[i] < 0:
            while r - l > 1:
                mid = (r + l) // 2
                if A[i] * A[mid] <= x:
                    r = mid
                else:
                    l = mid
            S += n - r
        else: # A[i]==0
            if x >= 0:
                S += n
        if A[i] ** 2 <= x:
            T += 1
    return (S-T)/2

left, right = -10**18//2, 10**18//2
while right - left > 1:
    mid = (right+left) // 2
    if countA(mid) >= k:
        right = mid
    else:
        left = mid
print(right)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
def countA(x):
    S, T = 0, 0
    for i in range(n):
        l, r = -1, n
        if A[i] > 0:
            while r - l > 1:
                mid = (r + l) // 2
                if A[i] * A[mid] <= x:
                    l = mid
                else:
                    r = mid
            S += l + 1
        elif A[i] < 0:
            while r - l > 1:
                mid = (r + l) // 2
                if A[i] * A[mid] <= x:
                    r = mid
                else:
                    l = mid
            S += n - r
        else: # A[i]==0
            if x >= 0:
                S += n
        if A[i] ** 2 <= x:
            T += 1
    return S/2 + T

left, right = -10**18//2, 10**18//2
while right - left > 1:
    mid = (right+left) // 2
    if countA(mid) >= k:
        right = mid
    else:
        left = mid
print(right)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
def countA(x):
    S, T = 0, 0
    for i in range(n):
        l, r = -1, n
        if A[i] > 0:
            while r - l > 1:
                mid = (r + l) // 2
                if A[i] * A[mid] <= x:
                    l = mid
                else:
                    r = mid
            S += l + 1
        elif A[i] < 0:
            while r - l > 1:
                mid = (r + l) // 2
                if A[i] * A[mid] <= x:
                    r = mid
                else:
                    l = mid
            S += n - r
        else: # A[i]==0
            if x >= 0:
                S += n
        if A[i] ** 2 <= x:
            T += 1
    return S/2 + T

left, right = -A[-1]**2//2, A[-1]**2//2
while right - left > 1:
    mid = (right+left) // 2
    if countA(mid) >= k:
        right = mid
    else:
        left = mid
print(right)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import deque

n,k=map(int,input().split())
A=sorted(list(map(int,input().split())))

negs=[]
poss=[]
zers=0
for i in range(n):
    if A[i]<0:
        negs.append(A[i])
    elif A[i]>0:
        poss.append(A[i])
    else: zers+=1
q=len(negs)
w=len(poss)
pairedpos=q*(q-1)//2+w*(w-1)//2
pairedneg=q*w
pairedzero=zers*(n-zers)

ans=0
flg=0
if k<=pairedneg:
    flg=1
elif pairedneg<k<=pairedneg+pairedzero:
    ans=0
else: flg=2 

if flg==1:
    higher=0
    lower=-10**18
    for _ in range(60):
        cnt=0
        mid=(higher+lower)//2
        for i in range(len(poss)):
            idx=bisect_left(negs, -(-mid//poss[i]))
            cnt+=idx
        if cnt<=k-1:
            lower=mid
        else:
            higher=mid
    ans=lower

elif flg==2:
    from copy import deepcopy
    lower=0
    higher=10**18
    nnegs=[-negs[i] for i in range(len(negs))]
    nnegs=sorted(nnegs)
    nnegs=deque(nnegs)
    poss=deque(poss)
    for _ in range(60):
        newnegs=deepcopy(nnegs)
        possc=deepcopy(poss)
        cnt=0
        mid=(higher+lower)//2
        while newnegs:
            nn=newnegs.popleft()
            idx1=bisect_left(newnegs, -(-mid//nn))
            cnt+=idx1
        while possc:
            pp=possc.popleft()
            idx2=bisect_left(possc, -(-mid//pp))
            cnt+=idx2
        if cnt<=(k-pairedneg-pairedzero)-1:
            lower=mid
        else:
            higher=mid
    ans=lower
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
import sys
hu=[i for i in A if i<0]
sei=[i for i in A if i>0]
zero=[i for i in A if i==0]
l_hu=len(hu)
l_sei=len(sei)
l_zero=len(zero)
C=[]

if l_hu*l_sei>=K:
    for i in hu:
        for j in sei:
            C.append(i*j)
    print(sorted(C)[K-1])
    sys.exit()
if (l_hu+l_sei)*l_zero>=K:
    for i in (sei+hu):
        for j in zero:
            C.append(0)
    print(sorted(C)[K-1-l_hu*l_sei])
    sys.exit()
    
for k in [zero,hu,sei]:
    for i in range(len(k)):
        for j in range(i+1,len(k)):
            C.append(k[i]*k[j])
print(sorted(C)[K-1-l_hu*l_sei-(l_hu+l_sei)*l_zero])
sys.exit()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations
import bisect
def run():
    N, K, *A = list(map(int, read().split()))
    B = []
    C = []
    C_abs = []
    O = 0
    for a in A:
        if a == 0:
            O += 1
            continue
        if a > 0:
            B.append(a)
            continue
        C.append(a)
        C_abs.append(-a)
    B = sorted(B)
    C = sorted(C)
    C_abs = sorted(C_abs)
    n_neg = len(B) * len(C)
    n_0 = O * (O - 1) // 2 + O * (len(B) + len(C))

    def find(x):
        ret = 0
        if x < 0:
            for b in B:
                val = bisect.bisect_right(C, math.floor(x/b)) - 1
                ret += val + 1

        elif x == 0:
            ret += n_0 + n_neg
        else:
            ret += n_neg + n_0
            b_val = 0
            for i, b in enumerate(B):
                val = bisect.bisect_right(B[i+1:], math.floor(x/b)) - 1
                b_val += val + 1

            c_val = 0
            for i, c in enumerate(C_abs):
                val = bisect.bisect_right(C_abs[i+1:], math.floor(x/c)) - 1
                c_val += val + 1
            ret += (b_val + c_val)
        return ret

    high = 10 ** 18
    low = -high
    current = 0
    while high - low > 1:
        tmp = find(current)
        if tmp < K:
            low = current
        if tmp >= K:
            high = current

        current = (low + high) // 2


    print(high)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations
def run():
    N, K, *A = list(map(int, read().split()))
    B = []
    C = []
    C_abs = []
    O = 0
    for a in A:
        if a == 0:
            O += 1
            continue
        if a > 0:
            B.append(a)
            continue
        C.append(a)
        C_abs.append(-a)
    B = sorted(B)
    C = sorted(C)
    C_abs = sorted(C_abs)
    n_neg = len(B) * len(C)
    n_0 = O * (O - 1) // 2 + O * (len(B) + len(C))

    def find(x):
        ret = 0
        if x < 0:
            for b in B:
                val = lower_bound(C, math.floor(x/b))
                if val == None:
                    val = -1
                ret += val + 1

        elif x == 0:
            ret += n_0 + n_neg
        else:
            ret += n_neg + n_0
            b_val = 0
            for i, b in enumerate(B):
                val = lower_bound(B[i+1:], math.floor(x/b))
                if val == None:
                    val = -1
                b_val += val + 1

            c_val = 0
            for i, c in enumerate(C_abs):
                val = lower_bound(C_abs[i+1:], math.floor(x/c))
                if val == None:
                    val = -1
                c_val += val + 1
            ret += (b_val + c_val)
        return ret

    def lower_bound(arr, x, same_val = True):
        """
        return the most idx,such that a[idx] <=(<) n
        Note: arr must be sorted.(e.g. [1,3,5,6,7,11....])
        """
        if arr == []: return None
        low = 0
        high = len(arr)-1
        current = (low + high) // 2
        if arr[0] > x:return None
        if arr[-1] < x:return high


        if same_val:
            if high == 0:
                if arr[0] <= x:
                    return 0
                else:
                    return None
            if high == 1:
                if arr[0] <= x < arr[1]:
                    return 0
                else:
                    return 1
            while high - low > 1:
                if arr[current] > x:
                    high = current
                if arr[current] <= x:
                    low = current
                current = (high + low) // 2
            return low

        if not same_val:
            if high == 0:
                if arr[0] < x:
                    return 0
                else:
                    return None
            if high == 1:
                if arr[0] >= x:return None
                if arr[0] < x <= arr[1]:
                    return 0
                else:
                    return 1
            while high - low > 1:
                if arr[current] >= x:
                    high = current
                if arr[current] < x:
                    low = current
                current = (high + low) // 2
            return low





    high = 10 ** 18
    low = -high
    current = 0
    while high - low > 1:
        tmp = find(current)
        if tmp < K:
            low = current
        if tmp >= K:
            high = current

        current = (low + high) // 2


    print(high)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))

    c = [[] for _ in range(3)]

    for ai in a:
        if ai < 0:
            c[0].append(ai)
        elif ai == 0:
            c[1].append(ai)
        elif ai > 0:
            c[2].append(ai)

    c0 = len(c[0])
    c1 = len(c[1])
    c2 = len(c[2])

    index = [c0 * c2, c1 * (c0 + c2) + c1 * (c1 - 1) // 2, c0 * (c0 - 1) // 2 + c2 * (c2 - 1) // 2]

    if 0 <= k < index[0]:
        tmp = []
        for i in c[0]:
            for j in c[2]:
                tmp.append(i * j)
        tmp.sort()
        print(tmp[k - 1])
    elif index[0] <= k < index[0] + index[1]:
        print(0)
    elif index[0] + index[1] <= k < index[0] + index[1] + index[2]:
        tmp = []
        for i in range(c0):
            for j in range(i + 1, c0):
                tmp.append(c[0][i] * c[0][j])
        for i in range(c2):
            for j in range(i + 1, c2):
                tmp.append(c[2][i] * c[2][j])
        tmp.sort()
        print(tmp[k - index[0] - index[1] - 1])


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right

def solve():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))

    INF = 10 ** 18

    negative_end = bisect_left(A, 0)
    positive_start = bisect_right(A, 0)

    positive_cnt = N - positive_start
    negative_cnt = negative_end
    zero_cnt = N - (positive_cnt + negative_cnt)

    negative_pairs_cnt = positive_cnt * negative_cnt
    zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

    negativeArray = A[0:negative_end]
    positiveArray = A[positive_start:]

    def negativeJudge(n: int):
        #print("n", n)
        count = 0
        for neg in reversed(range(0, negative_cnt)):
            for pos in range(0, positive_cnt):
                #print(negativeArray[neg] * positiveArray[pos])
                if negativeArray[neg] * positiveArray[pos] > n:
                    break
                count += 1
        #print("count", count)
        return count >= K

    def positiveJudge(n: int):
        count = 0
        for pos1 in range(0, positive_cnt - 1):
            for pos2 in range(pos1 + 1, positive_cnt):
                if positiveArray[pos1] * positiveArray[pos2] > n:
                    break
                count += 1

        for neg1 in reversed(range(0, negative_cnt - 1)):
            for neg2 in reversed(range(neg1 + 1, negative_cnt)):
                if negativeArray[neg1] * negativeArray[neg2] > n:
                    break
                count += 1

        return count >= K - negative_pairs_cnt - zero_pairs_cnt

    def binSearch(lb: int, ub: int, fn: "function"):
        while abs(lb - ub) > 1:
            mid = (lb + ub) // 2
            if fn(mid):
                ub = mid
            else:
                lb = mid
            #print(lb, ub)
        return ub

    # 答えが負の場合
    if K <= negative_pairs_cnt:
        print(binSearch(-INF, 0, negativeJudge))

    # 答えが0の場合
    elif K <= negative_pairs_cnt + zero_pairs_cnt:
        print(0)

    # 答えが正の場合
    else:
        print(binSearch(0, INF, positiveJudge))


def main():
    solve()
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

negativeArray = A[0:negative_end]
positiveArray = A[positive_start:]

def negativeJudge(n: int):
        count = 0
        for a in positiveArray:
            maxb = n // a
            count += bisect_right(negativeArray, maxb)
        #print("count:", count)
        return count >= K

def positiveJudge(n: int):
    #print("n", n)
    count = 0
    for a in positiveArray:
        maxb = n // a
        count += bisect_right(positiveArray, maxb)
        if maxb >= a:
            count -= 1
    #print("c", count)
    for a in negativeArray:
        maxb = n // a
        count += negative_cnt - bisect_left(negativeArray, maxb)
        #print("l", len(negA) - bisect_left(negA, maxb))
        if maxb <= a:
            count -= 1
    #print("c", count)
    count //= 2
    #print("count:", count)
    return count >= K - negative_pairs_cnt - zero_pairs_cnt

def binSearch(lb: int, ub: int, fn: "function"):
    while abs(lb - ub) > 1:
        mid = (lb + ub) // 2
        if fn(mid):
            ub = mid
        else:
            lb = mid
        #print(lb, ub)
    return ub

# 答えが負の場合
if K <= negative_pairs_cnt:
    ok, ng = 0, -10 ** 18
    print(binSearch(ng, ok, negativeJudge))

# 答えが0の場合
elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

# 答えが正の場合
else:
    ok, ng = 10 ** 18, 0
    print(binSearch(ng, ok, positiveJudge))

Submission status: Wrong Answer

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

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

negativeArray = A[0:negative_end]
positiveArray = A[positive_start:]

def negativeJudge(n: int):
        count = 0
        for a in positiveArray:
            maxb = n // a
            count += bisect_right(negativeArray, maxb)
        #print("count:", count)
        return count >= K

def positiveJudge(n: int):
    #print("n", n)
    count = 0
    for a in positiveArray:
        maxb = n // a
        count += bisect_right(positiveArray, maxb)
        if maxb >= a:
            count -= 1
    #print("c", count)
    for a in negativeArray:
        maxb = n // a
        count += negative_cnt - bisect_left(negativeArray, maxb)
        #print("l", len(negA) - bisect_left(negA, maxb))
        if maxb <= a:
            count -= 1
    #print("c", count)
    count //= 2
    #print("count:", count)
    return count >= K - negative_pairs_cnt - zero_pairs_cnt

def binSearch(lb: int, ub: int, fn: "function"):
    while abs(lb - ub) > 1:
        mid = (lb + ub) // 2
        if fn(mid):
            ub = mid
        else:
            lb = mid
        #print(lb, ub)
    return ub

# 答えが負の場合
if K <= negative_pairs_cnt:
    ok, ng = 0, -10 ** 18
    print(binSearch(ng, ok, negativeJudge))

# 答えが0の場合
elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

# 答えが正の場合
else:
    ok, ng = 10 ** 18, 0
    print(binSearch(ng, ok, negativeJudge))

Submission status: Wrong Answer

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

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

def negativeJudge(n: int):
        count = 0
        for a in A[positive_start:-1]:
            maxb = n // a
            count += bisect_right(A[0:negative_end + 1], maxb)
        #print("count:", count)
        return count >= K

def positiveJudge(n: int):
    #print("n", n)
    count = 0
    for a in A[positive_start:-1]:
        maxb = n // a
        count += bisect_right(A[positive_start:-1], maxb)
        if maxb >= a:
            count -= 1
    #print("c", count)
    for a in A[0:negative_end + 1]:
        maxb = n // a
        count += negative_cnt - bisect_left(A[0:negative_end + 1], maxb)
        #print("l", len(negA) - bisect_left(negA, maxb))
        if maxb <= a:
            count -= 1
    #print("c", count)
    count //= 2
    #print("count:", count)
    return count >= K - negative_pairs_cnt - zero_pairs_cnt

def binSearch(lb: int, ub: int, fn: "function"):
    while abs(lb - ub) > 1:
        mid = (lb + ub) // 2
        if fn(mid):
            ub = mid
        else:
            lb = mid
        #print(lb, ub)
    return ub

# 答えが負の場合
if K <= negative_pairs_cnt:
    ok, ng = 0, -10 ** 18
    print(binSearch(ng, ok, negativeJudge))

# 答えが0の場合
elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

# 答えが正の場合
else:
    ok, ng = 10 ** 18, 0
    print(binSearch(ng, ok, negativeJudge))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_right, bisect_left

def solve(N: int, K: int, A: "List(int)"):
    A = sorted(A)
    posA = []
    zeroA = []
    negA = []
    MAX = max(A[-1] * A[-2], A[0] * A[1]) + 1
    MIN = A[-1] * A[0] - 1
    #print(A)
    #print(MIN, MAX)

    for i in A:
        if i < 0:
            negA.append(i)
        elif i == 0:
            zeroA.append(i)
        else:
            posA.append(i)

    negmul = len(posA) * len(negA)
    posmul = (len(posA) * (len(posA) - 1) + len(negA) * (len(negA) - 1)) // 2
    zeromul = N * (N - 1) // 2 - negmul - posmul

    #print("num", negmul, zeromul, posmul, K - negmul - zeromul)
    #print("posA: ", posA)
    #print("negA: ", negA)
    def negativeJudge(n: int):
        count = 0
        for a in posA:
            maxb = n // a
            count += bisect_right(negA, maxb)
        #print("count:", count)
        return count >= K

    def positiveJudge(n: int):
        #print("n", n)
        count = 0
        for a in posA:
            maxb = n // a
            count += bisect_right(posA, maxb)
            if maxb >= a:
                count -= 1
        #print("c", count)
        for a in negA:
            maxb = n // a
            count += len(negA) - bisect_left(negA, maxb)
            #print("l", len(negA) - bisect_left(negA, maxb))
            if maxb <= a:
                count -= 1
        #print("c", count)
        count //= 2
        #print("count:", count)
        return count >= K - negmul - zeromul

    def binSearch(lb: int, ub: int, fn: "function"):
        while abs(lb - ub) > 1:
            mid = (lb + ub) // 2
            if fn(mid):
                ub = mid
            else:
                lb = mid
            #print(lb, ub)
        return ub

    if K <= negmul:
        print(binSearch(MIN, MAX, negativeJudge))
    elif K <= zeromul:
        print(0)
    else:
        print(binSearch(MIN, MAX, positiveJudge))
        

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]
    solve(N, K, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())  #数字
A = map(int, input().split())  #数字

A = sorted(A, reverse=False)
import bisect
tmp = bisect.bisect_left(A,0)

C = A[:tmp]#負の数
D = A[tmp:]#正の数
D = D[::-1]

#print(C)
#print(D)

B = []#負の数×正の数
cou = 0
E = 0
for i in range(len(C)):
    if E == 1:
        break
    for j in range(len(D)):
        B.append(C[i] * D[j])
        cou += 1
        if cou == K:
            E = 1
            break

#print(B)
F = []#正数
cou2 = 0
G = []#負の数
cou3 = 0

if E == 0:
    D = D[::-1]
    for i in range(len(D)):
        if E == 1:
            break
        for j in range(i+1, len(D)):
            F.append(D[i] * D[j])
            cou2 += 1
            if cou + cou2 == K:
                E = 1
                break
    E = 0
    for i in range(len(C)):
        if E == 1:
            break
        for j in range(i+1, len(C)):
            G.append(C[i] * C[j])
            cou3 += 1
            if cou + cou3 == K:
                E = 1
                break

#print(F)
#print(G)

B = B + F + G
B = sorted(B, reverse=False)
#print(B)
#print(len(B))
print(B[K-1])