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 sys


def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def nC2(n):
    return n * (n-1) // 2

n,k = get_nums_l()
aaa = get_nums_l()

negatives = []
zeros = 0
positives = []

for a in aaa:
    if a == 0:
        zeros += 1
    elif a > 0:
        positives.append(a)
    else:
        negatives.append(a)


positives.sort()
negatives.sort(reverse=True)

len_positives = len(positives)
len_negatives = len(negatives)


p_zeros = zeros*(len_negatives+len_positives) + nC2(zeros)
p_positives = nC2(len_positives) + nC2(len_negatives)
p_negatives = len_positives * len_negatives

if p_negatives < k <= (p_negatives+p_zeros):
    
    print(0)
    exit()

if k <= p_negatives:
    
    nokori = k

    left = -1 * ((10**9)**2 + 1)
    right = -1

    
    while left < right:
        center = (left+right+1) // 2

        left2 = len_positives-1
        right2 = len_negatives-1

        count = 0

        
        while right2 > 0 and positives[left2] * negatives[right2] < center:
            right2 -= 1

        while 0<=left2<len_positives and 0<=right2<len_negatives:
            if positives[left2] * negatives[right2] < center:
                count += len_negatives - right2
                left2 -= 1
            else:
                right2 += 1

        if count < nokori:
            left = center
        else:
            right = center - 1
    print(left)
    exit()


nokori = k - p_negatives - p_zeros

left = 1
right = (10**9)**2 + 1


while left < right:
    center = (left+right+1) // 2

    left2 = 0
    right2 = len_positives-1

    count = 0

    
    while left2 < right2:
        if positives[left2] * positives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    left2 = 0
    right2 = len_negatives-1

    
    while left2 < right2:
        if negatives[left2] * negatives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    if count < nokori:
        left = center
    else:
        right = center-1
print(left)

Solution (Python):

import numpy as np



def solve1(k, ml, pl):
    left, right = -(10 ** 18) - 1, 0
    while right - left > 1:
        x = (left + right) // 2
        n = (len(pl) - np.searchsorted(pl, x // ml + (x % ml != 0))).sum()
        if k <= n:
            right = x
        else:
            left = x
    return right



def solve2(k, ml, pl):
    left, right = 0, 10 ** 18
    while right - left > 1:
        x = (left + right) // 2
        n = 0
        n += (len(ml) - np.searchsorted(ml, x // ml + (x % ml != 0))).sum()
        n -= np.count_nonzero(ml ** 2 <= x)
        n += (np.searchsorted(pl, x // pl, side="right")).sum()
        n -= np.count_nonzero(pl ** 2 <= x)
        assert n % 2 == 0
        n //= 2
        if k <= n:
            right = x
        else:
            left = x
    return right


def main():
    N, K = list(map(int, input().split()))
    A = np.array(input().split(), dtype=int)
    A.sort()
    ml = A[A < 0]
    pl = A[A > 0]
    zl = A[A == 0]
    mn = len(ml) * len(pl)
    zn = sum([N - i - 1 for i in range(len(zl))])
    if K <= mn:
        ans = solve1(K, ml, pl)
    elif K <= mn + zn:
        ans = 0
    else:
        ans = solve2(K - mn - zn, ml, pl)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from bisect import bisect

INF = 10 ** 18

def check_neg(m, k, pos, neg):
    len_pos = len(pos)
    less = 0  
    j = 0
    for a in neg:
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if len_pos == j:
            break
        less += len_pos - j
    return less < k

def check_pos(m, k, pos, neg):
    less_eq = 0  
    j = 0
    len_pos = len(pos)
    len_neg = len(neg)
    for i in range(len_pos - 1, -1, -1):
        a = pos[i]
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if j == len_pos:
            less_eq += len_pos * (i + 1)
            break
        less_eq += j

    j = 0
    for i in range(len_neg - 1, -1, -1):
        a = neg[i]
        d = m // a
        while j < len_neg and neg[j] <= d:
            j += 1
        if j == len_neg:
            less_eq += len_neg * (i + 1)
            break
        less_eq += j

    m_sqrt = int(m ** 0.5)
    less_eq -= bisect(pos, m_sqrt)
    less_eq -= bisect(neg, m_sqrt)
    less_eq //= 2
    return less_eq < k


def solve(n, k, A):
    pos = []
    neg = []
    zeros = []
    for a in A:
        if a == 0:
            zeros.append(a)
        elif a > 0:
            pos.append(a)
        else:
            neg.append(a)

    pos = [a for a in A if a > 0]
    neg = [a for a in A if a < 0]
    num_neg = len(neg) * len(pos)
    num_zero = (len(neg) + len(pos)) * len(zeros) + len(zeros) * (len(zeros) - 1) // 2
    if k <= num_neg:
        l = -INF
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg):
                l = m
            else:
                r = m
        return l
    elif num_neg < k <= num_neg + num_zero:
        return 0
    else:
        k -= (num_neg + num_zero)
        l = 0
        r = INF
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg):
                l = m
            else:
                r = m
        return r


n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
print(solve(n, k, A))

Solution (Python):
import numpy as np


def count_pair(x):
    
    
    cnt = 0
    
    cnt += (N-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        
        cnt += len(A_zero)*N
    
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt



N, K = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < K:
        l = c
    else:
        r = c
print(l)

Solution (Python):


import numpy as np
import sys
input = sys.stdin.readline


def main():
    N,K = map(int, input().split())
    A = np.array(sorted([int(i) for i in input().split()]))

    zero_left = np.searchsorted(A, 0, side='left')
    zero_right = np.searchsorted(A, 0, side='right')

    negative = zero_left
    positive = N - zero_right
    zero = zero_right - zero_left
    non_posi = negative * positive + zero * (N - zero) + zero * (zero - 1) // 2

    if K <= negative * positive:
        Nega = A[A < 0]
        Posi = A[A > 0]

        left = -(10**18)
        right = 0
        while right - left > 1:
            x = (left + right) // 2
            count = np.searchsorted(Nega, x // Posi, side='right').sum()

            if count < K:
                left = x
            else:
                right = x

        print(right)

    elif K <= non_posi:
        print(0)

    else:
        Nega = np.sort(np.abs(A[A < 0]))
        Posi = A[A > 0]

        left = 0
        right = 10**18
        while right - left > 1:
            x = (left + right) // 2
            n = np.searchsorted(Nega, x // Nega, side='right')
            p = np.searchsorted(Posi, x // Posi, side='right')
            count = 0
            count += n.sum()
            count += p.sum()
            count -= np.int_(np.where(n >= np.arange(1,negative+1), True, False)).sum()
            count -= np.int_(np.where(p >= np.arange(1,positive+1), True, False)).sum()
            count //= 2

            if count + non_posi < K:
                left = x
            else:
                right = x

        print(right)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
import sys
input = sys.stdin.readline


def main():
    N,K = map(int, input().split())
    A = np.array(sorted([int(i) for i in input().split()]))

    negative = A[A < 0]
    positive = A[A > 0]
    ln = len(negative)
    lp = len(positive)
    zero = np.count_nonzero(A == 0)

    def count(x):
        count = 0
        if x >= 0:
            count += N * zero
        count += np.searchsorted(A, x // positive, side='right').sum()
        count += N * ln - np.searchsorted(A, -(-x // negative), side='left').sum()
        count -= np.count_nonzero(A * A <= x)
        count //= 2

        return count


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

    print(right)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)

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


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


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


print(right)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np

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

A_m = np.array(sorted([abs(int(x)) for x in A if x < 0]), np.int64)
N_m = len(A_m)

A_p = np.array(sorted([int(x) for x in A if x > 0]), np.int64)
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = np.searchsorted(A_m, x // A_p, side="right").sum()
    return cnt >= M - K + 1

if K <= M:
    left = -1 -10 ** 18
    right = 1 + 10 ** 18
    while right - left> 1:
        mid = (left + right) // 2
        if cnt_M(mid):
            right = mid
        else:
            left = mid
 
    print(-right)
    sys.exit()

K -= (M + Z)
def cnt_P(x):
    cnt = 0
    ng = 0
    cnt += np.searchsorted(A_m, x // A_m, side="right").sum()
    cnt += np.searchsorted(A_p, x // A_p, side="right").sum()
    ng = np.count_nonzero(A_m * A_m <= x) + np.count_nonzero(A_p * A_p <= x)
    cnt = (cnt - ng) // 2
    return cnt >= K

left = -1 - 10 ** 18
right = 1 + 10 ** 18

while right - left > 1:
    mid = (left + right) // 2
    if cnt_P(mid):
        right = mid
    else:
        left = mid
print(right)

Solution (Python):
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A_minus,A_zero,A_plus=[],[],[]
    x=bisect_left(A,0)
    y=bisect_right(A,0)
    A_minus=A[:x]
    A_minus=list(reversed(list(map(lambda x: -x,A_minus))))
    A_zero=A[x:y]
    A_plus=A[y:]
    if K<=len(A_minus)*len(A_plus):
        def nibutan1(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve1(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve1(mid):
            c=0
            z=bisect_left(A_plus,-(-mid//A_minus[0]))
            c+=len(A_plus)-z
            for x in A_minus[1:]:
                if z>0 and A_plus[z-1] >= -(-mid//x):
                    while z>0 and A_plus[z-1] >= -(-mid//x):
                        z-=1
                c+=len(A_plus)-z
            if c>=K:
                return True
            else:
                return False
        
        print(-nibutan1(0,10**18+1))
    K-=len(A_minus)*len(A_plus)
    if 0<K<=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2:
        print(0)
    K-=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2
    if K>0:
        def nibutan2(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve2(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve2(mid):
            c=0
            if len(A_minus)>1:
                z=bisect_right(A_minus,mid//A_minus[0])
                c+=z
                if mid//A_minus[0]>=A_minus[0]:
                    c-=1
                for x in A_minus[1:]:
                    if z>0 and A_minus[z-1] > mid//x:
                        while z>0 and A_minus[z-1] > mid//x:
                            z-=1
                    c+=z
                    if mid//x>=x:
                        c-=1
            if len(A_plus)>1:
                z=bisect_right(A_plus,(mid//A_plus[0]))
                c+=z
                if (mid//A_plus[0])>=A_plus[0]:
                    c-=1
                for x in A_plus[1:]:
                    if z>0 and A_plus[z-1] > mid//x:
                        while z>0 and A_plus[z-1] > mid//x:
                            z-=1
                    c+=z
                    if mid//x>=x:
                        c-=1
            c//=2
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan2(10**18+1,0))

    
        
    

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

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

A_max = max(np.abs(A))
A_minus = A[A<0]
A_zero = A[A==0]
A_plus = A[A>0]

def check(x):
    ret = 0
    if x >= 0:
        ret += N * len(A_zero)
    ret += np.searchsorted(A, x // A_plus, side='right').sum()
    ret += (N - np.searchsorted(A, -(x // -A_minus))).sum()
    ret -= np.count_nonzero(A * A <= x)
    return ret // 2

right = A_max * A_max
left = -right - 1
while (right - left > 1):
    middle = (right + left) >> 1
    if check(middle) < K:
        left = middle
    else:
        right = middle
print(right)

Solution (Python):
import numpy as np
import sys
 
n,k=map(int,sys.stdin.readline().split())
a=np.array(list(map(int, input().split())))
 
a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]
 
def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2
 
 
left=-10**18
right=10**18
 
while left+1<right:
    x=(left+right)//2
    out=count(x)
    if out>=k:
        right=x
    if out<k:
        left=x
print(right)

Solution (Python):



import numpy as np

N,K = map(int,input().split())
A = np.array(input().split(),dtype=np.int64)

A = np.sort(A)

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

hi = 10**18+1
lo = -10**18-1

while hi-lo > 1:
    mid = (hi+lo)//2
    under_mid = 0

    if mid > 0: under_mid += N*zero
    under_mid += np.searchsorted(A,-(-mid//pos),side='left').sum()
    under_mid += (N-np.searchsorted(A,mid//neg,side='right')).sum()
    under_mid -= np.count_nonzero(A*A < mid)
    under_mid //= 2

    if under_mid < K:
        lo = mid
    else:
        hi = mid

print(lo)

Solution (Python):
import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.read().split(),dtype=np.int64)

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

def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


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

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

print(right)

Solution (Python):
import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.readline().split(),dtype=np.int64)

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

def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


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

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

print(right)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(x):
    cnt = 0
    if x < 0:
        j = p-1
        for i in range(m)[::-1]:
            while j >= 0 and plus[j]*minus[i] <= x:
                j -= 1
            cnt += p - j - 1
    else:
        j = 0
        for i in range(m)[::-1]:
            while j < m and minus[j]*minus[i] > x:
                j += 1
            cnt += max(0,i-j)
        j = p-1
        for i in range(p):
            while j >= 0 and plus[j]*plus[i] > x:
                j -= 1
            cnt += max(0,j-i)
        cnt += zero*(zero-1)//2 + m*p + zero*(m+p)
    
    return cnt >= k

n,k = LI()
a = LI()
a.sort()
minus = [x for x in a if x < 0]
plus = [x for x in a if x > 0]
m,p = len(minus),len(plus)
zero = bl(a,1) - br(a,-1)
ok,ng = 10**18,-10**18-1

while ok - ng > 1:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

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

INF = 10**19
N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)
pos.sort()
neg.sort()
p, n = len(pos), len(neg)
if K <= p * n:
    lb, ub = -INF, INF
    while ub - lb > 1:
        mid = (lb + ub) // 2
        cnt = 0

        s, t = 0, 0
        while s < p:
            while t < n and pos[s] * neg[t] <= mid:
                t += 1
            cnt += t
            s += 1

        if cnt < K:
            lb = mid
        else:
            ub = mid
    print(ub)
else:
    K -= p * n
    neg = neg[::-1]
    lb, ub = -INF, INF
    while ub - lb > 1:
        mid = (lb + ub) // 2
        cnt = 0

        s, t = p-1, 0
        while s >= 0:
            while t < s and pos[s] * pos[t] <= mid:
                t += 1
            cnt += min(s, t)
            s -= 1

        s, t = n-1, 0
        while s >= 0:
            while t < s and neg[s] * neg[t] <= mid:
                t += 1
            cnt += min(s, t)
            s -= 1

        if cnt < K:
            lb = mid
        else:
            ub = mid
    print(ub)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np

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

INF = 10**18 + 1

A = np.sort(A)

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


def is_under_K(X:int):
    cnt = 0

    
    if X >= 0:
        cnt += len(zero) * N
    
    
    tmp = X // pos
    cnt += np.searchsorted(A, tmp, "right").sum()

    
    tmp = (-X-1) // (-neg)
    cnt += (N - np.searchsorted(A, tmp, "right")).sum()

    
    cnt -= np.count_nonzero(A * A <= X)

    assert cnt % 2 == 0
    return cnt // 2 < K

def main():
    
    ok, ng = -INF, INF
    while ng - ok > 1:
        mid = (ng + ok) // 2
        if is_under_K(mid):
            ok = mid
        else:
            ng = mid

    """
    is_under_K(X) = Flaseとなる最小値X
    -> X = ng
    """
    print(ng)

if __name__ == "__main__":
    main()

Solution (Python):
from subprocess import*
call(("pypy3","-c","""
def main():
  from bisect import bisect
  n,k,*a=map(int,open(0).read().split())
  a.sort()
  i=bisect(a,0)
  a,b=a[i:],a[i-1::-1]
  n,m=len(a),len(b)
  ok=10**18
  ng=-ok
  while ok-ng>1:
    x=(ok+ng)//2
    s=0
    if x>=0:
      i=n
      for y in a:
        while i and a[i-1]*y>x:i-=1   
        s+=i
        if y*y<=x:s-=1
      i=m
      for y in b:
        while i and b[i-1]*y>x:i-=1
        s+=i
        if y*y<=x:s-=1
      s=s//2+n*m
    else:
      i=m
      for y in a:
        while i and b[i-1]*y<=x:i-=1
        s+=m-i
    if s>=k:ok=x
    else:ng=x
  print(ok)
main()
"""))

Solution (Python):
def main():
  from bisect import bisect
  n,k,*a=map(int,open(0).read().split())
  a.sort()
  i=bisect(a,0)
  a,b=a[i:],a[i-1::-1]
  n,m=len(a),len(b)
  ok=10**18
  ng=-ok
  while ok-ng>1:
    x=(ok+ng)//2
    s=0
    if x>=0:
      s+=n*m
      t=0
      i=n
      for y in a:
        while i and a[i-1]*y>x:i-=1   
        t+=i
        if y*y<=x:t-=1
      s+=t//2
      t=0
      i=m
      for y in b:
        while i and b[i-1]*y>x:i-=1
        t+=i
        if y*y<=x:t-=1
      s+=t//2
    else:
      i=m
      for y in a:
        while i and b[i-1]*y<=x:i-=1
        s+=m-i
    if s>=k:ok=x
    else:ng=x
  print(ok)
main()

Solution (Python):
from bisect import*
def solve(x):
  s=t=0
  i=n
  j=-1
  for y in a:
    while i and a[i-1]*y>x:i-=1
    while j+1<m and b[j+1]*y<=x:j+=1
    s+=j+1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  t=0
  i=m
  for y in c:
    while i and c[i-1]*y>x:i-=1
    t+=i
    if y*y<=x:t-=1
  s+=t//2
  return s
n,k,*t=map(int,open(0).read().split())
t.sort()
i=bisect(t,0)
a,b,c=t[i:],t[:i],t[i-1::-1]
n,m=len(a),len(b)
ok=10**18
ng=-ok
while ok-ng>1:
  mid=(ok+ng)//2
  if solve(mid)>=k:ok=mid
  else:ng=mid
print(ok)

Solution (Python):
from numpy import int64, searchsorted, count_nonzero

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

A.sort()

Minus, Zero, Plus = A[A < 0], A[A == 0], A[0 < A]

def is_ok(md):
    cnt = 0 if md < 0 else len(Zero) * N

    cnt += searchsorted(A, md // Plus, side='right').sum()
    cnt += (N - searchsorted(A, (-md - 1) // (-Minus), side='right')).sum()
    cnt -= count_nonzero(A * A <= md)

    return (cnt // 2 >= K)


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

print(ok)

Solution (Python):
import sys


def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def nC2(n):
    return n * (n-1) // 2

n,k = get_nums_l()
aaa = get_nums_l()

negatives = []
zeros = 0
positives = []

for a in aaa:
    if a == 0:
        zeros += 1
    elif a > 0:
        positives.append(a)
    else:
        negatives.append(a)


positives.sort()
negatives.sort(reverse=True)

len_positives = len(positives)
len_negatives = len(negatives)


p_zeros = zeros*(len_negatives+len_positives) + nC2(zeros)
p_positives = nC2(len_positives) + nC2(len_negatives)
p_negatives = len_positives * len_negatives

if p_negatives < k <= (p_negatives+p_zeros):
    
    print(0)
    exit()

if k <= p_negatives:
    
    nokori = k

    left = -1 * ((10**9)**2 + 1)
    right = -1

    
    while left < right:
        center = (left+right+1) // 2

        left2 = len_positives-1
        right2 = len_negatives-1

        count = 0

        
        while right2 > 0 and positives[left2] * negatives[right2] < center:
            right2 -= 1

        while 0<=left2<len_positives and 0<=right2<len_negatives:
            if positives[left2] * negatives[right2] < center:
                count += len_negatives - right2
                left2 -= 1
            else:
                right2 += 1

        if count < nokori:
            left = center
        else:
            right = center - 1
    print(left)
    exit()


nokori = k - p_negatives - p_zeros

left = 1
right = (10**9)**2 + 1


while left < right:
    center = (left+right+1) // 2

    left2 = 0
    right2 = len_positives-1

    count = 0

    
    while left2 < right2:
        if positives[left2] * positives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    left2 = 0
    right2 = len_negatives-1

    
    while left2 < right2:
        if negatives[left2] * negatives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    if count < nokori:
        left = center
    else:
        right = center-1
print(left)

Solution (Python):

from bisect import bisect_left


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

    A.sort()

    
    Ns = 0
    Zs = bisect_left(A, 0)
    Ps = bisect_left(A, 1)

    
    lneg = Zs-Ns
    lzer = Ps-Zs
    lpos = N-Ps
    

    prod_neg = lneg * lpos
    prod_zero = lzer * (lneg+lpos)+lzer*(lzer-1)//2
    
    

    if prod_neg >= K:
        
        left = A[0]*A[-1]
        right = 0
        while right-left > 1:
            mid = (right + left)//2
            
            counter = 0
            ps = Ps
            for ns in range(Ns, Zs):
                while ps < N and A[ns]*A[ps] > mid-1:
                    ps += 1
                if ps == N:
                    break
                counter += N-ps
                
            
            if counter < K:
                left = mid
            else:
                right = mid
        print(left)
    elif prod_zero + prod_neg >= K:
        print(0)
    else:
        KK = K-prod_neg-prod_zero
        
        left = 0
        right = max(A[0]**2, A[-1]**2)
        while right - left > 1:
            mid = (left + right)//2
            
            counter = 0
            end = N-1
            for start in range(Ps, N):
                while end >= start and A[start]*A[end] >= mid:
                    end -= 1
                if end <= start:
                    break
                counter += end-start
            start = 0
            for end in range(Zs-1, -1, -1):
                while end >= start and A[start]*A[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 math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def nC2(n):
    return n * (n-1) // 2

n,k = get_nums_l()
aaa = get_nums_l()

negatives = []
zeros = 0
positives = []

for a in aaa:
    if a == 0:
        zeros += 1
    elif a > 0:
        positives.append(a)
    else:
        negatives.append(a)


positives.sort()
negatives.sort(reverse=True)

len_positives = len(positives)
len_negatives = len(negatives)

p_zeros = zeros*(len_negatives+len_positives) + nC2(zeros)
p_positives = nC2(len_positives) + nC2(len_negatives)
p_negatives = len_positives * len_negatives

log(len_negatives, zeros, len_positives)
log(p_negatives, p_zeros, p_positives)

if p_negatives < k <= (p_negatives+p_zeros):
    print(0)
    exit()

if k <= p_negatives:
    
    nokori = k
    log("nokori", nokori)

    left = -1 * ((10**9)**2 + 1)
    right = -1

    
    while left < right:
        center = (left+right+1) // 2
        

        left2 = len_positives-1
        right2 = len_negatives-1

        count = 0

        while right2 > 0 and positives[left2] * negatives[right2] < center:
            right2 -= 1
        
        

        while 0<=left2<len_positives and 0<=right2<len_negatives:
            
            if positives[left2] * negatives[right2] < center:
                count += len_negatives - right2
                left2 -= 1
            else:
                right2 += 1

        
        

        
        
        
        
        
        
        
        
        
        
        
        if count < nokori:
            left = center
        else:
            right = center - 1
    print(left)
    exit()


nokori = k - p_negatives - p_zeros


left = 1
right = (10**9)**2 + 1


while left < right:
    center = (left+right+1) // 2
    

    left2 = 0
    right2 = len_positives-1

    count = 0

    while left2 < right2:
        if positives[left2] * positives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    left2 = 0
    right2 = len_negatives-1

    while left2 < right2:
        if negatives[left2] * negatives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1
    
    

    if count < nokori:
        left = center
    else:
        right = center-1
print(left)

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 // -n))).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):
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)