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 *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

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

minas=[]
plus=[]
zero=[]
for a in A:
    if a<0:
        minas.append(-a)
    elif a==0:
        zero.append(a)
    else:
        plus.append(a)
minas.sort()
plus.sort()

st=-(10**18)-1
ed=10**18+1
len_minas=len(minas)
len_plus=len(plus)
len_zero=len(zero)
zero1=len_plus*len_minas
zero2=len_zero*(len_minas+len_plus)+len_zero*(len_zero-1)//2



while ed-st>1:
    mid=(st+ed)//2
    if mid<0:
        j=0
        i=0
        for m in range(len(minas)-1,-1,-1):
            while i<len(plus) and plus[i]*minas[m]<-mid:
                i+=1
            j+=len(plus)-i
    elif mid==0:
        if zero:
            if K<zero1:
                ed=0
                continue
            elif K>zero1+zero2:
                st=0
                continue
            else:

                print(0)
                exit()
        else:
            ed//=2
            continue
    else:
        j=zero1+zero2
        i=len(minas)-1
        for m in range(len(minas)-1):
            while m<i and minas[i]*minas[m]>mid:
                i-=1
            j+=max(i-m,0)


        i=len(plus)-1
        for m in range(len(plus)-1):
            while m<i and plus[i]*plus[m]>mid:
                i-=1
            j+=max(i-m,0)
    if j<K:
        st=mid
    else:
        ed=mid

print(ed)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

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

minas=[]
plus=[]
zero=[]
for a in A:
    if a<0:
        minas.append(-a)
    elif a==0:
        zero.append(a)
    else:
        plus.append(a)
minas.sort()
plus.sort()

st=-(10**18)-1
ed=10**18+1
len_minas=len(minas)
len_plus=len(plus)
len_zero=len(zero)
zero1=len_plus*len_minas
zero2=len_zero*(len_minas+len_plus)+len_zero*(len_zero-1)//2



while ed-st>1:
    mid=(st+ed)//2
    if mid<0:
        j=0
        i=0
        for m in range(len(minas)-1,-1,-1):
            while i<len(plus) and plus[i]*minas[m]<-mid:
                i+=1
            j+=len(plus)-i
    elif mid==0:
        if K<zero1:
            ed=0
            continue
        elif K>zero1+zero2:
            st=0
            continue
        else:
            print(0)
            exit()
    else:
        j=zero1+zero2
        i=len(minas)-1
        for m in range(len(minas)-1):
            while m<i and minas[i]*minas[m]>mid:
                i-=1
            j+=max(i-m,0)


        i=len(plus)-1
        for m in range(len(plus)-1):
            while m<i and plus[i]*plus[m]>mid:
                i-=1
            j+=max(i-m,0)

    if j<K:
        st=mid
    else:
        ed=mid

print(ed)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

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

minas=[]
plus=[]
zero=[]
for a in A:
    if a<0:
        minas.append(-a)
    elif a==0:
        zero.append(a)
    else:
        plus.append(a)
minas.sort()
plus.sort()

st=-(10**18)-1
ed=10**18+1
len_minas=len(minas)
len_plus=len(plus)
len_zero=len(zero)
zero1=len_plus*len_minas
zero2=len_zero*(len_minas+len_plus)+len_zero*(len_zero-1)//2



while ed-st>1:
    mid=(st+ed)//2
    if mid<0:
        j=0
        i=0
        for m in range(len(minas)-1,-1,-1):
            while i<len(plus) and plus[i]*minas[m]<-mid:
                i+=1
            j+=len(plus)-i
    elif mid==0:
        if K<zero1:
            ed=0
            continue
        elif K>zero1+zero2:
            st=0
            continue
        else:
            print(0)
            exit()
    else:
        j=zero1+zero2
        i=len(minas)-1
        for m in range(len(minas)):
            while m<i and minas[i]*minas[m]>mid:
                i-=1
            j+=max(i-m,0)


        i=len(plus)-1
        for m in range(len(plus)):
            while m<i and plus[i]*plus[m]>mid:
                i-=1
            j+=max(i-m,0)

    if j<K:
        st=mid
    else:
        ed=mid

print(ed)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    def f(x):
        res = 0
        l = n - 1
        r = n - 1
        for ai in a:
            if ai == 0:
                res += 0 if x < 0 else n - 1
                # pr.int(res)
            else:
                if ai <= -1:
                    res -= ai * ai <= x
                    while l >= 0 and a[l] * ai < x :
                        l -= 1
                    res += n - l - 1
                    # print(l,res)
                else:
                    res -= ai * ai <= x
                    while a[r] * ai > x and r >= 0:
                        r -= 1
                    res += r + 1
        #             print(r, res)
        # print(res,x)
        return k <= res // 2
    n, k = LI()
    a = LI()
    a.sort()
    ok = 10 ** 18
    ng = -10 ** 18 - 1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        # print(ok,ng,mid)
        if f(mid):
            ok = mid
        else:
            ng = mid
    # print(list(map(lambda x: 374999999999999999 / x if x != 0 else 0, a)))
    print(ok)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

lst.sort()
lst=np.array(lst)
zero_list=lst[lst==0]
pos_list=lst[lst>0]
neg_list=lst[lst<0]

#x未満が何個あるか
def how_many(x):
    ans=0
    if x>=0:
        ans+=n*len(zero_list)
    #lst*pos<xなるpos(in pos_list)とlstの組み合わせの数 => lst<x/pos
    for pos in pos_list:
        left=0; right=n-1
        while left+1<right:
            mid=(left+right)//2
            if lst[mid]<x/pos:
                left=mid
            else:
                right=mid
        #print("pos={}".format(right))
        ans+=len(lst[:(left+1)]) #条件を満たすものの数
    ans-=len(pos_list[pos_list<x/pos_list]) #自分自身をかけているものを引く
    #lst*neg<x=>lst>x/negとなる組み合わせ数
    for neg in neg_list:
        left=0; right=n-1
        while left+1<right:
            mid=(left+right)//2
            if lst[mid]>x/neg:
                left=mid
            else:
                right=mid
        #print("neg={}".format(right))
        ans+=len(lst[(left-1):])
    ans-=len(neg_list[neg_list>x/neg_list])
    return ans//2

left=-10**18
right=10**18
while left+1<right:
    mid=(left+right)//2
    #print(how_many(mid))
    if how_many(mid)<k:
        left=mid
    else:
        right=mid
print(left)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), np.int64)

a = np.sort(a)

u = a[a > 0]
d = a[a < 0]
z = len(a[a == 0])

L = - 10 ** 18
H = 10 ** 18

while H - L > 1:
    M = (H + L) // 2
    count = 0
    if M > 0:
        count += z * n
    count += np.searchsorted(a, M // u, side='right').sum()
    count += (n - np.searchsorted(a, (- M - 1) // (- d), side='right')).sum()
    count -= np.count_nonzero(a * a <= M)
    count //= 2
    #print(count)
    if count >= k:
        H = M
    else:
        L = M

print(H)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
pos = N - bisect(A,0)
zero = A.count(0)
neg = N - pos - zero

def is_ok(m):
    if m==0:
        zp = zero+pos
        k = (N-1)*zp -zp*(zp-1)//2 -pos*(pos-1)//2
        return k >= K
    if m < 0:
        k = 0
        l = 1
        for i in range(neg):
            a = A[i]
            while a*A[l] > m:
                l += 1
                if l==N: break
            k += N-l
            if k >= K: return True
            if l==N: break
        return False
    else:
        if (zero+pos)**2 - zero*(zero-1)//2 >= K:
            return True
        k = diag = 0
        r = neg-1
        for i in range(neg):
            a = A[i]
            while a*A[r] <= m:
                r -= 1
                if r==-1: break
            k += r+1
            if r>=i: diag += 1
            if r==-1: break
        nz = neg+zero
        l = nz
        for i in range(N-1,nz-1,-1):
            a = A[i]
            while a*A[l] <= m:
                l += 1
                if l==N: break
            k += N-l
            if l<=i: diag += 1
            if l==N: break
        tmp = N*(N-1)//2 - (k-diag)//2
        return tmp >= K

ng = -10**18-1
ok = 10**18+1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if mc * pc < k <= mc * pc + z * (n-z) + z * (z-1) // 2:
    print(0)
    exit()

print('dummy')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if mc * pc < k <= mc * pc + z * (n-z) + z * (z-1) // 2:
    print(0)

print('dummy')

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
A = np.array(input().split(), np.int64)

A.sort()

posA = A[A>0]
negA = A[A<0]
zeros = (A==0).sum()

const = 10**18
left = -(const+1)
right = const+1

while left+1 < right:
    num = (left+right)//2
    
    less_count = 0
    
    if num > 0:
        less_count += zeros * n
    
    limit_pair_for_pos = num / posA
    limit_idxs = np.searchsorted(A, limit_pair_for_pos, side='left')
    less_count += limit_idxs.sum()
    
    limit_pair_for_neg = num / negA
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='right')
    less_count += limit_idxs.sum()
    
    duplicate_cases = (A**2 < num).sum()
    less_count -= duplicate_cases
    less_count //= 2
    
    if less_count < k:
        left = num
    else:
        right = num

print(left)

Submission status: Wrong Answer

Solution code:
x,order = map(int, input().split())
nums = [int(str) for str in input().split()]

z = sum([int==0 for int in nums])
n = sum([int<0 for int in nums])
p = sum([int>0 for int in nums])

zero = int(z * (x-1) - z * (z-1) /2)
nega = int(p * n)
posi = int((n * (n-1) + p * (p-1)) /2)

if order > nega and order <= nega + zero:
  print(0)
else:
  negnums = [i for i in nums if i < 0]
  posnums = [i for i in nums if i > 0]

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = A[-1]**2+10
l = A[0]*A[-1]-10
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu):
      while True:
        if cou>=plu-i-1:
          num+=plu-i-1
          break
        x = A_plu_rev[i]*A_plu[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    cou = 0
    for i in range(0,mi):
      while True:
        if cou>=mi-i-1:
          num+=mi-i-1
          break
        x = A_mi[i]*A_mi_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break

    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    for a in A_mi_rev:
      for b in A_plu_rev:
        x = a*b
        if x<m:
          num+=1
        else:
          break
    if num>=K:
      r=m
    else:
      l = m
      
print(l)

Submission status: Wrong Answer

Solution code:
x,order = map(int, input().split())
nums = [int(str) for str in input().split()]

z = sum([int==0 for int in nums])
n = sum([int<0 for int in nums])
p = sum([int>0 for int in nums])

zero = int(z * (x-1) - z * (z-1) /2)
nega = int(p * n)
posi = int((n * (n-1) + p * (p-1)) /2)

if order > nega and order <= nega + zero:
  print(0)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = A[-1]**2+10
l = A[0]*A[-1]-10
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu):
      while True:
        if cou>=plu-i-1:
          num+=plu-i-1
          break
        x = A_plu_rev[i]*A_plu[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    cou = 0
    for i in range(0,mi):
      while True:
        if cou>=mi-i-1:
          num+=mi-i-1
          break
        x = A_mi[i]*A_mi_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break

    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    cou = 0
    for a in A_mi_rev:
      while True:
        if cou==plu:
          num+=cou
          break
        x = a*A_plu_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r = m
    else:
      l = m
      
print(l)

Submission status: Wrong Answer

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

A.sort()

pos = []
for i in range(N):
  if len(pos) == 0 and 0 <= A[i]: pos.append(i)
  if len(pos) == 1 and 1 <= A[i]:
    pos.append(i)
    break

def f(x):
  res = 0
  
  if 0 < len(pos):
    r = 1
    for l in range(pos[0]):
      while r < N and x <= A[l] * A[r]: r += 1
      res += N - r
      if l + 1 == r: r += 1
  else:
    r = 1
    for l in range(N):
      while r < N and x <= A[l] * A[r]: r += 1
      res += N - r
      if l + 1 == r: r += 1
    return res
  
  if 1 < len(pos):
    for l in range(pos[0], pos[1]):
      if 0 < x: res += N - (l + 1)
  else:
    for l in range(pos[0], N):
      if 0 < x: res += N - (l + 1)
    return res
  
  r = N
  for l in range(pos[1], N):
    while l < r-1 and x <= A[l] * A[r-1]: r -= 1
    if l < r: res += r - (l+1)

  return res

l, r = -10**18, 10**18
while r - l > 1:
  mid = (l + r) // 2
  if f(mid) < K: l = mid
  else: r = mid
print(l)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys

def D(*a, **kwa):
    print(*a, file=sys.stderr, **kwa)

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

neg = [a for a in A if a < 0]
pos = [a for a in A if a > 0]

n_neg = len(neg)
n_pos = len(pos)
n_zero = N - n_neg - n_pos

pairs = N * (N-1) // 2
neg_pairs = n_neg * n_pos
zero_pairs = n_zero * (n_zero-1) // 2 + n_zero * (N - n_zero)
pos_pairs = pairs - neg_pairs - zero_pairs

def cnt(x):
    res = 0
    if x < 0:
        for ne in neg:
            i = bisect_left(pos, (x +ne+1)// ne)
            res += n_pos - i
    elif x == 0:
        res = neg_pairs + zero_pairs
    else:
        for po in pos:
            i = bisect_right(pos, x // po)
            if i == 0: break
            res += i
            if i > 0 and po <= pos[i-1]:
                res -= 1
        for ne in neg:
            i = bisect_right(neg, (x -ne-1)// ne)
            res += n_neg - i
            if i < n_neg and ne >= neg[i]:
                res -= 1
        res //= 2
        res += neg_pairs + zero_pairs
    return res

l, r = -10**18-1, 10**18
while r-l > 1:
    m = l + (r - l) // 2
    c = cnt(m)
    D(l, m, r, c)
    if c >= K:
        r = m
    else:
        l = m

print(r)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = A[-1]**2+10
l = A[0]*A[-1]-10
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu):
      while True:
        if cou>=plu-i-1:
          num+=plu-i-1
          break
        x = A_plu_rev[i]*A_plu[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
    cou = 0
    for i in range(0,mi):
      while True:
        if cou>=mi-i-1:
          num+=mi-i-1
          break
        x = A_mi[i]*A_mi_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break


    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r = m
    else:
      l = m
  else:
    cou = 0
    for a in A_mi_rev:
      while True:
        if cou==plu:
          num+=cou
          break
        x = a*A_plu_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r = m
    else:
      l = m
      
print(l)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = A[-1]**2+10
l = A[0]*A[-1]-10
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu):
      for j in range(0,plu-1-i):
        x = A_plu_rev[i]*A_plu[j]
        if x<m:
          num+=1
        else:
          break
          
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    for i in range(0,mi):
      for j in range(mi-1-i):
        x = A_mi[i]*A_mi_rev[j]
        if x<m:
          num+=1
        else:
          break
          
      if num>=K:
        break

    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    cou = 0
    for a in A_mi_rev:
      while True:
        if cou==plu:
          num+=cou
          break
        x = a*A_plu_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r = m
    else:
      l = m
      
print(l)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = A[-1]**2+10
l = A[0]*A[-1]-10
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    b = 0
    for i in range(0,plu):
      a = A_plu_rev[i]
      for j in range(b,plu-1-i):
        x = a*A_plu[j]
        if x<m:
          num+=1
        else:
          break
          
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    for i in range(0,mi):
      a = A_mi[i]
      for j in range(mi-1-i):
        x = a*A_mi_rev[j]
        if x<m:
          num+=1
        else:
          break
          
      if num>=K:
        break

    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    b = 0
    for i in range(0,mi):
      a = A_mi_rev[i]
      for j in range(b,plu):
        x = a*A_plu_rev[j]
        
        if x<m:
          num+=1
        else:
          num+=b
          break

    if num>=K:
      r = m
    else:
      l = m
      
print(l)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = A[-1]**2+1
l = A[0]*A[-1]-1
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu):
      a = A_plu_rev[i]
      for j in range(0,plu-1-i):
        x = a*A_plu[j]
        if x<m:
          num+=1
        else:
          break
          
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    for i in range(0,mi):
      a = A_mi[i]
      for j in range(mi-1-i):
        x = a*A_mi_rev[j]
        if x<m:
          num+=1
        else:
          break
          
      if num>=K:
        break

    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    for i in range(0,mi):
      a = A_mi[i]
      for j in range(0,plu):
        x = a*A_plu_rev[j]
        
        if x<m:
          num+=1
        else:
          break

    if num>=K:
      r = m
    else:
      l = m
      
print(l)

Submission status: Wrong Answer

Solution code:
INF = 10**18+5


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

    a = sorted(a)
    l = -INF
    r = INF
    while(l+1 < r):
        x = (l+r)//2
        total = 0
        for i in range(n):
            if a[i] < 0:
                l2 = -1
                r2 = n
                while(l2+1 < r2):
                    x2 = (l2+r2)//2
                    if a[x2]*a[i] > x:
                        l2 = x2
                    else:
                        r2 = x2
                total += n-r2
            else:
                l2 = -1
                r2 = n
                while(l2+1 < r2):
                    x2 = (l2+r2)//2
                    if a[x2]*a[i] < x:
                        l2 = x2
                    else:
                        r2 = x2
                total += r2
            if a[i]*a[i] < x:
                total -= 1
        total //= 2
        if total < k:
            l = x
        else:
            r = x
    print(l)


main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = A[-1]**2+1
l = A[0]*A[-1]-1
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu):
      for j in range(0,plu-1-i):
        x = A_plu_rev[i]*A_plu[j]
        if x<m:
          num+=1
        else:
          break
          
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    for i in range(0,mi):
      for j in range(mi-1-i):
        x = A_mi[i]*A_mi_rev[j]
        if x<m:
          num+=1
        else:
          break
          
      if num>=K:
        break

    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    b = plu
    cou = 0
    for a in A_mi_rev:
      while True:
        if cou==b:
          num+=cou
          break
        x = a*A_plu_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r = m
    else:
      l = m
      
print(l)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
positive = [i for i in a if i > 0]
negative = [i for i in a if i < 0]
zero = a.count(0)
positive.reverse()

def count(x): # 積が x 以下のペアが何個あるか？
  ans = 0
  if x >= 0:
    ans += zero * n
  # 尺取り法
  at = 0
  for i in positive:
    while at < n and i * a[at] <= x:
      at += 1
    ans += at
  # 尺取り法
  at = 0
  for i in negative:
    while at < n and i * a[at] > x:
      at += 1
    ans += n - at
  # 同じものはペアにできない
  for i in a:
    ans -= i * i <= x
  return ans // 2

# 二分探索
ok = 10**18
ng = -ok - 1
while ok - ng > 1:
  cen = (ok + ng) // 2
  if count(cen) >= k:
    ok = cen
  else:
    ng = cen

print(ok)

Submission status: Wrong Answer

Solution code:
# 積が負で絶対値が T 以上の組合せ数を求める
# A, B は昇順
def count1(T, A, B):
	if T <= 0 or len(A) == 0 or len(B) == 0:
		return 0

	count, it = 0, -1
	for i in range(len(A) - 1, -1, -1):
		while it + 1 < len(B) and A[i] * B[it + 1] < T:
			it += 1

		# A[i] * B[it], A[i] * B[it + 1], ... は条件を満たす
		count += len(B) - it - 1
	return count


# 積が正で絶対値が T 以下の組合せ数を求める
# 絶対値が T より大きいものの組合せ数を求めてから全体から引く
# A は昇順
def count2(T, A):
	count_all = len(A) * (len(A) - 1) // 2
	count = count1(T + 1, A, A)

	# i * i が余計にカウントされた分を減らす．
	for e in A:
		if e * e > T:
			count -= 1

	count /= 2 # 同じ配列を渡しているため (i, j) == (j, i) が二回カウントされる

	return count_all - count


if __name__ == "__main__":
	N, K = map(int, input().split())
	A = list(map(int, input().split()))

	# X: 負の数の絶対値の配列
	# Y: 正の数の配列
	# Z: 0 の個数
	X, Y, Z = [], [], 0
	for e in A:
		if e < 0:
			X.append(-e)
		elif e > 0:
			Y.append(e)
		else:
			Z += 1
	X.sort()
	Y.sort()


	# 積が T 以下な組合せ数が K 未満か？
	def check(T):
		count = 0
		if T < 0:
			count += count1(abs(T), X, Y)
			print(T, ": ", count)
		else:
			count += len(X) * len(Y) # 結果が負
			count += Z * (Z - 1) // 2 + Z * (N - Z) # 結果が 0
			count += count2(T, X) + count2(T, Y)

		return count < K


	ok, ng = -10 ** 18, 10 ** 18
	while ng - ok > 1:
		mid = (ok + ng) // 2
		
		if check(mid):
			ok = mid
		else:
			ng = mid

	print(ok + 1)

Submission status: Wrong Answer

Solution code:
#11:09
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
import bisect
if a[0] > 0:
  xday = 0
else:
  xday = bisect.bisect_right(a,0)
size = 63
#size = 10
now = - 2 ** size
scale = 2 ** size
while scale != 0:
  tmp = now + scale
  c = []
  cnt = 0
  if tmp > 0:
    here = n
  else:
    here = 0
  for i in range(n):
    if i == xday:
      here = n
    if a[i] < 0:
      if tmp > 0:
        while a[i] * a[here-1] < tmp:
          if here == 1:
            c.append(n)
            cnt += n
            break
          here -= 1
        else:
          cnt += n-here
          c.append(n-here)
      else:
        while a[i] * a[here] >= tmp:
          if here == n-1:
            c.append(0)
            break
          here += 1
        else:
          cnt += here
          c.append(here)
    elif a[i] == 0:
      if tmp > 0:
        cnt += n
        c.append(n)
      else:
        c.append(0)
        pass
    else:
      while a[i] * a[here-1] >= tmp:
        if here == 1:
          c.append(0)
          break
        here -= 1
      else:
        cnt += here
        c.append(here)
    if a[i] ** 2 < tmp:
      cnt -= 1
      c[-1] -= 1
  #print(cnt,cnt//2,tmp,c)
  cnt //= 2
  if cnt < k:
    now = tmp
  scale //= 2
print(now)
#print(xday)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

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

minas=[]
plus=[]
zero=[]
for a in A:
    if a<0:
        minas.append(-a)
    elif a==0:
        zero.append(a)
    else:
        plus.append(a)
minas.sort()
plus.sort()

st=-(10**18)-1
ed=10**18+1
len_minas=len(minas)
len_plus=len(plus)
len_zero=len(zero)
zero1=len_plus*len_minas
zero2=len_zero*(len_minas+len_plus)+len_zero*(len_zero-1)//2


def nibun(lst,value,st,ed):
    if lst[st]>value:
        return(st)
    while ed-st>1:
        mid=(st+ed)//2
        if value>=lst[mid]:
            st=mid
        else:
            ed=mid
    return(ed)
while ed-st>1:
    mid=(st+ed)//2
    if mid<0:
        j=0
        for m in minas:
            value=-mid//m+((-mid%m)>=1)*1
            j+=len_plus-bisect_left(plus,value)
    elif mid==0:
        if K<zero1:
            ed=0
            continue
        elif K>zero1+zero2:
            st=0
            continue
        else:
            print(0)
            exit()
    else:
        j=zero1+zero2
        for i in range(len_plus-1):
            value=mid//plus[i]
            j+=nibun(plus,value,i+1,len_plus)-(i+1)
        for i in range(len_minas-1):
            value=mid//minas[i]
            j+=nibun(minas,value,i+1,len_minas)-(i+1)

    if j<K:
        st=mid
    else:
        ed=mid

print(ed)