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: Time Limit Exceeded

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

values = []
for i in range(N):
    for j in range(i+1, N):
        values.append(A[i] * A[j])

values.sort()
print(values[K-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    a = np.array(a)
    l, r = 0, 0
    if k <= num_neg_pair:
        l = neg_a[0] * pos_a[cnt_pos-1]
        r = neg_a[cnt_neg-1] * pos_a[0]+1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        if cnt_neg >= 2 and cnt_pos >= 2:
            l = min(neg_a[cnt_neg-1]*neg_a[cnt_neg-2], pos_a[0]*pos_a[1])
        elif cnt_neg >= 2:
            l = neg_a[cnt_neg-1]*neg_a[cnt_neg-2]
        else:
            l = pos_a[0]*pos_a[1]
        if cnt_neg >= 2 and cnt_pos >= 2:
            r = max(neg_a[0]*neg_a[1], pos_a[cnt_pos-1]*pos_a[cnt_pos-2])+1
        elif cnt_neg >= 2:
            r = neg_a[0]*neg_a[1]+1
        else:
            r = pos_a[cnt_pos-1]*pos_a[cnt_pos-2]+1
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = 0
                if target < 0:
                    index = np.searchsorted(neg_a, target, side="riget")
                elif target == 0:
                    index = cnt_neg + cnt_zro
                else:
                    index = np.searchsorted(pos_a, target, side="right")
                    index += cnt_neg + cnt_zro
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = 0
                if target < 0:
                    index = np.searchsorted(neg_a, target, side="left")
                elif target == 0:
                    index = cnt_neg
                else:
                    index = np.searchsorted(pos_a, target, side="left")
                    index += cnt_neg + cnt_zro
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    for v in a:
        if v < 0:
            cnt_neg += 1
            neg_a.append(v)
        elif v == 0:
            cnt_zro += 1
            zro_a.append(v)
        else:
            cnt_pos += 1
            pos_a.append(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    a = np.array(a)
    l, r = 0, 0
    if k <= num_neg_pair:
        l = neg_a[0] * pos_a[cnt_pos-1]
        r = neg_a[cnt_neg-1] * pos_a[0]+1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        if cnt_neg >= 2 and cnt_pos >= 2:
            l = min(neg_a[cnt_neg-1]*neg_a[cnt_neg-2], pos_a[0]*pos_a[1])
        elif cnt_neg >= 2:
            l = neg_a[cnt_neg-1]*neg_a[cnt_neg-2]
        else:
            l = pos_a[0]*pos_a[1]
        if cnt_neg >= 2 and cnt_pos >= 2:
            r = max(neg_a[0]*neg_a[1], pos_a[cnt_pos-1]*pos_a[cnt_pos-2])+1
        elif cnt_neg >= 2:
            r = neg_a[0]*neg_a[1]+1
        else:
            r = pos_a[cnt_pos-1]*pos_a[cnt_pos-2]+1
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = np.searchsorted(a, target, side="right")
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = np.searchsorted(a, target, side="left")
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    for v in a:
        if v < 0:
            cnt_neg += 1
            neg_a.append(v)
        elif v == 0:
            cnt_zro += 1
            zro_a.append(v)
        else:
            cnt_pos += 1
            pos_a.append(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    l, r = 0, 0
    if k <= num_neg_pair:
        l = neg_a[0] * pos_a[cnt_pos-1]
        r = neg_a[cnt_neg-1] * pos_a[0]+1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        if cnt_neg >= 2 and cnt_pos >= 2:
            l = min(neg_a[cnt_neg-1]*neg_a[cnt_neg-2], pos_a[0]*pos_a[1])
        elif cnt_neg >= 2:
            l = neg_a[cnt_neg-1]*neg_a[cnt_neg-2]
        else:
            l = pos_a[0]*pos_a[1]
        if cnt_neg >= 2 and cnt_pos >= 2:
            r = max(neg_a[0]*neg_a[1], pos_a[cnt_pos-1]*pos_a[cnt_pos-2])+1
        elif cnt_neg >= 2:
            r = neg_a[0]*neg_a[1]+1
        else:
            r = pos_a[cnt_pos-1]*pos_a[cnt_pos-2]+1
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = bisect_right(a, target)
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = bisect_left(a, target)
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    for v in a:
        if v < 0:
            cnt_neg += 1
        elif v == 0:
            cnt_zro += 1
        else:
            cnt_pos += 1
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    l, r = 0, 0
    if k <= num_neg_pair:
        l = -1*10**18
        r = -1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        l = 1
        r = 10**18
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = bisect_right(a, target)
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = bisect_left(a, target)
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s = [0]*n
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = bisect_right(a, target)
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = bisect_left(a, target)
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        tot = 0
        for i in range(n):
            sl, sr = -1, n
            if a[i] < 0:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sr = sp
                    else:
                        sl = sp
                tot += n-sr
            else:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sl = sp
                    else:
                        sr = sp
                tot += sr
            if a[i]**2 < p:
                tot -= 1
        tot //= 2
        if tot < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s = [0]*n
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        for i in range(n):
            sl, sr = -1, n
            if a[i] < 0:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sr = sp
                    else:
                        sl = sp
                s[i] = n-sr
            else:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sl = sp
                    else:
                        sr = sp
                s[i] = sr
            if a[i]**2 < p:
                s[i] -= 1
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        tot = 0
        for i in range(n):
            sl, sr = -1, n
            if a[i] < 0:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sr = sp
                    else:
                        sl = sp
                tot += n-sr
            else:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sl = sp
                    else:
                        sr = sp
                tot += sr
            if a[i]**2 < p:
                tot -= 1
        tot //= 2
        if tot < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
pair = []

for i in range(n):
  for j in range(i+1,n):
    pair.append(a[i]*a[j])
pair.sort()
print(pair[k-1])

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    import bisect
    def ok(x):
        # x以下になる組み合わせがk個以上
        cnt = 0
        for a in A:
            if a*a <= x:
                cnt -= 1
            if a > 0:
                c = x//a
                cnt += bisect.bisect_right(A, c)
            elif a < 0:
                c = (-x-1)//(-a)
                cnt += n - bisect.bisect_right(A, c)
            else:
                if x >= 0:
                    cnt += n
        cnt = cnt//2
        if cnt >= k:
            return True
        else:
            return False

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

import bisect
def ok(x):
    # x以下になる組み合わせがk個以上
    cnt = 0
    for a in A:
        if a*a <= x:
            cnt -= 1
        if a > 0:
            c = x//a
            cnt += bisect.bisect_right(A, c)
        elif a < 0:
            c = (-x-1)//(-a)
            cnt += n - bisect.bisect_right(A, c)
        else:
            if x >= 0:
                cnt += n
    cnt = cnt//2
    if cnt >= k:
        return True
    else:
        return False

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

Submission status: Time Limit Exceeded

Solution code:
import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

import bisect
def ok(x):
    # x以下になる組み合わせがk個以上
    cnt = 0
    for a in A:
        if a > 0:
            c = x//a
            cnt += bisect.bisect_right(A, c)
        elif a < 0:
            c = (-x-1)//(-a)
            cnt += n - bisect.bisect_right(A, c)
        else:
            if x >= 0:
                cnt += n
    for a in A:
        if a*a <= x:
            cnt -= 1
    cnt = cnt//2
    if cnt >= k:
        return True
    else:
        return False

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

Submission status: Time Limit Exceeded

Solution code:
import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline

import numpy as np

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

import bisect
def ok(x):
    # x以下になる組み合わせがk個以上
    cnt = 0
    for a in A:
        if a > 0:
            c = x//a
            cnt += bisect.bisect_right(A, c)
        elif a < 0:
            c = (-x-1)//(-a)
            cnt += n - bisect.bisect_right(A, c)
        else:
            if x >= 0:
                cnt += n
    for a in A:
        if a*a <= x:
            cnt -= 1
    cnt = cnt//2
    if cnt >= k:
        return True
    else:
        return False

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

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = sorted(map(int, input().split()))
INF = 10 ** 18
left = -INF
right = INF


def ok(x):
    total = 0
    for i in range(N):
        if A[i] < 0:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * A[i] < x:
                    right = mid
                else:
                    left = mid
            total += N - right
        else:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * A[i] < x:
                    left = mid
                else:
                    right = mid
            total += right
        if A[i] * A[i] < x:
            total -= 1
    total //= 2
    return total < K


while left + 1 < right:
    x = (left + right) // 2
    if ok(x):
        left = x
    else:
        right = x

print(left)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = sorted(map(int, input().split()))
INF = 10 ** 18 + 1
left = -INF
right = INF


def ok(x):
    total = 0
    for i in range(N):
        if A[i] < 0:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * A[i] < x:
                    right = mid
                else:
                    left = mid
            total += N - right
        else:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * A[i] < x:
                    left = mid
                else:
                    right = mid
            total += right
        if A[i] * A[i] < x:
            total -= 1
    total //= 2
    return total < K


while left + 1 < right:
    x = (left + right) // 2
    if ok(x):
        left = x
    else:
        right = x

print(left)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = sorted(map(int, input().split()))
INF = 10 ** 19
left = -INF
right = INF


def ok(x):
    total = 0
    for i in range(N):
        if A[i] < 0:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * A[i] < x:
                    right = mid
                else:
                    left = mid
            total += N - right
        else:
            left = -1
            right = N
            while left + 1 < right:
                mid = (left + right) // 2
                if A[mid] * A[i] < x:
                    left = mid
                else:
                    right = mid
            total += right
        if A[i] * A[i] < x:
            total -= 1
    total //= 2
    return total < K


while left + 1 < right:
    x = (left + right) // 2
    if ok(x):
        left = x
    else:
        right = x

print(left)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A= list(map(int,input().split()))
A.sort()
list_A=[]
for i in range(N):
    for j in range(N):
        if j > i:
            list_A.append(A[i]*A[j])
list_A.sort()
print(list_A[K-1])

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,k=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
x=bisect.bisect_left(A,0,lo=0,hi=len(A))
y=bisect.bisect_right(A,0,lo=0,hi=len(A))
AN=x
A0=y-x
AP=n-y
if x!=0:
  An=A[:x]
else:
  An=[]
Ann=An[::-1]
Annn=[0]*AN
for i in range(AN):
  Annn[i]=Ann[i]*(-1)
if y!=n:
  App=A[-n+y:]
  Ap=App[::-1]
else:
  Ap=[]
if k<=AN*AP:
  ok=An[0]*Ap[0]-1
  ng=0
  while ng-ok>1:
    mid=(ok+ng)//2
    c=0
    for i in range(AN):
      c=c+AP-bisect.bisect_left(App,((-1)*mid+(-1)*An[i]-1)//((-1)*An[i]),lo=0,hi=AP)
    if c<k:
      ok=mid
    else:
      ng=mid
  ans=ok+1
  print(ans)
elif k<=n*(n-1)//2-AN*(AN-1)//2-AP*(AP-1)//2:
  print(0)
else:
  k=n*(n-1)//2-k+1
  if AN>0 and AP>0:
    ok=max(An[0]**2,Ap[0]**2)
  elif AN>0:
    ok=An[0]**2
  else:
    ok=Ap[0]**2
  ng=0
  while ok-ng>1:
    mid=(ok+ng)//2
    c=0
    for i in range(AN):
      c=c+max(0,AN-i-1-bisect.bisect_left(Annn,(mid+Annn[AN-i-1]-1)//Annn[AN-i-1],lo=0,hi=AN))
    for i in range(AP):
      c=c+max(0,AP-i-1-bisect.bisect_left(App,(mid+App[AP-i-1]-1)//App[AP-i-1],lo=0,hi=AP))
    if c<k:
      ok=mid
    else:
      ng=mid
  ans=ok-1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = map(int,input().split())
A = list(A)
num = []
for i in range(N):
    for j in range(N):
        if(i<j):num.append(A[i]*A[j])
num.sort()
print(num[K-1])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
pY = []
mY = []
z = 0
for x in X:
    if x > 0:
        pY.append(x)
    elif x < 0:
        mY.append(x)
    else:
        z += 1

def bsearch(mn, mx, func):
    #func(i)=False を満たす最大のi
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mx = (idx + mn)//2, idx
            continue
        idx, mn = (idx + mx)//2, idx
    return idx


def count2(k):
    c = 0
    for y in pY:
        c += bsearch(-1, N, lambda i:X[i]*y>k) + 1
    for y in mY:
        c += N-(bsearch(-1, N, lambda i:X[i]*y<=k)+1)
    if k >= 0:
        c += N*z
    for x in X:
        if x*x <=k:
            c -= 1
    c = c//2
    return c


def count(k):
    # x*y <= k を満たすx,yの個数
    c = 0
    for i in range(N):
        for j in range(i+1, N):
            if X[i]*X[j] <= k:
                c += 1
    return c

x = bsearch(-10**18, 10**18, lambda x : count2(x)>=K)
print(x+1)

Submission status: Time Limit Exceeded

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

def ggg():
    ind=L1-1
    cnt=0
    for i in range(L1):
        u=d1[i]
        nnn=mid//u
        ind=L1-1
        while ind>i and d1[ind]>nnn:
            ind-=1
        if ind<=i:
            break
        cnt+=ind-i
    return cnt

def fff():
    ind=L2-1
    cnt=0
    for i in range(L2):
        u=d2[i]
        nnn=mid//u
        ind=L2-1
        while ind>i and d2[ind]>nnn:
            ind-=1
        if ind==-1:
            break
        if ind<=i:
            break
        else:
            cnt+=ind-i
    return cnt

N,K=map(int,input().split())
A=list(map(int,input().split()))
d1=[]
d2=[]
zeros=0
for i in range(N):
    if A[i]>0:
        d1.append(A[i])
    elif A[i]==0:
        zeros+=1
    else:
        d2.append(-A[i])
d1.sort()
d2.sort()
L1=len(d1)
L2=len(d2)

if L1*L2>=K:
    #数は負の数
    #d1,d2から一つずつ選ぶ組み合わせのうち、K番目に大きいもの
    low=0
    high=10**18+1
    while high-low>1:
        mid=(low+high)//2
        ind=L2-1
        cnt=0
        for u in d1:
            if mid%u==0:
                nnn=mid//u
            else:
                nnn=mid//u+1
            while ind>=0 and d2[ind]>=nnn:
                ind-=1
            cnt+=L2-1-ind
            
        if cnt>=K:
            low=mid
        else:
            high=mid
    print(-low)
    
elif L1*(L1-1)//2+L2*(L2-1)//2<=N*(N-1)//2-K:
    print(0)

else:
    K-=N*(N-1)//2-(L1*(L1-1)//2+L2*(L2-1)//2)
    #d1から二つ、d2から二つ選ぶ組のうちK番目に小さいもの
    
    low=0
    high=10**18+1
    while high-low>1:
        mid=(high+low)//2
        C=ggg()+fff()
        if C<K:
            low=mid
        else:
            high=mid
    
    print(high)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
d1=[]
d2=[]
zeros=0
for i in range(N):
    if A[i]>0:
        d1.append(A[i])
    elif A[i]==0:
        zeros+=1
    else:
        d2.append(-A[i])
d1.sort()
d2.sort()
L1=len(d1)
L2=len(d2)

if L1*L2>=K:
    #数は負の数
    #d1,d2から一つずつ選ぶ組み合わせのうち、K番目に大きいもの
    low=0
    high=10**18+1
    while high-low>1:
        mid=(low+high)//2
        ind=L2-1
        cnt=0
        for u in d1:
            if mid%u==0:
                nnn=mid//u
            else:
                nnn=mid//u+1
            while ind>=0 and d2[ind]>=nnn:
                ind-=1
            cnt+=L2-1-ind
            
        if cnt>=K:
            low=mid
        else:
            high=mid
    print(-low)
    
elif L1*(L1-1)//2+L2*(L2-1)//2<=N*(N-1)//2-K:
    print(0)

else:
    K-=N*(N-1)//2-(L1*(L1-1)//2+L2*(L2-1)//2)
    #d1から二つ、d2から二つ選ぶ組のうちK番目に小さいもの
    
    low=0
    high=10**18+1
    while high-low>1:
        mid=(high+low)//2
        
        ind=L1-1
        cnt=0
        for i in range(L1):
            u=d1[i]
            nnn=mid//u
            ind=L1-1
            while ind>=0 and d1[ind]>nnn:
                ind-=1
            if ind==-1:
                break
            if ind>=i:
                cnt+=ind
            else:
                cnt+=ind+1
                
        ind=L2-1
        for i in range(L2):
            u=d2[i]
            nnn=mid//u
            ind=L2-1
            while ind>=0 and d2[ind]>nnn:
                ind-=1
            if ind==-1:
                break
            if ind>=i:
                cnt+=ind
            else:
                cnt+=ind+1
        
        if cnt//2<K:
            low=mid
        else:
            high=mid
    
    print(high)

Submission status: Time Limit Exceeded

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

N,K=map(int,input().split())
A=list(map(int,input().split()))
d1=[]
d2=[]
zeros=0
for i in range(N):
    if A[i]>0:
        d1.append(A[i])
    elif A[i]==0:
        zeros+=1
    else:
        d2.append(-A[i])
d1.sort()
d2.sort()
L1=len(d1)
L2=len(d2)

if L1*L2>=K:
    #数は負の数
    #d1,d2から一つずつ選ぶ組み合わせのうち、K番目に大きいもの
    low=0
    high=10**18+1
    while high-low>1:
        mid=(low+high)//2
        ind=L2-1
        cnt=0
        for u in d1:
            if mid%u==0:
                nnn=mid//u
            else:
                nnn=mid//u+1
            while ind>=0 and d2[ind]>=nnn:
                ind-=1
            cnt+=L2-1-ind
            
        if cnt>=K:
            low=mid
        else:
            high=mid
    print(-low)
    
elif L1*(L1-1)//2+L2*(L2-1)//2<=N*(N-1)//2-K:
    print(0)

else:
    K-=N*(N-1)//2-(L1*(L1-1)//2+L2*(L2-1)//2)
    #d1から二つ、d2から二つ選ぶ組のうちK番目に小さいもの
    
    low=0
    high=10**18+1
    while high-low>1:
        mid=(high+low)//2
        
        ind=L1-1
        cnt=0
        for i in range(L1):
            u=d1[i]
            nnn=mid//u
            ind=L1-1
            while ind>=0 and d1[ind]>nnn:
                ind-=1
                
            if ind>=i:
                cnt+=ind
            else:
                cnt+=ind+1
        ind=L2-1
        for i in range(L2):
            u=d2[i]
            nnn=mid//u
            ind=L2-1
            while ind>=0 and d2[ind]>nnn:
                ind-=1
                
            if ind>=i:
                cnt+=ind
            else:
                cnt+=ind+1
        
        if cnt//2<K:
            low=mid
        else:
            high=mid
    
    print(high)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
d1=[]
d2=[]
zeros=0
for i in range(N):
    if A[i]>0:
        d1.append(A[i])
    elif A[i]==0:
        zeros+=1
    else:
        d2.append(-A[i])
d1.sort()
d2.sort()

if len(d1)*len(d2)>=K:
    #数は負の数
    #d1,d2から一つずつ選ぶ組み合わせのうち、K番目に大きいもの
    low=0
    high=10**18+1
    while high-low>1:
        mid=(low+high)//2
        ind=len(d2)-1
        cnt=0
        for u in d1:
            if mid%u==0:
                nnn=mid//u
            else:
                nnn=mid//u+1
            while ind>=0 and d2[ind]>=nnn:
                ind-=1
            cnt+=len(d2)-1-ind
        if cnt>=K:
            low=mid
        else:
            high=mid
    print(-low)
    
elif len(d1)*(len(d1)-1)//2+len(d2)*(len(d2)-1)//2<=N*(N-1)//2-K:
    print(0)

else:
    K-=N*(N-1)//2-(len(d1)*(len(d1)-1)//2+len(d2)*(len(d2)-1)//2)
    #d1から二つ、d2から二つ選ぶ組のうちK番目に小さいもの
    
    low=0
    high=10**18+1
    while high-low>1:
        mid=(high+low)//2
        
        ind=len(d1)-1
        cnt=0
        for i in range(len(d1)):
            u=d1[i]
            nnn=mid//u
            ind=len(d1)-1
            while ind>=0 and d1[ind]>nnn:
                ind-=1
                
            if ind>=i:
                cnt+=ind
            else:
                cnt+=ind+1
        ind=len(d2)-1
        for i in range(len(d2)):
            u=d2[i]
            nnn=mid//u
            ind=len(d2)-1
            while ind>=0 and d2[ind]>nnn:
                ind-=1
                
            if ind>=i:
                cnt+=ind
            else:
                cnt+=ind+1
        
        if cnt//2<K:
            low=mid
        else:
            high=mid
    
    print(high)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(x) for x in input().split(' ')]

def merge(l,r):
    merged = []
    i, j = 0,0
    end = 'e'
    l += [end]
    r += [end]
    for _ in range(len(l) + len(r) - 2):
        if r[j] == end:
            merged.append(l[i])
            i += 1
        elif l[i] == end:
            merged.append(r[j])
            j += 1
        elif l[i] <= r[j]:
            merged.append(l[i])
            i += 1
        else:
            merged.append(r[j])
            j += 1
    return merged

def sorting(p_l):
    if len(p_l) >= 2:
        p_l1 = p_l[:len(p_l)//2]
        p_l2 = p_l[len(p_l)//2:]
        return merge(sorting(p_l1), sorting(p_l2))
    else:
        return p_l

a_l = [int(x) for x in input().split(' ')]

a_l_tmp = []
p_l = []
p_l_sorted = []
for a in a_l:
    p_l_tmp = list(map(lambda x:a*x, a_l_tmp))
    a_l_tmp.append(a)
    p_l += p_l_tmp
    # print(p_l_tmp)
    # p_l_sorted = merge(p_l_sorted, sorting(p_l_tmp))
p_l_sorted = sorting(p_l)
# print(p_l_sorted)
print(p_l_sorted[K-1])