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: Accepted

Solution code:
import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a) # numpy の array で高速化

a = np.sort(a)
zero = np.count_nonzero(a == 0) # 整数が0の個数
pos = a[a > 0] # 整数が負の配列
neg = a[a < 0] # 整数が正の配列

def count(x): # 積がｘが以下のペアが何個あるか？
    ans = 0
    if x >= 0: # 片方が0の場合
        ans += zero * n 
    ans += np.searchsorted(a, x // pos, side="right").sum()
    ans += n * len(neg) - np.searchsorted(a, -(-x // neg), side="left").sum()
    ans -= np.count_nonzero(a * a <= x) # 同じものは2つ選べない
    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: Accepted

Solution code:
N, K = map(int, input().split())
plus = []
minus = []
zero = 0
for i in map(int, input().split()):
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1
plus.sort()
minus.sort(reverse=True)


def solve(mid):
    global N, K, zero
    cnt = 0
    if mid >= 0:
        cnt += len(plus) * len(minus)
        if mid > 0:
            cnt += zero * (zero - 1) // 2 + zero * (N - zero)
            for L in (plus, minus):
                l, r = 0, len(L) - 1
                while l < r:
                    while l < r and L[l] * L[r] >= mid:
                        r -= 1
                    cnt += r - l
                    l += 1
    else:
        r = len(minus) - 1
        for l in range(len(plus)):
            while r >= 0 and plus[l] * minus[r] < mid:
                r -= 1
            cnt += len(minus) - (r + 1)
    return cnt < K


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok, ng = -10 ** 19, 10 ** 19
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import numpy as np

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

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

def f(x): # count pairs x or less
    cnt=0
    #zero
    if x>=0:
        cnt += len(zero)*n
    #pos
    cnt += A.searchsorted(x//pos,side="right").sum()
    #neg
    cnt += (n-A.searchsorted(-(-x//neg),side="left")).sum()
    #except a*a
    cnt-=np.count_nonzero(A*A<=x)
    return cnt//2

l=-10**18
r=10**18

while l<r:
    pov=(l+r)//2
    if f(pov)>=k:
        r=pov
    else:
        l=pov+1
print(l)

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())

neg = sorted([-a for a in A if a < 0])
pos = sorted([a for a in A if a >= 0])

def _count_pair_neg(x):
    x = -x
    res = 0

    MAX = len(pos)
    i = 0
    for n in reversed(neg):
        while i < MAX and n * pos[i] < x:
            i += 1
            
        res += MAX - i
    return res


def _count_pair_pos(x):
    res = 0

    # Negative list
    i = 0
    MAX = len(neg)
    for n in reversed(neg):
        if n * n <= x:
            res -= 1
            
        while i < MAX and neg[i] * n <= x:
            i += 1
        res += i
        
    # Positive list
    i = 0
    MAX = len(pos)
    for n in reversed(pos):
        if n * n <= x:
            res -= 1
            
        while i < MAX and pos[i] * n <= x:
            i += 1
        res += i
        
    # Devide by 2 for counting the same pair twice
    res //= 2
    res += len(neg) * len(pos)
    return res


def count_pair(x):
    if x < 0:
        return _count_pair_neg(x)
    
    return _count_pair_pos(x)


# Bounds
lb = 0
ub = 2 * 10 ** 18 + 2

while ub - lb > 1:
    mid = (ub + lb) // 2
    if count_pair(mid - 10 ** 18 - 1) < K:
        lb = mid
    else:
        ub = mid

print(ub - 10 ** 18 - 1)

Submission status: Accepted

Solution code:
#場合分け尺取り


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

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr())
A.sort()
pos = A[A>0]
zero = A[A==0]
neg = A[A<0]

def check(x):
    # x以下の数がK個以上ある時、Trueを返す
    count = 0 #最後に２で割る
    if x >= 0:
        count += len(zero) * N
    count += (np.searchsorted(A, x//pos, side='right')).sum()
    count += (N - np.searchsorted(A, (-x-1)//(-neg), side='right')).sum()
    count -= np.count_nonzero(A * A <= x) #ペアなので自分自身は駄目
    assert count % 2 == 0
    count //= 2
    return count >= K

left = - 10 ** 19 # NG
right = 10 ** 19 # OK
while right > left + 1:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)
# 46

Submission status: Accepted

Solution code:
import numpy as np
import sys
from collections import deque

n,k=list(map(int,input().strip().split(" ")))
a=np.sort(np.array(list(map(int,input().split(" ")))))

zero=len(a[a==0])
pos=a[a>0]
neg=a[a<0]

l,r=10**18,-10**18
while l-r>1:
    c=(r+l)//2
    cnt=0
    if c>=0:
        cnt+=n*zero
    
    cnt+=np.searchsorted(a,c//pos,side='right').sum()+(n-np.searchsorted(a,(-c-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=c)
    cnt//=2

    if cnt>=k:
        l=c
    else:
        r=c

print(l)

Submission status: Accepted

Solution code:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a)
a.sort()
nega=a[a<0]
zera=a[a==0]
posa=a[a>0]

def cnt(x):
  y=0
  if x>=0:
    y+=n*len(zera)
  y+=np.searchsorted(a,x//posa,side="right").sum()
  y+=n*len(nega)-np.searchsorted(a,-(-x//nega)).sum() 
  y-=len(a[a*a<=x])
  return y//2

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

Submission status: Accepted

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()

left = -10 ** 18
right = 10 ** 18

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='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = -(-num // negA)
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A ** 2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2

    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Accepted

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()

left = -10 ** 18
right = 10 ** 18

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='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = num // negA + (num % negA != 0)
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A ** 2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2

    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Accepted

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()

left = -10**18
right = 10**18

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='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = (num+negA+1) // negA
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A**2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2
    
    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Accepted

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


A = np.sort(A)
posi = A[A>0]
zero = A[A==0]
nega = A[A<0]

def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    # count 0
    if x >= 0:
        cnt_tpl += len(zero) * N
    # count posi
    cnt_tpl += np.searchsorted(A, x//posi, side='right').sum()
    # count nega
    cnt_tpl += (N - np.searchsorted(A, (-x - 1) // (-nega), side='right')).sum()
    # remove a^2
    cnt_tpl -= np.count_nonzero(A*A <= x)
    return cnt_tpl // 2

# 二分探索
left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x

print(right)

Submission status: Accepted

Solution code:
import numpy as np

n, k = map(int, input().split())
num_list = [int(i) for i in input().split()]
num_list = np.array(num_list)
num_list.sort()

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

def count(x):
    ans = 0
    if x >= 0:
        ans += len(zero) * n
    ans += np.searchsorted(num_list, x // pos, side="right").sum()
    ans += n * len(neg) - np.searchsorted(num_list, -(-x // neg), side="left").sum()
    ans -= np.count_nonzero(num_list * num_list <= x)
    return ans // 2

left = -(10 ** 18)
right = 10 ** 18

while left + 1 < right:
    mid = (left + right) // 2
    if count(mid) >= k:
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mA, nA = [], []
for a in A:
    if a < 0:
        mA.append(a)
    else:
        nA.append(a)
mA = sorted(mA)[::-1]
nA = sorted(nA)
lnA = len(nA)
lmA = len(mA)


def F(k):
    # k以下の数
    # positive positive
    r = 0
    i, j = 0, lnA-1
    while i < lnA:
        while j >= 0 and nA[j]*nA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # negative negative
    i, j = 0, lmA-1
    while i < lmA:
        while j >= 0 and mA[j]*mA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # positive negative
    i, j = 0, lmA-1
    while i < lnA:
        while j >= 0 and mA[j]*nA[i] <= k:
            j -= 1
        r += 2*(lmA-j-1)
        i += 1
    for a in A:
        if a*a <= k:
            r -= 1
    return r//2


mx, mn = 2*10**18, -2*10**18
idx = (mx+mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        mn = idx
    else:
        mx = idx
    idx = (mx+mn)//2
print(idx+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mA, nA = [], []
for a in A:
    if a < 0:
        mA.append(a)
    else:
        nA.append(a)
mA = sorted(mA)[::-1]
nA = sorted(nA)
lnA = len(nA)
lmA = len(mA)


def F(k):
    # k以下の数
    # positive positive
    r = 0
    i, j = 0, lnA-1
    while i < lnA:
        while j >= 0 and nA[j]*nA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # negative negative
    i, j = 0, lmA-1
    while i < lmA:
        while j >= 0 and mA[j]*mA[i] > k:
            j -= 1
        r += j+1
        i += 1

    # positive negative
#    i, j = 0, lmA-1
#    while i < lnA:
#        while j >= 0 and mA[j]*nA[i] <= k:
#            j -= 1
#        r += 2*(lmA-j-1)
#        i += 1
    i, j = lmA-1, 0
    while i >= 0:
        while j < lnA and nA[j]*mA[i] > idx:
            j += 1
        r += 2*(lnA-j)
        i -= 1
    for a in A:
        if a*a <= k:
            r -= 1
    return r//2


mx, mn = 2*10**18, -2*10**18
idx = (mx+mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        mn = idx
    else:
        mx = idx
    idx = (mx+mn)//2
print(idx+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
zeros = 0
for a in A:
    if a > 0:
        pos.append(a)
    elif a < 0:
        neg.append(a)
    else:
        zeros += 1

pos.sort()
neg.sort(reverse=True)

minus_pattern = len(pos) * len(neg)
zero_pattern = zeros * (len(pos)+len(neg)) + (zeros*(zeros-1))//2

pos_length = len(pos)
neg_length = len(neg)

left = -10**18
right = 10**18

while left + 1 < right:
    num = (left+right)//2
    less_count = 0

    if num >= 0:
        pos_idx = pos_length-1
        for p in pos:
            while pos_idx >= 0 and p * pos[pos_idx] > num:
                pos_idx -= 1
            less_count += pos_idx + 1
            if p**2 <= num:
                less_count -= 1

        neg_idx = neg_length-1
        for m in neg:
            while neg_idx >= 0 and m * neg[neg_idx] > num:
                neg_idx -= 1
            less_count += neg_idx + 1
            if m**2 <= num:
                less_count -= 1

        less_count //= 2
        less_count += minus_pattern + zero_pattern

    elif num < 0:
        pos_idx = 0
        for m in neg[::-1]:
            while pos_idx < pos_length and m * pos[pos_idx] > num:
                pos_idx += 1
            less_count += pos_length - pos_idx

    if less_count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mA, nA = [], []
for a in A:
    if a<0:
        mA.append(a)
    else:
        nA.append(a)
lnA = len(nA)
lmA = len(mA)

def F(idx):
    i, j = 0, lnA-1
    r = 0
    while i < lnA:
        while j >= 0 and nA[j]*nA[i] > idx:
            j -= 1
        r += j+1
        i += 1
    i, j = lmA-1, 0
    while i >= 0:
        while j < lmA and mA[j]*mA[i] > idx:
            j += 1
        r += lmA-j
        i -= 1
    i, j = 0, 0
    while i < lmA:
        while j < lnA and nA[j]*mA[i] > idx:
            j += 1
        r += 2*(lnA-j)
        i += 1
    for a in A:
        if a*a <= idx:
            r-=1
    return r//2

mx, mn = 2*10**18, -2*10**18
idx = (mx + mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        idx, mn = (idx + mx)//2, idx
    else:
        idx, mx = (idx + mn)//2, idx
print(idx+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mA, nA = [], []
dd = []
for a in A:
    if a<0:
        mA.append(a)
    else:
        nA.append(a)
    dd.append(a*a)
#rA = A[::-1]
#print(mA, nA)
lnA = len(nA)
lmA = len(mA)

def F(idx):
    j = lnA-1
    r = 0
    for a in nA:
        while j >= 0:
            if nA[j]*a <= idx:
                break
            j -= 1
        r += j+1
    j = 0
    for a in mA[::-1]:
        while j < lmA:
            if mA[j]*a <= idx:
                break
            j += 1
        r += lmA-j
    j = 0
    for a in mA:
        while j < lnA:
            if nA[j]*a <= idx:
                break
            j += 1
        r += 2*(lnA-j)

    for a in dd:
        if a <= idx:
            r-=1
    return r//2
#print(F(448283280358331064))

mx, mn = 2*10**18, -2*10**18
idx = (mx + mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        idx, mn = (idx + mx)//2, idx
        continue
    idx, mx = (idx + mn)//2, idx
print(idx+1)

Submission status: Accepted

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)
    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
    else:
        j=zero1
        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: Accepted

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): # x以下のペアがk個以上あるかどうかを返す関数
    cnt = 0
    if x < 0: # xが負の場合(plusとminusで尺取り法)
        j = p-1
        for i in range(m)[::-1]:
            while j >= 0:
                if minus[i]*plus[j] <= x:
                    j -= 1
                else:
                    break
            cnt += p - j - 1
    else: # xが正の場合(x>=0)
        #正の数同士で尺取り法
        j = p-1
        for i in range(p):
            while j >= 0:
                if plus[i]*plus[j] > x:
                    j -= 1
                else:
                    break
            cnt += max(0,j - i)
        #負の数同士で尺取り法
        j = 0
        for i in range(m)[::-1]:
            while j < m:
                if minus[i]*minus[j] > x:
                    j += 1
                else:
                    break
            cnt += max(0,i - j)
        # 0x何かの場合 + 0x0の場合 + 負の数x正の数の場合
        cnt += (m+p)*zero + zero*(zero-1)//2 + m*p
    #k個以上あるならtrue
    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 = len(minus)
p = len(plus)
zero = bl(a,1) - br(a,-1)
ok = 10**18
ng = -10**18-1
while ok-ng > 1:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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:
                if minus[i]*plus[j] <= x:
                    j -= 1
                else:
                    break
            cnt += p - j - 1
    else:
        j = p-1
        for i in range(p):
            while j >= 0:
                if plus[i]*plus[j] > x:
                    j -= 1
                else:
                    break
            cnt += max(0,j - i)
        j = 0
        for i in range(m)[::-1]:
            while j < m:
                if minus[i]*minus[j] > x:
                    j += 1
                else:
                    break
            cnt += max(0,i - j)
        cnt += (m+p)*zero + zero*(zero-1)//2 + 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 = len(minus)
p = len(plus)
zero = bl(a,1) - br(a,-1)
ok = 10**18
ng = -10**18-1
while ok-ng > 1:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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])

if len(u) * len(d) < k <= len(u) * len(d) + z * (n-z) + z * (z-1) // 2:
    print(0)
    exit()

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: Accepted

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:
        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:
        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: Accepted

Solution code:
from sys import stdin
import numpy as np

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = np.sort(np.array([int(x) for x in stdin.readline().rstrip().split()]))
MINUS = A[A < 0]
ZERO = A[A == 0]
PLUS = A[A > 0]


def solve(x):
    count_tpl = 0
    if x >= 0:
        count_tpl += len(ZERO) * N
    count_tpl += np.searchsorted(A, x // PLUS, side='right').sum()
    count_tpl += (N - np.searchsorted(A, (-x - 1) // (-MINUS), side='right')).sum()
    count_tpl -= np.count_nonzero(A * A <= x)
    assert count_tpl % 2 == 0
    return count_tpl // 2






left = -10**18
right = 10**18
while left + 1 < right:
    x = (left + right) // 2
    if solve(x) >= K:
        right = x
    else:
        left = x
print(right)

Submission status: Accepted

Solution code:
import numpy as np

n,k = map(int,input().split())
a_list = np.array(list(map(int,input().split())))
a_list = np.sort(a_list)

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

def count(x): #積がx以下になるペアの個数を返す(一旦重複は考えない)
    ans = 0
    if x >= 0:
        ans += n * len(zero)
    # a_list * pos < xだから，a_list < x/posになる個数をcountしている(pos側を固定)
    ans += np.searchsorted(a_list,x // pos, side='right').sum()
    # a_list < x // negとなる者を全ての組み合わせから抜く
    ans += (n - np.searchsorted(a_list, (-x - 1) // (-neg), side='right')).sum()
    # 同じもの2つは選べない
    ans -= np.count_nonzero(a_list * a_list <= x)
    return ans // 2

left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if count(x) >= k:
        right = x
    else:
        left = x

print(right)

Submission status: Accepted

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)

	# A[i] * A[i] が余計にカウントされた分を減らす．
	for e in A:
		if e * e >= T + 1:
			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)
		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: Accepted

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

def count(A, B, x):
    N = len(A)
    M = len(B)
    res = 0
    r = -1
    for l in range(N):
        a = A[l]
        while r < M-1 and B[r+1]*a <= x:
            r += 1
        res += r+1
    return res

def count2(A, x):
    res = 0
    for a in A:
        if a*a <= x:
            res += 1
    return res
        

N, K = map(int, readline().split())
A = list(map(int, readline().split()))
Am = []
Ap = []

minus = 0
zero = 0
plus = 0
for a in A:
    if a < 0:
        minus += 1
        Am.append(-a)
    elif a == 0:
        zero += 1
    else:
        plus += 1
        Ap.append(a)

ms = minus*plus
zs = ms + zero*(minus+plus) + zero*(zero-1)//2

Am.sort()
Ap.sort()
Amr = Am[::-1]
Apr = Ap[::-1]

if K <= ms:
    K = ms+1-K
    ok = max(max(Am+[0]), max(Ap+[0]))**2
    ng = 0
    while abs(ok-ng)>1:
        med = (ok+ng)//2
        if count(Amr, Ap, med) >= K:
            ok = med
        else:
            ng = med
    ans = -ok
elif K <= zs:
    ans = 0
else:
    K -= zs
    ok = max(max(Am+[0]), max(Ap+[0]))**2
    ng = 0
    while abs(ok-ng)>1:
        med = (ok+ng)//2
        if (count(Amr, Am, med) + count(Apr, Ap, med) - count2(Am, med) - count2(Ap, med))//2 >= K:
            ok = med
        else:
            ng = med
    ans = ok

print(ans)

Submission status: Accepted

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)
zero = A[A == 0]
pos = A[A > 0]
neg = A[A < 0]

def f(x):
    cnt_tpl = 0
    if x >= 0: cnt_tpl += len(zero) * N
    cnt_tpl += np.searchsorted(A, x // pos, side='right').sum()
    cnt_tpl += (N - np.searchsorted(A, (-x - 1) // (-neg), side='right')).sum()
    cnt_tpl -= np.count_nonzero(A * A <= x)
    # assert cnt_tpl % 2 == 0
    return cnt_tpl // 2

left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x

print(right)

Submission status: Accepted

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()

left = -10**18
right = 10**18

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='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = -(num // -negA)
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A**2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2
    
    if less_count >= k:
        right = num
    else:
        left = num

print(right)