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

Solution (Python):
import numpy as np
import math
stdin = open(0)

N,K = map(int,input().split())
A = np.array([int(Ai) for Ai in input().split()])
A = np.sort(A)

maxA = max(np.abs(A))

z = A[A==0]
p = A[A>0]
n = A[A<0]

def check(x):
    ret = 0
    if x >= 0:
        ret += N*len(z)
    ret += np.searchsorted(A,x//p,side='right').sum()
    ret += (N - np.searchsorted(A, (-x - 1) // (-n), side='right')).sum()

    ret -= np.count_nonzero(A*A<=x)
    return ret//2;

ub = maxA*maxA
lb = -ub-1
while ub-lb > 1:
    mid = (ub+lb)>>1
    if check(mid) < K:
        lb = mid
    else:
        ub = mid
print(ub)

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()

    
    neg, zero, pos = [], [], []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a == 0:
            zero.append(a)
        else:
            pos.append(a)

    prod_neg = len(neg) * len(pos)
    prod_zero = len(zero) * (len(neg)+len(pos))+len(zero)*(len(zero)-1)//2
    

    if prod_neg >= K:
        
        left = neg[0]*pos[-1]-1
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            
            counter = 0
            ps = 0
            for ns in range(len(neg)):
                while ps < len(pos) and neg[ns]*pos[ps] > mid:
                    ps += 1
                if ps == len(pos):
                    break
                counter += len(pos)-ps
            if counter < K:
                left = mid
            else:
                right = mid
        print(right)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        KK = K-prod_neg-prod_zero
        
        left = 0
        right = 0
        if len(neg) > 0:
            right = max(neg[0]**2, right)
        if len(pos) > 0:
            right = max(pos[-1]**2, right)
        while right - left > 1:
            mid = (left + right)//2
            
            counter = 0
            end = len(pos)-1
            for start in range(len(pos)):
                while end >= start and pos[start]*pos[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
            start = 0
            for end in range(len(neg)-1, -1, -1):
                while end >= start and neg[start]*neg[end] >= mid:
                    start += 1
                if end <= start:
                    break
                counter += end-start
            if counter < KK:
                left = mid
            else:
                right = mid
        print(left)


if __name__ == '__main__':
    main()

Solution (Python):
import sys


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

    A.sort()

    
    neg, zero, pos = [], [], []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a == 0:
            zero.append(a)
        else:
            pos.append(a)

    prod_neg = len(neg) * len(pos)
    prod_zero = len(zero) * (len(neg)+len(pos))+len(zero)*(len(zero)-1)//2
    prod_pos = len(neg)*(len(neg)-1)//2 + len(pos)*(len(pos)-1)//2

    if prod_neg >= K:
        
        left = neg[0]*pos[-1]-1
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            
            counter = 0
            ps = 0
            for ns in range(len(neg)):
                while ps < len(pos) and neg[ns]*pos[ps] > mid:
                    ps += 1
                if ps == len(pos):
                    break
                counter += len(pos)-ps
            if counter < K:
                left = mid
            else:
                right = mid
        print(right)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        
        left = 0
        right = 0
        if len(neg) > 0:
            right = max(neg[0]**2, right)
        if len(pos) > 0:
            right = max(pos[-1]**2, right)
        while right - left > 1:
            mid = (left + right)//2
            
            counter = 0
            end = len(pos)-1
            for start in range(len(pos)):
                while end >= start and pos[start]*pos[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
            start = 0
            for end in range(len(neg)-1, -1, -1):
                while end >= start and neg[start]*neg[end] >= mid:
                    start += 1
                if end <= start:
                    break
                counter += end-start
            if counter < K-prod_neg-prod_zero:
                left = mid
            else:
                right = mid
        print(left)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
INF = float("inf")


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

    A.sort()

    
    neg, zero, pos = [], [], []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a == 0:
            zero.append(a)
        else:
            pos.append(a)
    neg.sort()
    pos.sort()

    prod_neg = len(neg) * len(pos)
    prod_zero = len(zero) * (len(neg)+len(pos))+len(zero)*(len(zero)-1)//2
    prod_pos = len(neg)*(len(neg)-1)//2 + len(pos)*(len(pos)-1)//2
    
    
    

    if prod_neg >= K:
        
        left = neg[0]*pos[-1]-1
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            
            counter = 0
            ns, ps = 0, 0
            for ns in range(len(neg)):
                while ps < len(pos) and neg[ns]*pos[ps] > mid:
                    ps += 1
                if ps == len(pos):
                    break
                counter += len(pos)-ps
            
            if counter < K:
                left = mid
            else:
                right = mid
        print(right)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        neg.sort(reverse=True)
        
        left = 0
        right = 0
        if len(neg) > 0:
            right = max(neg[-1]**2, right)
        if len(pos) > 0:
            right = max(pos[-1]**2, right)
        right += 1
        while right - left > 1:
            mid = (left + right)//2
            
            counter = 0
            start, end = 0, len(pos)-1
            
            for start in range(len(pos)):
                while end >= start and pos[start]*pos[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
                
            start, end = 0, len(neg)-1
            for start in range(len(neg)):
                while end >= start and neg[start]*neg[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
                
            
            if counter < K-prod_neg-prod_zero:
                left = mid
            else:
                right = mid
        print(left)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
a.sort()
pz = a[a > 0]
ng = a[a < 0]
z = np.count_nonzero(a == 0)


def count(x):
    res = 0
    if x >= 0:
        res += z * n
    res += np.searchsorted(a, x // pz, side="right").sum()
    res += n * len(ng) - np.searchsorted(a, -(-x // ng), side="left").sum()
    res -= np.count_nonzero(a * a <= x)
    return res // 2


l, r = -10 ** 19, 10 ** 19
while r - l > 1:
    m = (l + r) // 2
    if count(m) >= k:
        r = m
    else:
        l = m
print(r)

Solution (Python):



MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()

  Ans, Aps, Azs = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      Azs.append(A)
    else:
      Ans.append(A)

  def count(xs, ys, ub):
    c = 0
    r = len(ys) - 1
    for l in range(len(xs)):
      while  r >= 0 and xs[l] * ys[r] > ub:
        r -= 1
      c += r+1
    return c 

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      
      tot = 0      
      tot += count(Aps, Aps, mid) - sum([1 for A in Aps if A**2 <= mid])
      tot += count(Ans[::-1], Ans[::-1], mid) - sum([1 for A in Ans if A**2 <= mid])
      tot //= 2

      if mid >=0:
        tot += (len(Aps) + len(Ans)) * len(Azs) + (len(Azs) * (len(Azs) - 1)) // 2
      tot += count(Aps[::-1], Ans, mid)
      
      if tot < k:
        l = mid
      else:
        r = mid
  
  print(bs(MIN-1, MAX+1))
    
    
if __name__=='__main__':
  main()

Solution (Python):
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(i) for i in input().split()]
Pos = [x for x in L if x > 0]
Zero = [x for x in L if x == 0]
Neg = [x for x in L if x < 0]
Pos.sort()
Neg.sort(reverse=True)

Po = len(Pos)
Ne = len(Neg)
Ze= len(Zero)

ZeN = Ze*(Ze-1)//2 + Ze*(Po+Ne)
NeN = Po*Ne

if NeN<K<=NeN+ZeN:
    print(0)

else:
    def f(x):
        cnt = 0
        if x < 0:
            j = Po - 1
            for i in range(Ne):
                j=min(Po-1,j+1)
                while j >=0:
                    if Neg[i] * Pos[j] <= x:
                        j = j - 1
                    else:
                        break
                cnt = cnt + Po - j - 1
        else:
            j = 0
            for i in range(Po)[::-1]:
                j=max(0,j-1)
                while j < i:
                    if Pos[i]*Pos[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            j = 0
            for i in range(Ne)[::-1]:
                j = max(0, j - 1)
                while j < i:
                    if Neg[i]*Neg[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            cnt = cnt + ZeN + NeN
        return(cnt)

    Hi = 10**18
    Lo = -10**18

    while Hi-Lo > 1:
        Mid = (Hi + Lo) // 2
        if f(Mid) >= K:
            Hi = Mid
        else:
            Lo = Mid
    print(Hi)

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

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

neg = bisect_left(A, 0)
pos = bisect_right(A, 0)

def less(x):
    res = 0
    b = 0
    for i in range(0, neg):
        while b != N and A[i] * A[b] >= x:
            b += 1
        while b != 0 and A[i] * A[b - 1] < x:
            b -= 1
        res += max(i - b, 0)
    for i in range(neg, pos):
        if x > 0:
            res += i
    for i in range(pos, N):
        while b != N and A[i] * A[b] < x:
            b += 1
        while b != 0 and A[i] * A[b - 1] >= x:
            b -= 1
        res += min(b, i)
    return res

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

Solution (Python):
import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = len(n[np.where(n==0)])
mp = n[np.where(n>0)]
M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    if pos >= 0: a+=mz*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
        
print(M)

Solution (Python):
import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]
M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    if pos >= 0: a+=len(mz)*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
        
print(M)

Solution (Python):
import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]

cn = len(mn)
cp = len(mp)
cz = len(mz)

if cn*cp < K <= cn*cp + (N-cz)*cz + cz*(cz-1)//2:
    print(0)
    exit(0)

M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    if pos >= 0: a+=cz*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos

print(M)

Solution (Python):
import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]










M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    if pos >= 0: a+=len(mz)*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos

print(M)

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x):
    ans = 0
    la, lb = len(a), len(b)
    J = (i for i in range(lb)) if a == b else (-1 for i in range(la))

    j = lb - 1
    for i, k in enumerate(J):
        xa = a[i]

        for j in range(j, k, -1):
            x1 = b[j] * xa
            if x1 <= x:
                break
        else:
            break
        ans += j - k

    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid)
            
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A[0].sort(reverse=True)
    A[2].sort()
    K3 = K - a0 - a1 - 1
    
    lo, hi = 0, 10**18
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A[0], A[0], mid) + cnt_val(A[2], A[2], mid)
        
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x):
    ans = 0
    la, lb = len(a), len(b)
    J = (i for i in range(lb)) if a == b else (-1 for i in range(la))

    j = lb - 1
    for i, k in enumerate(J):
        xa = a[i]

        for j in range(j, k, -1):
            x1 = b[j] * xa
            if x1 <= x:
                break
        else:
            break
        ans += j - k

    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid)
            
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    
    lo, hi = 0, 10**18
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid) + cnt_val(A[2], A[2], mid)
        
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)


def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            while pR>=0:
                if na*pA[pR]>x: break
                pR-=1
            ret+=len(pA)-pR-1
    elif x==0:
        ret+=neg
        ret+=zzz
        ret//=2
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)-1
        for na in nA:
            while pR>=0:
                if na*nA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if na*na<=x else 0
        pR=len(pA)-1
        for pa in pA:
            while pR>=0:
                if pa*pA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if pa*pa<=x else 0
        ret//=2
    return ret

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

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x, cache):
    ans = 0
    la, lb = len(a), len(b)
    J = (i for i in range(lb)) if a == b else (-1 for i in range(la))

    if len(cache) == 0:
        ca = [x, 0]
        cb = [inf, lb-1]
        cache.append(ca)
        cache.append(cb)
    else:
        ca, cb = cache
        if x <= ca[0]:
            cache[0], cache[1] = ca, cb = cb, ca
        ca[0] = x

    j = cb[1]
    
    for i, k in enumerate(J):
        xa = a[i]

        for j in range(j, k, -1):
            x1 = b[j] * xa
            if x1 <= x:
                break
        else:
            break
        ans += j - k
        if i == 0:
            ca[1] = j

    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        cache1 = []
        
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid, cache1)
            
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    
    lo, hi = 0, 10**18
    cache1, cache2 = [], []
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid, cache1) + cnt_val(A[2], A[2], mid, cache2)
        
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x, cache):
    ans = 0
    la, lb = len(a), len(b)
    J = (i for i in range(lb)) if a == b else (-1 for i in range(la))

    j = lb - 1
    
    for i, k in enumerate(J):
        xa = a[i]

        for j in range(j, k, -1):
            x1 = b[j] * xa
            if x1 <= x:
                break
        else:
            break
        ans += j - k

    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        cache1 = []
        
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid, cache1)
            
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    
    lo, hi = 0, 10**18
    cache1, cache2 = [], []
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid, cache1) + cnt_val(A[2], A[2], mid, cache2)
        
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Solution (Python):
N, K = map(int, input().split())
A = [int(c) for c in input().split()]
Ap = []
An = []
Az = []
for i in range(N):
  if A[i]>0:
    Ap += [A[i]]
  elif A[i]<0:
    An += [A[i]]
  else:
    Az += [A[i]]
lp = len(Ap)
ln = len(An)
lz = len(Az)
Ap.sort(reverse=True)
An.sort(reverse=True)
def f(m, B, C):
  cnt = 0
  j  = 0
  lb = len(B)
  lc = len(C)
  for i in range(lc):
    while j<lb:
      if B[j]*C[i]>=m:
        cnt += j
        break
      j += 1
    else:
      cnt += j
  return cnt
if K<=lp*ln:
  r = 1
  l = -10**18+10
  while l+1<r:
    n = (l+r)//2
    if f(n,Ap,An)>=K:
      r = n
    else:
      l = n
  print(l)
  import sys
  sys.exit()
K -= lp*ln
if K<=lz*(lp+ln) + lz*(lz-1)//2:
  print(0)
  import sys
  sys.exit()
K -= lz*(lp+ln) + lz*(lz-1)//2
r = 10**18+10
l = -1
while l+1<r:
  n = (l+r)//2
  P = f(n,Ap[::-1],Ap)
  for i in range(lp):
    if Ap[lp-1-i]*Ap[lp-1-i]<n:
      P -= 1
    else:
      break
  P //= 2
  N = f(n,An,An[::-1])
  for i in range(ln):
    if An[i]*An[i]<n:
      N -= 1
    else:
      break
  N //= 2
  if P+N>=K:
    r = n
  else:
    l = n
print(l)

Solution (Python):
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    if m > 0:
    	negative = np.array(A[:m], np.int64)
    else:
      	negative = np.array([], np.int64)
    if p > 0:
    	positive = np.array(A[-p:], np.int64)
    else:
      	positive = np.array([], np.int64)
    negative = -negative[::-1]
    

    if K <= M:
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, (mid + negative - 1) // negative, side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        left = 0
        right = max(A[0] * A[1], A[-1] * A[-2])
        positive2 = positive ** 2
        negative2 = negative ** 2
        while left + 1 < right:
            mid = (left + right) // 2
            a = np.searchsorted(negative, mid // negative, side='right').sum() - (mid >= negative2).sum()
            b = np.searchsorted(positive, mid // positive, side='right').sum() - (mid >= positive2).sum()

            if (a + b) // 2 < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer[K - 1])


def main():
    read = sys.stdin.read

    N, K, *A = map(int, read().split())

    if N <= 10:
        test(A, K)
        exit()
    A.sort()
    A = np.array(A, np.int64)
    negative = A[A < 0]
    positive = A[A > 0]
    m = len(negative)
    p = len(positive)
    z = N - m - p

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = -negative[::-1]
    

    if K <= M:
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, (mid + negative - 1) // negative, side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        K -= M + Z
        left = 0
        right = max(A[0] * A[1], A[-1] * A[-2])
        positive2 = positive ** 2
        negative2 = negative ** 2
        while left + 1 < right:
            mid = (left + right) // 2
            a = np.searchsorted(negative, mid // negative, side='right').sum() - (mid >= negative2).sum()
            b = np.searchsorted(positive, mid // positive, side='right').sum() - (mid >= positive2).sum()

            if (a + b) // 2 < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x, cache):
    ai = 1 if a == b else 0
    ans = 0

    la, lb = len(a), len(b)
    if len(cache) == 0:
        loa = [i+1 for i in range(la-1)] if ai else [0] * la
        hia = [lb] * la
        mia = [0] * la

        cache.append([-inf, loa])
        cache.append([x, mia])
        cache.append([inf, hia])
        ic = 1
    else:
        if x < cache[1][0]:
            cache[1], cache[2] = cache[2], cache[1]
        else:
            cache[0] ,cache[1] = cache[1], cache[0]

        cache[1][0] = x

        loa = cache[0][1]
        mia = cache[1][1]
        hia = cache[2][1]

    for i in range(len(a) - ai):
        xa = a[i]

        lo, hi = loa[i], hia[i]

        

        while lo < hi:
            mid = (lo + hi) // 2
            x1 = b[mid] * xa
            

            if x1 <= x:
                lo = mid + 1
            else:
                hi = mid
        
        mia[i] = lo
        ans += lo
        if ai:
            ans -= i + 1
    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        cache1 = []
        
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid, cache1)
            
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    
    lo, hi = 0, 10**18
    cache1, cache2 = [], []
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid, cache1) + cnt_val(A[2], A[2], mid, cache2)
        
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Solution (Python):
import sys,bisect
input = sys.stdin.readline

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

    
    p = bisect.bisect_left(a,0)
    q = bisect.bisect_right(a,0)
    zeros = q-p

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

        
        cnt = 0
        if mid == 0:
            
            cnt += p*(n-p)
            
            cnt += (n-p)*(n-p-1)//2
        elif mid > 0:
            
            
            j = 0
            for i in range(p-1,-1,-1):
                while j <= p-1:
                    if a[i]*a[j] > mid:
                        j += 1
                    else:
                        break
                cnt += p-1-j+1
                if j <= i:
                    cnt -= 1
            
            
            
            j = n-1
            for i in range(q,n):
                while j >= q:
                    if a[i]*a[j] >  mid:
                        j -= 1
                    else:
                        break
                cnt += j-q+1
                if i <= j:
                    cnt -= 1
            
            cnt = cnt//2

            
            cnt += p*(n-p)
            
            
            cnt += zeros*(zeros-1)//2

            
            cnt += zeros*(n-q)
        else:
            
            
            j = q
            for i in range(p):
                while j < n:
                    if a[i]*a[j] >  mid:
                        j += 1
                    else:
                        break
                cnt += n-1-j+1

        if cnt >= k:
            ok = mid
        else:
            ng = mid
    print(ok)

if __name__ == "__main__":
    main()