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:
from bisect import bisect_right,bisect_left
import sys
input = sys.stdin.readline

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in a:
  if i>0: ap.append(i)
  elif i<0: an.append(-i)
  else: zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
  exit(0)

if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
        mid=(ok+ng)//2
        cnt=0
        for i in an:
            if mid%i!=0: cnt+=np-bisect_left(ap,mid//i+1)
            else: cnt+=np-bisect_left(ap,mid//i)
        if cnt>=k: ok=mid
        else: ng=mid
    print(-ok)
    exit(0)

k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
ok=10**18
ng=0
exit(0)
while ok-ng>1:
    mid=(ok+ng)//2
    cnt1, cnt2=0, 0
    for i in ap:
        cnt1+=bisect_right(ap,mid//i)
        if i**2<=mid: cnt1-=1
    for i in an:
        cnt2+=bisect_right(an,mid//i)
        if i**2<=mid: cnt2-=1
    if cnt1//2+cnt2//2>=k: ok=mid
    else: ng=mid
    print(ok)

Submission status: Wrong Answer

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0: ap.append(a[i])
  elif a[i]<0: an.append(-a[i])
  else: zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
    print(0)
    exit()

ng, ok = 10**18, 0
if k<=np*nn:
    while ng-ok>1:
      mid, cnt =(ok+ng)//2, 0
      for i in range(nn):
        if mid%an[i]!=0: cnt+=np-bisect_left(ap,mid//an[i]+1)
        else: cnt+=np-bisect_left(ap,mid//an[i])
      if cnt>=k: ok=mid
      else: ng=mid
    print(-ok)
else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    while ok-ng>1:
      mid, cnt1, cnt2 = (ok+ng)//2, 0, 0
      if np>=2:
        for i in range(np):
          cnt1 += bisect_right(ap,mid//ap[i])
          if ap[i]**2<=mid: cnt1-=1
      if nn>=2:
        for i in range(nn):
          cnt2 += bisect_right(an,mid//an[i])
          if an[i]**2<=mid: cnt2-=1
      if cnt1//2+cnt2//2>=k: ok=mid
      else: ng=mid
    print(ok)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k=input().split()
n=int(n)
k=int(k)
a=list(map(int,input().split()))
a=np.array(a)
a.sort()

neg=a[a<0]
zero=a[a==0]
pos=a[a>0]
m=len(pos)*len(neg)
z=len(zero)*(len(neg)+len(pos))+len(zero)*(len(zero)-1)/2
p=len(pos)*(len(pos)-1)/2+len(neg)*(len(neg)-1)/2

def judge_m(x):
  s=0
  for i in pos:
    b=x//i
    s+=np.searchsorted(neg,b,side="right")
  return s>=k

def judge_p(x):
  s=0
  for i in pos:
    b=x//i
    tmp=np.searchsorted(pos,b,side="right")
    if (tmp<len(pos) and pos[tmp]>i) or tmp>=len(pos):
      tmp-=1
    s+=tmp
  for i in neg:
    b=x//i
    tmp=len(neg)-np.searchsorted(neg,b,side="left")
    if (tmp<len(neg) and neg[tmp]<i) or tmp>=len(neg):
      tmp-=1
    s+=tmp
  s=s/2
  return s>=k


if k<m: #k<0
  left=-10**18
  right=10**18
  while left+1<right:
    x=(left+right)//2
    if judge_m(x):
      right=x
    else:
      left=x
  print(right)
elif m<k<=m+z:
  print(0)
  exit()

else:
  k=k-(m+z)
  left=-1
  right=10**18
  while left+1<right:
    x=(left+right)//2
    if judge_p(x):
      right=x
   #   print("R")
    else:
  #    print("L")
      left=x
  print(right)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def solve_negative():
        ok = -1
        ng = -(10 ** 18)
        a_neg_desc = a_neg[::-1]

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            pidx = 0
            count = 0
            for elem_neg in a_neg_desc:
                while pidx < pos_cnt:
                    elem_pos = a_pos[pidx]
                    prod = elem_neg * elem_pos
                    if prod > mid:
                        break
                    else:
                        pidx += 1
                count += pidx
            if count >= k:
                ok = mid
            else:
                ng = mid

        print(ok)

    def solve_positive():
        kp = k - (prod_neg_cnt + prod_zer_cnt)
        ok = 10 ** 18
        ng = 0
        a_neg_desc = a_neg[::-1]
        a_pos_desc = a_pos[::-1]

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            pidx = 0
            nidx = 0
            count = 0
            for i, elem_pos1 in enumerate(a_pos_desc):
                while pidx < pos_cnt:
                    elem_pos2 = a_pos[pidx]
                    prod = elem_pos1 * elem_pos2
                    if prod > mid:
                        break
                    else:
                        pidx += 1
                count += min(pidx, pos_cnt - (i + 1))

            for i, elem_neg1 in enumerate(a_neg):
                while nidx < neg_cnt:
                    elem_neg2 = a_neg_desc[nidx]
                    prod = elem_neg1 * elem_neg2
                    if prod > mid:
                        break
                    else:
                        nidx += 1
                count += min(nidx, neg_cnt - (i + 1))

            if count >= kp:
                ok = mid
            else:
                ng = mid

        print(ok)

    import bisect
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    neg_cnt = bisect.bisect_left(a, 0)
    zer_cnt = bisect.bisect_left(a, 1) - neg_cnt
    pos_cnt = n - (neg_cnt + zer_cnt)

    prod_neg_cnt = neg_cnt * pos_cnt
    prod_pos_cnt = (neg_cnt * (neg_cnt - 1) + pos_cnt * (pos_cnt - 1)) // 2
    prod_zer_cnt = ((n * (n - 1)) // 2) - (prod_neg_cnt + prod_pos_cnt)

    a_neg = a[:neg_cnt]
    a_pos = a[(n - pos_cnt):]

    if k <= prod_neg_cnt:
        solve_negative()
    elif k <= (prod_neg_cnt + prod_zer_cnt):
        print(0)
    else:
        solve_positive()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def solve_negative():
        ok = -1
        ng = -(10 ** 18)
        a_neg_desc = a_neg[::-1]

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            pidx = 0
            count = 0
            for elem_neg in a_neg_desc:
                while pidx < pos_cnt:
                    elem_pos = a_pos[pidx]
                    prod = elem_neg * elem_pos
                    if prod > mid:
                        break
                    else:
                        pidx += 1
                count += pidx
            if count >= k:
                ok = mid
            else:
                ng = mid

        print(ok)

    def solve_positive():
        kp = k - (prod_neg_cnt + prod_zer_cnt)
        ok = 10 ** 18
        ng = 0
        a_neg_desc = a_neg[::-1]
        a_pos_desc = a_pos[::-1]

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            pidx = 0
            nidx = 0
            count = 0
            for i, elem_pos1 in enumerate(a_pos_desc):
                while pidx < pos_cnt:
                    elem_pos2 = a_pos[pidx]
                    prod = elem_pos1 * elem_pos2
                    if prod > mid:
                        break
                    else:
                        pidx += 1
                count += min(pidx, (pos_cnt - (i + 1)))

            for i, elem_neg1 in enumerate(a_neg):
                while nidx < neg_cnt:
                    elem_neg2 = a_neg_desc[nidx]
                    prod = elem_neg1 * elem_neg2
                    if prod > mid:
                        break
                    else:
                        nidx += 1
                count += min(nidx, (neg_cnt - (i + 1)))

            if count >= kp:
                ok = mid
            else:
                ng = mid

        print(ok)

    import bisect
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    neg_cnt = bisect.bisect_left(a, 0)
    zer_cnt = bisect.bisect_left(a, 1) - neg_cnt
    pos_cnt = n - (neg_cnt + zer_cnt)

    prod_neg_cnt = neg_cnt * pos_cnt
    prod_pos_cnt = (neg_cnt * (neg_cnt - 1) + pos_cnt * (pos_cnt - 1)) // 2
    prod_zer_cnt = ((n * (n - 1)) // 2) - (prod_neg_cnt + prod_pos_cnt)

    a_neg = a[:neg_cnt]
    a_pos = a[(n - pos_cnt):]

    if k <= prod_neg_cnt:
        solve_negative()
    elif k <= (prod_neg_cnt + prod_zer_cnt):
        print(0)
    else:
        solve_positive()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, readline().split())
a = sorted(list(map(int, readline().split())))
cnt_b = 0
b = []
for i in range(n):
    if a[0] > 0:
        break
    cnt_b += 1
    b.append(a.pop(0))
cnt_a = len(a)
memo = 0
b.sort(reverse=True)
for i in range(cnt_b):
    if b[0] < 0:
        break
    b.pop(0)
    memo += 1
cnt_b -= memo


def check_m(mid):
    j = 0
    res = 0
    for i in range(cnt_a):
        for j in range(cnt_b):
            if a[i] * b[j] > mid:
                break
            res += 1
    return k <= res


def check_p(mid):
    res = 0
    for i in range(cnt_a):
        for j in range(i + 1, cnt_a):
            if a[i] * a[j] > mid:
                break
            res += 1
    for i in range(cnt_b):
        for j in range(i + 1, cnt_b):
            if b[i] * b[j] > mid:
                break
            res += 1
    return k <= res


if k <= cnt_b * cnt_a:
    left = -(10 ** 18 + 1)
    right = 0
    while left + 1 < right:
        mid = (left + right) // 2
        if check_m(mid):
            right = mid
        else:
            left = mid
    print(right)
else:
    k -= cnt_b * cnt_a
    k -= (cnt_a + cnt_b) * memo + (memo * (memo - 1) // 2)
    if k < 0:
        print(0)
        exit()
    left = 1
    right = 10 ** 18 + 1
    while left + 1 < right:
        mid = (left + right) // 2
        if check_p(mid):
            right = mid
        else:
            left = mid
    print(right)

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline

N,K=map(int,readline().split())
A=list(map(int,readline().split()))

nega_list=[]
posi_list=[]
zero_num=0

for a in A:
  if a<0:
    nega_list+=[a]
  elif a>0:
    posi_list+=[a]
  else:
    zero_num+=1
    
nega_list=sorted(nega_list)
posi_list=sorted(posi_list)
nega_cnt=len(nega_list) * len(posi_list)
posi_cnt=((len(posi_list) * (len(posi_list)-1)) // 2) + ((len(nega_list) * (len(nega_list)-1)) // 2)
zero_cnt=(zero_num * (zero_num-1)) // 2 + zero_num * (len(nega_list) + len(posi_list))

import bisect
# Kがどこに属するかを判断
if K <= nega_cnt:
  # 負の数が答え
  # 正のリストと負のリスト（正に変換したもの）から一つずつ選んで数を作る
  # 絶対値がX以上の数がK個以上作れればOK
  # 答えに-1を掛けて回答
  nega_list=list(map(lambda x:x*(-1),nega_list))[::-1]
  
  def isOkNega(x):
    cnt=0
    for p in posi_list:
      cnt+=len(nega_list)-bisect.bisect_left(nega_list,x/p)
    return cnt>=K
    
  ok=0
  ng=10**18+1
  while abs(ok-ng)>1:
    mid=abs(ok+ng)//2
    if isOkNega(mid):
      ok=mid
    else:
      ng=mid
  print(ok*(-1))
  
elif K <= nega_cnt+zero_cnt:
  # 0が答え
  print(0)
  
else:  
  # 正の数が答え
  K-=(nega_cnt+zero_cnt)
  # 正のグループ内の積、負のグループ内の積、それぞれを合わせてX以下の数をK個以上作れる
  nega_list=list(map(lambda x:x*(-1),nega_list))[::-1]
  
  def isOkPosi(x):
    cnt=0
    for i in range(len(nega_list)):
      cnt+=bisect.bisect_right(nega_list,x//nega_list[i],lo=i+1)-(i+1)

    for i in range(len(posi_list)):
      cnt+=bisect.bisect_right(posi_list,x//posi_list[i],lo=i+1)-(i+1)
        
    return cnt >= K
  
  ok=10**18+1
  ng=0
  while abs(ok-ng)>1:
    mid=abs(ok+ng)//2
    if isOkPosi(mid):
      ok=mid
    else:
      ng=mid
  print(ok)

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):#積が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(h)

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
hu=0
sei=0
zero=0
for i in range(n):
    if a[i]<0:
        hu+=1
    elif a[i]==0:
        zero+=1
    else:
        sei+=1
where=0 
if k<=hu*sei:
    where=1
elif hu*sei+1<=k<=hu*sei+zero*(n-zero)+(zero*(zero-1))//2:
    print(0)
    sys.exit(0)

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]

def cnt(x):
    c = 0
    if x >= 0:
        c += len(zero)*n
    c += np.searchsorted(a, x // posi, side = 'right').sum()
    c += n-np.searchsorted(a, (- x - 1) // (-nega), side = 'right').sum()
    c -= np.count_nonzero(a * a <= x)
    return c // 2

l = - 10 ** 18
r = 10 ** 18
while l + 1 < r:
    m = (l + r) // 2
    if cnt(m) < k:
        l = m
    else:
        r = m
print(r)

Submission status: Wrong Answer

Solution code:
#155d
import bisect
import math
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番目の数 X を求める時の典型テクニックとして、
#勝手に決めた値Xよりも積が小さくなるペアの個数を数え、
#それがK個以上であればK番目の値はXより小さく、K個未満であればK番目の値はXより大きいことが分かります。

#Xを二部探索する
#ペアの個数の計算はaを固定し
#a*b <= X
#b <= X/aでいける。
#aは回す。

if K <= minus_num * plus_num :
    #答えは負の値
    min_X = A_list_minus[0]*A_list_plus[-1]
    max_X = A_list_minus[-1]*A_list_plus[0]

    #print("∴",min_X,"<=X<=",max_X)
    i = 0
    while 1:
        X = min_X + ((max_X-min_X)//2)
        
        #print("-------------------------------")
        #print("積が",X,"以下の個数を計算する。")
        
        under_X_sum = 0
        
        for i in range(minus_num):
            A = A_list_minus[i]
            #print(A,X//A,[A_list_plus])
            under_X = plus_num - bisect.bisect_right(A_list_plus,X//A)
            
            under_X_sum += under_X
        
        #print("積が",X,"以下の個数は",under_X_sum)
        
        if under_X_sum < K:
            min_X = X
        else:
            max_X = X
    
        #print("∴",min_X,"<=X<=",max_X)

        if abs(max_X - min_X) <= 1:
            #print("#ans#")
            print(max_X)
            break
    
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:
    under_zero = minus_num * plus_num + int(zero_num*(minus_num+plus_num)+zero_num*(zero_num-1)/2)
    #答えは正の値となる
    #print("ans is plus")
    min_X = 0
    if minus_num >= 2:
        minus_max = A_list_minus[0]*A_list_minus[1]
    else:
        minus_max = 0
        
    if plus_num >= 2:
        plus_max = A_list_plus[-1]*A_list_plus[-2]
    else:
        plus_max = 0   

    max_X = max(plus_max,minus_max)

    #print("∴",min_X,"<=X<=",max_X)
    counter = 0
    while counter < 100:
        counter += 1
        X = min_X + ((max_X-min_X)//2)
        #print("-------------------------------")
        #print("積が",X,"以下の個数を計算する。")
        
        under_X_sum = 0
        
        #負×負
        if minus_num != 1:
          for i in range(minus_num-1):
              A = A_list_minus[i]
              target_list = A_list_minus[i+1:]
              #print(A,X//A,target_list[::-1],"……",end="")
              if abs(A)<=X:
                  under_X = minus_num -1 -i - bisect.bisect_left(target_list,X//A)
              else:
                  under_X = 0
              #print(under_X)
              under_X_sum += under_X

        #正×正
        if plus_num != 1:
          for i in range(plus_num-1):
              A = A_list_plus[i]
              target_list = A_list_plus[i+1:]
              #print(A,X//A,target_list,"……",end="")
              under_X = bisect.bisect_right(target_list,X//A)
              #print(under_X)
              under_X_sum += under_X
        
        #print("積が",X,"以下の個数は",under_zero,"+",under_X_sum,"=", under_zero+under_X_sum )
        
        if under_X_sum + under_zero >= K:
            max_X = X
        else:
            min_X = X

        #print("∴",min_X,"<=X<=",max_X)

        if abs(max_X - min_X) <= 1:
            #print("#ans#")
            print(max_X)
            break

#愚直解
#all_list = list()
#for i in range(N-1):
#    for j in range(i+1,N):
#        all_list.append(A_list[i]*A_list[j])
#
#all_list.sort(reverse=False)
#print(all_list[405:415])
#print("ans is ",all_list[K-1])

Submission status: Wrong Answer

Solution code:

from bisect import bisect_left, bisect_right


N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

lb, ub = -10**18, 10**18


def judge_self(x, a):
    if a**2 < x:
        return 1
    else:
        return 0


def judge(x: int) -> bool:
    cnt = 0
    for a in A:
        # a * kがxより小さい数をカウントする
        if a < 0:
            idx = bisect_right(A, x/a)
            cnt += N - idx
        elif a == 0:
            # 積は常に0なので、xが正の数であれば全て満たす
            # 一方xが0以下であればxより小さい値にはならない
            if x > 0:
                cnt += N
        else:
            # 正の数の場合：(x/aより小さい数)
            idx = bisect_left(A, x/a)
            # print(a, idx)
            cnt += idx
        cnt -= judge_self(x, a)

    cnt = int(cnt/2)

    return cnt, cnt < K


# xの二部探索
for i in range(100):
    x = int((lb + ub) / 2)
    cnt, res = judge(x)

    # print(x, lb, ub, cnt, res)

    if res:
        lb = x
    else:
        ub = x

# print(lb, ub, x)
print(lb)

Submission status: Wrong Answer

Solution code:
import bisect

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

zero = A.count(0)
inm = bisect.bisect_left(A,0)
inp = bisect.bisect_right(A,0)
mi = [-x for x in A[:inm]]
mi = mi[::-1]
pl = A[inp:]
numm = inm
nump = n-inp

def shaku(x,l):
    count = 0
    if len(l) <= 1:
        return 0
    ri = len(l)-1
    for i in range(len(l)):
        while ri >= 0 and l[ri]*l[i] > x:
            ri -= 1
        
        count += max(ri-i,0)
        
    return count 

def search(x):
    count = 0
    if x >= 0:
        count += zero*(n-zero)+numm*nump+(zero*(zero-1))//2
        count += shaku(x,pl)
        count += shaku(x,mi)
            
        return count
    else:
        ri = 0
        
        for i in mi:
            while ri < nump and i*pl[ri] < -x:
                ri += 1
            count += nump-ri
        return count

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

Submission status: Wrong Answer

Solution code:
import bisect

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

zero = A.count(0)
inm = bisect.bisect_left(A,0)
inp = bisect.bisect_right(A,0)
mi = [-x for x in A[:inm]]
mi = mi[::-1]
pl = A[inp:]
numm = inm
nump = n-inp

def shaku(x,l):
    count = 0
    if len(l) <= 1:
        return 0
    ri = len(l)-1
    for i in range(len(l)):
        while ri >= 0 and l[ri]*l[i] > x:
            ri -= 1
        
        count += max(ri-i,0)
        if ri <= i:
            return count
    return count 

def search(x):
    count = 0
    if x >= 0:
        count += zero*(n-zero)+numm*nump+(zero*(zero-1))//2
        count += shaku(x,pl)
        count += shaku(x,mi)
            
        return count
    else:
        ri = 0
        
        for i in mi:
            while ri < nump and i*pl[ri] < -x:
                ri += 1
            count += nump-ri
        return count

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

Submission status: Wrong Answer

Solution code:
import bisect

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

zero = A.count(0)
inm = bisect.bisect_left(A,0)
inp = bisect.bisect_right(A,0)
mi = [-x for x in A[:inm]]
mi = mi[::-1]
pl = A[inp:]
numm = inm
nump = n-inp

def shaku(x,l):
    count = 0
    if len(l) <= 1:
        return 0
    ri = len(l)-1
    for i in range(len(l)):
        while ri >= 0 and l[ri]*l[i] > x:
            ri -= 1
        
        count += max(ri-i,0)
        if ri <= i:
            return count
    return count 

def search(x):
    count = 0
    if x >= 0:
        count += zero*(n-zero)+numm*nump+(zero*(zero-1))//2
        count += shaku(x,pl)
        count += shaku(x,mi)
            
        return count
    else:
        for i in mi:
            a = bisect.bisect_left(pl,-x/i)
            count += nump-a
        return count

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

n, k = [int(s) for s in input().split()]

a_list = [int(s) for s in input().split()]
a_list.sort()

li = bisect_left(a_list, 0)
ri = bisect_right(a_list, 0)

a_list_1 = a_list[:li]
a_list_1_num = len(a_list_1)
# print(a_list_1)
a_list_2 = a_list[li:ri]
a_list_2_num = len(a_list_2)
# print(a_list_2)
a_list_3 = a_list[ri:]
a_list_3_num = len(a_list_3)
# print(a_list_3)

ans = None

temp_num = a_list_1_num * a_list_3_num
if k > temp_num:
    k -= temp_num
else:
    i, j = divmod(k - 1, a_list_3_num)
    ans = a_list_1[i] * a_list_3[j - 1]

if ans is None:
    temp_num = int(a_list_2_num * (a_list_1_num + (a_list_2_num - 1) / 2 + a_list_3_num))
    if k > temp_num:
        k -= temp_num
    else:
        ans = 0

if ans is None:
    a_list_1 = [-num for num in a_list_1]
    a_list_1.reverse()
    # print(a_list_1)

    if a_list_1_num > 1:
        temp_1 = a_list_1.pop(0)
        a_list_1_num -= 1
    else:
        temp_1 = a_list_3[-1] + 1

    if a_list_3_num > 1:
        temp_3 = a_list_3.pop(0)
        a_list_3_num -= 1
    else:
        temp_3 = a_list_1[-1] + 1
    
    for _ in range(a_list_1_num + a_list_3_num):
        # print(k, temp_1, temp_3)
        if temp_1 < temp_3:
            if k > a_list_1_num:
                k -= a_list_1_num
                
                if a_list_1_num > 1:
                    temp_1 = a_list_1.pop(0)
                    a_list_1_num -= 1
                else:
                    temp_1 = a_list_3[-1] + 1

                continue

            ans = temp_1 * a_list_1[k - 1]
            break
        elif temp_1 > temp_3:
            if a_list_3_num == 0:
                a_list_3.append(a_list_1[-1] + 1)
                continue

            if k > a_list_3_num:
                k -= a_list_3_num

                if a_list_3_num > 1:
                    temp_3 = a_list_3.pop(0)
                    a_list_3_num -= 1
                else:
                    temp_3 = a_list_1[-1] + 1

                continue

            ans = temp_3 * a_list_3[k - 1]
            break
        elif temp_1 == temp_3:
            if k > a_list_1_num + a_list_3_num:
                k -= a_list_1_num + a_list_3_num

                if a_list_1_num > 1:
                    temp_1 = a_list_1.pop(0)
                    a_list_1_num -= 1
                else:
                    temp_1 = a_list_3[-1] + 1

                if a_list_3_num > 1:
                    temp_3 = a_list_3.pop(0)
                    a_list_3_num -= 1
                else:
                    temp_3 = a_list_1[-1] + 1
                
                continue

            temp_list = [temp_1 * num for num in a_list_1] + [temp_3 * num for num in a_list_3]
            temp_list.sort()

            ans = temp_list[k - 1]
            break

print(ans)

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 :
    
    #答えは負の値となる
    #print("ans is minus")
    #正負共に0から遠い値から計算していく
    multiplied_list = list()
    for i in range(0,minus_num,1):
        X = A_list_minus[i]
        for j in range(plus_num-1,-1,-1):
            Y = A_list_plus[j]
            
            #print(X,Y)
            
            if len(multiplied_list) <= K:
                multiplied_list.insert(bisect.bisect_right(multiplied_list,X*Y),X*Y)
            else:
                if multiplied_list[K-1] > X*Y:
                    multiplied_list.pop()
                    insert_place = bisect.bisect_right(multiplied_list,X*Y)
                    multiplied_list.insert(insert_place,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:
    #答えは正の値となる
    #print("ans is plus")
    #マイナスと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))]

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