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:
# Code for D - Pairs
# Use input() to fetch data from STDIN
import logging
from itertools import combinations

[n, k] = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

g = []
z = []
l = []
for x in a:
    if x > 0:
        g.append(x)
    elif x < 0:
        l.append(x)
    else:
        z.append(x)

lb = len(l) * len(g)
zb = lb + len(z) * len(l) + len(z) * (len(z) - 1) // 2 + len(z) * len(g)

if k <= lb:
    r = []
    for x in l:
        for y in g:
            r.append(x * y)
    print(sorted(r)[k])
elif k <= zb:
    print(0)
else:
    r = []
    for x in combinations(l, 2):
        r.append(x[0] * x[1])
    for x in combinations(g, 2):
        r.append(x[0] * x[1])
    print(sorted(r)[k - zb - 1])

Submission status: Runtime Error

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

N = int(N)
K = int(K)
A = list(map(int, A))

B = []
for i in range(N):
    for j in range(N):
        if i>j:
            B.append(A[i] * A[j])

B.sort()

print(B[K])

Submission status: Runtime Error

Solution code:
import itertools

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

for index, item in enumerate(A):
    if item > 0:
        tmp = index
        break

B = A[:tmp]
lb = len(B)
C = A[tmp:]
lc = len(C)


if K <= lb*lc:
    count = 0
    D = [None]*(lb*lc)
    for i in B:
        for j in C:
            D[count] = i*j
            count += 1
    D = sorted(D)
    print(D[K])
else:
    counter = 0
    D = [None]*(lb*(lb-1)//2)
    for i in range(lb-1):
        for j in range(i+1, lb):
            D[counter] = B[i]*B[j]
            counter += 1
    counter = 0
    E = [None]*(lc*(lc-1)//2)
    for i in range(lc-1):
        for j in range(i+1, lc):
            E[counter] = C[i]*C[j]
            counter += 1
    F = sorted(D+E)
    print(F[N-(K-lb*lc)])
    print
"""
10 40
5 4 3 2 -1 0 0 0 0 0
"""

Submission status: Runtime Error

Solution code:
count, index = input().split()
ary = (int(x) for x in input().split())
ary1 = []
ary2 = []
for i in ary:
    ary1.append(i)
    ary2.append(i)
seki = []

cnt1 = 0
cnt2 = 0
for i in ary1:
    #半分行ったら終了
    if cnt1 >= int(count)/2:
        break
    for j in ary2:
        print(str(cnt1)+"|"+str(cnt2))
        if cnt1 != cnt2:
            seki.append(i * j)
        cnt2 = cnt2 + 1
    cnt2 = 0
    cnt1 += 1
seki.sort()
print(seki)
print(seki[int(index)])
#print(seki[count[1]])

Submission status: Runtime Error

Solution code:
import itertools
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
negatives = []
positives = []
zeros = []
for n in A:
    if n < 0:
        negatives.append(n)
    elif n > 0:
        positives.append(n)
    else:
        zeros.append(n)
negatives.sort()
positives.sort(reverse=True)
P = len(positives)
N = len(negatives)
Z = len(zeros)
if K < P*N:
    products = []
    for n in range(P):
        for m in range(N):
            products.append(negatives[n]*positives[m])
    products.sort()
    print(products[K-1])
    exit()
if K >= P*N and K < (P+N+Z)*(P+N+Z-1)//2-P*(P-1)//2-N*(N-1)//2:
    print(0)
else:
    products = []
    for n in range(P-1):
        for m in range(n+1, P):
            products.append(positives[n]*positives[m])
    for m in range(N-1):
        for n in range(m+1, N):
            products.append(negatives[n]*negatives[m])
    products = sorted(products)
    print(products[K-P*N-Z*(P+N)-Z*(Z-1)//2-1])

Submission status: Runtime Error

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

d={}
r = []
for i in range(len(A)-1):
  for j in range(i+1,len(A)):
    k = A[i]*A[j]
    if k not in d:
      d[k] = 1
    else:
      d[k] +=1
      
kk = sorted(d.keys())
#print(kk)
summ=0
last = None
for k in kk:
  summ += d[k]
  if N<=summ:
    if last==None:
      last=k
    print(last)
    exit(1)

  last = k

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)
b = np.array(A)

m = np.outer(a, b)

ans = []
n = 1

for i in m:
    ans.extend(i[n:])
    n += 1

ans = sorted(ans, reverse=True)    
print(ans[K])

Submission status: Runtime Error

Solution code:
import sys
import bisect
sys.setrecursionlimit(10 ** 7)

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

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

negative = minus * plus
positive = (plus * (plus - 1) // 2) + (minus * (minus - 1) // 2)
zeros = (N * N - 1) // 2 - (positive + negative)

if K <= negative:
    A0 = A[:minus]
    A1 = A[plus:]
    A1.sort()

    left = -(10 ** 18)
    right = 0

    print(A0)
    print(A1)

    def test(val):
        cnt = 0
        lg = len(A0)
        for a0 in A0:
            p = val // a0
            cnt += lg - bisect.bisect_left(A1, p)
        return cnt

    while (right - left) > 1:
        mid = (left + right) // 2
        res = test(mid)
        print("mid,cnt", mid, res)
        if res >= K:
            right = mid
        else:
            left = mid

    print(left)
    exit()


elif negative < K and K <= (negative + zeros):
    print(0)
    exit()
else:
    A0 = A[:minus]
    A1 = A[plus:]

    A0.sort(reverse=True)

    K -= zeros + negative

    def test(val):
        cnt = 0
        lg = len(A0)
        if lg > 1:
            for i in ren(lg - 1):
                l = i+1
                r = len(lg) - 1

                a0 = A0[i]
                if val < a0 * A0[l]:
                    continue

                while (r - l) > 1:
                    m = (l + r) // 2
                    if val < a0 * A0[m]:
                        r = m
                    else:
                        l = m

                cnt += l

        lg = len(A1)
        if lg > 1:
            for i in ren(lg - 1):
                l = i+1
                r = len(lg) - 1

                a0 = A0[i]
                if val < a0 * A0[l]:
                    continue

                while (r - l) > 1:
                    m = (l + r) // 2
                    if val < a0 * A0[m]:
                        r = m
                    else:
                        l = m

                cnt += l
        return cnt

    left = 0
    right = 10 ** 18

    while (right - left) > 1:
        mid = (left + right) // 2
        res = test(mid)
        if res >= K:
            right = mid
        else:
            left = mid

    print(left)
    exit()

Submission status: Runtime Error

Solution code:
n = int(input())
sl = list(input() for _ in range(n))

sl_s = sorted(list(set(sl)))

# if len(sl_s) == 1:
#     print(sl[0])
# else:
#     ans = []
#     count = 1
#     for s in sl_s:
#         if sl.count(s) == count and ans.count(s) == 0:
#             ans.append(s)
#         elif sl.count(s) > count and ans.count(s) == 0:
#             ans.clear()
#             ans.append(s)
#             count = sl.count(s)
#     print('\n'.join(ans))


dict = {}
for s in sl:
    if s in dict:
        dict[s] += 1
    else:
        dict[s] = 1

ans_ = [k for k, v in dict.items() if v == max(dict.values())]
ans = '\n'.join(sorted(ans_))
print(ans)

Submission status: Runtime Error

Solution code:
NK = list(map(int,input().split()))
N = NK[0]
K = NK[1]
a = list(map(int,input().split()))
ans = []
for i in range(N-1):
    for j in range(i+1, N):
        ans.append(a[i]*a[j])
ans.sort()
print(ans[K])

Submission status: Runtime Error

Solution code:
n,k=(int(x) for x in input().split())
list1 = list(map(int, input().split()))
list1.sort()
list2 = [n-1]*n
list3=[]
for j in range(n):
	list3.append(list1[j]*list1[list2[j]])
for j in range(k):
	max=list3.index(max(list3))
	list2[max]-=1
	list3[max]=list1[max]*list2[max]
print(list3[max])

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)
minus_num = zero_i * (N-zero_i)
minus_A = A[:zero_i][::-1]
plus_A = A[zero_i:]

if K <= minus_num:
    def isOK(score):
        count = 0
        for a in minus_A:
            border_score = score/a
            index = bright(plus_A, border_score)
            count += index
            if count >= K:
                return False
        return True
    ng = minus_A[0] * plus_A[0]
    ok = minus_A[-1] * plus_A[-1]

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
    # check ok is ok?
    count = 0
    for a in minus_A:
        border_score = ok/a
        index = bright(plus_A, border_score)
        count += index
    if count == K:
        print(ok)
    else:
        print(ng)
    # print(ok, ng)
    # print(plus_A, minus_A)
else:
    def isOK(score):
        count = 0
        for i, a in enumerate(minus_A):
            if i == len(minus_A):
                break
            border_score = score/a
            index = bright(minus_A[i+1:], border_score)
            count += index
            if count >= K:
                return False
        for i, a in enumerate(plus_A):
            if i == len(plus_A):
                break
            if a == 0:
                count += len(plus_A[i+1:])
            else:
                border_score = score/a
                index = bright(plus_A[i+1:], border_score)
                count += index
            if count >= K:
                return False
        return True

    K -= minus_num
    minus_A = [-1 * a for a in minus_A]
    #print(minus_A)
    if len(minus_A) == 1:
        ng = plus_A[-1]*plus_A[-2]
        ok = plus_A[0]*plus_A[1]
    elif len(plus_A) == 1:
        ng = minus_A[-1]*minus_A[-2]
        ok = minus_A[0]*minus_A[1]
    else:
        ng = max(minus_A[-1]*minus_A[-2], plus_A[-1]*plus_A[-2])
        ok = min(minus_A[0]*minus_A[1], plus_A[0]*plus_A[1])
    #print(plus_A, minus_A)
    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
    max_A = 0
    count = 0
    for i, a in enumerate(minus_A):
        if i == len(minus_A):
            break
        border_score = ok/a
        index = bright(minus_A[i+1:], border_score)
        if index != 0:
            max_A = max(max_A, a*minus_A[i+1+index-1])
        count += index
    for i, a in enumerate(plus_A):
        if i == len(plus_A):
            break
        if a == 0:
            count += len(plus_A[i+1:])
            max_A = max(max_A, 0)
        else:
            border_score = ok/a
            index = bright(plus_A[i+1:], border_score)
            if index != 0:
                max_A = max(max_A, a*plus_A[i+1+index-1])
            count += index
    if count == K:
        print(max_A)
        exit()
    #print(ok, ng)
    #print(plus_A, minus_A)
    max_A = 0
    count = 0
    for i, a in enumerate(minus_A):
        if i == len(minus_A):
            break
        border_score = ng/a
        index = bright(minus_A[i+1:], border_score)
        if index != 0:
            max_A = max(max_A, a*minus_A[i+1+index-1])
        count += index
    for i, a in enumerate(plus_A):
        if i == len(plus_A):
            break
        if a == 0:
            count += len(plus_A[i+1:])
            max_A = max(max_A, 0)
        else:
            border_score = ng/a
            index = bright(plus_A[i+1:], border_score)
            if index != 0:
                max_A = max(max_A, a*plus_A[i+1+index-1])
            count += index
    print(max_A)

Submission status: Runtime Error

Solution code:
n,order = map(int, input().split())
nums = [int(str) for str in input().split()]
maxn = int(n * (n-1) /2)
result = list(range(maxn))
bangou = 0
 
for x in range(n-1):
  for y in range(n-x-2):
    result[bangou] = int( nums[x] * nums[x + y + 1] )
    bangou += 1

result.sort()
print(result[order-1])

Submission status: Runtime Error

Solution code:
import bisect
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
zm=bisect.bisect_left(0,a)
z=a.count(0)
zp=n-zm-z
m=[]
p=[]
for i in range(zm):
  m.append(a[i])
for i in range(zm+z,n):
  p.append(a[i])
if k<=zm*zp:
  Zm=map(abs,zm)
  Z=Zm+p
  Z.sort()
  print(-Z[k-1])
  sys.exit()
if zm*zp<k<=(zm*zp)+z*(zm+zp):
  print(0)
  sys.exit()
else:
  def sq(l):
    return(l**2)
  Zm=map(sq,m)
  Zp=map(sq,p)
  Z=Zm+Zp
  k=k-(zm+z)
  Z.sort()
  print(Z[k-1])
  sys.exit()

Submission status: Runtime Error

Solution code:
from itertools import combinations
N, K =map(int,input().split())
A = list(map(int,input().split()))
memo = [["a" for _ in range(max(A)+1)] for _ in range(max(A)+1)]
ans = []
for x in list(combinations(A, 2)):
    if memo[x[0]][x[1]] != "a":
        ans.append(memo[x[0]][x[1]])
    else:
        memo[x[0]][x[1]] = x[0]*x[1]
    ans.append(memo[x[0]][x[1]])
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
n, k  = map(int, input().split())
plst = []
mlst = []
zlst = []
lst = map(int,input().split())
lst = sorted(lst, key=int)
abslst = []

p = len(plst)
m = len(mlst)
z = len(zlst)
a = len(abslst)

if k <= p * m:
    h = k // p + 1
    w = k - (h -1) * p
    print(mlst[h-1] * plst[w-1])
elif k <= (p + m) * z:
    print(0)
else:
    h = k // p + 1
    w = k - (h -1) * p
    print(mlst[h] * mlst[w])

Submission status: Runtime Error

Solution code:
from bisect import bisect_right, bisect_left

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

t0 = bisect_left(A,0)
t1 = bisect_right(A,0)
pos = A[t1:]
neg = [-v for v in reversed(A[:t0])]
zeros = t1-t0
offset_negative = len(pos)*len(neg)
offset_zero = zeros*(N-zeros) + zeros*(zeros-1)//2
offset = offset_zero + offset_negative

def bisect2(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

def count1(l,n):
    j = len(l)
    cnt = 0
    for i,a in enumerate(l):
        v = n//a
        while j > i and l[j-1] > v:
            j -= 1
        if j <= i:
            break
        else:
            cnt += j-i-1
    return cnt

def count2(l1,l2,n):
    j = len(l2)
    cnt = 0
    for i,a in enumerate(l1):
        v = n//a
        while j > 0 and l2[j-1] > v:
            j -= 1
        cnt += j
    return cnt


def cnt(n):
    if n > 0:
        cnt = count1(pos,n-1) + count1(neg,n-1) + offset
    else:
        cnt = offset_negative - count2(pos,neg,-n)
    return cnt


if offset_negative < K <= offset:
    print(0)
else:
    temp = max(pos[-1],neg[-1])**2
    print(bisect2(temp, -temp, lambda n: cnt(n) <= K-1))

# from itertools import combinations
# s = sorted(a*b for a,b in combinations(A,2))
# for i,v in enumerate(s):
#     print(cnt(v),i,v)

Submission status: Runtime Error

Solution code:
list1=[]
list2=[]
n,m = input().split()
n = int(n)
m = int(m)
list1 = [int(x) for x in input().split()]
for i in range(0,n-1):
  for j in range(i+1,n):
    list2.append(list1[i]*list1[j])
    #print(list2)
    print(list2[m-1])

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
m = 0
z = 0
p = 0
while A[m] < 0:
  m += 1
while A[m+z] == 0:
  z += 1
p = N -m -z
n_m = m*p
n_p = m*m + p*p
n_z = N(N-1)//2 - n_m - n_p
if K <= n_m:
  
elif n_m < K <= n_m + n_z:
  print(0)
else:

Submission status: Runtime Error

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

zero_list = []
plus_list = []
minus_list = []
for i in A:
    if i == 0:
        zero_list.append(i)
    elif i > 0:
        plus_list.append(i)
    else:
        minus_list.append(i)

minus = len(minus_list) * len(plus_list)
zero = int(len(zero_list) * (N-len(zero_list)) + len(zero_list)*(len(zero_list)-1)/2)
plus = int((len(minus_list)*((len(minus_list))-1) + len(plus_list)*(len(plus_list)-1))/2)

number_list = []
if minus > K:
    tyokuseki = itertools.product(minus_list, plus_list)
    for i in tyokuseki:
        number_list.append(tyokuseki[0]*tyokuseki[1])
    number_list.sort()
    print(number_list[K-1])

elif minus < K <= (minus+zero):
    print(0)

else:
    conb1 = itertools.combinations(minus_list, 2)
    conb2 = itertools.combinations(plus_list, 2)
    for i in conb1:
        number_list.append(i[0]*i[1])
    for i in conb2:
        number_list.append(i[0]*i[1])
    number_list.sort()
    print(number_list[K-minus-zero-1])

Submission status: Runtime Error

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

import numpy as np
arr = np.array(a, dtype=np.int64)
arr2 = arr
arr = np.c_[arr]

ar = np.outer(arr,arr2)
art = np.triu(ar, k=1)
l= art[np.triu_indices(n, k=1)]
l_sort = np.sort(l)
print(l_sort[k-1])

Submission status: Runtime Error

Solution code:
from itertools import combinations
N, K =map(int,input().split())
A = list(map(int,input().split()))
memo = [[0 for _ in range(max(A)+1)] for _ in range(max(A)+1)]
ans = []
for x in list(combinations(A, 2)):
    if memo[x[0]][x[1]] != 0:
        ans.append(memo[x[0]][x[1]])
    else:
        memo[x[0]][x[1]] = x[0]*x[1]
    ans.append(memo[x[0]][x[1]])
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
import sys
import heapq
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, K = [int(x) for x in input().strip().split()]
A = sorted([int(x) for x in input().strip().split()])
minus = [x for x in A if x < 0]
zeros = [x for x in A if x == 0]
plus = [x for x in A if x > 0]

len_minus = len(minus)
len_zeros = len(zeros)
len_plus = len(plus)
if len_minus * len_plus >= K:
    cnt = 0
    mi = 0
    pi = 0
    q = [(minus[0]*plus[-1], mi, pi)]
    while cnt < K:
        cnt += 1
        v, mi, pi = heapq.heappop(q)
        if mi < len_minus - 1:
            heapq.heappush(q, (minus[mi+1]*plus[-1-pi], mi+1, pi))
        if pi < len_plus - 1:
            heapq.heappush(q, (minus[mi]*plus[-1-(pi+1)], mi, pi+1))
    print(minus[mi]*plus[-1-pi])
else:
    K -= len_minus * len_plus
    if len_zeros * (len_zeros - 1) // 2 + len_zeros * (len_minus + len_plus) >= K:
        print(0)
    else:
        K -= len_zeros * (len_zeros - 1) // 2 + len_zeros * (len_minus + len_plus)
        cnt = 0
        pi1 = 0
        pi2 = 1
        mi1 = 0
        mi2 = 1
        if plus[pi1]*plus[pi2] <= minus[-1-mi1]*minus[-1-mi2]:
            q = [(plus[pi1]*plus[pi2], pi1, pi2, 1)]
        else:
            q = [(minus[mi1]*minus[pi2], pi1, pi2, 0)]
        while cnt < K:
            cnt += 1
            v, i1, i2, f = heapq.heappop(q)
            if f == 1:
                if i1 + 1 < i2:
                    heapq.heappush(q, (plus[i1+1]*plus[i2], i1+1, i2, f))
                if i2 < len_plus - 1:
                    heapq.heappush(q, (plus[i1]*plus[i2+1], i1, i2+1, f))
            else:
                if i1 + 1 < i2:
                    heapq.heappush(q, (minus[-1-(i1+1)]*minus[-1-i2], i1+1, i2, f))
                if i2 < len_minus - 1:
                    heapq.heappush(q, (minus[-1-i1]*minus[-1-(i2+1)], i1, i2+1, f))
        if f == 1:
            print(plus[i1]*plus[i2])
        elif f == 0:
            print(minus[-1-i1]*minus[-1-i2])

Submission status: Runtime Error

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

d={}
r = []
for i in range(len(A)-1):
  for j in range(i+1,len(A)):
    k = A[i]*A[j]
    if k not in d:
      d[k] = 1
    else:
      d[k] +=1
      
kk = sorted(d.keys())
print(kk)
summ=0
last = None
for k in kk:
  if N<=summ:
    if last==None:
      last=k
    print(last)
    exit(1)

  summ += d[k]
  last = k

Submission status: Runtime Error

Solution code:
import itertools
N, K= map(int,input().split())
num_list = list(map(int,input().split()))
set_list = list(set(num_list))
count = 0
ans_list = []
for i in range(len(set_list)):
  num_a = set_list[i]
  count = num_list.count(num_a)
  if count >= 2:
    ans_list += [num_a**2] * int(count*(count-1)/2)
  for j in range(i+1,len(set_list)):
    num_b = set_list[j]
    count = num_list.count(num_a) * num_list.count(num_b)
    ans_list += [num_a*num_b] * count
ans_list.sort()
print(ans_list[K-1])

Submission status: Runtime Error

Solution code:
import bisect
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
zm=bisect.bisect_left(0,a)
z=a.count(0)
zp=n-zm-z
m=[]
p=[]
for i in range(zm):
  m.append(a[i])
for i in range(zm+z,n):
  p.append(a[i])
if k<=zm*zp:
  Zm=map(abs,zm)
  Z=Zm+zm
  lm=[]
  num_m=0
  for i in range(zm):
    num_m+=zp
    lm.append(num_m)
  idx_m=bisect.bisect_left(k,lm)
  Lm=[]
  p.sort(reverse=True)
  for j in range(zp):
    Lm.append(m[idx_m]*p[j])
  k=k-(idx_m*zp)
  print(Lm[k-1])  
if zm*zp<k<=(zm*zp)+z*(zm+zp):
  print(0)
  sys.exit()
else:
  def sq(l):
    return(l**2)
  Zm=map(sq,m)
  Zp=map(sq,p)
  Z=Zm+Zp
  k=k-(zm+z)
  Z.sort()
  print(Z[k-1])
  sys.exit()

Submission status: Runtime Error

Solution code:
[N, K] = list(map(int, input().split()))
A = list(map(int, input().split()))
[Am, Az, Ap] = [[],[],[]]
for a in A:
  if a < 0:
    Am.append(a)
  elif a == 0:
    Az.append(a)
  else:
    Ap.append(a)
    
Am.sort() 
Az.sort() 
Ap.sort()

mul = []
mulm = len(Am) * len(Ap)
mulz = int(len(Az) * (len(Am)+len(Ap)) + len(Az)*(len(Az)-1)/2)
mulp = int((len(Am) * (len(Am)-1) + len(Ap) * (len(Ap)-1))/2)

if K < mulm:
  for i in Am:
    for j in Ap:
      mul.append(i*j)
  mul.sort()
  print(mul[K-1])
elif K < mulm+mulz:
  print(0)
else:
  for i in range(len(Am)):
    for j in range(i+1, len(Am)):
      mul.append(Am[i]*Am[j])
  for i in range(len(Ap)):
    for j in range(i+1, len(Ap)):
      mul.append(Ap[i]*Ap[j])
  mul.sort()
  print(mul[K-mulm-mulz-1])

Submission status: Runtime Error

Solution code:
from itertools import combinations
import numpy as np

def multiply(A):
  return(A[0]*A[1])
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
A = np.array(A)
over_0 = A[A > 0]
under_0 = A[A < 0]
zero = A[A == 0]
minus = len(over_0) * len(under_0)
between_zero = minus + len(over_0) * len(zero) + len(under_0) * len(zero) + (len(zero)*(len(zero)-1)/2)
if minus >= K:
    a = len(under_0) // K
    b = len(under_0) % K
    answer = over_0[a] * under_0[b-2]
elif minus < K and K <= between_zero:
    answer = 0
else:
    answer = sorted(list(map(multiply, combinations(over_0, r=2))) + list(map(multiply, combinations(under_0, r=2))))[K-int(between_zero) -1 ]
print(answer)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A,B,C,X=[],[],[],[]
a=map(int,input().split())
for i in (a):
    if i==0:
        B.append(i)
    elif i<0:
        A.append(i)
    else:
        C.append(i)
D=len(A)*len(C)
if D>=K:
    for a in (A):
        for c in (C):
            d=a*c
            X.append(d)
    X.sort()
    print(X[K])
elif D+len(B)>=K:
    print(0)
else:
    E=K-D-len(B)
    for a in (A):
        for c in (A):
            d=a*c
            X.append(d)
    for a in (C):
        for c in (C):
            d=a*c
            X.append(d)
    X.sort()
    print(X[E])

Submission status: Runtime Error

Solution code:
import bisect
n,k = map(int,input().split( ))
a = list(map(int, input().split( )))

a.sort()

#2分探索
#負の数あるぞ

j = bisect.bisect_left(a,-0,1)
l = bisect.bisect_right(a,0.1)
a1 = a[:j]
a2 = a[l:]
if j*(n-l)>=k:##負の数で揃う
    mx = 0
    mn = -max(a1[0]*a1[0],a2[0]*a2[0])-1
    while mx-mn>1:
        md = (mx+mn)//2
        cnt = 0
        for t in range(j):
            tmp = bisect.bisect_left(a2,md//a1[t])
            cnt += n-l-tmp
        if cnt >=k:
            mx = md
        else:
            mn = md
        print(mx)
        exit()
k -= j*(n-l)

if k<=(l-j)*(l-j-1)//2+(n-l+j)*(l-j):
    print(0)
    exit()
#print(k,(n-l+j)*(l-j)+(l-j)*(l-j-1)//2)
k-=(l-j)*(l-j-1)//2+(n-l+j)*(l-j)
#print(k,k)
mx = max(a1[0]*a1[0],a2[-1]*a2[-1])+1
mn = -1
a1 = [-a1[j-i-1] for i in range(j)]
while mx-mn>1:
    md = (mx+mn)//2
    cnt = 0
    for t in range(j):
        tmp = bisect.bisect_right(a1,md//a1[t])
        cnt += tmp
        if tmp >=t+1:
            cnt-=1
    for t in range(n-l):
        tmp = bisect.bisect_right(a2,md//a2[t])
        cnt += tmp
        if tmp>=t+1:
            tmp-=1
    if cnt >= 2*k:
        mx = md
    else:
        mn = md
print(mx)

Submission status: Runtime Error

Solution code:
import bisect
def Main(N, K, A):
    L_fu = []
    L_sei = []
#     A.sort()
    fu = list(filter(lambda x: x < 0, A))
    zero = list(filter(lambda x: x == 0, A))
    sei = list(filter(lambda x: x > 0, A))
    n_f = len(fu)
    n_z = len(zero)
    n_s = len(sei)
    fu.sort()
    sei.sort()
    m_f = n_f*n_s
    m_s = n_f*(n_f-1)//2+n_s*(n_s-1)//2
    if K <= m_f:
        for i in range(n_f):
            for j in range(n_s):
                bisect.insort_left(L_fu, fu[i]*sei[j])
        return L_fu[K-1]
    elif N*(N-1)//2 - K <= m_s:
        for i in range(n_f-1):
            for j in range(i+1, n_f):
                bisect.insort_left(L_sei, fu[i]*fu[j])
        for i in range(n_s-1):
            for j in range(i+1, n_s):
                bisect.insort_left(L_sei, sei[i]*sei[j])
        return L_sei[K-N*(N-1)//2-1]        
    else:
        return 0
    
    
#     print(len(P))
#     print(P)
    return P[K-1]

def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    print(Main(N, K, A))
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
N, K = list(map(int, input().split()))
A_N = list(map(int, input().split()))
comb = N*(N-1)/2
B = []
b = 0
for i in range(N-1):
    for j in range(N-1):
        if i <= j:
            b = A_N[i] * A_N[j+1]
            B.append(b)
            b = 0
B = sorted(B)
print(B[K])

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
n, k = map(int,input().split())
a = list(map(int,input().split()))

ans = list(itertools.combinations(a, 2))
ans = np.array(ans)

ans = np.prod(ans, axis = 1)
ans = np.sort(ans)

print(ans[k-1])

Submission status: Runtime Error

Solution code:
_n,k = gets.split.map(&:to_i)
ar = gets.split.map(&:to_i)
ar2 = []
ar.combination(2).to_a.each do |v|
  ar2 << v[0] * v[1]
end

ar2.sort!
puts ar2[k-1]

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

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

info.sort()
another_info = info.copy()

info = np.array(info)
another_info = np.array(another_info)

info = info.reshape(n,1)
another_info = another_info.reshape(1, n)

ans_arr = info * another_info

print(ans_arr)
ans_arr = ans_arr.tolist()

for i in range(n):
    ans_arr[i] = ans_arr[i:]
ans_arr = list(itertools.chain.from_iterable(ans_arr))
ans_arr.sort()
print(ans_arr[k-1])

Submission status: Runtime Error

Solution code:
import heapq
N, K=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
if A[0]>=0:
  print(kantan(A))
  exit()
if A[-1]<=0:
  A=A[::-1]
  print(kantan(A))
  exit()
  
x=0
y=N-1
while y-x>1:
  if A[(x+y)//2]<0:
    x=(x+y)//2
  else:
    y=(x+y)//2
w=y
z=N-1
while z-w>1:
  if A[(w+z)//2]<1:
    w=(w+z)//2
  else:
    z=(w+z)//2
    
if A[y]!=0:
    y=z
    
po=y*(y-1)//2+(N-z)*(N-z-1)//2
ne=y*(N-z)
ze=(z-y)*(N-(z-y))+(z-y)*(z-y-1)//2

if K<=ne:
  nums=[[A[0]*A[-1], 0, -1]]
  heapq.heapify(nums)
  counter=0
  sumi=[[0]*N for _ in range(N)]
  while counter<K:
    tmp=heapq.heappop(nums)
    if A[tmp[1]+1]<0 and sumi[tmp[1]+1][tmp[2]]==0:
      heapq.heappush(nums, [A[tmp[1]+1]*A[tmp[2]], tmp[1]+1, tmp[2]])
      sumi[tmp[1]+1][tmp[2]]=1
      sumi[tmp[2]][tmp[1]+1]=1
    if A[tmp[2]-1]>0 and sumi[tmp[1]][tmp[2]+1]==0:
      heapq.heappush(nums, [A[tmp[1]]*A[tmp[2]-1], tmp[1], tmp[2]-1])
      sumi[tmp[1]][tmp[2]+1]=1
      sumi[tmp[2]+1][tmp[1]]=1
    counter+=1
  print(tmp[0])
  exit()
  
def kantan(A):
  nums=[[A[0]*A[1], 0, 1]]
  heapq.heapify(nums)
  counter=0
  sumi=[[0]*N for _ in range(N)]
  while counter<K:
    tmp=heapq.heappop(nums)
    if tmp[2]-tmp[1]>1 and sumi[tmp[1]+1][tmp[2]]==0:
      heapq.heappush(nums, [A[tmp[1]+1]*A[tmp[2]], tmp[1]+1, tmp[2]])
      sumi[tmp[1]+1][tmp[2]]=1
      sumi[tmp[2]][tmp[1]+1]=1
    if tmp[2]<N-1 and sumi[tmp[1]][tmp[2]+1]==0:
      heapq.heappush(nums, [A[tmp[1]+1]*A[tmp[2]], tmp[1], tmp[2]+1])
      sumi[tmp[1]][tmp[2]+1]=1
      sumi[tmp[2]+1][tmp[1]]=1
    counter+=1
  return tmp[0]
  
if K<=ne+ze:
  print(0)
  exit()

nums=[[A[y-2]*A[y-1], y-2, y-1, -1], [A[z]*A[z+1], z, z+1, 1]]
heapq.heapify(nums)
counter=ne+ze
sumi=[[0]*N for _ in range(N)]
while counter<K:
  tmp=heapq.heappop(nums)
  if tmp[3]>0:
    if tmp[2]-tmp[1]>1 and sumi[tmp[1]+1][tmp[2]]==0:
      heapq.heappush(nums, [A[tmp[1]+1]*A[tmp[2]], tmp[1]+1, tmp[2], 1])
      sumi[tmp[1]+1][tmp[2]]=1
      sumi[tmp[2]][tmp[1]+1]=1
    if tmp[2]<N-1 and sumi[tmp[1]][tmp[2]+1]==0:
      heapq.heappush(nums, [A[tmp[1]]*A[tmp[2]+1], tmp[1], tmp[2]+1, 1])
      sumi[tmp[1]][tmp[2]+1]=1
      sumi[tmp[2]+1][tmp[1]]=1
  else:
    if tmp[2]-tmp[1]>1 and sumi[tmp[1]][tmp[2]-1]==0:
      heapq.heappush(nums, [A[tmp[1]]*A[tmp[2]-1], tmp[1], tmp[2]-1, -1])
      sumi[tmp[1]][tmp[2]-1]=1
      sumi[tmp[2]-1][tmp[1]]=1
    if tmp[2]>0 and sumi[tmp[1]-1][tmp[2]]==0:
      heapq.heappush(nums, [A[tmp[1]]*A[tmp[2]-1], tmp[1]-1, tmp[2], -1])
      sumi[tmp[1]-1][tmp[2]]=1
      sumi[tmp[2]][tmp[1]-1]=1
  counter+=1
print(tmp[0]) #\(^o^)/ｺﾞﾘｵｼｼﾀｲｼﾞﾝｾｲﾀﾞｯﾀ

Submission status: Runtime Error

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

dp = [[0] * ((n+1)*2) for _ in range((n+1)*2)]

for i in itertools.combinations(a, 2):
    if dp[i[0]+n][i[1]+n] != 0:
        res = dp[i[0]+n][i[1]+n]
    else:
        res = i[0] * i[1]
        dp[i[0]+n][i[1]+n] = res
    ans.append(res)
ans.sort()
print(ans[k-1])

Submission status: Runtime Error

Solution code:
import math

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

fu = len([i for i in A if i < 0])
zero = len([i for i in A if i == 0])
sei = len([i for i in A if i > 0])

fu_num = fu * sei
zero_num = zero * (fu + sei)
sei = fu * (fu - 1) + sei * (sei - 1)

fu = A[:fu_num]
sei = A[fu + zero:]

if fu_num < k <= fu_num + zero:
    print("0")