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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)
print(num_minus_pair,num_zero_pair,num_plus_pair)
if num_minus_pair >= K:
  th0, th1 = min(A)*max(A), min(A)*max(A)/2
  pair_val_set = []
  count = 0
  while 1:
    for i in range(num_minus):
      for j in range(num_plus):
        val = A[i]*A[num_minus+num_zero+num_plus-1-j]
        if th0 <= val < th1:
          pair_val_set.append(val)
          count += 1
        else:
          break
    if count >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif count < K:
      th0 = th1
      #th1 /= th1 - th1/2
      th1 /= 2
elif num_minus_pair+num_zero_pair >= K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair >= K:
  th0 = 0.0
  th1 = 0.0
  val0 = A[0]*A[1]
  val1 = A[num_minus+num_zero+num_plus-2]*A[num_minus+num_zero+num_plus-1]
  if val0 > val1:    th1 = float(val0/2)
  else:              th1 = float(val1/2)
  K = K - (num_minus_pair + num_zero_pair)
  pair_val_set = []
  count = 0
  while 1:
    for i in range(num_minus):
      for j in range(i+1,num_minus):
        val = A[num_minus-1-i]*A[num_minus-1-j]
        if th0 <= val < th1:
          pair_val_set.append(val)
          count += 1
        else:
          break
    for i in range(num_plus):
      for j in range(i+1,num_plus):
        val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
        if th0 <= val < th1:
          pair_val_set.append(val)
          count += 1
        else:
          break
    if count >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif count < K:
      th0 = th1
      th1 = th1 + float((val0-th1)/2)

Submission status: Wrong Answer

Solution code:
import sys
first_line = True
for line in sys.stdin:
    #print(line)
    if first_line:
        N, K = line.split()
        N = int(N)
        K = int(K)
        first_line = False
    else:
        nums = list(map(int, line.split()))
        nums = sorted(nums)
        if nums[0] <= 0:
            if nums[-1] <= 0:
                left = nums[-1] * nums[-2]
                right = 1
            else:
                left = nums[0] * nums[-1]
                right = nums[-1] * nums[-2] + 1
        else:
            left = nums[0] * nums[1]
            right = nums[-1] * nums[-2] + 1

        while left < right - 1:
            # left always have less than K pairs
            mid = (left + right) // 2
            count = 0
            for i in range(N):
                if (nums[i] < 0):
                    l, r = -1, N
                    while (l < r-1):
                        m = (l+r)//2
                        if nums[m] * nums[i] < mid:
                            r = m
                        else:
                            l = m
                    count += (N-r)
                else:
                    l, r = -1, N
                    while (l<r-1):
                        m = (l+r)//2
                        if nums[m] *nums[i]<mid:
                            l = m
                        else:
                            r = m
                    count += r
                if nums[i] *nums[i] < mid:
                    count -= 1
            count /= 2
            if count < K:
                left = mid
            else:
                right = mid
        print(left)

Submission status: Wrong Answer

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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)
print(num_minus_pair,num_zero_pair,num_plus_pair)
if num_minus_pair >= K:
  th0, th1 = min(A)*max(A), min(A)*max(A)/2
  pair_val_set = []
  count = 0
  while 1:
    for i in range(num_minus):
      for j in range(num_plus):
        val = A[i]*A[num_minus+num_zero+num_plus-1-j]
        if th0 <= val < th1:
          pair_val_set.append(val)
          count += 1
        else:
          break
    if count >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif count < K:
      th0 = th1
      #th1 /= th1 - th1/2
      th1 /= 2
elif num_minus_pair+num_zero_pair >= K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair >= K:
  th0 = 0.0
  th1 = 0.0
  val0 = A[0]*A[1]
  val1 = A[num_minus+num_zero+num_plus-2]*A[num_minus+num_zero+num_plus-1]
  if val0 > val1:    th1 = float(val0/2)
  else:              th1 = float(val1/2)
  K = K - (num_minus_pair + num_zero_pair)
  pair_val_set = []
  count = 0
  print('K', K)
  while 1:
    for i in range(num_minus):
      for j in range(i+1,num_minus):
        val = A[num_minus-1-i]*A[num_minus-1-j]
        if th0 <= val < th1:
          print(i,j)
          pair_val_set.append(val)
          count += 1
        else:
          break
    for i in range(num_plus):
      for j in range(i+1,num_plus):
        val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
        if th0 <= val < th1:
          pair_val_set.append(val)
          count += 1
        else:
          break
    if count >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif count < K:
      th0 = th1
      th1 = th1 + float((val0-th1)/2)

Submission status: Wrong Answer

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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)
print(num_minus_pair,num_zero_pair,num_plus_pair)
if num_minus_pair >= K:
  th0, th1 = min(A)*max(A), min(A)*max(A)/2
  pair_val_set = []
  count = 0
  while 1:
    for i in range(num_minus):
      for j in range(num_plus):
        val = A[i]*A[num_minus+num_zero+j]
        if th0 <= val < th1:
          pair_val_set.append(val)
          count += 1
        else:
          break
    if count >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif count < K:
      th0 = th1
      #th1 /= th1 - th1/2
      th1 /= 2
elif num_minus_pair+num_zero_pair >= K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair >= K:
  th0 = 0.0
  th1 = 0.0
  val0 = A[0]*A[1]
  val1 = A[num_minus+num_zero+num_plus-2]*A[num_minus+num_zero+num_plus-1]
  if val0 > val1:    th1 = float(val0/2)
  else:              th1 = float(val1/2)
  K = K - (num_minus_pair + num_zero_pair)
  pair_val_set = []
  count = 0
  print('K', K)
  while 1:
    for i in range(num_minus):
      for j in range(i+1,num_minus):
        val = A[num_minus-1-i]*A[num_minus-1-j]
        if th0 <= val < th1:
          print(i,j)
          pair_val_set.append(val)
          count += 1
        else:
          break
    for i in range(num_plus):
      for j in range(i+1,num_plus):
        val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
        if th0 <= val < th1:
          pair_val_set.append(val)
          count += 1
        else:
          break
    if count >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif count < K:
      th0 = th1
      th1 = th1 + float((val0-th1)/2)

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


def main():
    N, K = list(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, 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)


main()

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


def main():
    N, K = list(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, 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(0, m * m, helper)
    print(l + 1)


main()

Submission status: Wrong Answer

Solution code:
import sys
first_line = True
for line in sys.stdin:
    #print(line)
    if first_line:
        N, K = line.split()
        N = int(N)
        K = int(K)
        first_line = False
    else:
        nums = list(map(int, line.split()))
        negative_count = 0
        positive_count = 0
        for num in nums:
            if num <0:
                negative_count += 1
            if num > 0:
                positive_count += 1
        zero_count = len(nums) - negative_count - positive_count
        n_res_count = negative_count  * positive_count
        p_res_count = negative_count * (negative_count-1)//2 + positive_count * (positive_count-1)//2
        z_res_count = N*(N-1)//2 - n_res_count - p_res_count
        nums = sorted(nums)

        if K <= n_res_count:
            # find in negative nums
            left = nums[0] * nums[-1]
            right = 0
            while left < right - 1:
                mid = (left + right) // 2
                count = 0
                for one in nums[:negative_count]:
                    for two in nums[(negative_count+zero_count):]:
                        if one * two <= mid:
                            count += 1
                        else:
                            break
                if count < K:
                    left = mid + 1
                else:
                    right = mid
            print(left)
        elif K <= n_res_count + z_res_count:
            print(0)
        else:
            K -= (n_res_count + z_res_count)
            left = 0
            right = max(nums[-1] * nums[-2], nums[0] * nums[1]) + 1
            while left < right - 1:
                count = 0
                mid = (left + right) // 2
                for i in range(negative_count+zero_count, len(nums) - 1):
                    for j in range(i+1, len(nums)):
                        one, two = nums[i], nums[j]
                        if one * two <= mid:
                            count += 1
                        else:
                            break
                for i in range(negative_count-1, 0, -1):
                    for j in range(i-1, -1, -1):
                        one, two = nums[i], nums[j]
                        if one * two <= mid:
                            count += 1
                        else:
                            break
                if count < K:
                    left = mid + 1
                else:
                    right = mid
            print(left)

Submission status: Wrong Answer

Solution code:
import numpy as np
# from numba import njit

# @njit('(i8,i8[:],i8[:])')
def solve1(m, minus, plus):
    minus = np.sort(minus)
    plus = np.sort(plus)[::-1]
    # ２分探索
    lo = minus[0] * plus[0]
    hi = minus[-1] * plus[-1]
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0
        j = minus.shape[0] - 1
        for i in range(plus.shape[0]):
            s = mid // plus[i]
            while j >= 0 and minus[j] < -s:
                j -= 1
            if j > -1:
                num += j + 1
            else:
                break
        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j = minus.shape[0] - 1
    res = minus[0] * plus[0]
    for i in range(plus.shape[0]):
        while j >= 0 and minus[j] * plus[i] > hi:
            j -= 1
        if j > -1:
            res = max(res, minus[j] * plus[i])
        else:
            break
    return res

# @njit('(i8,i8[:],i8[:])')
def solve2(m, minus, plus):
    minus = np.sort(minus)[::-1]
    plus = np.sort(plus)
    # ２分探索
    lo = 0
    hi = plus[-1] * plus[-2] if len(plus) > 1 else 0
    hi += minus[-1] * minus[-2] if len(minus) > 1 else 0
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0

        j1 = plus.shape[0] - 1
        if j1 > 0:
            for i in range(plus.shape[0]):
                s = mid // plus[i]
                while j1 >= 0 and plus[j1] > s:
                    j1 -= 1
                if j1 > i:
                    num += j1 - i

        j2 = minus.shape[0] - 1
        if j2 > 0:
            for i in range(minus.shape[0]):
                s = mid // -minus[i]
                while j2 >= 0 and minus[j2] < -s:
                    j2 -= 1
                if j2 > i:
                    num += j2 - i

        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j1 = plus.shape[0] - 1
    j2 = minus.shape[0] - 1
    res = 0
    if j1 > 0:
        for i in range(plus.shape[0]):
            while j1 >= 0 and plus[j1] * plus[i] > hi:
                j1 -= 1
            if j1 > i:
                res = max(res, plus[j1] * plus[i])
            else:
                break
    if j2 > 0:
        for i in range(minus.shape[0]):
            while j2 >= 0 and minus[j2] * minus[i] > hi:
                j2 -= 1
            if j2 > i:
                res = max(res, minus[j2] * minus[i])
            else:
                break
    return res


def main():
    N, K = [int(x) for x in input().split()]
    A = np.fromstring(input(), np.int64, sep=' ')
    minus = A[A < 0]
    zero = A[A == 0]
    plus = A[A > 0]

    n_zero = len(zero)
    p_minus = len(minus) * len(plus)
    p_zero = n_zero * (len(minus) + len(plus)) + n_zero * (n_zero - 1) // 2

    if K <= p_minus:
        ans = solve1(K, minus, plus)
        print(ans)
    elif K <= p_minus + p_zero:
        print(0)
    else:
        ans = solve2(K - p_minus - p_zero, minus, plus)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
 
 
n, k = map(lambda x: int(x), input().split())
a = list(map(lambda x: int(x), input().split()))
 
a.sort()
pos = bisect.bisect(a, 0)
 
def judge(cur):
    global n, k, a
    cnt, j = 0, 1
    for i in range(pos):
        while(j < len(a) and (i == j or a[i] * a[j] > cur)): j += 1
        if(j >= len(a)): break
        cnt += (len(a) - j)
 
    j = len(a) - 1
    for i in range(pos, len(a)):
        while(j > i and (i == j or a[i] * a[j] > cur)): j -= 1
        if(i >= j): break
        cnt += (j-i)
 
    if(cnt >= k): return True
    else: return False
 
 
l, r = int(-1e18), int(1e18)
while(l < r):
    m = (l+r)>>1
    if(judge(m)): r = m
    else: l = m + 1
 
if(judge(r) == False): r -= 1
print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np
# from numba import njit

# @njit('(i8,i8[:],i8[:])')
def solve1(m, minus, plus):
    minus = np.sort(minus)
    plus = np.sort(plus)[::-1]
    # ２分探索
    lo = minus[0] * plus[0]
    hi = minus[-1] * plus[-1]
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0
        j = minus.shape[0] - 1
        for i in range(plus.shape[0]):
            s = (mid - 1) // plus[i] + 1
            while j >= 0 and minus[j] < -s:
                j -= 1
            if j > -1:
                num += j + 1
            else:
                break
        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j = minus.shape[0] - 1
    res = minus[0] * plus[0]
    for i in range(plus.shape[0]):
        while j >= 0 and minus[j] * plus[i] > hi:
            j -= 1
        if j > -1:
            res = max(res, minus[j] * plus[i])
        else:
            break
    return res

# @njit('(i8,i8[:],i8[:])')
def solve2(m, minus, plus):
    minus = np.sort(minus)[::-1]
    plus = np.sort(plus)
    # ２分探索
    lo = 0
    hi = plus[-1] * plus[-2] if len(plus) > 1 else 0
    hi += minus[-1] * minus[-2] if len(minus) > 1 else 0
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0

        j1 = plus.shape[0] - 1
        if j1 > 0:
            for i in range(plus.shape[0]):
                s = (mid - 1) // plus[i] + 1
                while j1 >= 0 and plus[j1] > s:
                    j1 -= 1
                if j1 > i:
                    num += j1 - i

        j2 = minus.shape[0] - 1
        if j2 > 0:
            for i in range(minus.shape[0]):
                s = (mid - 1) // (-minus[i]) + 1
                while j2 >= 0 and minus[j2] < -s:
                    j2 -= 1
                if j2 > i:
                    num += j2 - i

        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j1 = plus.shape[0] - 1
    j2 = minus.shape[0] - 1
    res = 0
    if j1 > 0:
        for i in range(plus.shape[0]):
            while j1 >= 0 and plus[j1] * plus[i] > hi:
                j1 -= 1
            if j1 > i:
                res = max(res, plus[j1] * plus[i])
            else:
                break
    if j2 > 0:
        for i in range(minus.shape[0]):
            while j2 >= 0 and minus[j2] * minus[i] > hi:
                j2 -= 1
            if j2 > i:
                res = max(res, minus[j2] * minus[i])
            else:
                break
    return res


def main():
    N, K = [int(x) for x in input().split()]
    A = np.fromstring(input(), np.int64, sep=' ')
    minus = A[A < 0]
    zero = A[A == 0]
    plus = A[A > 0]

    n_zero = len(zero)
    p_minus = len(minus) * len(plus)
    p_zero = n_zero * (len(minus) * len(plus)) + n_zero * (n_zero - 1) // 2

    if K <= p_minus:
        ans = solve1(K, minus, plus)
        print(ans)
    elif K <= p_minus + p_zero:
        print(0)
    else:
        ans = solve2(K - p_minus - p_zero, minus, plus)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
# from numba import njit

# @njit('(i8,i8[:],i8[:])')
def solve1(m, minus, plus):
    minus = np.sort(minus)
    plus = np.sort(plus)[::-1]
    # ２分探索
    lo = minus[0] * plus[0]
    hi = minus[-1] * plus[-1]
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0
        j = minus.shape[0] - 1
        for i in range(plus.shape[0]):
            s = (mid - 1) // plus[i] + 1
            while j >= 0 and minus[j] < -s:
                j -= 1
            if j > -1:
                num += j + 1
            else:
                break
        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j = minus.shape[0] - 1
    res = minus[0] * plus[0]
    for i in range(plus.shape[0]):
        while j >= 0 and minus[j] * plus[i] > hi:
            j -= 1
        if j > -1:
            res = max(res, minus[j] * plus[i])
        else:
            break
    return res

# @njit('(i8,i8[:],i8[:])')
def solve2(m, minus, plus):
    minus = np.sort(minus)[::-1]
    plus = np.sort(plus)
    # ２分探索
    lo = 0
    hi = plus[-1] * plus[-2] if len(plus) > 1 else 0
    hi += minus[-1] * minus[-2] if len(minus) > 1 else 0
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0

        j1 = plus.shape[0] - 1
        if j1 > 0:
            for i in range(plus.shape[0]):
                s = (mid - 1) // plus[i] + 1
                while j1 >= 0 and plus[j1] > s:
                    j1 -= 1
                if j1 > i:
                    num += j1 - i

        j2 = minus.shape[0] - 1
        if j2 > 0:
            for i in range(minus.shape[0]):
                s = (mid - 1) // (-minus[i]) + 1
                while j2 >= 0 and minus[j2] > -s:
                    j2 -= 1
                if j2 > i:
                    num += j2 - i

        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j1 = plus.shape[0] - 1
    j2 = minus.shape[0] - 1
    res = 0
    if j1 > 0:
        for i in range(plus.shape[0]):
            while j1 >= 0 and plus[j1] * plus[i] > hi:
                j1 -= 1
            if j1 > i:
                res = max(res, plus[j1] * plus[i])
            else:
                break
    if j2 > 0:
        for i in range(minus.shape[0]):
            while j2 >= 0 and minus[j2] * minus[i] > hi:
                j2 -= 1
            if j2 > i:
                res = max(res, minus[j2] * minus[i])
            else:
                break
    return res


def main():
    N, K = [int(x) for x in input().split()]
    A = np.fromstring(input(), np.int64, sep=' ')
    minus = A[A < 0]
    zero = A[A == 0]
    plus = A[A > 0]

    n_zero = len(zero)
    p_minus = len(minus) * len(plus)
    p_zero = n_zero * (len(minus) * len(plus)) + n_zero * (n_zero - 1) // 2

    if K <= p_minus:
        ans = solve1(K, minus, plus)
        print(ans)
    elif K <= p_minus + p_zero:
        print(0)
    else:
        ans = solve2(K - p_minus - p_zero, minus, plus)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

it=0
for i in range(n):
  for j in range(i+1,n):
      lst.append(a[i]*a[j])

m=[i for i in lst if i<0]
z=[i for i in lst if i==0]
p=[i for i in lst if i>0]

if ((len(m)+len(z))<k):
  p.sort()
  print(p[k-len(m)-len(z)-1])
elif len(m)>k:
  m.sort()
  print(m[k])
else:
  print(0)

Submission status: Wrong Answer

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

for i, a in enumerate(A):
    if a >= 0:
        break
A_minus = A[:i]
A_plus = A[i:]
mi_len = len(A_minus)
pl_len = len(A_plus)

nl = mi_len * pl_len
pl = (pl_len * (pl_len - 1) + mi_len * (mi_len - 1)) // 2


def count_minor1(Th):
    A_m = list(reversed(A_minus))
    A_p = list(reversed(A_plus))
    start = 0
    count = 0
    for i in range(pl_len):
        for j in range(start, mi_len):
            if A_m[j] * A_p[i] < Th:
                start = j
                count += mi_len - j
                break
    return count


def count_minor2(Th):
    A_abs = A_plus
    L = len(A_abs)
    count = 0
    start = 0
    for i in range(L-1, -1, -1):
        for j in range(start, L):
            if A_abs[i] * A_abs[j] >= Th:
                if i <= j-1:
                    count += j - 1
                else:
                    count += j
                start = j
                break
        else:
            count += L-1
    A_abs = [abs(a) for a in A_minus]
    A_abs.sort()
    L = len(A_abs)
    start = 0
    for i in range(L-1, -1, -1):
        for j in range(start, L):
            if A_abs[i] * A_abs[j] >= Th:
                if i <= j-1:
                    count += j - 1
                else:
                    count += j
                start = j
                break
        else:
            count += L-1
    return count//2


if K <= nl:
    lower = -10**18+10
    upper = 0
    while upper-lower > 1:
        S = (lower + upper) // 2
        if count_minor1(S) > K:
            upper = S
        else:
            lower = S

else:
    K_ = K - nl
    upper = 10**18+10
    lower = 0
    while upper-lower > 1:
        S = (lower + upper) // 2
        if count_minor2(S) >= K_:
            upper = S
        else:
            lower = S
    print(lower)

Submission status: Wrong Answer

Solution code:
#aのリストの中で２つ選び積がb未満の組み合わせがいくつあるかを出力する
def ok(a,b):
    ans=0
    n=len(a)
    for i in range(n):
        l=0
        r=len(a)-1
        
        if(a[i]*a[i]<b):
            ans-=1
        
        if(a[i]<0):
            if(a[l]*a[i]<b):
                ans+=n
                
                continue
            if(a[r]*a[i]>=b):
                ans+=0
                continue
        
            while(l+1<r):
                middle=(l+r)//2
                if(a[i]*a[middle]<b):
                    r=middle
                else:
                    l=middle
            ans+=n-r
        else:
            
            if(a[r]*a[i]<b):
                ans+=n
                continue
            if(a[l]*a[i]>=b):
                ans+=0
                continue           
            while(l+1<r):
                middle=(l+r)//2
                if(a[i]*a[middle]<b):
                    l=middle
                else:
                    r=middle   
                    
            ans+=l+1

    ans/=2
    
    return ans
        

NK=list(map(int,input().split()))
N=NK[0]
K=NK[1]
A=list(map(int,input().split()))
A=sorted(A)
l=-10^18
r=10^18

while(l+1<r):
    middle=(l+r)//2
    if(ok(A,middle)<K):
        l=middle
    else:
        r=middle

print(l)