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 = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import bisect
    mod=10**9+7
    N,K=MI()
    A=LI()
    pos=[]
    zero=[]
    nega=[]
    for i in range(N):
        if A[i]>0:
            pos.append(A[i])
        elif A[i]==0:
            zero.append(A[i])
        else:
            nega.append(A[i]*-1)
            
    np=len(pos)
    nz=len(zero)
    nn=len(nega)
    
    pos.sort()
    zero.sort()
    nega.sort()
    
    inf=10**18 + 1
    
    #全部正で考える
    
    if K<=np * nn:
        # 答えが負になるパターン
        # 正の数で考えるので大きい方からK番目を考える
        # 二分探索*2
        # X以上になるものが，初めてK個以上になったタイミングが答え
        
        def ch(x):
            cnt=0
            for p in pos:
                t=(x+p-1)//p
                num=bisect.bisect_left(nega,t)
                cnt+=nn-num
            return cnt>=K
                
        
        ok=0
        ng=inf
        while ng-ok>1:
            x=(ok+ng)//2
            if ch(x):
                ok=x
            else:
                ng=x
        
        print(ok*-1)
        
    elif K<= np*nn + nz*(N-nz) + (nz*(nz-1))//2:
        print(0)
        
    else:
        # 答えが正になるパターン
        # 大きい方からK2= (N*(N-1))//2 - K番目を考える
        # 二分探索*2
        # X以上になるものが，初めてK2個以上になったタイミングが答え
        K2=(N*(N-1))//2 - K + 1
        # print(K2)
        
        def ch(x):
            cnt=0
            for p in pos:
                t=(x+p-1)//p
                num=bisect.bisect_left(pos,t)
                rem=np-num
                if t<=p:
                    rem-=1
                cnt+=rem
                
            for ne in nega:
                t=(x+ne-1)//ne
                num=bisect.bisect_left(nega,t)
                rem=nn-num
                if t<=ne:
                    rem-=1
                cnt+=rem
                
            cnt=cnt//2
            # print(x,cnt)
            return cnt>=K2
                
        
        ok=0
        ng=inf
        while ng-ok>1:
            x=(ok+ng)//2
            if ch(x):
                ok=x
            else:
                ng=x
        
        print(ok)
        
        
        

main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
Aminus=[]
Aplus=[]
negative=0
positive=0
posinega=0
for i in range(N):
    if A[i]>0:
        positive+=1
        Aplus.append(A[i])
    elif A[i]<0:
        negative+=1
        Aminus.append(A[i])
    else:
        posinega+=1
Aplus.sort()
Aminus.sort()
PLUS=positive*positive+negative*negative
MINUS=2*positive*negative
ZERO=N*N-PLUS-MINUS

PLUS=(PLUS-(N-posinega))//2
MINUS=MINUS//2
ZERO=(ZERO-posinega)//2
if K<=MINUS:
    #ans<0
    low=min(A)*max(A)
    high=0
    while(high-low>1):
        mid=(high+low)//2
        '''
        A[i]*A[j]<lowとなる(i<j)の組み合わせはK個未満である
        A[i]*A[j]<highとなる(i<j)の組み合わせはK個以上である
        tmpはA[i]*A[j]<midとなる(i<j)の組み合わせである
        '''
        tmp=0
        for i in range(positive):
            low0=-1
            high0=negative
            while(high0-low0>1):
                mid0=(high0+low0)//2
                '''
                Aplus[i]*Aminus[j]はjについて単調増加である。
                Aplus[i]*Aminus[low0]<mid<=Aplus[i]*Aminus[high0]を常に満たす必要がある
                '''
                if Aplus[i]*Aminus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
        if tmp<K:
            low=mid
        else:
            high=mid
    print(low)
elif K<=MINUS+ZERO:
    print(0)
else:
    K-=MINUS+ZERO
    #ans>0
    low=0
    high=max(min(A)**2,max(A)**2)
    Aminus=Aminus[::-1]
    while(high-low>1):
        mid=(high+low)//2
        '''
        A[i]*A[j]<lowとなる(i<j)の組み合わせはK個未満である
        A[i]*A[j]<highとなる(i<j)の組み合わせはK個以上である
        tmpはA[i]*A[j]<midとなる(i<j)の組み合わせである
        '''
        tmp=0
        for i in range(positive):
            low0=-1
            high0=positive
            while(high0-low0>1):
                mid0=(high0+low0)//2
                '''
                Aplus[i]*Aplus[j]はjについて単調増加である。
                Aplus[i]*Aplus[low0]<mid<=Aplus[i]*Aplus[high0]を常に満たす必要がある
                '''
                if Aplus[i]*Aplus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
            if Aplus[i]*Aplus[i]<mid:
                tmp-=1
        for i in range(negative):
            low0=-1
            high0=negative
            while(high0-low0>1):
                mid0=(high0+low0)//2
                if Aminus[i]*Aminus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
            if Aminus[i]*Aminus[i]<mid:
                tmp-=1
        tmp=tmp//2
        if tmp<K:
            low=mid
        else:
            high=mid
    print(low)

Submission status: Accepted

Solution code:
def General_Binary_Increase_Search(L,R,cond,Integer=True,ep=1/(1<<20)):
    """条件式が単調増加であるとき,一般的な二部探索を行う.
    L:解の下限
    R:解の上限
    cond:条件(1変数関数,広義単調減少 or 広義単調減少を満たす)
    Integer:解を整数に制限するか?
    ep:Integer=Falseのとき,解の許容する誤差
    """
    if not(cond(R)):
        return False

    if Integer:
        R+=1
        while R-L>1:
            C=L+(R-L)//2
            if cond(C):
                R=C
            else:
                L=C
        return R
    else:
        while (R-L)>=ep:
            C=L+(R-L)/2
            if cond(C):
                R=C
            else:
                L=C
        return R

def f(R):
    I=0
    S=0
    for a in Pos:
        if I<Negative:
            while a*Neg[I]<=R:
                I+=1
                if I==Negative:
                    break

        S+=I
    return S

def g(R):
    S=0

    I=Positive
    for a in Pos:
        if I>0:
            while a*Pos[I-1]>R:
                I-=1
                if I==0:
                    break
        S+=I
        if a*a<=R:
            S-=1

    J=0
    for b in Neg:
        if J<Negative:
            while b*Neg[-(J+1)]<=R:
                J+=1
                if J==Negative:
                    break
        S+=J
        if b*b<=R:
            S-=1

    return S>>1
#================================================
N,K=map(int,input().split())

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

Pos=[a for a in A if a>0]
Neg=[a for a in A if a<0]

Positive=Zero=Negative=0
for a in A:
    if a>0:
        Positive+=1
    elif a==0:
        Zero+=1
    else:
        Negative+=1

Pos_Count=(Positive*(Positive-1))//2+(Negative*(Negative-1))//2
Neg_Count=Positive*Negative
Zero_Count=(N*(N-1))//2-(Pos_Count+Neg_Count)

H=max(A,key=lambda a:abs(a))
H=H*H+1

if Neg_Count+1<=K<=Neg_Count+Zero_Count: #ゼロ確定
    Ans=0
elif K<=Neg_Count: #負確定
    Ans=General_Binary_Increase_Search(-H,0,lambda x:f(x)>=K)
else: #正確定
    Ans=General_Binary_Increase_Search(0,H,lambda x:g(x)>=K-(Neg_Count+Zero_Count))

print(Ans)

Submission status: Accepted

Solution code:
from numpy import *
N,K = map(int,input().split())
A = array(sorted(list(map(int,input().split()))))
nega = A[A<0]
zera = A[A==0]
posa = A[0<A]

def cnt(x):
  y = 0
  if x>=0:
    y+=N*len(zera)
  y+=searchsorted(A,x//posa,side="right").sum()
  y+=N*len(nega)-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 K<=cnt(c):
    r=c
  else:
    l=c

print(r)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
plus = []
minus = []
zero = 0
for i in range(n):
    if a[i] < 0:
        minus.append(-a[i])
    elif a[i] > 0:
        plus.append(a[i])
    else:
        zero += 1
plus.sort()
minus.sort()
p = len(plus)
m = len(minus)
am = p*m
ap = p*(p-1)//2 + m*(m-1)//2
az = n*(n-1)//2 - am - ap
# print(plus,minus)

def binary_search_func(ok, ng, f):
    while(abs(ok - ng) > 1):
        med = (ok + ng) // 2
        if(f(med) == True):
            ok = med
        else:
            ng = med
    return ok

if k <= am:
    def c(x):# ~-xはk個以上あるか？
        res = p*m
        v = 0
        for i in minus[::-1]:
            kk = (x+i-1)//i
            # x以下のやつを引いていく
            while v < p and plus[v] < kk:
                v += 1
            res -= v
        return res >= k

    ok = 0
    ng = 10**18
    ans = -(binary_search_func(ok, ng, c))
    
elif k <= am + az:
    ans = 0

else:
    k -= am + az
    def c(x):# 1~xはk個以上あるか？
        res = 0
        vm = m-1
        for i,ai in enumerate(minus):
            kkm = x//ai
            while vm and minus[vm] > kkm:
                vm -= 1
            if vm > i:
                res += vm - i
        vp = p-1
        for i,ai in enumerate(plus):
            kkp = x//ai
            while vp and plus[vp] > kkp:
                vp -= 1
            if vp > i:
                res += vp - i
        return res >= k
    
    ok = 10**18
    ng = 0
    ans = binary_search_func(ok, ng, c)

print(ans)

Submission status: Accepted

Solution code:
N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = max(A[0]**2,A[-1]**2)
ok1 = inf
ng1 = -inf
while (abs(ok1 - ng1) > 1):
    arg = (ok1 + ng1) // 2
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] == 0:
            if arg > 0:
                ans += N
        elif A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    if K>ans:
        ng1 = arg
    else:
        ok1 = arg
print(ng1)

Submission status: Accepted

Solution code:
import bisect

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

def count(t):
    c = 0
    for x in a:
        if x == 0:
            c += len(a) - 1 if t >= 0 else 0
        elif x > 0:
            c += bisect.bisect_left(a, (t // x) + 1) - (x * x <= t)
        else:
            c += len(a) - bisect.bisect_left(a, -(t // -x)) - (x * x <= t)
    return c

lo = -1000000000000000001
hi = 1000000000000000001
while hi - lo > 1:
    mid = (lo + hi) // 2
    if count(mid) < k * 2:
        lo = mid
    else:
        hi = mid
print(hi)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
def main():
    N, K = MI()
    A = LI()
    A.sort()
    def is_ok(arg):
        # 条件を満たすかどうか？問題ごとに定義、argを求めたい値にして条件をreturnで返す
        cnt = 0
        for a in A:
            if a == 0:
                if arg >= 0:
                    cnt += N - 1
                else:
                    cnt += 0
            elif a < 0:
                aa = -((-arg) // a)
                cnt += N - bisect.bisect_left(A, aa)
                if aa <= a:
                    cnt -= 1
            else:
                aa = arg // a
                cnt += bisect.bisect_right(A, aa)
                if aa >= a:
                    cnt -= 1
        cnt //= 2
        return cnt >= K

    def meguru_bisect(ng, ok):
        '''
        初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
        まずis_okを定義すべし
        ng ok は  とり得る最小の値-1 とり得る最大の値+1
        最大最小が逆の場合はよしなにひっくり返す
        '''
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok
    cnt_neg = bisect.bisect_left(A, 0)
    cnt_pos = N - bisect.bisect_right(A, 0)
    cnt_zer = N - cnt_pos - cnt_neg

    if K <= cnt_neg * cnt_pos:
        ng = - 10 ** 18 - 10
        ok = 1
        ans = meguru_bisect(ng, ok)
        print(ans)
    elif K <= cnt_neg * cnt_pos + cnt_zer * (N - 1) - cnt_zer * (cnt_zer - 1) // 2:
        print(0)
    else:
        ng = -1
        ok = 10 ** 18 + 10
        ans = meguru_bisect(ng, ok)
        print(ans)

if __name__ == "__main__":
    main()

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:
N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((mid+1)//(H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid-1)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from bisect import bisect_left, bisect_right

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

    negative_end = bisect_left(A, 0)
    postive_start = bisect_right(A, 0)

    postive_cnt = N - postive_start
    negative_cnt = negative_end
    zero_cnt = N - postive_cnt - negative_cnt

    negative_pairs_cnt = postive_cnt * negative_cnt
    zero_pairs_cnt = (zero_cnt * (postive_cnt + negative_cnt)
                      + (zero_cnt * (zero_cnt - 1) // 2))
    
    # 答えが負の場合
    if K <= negative_pairs_cnt:
        # 二分探索：mid以下になるペアがK個以上あるか？
        ok, ng = 0, -10 ** 19
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            or_higher_cnt, right = 0, postive_start
            for left in range(negative_end):
                while right < N and A[left] * A[right] > mid:
                    right += 1
                or_higher_cnt += postive_cnt - (right - postive_start)
            if or_higher_cnt >= K:
                ok = mid
            else:
                ng = mid
        print(ok)
    # 答えが0の場合
    elif K <= negative_pairs_cnt + zero_pairs_cnt:
        print(0)
    # 答えが正の場合
    else:
        # 二分探索：mid以下になるペアがK個以上あるか？
        K -= negative_pairs_cnt + zero_pairs_cnt
        ok, ng = 10 ** 19, 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            # 正*正の場合
            or_higher_cnt, right = 0, N - 1
            for left in range(postive_start, N):
                while right < N and A[left] * A[right] > mid and left < right:
                    right -= 1
                or_higher_cnt += max(0, right - left)
            # 負*負の場合
            left = 0
            for right in range(negative_end - 1, -1, -1):
                while left < N and A[left] * A[right] > mid and left < right:
                    left += 1
                or_higher_cnt += max(0, right - left)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

minus = 0
for i in range(n):
    if A[i] < 0:
        minus += 1
zplus = n - minus

B = []
C = []
for i in range(n):
    if A[i] < 0:
        C.append(A[i])
    else:
        B.append(A[i])
B.sort(reverse=True)
C.sort()


if k <= minus * zplus:
    ok = 1
    ng = -10**20
    m = (ok+ng) // 2
    while abs(ng-ok) > 1:
        co = 0
        j = len(C)-1
        for i in range(len(B)):
            while j >= 0 and B[i]*C[j] > m:
                j -= 1
            co += j+1
        # print(m, co)
        if co >= k:
            ok = m
            # print("ok")
        else:
            ng = m
            # print("ng")
        m = (ok+ng) // 2
    print(ok)
else:
    k -= minus * zplus
    ok = 10**20
    ng = -1
    m = (ok+ng) // 2
    while abs(ng-ok) > 1:
        co = 0
        j = len(C)-1
        for i in range(len(C)):
            while j > i and C[i]*C[j] <= m:
                j -= 1
            co += len(C)-1-j
            j = max(j, i+1)
        j = len(B)-1
        for i in range(len(B)):
            while j > i and B[i]*B[j] <= m:
                j -= 1
            co += len(B)-1-j
            j = max(j, i+1)

        if co >= k:
            ok = m
            # print("ok")
        else:
            ng = m
            # print("ng")
        m = (ok+ng) // 2
    print(ok)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid-1)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()
 
 
def is_ok(arg, sei, hu, k):
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    for index, NN in enumerate(sei, 1):
        if NN==0:
            count+=len(sei)-index
        else:
            if NN**2 >= arg:
                break
            count += bisect.bisect_right(sei, ((arg)//NN))-index  # n以下の個数を数える
    for index, NN in enumerate(hu, 1):
        if NN**2 >= arg:
            break
        count += bisect.bisect_right(hu, ((arg)//NN))-index  # n以下の個数を数える
    return count >= k
 
 
def meguru_bisect(ng, ok, sei, hu, k):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, sei, hu, k):
            ok = mid
        else:
            ng = mid
    return ok
 
 
def is_ok2(arg, sei, hu, k):#seiとhuの組み合わせで-arg以上の数がk個あるか？
    # 条件を満たすかどうか？問題ごとに定義
    count = 0
    hulen=len(sei)
    for NN in hu:
        count += hulen-bisect.bisect_right(sei, ((-arg)-1)//NN)#n未満の個数を数える
    return count >= k
 
def meguru_bisect2(ng, ok, sei, hu, k):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok2(mid, sei, hu, k):
            ok = mid
        else:
            ng = mid
    return ok
 
def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    sei = []
    hu = []
    for AA in A:
        if AA >= 0:
            sei.append(AA)
        else:
            hu.append(-AA)
    sei.sort()
    hu.sort()
    seinum = len(sei)
    hunum = len(hu)
    if seinum*hunum < k:
        ans=meguru_bisect(-1, 10**18, sei, hu, k-seinum*hunum)
    else:
        ans=meguru_bisect2(-1*10**18, 0, sei, hu, k)
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("YES") if fl else print("NO")
import collections
import math
import itertools
import heapq as hq
def isok1(x,ls1,ls2,cnt=0):
    ##ls1 :minus -2,-1  ls2 :plus 1,2,..
    l1,l2=0,0
    while l1<len(ls1) and l2<len(ls2):
        if ls1[l1]*ls2[l2] <= x:
            cnt+=len(ls2) -l2
            l1+=1
        else:
            l2+=1
    return cnt<k
def isok2(x,ls1,ls2,cnt=0):
    ##ls1 :minus -2,-1,  ls2 :plus 2,1,..
    l,r=0,0
    tmp=0
    while r<len(ls1) and l<len(ls1):
        if ls1[-l-1]*ls1[r] <=x:
            tmp+=len(ls1)-r
            l+=1
        else:
            r+=1
    for i in range(len(ls1)):
        if ls1[i]**2 <=x:tmp-=1
    cnt+=tmp//2
    l,r=0,0
    tmp=0
    while r<len(ls2) and l<len(ls2):
        #print(ls2[-l-1]*ls2[r],l,r)
        if ls2[-l-1]*ls2[r] <=x:
            tmp+=len(ls2)-r
            #print(tmp,ls2[-l-1]*ls2[r],l,r)
            l+=1
        else:
            r+=1
    for i in range(len(ls2)):
        if ls2[i]**2 <=x:tmp-=1
    cnt+=tmp//2
    #print(x,cnt)
    return cnt<k



n,k = ma()
A = lma()
pA = [a for a in A if a>0]
mA = [a for a in A if a<0]
pn = len(mA)*(len(mA)-1)//2 +len(pA)*(len(pA)-1)//2
mn = len(pA) *len(mA)
z = n*(n-1)//2 -pn -mn
if k<=mn:
    f=True
    pA.sort()
    mA.sort()
elif k>mn+z:
    f=False
    pA.sort(reverse=True)
    mA.sort()
else:
    print(0)
    exit()
#print(isok2(6,mA,pA,cnt=mn+z))
ok = -10**18-2
ng = 10**18+2
x = (ok+ng)//2

while ng-ok>1:
    if f:
        if isok1(x,mA,pA):
            ok = x
        else:
            ng=x
        x = (ok+ng)//2
    else:
        if isok2(x,mA,pA,cnt=mn+z):
            ok = x
        else:
            ng=x
        x = (ok+ng)//2
print(ng)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ll = - 10**18 - 1
rr = 10**18 + 1
while ll + 1 < rr:
  x = (ll + rr) // 2
  tot = 0
  for i in range(N):
    if A[i] < 0:
      l = -1
      r = N
      while l + 1 < r:
        c = (l + r) // 2
        if A[i] * A[c] < x:
          r = c
        else:
          l = c
      tot += N - r
    else:
      l = -1
      r = N
      while l + 1 < r:
        c = (l + r) // 2
        if A[i] * A[c] < x:
          l = c
        else:
          r = c
      tot += r
    if A[i] * A[i] < x:
      tot -= 1
  tot //= 2
  if tot < K:
    ll = x
  else:
    rr = x
print(ll)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right
# 自分より小さい数字がk個未満のうち最大の値を求める
# 自分より小さい数字がk個未満ならTrue
def func(mn,zn,pn,am,ap,x):
    cnt=0
    if x>0:
        cnt+=mn*pn
        cnt+=(zn*(n-1+n-zn))//2
        cnt1=0
        for y in ap:
            cnt1+=bisect_left(ap,(x+y-1)//y)
            if y**2<x:cnt1-=1
        for y in am:
            cnt1+=bisect_left(am,(x+y-1)//y)
            if y**2<x:cnt1-=1
        cnt+=cnt1//2
    elif x<0:
        x=abs(x)
        for y in ap:
            cnt+=mn-bisect_right(am,x//y)
    elif x==0:
        cnt+=mn*pn
    return cnt<k
def main(n,k,a):
    a.sort()
    # 0未満の個数
    mn=bisect_left(a,0)
    # 0の個数
    zn=bisect_right(a,0)-mn
    # 0より大きい個数
    pn=n-mn-zn
    am=a[:mn]
    am=[-x for x in am[::-1]]
    ap=a[mn+zn:]
    if k<=mn*pn:# 答えは負になる
        l,r=a[0]*a[-1]-1,0
    elif k<=mn*pn+zn*(n-zn)+(zn*(zn-1))//2:#答えはゼロになる
        print(0)
        exit()
    else:# 答えは正
        l,r=0,max(a[0]*a[1],a[-1]*a[-2])+1
    while r-l>1:
        x=(l+r)//2
        if func(mn,zn,pn,am,ap,x):
            l,r=x,r
        else:
            l,r=l,x
    print(l)

    """
    b=[]
    for i in range(n-1):
        for j in range(i+1,n):
            b.append(a[i]*a[j])
    b.sort()
    print(b[k-1])
    """
if __name__=='__main__':
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    main(n,k,a)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n,k=MI()
    lis=LI()
    p,z,m=0,0,0
    plus=[]
    minus=[]
    for i in range(n):
        if lis[i]>0:
            p+=1
            plus.append(lis[i])
        elif lis[i]==0:
            z+=1
        else:
            m+=1
            minus.append(lis[i])
    plus.sort()
    minus.sort()
    #print(plus)
    #print(minus)
    #plus,minus,sort
    resm=p*m
    resz=z*p+z*m+p*m+z*(z-1)//2
    if k<=resm:
        left=-10**18-1
        right=-1
        while left+1<right:
            x=(left+right)//2
            i=0
            ans=0
            j=0
            while i<p:
                while j<m:
                    if plus[i]*minus[j]<=x:
                        if j==m-1:
                            ans+=m
                            i+=1
                            break
                        j+=1
                    else:
                        i+=1
                        ans+=j
                        break
            #print(left,right,x,ans)
            if ans>=k:
                right=x
            else:
                left=x
        print(right)
    
    elif k<=resz:
        print(0)
        sys.exit()
    else:
        k=k-resz
        #print(k)
        left=0
        right=10**18
        square=[]
        for i in range(p):
            square.append(plus[i]**2)
        for i in range(m):
            minus[i]*=(-1)
            square.append(minus[i]**2)
        square.sort()
        plus.sort()
        minus.sort()
        plus2=sorted(plus,reverse=True)  
        minus2=sorted(minus,reverse=True)
        while left+1<right:
            x=(left+right)//2
            i=0
            ans=0
            j=0
            zure=bisect_right(square,x)-1
            while i<p:
                while j<p:
                    if plus2[i]*plus[j]<=x:
                        if j==p-1:
                            ans+=p
                            i+=1
                            break
                        j+=1
                    else:
                        i+=1
                        ans+=j
                        break
            i=0
            j=0
            while i<m:
                while j<m:
                    if minus2[i]*minus[j]<=x:
                        if j==m-1:
                            ans+=m
                            i+=1
                            break
                        j+=1
                    else:
                        i+=1
                        ans+=j
                        break
            #print(left,right,x,ans,zure,(ans-zure)//2)
            if (ans-zure)//2>=k:
                right=x
            else:
                left=x
        print(right)
            
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import decimal


def solve_gutyoku(N, K, A):
    A_combinations = []
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            A_combinations.append(A[i] * A[j])
    ans = sorted(A_combinations)[K-1]
    return ans


def solve(N, K, A):
    for i, a in enumerate(A):
        if a >= 0:
            break
    for j, a in enumerate(A):
        if a > 0:
            break
    A_hu = A[:i]
    A_0 = A[i:j]
    A_sei = A[j:]
    n_hu = len(A_hu)*len(A_sei)
    n_0 = len(A_0)*(len(A)-1) - len(A_0)*(len(A_0)-1)//2
    n_sei = (len(A_sei) - 1) * len(A_sei) // 2 + \
        (len(A_hu) - 1) * len(A_hu) // 2
    if K > n_hu and K <= n_hu + n_0:
        return 0
    elif K <= n_hu:
        left, right = int(-1 * 1e18), 0
        while right - left > 1:
            piv = (left + right) // 2
            cnt = 0
            i = 0
            for a in A_sei:
                while i < len(A_hu) and A_hu[i] * a <= piv:
                    i += 1
                cnt += i
            if cnt >= K:
                right = piv
            else:
                left = piv
        return right
    else:
        A_hu = [-1 * a for a in A_hu[::-1]]
        K -= n_hu + n_0
        left, right = 0, int(1e18) + 1
        while right - left > 1:
            piv = (left + right) // 2
            cnt = 0
            i = 0
            for a in A_sei[::-1]:
                while i < len(A_sei) and A_sei[i] * a <= piv:
                    i += 1
                cnt += i - (a * a <= piv)
            i = 0
            for a in A_hu[::-1]:
                while i < len(A_hu) and A_hu[i] * a <= piv:
                    i += 1
                cnt += i - (a * a <= piv)
            cnt = cnt // 2
            if cnt >= K:
                right = piv
            else:
                left = piv
        return right


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



main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=sorted(map(int,input().split()))
x=0
r=10**18+1
l=-(10**18)
while l+1<r:
    x=(l+r)//2
    k=0
    for a in A:
        if a<0:
            ll,rr=-1,N
            while ll+1<rr:
                c=(rr+ll)//2
                if x>a*A[c]:
                    rr=c
                else:
                    ll=c
            k+=N-rr
        else:
            ll,rr=-1,N
            while ll+1<rr:
                c=(rr+ll)//2
                if x>a*A[c]:
                    ll=c
                else:
                    rr=c
            k+=rr
        if x>a**2:
            k-=1
    k//=2
    if k<K:
        l=x
    else:
        r=x
print(l)