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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(x):
    cnt = 0
    if x < 0:
        j = p-1
        for i in range(m)[::-1]:
            while j >= 0 and plus[j]*minus[i] <= x:
                j -= 1
            cnt += m - j - 1
    else:
        j = 0
        for i in range(m)[::-1]:
            while j < m and minus[j]*minus[i] > x:
                j += 1
            cnt += max(0,i-j)
        j = p-1
        for i in range(p):
            while j >= 0 and plus[j]*plus[i] > x:
                j -= 1
            cnt += max(0,j-i)
        cnt += zero*(zero-1)//2 + m*p + zero*(m+p)
    
    return cnt >= k

n,k = LI()
a = LI()
a.sort()
minus = [x for x in a if x < 0]
plus = [x for x in a if x > 0]
m,p = len(minus),len(plus)
zero = bl(a,1) - br(a,-1)
ok,ng = 10**18,-10**18-1

while ok - ng > 1:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

Solution code:
import numpy as np
INF = 10**18

N, K = map(int,input().split())
a = np.array(list(map(int,input().split())))
a = np.sort(a)
l = -INF; r = INF

zero = a[a==0]
pos = a[a>0]
neg = a[a<0]


def f(x):
    c=0
    if(len(pos)*len(neg)>=K):   #積が負
        for po in pos:
            for ne in neg:
                if(po*ne < x):
                    c+=1
    else:    #積が正
        for i in range(len(pos)-1):
            for j in list(range(i+1,len(pos))):
                if(pos[i]*pos[j] < x):
                    c+=1

        for i in range(len(neg)-1):
            for j in list(range(i+1,len(neg))):
                if(neg[i]*neg[j] < x):
                    c+=1
        
        c += len(pos)*len(neg) + len(zero)*(len(pos)+len(neg))+((len(zero)*(len(zero)-1))//2)
        
        print(x,c)
    
    return c

if((len(pos)*len(neg)+len(zero)*(len(pos)+len(neg))+((len(zero)*(len(zero)-1))//2)>=K) & (len(pos)*len(neg)<K)):
    print(0)
    exit()
    
while r-l>1:
    x = (l+r)//2
    if f(x) >= K:
        r = x
    else:
        l = x
print(l)

Submission status: Wrong Answer

Solution code:
import numpy as np
INF = 10**18

N, K = map(int,input().split())
a = np.array(list(map(int,input().split())))
a = np.sort(a)
l = -INF; r = INF

zero = a[a==0]
pos = a[a>0]
neg = a[a<0]


def f(x):
    c=0
    if(len(pos)*len(neg)>=K):   #積が負
        for po in pos:
            for ne in neg:
                if(po*ne < x):
                    c+=1
    else:    #積が正
        for i in range(len(pos)-1):
            for j in list(range(i+1,len(pos))):
                if(pos[i]*pos[j] < x):
                    c+=1
        for i in range(len(neg)-1):
            for j in list(range(i+1,len(neg))):
                if(neg[i]*neg[j] < x):
                    c+=1

        c += len(pos)*len(neg) + len(zero)*(len(pos)+len(neg))+((len(zero)*(len(zero)-1))//2)
        
        print(x,c)
    
    return c

if((len(pos)*len(neg)+len(zero)*(len(pos)+len(neg))+((len(zero)*(len(zero)-1))//2)>=K) & (len(pos)*len(neg)<K)):
    print(0)
    exit()
    
while r-l>1:
    x = (l+r)//2
    if f(x) >= K:
        r = x
    else:
        l = x
print(l)

Submission status: Wrong Answer

Solution code:
def main():
  from bisect import bisect
  n,k,*a=map(int,open(0).read().split())
  a.sort()
  i=bisect(a,0)
  a,b=a[i:],a[i-1::-1]
  n,m=len(a),len(b)
  ok=10**18//2
  ng=-ok
  while ok-ng>1:
    x=(ok+ng)//2
    s=0
    if x>=0:
      i=n
      for y in a:
        while i and a[i-1]*y>x:i-=1   
        s+=i
        if y*y<=x:s-=1
      i=m
      for y in b:
        while i and b[i-1]*y>x:i-=1
        s+=i
        if y*y<=x:s-=1
      s=s//2+n*m
    else:
      i=m
      for y in a:
        while i and b[i-1]*y<=x:i-=1
        s+=m-i
    if s>=k:ok=x
    else:ng=x
  print(ok)
main()

Submission status: Wrong Answer

Solution code:
def main():
  from bisect import bisect
  n,k,*a=map(int,open(0).read().split())
  a.sort()
  i=bisect(a,0)
  a,b=a[i:],a[i-1::-1]
  n,m=len(a),len(b)
  ok=10**18
  ng=-ok
  while ok-ng>1:
    x=(ok+ng)//2
    s=0
    if x>0:
      s+=n*m
      t=0
      i=n
      for y in a:
        while i and a[i-1]*y>x:i-=1   
        t+=i
        if y*y<=x:t-=1
      s+=t//2
      t=0
      i=m
      for y in b:
        while i and b[i-1]*y>x:i-=1
        t+=i
        if y*y<=x:t-=1
      s+=t//2
    else:
      i=m
      for y in a:
        while i and b[i-1]*y<=x:i-=1
        s+=m-i
    if s>=k:ok=x
    else:ng=x
  print(ok)
main()

Submission status: Wrong Answer

Solution code:
def main():
  from bisect import bisect
  n,k,*a=map(int,open(0).read().split())
  a.sort()
  i=bisect(a,0)
  a,b,c=a[i:],a[:i],a[i-1::-1]
  n,m=len(a),len(b)
  ok=10**18
  ng=-ok
  while ok-ng>1:
    x=(ok+ng)//2
    s=0
    if x>0:
      s+=n*m
      t=0
      i=n
      for y in a:
        while i and a[i-1]*y>x:i-=1   
        t+=i
        if y*y<=x:t-=1
      s+=t//2
      t=0
      i=m
      for y in c:
        while i and c[i-1]*y>x:i-=1
        t+=i
        if y*y<=x:t-=1
      s+=t//2
    else:
      i=-1
      for y in a:
        while i+1<m and b[i+1]*y<=x:i+=1
        s+=i+1
    if s>=k:ok=x
    else:ng=x
  print(ok)
main()

Submission status: Wrong Answer

Solution code:
from bisect import*
def solve(x):
  s=t=0
  i=n
  j=0
  for y in a:
    while i and a[i-1]*y>x:i-=1
    while j+1<m and b[j+1]*y<=x:j+=1
    s+=j+1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  t=0
  i=m
  for y in c:
    while i and c[i-1]*y>x:i-=1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  return s
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bisect(t,0)
a,b,c=t[i:],t[:i],t[i-1::-1]
n,m=len(a),len(b)
ok=10**18
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if solve(mid)>=k:ok=mid
  else:ng=mid
print(ok)

Submission status: Wrong Answer

Solution code:
from bisect import*
def solve(x):
  s=t=0
  i=n
  for y in a:
    while i and a[i-1]*y>x:i-=1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  t=0
  i=m
  for y in c:
    while i and c[i-1]*y>x:i-=1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  i=m
  for y in a:
    while i and b[i-1]*y>x:i-=1
    s+=i
  return s
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bisect(t,0)
a,b,c=t[i:],t[:i],t[i-1::-1]
n,m=len(a),len(b)
ok=10**18
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if solve(mid)>=k:ok=mid
  else:ng=mid
print(ok)

Submission status: Wrong Answer

Solution code:
from bisect import*
def solve(x):
  s=0
  if x>0:
    s+=n*m
    t=0
    i=n
    for y in a:
      while i and a[i-1]*y>x:i-=1
      t+=i
      if y*y<=x:t-=1
    s+=t//2
    t=0
    i=m
    for y in c:
      while i and c[i-1]*y>x:i-=1
      t+=i
      if y*y<=x:t-=1
    s+=t//2
  else:
    i=m
    for y in a:
      while i and b[i-1]*y>x:i-=1
      s+=i
  return s
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bisect(t,0)
a,b,c=t[i:],t[:i],t[i-1::-1]
n,m=len(a),len(b)
ok=10**18+1
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if solve(mid)>=k:ok=mid
  else:ng=mid
print(ok)

Submission status: Wrong Answer

Solution code:
from bisect import*
def solve(x):
  s=0
  if x>0:
    s+=n*m
    t=0
    i=n
    for y in a:
      while i and a[i-1]*y>x:i-=1
      t+=i
      if y*y<=x:t-=1
    s+=t//2
    t=0
    i=m
    for y in c:
      while i and c[i-1]*y>x:i-=1
      t+=i
      if y*y<=x:t-=1
    s+=t//2
  else:
    i=m
    for y in a:
      while i and b[i-1]*y>x:i-=1
      s+=i
  return s
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bisect(t,0)
a,b,c=t[i:],t[:i],t[i-1::-1]
n,m=len(a),len(b)
ok=10**18
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if solve(mid)>=k:ok=mid
  else:ng=mid
print(ok)

Submission status: Wrong Answer

Solution code:
a = raw_input()
n, k = a.split()
n = int(n)
k = int(k)
b = raw_input()
data = [int(one) for one in b.split()]
res = []
for i in range(len(data) - 1):
  for j in range(1, len(data)):
    res.append(data[i]*data[j])
res = sorted(res)
print(res[k-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
from math import ceil

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

INF = 10**18 + 1

# x以下の個数がK未満か判定
def is_under_K(x:int):
    cnt = 0
    for i in range(N):
        if A[i]*A[i] <= x:
            cnt -= 1
        if A[i] == 0:
            cnt += N if x >= 0 else 0
            continue
        if A[i] < 0:
            tmp = ceil(x / A[i])
            pos = bisect_left(A, tmp)
            cnt += (N - pos)
        else:
            tmp = x // A[i]
            pos = bisect_right(A, tmp)
            cnt += pos
    cnt //= 2
    return cnt < K

def main():
    ok = -INF
    ng = INF
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        if is_under_K(X):
            ok = X
        else:
            ng = X

    print(ng)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
from math import ceil

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

INF = 10**18 + 1

# x以下の個数がK未満か判定
def is_under_K(x:int):
    cnt = 0
    # 676 753
    for i in range(N):
        if A[i]*A[i] <= x:
            cnt -= 1
        if A[i] == 0:
            cnt += N if x >= 0 else 0
            continue
        if A[i] < 0:
            tmp = ceil(x / A[i])
            pos = bisect_left(A, tmp)
            cnt += (N - pos)
        else:
            tmp = x // A[i]
            pos = bisect_right(A, tmp)
            cnt += pos
    cnt //= 2
    return cnt < K

def main():
    ok = -INF
    ng = INF
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        if is_under_K(X):
            ok = X
        else:
            ng = X

    print(ng)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
stdin = open(0)

N,K = map(int,input().split())
A = np.array([int(Ai) for Ai in input().split()])
A = np.sort(A)

maxA = max(np.abs(A))

z = A[A==0]
p = A[A>0]
n = A[A<0]

def check(x):
    ret = 0
    if x >= 0:
        ret += N*len(z)
    ret += np.searchsorted(A,x//p,side='right').sum()
    ret += (N - np.searchsorted(A, -(x // -n), side='right')).sum()
#     ret += (N-np.searchsorted(A,np.ceil(x/n))).sum()
    ret -= np.count_nonzero(A*A<=x)
    return ret//2;

ub = maxA*maxA
lb = -ub-1
while ub-lb > 1:
    mid = (ub+lb)>>1
    if check(mid) < K:
        lb = mid
    else:
        ub = mid
print(ub)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
stdin = open(0)

N,K = map(int,input().split())
A = np.array([int(Ai) for Ai in input().split()])
A = np.sort(A)

maxA = max(np.abs(A))

z = A[A==0]
p = A[A>0]
n = A[A<0]

def check(x):
    ret = 0
    if x >= 0:
        ret += N*len(z)
    ret += np.searchsorted(A,x//p,side='right').sum()
    ret += (N - np.searchsorted(A, (x+n-1) // n, side='right')).sum()
#     ret += (N-np.searchsorted(A,np.ceil(x/n))).sum()
    ret -= np.count_nonzero(A*A<=x)
    return ret//2;

ub = maxA*maxA
lb = -ub-1
while ub-lb > 1:
    mid = (ub+lb)>>1
    if check(mid) < K:
        lb = mid
    else:
        ub = mid
print(ub)

Submission status: Wrong Answer

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


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

    A.sort()

    # 負数、 0数、 正数
    Ns = 0
    Zs = bisect_left(A, 0)
    Ps = bisect_left(A, 1)

    # print(Ns, Zs, Ps)
    lneg = Zs-Ns
    lzer = Ps-Zs
    lpos = N-Ps
    # print(lneg, lzer, lpos)

    prod_neg = lneg * lpos
    prod_zero = lzer * (lneg+lpos)+lzer*(lzer-1)//2
    # prod_pos = lneg*(lneg-1)//2 + lpos*(lpos-1)//2
    # print(prod_neg, prod_zero, prod_pos)

    if prod_neg >= K:
        # 二分探索
        left = A[0]*A[-1]
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            # しゃくとり法
            counter = 0
            ps = Ps
            for ns in range(Ns, Zs):
                while ps < N and A[ns]*A[ps] > mid:
                    ps += 1
                if ps == N:
                    break
                counter += N-ps
            # print("{} in [{}, {}] ==> {}".format(mid, left, right, counter))
            if counter < K:
                left = mid
            else:
                right = mid
        print(right)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        KK = K-prod_neg-prod_zero
        # 二分探索
        left = 0
        right = max(A[0]**2, A[-1]**2)
        while right - left > 1:
            mid = (left + right)//2
            # しゃくとり法
            counter = 0
            end = N-1
            for start in range(Ps, N):
                while end >= start and A[start]*A[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
            start = 0
            for end in range(Zs-1, -1, -1):
                while end >= start and A[start]*A[end] >= mid:
                    start += 1
                if end <= start:
                    break
                counter += end-start
            if counter < KK:
                left = mid
            else:
                right = mid
        print(left)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def nC2(n):
    return n * (n-1) // 2

n,k = get_nums_l()
aaa = get_nums_l()

negatives = []
zeros = 0
positives = []

for a in aaa:
    if a == 0:
        zeros += 1
    elif a > 0:
        positives.append(a)
    else:
        negatives.append(a)

# 絶対値小さい順
positives.sort()
negatives.sort(reverse=True)

len_positives = len(positives)
len_negatives = len(negatives)

p_zeros = zeros*(len_negatives+len_positives) + nC2(zeros)
p_positives = nC2(len_positives) + nC2(len_negatives)
p_negatives = len_positives * len_negatives

log(len_negatives, zeros, len_positives)
log(p_negatives, p_zeros, p_positives)

if p_negatives < k <= (p_negatives+p_zeros):
    print(0)
    exit()

if k <= p_negatives:
    # 負の場合
    nokori = k
    log("nokori", nokori)

    left = -1 * ((10**9)**2 + 1)
    right = -1

    # 積がcenter未満になるペアがnokori個未満になる最大のcenterを探す
    while left < right:
        center = (left+right+1) // 2
        log("center", center)

        left2 = len_positives-1
        right2 = len_negatives-1

        count = 0

        while right2 > 0 and positives[left2] * negatives[right2] < center:
            right2 -= 1
        
        log("right2", right2)

        while 0<=left2<len_positives and 0<=right2<len_negatives:
            log(positives[left2] * negatives[right2])
            if positives[left2] * negatives[right2] < center:
                count += len_negatives - right2
                left2 -= 1
            else:
                right2 += 1

        # left2 = len_positives-1
        # right2 = len_negatives-1

        # while left2 > 0 and positives[left2] * negatives[right2] < center:
        #     left2 -= 1
        # while right2 >= 0 and left2 < len_positives and (len_positives-left2 < len_negatives-right2):
        #     log(positives[left2] * negatives[right2])
        #     if positives[left2] * negatives[right2] < center:
        #         count += len_positives - left2
        #         right2 -= 1
        #     else:
        #         left2 += 1
        
        log("count", count)
        if count < nokori:
            left = center
        else:
            right = center - 1
    print(left)
    exit()

# 正の場合
nokori = k - p_negatives - p_zeros
log("nokori", nokori)

left = 1
right = (10**9)**2 + 1

# 積がcenter未満になるペアがnokori個未満になる最大のcenterを探す
while left < right:
    center = (left+right) // 2
    # log("center", center)

    left2 = 0
    right2 = len_positives-1

    count = 0

    while left2 < right2:
        if positives[left2] * positives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    left2 = 0
    right2 = len_negatives-1

    while left2 < right2:
        if negatives[left2] * negatives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1
    
    if count < nokori:
        left = center + 1
    else:
        right = center
print(center)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
stdin = open(0)

N,K = map(int,input().split())
A = np.array([int(Ai) for Ai in input().split()])
A = np.sort(A)

maxA = max(np.abs(A))

z = A[A==0]
p = A[A>0]
n = A[A<0]

def check(x):
    ret = 0
    if x >= 0:
        ret += N*len(z)
    ret += np.searchsorted(A,x//p,side='right').sum()
    ret += (N-np.searchsorted(A,np.ceil(x/n))).sum()
    ret -= np.count_nonzero(A*A<=x)
    return ret//2;

ub = maxA*maxA
lb = -ub-1
while ub-lb > 1:
    mid = (ub+lb)>>1
    if check(mid) < K:
        lb = mid
    else:
        ub = mid
print(ub)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
stdin = open(0)

N,K = map(int,input().split())
A = np.array([int(Ai) for Ai in input().split()])
A = np.sort(A)

maxA = max(np.abs(A))

z = A[A==0]
p = A[A>0]
n = A[A<0]

def check(x):
    ret = 0
    if x >= 0:
        ret += N*len(z)
    ret += np.searchsorted(A,x//p,side='right').sum()
    ret += N*len(n)-np.searchsorted(A,np.ceil(x/n)).sum()
    ret -= np.count_nonzero(A*A<=x)
    return ret//2;

ub = maxA*maxA
lb = -ub-1
while ub-lb > 1:
    mid = (ub+lb)>>1
    if check(mid) < K:
        lb = mid
    else:
        ub = mid
print(ub)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


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

    A.sort()

    # 負数、 0数、 正数
    neg, zero, pos = [], [], []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a == 0:
            zero.append(a)
        else:
            pos.append(a)

    prod_neg = len(neg) * len(pos)
    prod_zero = len(zero) * (len(neg)+len(pos))+len(zero)*(len(zero)-1)//2
    # prod_pos = len(neg)*(len(neg)-1)//2 + len(pos)*(len(pos)-1)//2

    if prod_neg >= K:
        # 二分探索
        left = neg[0]*pos[-1]
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            # しゃくとり法
            counter = 0
            ps = 0
            for ns in range(len(neg)):
                while ps < len(pos) and neg[ns]*pos[ps] > mid:
                    ps += 1
                if ps == len(pos):
                    break
                counter += len(pos)-ps
            if counter < K:
                left = mid
            else:
                right = mid
        print(right)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        KK = K-prod_neg-prod_zero
        # 二分探索
        left = 0
        right = 0
        if len(neg) > 0:
            right = max(neg[0]**2, right)
        if len(pos) > 0:
            right = max(pos[-1]**2, right)
        while right - left > 1:
            mid = (left + right)//2
            # しゃくとり法
            counter = 0
            end = len(pos)-1
            for start in range(len(pos)):
                while end >= start and pos[start]*pos[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
            start = 0
            for end in range(len(neg)-1, -1, -1):
                while end >= start and neg[start]*neg[end] >= mid:
                    start += 1
                if end <= start:
                    break
                counter += end-start
            if counter < KK:
                left = mid
            else:
                right = mid
        print(left)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    A.sort()

    # 負数、 0数、 正数
    neg, zero, pos = [], [], []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a == 0:
            zero.append(a)
        else:
            pos.append(a)

    prod_neg = len(neg) * len(pos)
    prod_zero = len(zero) * (len(neg)+len(pos))+len(zero)*(len(zero)-1)//2
    # prod_pos = len(neg)*(len(neg)-1)//2 + len(pos)*(len(pos)-1)//2

    if prod_neg >= K:
        # 二分探索
        left = neg[0]*pos[-1]
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            # しゃくとり法
            counter = 0
            ps = 0
            for ns in range(len(neg)):
                while ps < len(pos) and neg[ns]*pos[ps] > mid:
                    ps += 1
                if ps == len(pos):
                    break
                counter += len(pos)-ps
            if counter < K:
                left = mid
            else:
                right = mid
        print(right)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        KK = K-prod_neg-prod_zero
        # 二分探索
        left = 0
        right = 0
        if len(neg) > 0:
            right = max(neg[0]**2, right)
        if len(pos) > 0:
            right = max(pos[-1]**2, right)
        while right - left > 1:
            mid = (left + right)//2
            # しゃくとり法
            counter = 0
            end = len(pos)-1
            for start in range(len(pos)):
                while end >= start and pos[start]*pos[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
            start = 0
            for end in range(len(neg)-1, -1, -1):
                while end >= start and neg[start]*neg[end] >= mid:
                    start += 1
                if end <= start:
                    break
                counter += end-start
            if counter < KK:
                left = mid
            else:
                right = mid
        print(left)


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())),np.int64)
A = np.sort(A)

maxA = max(np.abs(A))


z = A[A==0]
p = A[A>0]
n = A[A<0]


def check(x):
    ret = 0
    if x >= 0:
        ret += N*len(z)
    ret += np.searchsorted(A,x//p,side='right').sum()
    ret += (N-np.searchsorted(A,x/n)).sum()
    ret -= len([a for a in A if a*a <= x])
    return ret//2;
        

ub = maxA*maxA
lb = -ub-1
while ub-lb > 1:
    mid = (ub+lb)>>1
    if check(mid) < K:
        lb = mid
    else:
        ub = mid
print(ub)

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)

pair_val_set = []
if num_minus_pair > K:
  for i in range(num_minus):
    for j in range(num_plus):
      pair_val_set.append(A[i]*A[num_minus+num_zero+j])
  pair_val_set = sorted(pair_val_set)
  print(pair_val_set[K-1])
else:
  if num_minus_pair+num_zero_pair > K:
    print(0)
  elif num_minus_pair+num_zero_pair+num_plus_pair > K:
    #for i in range(num_zero_pair):
    #  pair_val_set.append(0)
    #for i in range(num_minus):
    #  for j in range(num_plus):
    #    pair_val_set.append(A[i]*A[num_minus+num_zero+j])
    for i in range(num_minus):
      for j in range(i+1,num_minus):
        pair_val_set.append(A[i]*A[j])
    for i in range(num_plus):
      for j in range(i+1,num_plus):
        pair_val_set.append(A[num_minus+num_zero+i]*A[num_minus+num_zero+j])
    pair_val_set = sorted(pair_val_set)
    K = K - (num_minus_pair + num_zero_pair) - 1
    print(pair_val_set[K])

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)

pair_val_set = []
if num_minus_pair > K:
  for i in range(num_minus):
    for j in range(num_plus):
      pair_val_set.append(A[i]*A[num_minus+num_zero+j])
  pair_val_set = sorted(pair_val_set)
  print(pair_val_set[K-1])
else:
  if num_minus_pair+num_zero_pair > K:
    print(0)
  elif num_minus_pair+num_zero_pair+num_plus_pair > K:
    for i in range(num_zero_pair):
      pair_val_set.append(0)
    for i in range(num_minus):
      for j in range(num_plus):
        pair_val_set.append(A[i]*A[num_minus+num_zero+j])
    for i in range(num_minus):
      for j in range(i+1,num_minus):
        pair_val_set.append(A[i]*A[j])
    for i in range(num_plus):
      for j in range(i+1,num_plus):
        pair_val_set.append(A[num_minus+num_zero+i]*A[num_minus+num_zero+j])
    pair_val_set = sorted(pair_val_set)
    print(pair_val_set[K-1])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
#b1,b3はそれぞれ絶対値の大きい順に並ぶ
b1=sorted([i for i in a if i<0])
l1=len(b1)
b2=sorted([i for i in a if i==0])
l2=len(b2)
b3=sorted([i for i in a if i>0],reverse=True)
l3=len(b3)
def countk1(x,b11,b13):#x以下になるものの個数
    ret=0
    for i in range(l1):
        lx,rx=0,l3-1
        while lx+1<rx:
            if b13[(lx+rx)//2]*b11[i]<=x:
                lx=(lx+rx)//2
            else:
                rx=(lx+rx)//2
        if b13[rx]*b11[i]<=x:
            ret+=(rx+1)
        elif b13[lx]*b11[i]<=x:
            ret+=(lx+1)
    return ret

def countk2(x,b21,b23):
    #ここ数えすぎ
    ret=0
    for i in range(l1-1):
        lx,rx=i+1,l1-1
        while lx+1<rx:
            if b21[(lx+rx)//2]*b21[i]<=x:
                lx=(lx+rx)//2
            else:
                rx=(lx+rx)//2
        if b21[rx]*b21[i]<=x:
            ret+=(rx-i)
        elif b21[lx]*b21[i]<=x:
            ret+=(lx-i)
    for i in range(l3-1):
        lx,rx=i+1,l3-1
        while lx+1<rx:
            if b23[(lx+rx)//2]*b23[i]<=x:
                lx=(lx+rx)//2
            else:
                rx=(lx+rx)//2
        if b23[rx]*b23[i]<=x:
            ret+=(rx-i)
        elif b23[lx]*b23[i]<=x:
            ret+=(lx-i)
    return ret

if k<=l1*l3:
    l,r=b1[0]*b3[-1],-1
    while l+1<r:
        if countk1((l+r)//2,b1,b3)>=k: #k以上、数が存在するかどうか
            r=(l+r)//2
        else:
            l=(l+r)//2
    if countk1(l,b1,b3)==k:
        print(l)
    else:
        print(r)
elif k<=l1*l3+l2*(l1+l3)+(l2*(l2-1))//2:
    print(0)
else:
    k-=(l1*l3+l2*(l1+l3)+(l2*(l2-1))//2)
    l=1
    if l1>=2 and l3<2:
        r=b1[0]*b1[1]
    elif l1<2 and l3>=2:
        r=b3[0]*b3[1]
    else:
        r=max(b1[0]*b1[1],b3[0]*b3[1])
    while l+1<r:
        if countk2((l+r)//2,sorted(b1,reverse=True),sorted(b3))>=k: #k以上、数が存在するかどうか
            r=(l+r)//2
        else:
            l=(l+r)//2
    if countk2(l,sorted(b1,reverse=True),sorted(b3))==k:
        print(l)
    else:
        print(r)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
nA = [A[i] for i in range(N) if A[i] < 0]
Nn = len(nA)
pA = [A[i] for i in range(N) if A[i] > 0]
Np = len(pA)
N0 = A.count(0)

if Nn * Np >= K:
    def hantei1(f):
        p = Np-1
        n = 0
        res = 0
        while p >= 0:
            while n < Nn and pA[p]*nA[n] < f:
                n += 1
            res += n
            p -= 1
        if res < K:
            return True
        else:
            return False

    def nibun1(l, r):
        f = (l+r)//2
        res1 = hantei1(f)
        if not res1:
            return nibun1(l, f)
        res2 = hantei1(f+1)
        if not res2:
            return f
        return nibun1(f+1, r)

    print(nibun1(-(10**18), 0))

elif Nn * Np + N0*(Nn+Np) + (N*(N-1)//2) >= K:
    print(0)
else:
    K -= Nn * Np + N0*(Nn+Np) + (N*(N-1)//2)
    print(1)

Submission status: Wrong Answer

Solution code:
import bisect

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
nA = [A[i] for i in range(N) if A[i] < 0]
Nn = len(nA)
pA = [A[i] for i in range(N) if A[i] > 0]
Np = len(pA)
N0 = A.count(0)

if Nn * Np >= K:
    def hantei1(f):
        p = Np-1
        n = 0
        res = 0
        while p >= 0:
            while n < Nn and pA[p]*nA[n] < f:
                n += 1
            res += n
            p -= 1
        if res < K:
            return True
        else:
            return False

    def nibun1(l, r):
        f = (l+r)//2
        res1 = hantei1(f)
        if not res1:
            return nibun1(l, f)
        res2 = hantei1(f+1)
        if not res2:
            return f
        return nibun1(f+1, r)

    print(nibun1(-(10**18), 0))

elif Nn * Np + N0*(Nn+Np) + (N*(N-1)//2) >= K:
    print(0)
else:
    K -= Nn * Np + N0*(Nn+Np) + (N*(N-1)//2)
    print(1)