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: Accepted

Solution code:
import sys
import numpy as np


TEST_INPUT = [
    """
    4 3
    3 3 -4 -2
    """,
    """
    10 40
    5 4 3 2 -1 0 0 0 0 0
    """,
    """
    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
    """
]
ANSWER = [
    "-6",
    "6",
    "448283280358331064"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


def query(a, n, a_arr_p, a_arr_n, n_zeros, k):

    # return (num of pairs <= a) < k

    if a >= 0:
        # negative
        res = len(a_arr_p) * len(a_arr_n)
        # zero
        res += n_zeros * (n - n_zeros) + n_zeros * (n_zeros - 1) // 2
        # p * p
        res_pp = np.searchsorted(a_arr_p, a // a_arr_p, side="right").sum()
        res_pp -= (a_arr_p * a_arr_p <= a).sum()
        res += res_pp // 2
        # n * n
        res_nn = np.searchsorted(a_arr_n, a // a_arr_n, side="right").sum()
        res_nn -= (a_arr_n * a_arr_n <= a).sum()
        res += res_nn // 2
    else:
        # p * n
        res = len(a_arr_p) * len(a_arr_n) - np.searchsorted(a_arr_n, (a_arr_p - a - 1) // a_arr_p, side="left").sum()
    # print(a, res)
    if res < k:
        return True
    else:
        return False


def solve(n, k, a_list):

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

    a_arr = np.array(a_list)

    a_arr_p = a_arr[a_arr > 0]
    a_arr_n = - a_arr[a_arr < 0]
    n_zeros = (a_arr == 0).sum()
    a_arr_p.sort()
    a_arr_n.sort()

    while right > left + 1:
        if query(center, n, a_arr_p, a_arr_n, n_zeros, k):
            left, center = center, (center + right) // 2
        else:
            center, right = (left + center) // 2, center

    return right


def input_and_solve(ih):
    n, k = map(int, ih.input().split())
    a_list = list(map(int, ih.input().split()))
    res = solve(n, k, a_list)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        # print(res, ans)
        assert str(res) == str(ans)


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

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

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

p = []
m = []
zero = 0
for i in range(N) :
  if A[i] > 0 :
    p.append(A[i])
  elif A[i] < 0 :
    m.append(-A[i])
  else :
    zero += 1

p.sort()
m.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(m) - 1, -1, -1) :
      while j < len(p) and m[i] * p[j] < -mid :
        j += 1
      s += len(p) - j
      
  else :
    j = len(p) - 1
    for i in range(len(p)) :
      while j >= 0 and p[i] * p[j] > mid :
        j -= 1
      s += max(0, j - i)
      
    j = len(m) - 1
    for i in range(len(m)) :
      while j >= 0 and m[i] * m[j] > mid :
        j -= 1
      s += max(0, j - i)
      
    s += (len(p) + len(m)) * zero + len(p) * len(m) + zero * (zero - 1) // 2

  if s < K :
    ng = mid
  else :
    ok = mid
    
print(ok)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A00 = A[:]

A0 = []
A1 = []

F = [0,0,0]
for i in range(n):
    if A[i] > 0:
        F[0] += 1
        A0.append(A[i])
    elif A[i] == 0:
        F[1] += 1
    else:
        F[2] += 1
        A1.append(A[i])
G = [F[2]*(F[2]-1)//2 + F[0]*(F[0]-1)//2,
 (F[0]+F[2]) * F[1] + F[1]*(F[1]-1)//2,
  F[2] * F[0]]
# print("G",G)
g = 2
if G[2] < k and G[2]+G[1] >= k:
    k -= G[2]
    g = 1
if G[2]+G[1] < k:
    k -= G[2]+G[1]
    g = 0
if g==2:
    k = n*(n-1)//2 + 1 - k  # 上からk番目
    k -= G[0]+G[1]  # 負になるペアの中で上からk番目
    
k -= 1 # これで「それより絶対値が下の数がk個」になる
# print("k",k)

# print("g",g)

if g==1:
    print(0)
elif g==0:
    A = A0[:]
    B = [-i for i in A1]
    B.sort()
    le = -1
    ri = 10**18+2
    m = (le+ri) // 2
    while ri-le > 1:
        ans = 0
        if len(A) > 0:
            j0 = len(A)-1
            for i in range(len(A)):
                while j0 > i and A[i]*A[j0] >= m:
                    j0 -= 1
                ans += j0-i
                j0 = max(i+1,j0)
        if len(B) > 0:
            j1 = len(B)-1
            for i in range(len(B)):
                while j1 > i and B[i]*B[j1] >= m:
                    j1 -= 1
                ans += j1-i
                j1 = max(i+1,j1)
        # print(le,ri,m,ans) # ansはm未満の数の個数
        if ans > k:
            ri = m
        else:
            le = m
        m = (le+ri)//2
    print(le)
else:
    # print("k",k)
    A = A0[:]
    B = [-i for i in A1]
    B.sort()
    # print(A,B)

    le = -1
    ri = 10**18+2
    m = (le+ri) // 2
    while ri-le > 1:
        ans = 0
        if len(A) > 0:
            j0 = len(B)-1
            for i in range(len(A)):
                # print("seki",A[i]*B[j0])
                while j0 >= 0 and A[i]*B[j0] >= m:
                    
                    j0 -= 1
                ans += j0+1
                # print("plus",j0)
        # print(le,ri,m,ans) # ansはm未満の数の個数
        if ans > k:
            ri = m
        else:
            le = m
        m = (le+ri)//2
    print(-le)



# CC = []
# A = A00[:]
# for i in range(n):
#     for j in range(i+1,n):
#         CC.append(A[i]*A[j])
# CC.sort()
# print("lenCC", len(CC))
# print(CC)
# print(CC[400:420])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*a = [int(i) for i in read().split()]
#a = [int(i) for i in readline().split()]
#n = int(input())

def solve():
    from bisect import bisect_right, bisect_left
    
    n,k,*a = map(int,read().split())
    a.sort()
    
    #v = [a[i]*a[j] for i in range(n) for j in range(i+1,n)]
    #v.sort()
    #print(v)
    #print(v[k-1])
    
    l = bisect_left(a,0)
    r = bisect_right(a,0,lo = l)
    
    a_neg = [-i for i in a[:l][::-1]]
    a_pos = a[r:]
    
    if k <= l*(n-r): # negative
        def check(x): #x 以上は k 個以上あるか？
            res = (n-r)*l
            L = n-r
            v = 0
            for i in a_neg[::-1]:
                V = (x+i-1)//i
                while v < L and a_pos[v] < V:
                    v += 1
                res -= v
            return res >= k
    
        ok = 0
        ng = 10**18
        while ng-ok > 1:
            mid = (ok+ng)//2
            if check(mid): ok = mid
            else: ng = mid
    
        print(-ok)
    
    elif k <= n*(n-1)//2 - l*(l-1)//2 - (n-r)*(n-r-1)//2:
        print(0)
    
    else:
        k -= n*(n-1)//2 - l*(l-1)//2 - (n-r)*(n-r-1)//2
    
        def check(x): #x 以下は k 個以上あるか？
            res = 0
            vn = l-1
            for i,ai in enumerate(a_neg):
                X = x//ai
                while vn and a_neg[vn] > X:
                    vn -= 1            
                #vn = bisect_right(a_neg,x//ai,hi=vn)
                if vn+1 > i+1: res += vn+1-i-1

            vp = n-r-1
            for i,ai in enumerate(a_pos):
                X = x//ai
                while vp and a_pos[vp] > X:
                    vp -= 1            
                #vp = bisect_right(a_pos,x//ai,hi=vp)
                if vp+1 > i+1: res += vp+1-i-1
            return res >= k
        
        ng = 0
        ok = 10**18
        while ok-ng > 1:
            mid = (ok+ng)//2
            if check(mid): ok = mid
            else: ng = mid
    
        print(ok)


solve()

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.sort(np.array(input().split(),np.int64))
z = A[A == 0]
p = A[A > 0]
n = A[A < 0]

def count_func(x):
    cnt = 0
    if x >= 0:
        cnt += len(z) * N
    cnt += np.searchsorted(A, x // p, side='right').sum()
    cnt += (N - np.searchsorted(A, (-x - 1) // (-n), side='right')).sum()
    cnt -= np.count_nonzero(A * A <= x)
    assert cnt % 2 == 0
    return cnt // 2

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

print(r)

Submission status: Accepted

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(abs(a) for a in A)**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: Accepted

Solution code:
N, K = map(int, input().split())
A = sorted([int(a) for a in input().split()])

pos = 0
zer = 0
neg = 0
for a in A:
    if a > 0: pos += 1
    elif a < 0: neg += 1
    else: zer += 1
B = [a for a in A if a > 0]
C = [-a for a in A if a < 0][::-1]
b = len(B)
c = len(C)

def cnt(x):
    if x >= 0:
        re = pos * neg + zer * (pos + neg) + zer * (zer - 1) // 2
        j = b - 1
        for i in range(b):
            while j >= 0 and B[i] * B[j] > x:
                j -= 1
            re += max(j - i, 0)
        j = c - 1
        for i in range(c):
            while j >= 0 and C[i] * C[j] > x:
                j -= 1
            re += max(j - i, 0)
        return re
        
    re = 0
    j = 0
    y = -x
    for i in range(b)[::-1]:
        while j < c and B[i] * C[j] < y:
            j += 1
        re += c - j
    return re

l, r = - (1<<60), 1<<60
while r - l > 1:
    m = (l+r) // 2
    if cnt(m) >= K:
        r = m
    else:
        l = m

print(r)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

import numpy as np

# from libs.debug import debug

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

A = np.array(A, dtype=int)
minuses = np.msort(np.abs(A[A < 0]))
pluses = np.msort(A[A > 0])
zeros = A[A == 0]


def solve():
    p = []
    for a, b in itertools.combinations(A, r=2):
        p.append(a * b)
    p.sort()
    print(p[K - 1])


def test(n):
    # n 以下の数が k こ以上ある
    minus_cnt = len(minuses) * len(pluses)
    zeros_cnt = len(zeros) * (N - len(zeros)) + (len(zeros) * (len(zeros) - 1) // 2)
    if n == 0:
        return minus_cnt + zeros_cnt >= K
    ret = minus_cnt + zeros_cnt
    if n > 0:
        a = np.searchsorted(pluses, n // pluses, side='right')
        b = np.searchsorted(minuses, n // minuses, side='right')
        c = pluses ** 2 <= n
        d = minuses ** 2 <= n
        return ret + (a.sum() + b.sum() - c.sum() - d.sum()) // 2 >= K
    else:
        a = np.searchsorted(-minuses[::-1], n // pluses, side='right')
        b = np.searchsorted(-pluses[::-1], n // minuses, side='right')
        return (a.sum() + b.sum()) // 2 >= K


ok = 10 ** 18 - 1
ng = -10 ** 18 - 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if test(mid):
        ok = mid
    else:
        ng = mid
print(ok)

# solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def solve_binary(mid):
  count = 0

  if mid == 0:
    count = (P+M)*zero + P*M + (zero*(zero-1)//2 if zero >= 2 else 0)
    return k <= count

  if mid < 0:
    # jのスタート位置を求める
    # for j in range(P):
    #   if Plus[j]*Minus[0] <= mid: break
    j=0
    for i in range(M):
      while j<P and Plus[j]*Minus[i] > mid:
        j += 1
      count += P-j
    return k <= count

  if mid > 0:
    count += (P+M)*zero + P*M + (zero*(zero-1)//2 if zero >= 2 else 0)
    # Mについて
    # print(count,mid)
    j = 0
    for i in range(M-1,-1,-1):
      while j<M and Minus[j]*Minus[i] > mid:
        j += 1
      count += max(0,i-j)
    # print(count,mid)
    # Pについて
    j = P-1
    for i in range(P):
      while 0<=j and Plus[j]*Plus[i] > mid:
        j -= 1
      count += max(0,j-i)
    # print(count,mid)
    return k <= count
      

def binary_search(n):
    ng=-n-1
    ok=n
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve_binary(mid):
            ok=mid
        else:
            ng=mid
    return ok

zero=0
n,k=map(int,input().split())
A=list(map(int,input().split()))
Minus=[]; Plus=[]
for ai in A:
  if ai < 0: Minus.append(ai)
  elif ai == 0 : zero += 1
  elif ai > 0: Plus.append(ai)
Minus.sort(); Plus.sort()
M = len(Minus) ; P = len(Plus)
# print(solve_binary(6))
# print(solve_binary(448283280358331064))
# print(solve_binary(2))
# exit()
X = binary_search(10 ** 18)
print(X)

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input

n, k = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
i = 0
while i < n and A[i] < 0:
    i += 1
Aneg = A[:i]
Apos = A[i:]

Aneg.reverse()
nneg = len(Aneg)
npos = len(Apos)

l = -10**18 - 100
r = 10**18 + 100
while l < r:
    mid = l + r >> 1

    counter = 0
    if mid >= 0:
        counter += nneg * npos
        for B in Aneg, Apos:
            j = 0
            for i in reversed(range(len(B))):
                b = B[i]
                while j < len(B) and B[j] * b <= mid:
                    j += 1
                counter += min(j, i)
    else:
        j = 0
        for i in range(nneg):
            a = Aneg[i]
            while j < npos and Apos[~j] * a <= mid:
                j += 1
            counter += j
    
    if counter >= k:
        r = mid
    else:
        l = mid + 1

print l

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np
stdin = open(0)

N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().split(), np.int64)


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


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


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


print(right)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
minus = [-x for x in a if x < 0]
plus = [x for x in a if x >= 0]

minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        x = -x
        r = 0
        for num in minus[::-1]:
            while r < len(plus) and plus[r] * num < x:
                r += 1
            ans += len(plus) -  r
        return ans

    r = 0
    for num in minus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(minus) and minus[r] * num <= x:
            r += 1
        ans += r
    r = 0
    for num in plus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(plus) and plus[r] * num <= x:
            r += 1
        ans += r
    ans //= 2
    ans += len(minus) * len(plus)    
    return ans

bottom = 0
top = 2*(10**18) + 2


while top - bottom > 1:
    mid = (top + bottom) // 2
    if cnt(mid - 10**18-1) < k:
        bottom = mid
    else:
        top = mid

print(int(top - 10**18-1))

Submission status: Runtime Error

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

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

li_p = []
li_m = []
li_0 = []
li_all = []

a.sort()

for i in range(n):
    if a[i]<0:
        li_m.append(a[i])
    elif a[i] == 0:
        li_0.append(a[i])
    else:
        li_p.append(a[i])


LI_m =len(li_m)
LI_0 =len(li_0)
LI_p =len(li_p)


if k <= LI_0 - 1:
    print(0)

elif LI_0 - 1 < k < LI_m * LI_p:
    li_p.sort(reverse=True)
    for i in range(LI_m):
        for j in range(LI_p):

            li_all.append(li_m[i]*li_p[j])
            li_all.sort()
    else:
        print(li_all[k - LI_0 -1])

else:
    li_p.sort(reverse=True)
    for i in range(LI_m-1):

Submission status: Runtime Error

Solution code:
from numpy import *
N,K = map(int,input().split())
A = array(sorted(list(map(int,input().split()))))
nega = A[A<0]
zera = A[A==0]
posa = A[0<A]

def cnt(x):
  y = 0
  if x>=0:
    y+=n*len(zera)
  y+=searchsorted(A,x//posa,side="right").sum()
  y+=N*len(nega)-searchsorted(A,-(-x//nega)).sum() 
  y-=len(A[A*A<=x])
  return y//2

r = 10**18
l = -r-1

while r-l>1:
  c=(r+l)//2
  if K<=cnt(c):
    r=c
  else:
    l=c

print(r)

Submission status: Runtime Error

Solution code:
import bisect

N, K = list(map(int, input().split()))
A = map(int, input().split())
A_neg = map(lambda x: -x, A)


l = -10000000000
r = 10000000000


def check_search(m):
    cnt = 0
    for x in A:
        if x == 0:
            cnt += len(A) if m > 0 else 0
        elif x > 0:
            cnt += bisect.bisect_left(A, m / x)
        else:
            cnt += bisect.bisect_left(A_neg, m / x)

    return cnt <= K


while l + 1 < r:
    m = (l + r) // 2
    if check_search(m):
        l = m
    else:
        r = m
print(l)

Submission status: Runtime Error

Solution code:
import itertools

a,b = map(int, input().split())
num_list = [int(input()) for _ in range(a)]
print(sort(list(itertools.permutations(num_list, 2)))[b-1])

Submission status: Runtime Error

Solution code:
import decimal

def solve_gutyoku(N, K, A):
    A_combinations = []
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            A_combinations.append(A[i] * A[j])
    ans = sorted(A_combinations)[K-1]
    return ans


def solve(N, K, A):
    for i, a in enumerate(A):
        if a >= 0:
            break
    for j, a in enumerate(A):
        if a > 0:
            break
    A_hu = A[:i]
    A_0 = A[i:j]
    A_sei = A[j:]
    n_hu = len(A_hu)*len(A_sei)
    n_0 = len(A_0)*(len(A)-1) - len(A_0)*(len(A_0)-1)//2
    n_sei = (len(A_sei) - 1) * len(A_sei) // 2 + \
        (len(A_hu) - 1) * len(A_hu) // 2
    if K > n_hu and K <= n_hu + n_0:
        return 0
    elif K <= n_hu:
        left, right = int(-1 * 1e18), 0
        while right - left > 1:
            piv = (left + right) // 2
            cnt = 0
            for a in A_sei:
                piv_ = piv / a
                if A_hu[-1] <= piv_:
                    cnt += len(A_hu)
                    continue
                elif A_hu[0] > piv_:
                    continue
                left_, right_ = 0, len(A_hu)
                while right_ - left_ > 1:
                    if A_hu[(left_ + right_) // 2] <= piv_:
                        left_ = (left_ + right_) // 2
                    else:
                        right_ = (left_ + right_) // 2
                cnt += left_ + 1
            if cnt >= K:
                right = piv
            else:
                left = piv
        return right
    else:
        A_hu = [-1 * a for a in A_hu[::-1]]
        K -= n_hu + n_0
        left, right = 0, int(1e18) + 1
        while right - left > 1:
            piv = (left + right) // 2
            cnt = 0
            for a in A_sei:
                piv_ = decimal.Decimal(piv) / decimal.Decimal(a)
                if A_sei[-1] <= piv_:
                    cnt += len(A_sei) - 1
                    continue
                elif A_sei[0] > piv_:
                    continue
                left_, right_ = 0, len(A_sei)
                while right_ - left_ > 1:
                    if A_sei[(left_ + right_) // 2] <= piv_:
                        left_ = (left_ + right_) // 2
                    else:
                        right_ = (left_ + right_) // 2
                cnt += left_ + 1 - (a <= piv_)
            for a in A_hu:
                piv_ = decimal.Decimal(piv) / decimal.Decimal(a)
                if A_hu[-1] <= piv_:
                    cnt += len(A_hu) - 1
                    continue
                elif A_hu[0] > piv_:
                    continue
                left_, right_ = 0, len(A_hu)
                while right_ - left_ > 1:
                    if A_hu[(left_ + right_) // 2] <= piv_:
                        left_ = (left_ + right_) // 2
                    else:
                        right_ = (left_ + right_) // 2
                cnt += left_ + 1 - (a <= piv_)
            cnt = cnt // 2
            if cnt >= K:
                right = piv
            else:
                left = piv
        return right


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

main()

Submission status: Runtime Error

Solution code:
import decimal

def solve_gutyoku(N, K, A):
    A_combinations = []
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            A_combinations.append(A[i] * A[j])
    ans = sorted(A_combinations)[K-1]
    return ans


def solve(N, K, A):
    for i, a in enumerate(A):
        if a >= 0:
            break
    for j, a in enumerate(A):
        if a > 0:
            break
    A_hu = A[:i]
    A_0 = A[i:j]
    A_sei = A[j:]
    n_hu = len(A_hu)*len(A_sei)
    n_0 = len(A_0)*(len(A)-1) - len(A_0)*(len(A_0)-1)//2
    n_sei = (len(A_sei) - 1) * len(A_sei) // 2 + \
        (len(A_hu) - 1) * len(A_hu) // 2
    if K > n_hu and K <= n_hu + n_0:
        return 0
    elif K <= n_hu:
        left, right = int(-1 * 1e18), 0
        while right - left > 1:
            piv = (left + right) // 2
            cnt = 0
            for a in A_sei:
                piv_ = piv / a
                if A_hu[-1] <= piv_:
                    cnt += len(A_hu)
                    continue
                elif A_hu[0] > piv_:
                    continue
                left_, right_ = 0, len(A_hu)
                while right_ - left_ > 1:
                    if A_hu[(left_ + right_) // 2] <= piv_:
                        left_ = (left_ + right_) // 2
                    else:
                        right_ = (left_ + right_) // 2
                cnt += left_ + 1
            if cnt >= K:
                right = piv
            else:
                left = piv
        return right
    else:
        A_hu = [-1 * a for a in A_hu[::-1]]
        K -= n_hu + n_0
        left, right = 0, int(1e18) + 1
        while right - left > 1:
            piv = (left + right) // 2
            cnt = 0
            for a in A_sei:
                piv_ = decimal.Decimal(piv) / decimal.Decimal(a)
                if A_sei[-1] <= piv_:
                    cnt += len(A_sei) - 1
                    continue
                elif A_sei[0] > piv_:
                    continue
                left_, right_ = 0, len(A_sei)
                while right_ - left_ > 1:
                    if A_sei[(left_ + right_) // 2] <= piv_:
                        left_ = (left_ + right_) // 2
                    else:
                        right_ = (left_ + right_) // 2
                cnt += left_ + 1 - (a <= piv_)
            for a in A_hu:
                piv_ = decimal.Decimal(piv) / decimal.Decimal(a)
                if A_hu[-1] <= piv_:
                    cnt += len(A_hu) - 1
                    continue
                elif A_hu[0] > piv_:
                    continue
                left_, right_ = 0, len(A_hu)
                while right_ - left_ > 1:
                    if A_hu[(left_ + right_) // 2] <= piv_:
                        left_ = (left_ + right_) // 2
                    else:
                        right_ = (left_ + right_) // 2
                cnt += left_ + 1 - (a <= piv_)
            cnt = cnt // 2
            if cnt >= K:
                right = piv
            else:
                left = piv
        return right


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    ans = solve(N, K, A)
    print(ans)
    A_combinations = []
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            A_combinations.append(A[i] * A[j])


main()

Submission status: Runtime Error

Solution code:
from itertools import combinations

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

    a = map(int,input().split())

    combi = combinations(a,2)

    def kakeru(n):
        return n[0]*n[1]

    pairs = list(map(kakeru,combi))

    pairs_sort = pairs.sort()

    print(pairs_sort[k-1])
    
main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

def main():
    n, k = map(int, input().split())
    A = [int(x) for x in input().split()]
    list_m = list()
    list_0 = list()
    list_p = list()
    a_cnt_m = 0
    a_cnt_0 = 0
    a_cnt_p = 0
    cnt_m = 0
    cnt_0 = 0
    cnt_p = 0
    for a in A:
        if a < 0:
            list_m.append(a)
            a_cnt_m += 1
        elif a == 0:
            list_0.append(a)
            a_cnt_0 += 1
        else:
            list_p.append(a)
            a_cnt_p += 1
    # 掛け算の結果負の数
    cnt_m = a_cnt_m * a_cnt_p
    # 掛け算の結果0の数
    cnt_0 = a_cnt_0 * (a_cnt_m+a_cnt_p) + int(a_cnt_0*(a_cnt_0-1)/2)
    list_ans = list()
    if k <= cnt_m:
        for i in list_m:
            for j in list_p:
                list_ans.append(i*j)
        list_ans_s = sorted(list_ans)
        print(list_ans_s[k])
    elif cnt_0 > 0 and k <= cnt_m + cnt_0:
        print(0)
        exit()
    elif k > cnt_m + cnt_0:
        for idx_i, i in enumerate(list_p):
            for idx_j, j in enumerate(list_p):
                if idx_i < idx_j:
                    list_ans.append(i*j)
        cnt = 0
        for idx_i, i in enumerate(list_m):
            for idx_j, j in enumerate(list_m):
                if idx_i < idx_j:
                    list_ans.append(i*j)
                    cnt += 1
            list_ans_s = sorted(list_ans)
        print(list_ans_s[k - (cnt_m + cnt_0)-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

def main():
    n, k = map(int, input().split())
    A = [int(x) for x in input().split()]
    list_m = list()
    list_0 = list()
    list_p = list()
    a_cnt_m = 0
    a_cnt_0 = 0
    a_cnt_p = 0
    cnt_m = 0
    cnt_0 = 0
    cnt_p = 0
    for a in A:
        if a < 0:
            list_m.append(a)
            a_cnt_m += 1
        elif a == 0:
            list_0.append(a)
            a_cnt_0 += 1
        else:
            list_p.append(a)
            a_cnt_p += 1
    print('n', n)
    print('k', k)
    print(a_cnt_m, a_cnt_0, a_cnt_p)
    # 掛け算の結果負の数
    cnt_m = a_cnt_m * a_cnt_p
    # 掛け算の結果0の数
    cnt_0 = a_cnt_0 * (a_cnt_m+a_cnt_p) + int(a_cnt_0*(a_cnt_0-1)/2)
    list_ans = list()
    if k <= cnt_m:
        for i in list_m:
            for j in list_p:
                list_ans.append(i*j)
        list_ans_s = sorted(list_ans)
        print(k)
        print(list_ans_s[k])
    elif cnt_0 > 0 and k <= cnt_m + cnt_0:
        print(0)
        exit()
    elif k > cnt_m + cnt_0:
        for idx_i, i in enumerate(list_p):
            for idx_j, j in enumerate(list_p):
                if idx_i < idx_j:
                    list_ans.append(i*j)
        print(len(list_ans))
        cnt = 0
        for idx_i, i in enumerate(list_m):
            for idx_j, j in enumerate(list_m):
                if idx_i < idx_j:
                    list_ans.append(i*j)
                    cnt += 1
        print(cnt)
        print(len(list_ans))
        list_ans_s = sorted(list_ans)
        print(k - (cnt_m + cnt_0))
        print(len(list_ans_s))
        print(list_ans_s[k - (cnt_m + cnt_0)-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
nk=input("").split(" ")
n=int(nk[0])
k=int(nk[1])
lisa=input("").split(" ")
def minas(k,und,up):
    cc=0
    tund=und
    tup=up.reverse
    un=len(und)-1
    up=len(up)-1
    while(cc<k):
        if(un>0 and up>0):
            if(tund[un]*tup[up-1]<tund[un-1]*tup[up]):
                up-=1
            else:
                un-=1
        elif(un==0):
            up-=1
        else:
            un-=1
        cc+=1
    print(tund[un]*tup[up])
def pls(k,und,up):
    mt=0
    ms=1
    pt=0
    ps=1
    mm=len(und)
    mu=len(up)
    print(1)
        
    
a=[]
pl=0
mi=0
zero=0
for i in lisa:
    a+=[int(i)]
    if(int(i)==0):
        zero+=1
    elif(int(i)>0):
        pl+=1
    else:
        mi+=1
a.sort()
if(mi*pl>=k):
    minas(k,a[:mi],a[mi+zero:])
elif(k-mi*pl-zero*(n-1)>=0):
    print(0)
else:
    pls(k-mi*pl-zero*(n-1),a[:mi],a[mi+zero:])