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 sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n,k = map(int, input().split())
a = list(map(int, input().split()))
ma = []
pa = []
zc = 0
for num in a:
    if num<0:
        ma.append(num)
    elif num>0:
        pa.append(num)
    else:
        zc += 1
mn = len(ma)*len(pa)
ma.sort()
pa.sort()
ma =ma[::-1]

def _sub(m, l1):
    lp = len(l1)
    t = lp-1
    ans = 0
    for s in range(lp):
        if t<=s:
            break
        while l1[s]*l1[t]>m and t>s+1:
            t -= 1
        if l1[s]*l1[t]>m:
            break
        ans += (t-s)
    return ans

def sub1(m):
    # 0以上m以下の値の個数
    ans = 0
    ans += _sub(m, pa)
    ans += _sub(m, ma)
    return ans

def sub2(m):
    # 0以下、m以下の値の個数
    ans = 0
    lp = len(pa)
    lm = len(ma)
    t = 0
    for s in reversed(range(lp)):
        while pa[s]*ma[t]>m and t<lm-1:
            t += 1
        if pa[s]*ma[t]>m:
            break
        ans += lm - t
    return ans

znum = zc*(len(ma)+len(pa)) + (zc-1)*zc//2
if k>mn:
    k -= mn
    if znum>=k:
        ans = 0
    else:
        k -= znum
        l = 0
        r = 10**18+1
        while l<r-1:
            m = (l+r)//2
            v = sub1(m)
            if v>=k:
                r = m
            else:
                l = m
        ans = l+1
else:
    l = -10**18-1
    r = 0
    while l<r-1:
        m = (l+r)//2
        v = sub2(m)
        if v>=k:
            r = m
        else:
            l = m
    ans = l+1
print(ans)

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]
zero = a[a==0]
posi = a[a>0]

l = -10**18-1
r = 10**18+1
while r - l > 1:
   mid = (r+l)//2
   cnt = 0
   if mid >= 0:
      cnt += len(zero)*n
   cnt += a.searchsorted(mid//posi, side='right').sum()
   cnt += (n - a.searchsorted(-(-mid//nega), side='left')).sum()
   cnt -= np.count_nonzero(a*a <= mid)
   cnt //=2
   if cnt >= k:
      r = mid
   else:
      l= mid

print(r)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=np.array(readline().strip().split(),dtype="int64")
    
    a.sort()
    neg=a[a<0]
    neg_p=neg**2
    zero=a[a==0]
    pos=a[a>0]
    pos_p=pos**2
    l=-10**18-1
    r=10**18
    while l<r-1:
        x=(l+r)//2
        cnt=0
        if neg.size>0:
            cnt+=(a.size-np.searchsorted(a,(x+neg+1)//neg)).sum()
            cnt-=neg_p[neg_p<=x].size
        if zero.size>0:
            if x>=0:
                cnt+=(a.size-1)*zero.size
        if pos.size>0:
            cnt+=np.searchsorted(a,x//pos,side="right").sum()
            cnt-=pos_p[pos_p<=x].size

        cnt//=2
        if cnt>=k: r=x
        else: l=x

    print(r)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
MAX = int(10e18)


def count(arr1, arr2, target, remove_dup):
    ret = 0
    j = len(arr2)
    for i, val1 in enumerate(arr1):
        while j > 0 and val1 * arr2[j-1] > target:
            j -= 1
        ret += j
        if remove_dup and j >= (i+1):
            ret -= 1
    if remove_dup:
        ret //= 2
    return ret


def search_negative(pos, neg, K):
    neg.sort()
    pos.sort(reverse=True)
    lo = -MAX
    hi = 0
    while lo < hi:
        mid = (lo + hi) // 2
        cnt = count(pos, neg, mid, False)
        if cnt < K:
            lo = mid + 1
        else:
            hi = mid
    return lo


def search_positive(pos, neg, K):
    pos.sort()
    neg.sort(reverse=True)
    lo = 0
    hi = MAX
    while lo < hi:
        mid = (lo + hi) // 2
        cnt = count(pos, pos, mid, True) + count(neg, neg, mid, True)
        if cnt < K:
            lo = mid + 1
        else:
            hi = mid
    return lo


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    negative_nums = []
    positive_nums = []
    zeros = 0
    for a in A:
        if a < 0:
            negative_nums.append(a)
        elif a > 0:
            positive_nums.append(a)
        else:
            zeros += 1
    negative_count = len(negative_nums) * len(positive_nums)
    zero_count = zeros * (N-1) - zeros * (zeros-1) // 2
    ans = 0
    if K <= negative_count:
        ans = search_negative(positive_nums, negative_nums, K)
    elif K <= negative_count + zero_count:
        ans = 0
    else:
        ans = search_positive(positive_nums, negative_nums,
                              K - negative_count - zero_count)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
neg_end = bisect_left(A, 0)
pos_start = bisect_right(A, 0)

pos_cnt = N - pos_start
neg_cnt = neg_end
zero_cnt = N - (pos_cnt + neg_cnt)

neg_pairs_cnt = pos_cnt * neg_cnt
zero_pairs_cnt = zero_cnt * (pos_cnt + neg_cnt) + (zero_cnt * (zero_cnt-1) // 2)

if K <= neg_pairs_cnt:
  # X以下のpairはK個以上あるか？
  ok, ng = 0, -10**18
  while abs(ok - ng) > 1:
    X = (ok+ng) // 2
    or_higher_cnt, r = 0, pos_start
    # それぞれのnegごとに尺取り法
    for l in range(neg_end):
      while r < N and A[l] * A[r] > X:
        r += 1
      # positive_integers - (max_point - positive_start_index)
      or_higher_cnt += pos_cnt - (r - pos_start)

    if or_higher_cnt >= K:
      ok = X
    else:
      ng = X
  print(ok)

elif K <= neg_pairs_cnt + zero_pairs_cnt:
  print(0)

else:
  K -= (neg_pairs_cnt + zero_pairs_cnt)
  ok, ng = 10**18, 0
  while abs(ok - ng)> 1:
    X = (ok+ng) // 2
    or_higher_cnt = 0

    r = N - 1
    for l in range(pos_start, N):
      while r < N and A[l] * A[r] > X and l < r:
        r -= 1
      or_higher_cnt += max(0, r-l)

    l = 0
    for r in range(neg_end-1, -1, -1):
      while l < N and A[l] * A[r] > X and l < r:
        l += 1
      or_higher_cnt += max(0, r-l)

    if or_higher_cnt >= K:
      ok = X
    else:
      ng = X

  print(ok)

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()
plus = a[a>0]
zero = np.count_nonzero(a==0)
minus = a[a<0]

low = -10**20
hi = 10**20

while hi-low > 1:
    # n*nのマスからave以下という条件を満たす個数をカウントするイメージ
    item = 0
    ave = (hi+low)//2

    # aveがプラスの時ゼロの分は条件を満たすため加算してやる
    if ave >= 0:
        item += zero*n

    # bisect結果*(serchしたいplus) <= ave　を変形
    # bisect結果 <= ave//(serchしたいplus)　になる
    item += a.searchsorted(ave//plus,side='right').sum()

    # マイナスの方も式変形のやり方は同じ
    # マイナスの方は結果がaveより大きいものを除外する
    item += n*len(minus)-a.searchsorted(-(-ave//minus),side='left').sum()

    # 最後に条件は満たしているものの、自分自身をかけているものを引いてやる
    item -= np.count_nonzero(a*a <= ave)
    
    # 二分探索部分組み合わせの際に(a,b),(b,a)の２通り足してるので割る
    if item//2 >= k:
        hi = ave
    else:
        low = ave

print(hi)

Submission status: Accepted

Solution code:
import numpy as np
n,k=map(int,input().split())
a=np.array(list(map(int,input().split())))
a.sort()
p=a[a>0]
z=np.count_nonzero(a==0)
m=a[a<0]
r=10**19
l=-r
while r-l>1:
    # 区間[l,r]を半分に分けて探索。最終的にrが求める値になるようにする。
    # b以下のものがk個以上あるような、最小のbを求める。bを大きくする→b以下のものも増える。b以下のものがめちゃくちゃある→bを減らす。
    b=(l+r)//2
    c=0
    if b>=0:
        c+=z*n
    # 配列aに対し、配列b//pの要素たちをそれぞれsearchsortedする。結果の配列はb//pと同じ形になる。
    c+=a.searchsorted(b//p,side='right').sum()
    # 配列aに対し、配列b//mの要素たちをそれぞれsearchsortedする。結果の配列はb//mと同じ形になる。
    c+=n*len(m)-a.searchsorted(-(-b//m),side='left').sum()
    c-=np.count_nonzero(a*a<=b)
    if c//2>=k:
        r=b
    else:
        l=b
print(r)

Submission status: Accepted

Solution code:
import numpy as N
n,k=map(int,input().split())
A=N.array(list(map(int,input().split())))
A.sort()
p=A[A>0]
z=N.count_nonzero(A==0)
m=A[A<0]
r=10**19
l=-r
while r-l>1:
    b=(l+r)//2
    c=0
    if b>=0:
        c+=z*n
    c+=A.searchsorted(b//p,side='right').sum()
    c+=n*len(m)-A.searchsorted(-(-b//m),side='left').sum()
    c-=N.count_nonzero(A*A<=b)
    if c//2>=k:
        r=b
    else:
        l=b
print(r)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,K = LI()
    pl = []
    mi = []
    z = 0
    for x in sys.stdin.readline().split():
        x = int(x)
        if x > 0:
            pl.append(x)
        elif x < 0:
            mi.append(-x)
        else:
            z += 1
    pl.sort()
    mi.sort()

    minus = len(pl) * len(mi)
    zero = z * (len(pl) + len(mi)) + z * (z-1) // 2

    h = INF
    l = -INF-1

    while l+1 < h:
        m = (h+l)//2

        if m > 0:
            k = minus + zero
            j = len(pl)-1
            for i in range(len(pl)-1):
                if i >= j: break
                while pl[i] * pl[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
            j = len(mi)-1
            for i in range(len(mi)-1):
                if i >= j: break
                while mi[i] * mi[j] > m:
                    j -= 1
                    if j == i: break
                else:
                    k += j - i
                    continue
                break
        elif m < 0:
            k = 0
            j = 0
            if len(mi) > 0:
                for i in range(len(pl)-1,-1,-1):
                    while -pl[i] * mi[j] > m:
                        j += 1
                        if j == len(mi): break
                    else:
                        k += len(mi) - j
                        continue
                    break
        else:
            k = minus + zero

        if k < K:
            l = m
        else:
            h = m

    print(h)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=np.array(readline().strip().split(),dtype="int64")
    
    a.sort()
    neg=a[a<0]
    neg_p=neg**2
    zero=a[a==0]
    pos=a[a>0]
    pos_p=pos**2
    l=-10**18-1
    r=10**18
    while l<r-1:
        x=(l+r)//2
        cnt=0
        if len(neg)>0:
            cnt+=(len(a)-np.searchsorted(a,(x+neg+1)//neg)).sum()
            cnt-=len(neg_p[neg_p<=x])
        if len(zero)>0:
            if x>=0:
                cnt+=(len(a)-1)*len(zero)
        if len(pos)>0:
            cnt+=np.searchsorted(a,x//pos,side="right").sum()
            cnt-=len(pos_p[pos_p<=x])

        cnt//=2
        if cnt>=k: r=x
        else: l=x

    print(r)

if __name__=="__main__":
    main()

Submission status: Accepted

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

N, K = map(int, stdin.readline().split())
# A = np.array(stdin.read().split(), np.int64)
A = list(map(int, stdin.read().split()))

# A = np.sort(A)
# zero = A[A == 0]
# pos = list(A[A > 0])
# neg = list(A[A < 0])

A.sort()
zero = list(filter(lambda x: x == 0, A))
pos = list(filter(lambda x: x > 0, A))
neg = list(filter(lambda x: x < 0, A))

pos_size = len(pos)
neg_size = len(neg)
zero_size = len(zero)

neg_count = pos_size * neg_size
pos_count = pos_size * (pos_size - 1) // 2 + neg_size * (neg_size - 1) // 2
zero_count = N * (N - 1) // 2 - neg_count - pos_count

if K > neg_count and K <= neg_count + zero_count:
    print(0)
    exit(0)

def f(x):
    """x以下の積の組み合わせを数える(k番目が負の場合)"""
    count = 0
    pos_idx = None
    neg_idx = 0
    for idx, p in enumerate(pos):
        if p * neg[neg_idx] <= x:
            pos_idx = idx
            break
    # pos_idxに最大の負の値x正の値 <= xを満たす最小の正値のindexが入っている
    if pos_idx is not None:
        count += pos_size - pos_idx
        # print(pos_idx, count)
        while neg_idx < neg_size - 1:
            neg_idx += 1
            ans = None
            for i in range(pos_idx, pos_size):
                if pos[i] * neg[neg_idx] <= x:
                    ans = i
                    break
            if ans is None:
                break
            count += pos_size - ans
            pos_idx = ans
    return count

def g(x):
    """x以下の積の組み合わせを数える(k番目が正の場合)"""
    count = neg_count + zero_count
    # print('c1', count)
    l_idx = 0
    r_idx = 0
    # 正数 x 正数の場合
    for idx, p in enumerate(reversed(pos)):
        if p * pos[l_idx] <= x:
            r_idx = pos_size - idx - 1
            break
    if r_idx > 0:
        count += (r_idx + 1) - 1  # index = 0の分は引く
        while r_idx - l_idx > 0:
            l_idx += 1
            ans = l_idx
            # print(l_idx, r_idx)
            # for i in reversed(range(l_idx + 1, r_idx + 1)):
            for i in range(r_idx, l_idx, -1):
            # for j in range(l_idx + 1, r_idx + 1):
            #     i = r_idx + l_idx + 1 - j
                if pos[i] * pos[l_idx] <= x:
                    ans = i
                    break
            # print('ans', ans, l_idx)
            if ans > l_idx:
                count += ans - l_idx
                r_idx = ans
            else:
                break
    # print('c2', count)
    # 負数 x 負数の場合
    r_idx = neg_size - 1
    l_idx = neg_size - 1
    for idx, n in enumerate(neg):
        if n * neg[r_idx] <= x:
            l_idx = idx
            break
    # print(l_idx, r_idx)
    if l_idx < r_idx:
        count += neg_size - l_idx - 1 # r_idxの分は引く
        # print('c3', count)
        while r_idx - l_idx > 0:
                r_idx -= 1
                ans = r_idx
                # print(l_idx, r_idx)
                for i in range(l_idx, r_idx):
                    # print(i, pos[i], l_idx, pos[l_idx])
                    if neg[i] * neg[r_idx] <= x:
                        ans = i
                        break
                # print(l_idx, r_idx, ans)
                # print('ans', ans, l_idx)
                if ans < r_idx:
                    count += r_idx - ans
                    l_idx = ans
                else:
                    break
    return count


def h(x):
    return f(x) if K <= neg_count else g(x)


# print(h(-7))

def main():
    l = -1 * 10 ** 18
    r = 10 ** 18
    if K <= neg_count:
        r = 0
        h = f
    else:
        l = 0
        h = g

    while l + 1 < r:
        mid = (l + r) // 2
        count = h(mid)
        # print(mid, count)
        if count >= K:
            r = mid
        else:
            l = mid
    print(r)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N,K = MI()
A = LI()
minus,zero,plus = [], [], []
for i in A:
    if i<0:
        minus.append(i)
    elif i==0:
        zero.append(i)
    else:
        plus.append(i)
m = len(minus)
p = len(plus)
z = len(zero)
minus.sort()
plus.sort()

def count_lower_negpos(v): #pos*negでv以下のペアを数える
    if not minus or not plus:
        return 0
    m_idx = 0
    p_idx = 0
    ans = 0
    while True:
        val = minus[m_idx]*plus[p_idx]
        if val < v:
            ans += p - p_idx
            m_idx += 1
            if m_idx>m-1:
                break
        else:
            p_idx += 1
            if p_idx>p-1:
                break
    return ans

def count_lower_pospos(v): #pos同士でv以下のペアを数える
    if not plus:
        return 0
    left = 0
    right = p-1
    ans = 0
    while True:
        val = plus[left]*plus[right]
        if val < v:
            ans += right - left
            left += 1
            if left>=right:
                break
        else:
            right -= 1
            if left>=right:
                break
    return ans

def count_lower_negneg(v): #neg同士でv以下のペアを数える
    if not minus:
        return 0
    left = 0
    right = m-1
    ans = 0
    while True:
        val = minus[left]*minus[right]
        if val < v:
            ans += right - left
            right -= 1
            if left>=right:
                break
        else:
            left += 1
            if left>=right:
                break
    return ans


if K <= m*p: #答えがマイナス
    l = -10**18-5
    r = 0
    while l+1<r:
        x = (l+r)//2
        if count_lower_negpos(x) < K:
            l = x
        else:
            r = x
    print(l)


elif K <= m*p+z*(m+p)+z*(z-1)//2: #答えがゼロ
    print(0)

else: #答えがプラス
    K = K - (m*p+z*(m+p)+z*(z-1)//2)
    l = 0
    r = 10**18+5
    while l+1<r:
        x = (l+r)//2
        if count_lower_pospos(x)+count_lower_negneg(x) < K:
            l = x
        else:
            r = x
    print(l)

Submission status: Accepted

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]
l = -10**18-1
r = 10**18+1
while r-l > 1:
    mid = (r+l)//2
    cnt = 0
    if mid >= 0:
        cnt += len(zero)*n
    cnt += a.searchsorted(mid//posi, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//nega), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt //= 2
    if cnt >= k:
        r = mid
    else:
        l = mid
print(r)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

pos_start = bisect_right(a, 0)
neg_end = bisect_left(a, 0)

pos_cnt = n - pos_start
neg_cnt = neg_end

pairs_cnt = n * (n - 1) // 2
pos_pairs_cnt = pos_cnt * (pos_cnt - 1) // 2 + neg_cnt * (neg_cnt - 1) // 2
neg_pairs_cnt = pos_cnt * neg_cnt

if k <= neg_pairs_cnt:
    high = 0
    low = -10 ** 18
    while abs(high - low) > 1:
        mid = (high + low) // 2
        cnt = 0
        r = pos_start
        for l in range(neg_end):
            while r < n and mid < a[r] * a[l]:
                r += 1
            cnt += pos_cnt - (r - pos_start)

        if cnt >= k:
            high = mid
        else:
            low = mid

    print(high)

elif pairs_cnt - pos_pairs_cnt < k:
    k -= (pairs_cnt - pos_pairs_cnt)
    high = 10 ** 18
    low = 0
    while abs(high - low) > 1:
        mid = (high + low) // 2
        cnt = 0
        r = n - 1
        for l in range(pos_start, n):
            while l < r and mid < a[r] * a[l]:
                r -= 1
            cnt += max(0, r - l)
        
        l = 0
        for r in range(neg_end-1, -1, -1):
            while l < r and mid < a[r] * a[l]:
                l += 1
            cnt += max(0, r - l)

        if cnt >= k:
            high = mid
        else:
            low = mid

    print(high)

else:
    print(0)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
 
negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)
 
positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)
 
negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

if K <= negative_pairs_cnt:
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)
 
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X
 
    print(ok)

elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

else:
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0
 
        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)
 
        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1
 
            or_higher_cnt += max(0, r - l)
 
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X
 
    print(ok)

Submission status: Accepted

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

pos = []
neg = []
zero = 0
for a in A:
    if a > 0:
        pos.append(a)
    elif a == 0:
        zero += 1
    else:
        neg.append(a)
        
len_pos = len(pos)
len_neg = len(neg)

cnt_pos = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
cnt_neg = len_pos * len_neg
cnt_zero = zero * (zero - 1) // 2 + zero * (len_pos + len_neg)
#print(cnt_pos, cnt_neg, cnt_zero, cnt_pos + cnt_neg + cnt_zero, N * (N - 1) // 2)

if K <= cnt_neg:
    pos.sort()
    neg.sort()
    ok = 10 ** 19
    ng = -10 ** 19
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        pos_i, neg_i = len_pos - 1, len_neg - 1
        cnt = 0
        while pos_i >= 0 and neg_i >= 0:
            if pos[pos_i] * neg[neg_i] <= mid:
                cnt += neg_i + 1
                pos_i -= 1
            else:
                if neg_i:
                    neg_i -= 1
                else:
                    pos_i -= 1
        if cnt >= K:
            ok = mid
        else:
            ng = mid
    print(ok)

elif K <= cnt_neg + cnt_zero:
    print(0)
    
else:
    K -= cnt_neg + cnt_zero
    pos.sort()
    neg = [abs(n) for n in neg]
    neg.sort()

    ok = 10 ** 19
    ng = -10 ** 19
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        left, right = 0, len_pos - 1
        cnt = 0
        while left <= len_pos - 1 and right >= 0:
            if pos[left] * pos[right] <= mid:
                cnt += right + 1
                if left <= right:
                    cnt -= 1
                left += 1
            else:
                if right:
                    right -= 1
                else:
                    left += 1

        left, right = 0, len_neg - 1
        while left <= len_neg - 1 and right >= 0:
            if neg[left] * neg[right] <= mid:
                cnt += right + 1
                if left <= right:
                    cnt -= 1
                left += 1
            else:
                if right:
                    right -= 1
                else:
                    left += 1
        cnt //= 2
        
        if cnt >= K:
            ok = mid
        else:
            ng = mid
    print(ok)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

an = []
az = []
ap = []

for i in range(n):
    if a[i] < 0:
        an.append(a[i])
    elif a[i] == 0:
        az.append(a[i])
    else:
        ap.append(a[i])

an = sorted(an)
ap = sorted(ap)

an_rev = sorted(an, reverse=True)


def count(x):
    cnt = 0
    if x < 0:
        r = 0
        for t in ap:
            while r < len(an) and t*an[r] <= x:
                r += 1
            cnt += r
    elif x == 0:
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    else:
        r = 0
        for t in ap[::-1]:
            while r < len(ap) and t*ap[r] <= x:
                r += 1
            cnt += r
            if t*t <= x:
                cnt -= 1
        r = 0
        for t in an:
            while r < len(an) and t*an_rev[r] <= x:
                r += 1
            cnt += r
            if t*t <= x:
                cnt -= 1
        cnt //= 2
        cnt += len(az)*(len(az)-1)//2 + len(az)*(n-len(az)) + len(ap)*len(an)
    return cnt


bottom = -10**18-1
top = 10**18+1

while top - bottom > 1:
    mid = (top + bottom) // 2
    if count(mid) >= k:
        top = mid
    else:
        bottom = mid

print(top)

Submission status: Accepted

Solution code:
from bisect import *
n, k = map(int, input().split())
a = list(map(int, input().split()))

posi = 0
nega = 0
zero = 0
p = []
m = []

for i in range(n):
    if a[i] > 0:
        p.append(a[i])
        posi += 1
    elif a[i] < 0:
        nega += 1
        m.append(-a[i])
    else:
        zero += 1

p.sort()
m.sort()

if k <= posi*nega:
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)-1, -1, -1):
            count -= nega-bisect_left(m, (mid-1)//p[i]+1)
            if count <= 0:
                break
        if count <= 0:
            l = mid
        else:
            r = mid
        #print(r, l)

    print(-l)

elif k <= posi*nega+zero*(zero-1)//2+zero*(posi+nega):
    print(0)

else:
    k -= posi*nega+zero*(zero-1)//2+zero*(posi+nega)
    l = 0
    r = 10**18
    while r - l > 1:
        mid = l+(r-l)//2
        count = k
        for i in range(len(p)):
            count -= max(bisect_right(p, (mid)//p[i])-i-1, 0)
            if count < 0:
                #continue
                break
        for i in range(len(m)):
            count -= max(bisect_right(m, (mid)//m[i])-i-1, 0)
            if count < 0:
                #continue
                break

        if count > 0:
            l = mid
        else:
            r = mid
    print(r)

Submission status: Accepted

Solution code:
#https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-02-16abc-155
import numpy as np
N,K=map(int,input().split())
A=np.array(list(map(int,input().split())))
A.sort()
G=A[A>0]
Z=A[A==0]
L=A[A<0]

ok=10**18+1
ng=-10**18-1

#x以下がK個以上であるxの最小値

while ok-ng>1:
  mid = (ng+ok)//2
  #mid以下のペアの個数を数える
  
  #正のもののうち、mid以下のペアの個数を数える
  cg=np.searchsorted(A,mid//G,side="right").sum()
  
  #負のもののうちmid以下のペアの個数を数える
  cl=(N-np.searchsorted(A,(-mid-1)//(-L),side="right")).sum()
  
  #同じ数字同士の積がmid以下のものを数える
  d = np.count_nonzero(A*A <= mid)
  
  #0がmid以下なら、それもプラスするために必要
  z=0
  if mid>=0:
    z += len(Z)*N
  
  c=cg+cl+z-d
  
  #二重になっているので、割る
  c //=2
  
  #mid以下のペアの個数がK個以上のとき
  if c>=K:
    ok=mid
  else:
    ng=mid
    
print(ok)

Submission status: Accepted

Solution code:
import bisect, sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

pl = []
mi = []
ze = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(-x)
    else:
        ze += 1

p, m = len(pl), len(mi)
res1 = p * m
res2 = (p + m) * ze + ze * (ze - 1) // 2

#K番目が負
if res1 >= k:
    pl.sort(reverse=True)
    mi.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = p * m
        tmp = 0
        for i in range(p):
            while tmp < m and pl[i] * mi[tmp] < x:
                tmp += 1
            cnt -= tmp
        if cnt < k:
            r = x
        else:
            l = x
    print(-l)

#K番目が0
elif res1 + res2 >= k:
    print(0)

#K番目が正
else:
    k = k - res1 - res2
    pl.sort(reverse=True)
    pl2 = pl[::-1]
    mi.sort(reverse=True)
    mi2 = mi[::-1]
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = 0
        tmp = 0
        for i in range(p):
            if pl[i] ** 2 <= x:
                cnt -= 1
            while tmp < p and pl[i] * pl2[tmp] <= x:
                tmp += 1
            cnt += tmp
        tmp = 0
        for i in range(m):
            if mi[i] ** 2 <= x:
                cnt -= 1
            while tmp < m and mi[i] * mi2[tmp] <= x:
                tmp += 1
            cnt += tmp

        cnt //= 2
        if cnt < k:
            l = x
        else:
            r = x
    print(r)

Submission status: Accepted

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

p = a[a>0]
m = a[a<0]
z = np.count_nonzero(a==0)

def count(x):
  cnt = 0
  if x>=0:
    cnt+=z*n
  cnt += a.searchsorted(x//p,side='right').sum()
  cnt += n*len(m) - a.searchsorted(-(-x//m),side='left').sum()
  cnt -= np.count_nonzero(a*a<=x)
  return cnt//2
l,r = -10**19,10**19
while r-l>1:
  mid = (l+r)//2
  cnt = count(mid)
  if cnt >= k:
    r = mid
  else:
    l = mid
print(r)