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:
N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

pos = []
for i in range(N):
  if len(pos) == 0 and 0 <= A[i]: pos.append(i)
  if len(pos) == 1 and 1 <= A[i]:
    pos.append(i)
    break

def f(x):
  res = 0
  
  r = 1
  for l in range(pos[0]):
    while r < N and x <= A[l] * A[r]: r += 1
    res += N - r
    if l + 1 == r: r += 1
  
  for l in range(pos[0], pos[1]):
    if 0 < x: res += N - (l + 1)
  
  r = N
  for l in range(pos[1], N):
    while l < r-1 and x <= A[l] * A[r-1]: r -= 1
    if l < r: res += r - (l+1)

  return res

l, r = -10**18, 10**18
while r - l > 1:
  mid = (l + r) // 2
  if f(mid) < K: l = mid
  else: r = mid
print(l)

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:
        if nu <= len(result)-1:
          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):
      for z in range(n-y-1):
        result[nu] = int(negnums[y]*negnums[y + z +1])
        nu += 1
    for y in range(p):
      for z in range(p-y-1):
        if nu <= len(result)-1:
          result[nu] = int(posnums[y]*posnums[y + z +1])
          nu += 1
    result.sort()
    print(result[order-1])

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
print(A_mi[0]*A_mi[1])

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
print(A_plu_rev[0]*A_plu_rev[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):
      for z in range(n-y-1):
        result[nu] = int(negnums[y]*negnums[y + z +1])
        nu += 1
    for y in range(p):
      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:
import numpy as np

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

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
readline = sys.stdin.readline

def count(A, B, x):
    N = len(A)
    M = len(B)
    res = 0
    r = -1
    for l in range(N):
        a = A[l]
        while r < M-1 and B[r+1]*a <= x:
            r += 1
        res += r+1
    return res

def count2(A, x):
    res = 0
    for a in A:
        if a*a <= x:
            res += 1
    return res
        

N, K = map(int, readline().split())
A = list(map(int, readline().split()))
Am = []
Ap = []

minus = 0
zero = 0
plus = 0
for a in A:
    if a < 0:
        minus += 1
        Am.append(-a)
    elif a == 0:
        zero += 1
    else:
        plus += 1
        Ap.append(a)

ms = minus*plus
zs = ms + zero*(minus+plus) + zero*(zero-1)//2

Am.sort()
Ap.sort()
Amr = Am[::-1]
Apr = Ap[::-1]

if K <= ms:
    K = ms+1-K
    ok = max(max(Am), max(Ap))**2
    ng = 0
    while abs(ok-ng)>1:
        med = (ok+ng)//2
        if count(Amr, Ap, med) >= K:
            ok = med
        else:
            ng = med
    ans = -ok
elif K <= zs:
    ans = 0
else:
    K -= zs
    ok = max(max(Am), max(Ap))**2
    ng = 0
    while abs(ok-ng)>1:
        med = (ok+ng)//2
        if (count(Amr, Am, med) + count(Apr, Ap, med) - count2(Am, med) - count2(Ap, med))//2 >= K:
            ok = med
        else:
            ng = med
    ans = ok

print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = A[-1]**2+1
l = A[0]*A[-1]-1
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu-1):
      j = max(i+1,cou)
      while True:
        if j==plu:
          cou=j
          num+=j-i-1
          break
        x = A_plu_rev[i]*A_plu_rev[j]
        if x<m:
          j+=1
        else:
          cou=j-1
          num+=j-i-1
          break
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    for i in range(0,mi-1):
      j = max(i+1,cou)
      while True:
        if j==mi:
          cou=j
          num+=j-i-1
          break
        x = A_mi[i]*A_mi[j]
        if x<m:
          j+=1
        else:
          cou=j-1
          num+=j-i-1
          break
      if num>=K:
        break
        
    if num>=K:
      r=m
    else:
      l=m
      
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    b = plu
    cou = 0
    for a in A_mi_rev:
      while True:
        if cou==b:
          num+=cou
          break
        x = a*A_plu_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r = m
    else:
      l = m
      
print(l)

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
    #print(M, count)
    if count < k:
        L = M
    else:
        H = M
if count == k:
    print(M)
else:
    print(M+1)

Submission status: Runtime Error

Solution code:
import numpy as np

# 標準入力の受け取り
N, K = [int(i) for i in input().split()]
A = np.array([int(i) for i in input().split()], dtype=np.int64)

outer = np.outer(A, A)

try:
    print(sorted(outer[np.triu_indices(N, k=1)])[K-1])

except:
    print(1)

Submission status: Runtime Error

Solution code:
import numpy as np

# 標準入力の受け取り
N, K = [int(i) for i in input().split()]
A = np.array([int(i) for i in input().split()], dtype=np.int64)

print(sorted(np.outer(A, A)[np.triu_indices(N, k=1)])[K - 1])

Submission status: Runtime Error

Solution code:
Q = list(map(int, input().split()))
N = Q[0]
K = Q[1]
A = list(map(int, input().split()))
B=[]
for i in range(N):
    for l in range(i+1,N):
        B.append(A[i]*A[l])
B=sorted(B)
print(B[K])

Submission status: Runtime Error

Solution code:
import numpy as np

# 標準入力の受け取り
N, K = [int(i) for i in input().split()]
A = np.array([int(i) for i in input().split()], dtype=np.int64)

sorted_ = sorted(np.outer(A, A)[np.triu_indices(N, k=1)].flatten())

print(sorted_[K - 1])

Submission status: Runtime Error

Solution code:
import numpy as np

# 標準入力の受け取り
N, K = [int(i) for i in input().split()]
A = np.array([int(i) for i in input().split()], dtype=np.int64)


sq = np.square(A)
# print("sq",sq)
sorted_2 = sorted(np.outer(A, A).flatten())
for i in sq:
    sorted_2.remove(i)
# print(sorted_2, len(sorted_2))
print(sorted_2[2 * K - 1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for i in range(N):
  for j in range(N):
    if i<j:
      B.append(A[i]*A[j])
C=sorted(B)
print(C[M])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

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]
    while H - L > 1:
        M = (H + L) // 2
        count = 0
        for x in u:
            #print(M, x, M // x)
            count += bisect_right(d, M // x)
        #print(L, H, count)
        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):
    print(0)
    exit()
print(a[10 ** 6])

Submission status: Runtime Error

Solution code:

import numpy as np

def main():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    A = np.array(A)
    A.sort()
    zero = np.count_nonzero(A==0)
    positive = A[A>0]
    negative = A[A<0]
    def count(x): # 積がx以下になるペアの個数を返す
        ans = 0
        if x >= 0:
            ans += N*zero
        ans += np.searchsorted(A, x//positive, side="right").sum()
        ans += N*len(negative) - np.searchsorted(A, -(-x//negative), side="left").sum()
        ans -= np.count_nonzero(A*A <= x) # 同じものはふたつ選べない
        return ans//2
    ok = 10**8
    ng = -ok-1
    while ok-ng>1:
        cur = (ok+ng)//2
        if count(cur)>=K:
            ok = cur
        else:
            ng = cur
    print(int(ok))


    
if __name__ == "__main__":
    main()

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[:bisect_left(A, 0)]
pos = A[bisect_right(A, 0):]

all_pairs = N * (N-1) // 2
neg_pairs = len(neg) * len(pos)
pos_pairs = len(pos) * (len(pos)-1) // 2 + len(neg) * (len(neg)-1) // 2
zero_pairs = all_pairs - neg_pairs - pos_pairs

mi = []
ma = []
if neg_pairs >= 2:
    mi.append(neg[-2] * neg[-1])
    ma.append(neg[0] * neg[1])
if zero_pairs > 0:
    mi.append(0)
    ma.append(0)
if pos_pairs >= 2:
    mi.append(pos[0] * pos[1])
    ma.append(pos[-2] * pos[-1])
if pos_pairs > 0 and neg_pairs > 0:
    mi.append(pos[-1] * neg[0])

def cnt(x):
    res = 0
    if x < 0:
        for ne in neg:
            res += len(pos) - bisect_left(pos, (x +ne+1)// ne)
    elif x == 0:
        res = neg_pairs + zero_pairs
    else:
        for po in pos:
            i = bisect_right(pos, x // po)
            if i > 0:
                res += i - (po <= pos[i-1]) 
        for ne in neg:
            i = bisect_right(neg, x // ne)
            if len(neg) - i > 0:
                res += len(neg) - i - (ne >= neg[i]) 
        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:
n, k = map(int, input().split(" "))
num = list(map(int, input().split(" "))).sort()
p_num = [i for i in num if i > 0]
zero_num = [i for i in num if i == 0]
n_num = [i for i in num if i < 0]
positive = len(p_num)*(len(p_num)-1)+len(n_num)*(len(n_num)-1)
zero =  len(zero_num)*(len(p_num)+len(n_num))
negative=len(n_num)*len(p_num)
if k - negative <= 0:
    multiplication_list = [i * j for i in n_num for j in n_num]
    multiplication_list.sort()
    print(multiplication_list[k-1])
elif k - n_num - zero <= 0:
    print(0)
else:
    idx = k - n_num - zero
    multiplication_list_1 = [p_num[i] * p_num[j] for i in range(len(p_num)) for j in range(i+1,len(p_num))]
    multiplication_list_2 = multiplication_list = [n_num[i] * n_num[j] for i in range(len(n_num)) for j in range(i+1,len(n_num))]
    multiplication_list = multiplication_list_1 + multiplication_list_2
    multiplication_list.sort()
    print(multiplication_list[idx])

Submission status: Runtime Error

Solution code:
import itertools as it
from scipy.special import comb
N,K=map(int,input().split())
A=list(map(int,input().split()))

m=[]
z=[]
p=[]

for i in A:
    if i<0:
        m.append(i)
    elif i==0:
        z.append(i)
    else:
        p.append(i)
if len(m)*len(p)>=K:
    A=list(it.combinations(m+p,2))
    B=sorted(A,reverse=True)
    print(B[K-1][0]*B[K-1][1])
elif len(m)*len(p)<K and len(m)*len(p)+(len(m)+len(p))*len(z)+comb(len(z),2,exact=True)>=K:
    print(0)
else:
    k=K-1-(len(m)*len(p))-(len(m)+len(p))*len(z)+comb(len(z),2,exact=True)
    A=list(it.combinations(-1*m,2))+list(it.combinations(p,2))
    B=sorted(A)
    #print(B[k][0]*B[k][1])
    #print((len(m)*len(p))+(len(m)+len(p))*len(z)+comb(len(z),2,exact=True))
    print(len(A))
    print(k)
    print(comb(N,2))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right


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

nega = bisect_left(A, 0)
posi = N - bisect_right(A, 0)
zero = N - nega - posi

numNega = nega * posi
numZero = (nega + posi) * zero + zero * (zero - 1) // 2
numPosi = N * (N - 1) // 2 - numNega - numZero

Nega = A[:nega]
Posi = A[N - posi:]


def negaCnt(n):
    rst = 0
    for a in Nega:
        b = n // a
        idx = bisect_right(Posi, b)
        rst += posi - idx
    return rst


def posiCnt(n):
    rst = 0
    for i, a in enumerate(Posi):
        b = (n + a - 1) // a
        idx = bisect_left(Posi, b, i + 1)
        rst += idx - (i + 1)
    for i, a in enumerate(Nega):
        b = (n + a - 1) // a
        idx = bisect_left(Nega, b, i + 1)
        rst += idx - (i + 1)
    return rst


if K <= numNega:
    # [ok, ng) - Maximum
    # (ng, ok] - Minimum
    # ok が 最終的な答え
    ok = Nega[0] * Posi[0]
    ng = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if negaCnt(mid) < K:
            ok = mid
        else:
            ng = mid
    ans = ok
elif numNega < K <= numNega + numZero:
    ans = 0
else:
    K2 = K - numNega - numZero
    Nega = [-x for x in reversed(Nega)]
    ok = 0
    ng = max(Nega[-1] ** 2, Posi[-1] ** 2) if nega > 0 else Posi[-1] ** 2
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if posiCnt(mid) < K2:
            ok = mid
        else:
            ng = mid
    ans = ok

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def cnt(x,A,An,Ap,N,Nz):
    res = 0
    if x >= 0:
        res += N * Nz
    res += np.searchsorted(A,x//Ap,side='right').sum()
    res += N * len(An) - np.searchsorted(A,-(-x//An),side='left').sum()
    res -= np.count_nonzero(A*A<=x)
    return res//2


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

    print(len(A))

    A = np.array(A)
    A.sort()

    An = A[A<0]
    Az = A[A==0]
    Ap = A[A>0]

    Nz = np.count_nonzero(A==0)

    INF = 10 ** 18

    l = - INF - 1
    r = INF + 1

    while r-l > 1:
        m = (l+r)//2
        if cnt(m,A,An,Ap,N,Nz) >= K:
            r = m
        else:
            l = m

    print(r)





main()

Submission status: Runtime Error

Solution code:
# 1行目は入力ワード数、検索するindex
# 値が2行に空白を挟んで羅列、総当たりで掛け算し小さい順に並べたindex番目(1番目、2番目、…)を出力

import numpy as np

def check(num, input_list):
    multi_list = []
    input_list_np = np.array(input_list)
    
    multi_list_np = input_list_np * input_list_np.reshape(num, 1)
    
    # for i in range(num):
    #     for j in range(i + 1, num):
    #         multi_list.append(multi_list_np[i,j])
            
    multi_list = [multi_list_np[i,j] for i in range(num) for j in range(i+1, num)]

    multi_list.sort()
    return multi_list

if __name__ == '__main__':
    num, index = input().split()
    num = int(num)
    index = int(index)
    input_list = [int(a) for a in input().split()]

    check(num, input_list)
    print(check(num, input_list)[index - 1])

Submission status: Runtime Error

Solution code:
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0
    j = 0
    for a in neg:
        d = m // a
        j = bisect(pos, d, lo=j)
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    less = 0
    j = 0
    for i in range(len_pos - 1, 0, -1):
        a = pos[i]
        d = m // a
        j = bisect(pos, d, lo=j, hi=i)
        less += j
    for i in range(len_neg - 1, 0, -1):
        a = neg[i]
        d = m // a
        j = bisect(neg, d, lo=j, hi=i)
        less += j
    return less < k


def solve(n, k, aaa):
    pos = [a for a in aaa if a > 0]
    neg = [a for a in aaa if a < 0]
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        raise RuntimeError
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg):
                l = m
            else:
                r = m
        return r


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

Submission status: Runtime Error

Solution code:
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0
    j = 0
    for a in neg:
        d = m / a
        j = bisect(pos, d, lo=j)
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    raise RuntimeError
    less = 0
    j = 0
    for i in range(len_pos - 1, 0, -1):
        a = pos[i]
        d = m // a
        j = bisect(pos, d, lo=j, hi=i)
        less += j
    for i in range(len_neg - 1, 0, -1):
        a = neg[i]
        d = m // a
        j = bisect(neg, d, lo=j, hi=i)
        less += j
    return less < k


def solve(n, k, aaa):
    pos = [a for a in aaa if a > 0]
    neg = [a for a in aaa if a < 0]
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg):
                l = m
            else:
                r = m
        return r


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

Submission status: Runtime Error

Solution code:
# 1行目は入力ワード数、検索するindex
# 値が2行に空白を挟んで羅列、総当たりで掛け算し小さい順に並べたindex番目(1番目、2番目、…)を出力

import numpy as np

def check(num, input_list):
    multi_list = []
    input_list_np = np.array(input_list)
    
    multi_list_np = input_list_np * input_list_np.reshape(num, 1)
    
    for i in range(num):
        for j in range(i + 1, num):
            multi_list.append(multi_list_np[i,j])

    multi_list.sort()
    return multi_list

if __name__ == '__main__':
    num, index = input().split()
    num = int(num)
    index = int(index)
    input_list = [int(a) for a in input().split()]

    check(num, input_list)
    print(check(num, input_list)[index - 1])

Submission status: Runtime Error

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

P = [a for a in A if a > 0]
Z = [a for a in A if a == 0]
M = [a for a in A if a < 0]

P.sort()
Z.sort()
M.sort(reverse=True)

minus_count = len(P) * len(M)
zero_count = len(Z) * (len(P)+len(M))
if len(Z) >= 2:
    zero_count += (len(Z) * (len(Z)-1)) // 2

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

while left + 1 < right:
    num = (left + right) // 2
    count = 0

    if num >= 0:
        count += zero_count + minus_count

        limit_idx = len(P)-1
        for idx, p in enumerate(P):
            pair = num / p
            while P[limit_idx] > pair and limit_idx > idx:
                limit_idx -= 1

            pattern = limit_idx - idx
            if pattern == 0:
                break
            count += pattern

        limit_idx = len(M) - 1
        for idx, m in enumerate(M):
            pair = num / m
            while M[limit_idx] < pair and limit_idx > idx:
                limit_idx -= 1

            pattern = limit_idx - idx
            if pattern == 0:
                break
            count += pattern

    elif num < 0:
        for idx, p in enumerate(P):
            pair = num / p

            limit_idx = len(M) - 1
            while M[limit_idx] <= pair and limit_idx >= 0:
                limit_idx -= 1

            pattern = len(M) - limit_idx - 1
            count += pattern

    if count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Runtime Error

Solution code:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(np.outer(a,a))
c=sorted([b[i][j] for i in range(n) for j in range(n) if i<j],reverse=False)
print(c[k-1])

Submission status: Runtime Error

Solution code:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(np.outer(a,a))
c=sorted([b[i][j] for i in range(n) for j in range(n) if i<j])
print(c[k-1])

Submission status: Runtime Error

Solution code:
#from math import sqrt
from heapq import heappush, heappop
#from collections import deque

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

ary1 = []
ary2 = []
ary3 = []

for v in input().split():
    v = int(v)
    if v > 0:
        ary1.append(v)
    elif v < 0:
        ary3.append(v)
    else:
        ary2.append(v)

l1 = len(ary1)
l2 = len(ary2)
l3 = len(ary3)


n1 = l1 * (l1 - 1) // 2 + l3 * (l3 - 1) // 2
n2 = l2 * (l1 + l3) + l2 * (l2 - 1) // 2
n3 = l1 * l3


def search1(ary1, ary2):
    q = []
    l = len(ary1)
    for i in range(l-1):
        v1 = ary1[i]
        for j in range(i+1, l):
            v2 = ary1[j]
            heappush(q, v1 * v2)

    l = len(ary2)
    for i in range(l-1):
        v1 = ary2[i]
        for j in range(i+1, l):
            v2 = ary2[j]
            heappush(q, v1 * v2)
    return q


def search2(ary1, ary2):
    q = []
    len1 = len(ary1)
    len2 = len(ary1)
    for i in range(len1):
        v1 = ary1[i]
        for j in range(len2):
            v2 = ary2[j]
            heappush(q, v1 * v2)
    return q


if k < n3:
    # nega
    q = search2(ary1, ary3)
elif k < n3 + n2:
    print("0")
    exit()
else:
    # posi
    q = search1(ary1, ary3)

    k = k - n3 - n2

i = 0
while i < k:
    v = heappop(q)
    i += 1
print(v)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A = list(map(int,input().split()))
B =[0]*(N*(N-1)//2)
c=0
for k in range(N-1):
    for m in range(k+1,N):
        d = c+m-k-1
        B[d] = A[k]*A[m]
    c = c+(N-k)-1
sorted(B)
print(B[K-1])

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 = []
ans_extend = ans.extend

for i in range(N-1):
    ans_extend(m[i,i+1:])


ans.sort()   

print(ans[K-1])

Submission status: Runtime Error

Solution code:
a = input().split()
a,b = map(int, a)
c = list(input().split())
c = list(map(int, c))
e = []
for i in range(b):
    for l in range(b):
            if i < l:
                if l < a:
                    product = c[i]*c[l]
                    e.append(product)
e.sort()
print(e[b-1])

Submission status: Runtime Error

Solution code:
import bisect
from copy import deepcopy

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

negs=[]
poss=[]
zers=[]
for i in range(n):
    if A[i]<0:
        negs.append(A[i])
    elif A[i]>0:
        poss.append(A[i])
    else: zers.append(A[i])

pairedpos=len(negs)*(len(negs)-1)/2+len(poss)*(len(poss)-1)/2
pairedneg=len(negs)*len(poss)
pairedzero=(len(negs)+len(poss))*len(zers)+len(zers)*(len(zers)-1)/2

ans=0
flg=0
if k<=pairedneg:
    flg=1
elif pairedneg<k<=pairedneg+pairedzero:
    ans=0
else: flg=2 

if flg==1:
    higher=0
    lower=-(1e+9)**2+1
    while abs(higher-lower)>1:
        cnt=0
        mid=int((higher+lower)//2)
        for i in range(len(poss)):
            idx=bisect.bisect_left(negs, -(-mid//poss[i]))
            cnt+=idx
        if cnt<=k-1:
            lower=mid
        else:
            higher=mid
    ans=lower

elif flg==2:
    lower=0
    higher=(1e+9)**2+1
    newnegs=[-negs[i] for i in range(len(negs))]
    newnegs=sorted(newnegs)
    while abs(higher-lower)>1:
        cnt=0
        mid=int((higher+lower)//2)
        for i in range(len(newnegs)):
            idx1=bisect.bisect_left(newnegs[i+1:], -(-mid//newnegs[i]))
            cnt+=idx1
        for j in range(len(poss)):
            idx2=bisect.bisect_left(poss[j+1:], -(-mid//poss[j]))
            cnt+=idx2
        if cnt<=(k-pairedneg-pairedzero)-1:
            lower=mid
        else:
            higher=mid
    ans=lower
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

  def calc():
  n,k=map(int,input().split())
  arr=list(map(int,input().split()))
  arr=sorted(arr)
  nc=0
  zc=0
  pc=0
  for i in range(n):
    if arr[i]<0:
      nc+=1
    elif arr[i]==0:
      zc+=1
    else:
      pc+=1
  ncc=nc*pc
  zcc=zc*(nc+pc)+(zc*(zc-1))//2
  pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
  if k<=ncc:
    arr1=[]
    arr2=[]
    for i in range(n):
      if arr[i]<0:
        arr1.append(-arr[i])
      elif arr[i]>0:
        arr2.append(arr[i])
    arr1=arr1[::-1]
    c1=len(arr1)
    c2=len(arr2)
    k=ncc-k
    l=0
    r=10**18+1
    while r-l!=1:
      mid=(l+r)//2
      cnt=0
      for i in range(c1):
        cnt+=bisect.bisect_right(arr2,mid//arr1[i])
      if cnt>k:
        r=mid
      else:
        l=mid
    print(-r)
  elif k<=(ncc+zcc):
    print(0)
  else:
    arr1=[]
    arr2=[]
    for i in range(n):
      if arr[i]<0:
        arr1.append(-arr[i])
      elif arr[i]>0:
        arr2.append(arr[i])
    arr1=arr1[::-1]
    c1=len(arr1)
    c2=len(arr2)
    l=0
    r=10**18+1
    k-=(ncc+zcc)
    while r-l!=1:
      mid=(l+r)//2
      cnt1=0
      for i in range(c1):
        tmp=bisect.bisect_right(arr1,mid//arr1[i])
        if arr1[i]**2<mid:
          tmp-=1
        cnt1+=tmp
      cnt1=cnt1//2
      cnt2=0
      for i in range(c2):
        tmp=bisect.bisect_right(arr2,mid//arr2[i])
        if arr2[i]**2<mid:
          tmp-=1
        cnt2+=tmp
      cnt2=cnt2//2
      cnt=cnt1+cnt2
      if cnt>=k:
        r=mid
      else:
        l=mid
    print(r)
calc()