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:
#155d
import bisect
N,K = map(int, input().split())
A_list = [int(e) for e in input().split()]

#負・0・正の三つに分ける
A_list.sort(reverse=False)
zero_left = bisect.bisect_left(A_list,0)
zero_right = bisect.bisect_right(A_list,0)
A_list_minus = A_list[:zero_left]
A_list_zero = A_list[zero_left:zero_right]
A_list_plus = A_list[zero_right:]

#print("分割したリストの確認")
#print(A_list_minus)
#print(A_list_zero)
#print(A_list_plus)

#print("分割したリストのそれぞれの長さ")
#print("-",len(A_list_minus))
#print("0",len(A_list_zero))
#print("+",len(A_list_plus))

minus_num = len(A_list_minus)
zero_num = len(A_list_zero)
plus_num = len(A_list_plus)

#print("#multiplied#") #掛け算により出てくる数の個数
#print("-",minus_num * plus_num) #正*負
#print("0",int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2)) #ゼロ×any
#print("+",int(minus_num*(minus_num-1)/2 + plus_num*(plus_num-1)/2)) #負*負 or 正*正
#同じ種類同士の掛け算の場合は組み合わせなのでnC2
#異なる種類同士の掛け算の場合はmC1 * nC1

#尺取り法もどきで最終解答を求める
#小さい値同士で積算していき、Kを超えたら、次の値を試す。

if K <= minus_num * plus_num :
    multiplied_list = list()
    #答えは負の値となる
    for i in range(minus_num-1,-1,-1):
        X = A_list_minus[i]
        for j in range(plus_num-1,-1,-1):
            Y = A_list_plus[j]
            insert_place = bisect.bisect_right(multiplied_list,X*Y)
            if insert_place <= K:
                multiplied_list.insert(bisect.bisect_right(multiplied_list,X*Y),X*Y)    
            else:
                break
                
    print(multiplied_list[K-1])
    
elif minus_num * plus_num < K <= minus_num * plus_num + int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2):
    #答えは0
    print(0)
elif minus_num * plus_num + int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2) < K:
    #答えは正の値となる
    #マイナスと0の値の分を0で埋めておく
    multiplied_list = [0 for _ in range(minus_num * plus_num + int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2))]

    #まずマイナス同士から
    for i in range(minus_num-1):
        X = A_list_minus[i]
        for j in range(i+1,minus_num):
            Y = A_list_minus[j]
            insert_place = bisect.bisect_right(multiplied_list,X*Y)
            if insert_place <= K:
                multiplied_list.insert(bisect.bisect_right(multiplied_list,X*Y),X*Y)    
            else:
                break
                
    #次にプラス同士
    for i in range(plus_num-1):
        X = A_list_plus[i]
        for j in range(i+1,plus_num):
            Y = A_list_plus[j]
            insert_place = bisect.bisect_right(multiplied_list,X*Y)
            if insert_place <= K:
                multiplied_list.insert(bisect.bisect_right(multiplied_list,X*Y),X*Y)    
            else:
                break    
    
    print(multiplied_list[K-1])

Submission status: Wrong Answer

Solution code:
tot =  lambda n: n * (n-1) / 2

AMOUNT_NUMBERS, K = map(int, input().split())
neg, pos, zero = [], [], []

for i in input().split():
    i = int(i)
    if i < 0:
        neg.append(i)
    elif i > 0:
        pos.append(i)
    else:
        zero.append(i)

neg.sort()
pos.sort()

N, P, Z = len(neg), len(pos), len(zero)
if K <= N*P: # Negative numbers
    res = []
    for n_num in neg:
        for p_num in pos:
            res.append(n_num*p_num)
    res.sort()
    print(res[K-1])
elif K <= N * P + Z * (N+P+Z-1) / 2: # Zero
    print(0)
else:
    # Positive numbers
    # Ignore Z
    # Z ^
    res = []
    
    for i in range(N):
        for j in range(i+1, N):
            res.append(neg[i] * neg[j])

    for i in range(P):
        for j in range(i+1, P):
            res.append(pos[i] * pos[j])

    res.sort()
    K -= int(tot(AMOUNT_NUMBERS) - len(res))
    print(res[K-1])
    


# is the result 0 or lower
# is the result higher than 0?

Submission status: Wrong Answer

Solution code:
N,K  = map(int,input().split())
nums = list(map(int,input().split()))
# preprocess
#

nums.sort()



minus = [num for num in nums if num < 0]
minus.sort(reverse=True)
minus_count = len(minus)

plus =  [num for num in nums if num > 0]
plus.sort()
plus_count = len(plus)

zero_count = sum([1 for num in nums if num  == 0] )

zero_count  = zero_count * (minus_count  + plus_count)  + zero_count  *  (zero_count - 1) //2
temp = minus_count * (minus_count - 1) //2 + plus_count * (plus_count  - 1)//2 #正になるパターン数
minus_count = minus_count * plus_count
plus_count = temp
# print(plus_count,minus_count,zero_count)
acc = minus_count

def case_minus(): #plus * minus
    NG = -10 ** 18 - 1
    OK = -1
    m = (NG + OK) // 2  # mの候補に関して二分探索
    while OK - NG > 1:
        cot = 0
        # pn = [plus, minus]  # 積が正になるのは + *- o
        # minus.reverse()
        for num in plus:  # あるplusで固定したとき
            # そのnum(plus)と組み合わせられるminusはいくつあるか？

            ok_ind = -1
            ng_ind = len(minus)
            mid_ind = (ok_ind + ng_ind) // 2

            while ng_ind - ok_ind > 1:  # 2分探索で満たす個数を探す
                if minus[mid_ind] * num <= m:
                    ok_ind = mid_ind
                else:
                    ng_ind = mid_ind
                mid_ind = (ok_ind + ng_ind) // 2

            cot += (ok_ind + 1)  # 可能な個数
            # if num ** 2 <= m:
            #     cot -= 1
        # cot //= 2  # A * B と B * A のダブルカウント

        if cot >= K:  # あるmがOKなケース
            OK = m
        else:
            NG = m
        m = (OK + NG) // 2

    return OK

def case_plus():
    # K 番目の数m を考える
    # mはつまり、m以下の数がK個以上あるときの最少の値である

    NG =  -1
    OK =  10 ** 18 +  1
    m = (NG + OK)//2 #mの候補に関して二分探索
    while OK - NG > 1:
        cot  = 0
        pn = [plus,minus] #積が正になるのは-*- or +*+
        for temp in pn: # + と - の場合をそれぞれやってる
            for num in temp: #あるnumで固定したとき
                #そのnumと組み合わせられるbはいくつあるか？

                ok_ind = -1
                ng_ind = len(temp)
                mid_ind = (ok_ind + ng_ind) //2

                while ng_ind - ok_ind > 1: # 2分探索で満たす個数を探す
                    if temp[mid_ind] * num <= m:
                        ok_ind = mid_ind
                    else:
                        ng_ind = mid_ind
                    mid_ind = (ok_ind + ng_ind) // 2

                cot += (ok_ind + 1 ) #可能な個数
                if num ** 2 <= m:
                    cot -= 1
        cot //= 2  #A * B と B * A のダブルカウント

        if cot >= K: #あるmがOKなケース
            OK = m
        else:
            NG = m
        m = (OK + NG) // 2

    return OK

if K <= acc:#答えがマイナスの場合
    ans = case_minus()


elif K <= acc + zero_count:
    ans = 0

elif K <=acc + plus_count + zero_count:
    K  =  K - (minus_count + zero_count)
    ans = case_plus()


print(ans)

Submission status: Wrong Answer

Solution code:
N,K  = map(int,input().split())
nums = list(map(int,input().split()))
# preprocess
#

nums.sort()



minus = [num for num in nums if num < 0]
minus.sort(reverse=True)
minus_count = len(minus)

plus =  [num for num in nums if num > 0]
plus.sort()
plus_count = len(plus)

zero_count = sum([1 for num in nums if num  == 0] )

zero_count  = zero_count * (minus_count  + plus_count)  + zero_count  *  (zero_count - 1) //2
temp = minus_count * (minus_count - 1) //2 + plus_count * (plus_count  - 1)//2 #正になるパターン数
minus_count = minus_count * plus_count
plus_count = temp
# print(plus_count,minus_count,zero_count)
acc = minus_count

def case_minus(): #plus * minus
    NG = -10 ** 22 - 1
    OK = 10 ** 22 + 1
    m = (NG + OK) // 2  # mの候補に関して二分探索
    while OK - NG > 1:
        cot = 0
        # pn = [plus, minus]  # 積が正になるのは + *- o
        # minus.reverse()
        for num in plus:  # あるplusで固定したとき
            # そのnum(plus)と組み合わせられるminusはいくつあるか？

            ok_ind = -1
            ng_ind = len(minus)
            mid_ind = (ok_ind + ng_ind) // 2

            while ng_ind - ok_ind > 1:  # 2分探索で満たす個数を探す
                if minus[mid_ind] * num <= m:
                    ok_ind = mid_ind
                else:
                    ng_ind = mid_ind
                mid_ind = (ok_ind + ng_ind) // 2

            cot += (ok_ind + 1)  # 可能な個数
            # if num ** 2 <= m:
            #     cot -= 1
        # cot //= 2  # A * B と B * A のダブルカウント

        if cot >= K:  # あるmがOKなケース
            OK = m
        else:
            NG = m
        m = (OK + NG) // 2

    return OK

def case_plus():
    # K 番目の数m を考える
    # mはつまり、m以下の数がK個以上あるときの最少の値である

    NG = -10 ** 22 - 1
    OK =  10 ** 22 +  1
    m = (NG + OK)//2 #mの候補に関して二分探索
    while OK - NG > 1:
        cot  = 0
        pn = [plus,minus] #積が正になるのは-*- or +*+
        for temp in pn: # + と - の場合をそれぞれやってる
            for num in temp: #あるnumで固定したとき
                #そのnumと組み合わせられるbはいくつあるか？

                ok_ind = -1
                ng_ind = len(temp)
                mid_ind = (ok_ind + ng_ind) //2

                while ng_ind - ok_ind > 1: # 2分探索で満たす個数を探す
                    if temp[mid_ind] * num <= m:
                        ok_ind = mid_ind
                    else:
                        ng_ind = mid_ind
                    mid_ind = (ok_ind + ng_ind) // 2

                cot += (ok_ind + 1 ) #可能な個数
                if num ** 2 <= m:
                    cot -= 1
        cot //= 2  #A * B と B * A のダブルカウント

        if cot >= K: #あるmがOKなケース
            OK = m
        else:
            NG = m
        m = (OK + NG) // 2

    return OK

if K <= acc:#答えがマイナスの場合
    ans = case_minus()


elif K <= acc + zero_count:
    ans = 0

elif K <=acc + plus_count + zero_count:
    K  =  K - (minus_count + zero_count)
    ans = case_plus()


print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = [int(i) for i in input().split()]

A = sorted(A)

B = []
C = []
D = []

for i in range(len(A)):
  if A[i] < 0:
    B.append(A[i])
  elif A[i] == 0:
    C.append(A[i])
  else:
    D.append(A[i])

b = len(B)
c = len(C)
d = len(D)

def f(n):
  if n <= 0:
    i = 0
    j = 0
    k = 0
    while i < b and j < d:
      if B[i]*D[j] > n:
        j += 1
      else:
        i += 1
        k += d-j
    return k
  
  elif n == 0:
    return (c*(c-1))//2 + b*c + b*d + c*d
  
  else:
    i = 0
    j = b-1
    k = 0
    while i < b and j > -1:
      if B[i]*B[j] > n:
        i += 1
        k += j+1
      else:
        j -= 1
    
    k = b**2-k
    
    i = 0
    j = d-1
    while i < d and j > -1:
      if D[i]*D[j] <= n:
        i += 1
        k += j+1
      else:
        j -= 1
        
    l = 0   
    for i in range(b):
      if B[i]**2 <= n:
        l += 1
        
    for i in range(d):
      if D[i]**2 <= n:
        l += 1
        
    return (k-l)//2 + (c*(c-1))//2 + b*c + b*d + c*d
  
l = - 10**18
h = 10**18

while l+1 < h:
  m = (l+h)//2
  if f(m) >= K:
    h = m
  else:
    l = m

print(m)

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
List=list(map(int,input().split()))
ans=[]
for i in range(a):
    for j in range(i+1,a):
        ans+=[List[i]*List[j]]
print(ans[b-1])

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
List=list(map(int,input().split()))
ans=[]
for i in range(a):
    for j in range(a):
        if i>=j:
            continue
        else:
            ans+=[List[i]*List[j]]
print(ans[b-1])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    nega, posi = [], []
    for i in a:
        if i < 0:
            nega.append(-i)
        else:
            posi.append(i)
    nega_len = len(nega)
    posi_len = len(posi)

    def check(n):
        total = 0
        for i in range(posi_len):
            if posi[i] == 0:
                continue
            else:
                a = n / posi[i]
            total += nega_len - bisect_left(nega, a)
            if total >= k:
                return True
        return False

    def check2(n):
        total = 0
        for i in range(posi_len):
            if p1[i] == 0:
                continue
            else:
                a = n / p1[i]
            total += posi_len - bisect_left(p2, a) - (i + 1)
            if total >= k:
                return True
        for i in range(nega_len):
            a = n / n1[i]
            total += nega_len - bisect_left(n2, a) - (i + 1)
            if total >= k:
                return True
        return False

    if nega_len*posi_len >= k:
        posi.sort()
        nega.sort(reverse=True)
        l = -1
        r = 10**20
        while r-l>1:
            mid = (l + r) // 2
            if check(mid):
                l = mid
            else:
                r = mid
        print(-l)
    else:
        p1 = sorted(posi, reverse=True)
        p2 = p1[::-1]
        n1 = sorted(nega, reverse=True)
        n2 = n1[::-1]
        l = -1
        r = 10**20
        k = n*(n-1)//2 - k + 1
        while r-l>1:
            mid = (l + r) // 2
            if check2(mid):
                l = mid
            else:
                r = mid
        print(l)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A == 0]
nega = A[A < 0]

# 積がx以下の組を求める
def check(x):
    count = 0  # 積がx以下の組
    if x >= 0:
        count += len(zero) * N  # zero * N
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += np.searchsorted(A, (-x - 1) // (-nega), side = 'right').sum()  # nega * N
    count -= np.count_nonzero(A * A <= x)  # 自分自身との組
    return count // 2  #重複を消す

# 二分探索
low = -10 ** 18
high = 10 ** 18
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid) < K:  # OK
        low = mid
    else:               # NG
        high = mid

print(high)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A == 0]
nega = A[A < 0]

# 積がx以下の組を求める
def check(x):
    count = 0  # 積がx以下の組
    if x >= 0:
        count += len(zero) * N  # zero * N
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += np.searchsorted(A, (-x - 1) // (-nega), side = 'left').sum()  # nega * N
    count -= np.count_nonzero(A * A <= x)  # 自分自身との組
    return count // 2  #重複を消す

# 二分探索
low = -10 ** 18
high = 10 ** 18
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid) < K:  # OK
        low = mid
    else:               # NG
        high = mid

print(high)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A == 0]
nega = A[A < 0]

# 積がx以下の組を求める
def check(x):
    count = 0  # 積がx以下の組
    if x >= 0:
        count += len(zero) * N  # zero * N
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += np.searchsorted(A, (-x - 1) // nega, side = 'left').sum()  # nega * N
    count -= np.count_nonzero(A * A <= x)  # 自分自身との組
    return count // 2  #重複を消す

# 二分探索
low = -10 ** 18
high = 10 ** 18
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid) < K:  # OK
        low = mid
    else:               # NG
        high = mid
        
print(high)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
A.sort()
posi = A[A > 0]
zero = A[A == 0]
nega = A[A < 0]

# x以下の数を求める
def check(x):
    count = 0  # 積がx以下の組
    if x >= 0:
        count += len(zero) * N  # zero * N
    count += np.searchsorted(A, x // posi, side = 'right').sum()  # posi * N
    count += np.searchsorted(A, (-x - 1) // nega, side = 'left').sum()  # nega * N
    count -= np.count_nonzero(A * A <= x)  # 自分自身との組
    return count // 2  #重複を消す

# 二分探索
low = -10 ** 18
high = 10 ** 18
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid) >= K:
        low = mid
    else:
        high = mid

print(low)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
import sys
import queue


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    N, K = read_values()
    A = read_list()
    A.sort()

    L = -(10 ** 18)
    R = 10 ** 18
    while L != R:
        M = (L + R) // 2
        t = 0
        for a in A:
            if a < 0:
                t += N - bisect.bisect_right(A, M // a)
            elif a == 0:
                t += N if M >= 0 else 0
            else:
                t += bisect.bisect_right(A, M // a)

            if a ** 2 <= M:
                t -= 1

        t //= 2

        if t < K:
            L = M + 1
        else:
            R = M
    print(R)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
for i in range(n):
  if arr[i]<0:
    nc+=1
  elif arr[i]==0:
    zc+=1
  else:
    pc+=1
ncc=nc*pc
zcc=zc*(nc+pc)+(zc*(zc-1))//2
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
if k<=ncc:
  arr1=[]
  arr2=[]
  for i in range(n):
    if arr[i]<0:
      arr1.append(-arr[i])
    elif arr[i]>0:
      arr2.append(arr[i])
  arr1=arr1[::-1]
  c1=len(arr1)
  c2=len(arr2)
  l=0
  r=10**18+1
  k=ncc-k
  while r-l!=1:
    mid=(l+r)//2
    cnt=0
    pos=c2-1
    for i in range(c1):
      while pos!=-1:
        if arr2[pos]>mid//arr1[i]:
          pos-=1
        else:
          break        
      cnt+=pos+1
    if cnt>k:
      r=mid
    else:
      l=mid
  print(-r)
elif k<=(ncc+zcc):
  print(0)
else:
  arr1=[]
  arr2=[]
  for i in range(n):
    if arr[i]<0:
      arr1.append(-arr[i])
    elif arr[i]>0:
      arr2.append(arr[i])
  arr1=arr1[::-1]
  c1=len(arr1)
  c2=len(arr2)
  l=0
  r=10**18+1
  k-=(ncc+zcc)
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    pos1=c1-1
    for i in range(c1):
      tmp=0
      while pos1!=-1:
        if arr1[pos1]>mid//arr1[i]:
          pos1-=1
        else:
          break
      tmp+=pos1+1
      if arr1[i]**2<mid:
        tmp-=1
      cnt1+=tmp
    cnt1=cnt1//2
    cnt2=0
    pos2=c2-1
    for i in range(c2):
      tmp=0
      while pos2!=-1:
        if arr2[pos2]>mid//arr2[i]:
          pos2-=1
        else:
          break
      tmp+=pos2+1
      if arr2[i]**2<mid:
        tmp-=1
      cnt2+=tmp
    cnt2=cnt2//2
    cnt=cnt1+cnt2
    if cnt>=k:
      r=mid
    else:
      l=mid
    print(r)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def count(x, li1, li2, p):
    cnt = 0
    now = len(li2)-1 if p else 0
    for ind, i in enumerate(li1):
        rng = range(now, -1, -1) if p else range(now, len(li2))
        for j in rng:
            if p and ind==j:
                continue
            if i*li2[j]<x:
                # print(cnt, ind, j)
                cnt += j+1 if p else len(li2)-j
                cnt -= 1 if p and ind<j else 0
                now = j
                break
        else:
            break
    return cnt//2 if p else cnt

def bisect(ok, ng, solve):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def p_solve(x):
    tmp = count(x, posi, posi, True)
    tmp += count(x, nega[::-1], nega[::-1], True)
    # print(x, tmp)
    return np*nn+nn*nz+nz*np+nz*(nz-1)//2+tmp < k

def n_solve(x):
    return count(x, nega, posi, False) < k


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
nega = a[:bisect_left(a, 0)]
posi = a[bisect_right(a, 0):]
np = len(posi)
nn = len(nega)
nz = n - np - nn
if k <= np*nn:
    ans = bisect(-10**18-1, 0, n_solve)
elif k <= np*nn+nn*nz+nz*np+nz*(nz-1)//2:
    ans = 0
else:
    ma = 0
    if len(nega)>1:
        ma = nega[-1]*nega[-2]
    if len(posi)>1 and ma<posi[-1]*posi[-2]:
        ma = posi[-1]*posi[-2]
    ans = bisect(1, ma+1, p_solve)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def count(x, li1, li2, p):
    cnt = 0
    now = len(li2)-1 if p else 0
    for ind, i in enumerate(li1):
        rng = range(now, -1, -1) if p else range(now, len(li2))
        for j in rng:
            if p and ind==j:
                continue
            if i*li2[j]<x:
                # print(cnt, ind, j)
                cnt += j+1 if p else len(li2)-j
                cnt -= 1 if p and ind<j else 0
                now = j
                break
        else:
            break
    return cnt//2 if p else cnt

def bisect(ok, ng, solve):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def p_solve(x):
    tmp = count(x, posi, posi, True)
    tmp += count(x, nega[::-1], nega[::-1], True)
    # print(x, tmp)
    return np*nn+nn*nz+nz*np+nz*(nz-1)//2+tmp < k

def n_solve(x):
    return count(x, nega, posi, False) < k


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
nega = a[:bisect_left(a, 0)]
posi = a[bisect_right(a, 0):]
np = len(posi)
nn = len(nega)
nz = n - np - nn
if k <= np*nn:
    ans = bisect(nega[0]*posi[-1]-1, 0, n_solve)
elif k <= np*nn+nn*nz+nz*np+nz*(nz-1)//2:
    ans = 0
else:
    ma = 0
    if len(nega)>1:
        ma = nega[-1]*nega[-2]
    if len(posi)>1 and ma<posi[-1]*posi[-2]:
        ma = posi[-1]*posi[-2]
    ans = bisect(1, ma+1, p_solve)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def count(x, li1, li2, p):
    cnt = 0
    now = len(li2)-1 if p else 0
    for ind, i in enumerate(li1):
        rng = range(now, -1, -1) if p else range(now, len(li2))
        for j in rng:
            if p and ind==j:
                continue
            if i*li2[j]<x:
                # print(cnt, ind, j)
                cnt += j+1 if p else len(li2)-j
                cnt -= 1 if p and ind<j else 0
                now = j
                break
        else:
            break
    return cnt//2 if p else cnt

def bisect(ok, ng, solve):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def p_solve(x):
    tmp = count(x, posi, posi, True)
    tmp += count(x, nega[::-1], nega[::-1], True)
    # print(x, tmp)
    return np*nn+nn*nz+nz*np+nz*(nz-1)//2+tmp < k

def n_solve(x):
    return count(x, nega, posi, False) < k


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
nega = a[:bisect_left(a, 0)]
posi = a[bisect_right(a, 0):]
np = len(posi)
nn = len(nega)
nz = n - np - nn
if k <= np*nn:
    ans = bisect(nega[0]*posi[-1], 0, n_solve)
elif k <= np*nn+nn*nz+nz*np+nz*(nz-1)//2:
    ans = 0
else:
    ma = 0
    if len(nega)>1:
        ma = nega[-1]*nega[-2]
    if len(posi)>1 and ma<posi[-1]*posi[-2]:
        ma = posi[-1]*posi[-2]
    ans = bisect(1, ma+1, p_solve)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def count(x, li1, li2, p):
    cnt = 0
    ng = len(li2) if p else -1
    for ind, i in enumerate(li1):
        if p:
            j = bisect(-1, ng, lambda xx:li2[xx]*i<x)
            if j==-1:
                break
            cnt += j if ind<j else j+1
            ng = j+1
            # print(cnt, ind, j)
        else:
            j = bisect(len(li2), ng, lambda xx:li2[xx]*i<x)
            if j==len(li2):
                break
            cnt += len(li2)-j
            ng = j-1
    return cnt//2 if p else cnt

def bisect(ok, ng, solve):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def p_solve(x):
    tmp = count(x, posi, posi, True)
    tmp += count(x, nega, nega, True)
    # print(x, tmp)
    return np*nn+nn*nz+nz*np+nz*(nz-1)//2+tmp < k

def n_solve(x):
    return count(x, nega, posi, False) < k


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
nega = a[:bisect_left(a, 0)]
posi = a[bisect_right(a, 0):]
np = len(posi)
nn = len(nega)
nz = n - np - nn
if k <= np*nn:
    ans = bisect(nega[0]*posi[-1], 0, n_solve)
elif k <= np*nn+nn*nz+nz*np+nz*(nz-1)//2:
    ans = 0
else:
    ma = 0
    if len(nega)>1:
        ma = nega[-1]*nega[-2]
    if len(posi)>1 and ma<posi[-1]*posi[-2]:
        ma = posi[-1]*posi[-2]
    ans = bisect(1, ma+1, p_solve)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def count(x, li1, li2, p):
    cnt = 0
    for ind, i in enumerate(li1):
        if p:
            j = bisect(-1, len(li2), lambda xx:li2[xx]*i<x)
            cnt += j if ind<j else j+1
            # print(cnt, ind, j)
        else:
            j = bisect(len(li2), -1, lambda xx:li2[xx]*i<x)
            cnt += len(li2)-j
    return cnt//2 if p else cnt

def bisect(ok, ng, solve):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def p_solve(x):
    tmp = count(x, posi, posi, True)
    tmp += count(x, nega, nega, True)
    # print(x, tmp)
    return np*nn+nn*nz+nz*np+nz*(nz-1)//2+tmp < k

def n_solve(x):
    return count(x, nega, posi, False) < k


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
nega = a[:bisect_left(a, 0)]
posi = a[bisect_right(a, 0):]
np = len(posi)
nn = len(nega)
nz = n - np - nn
if k <= np*nn:
    # ans = bisect(nega[0]*posi[-1], 0, n_solve)
    ans = bisect(-10**18-3, 0, n_solve)
elif k <= np*nn+nn*nz+nz*np+nz*(nz-1)//2:
    ans = 0
else:
    # ma = 0
    # if len(nega)>1:
    #     ma = nega[-1]*nega[-2]
    # if len(posi)>1 and ma<posi[-1]*posi[-2]:
    #     ma = posi[-1]*posi[-2]
    ans = bisect(0, 10**18+3, p_solve)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def count(x, li1, li2, p):
    cnt = 0
    now = len(li2)-1 if p else 0
    for ind, i in enumerate(li1):
        rng = range(now, -1, -1) if p else range(now, len(li2))
        for j in rng:
            if p and ind==j:
                continue
            if i*li2[j]<x:
                # print(cnt, ind, j)
                cnt += j+1 if p else len(li2)-j
                cnt -= 1 if p and ind<j else 0
                now = j
                break
        else:
            break
    return cnt//2 if p else cnt

def bisect(ok, ng, solve):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def p_solve(x):
    tmp = count(x, posi, posi, True)
    tmp += count(x, nega, nega, True)
    # print(x, tmp)
    return np*nn+nn*nz+nz*np+nz*(nz-1)//2+tmp < k

def n_solve(x):
    return count(x, nega, posi, False) < k


n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
nega = a[:bisect_left(a, 0)]
posi = a[bisect_right(a, 0):]
np = len(posi)
nn = len(nega)
nz = n - np - nn
if k <= np*nn:
    ans = bisect(nega[0]*posi[-1], 0, n_solve)
elif k <= np*nn+nn*nz+nz*np+nz*(nz-1)//2:
    ans = 0
else:
    ma = 0
    if len(nega)>1:
        ma = nega[-1]*nega[-2]
    if len(posi)>1 and ma<posi[-1]*posi[-2]:
        ma = posi[-1]*posi[-2]
    ans = bisect(1, ma+1, p_solve)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l

n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
p = bisect_left(A, 0)
an = A[:p]
ap = A[p:]

if k < p * (n - p):
    def helper(x):
        t = 0
        r = 0
        for p in ap:
            while t < len(an) and an[t] * p <= x:
                t += 1
            r += t
        return r < k
    l = binsearch(ap[-1] * an[0] - 1, 1, helper)
else:
    k -= p * (n - p)
    an.reverse()
    def helper(x):
        r = 0
        for a in [ap, an]:
            t = len(a) - 1
            for i, p in enumerate(a):
                if t <= i:
                    break
                while t > i and a[t] * p > x:
                    t -= 1
                r += t - i
            return r < k
    m = ap[-1]
    if an:
        m = max(m, -an[-1])
    l = binsearch(-1, m * m, helper)
print(l + 1)

Submission status: Wrong Answer

Solution code:
# 上からk番目の数がxである。
# xとなる数はk個以上　かつ　x＋1となる数はk-1個以下
# xとなる数がk個以上となるxの最大値
from bisect import bisect_left, bisect_right
import sys

input = sys.stdin.buffer.readline


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

ng = -5 * (10 ** 10)
ok = 5 * (10 ** 10)


def count(x):
    cnt = 0
    for i in range(n):
        a = A[i]
        if a > 0:
            gendo = x // a
            pos = bisect_right(A, gendo)
            cnt += pos
            if pos >= i + 1:
                cnt -= 1
        elif a < 0:
            gendo = (-x + (-a - 1)) // (-a)
            pos = bisect_left(A, gendo)
            cnt += n - pos
            if pos <= i:
                cnt -= 1
        else:
            if x < 0:
                cnt += 0
            else:
                cnt += n - 1
    return cnt // 2


# x = mid 以上のものをカウントしたい
while ok - ng > 1:
    mid = (ok + ng) // 2
    cnt = count(mid)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

print(ok)