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: Runtime Error

Solution code:
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)
    print(answer[K - 1])


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

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

    # test(A, K)
    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
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            # mid以下の積はK個未満か？ left以下の積は常にK個未満
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses).astype(int), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:
        K -= M+Z
        left = 0
        right = max(minuses[0] ** 2, pluses[-1] ** 2)
        while left + 1 < right:
            mid = (left + right) // 2
            a = mid // minuses
            b = (m - np.searchsorted(minuses, a, side='left')).sum() - (mid >= minuses ** 2).sum()
            b //= 2

            d = mid // pluses
            e = np.searchsorted(pluses, d, side='right').sum() - (mid >= pluses ** 2).sum()
            e //= 2

            if b + e < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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)
    print(answer[K - 1])


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

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

    test(A, K)
    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
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            # mid以下の積はK個未満か？ left以下の積は常にK個未満
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses).astype(int), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:

        K -= M+Z
        left = 0
        right = max(minuses[0] ** 2, pluses[-1] ** 2)
        while left + 1 < right:
            mid = (left + right) // 2
            a = mid // minuses
            b = (m - np.searchsorted(minuses, a, side='left')).sum() - (mid >= minuses ** 2).sum()
            b //= 2

            d = mid // pluses
            e = np.searchsorted(pluses, d, side='right').sum() - (mid >= pluses ** 2).sum()
            e //= 2

            if b + e < K:
                left = mid
            else:
                right = mid

        print(right)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
import numpy as np


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

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

    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
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses).astype(int), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:
        print(n)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect
N, K = map(int, input().split())
A = sorted(map(int, input().split()))
bleft = bisect.bisect_left
bright = bisect.bisect_right
zero_i = bleft(A, 0)
zero_i2 = bright(A, 0)
tmp_zero_num = zero_i2-zero_i
zero_num = tmp_zero_num * (N-tmp_zero_num) + tmp_zero_num*(tmp_zero_num-1)//2

minus_A = A[:zero_i][::-1]
plus_A = A[zero_i2:]
LM = len(minus_A)
LP = len(plus_A)

minus_num = len(minus_A) * len(plus_A)
plus_num = len(minus_A)*(len(minus_A)-1)//2 + len(plus_A)*(len(plus_A)-1)//2
if K <= minus_num:
    def isOK(score):
        count = 0
        for a in minus_A:
            border_score = (score*(-1)) // (-a)
            #print(a, border_score)
            index = bright(plus_A, border_score)
            count += LP - index

        if count >= K:
            return True
        else:
            return False
    ok = minus_A[0] * plus_A[0]
    ng = minus_A[-1] * plus_A[-1] - 1

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

    print(ok)
    # print(plus_A, minus_A)
elif K <= zero_num+minus_num:
    print(0)
else:
    def isOK(score):
        count = 0
        if LM > 1:
            for i, a in enumerate(minus_A):
                if i == LM - 1:
                    break
                border_score = score//a
                index = bright(minus_A[i+1:], border_score)
                count += index
                if count >= K:
                    return True
        if LP > 1:
            for i, a in enumerate(plus_A):
                if i == LP - 1:
                    break
                border_score = score//a
                index = bright(plus_A[i+1:], border_score)
                count += index
                #print(count)
                if count >= K:
                    return True
        return False

    K -= (minus_num + zero_num)
    minus_A = [-1 * a for a in minus_A]

    if len(minus_A) < 1:
        ok = plus_A[-1]*plus_A[-2]
        ng = plus_A[0]*plus_A[1] - 1
    elif len(plus_A) < 1:
        ok = minus_A[-1]*minus_A[-2]
        ng = minus_A[0]*minus_A[1] - 1
    else:
        ok = max(minus_A[-1]*minus_A[-2], plus_A[-1]*plus_A[-2])
        ng = min(minus_A[0]*minus_A[1], plus_A[0]*plus_A[1]) - 1

    while(abs(ok-ng) > 1):
        mid = (ok+ng) // 2
        f = isOK(mid)
        print(ok,ng,mid,f)
        if f:
            ok = mid
        else:
            ng = mid
    print(ok)
    print(K, LM, LP, tmp_zero_num)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
import numpy as np


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

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

    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
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)

    if K <= M:
        left = A[0] * A[-1] - 1
        right = -1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(pluses, np.ceil(mid / minuses), side='left')).sum()
            if cnt < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:
        print(n)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = map(int,input().split())
a = list(map(int,input().split()))
A = np.array(a, dtype='int64')
A_outer = np.outer(A, A)
A_triu = A_outer[np.triu_indices(N, k = 1)]

A_triu.sort()  

print(A_triu[K-1])

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
import numpy as np
from math import ceil


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

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

    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 K <= M:
        left = A[0] * A[-1] - 1
        right = 0
        minuses = np.array(A[:m], np.int64)
        pluses = np.array(A[-p:], np.int64)
        while left + 1 < right:
            mid = ceil((left + right) / 2)
            a = (p-np.searchsorted(pluses, np.ceil(mid / minuses), side='left')).sum()
            if a < K:
                left = mid
            else:
                right = mid

        print(right)
    elif K <= M + Z:
        print(0)
    else:
        print(n)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
import numpy as np
from math import ceil

read = sys.stdin.read

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

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 K <= M:
    left = A[0] * A[-1] - 1
    right = 0
    minuses = np.array(A[:m], np.int64)
    pluses = np.array(A[-p:], np.int64)
    while left + 1 < right:
        mid = ceil((left + right) / 2)
        a = (p-np.searchsorted(pluses, np.ceil(mid / minuses), side='left')).sum()
        if a < K:
            left = mid
        else:
            right = mid

    print(right)
else:
    print(n)

Submission status: Runtime Error

Solution code:
import numpy as np
N,K = map(int,input().split())
A = np.array([int(i) for i in input().split()])

posi = A[A>0]
zero = A[A==0]
nega = A[A<0]


def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    # count 0
    if x >= 0:
        cnt_tpl += len(zero) * N
    # count posi
    cnt_tpl += np.searchsorted(A, x//pos, side='right').sum()
    # count nega
    cnt_tpl += (N - np.searchsorted(A, (-x - 1) // (-neg), side='right')).sum()
    # remove a^2
    cnt_tpl -= np.count_nonzero(A*A <= x)
    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)

Submission status: Runtime Error

Solution code:
n ,K = map(int,input().split())
A = [int(i) for i in input().split()]

# プラスとマイナスに分ける
plus_list = []
minus_list = []
zero = 0
for i in range(n):
    if a_list[i] > 0:
        plus_list.append(A[i])
    elif a_list[i] < 0:
        minus_list.append(-A[i])
    else:
        zero += 1

plus_list.sort()
minus_list.sort()

# 二分探索
ng, ok = -(10 ** 18)-1, 10 ** 18+1
while ok - ng > 1:
    mid = (ok + ng) // 2
    s = 0
    if mid < 0:
        j = 0
        for i in range(len(minus_list) - 1, -1, -1):
            while j < len(plus_list) and minus_list[i] * plus_list[j] < -mid:
                j += 1
            s += len(plus_list) - j

    else :
        j = len(plus_list) - 1
        for i in range(len(plus_list)):
            while j >= 0 and plus_list[i] * plus_list[j] > mid:
                j -= 1
            s += max(0, j - i)

        j = len(minus_list) - 1
        for i in range(len(minus_list)) :
            while j >= 0 and minus_list[i] * minus_list[j] > mid :
                j -= 1
            s += max(0, j - i)

        s += (len(plus_list) + len(minus_list)) * zero + len(plus_list) * len(minus_list) + zero * (zero - 1) // 2

    if s < K :
        ng = mid
    else :
        ok = mid

print(ok)

Submission status: Runtime Error

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

# プラスとマイナスに分ける
plus_list = []
minus_list = []
zero = 0
for i in range(n):
    if a_list[i] > 0:
        p.append(A[i])
    elif a_list[i] < 0:
        m.append(-A[i])
    else:
        zero += 1

plus_list.sort()
minus_list.sort()

# 二分探索
ng, ok = -(10 ** 18)-1, 10 ** 18+1
while ok - ng > 1:
    mid = (ok + ng) // 2
    s = 0
    if mid < 0:
        j = 0
        for i in range(len(minus_list) - 1, -1, -1):
            while j < len(plus_list) and minus_list[i] * plus_list[j] < -mid:
                j += 1
            s += len(plus_list) - j

    else :
        j = len(plus_list) - 1
        for i in range(len(plus_list)):
            while j >= 0 and plus_list[i] * plus_list[j] > mid:
                j -= 1
            s += max(0, j - i)

        j = len(minus_list) - 1
        for i in range(len(minus_list)) :
            while j >= 0 and minus_list[i] * minus_list[j] > mid :
                j -= 1
            s += max(0, j - i)

        s += (len(plus_list) + len(minus_list)) * zero + len(plus_list) * len(minus_list) + zero * (zero - 1) // 2

    if s < K :
        ng = mid
    else :
        ok = mid

print(ok)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
[n,k]=map(int,input().split())
a=np.array(list(map(int,input().split())))
     
c=sorted([x * y for x, y in itertools.combinations(a,2)])
print(c[k-1])

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left, bisect_right
import numpy as np


def cmb(n):
    if n == 0:
        return 0
    over = n * (n - 1)
    return over // 2


read = sys.stdin.read

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

A.sort()
minus = bisect_left(A, 0)
plus = N - bisect_right(A, 0)
zero = N - minus - plus

A_minus = np.array(A[:minus], np.int64)
A_plus = np.array(A[-plus:], np.int64)

minus_pair = minus * plus
zero_pair = cmb(zero) + zero * (N - zero)
plus_pair = cmb(N) - zero_pair - minus_pair

if K <= minus_pair:
    left = A_minus[0] * A_plus[-1] - 1
    right = -1

    while left + 1 < right:
        mid = (left + right) // 2
        a = np.ceil(mid / A_minus)
        b = (plus - np.searchsorted(A_plus, a, side='left')).sum()

        if b < K:
            left = mid
        else:
            right = mid

    print(right)

elif minus_pair < K <= minus_pair + zero_pair:
    print(0)
else:
    K -= minus_pair + zero_pair
    left = 0
    right = max(A_minus[0] ** 2, A_plus[-1] ** 2)
    while left + 1 < right:
        mid = (left + right) // 2
        a = mid // A_minus
        b = (minus - np.searchsorted(A_minus, a, side='left')).sum() - (mid >= A_minus ** 2).sum()
        b //= 2

        d = mid // A_plus
        e = np.searchsorted(A_plus, d, side='right').sum() - (mid >= A_plus ** 2).sum()
        e //= 2

        if b + e < K:
            left = mid
        else:
            right = mid

    print(right)

Submission status: Runtime Error

Solution code:
import bisect

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

left=-10**18
right=10**18
count=0

a=bisect.bisect_left(A,0)
b=bisect.bisect_right(A,0)

if n*(n-1)-b*(n-a)-(b-a)>=2*k:
    right=0
else:
    left=1

while right!=left:
    pos=(left+right)//2
    count=0
    for a in A:
        if a==0 and pos>=0:
            count+=n-1
        elif a<0:
            i=bisect.bisect_right(A,(-1-pos)//(-a))
            count+=n-i + (-1 if a*a<=pos else 0)
        else:
            i=bisect.bisect_right(A,pos//a)
            count+=i + (-1 if a*a<=pos else 0)
    if count>=2*k:
        right=pos
    else:
        left=pos+1

print(left)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if k <= mc * pc:
    d = a[:mc]
    u = a[mc + z:]
    H = 0
    L = d[0] * u[-1]
    D = len(d)
    while H - L > 1:
        M = (H + L) // 2
        count = 0
        P = 0
        for x in u:
            while P < D:
                if d[P] > M // x:
                    break
                P += 1
            count += P
        if count == k:
            break
        elif count < k:
            L = M
        else:
            H = M
    print(H)
    exit()
elif k <= mc * pc + z * (n - z) + z * (z - 1) // 2:
    print(0)
    exit()

d = list(map(lambda x: -x, reversed(a[:mc])))
u = a[mc + z:]
D = len(d)
U = len(u)

k -= mc * pc + z * (n - z) + z * (z - 1) // 2
L = 0
H = max(d[-1] * d[-1], u[-1] * u[-1])

while H - L > 1:
    M = (H + L) // 2
    count = 0
    P = 0
    for i in range(U-1, -1, -1):
        x = u[i]
        while P < U:
            if u[P] * x > M:
                break
            P += 1
        count += P
    for i in range(U):
        if u[i] ** 2 <= M:
            count -= 1
        else:
            break
    P = 0
    for i in range(D-1, -1, -1):
        x = d[i]
        while P < D:
            if d[P] * x > M:
                break
            P += 1
        count += P
    for i in range(D):
        if d[i] ** 2 <= M:
            count -= 1
        else:
            break
    count //= 2
    if count < k:
        L = M
    else:
        H = M
print(H)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if k <= mc * pc:
    d = a[:mc]
    u = a[mc + z:]
    H = 0
    L = d[0] * u[-1]
    D = len(d)
    while H - L > 1:
        M = (H + L) // 2
        count = 0
        P = 0
        for x in u:
            while P < D:
                if d[P] > M // x:
                    break
                P += 1
            count += P
        if count == k:
            break
        elif count < k:
            L = M
        else:
            H = M
    if count == k:
        print(M)
    else:
        print(M+1)
    exit()
elif k <= mc * pc + z * (n - z) + z * (z - 1) // 2:
    print(0)
    exit()

d = list(map(lambda x: -x, reversed(a[:mc])))
u = a[mc + z:]
D = len(d)
U = len(u)

k -= mc * pc + z * (n - z) + z * (z - 1) // 2
#print(k, mc * pc, z * (n-z), z * (z-1) // 2)
#print(U, D, mc, pc, z)
#print(d)
# #print(u)

L = 0
H = max(d[-1] * d[-1], u[-1] * u[-1])

while H - L > 1:
    M = (H + L) // 2
    count = 0
    P = 0
    for i in range(U-1, -1, -1):
        x = u[i]
        while P < U:
            if u[P] * x > M:
                break
            P += 1
        count += P
    for i in range(U):
        if u[i] ** 2 <= M:
            count -= 1
        else:
            break
    P = 0
    for i in range(D-1, -1, -1):
        x = d[i]
        while P < D:
            #print(x, P)
            if d[P] * x > M:
                break
            P += 1
        count += P
    for i in range(D):
        if d[i] ** 2 <= M:
            count -= 1
        else:
            break
    count //= 2
    if count < k:
        L = M
    else:
        H = M
if count == k:
    print(M)
else:
    print(M+1)

Submission status: Runtime Error

Solution code:
x,order = map(int, input().split())
nums = [int(str) for str in input().split()]

z = sum([int==0 for int in nums])
n = sum([int<0 for int in nums])
p = sum([int>0 for int in nums])

zero = int(z * (x-1) - z * (z-1) /2)
nega = int(p * n)
posi = int((n * (n-1) + p * (p-1)) /2)

if order > nega and order <= nega + zero:
  print(0)
else:
  negnums = [i for i in nums if i < 0]
  posnums = [i for i in nums if i > 0]
  if order <= nega:
    result = list(range(nega))
    nu = 0
    try:
      for y in negnums:
      	for z in posnums:
        	result[nu] = y*z
        	nu += 1
    except:
      pass
    result.sort()
    print(result[order-1])
  else:
    result = list(range(posi))
    nu = 0
    try:
      for y in range(n-1):
      	for z in range(n-y-1):
          result[nu] = negnums[y]*negnums[y + z +1]
      	  nu += 1
      for y in range(p-1):
        for z in range(p-y-1):
          result[nu] = posnums[y]*posnums[y + z +1]
          nu += 1
    except:
      pass
    result.sort()
    print(result[order-nega-zero-1])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
import sys


def D(*a, **kwa):
    print(*a, file=sys.stderr, **kwa)


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

neg = [a for a in A if a < 0]
pos = [a for a in A if a > 0]

n_neg = len(neg)
n_pos = len(pos)
n_zero = N - n_neg - n_pos

pairs = N * (N - 1) // 2
neg_pairs = n_neg * n_pos
zero_pairs = n_zero * (n_zero - 1) // 2 + n_zero * (N - n_zero)
pos_pairs = pairs - neg_pairs - zero_pairs

mi = []
ma = []
if n_neg > 0 and n_pos > 0:
    mi.append(neg[0] * pos[-1])
if n_zero > 0:
    mi.append(0)
    ma.append(0)
if n_neg >= 2:
    mi.append(neg[-1] * neg[-2])
    ma.append(neg[0] * neg[1])
if n_pos >= 2:
    mi.append(pos[0] * pos[1])
    ma.append(pos[-1] * pos[-2])
if len(mi) == 0:
    mi.append(-10**18)
if len(ma) == 0:
    ma.append(10**18)


def cnt(x):
    res = 0
    if x < 0:
        for ne in neg:
            i = bisect_left(pos, (x + ne + 1) // ne)
            if i == n_pos: break
            res += n_pos - i
    elif x == 0:
        res = neg_pairs + zero_pairs
    else:
        for po in pos:
            i = bisect_right(pos, x // po)
            if i == 0: break
            res += i
            if i > 0 and po <= pos[i - 1]:
                res -= 1
        for ne in reversed(neg):
            if i == n_neg: break
            i = bisect_right(neg, (x - ne - 1) // ne)
            res += n_neg - i
            if i < n_neg and ne >= neg[i]:
                res -= 1
        res //= 2
        res += neg_pairs + zero_pairs
    return res


l, r = min(mi) - 1, max(ma)
while r - l > 1:
    m = l + (r - l) // 2
    c = cnt(m)
    #D(l, m, r, c)
    if c >= K:
        r = m
    else:
        l = m

print(r)

Submission status: Runtime Error

Solution code:
x,order = map(int, input().split())
nums = [int(str) for str in input().split()]

z = sum([int==0 for int in nums])
n = sum([int<0 for int in nums])
p = sum([int>0 for int in nums])

zero = int(z * (x-1) - z * (z-1) /2)
nega = int(p * n)
posi = int((n * (n-1) + p * (p-1)) /2)

if order > nega and order <= nega + zero:
  print(0)
else:
  negnums = [i for i in nums if i < 0]
  posnums = [i for i in nums if i > 0]
  if order >= nega + posi:
    order -= nega + zero
    result = list(range(posi))
    nu = 0
    for y in range(n-1):
      for z in range(n-y-1):
        result[nu] = negnums[y]*negnums[y + z +1]
        nu += 1
    for y in range(p-1):
      for z in range(p-y-1):
        result[nu] = posnums[y]*posnums[y + z +1]
        nu += 1
    result.sort()
    print(result[order-1])

Submission status: Runtime Error

Solution code:
x,order = map(int, input().split())
nums = [int(str) for str in input().split()]

z = sum([int==0 for int in nums])
n = sum([int<0 for int in nums])
p = sum([int>0 for int in nums])

zero = int(z * (x-1) - z * (z-1) /2)
nega = int(p * n)
posi = int((n * (n-1) + p * (p-1)) /2)

if order > nega and order <= nega + zero:
  print(0)
else:
  negnums = [i for i in nums if i < 0]
  posnums = [i for i in nums if i > 0]
  if order <= nega:
    result = list(range(nega))
    nu = 0
    for y in negnums:
      for z in posnums:
        result[nu] = y*z
        nu += 1

Submission status: Runtime Error

Solution code:
x,order = map(int, input().split())
nums = [int(str) for str in input().split()]

z = sum([int==0 for int in nums])
n = sum([int<0 for int in nums])
p = sum([int>0 for int in nums])

zero = int(z * (x-1) - z * (z-1) /2)
nega = int(p * n)
posi = int((n * (n-1) + p * (p-1)) /2)

if order > nega and order <= nega + zero:
  print(0)
else:
  negnums = [i for i in nums if i < 0]
  posnums = [i for i in nums if i > 0]
  if order <= nega:
    result = list(range(nega))
    nu = 0
    for y in negnums:
      for z in posnums:
        result[nu] = y*z
        nu += 1
    result.sort()
    print(result[order-1])

Submission status: Runtime Error

Solution code:
x,order = map(int, input().split())
nums = [int(str) for str in input().split()]

z = sum([int==0 for int in nums])
n = sum([int<0 for int in nums])
p = sum([int>0 for int in nums])

zero = int(z * (x-1) - z * (z-1) /2)
nega = int(p * n)
posi = int((n * (n-1) + p * (p-1)) /2)

if order > nega and order <= nega + zero:
  print(0)
else:
  negnums = [i for i in nums if i < 0]
  posnums = [i for i in nums if i > 0]
  if order <= nega:
    result = list(range(nega))
    nu = 0
    for y in negnums:
      for z in posnums:
        result[nu] = y*z
        nu += 1
    result.sort()
    print(result[order-1])
  else:
    order -= nega + zero
    result = list(range(zero + nega + posi))
    nu = 0
    for y in range(n-1):
      for z in range(n-y-1):
        result[nu] = negnums[y]*negnums[y + z +1]
        nu += 1
    for y in range(p-1):
      for z in range(p-y-1):
        result[nu] = posnums[y]*posnums[y + z +1]
        nu += 1
    result.sort()
    print(result[order-1])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
import sys


def D(*a, **kwa):
    print(*a, file=sys.stderr, **kwa)


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

neg = [a for a in A if a < 0]
pos = [a for a in A if a > 0]

n_neg = len(neg)
n_pos = len(pos)
n_zero = N - n_neg - n_pos

pairs = N * (N - 1) // 2
neg_pairs = n_neg * n_pos
zero_pairs = n_zero * (n_zero - 1) // 2 + n_zero * (N - n_zero)
pos_pairs = pairs - neg_pairs - zero_pairs

mi = []
ma = []
if neg_pairs > 0 and pos_pairs > 0:
    mi.append(neg[0] * pos[-1])
if n_zero > 0:
    mi.append(0)
    ma.append(0)
if n_neg >= 2:
    mi.append(neg[-1] * neg[-2])
    ma.append(neg[0] * neg[1])
if n_pos >= 2:
    mi.append(pos[0] * pos[1])
    ma.append(pos[-1] * pos[-2])
if len(mi) == 0:
    mi.append(-10**18)
if len(ma) == 0:
    ma.append(10**18)


def cnt(x):
    res = 0
    if x < 0:
        for ne in neg:
            i = bisect_left(pos, (x + ne + 1) // ne)
            if i == n_pos: break
            res += n_pos - i
    elif x == 0:
        res = neg_pairs + zero_pairs
    else:
        for po in pos:
            i = bisect_right(pos, x // po)
            if i == 0: break
            res += i
            if i > 0 and po <= pos[i - 1]:
                res -= 1
        for ne in reversed(neg):
            if i == n_neg: break
            i = bisect_right(neg, (x - ne - 1) // ne)
            res += n_neg - i
            if i < n_neg and ne >= neg[i]:
                res -= 1
        res //= 2
        res += neg_pairs + zero_pairs
    return res


l, r = min(mi) - 1, max(ma)
while r - l > 1:
    m = l + (r - l) // 2
    c = cnt(m)
    #D(l, m, r, c)
    if c >= K:
        r = m
    else:
        l = m

print(r)

Submission status: Runtime Error

Solution code:
x,order = map(int, input().split())
nums = [int(str) for str in input().split()]

z = sum([int==0 for int in nums])
n = sum([int<0 for int in nums])
p = sum([int>0 for int in nums])

zero = int(z * (x-1) - z * (z-1) /2)
nega = int(p * n)
posi = int((n * (n-1) + p * (p-1)) /2)

if order > nega and order <= nega + zero:
  print(0)
else:
  negnums = [i for i in nums if i < 0]
  posnums = [i for i in nums if i > 0]
  if order <= nega:
    result = list(range(nega))
    nu = 0
    for y in negnums:
      for z in posnums:
        result[nu] = int(y*z)
        nu += 1
    result.sort()
    print(result[order-1])
  else:
    order -= nega + zero
    result = list(range(posi))
    nu = 0
    for y in range(n-1):
      for z in range(n-y-1):
        result[nu] = int(negnums[y]*negnums[y + z +1])
        nu += 1
    for y in range(p-1):
      for z in range(p-y-1):
        result[nu] = int(posnums[y]*posnums[y + z +1])
        nu += 1
    result.sort()
    print(result[order-1])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
import sys

def D(*a, **kwa):
    print(*a, file=sys.stderr, **kwa)

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

neg = [a for a in A if a < 0]
pos = [a for a in A if a > 0]

n_neg = len(neg)
n_pos = len(pos)
n_zero = N - n_neg - n_pos

pairs = N * (N-1) // 2
neg_pairs = n_neg * n_pos
zero_pairs = n_zero * (n_zero-1) // 2 + n_zero * (N - n_zero)
pos_pairs = pairs - neg_pairs - zero_pairs

def cnt(x):
    res = 0
    if x < 0:
        for ne in neg:
            i = bisect_left(pos, (x +ne+1)// ne)
            if i == n_pos: break
            res += n_pos - i
    elif x == 0:
        res = neg_pairs + zero_pairs
    else:
        for po in pos:
            i = bisect_right(pos, x // po)
            if i == 0: break
            res += i
            if i > 0 and po <= pos[i-1]:
                res -= 1
        for ne in reversed(neg):
            if i == n_neg: break
            i = bisect_right(neg, (x -ne-1)// ne)
            res += n_neg - i
            if i < n_neg and ne >= neg[i]:
                res -= 1
        res //= 2
        res += neg_pairs + zero_pairs
    return res

l, r = -10**18-1, 10**18
while r-l > 1:
    m = l + (r - l) // 2
    c = cnt(m)
    #D(l, m, r, c)
    if c >= K:
        r = m
    else:
        l = m

print(r)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
k=int(input().split()[1])
source = [int(i) for i in input().split()]

#target = []
nagasa=len(source)

for j in range(nagasa):
    num=source[j]
    for i in range(j+1, nagasa):
        target.append(num*source[i])
#target=[source[y]*source[x]for y in range(nagasa) for x in range(y+1,nagasa)]
target.sort()
#print(sorted_target[k-1])
print(target[k-1])

Submission status: Runtime Error

Solution code:
x,order = map(int, input().split())
nums = [int(str) for str in input().split()]

z = sum([int==0 for int in nums])
n = sum([int<0 for int in nums])
p = sum([int>0 for int in nums])

zero = int(z * (x-1) - z * (z-1) /2)
nega = int(p * n)
posi = int((n * (n-1) + p * (p-1)) /2)

if order > nega and order <= nega + zero:
  print(0)
else:
  negnums = [i for i in nums if i < 0]
  posnums = [i for i in nums if i > 0]
  if order <= nega:
    result = list(range(p*n))
    nu = 0
    for y in negnums:
      for z in posnums:
        result[nu] = int(y*z)
        nu += 1
    result.sort()
    print(result[order-1])
  else:
    order -= nega + zero
    result = list(range(posi))
    nu = 0
    for y in range(n-1):
      for z in range(n-y-1):
        result[nu] = int(negnums[y]*negnums[y + z +1])
        nu += 1
    for y in range(p-1):
      for z in range(p-y-1):
        result[nu] = int(posnums[y]*posnums[y + z +1])
        nu += 1
    result.sort()
    print(result[order-1])