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:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    ans = - 10**18

    from bisect import bisect_left, bisect_right


    N, K = LMIIS()
    A = LMIIS()
    A.sort()
    num_negative = bisect_left(A,0)
    num_zero = bisect_right(A,0) - num_negative
    num_positive = N - num_negative - num_zero
    
    inf = 10**18+1
    u = inf
    l = -inf
    # 答えが負
    if num_negative * num_positive >= K:
        def g(i,x):
            up = N
            lp = num_negative + num_zero
            max_m = -1
            mp = (up+lp)//2
            while up-lp > 1:
                mp = (up+lp)//2
                if A[i] * A[mp] < x:
                    lp = mp
                    max_m = max(max_m,mp)
                else:
                    up = mp
            # if amm * A[mp] < x:
            #     max_m = max(max_m,mp)
            # print(amm,x,max_m,num_negative + num_zero,mp)
            return max(max_m - (num_negative + num_zero-1),0)
            

        def f(x):
            ans = 0
            for i in range(num_negative):
                ans += g(i,x)
            return ans

        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if f(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        m = (u+l)//2
        if f(m) >= K:
            u = m
        else:
            l = m
            max_m = max(max_m,m)
        print(max_m)
        return max_m

    # 答えがゼロ
    elif num_negative * num_positive + num_negative * num_zero + num_positive * num_zero + num_zero*(num_zero-1)//2 >= K:
        print(0)
        return

    # 答えが正
    else:
        assert(False)
        K -= num_negative * num_positive +\
             num_negative * num_zero +\
             num_positive * num_zero + num_zero*(num_zero-1)//2

        def f(i,x):
            # u = num_negative
            u = i
            l = 0
            min_m = N
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    u = m
                    min_m = min(min_m,m)
                else:
                    l = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                    min_m = min(min_m,m)

            # ans = num_negative - min_m
            ans = i - min_m
            # if i >= min_m:
            #     ans -= 1 
            ans = max(ans,0)
            #print('f(',x,')=',ans, num_negative, min_m, i,A[0]*A[i]<x)
            return ans

        def g(i,x):
            u = N
            # l = num_negative + num_zero
            l = i+1
            max_m = num_negative + num_zero -1
            m = (u+l)//2
            while u-l > 1:
                m = (u+l)//2
                if A[i] * A[m] < x:
                    l = m
                    max_m = max(max_m,m)
                else:
                    u = m
            m = (u+l)//2
            if A[i] * A[m] < x:
                max_m = max(max_m,m)
            
            
            # ans = max_m - num_negative - num_zero +1
            ans = max_m - i
            
            # if i <=max_m :
            #     ans -= 1 
            ans = max(ans,0)
            #print('g(',x,')=',ans,max_m,num_negative+num_zero,'A[i]=',A[i])
            
            return ans
            
        def h(x):
            ans = 0
            for i in range(1,num_negative):
                ans += f(i,x)
            preans = ans
            
            for i in range(num_negative+num_zero,N-1):
                ans += g(i,x)
            #print('h(',x,')=',ans,'K=',K)
            # print('neg*neg=',preans,'pos*pos=',ans-preans)
            return ans
        





        max_m = -inf
        while u-l > 1:
            m = (u+l)//2
            if h(m) >= K:
                u = m
            else:
                l = m
                max_m = max(max_m,m)
        # m = (u+l)//2
        # if f(m) >= K:
        #     u = m
        # else:
        #     l = m
        #     max_m = max(max_m,m)
        #print('ans=',max_m,448283280358331064-max_m)
        # print(h(87940638538504704))
        print(max_m)
        return max_m




if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

if N*(N-1)/(2*2) >= K:
    mylist = [10**9*10**9] * K
    A.sort()
    for num1 in range(N-1):
        for num2 in range(N-(num1+1)):
            res_multi = A[num1] * A[num1 + (num2 + 1)]
            if res_multi < mylist[-1]:
                mylist[-1] = res_multi
                mylist.sort()
            else:
                break
else:
    mylist = [-10**9*10**9] * int((N*(N-1)/2-K+1))
    A.sort(reverse=True)
    for num1 in range(N-1):
        for num2 in range(N-(num1+1)):
            res_multi = A[num1] * A[num1 + (num2 + 1)]
            if res_multi > mylist[-1]:
                mylist[-1] = res_multi
                mylist.sort(reverse=True)
            else:
                break

print(mylist[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    N,K = map(int, input().split())
    A = np.array(sorted([int(i) for i in input().split()]))

    zero_left = np.searchsorted(A, 0, side='left')
    zero_right = np.searchsorted(A, 0, side='right')

    negative = zero_left
    positive = N - zero_right
    zero = zero_right - zero_left
    non_posi = negative * positive + zero * (N - zero) + zero * (zero - 1) // 2

    if K <= negative * positive:
        Nega = A[:zero_left]
        Posi = A[zero_right:]

        left = -(A[0]**2)
        right = 0
        while right - left > 1:
            x = (left + right) // 2
            count = np.searchsorted(Nega, x // Posi, side='right').sum()

            if count < K:
                left = x
            else:
                right = x

        print(right)

    elif K <= non_posi:
        print(0)

    else:
        Nega = np.sort(np.abs(A[:zero_left]))
        Posi = A[zero_right:]

        left = 0
        right = Posi[-1]**2
        while right - left > 1:
            x = (left + right) // 2
            A = np.searchsorted(Nega, x // Nega, side='right')
            B = np.searchsorted(Posi, x // Posi, side='right')
            count = 0
            count += A.sum()
            count += B.sum()
            count -= np.int_(np.where(A >= np.arange(1,negative+1), True, False)).sum()
            count -= np.int_(np.where(B >= np.arange(1,positive+1), True, False)).sum()
            count //= 2

            if count + non_posi < K:
                left = x
            else:
                right = x

        print(right)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = list(map(int, input().split()))
x = np.asarray(list(map(int, input().split())), dtype = int)
x = np.tile(x, (len(x), 1)).T * x
#print(np.tril(np.ones((len(x), len(x)), dtype=int), k=-1))
x[np.tril(np.ones((len(x), len(x)), dtype=int), k=0)==1] = np.iinfo(int).max
x = x.flatten()
x.sort()
#print(x.shape)
print(x[k-1])
#print(x)

Submission status: Runtime Error

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

# 組み合わせの計算
def combination(x):
    return int((x * (x - 1)) / 2)

# 組み合わせのリストを作成
def list_conbination(l):
    list_c = []
    l_length = len(l)
    
    if l_length <= 1:
        return list_c
    
    for i in range(l_length):
        n = i + 1
        while n < l_length:
            list_c.append(l[i] * l[n])
            n += 1
    
    return list_c

# 負,0,正のリストを作成
minus = []
zero = []
plus = []
for i in a:
    if i < 0:
        minus.append(i)
    elif i == 0:
        zero.append(i)
    else:
        plus.append(i)

# 負,0,正の個数
minus_num = len(minus)
zero_num = len(zero)
plus_num = len(plus)

# 積が負,0,正になる個数
minus_ans_num = minus_num * plus_num
zero_ans_num = minus_num * zero_num + plus_num * zero_num + combination(zero_num)
plus_ans_num = combination(minus_num) + combination(plus_num)

# 小さい順に並べて、K番目の数値を出力(負,0,正の順番で判定)
if minus_ans_num > k: #Kが負の範囲
    ans = []
    for m in minus:
        for p in plus:
            ans.append(m * p)
    ans.sort()
    print(ans[k - 1])
elif minus_ans_num + zero_ans_num > k: # Kが0の範囲
    print(0)
else: #Kが正の範囲
    ans = list_conbination(minus) + list_conbination(plus)
    ans.sort()
    print(ans[k - minus_ans_num - zero_ans_num - 1])

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A_minus,A_zero,A_plus=[],[],[]
    x=bisect_left(A,0)
    y=bisect_right(A,0)
    A_minus=A[:x]
    A_minus=list(reversed(list(map(lambda x: -x,A_minus))))
    A_zero=A[x:y]
    A_plus=A[y:]
    if K<=len(A_minus)*len(A_plus):
        def nibutan1(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve1(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve1(mid):
            c=0
            z=bisect_right(A_plus,mid//A_minus[0])
            c+=z
            for x in A_minus[1:]:
                if z<len(A_minus) and A_plus[z-1] < mid//x:
                    while z<len(A_minus) and A_plus[z-1] < mid//x:
                        z+=1
                c+=z
            if c>=K:
                return True
            else:
                return False
        
        print(-nibutan1(10**18+1,0))
    K-=len(A_minus)*len(A_plus)
    if 0<K<=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2:
        print(0)
    K-=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2
    if K>0:
        def nibutan2(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve2(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve2(mid):
            c=0
            if len(A_minus)>1:
                z=bisect_right(A_minus,mid//A_minus[0])
                c+=z
                if mid//A_minus[0]>=A_minus[0]:
                    c-=1
                for x in A_minus[1:]:
                    if z>0 and A_minus[z-1] > mid//x:
                        while z>0 and A_minus[z-1] > mid//x:
                            z-=1
                    c+=z
                    if mid//x>=x:
                        c-=1
            if len(A_plus)>1:
                z=bisect_right(A_plus,(mid//A_plus[0]))
                c+=z
                if (mid//A_plus[0])>=A_plus[0]:
                    c-=1
                for x in A_plus[1:]:
                    if z>0 and A_plus[z-1] > mid//x:
                        while z>0 and A_plus[z-1] > mid//x:
                            z-=1
                    c+=z
                    if mid//x>=x:
                        c-=1
            c//=2
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan2(10**18+1,0))

    
        
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def count_pair(A, x, K):
    # A内のペアで積がxより小さいものの個数がK未満ならTrueを返す
    cnt = 0
    N = len(A)
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            m = N-1
            while A[m] > y and m > n:
                cnt += 1
                m -= 1
                if cnt >= K:
                    return False
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            m = n + 1
            while A[m] < y and m < N:
                cnt += 1
                m += 1
                if cnt >= K:
                    return False
        elif x > 0:
            cnt += N - (n + 1)
            if cnt >= K:
                return False
    return True


def main():
    # count_pair(x)<Kをみたすxの最大値を求める
    N, K = map(int, input().split())
    * A, = map(int, input().split())
    A.sort()
    inf = 10**18+1
    l, r = -inf, inf
    for _ in range(inf):
        if r - l <= 1:
            print(l)
            exit()
        c = (l + r) // 2
        if count_pair(A, c, K):
            l = c
        else:
            r = c


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)

if num_minus_pair > K:
  th = -5
  while 1:
    count = 0
    pair_val_set = []
    for i in range(num_minus):
      for j in range(num_plus):
        val = A[i]*A[num_minus+num_zero+j]
        if val < th:
          pair_val_set.append(val)
          count += 1
        else:
          break
    if count >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif count < K:
      th /= 2
elif num_minus_pair+num_zero_pair > K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair > K:
  th = 5
  K = K - (num_minus_pair + num_zero_pair)
  while 1:
    count = 0
    pair_val_set = []
    for i in range(num_minus):
      for j in range(i+1,num_minus):
        val = A[i]*A[j]
        if val < th:
          pair_val_set.append(val)
          count += 1
        else:
          break
    for i in range(num_plus):
      for j in range(i+1,num_plus):
        val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
        if val < th:
          pair_val_set.append(val)
          count += 1
        else:
          break
    if count >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif count < K:
      th = th + th/2

Submission status: Runtime Error

Solution code:
import math
import itertools
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,k=map(int,input().split())
a=list(map(int, input().split()))
a=sorted(a)
mlist=[]
zlist=[]
plist=[]
for i in a:
  if i<0:
    mlist.append(i)
  elif i==0:
    zlist.append(i)
  else:
    plist.append(i)
mnum=len(mlist)
znum=len(zlist)
pnum=len(plist)
mans=mnum*pnum
zans=znum*(pnum+mnum)
if znum>=2:
  zans+=combinations_count(znum,2)
pans=0
if pnum>=2:
  pans+=combinations_count(pnum,2)
if mnum>=2:
  pans+=combinations_count(mnum,2)

if k<mans:
  ans=[]
  l=mlist[0]*plist[-1]
  r=mlist[-1]*plist[0]
  while True:
    x=(l+r)//2
    c=0
    for m in mlist:
      for p in plist[::-1]:
        if m*p<x:
          c+=1
        else:
          break
    if c<k:
      l=x
    else:
      r=x
    if r==l+1:
      break
  print(l)
elif k<mans+zans:
  print(0)
else:
  k=k-(mans+zans)
  mlist=mlist[::-1]
  if mnum<2:
    l=plist[0]*plist[1]
    r=plist[-1]*plist[-2]
  elif pnum<2:
    l=mlist[0]*mlist[1]
    r=mlist[-1]*mlist[-2]
  else:
    if mlist[0]*mlist[1]<plist[0]*plist[1]:
      l=mlist[0]*mlist[1]
    else:
      l=plist[0]*plist[1]
    if mlist[-1]*mlist[-2]>plist[-1]*plist[-2]:
      r=mlist[-1]*mlist[-2]
    else:
      r=plist[-1]*plist[-2]
  #print(k)
  while True:
    x=(l+r)//2
    c=0
    max=0
    if mnum>=2:
      for i,m in enumerate(mlist[:-1]):
        for j in mlist[i:]:
          n=m*j
          if n<x:
            c+=1
            if n>=max:max=n
          else:
            break
    if pnum>=2:
      for i,p in enumerate(plist[:-1]):
        for j in plist[i:]:
          n=p*j
          if n<x:
            c+=1
            if n>=max:max=n
          else:
            break
    #print("c"+str(c))
    if c<k:
      l=x
      #print("l"+str(l))
    else:
      r=x
      #print("r"+str(r))
    if r==l+1:
      break
    if c==k:break
  print(l)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long LINF=1e18;

signed main(){
  cin>>n>>k;
  vector<int> v(n),w(n);
  for(int i=0;i<n;i++)cin>>v[i];
  for(int i=0;i<n;i++)w[i]=-v[i];
  sort(v.begin(),v.end());
  sort(w.begin(),w.end());
  int l=-LINF,r=LINF;
  while(r-l>1){
    int mid=(r+l)>>1,tmp=0;
    for(int i=0;i<n;i++){
      if(v[i]>0){
        int ll=-1,rr=n;
        while(rr-ll>1){
          int m=(rr+ll)>>1;
          if(v[i]*v[m]>mid)rr=m;
          else ll=m;
        }
        tmp+=rr;
        if(v[i]*v[i]<=mid)tmp--;
      }
      if(v[i]==0)if(mid>=0)tmp+=n-1;
      if(v[i]<0){
        int ll=-1,rr=n;
        while(rr-ll>1){
          int m=(rr+ll)>>1;
          if(v[i]*w[m]>mid)rr=m;
          else ll=m;
        }
        tmp+=rr;
        if(v[i]*v[i]<=mid)tmp--;
      }
    }
    if(tmp>=k*2)r=mid;
    else l=mid;
  }
  cout<<r<<endl;
}

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
result = []
for i in range(len(l)):
  for j in range(len(l)-i):
    try:
      result.append(l[i]*l[i+j+1])
    except:
      pass
print(sorted(result)[k])

Submission status: Runtime Error

Solution code:
import sys

n=sys.stdin.readline().rstrip()[::-1]
to=0
num=len(n)
m=0

for i in range(num):
    k=int(n[i])
    k+=m
    if k==5:
        if int(n[i+1])>=5:
            to+=10-k
            m=1
        else:
            to+=k
            m=0
    if k<5:
        to+=k
        m=0
    elif k>5:
        to+=10-k
        m=1
        if i==num-1:
            to+=1
        
print(to)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
result = []
for i in range(len(l)):
  for j in range(5-i):
    result.append(l[i]*l[j])
print(sorted(result)[k])

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

n,k,*a=map(int,sys.stdin.readlines().split())
a=np.array(a,dtype=np.int64)

print(n,k,a)

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

print(np.searchsorted(a,0//pos,side='right').sum())

def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


left=-10**18
right=10**18

while left+1<right:
    x=(left+right)//2
    cnt=count(x)
    if cnt>=k:
        right=x
    if cnt<k:
        left=x

print(right)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = [int(e) for e in input().aplit()]
result = []
for i in range(n-1):
  for a in A[i+1:]:
    result.append(A[i]*a)
result.sort()
print(result[k-1])

Submission status: Runtime Error

Solution code:
import bisect

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

A.sort()

Nn = bisect.bisect_left(A,0)
Nz = bisect.bisect_left(A,1) - Nn
Np = N - Nn - Nz
An = A[:Nn]
Ap = A[Nn+Nz:]

if Nn*Np >= K:
    left = -10**18-1
    right = -1
    n = Nn*Np - K
    while left+1 < right:
        mid = (left + right) //2
        i = j = 0
        c = 0
        while i < Nn and j < Np:
            if An[i]*Ap[j] > mid:
                c += 1
                j += 1
                if j >= Np:
                    c += (Nn-1-i)*Np
            else:
                i += 1
            if c > n:
                break
        if c > n:
            left = mid
        else:
            right = mid
    ans = right
    print(ans)

elif Nn*Np + Nz*(Nn+Np) + Nz*(Nz-1)//2 >= K:
    ans = 0
    print(ans)

else:
    An = [-an for an in an][::-1]
    N = Nn*(Nn-1)//2 + Np*(Np-1)//2
    k = k - Nn*Np + Nz*(Nn+Np) + Nz*(Nz-1)//2
    n = N - k

Submission status: Runtime Error

Solution code:
import bisect

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

A.sort()

Nn = bisect.bisect_left(A,0)
Nz = bisect.bisect_left(A,1) - Nn
Np = N - Nn - Nz
An = A[:Nn]
Ap = A[Nn+Nz:]

if Nn*Np >= K:
    left = -10**18-1
    right = -1
    n = Nn*Np - K
    while left+1 < right:
        mid = (left + right) //2
        i = j = 0
        c = 0
        while i < Nn and j < Np:
            if An[i]*Ap[j] > mid:
                c += 1
                j += 1
                if j >= Np:
                    c += (Nn-1-i)*Np
            else:
                i += 1
            if c > n:
                break
        if c > n:
            left = mid
        else:
            right = mid
    ans = right

elif Nn*Np + Nz*(Nn+Np) + Nz*(Nz-1)//2 >= K:
    ans = 0

else:
    An = [-an for an in an][::-1]
    N = Nn*(Nn-1)//2 + Np*(Np-1)//2
    k = k - Nn*Np + Nz*(Nn+Np) + Nz*(Nz-1)//2
    n = N - k

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a_p, a_m, a_z = [], [], 0
for i in input().split():
  ii = int(i)
  if ii==0:
    a_z += 1
  elif ii>0:
    a_p.append(ii)
  else:
    a_m.append(-ii)
a_p.sort()
a_m.sort()
l_p, l_m = len(a_p), len(a_m)
    
def rank(x):
  r = 0
  if x > 0:
    r += a_z*(n-a_z) + a_z*(a_z-1)//2
    for a in [a_p, a_m]:
      for i in range(len(a)-1):
        xi = x/a[i]
        if xi < 1:
          break
        for j in a[i+1:]:
          if xi > j:
            r += 1
          else:
            break
  if x >= 0:
    r += l_m*l_p 
  else:
    for i in a_p:
      xi = -x/i
      for j in range(l_m-1,-1,-1):
        if xi < a_m[j]:
          r += 1
        else:
          break
  return r

high = max(max(a_p),max(a_m))**2
low = -high

while high - low > 1:
  mid = (high + low)//2
  if rank(mid) >= k:
    high = mid
  else:
    low = mid
print(high+low-mid)

Submission status: Runtime Error

Solution code:
import math
import numpy as nu

N, K = map(int,input().split())
A = list(map(int,input().split()))
a = (N*(N-1))/2
B = nu.zeros(a)
bl=0

for j in range(0,N-1):
  for i in range(j,N-1):
    b = A[i+1]*A[j]
    B[bl] = b
    bl += 1

B = sorted(B,  reverse=False)
print(int(B[K-1]))

Submission status: Runtime Error

Solution code:
import math
import numpy as nu

N, K = map(int,input().split())
A = list(map(int,input().split()))
a = (N*(N-1))/2
B = nu.zeros(a)
bl=0

for j in range(0,N-1):
  for i in range(j,N-1):
    b = A[i+1]*A[j]
    B[bl] = b
    bl += 1

B = sorted(B,  reverse=False)
print(B[K-1])

Submission status: Runtime Error

Solution code:
import numpy as np
stdin = open(0)

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

maxA = max(np.abs(A))


z = A[A==0]
p = A[A>0]
n = A[A<0]


def check(x):
    ret = 0
    if x >= 0:
        ret += N*len(z)
    ret += np.searchsorted(A,x//p,side='right').sum()
    ret += (N-np.searchsorted(A,x/n)).sum()
    ret -= len([a for a in A if a*a <= x])
    return ret//2;
        

ub = maxA*maxA
lb = -ub-1
while ub-lb > 1:
    mid = (ub+lb)>>1
    if check(mid) < K:
        lb = mid
    else:
        ub = mid
print(ub)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def nC2(n):
    return n * (n-1) // 2

n,k = get_nums_l()
aaa = get_nums_l()

negatives = []
zeros = 0
positives = []

for a in aaa:
    if a == 0:
        zeros += 1
    elif a > 0:
        positives.append(a)
    else:
        negatives.append(a)

# 絶対値小さい順
positives.sort()
negatives.sort(reverse=True)

len_positives = len(positives)
len_negatives = len(negatives)

p_zeros = zeros*(len_negatives+len_positives) + nC2(zeros)
p_positives = nC2(len_positives) + nC2(len_negatives)
p_negatives = len_positives * len_negatives

log(len_negatives, zeros, len_positives)
log(p_negatives, p_zeros, p_positives)

if p_negatives < k <= (p_negatives+p_zeros):
    print(0)
    exit()

if k <= p_negatives:
    # 負の場合
    nokori = k
    log("nokori", nokori)

    left = -1 * ((10**9)**2 + 1)
    right = (10**9)**2 + 1

    # 積がcenter未満になるペアがnokori個未満になる最大のcenterを探す
    while left < right:
        center = (left+right+1) // 2
        log("center", center)

        left2 = len_positives-1
        right2 = len_negatives-1

        count = 0

        while right2 > 0 and positives[left2] * negatives[right2] < center:
            right2 -= 1

        while abs(left2) > abs(right2):
            if positives[left2] * negatives[right2] < center:
                count += len_negatives - right2
                left2 -= 1
            else:
                right2 += 1

        left2 = len_positives-1
        right2 = len_negatives-1

        while left2 > 0 and positives[left2] * negatives[right2] < center:
            left2 -= 1
        while abs(left2) < abs(right2):
            if positives[left2] * negatives[right2] < center:
                count += len_positives - left2
                right2 -= 1
            else:
                left2 += 1
        
        log("count", count)
        if count < nokori:
            left = center
        else:
            right = center - 1
    print(left)
    exit()

# 正の場合
nokori = k - p_negatives - p_zeros
log("nokori", nokori)

left = 1
right = (10**9)**2 + 1

# 積がcenter未満になるペアがnokori個未満になる最大のcenterを探す
while left < right:
    center = (left+right) // 2
    # log("center", center)

    left2 = 0
    right2 = len_positives-1

    count = 0

    while left2 < right2:
        if positives[left2] * positives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1

    left2 = 0
    right2 = len_negatives-1

    while left2 < right2:
        if negatives[left2] * negatives[right2] < center:
            count += right2 - left2
            left2 += 1
        else:
            right2 -= 1
    
    if count < nokori:
        left = center + 1
    else:
        right = center
print(center)

Submission status: Runtime Error

Solution code:
import math
import itertools
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,k=map(int,input().split())
a=list(map(int, input().split()))
a=sorted(a)
mlist=[]
zlist=[]
plist=[]
for i in a:
  if i<0:
    mlist.append(i)
  elif i==0:
    zlist.append(i)
  else:
    plist.append(i)
mnum=len(mlist)
znum=len(zlist)
pnum=len(plist)
mans=mnum*pnum
zans=znum*(pnum+mnum)
if znum>=2:
  zans+=combinations_count(znum,2)
pans=0
if pnum>=2:
  pans+=combinations_count(pnum,2)
if mnum>=2:
  pans+=combinations_count(mnum,2)

if k<mans:
  ans=[]
  for m in mlist:
    for p in plist:
      ans.append(m*p)
  ans=sorted(ans)
  print(ans[k-1])
elif k<mans+zans:
  print(0)
else:
  k=k-(mans+zans)
  ans=[]
  for i in itertools.combinations(plist, 2):
    ans.append(i[0]*i[1])
  for i in itertools.combinations(mlist, 2):
    ans.append(i[0]*i[1])
  ans=sorted(ans)
  print(ans[k-1])

Submission status: Runtime Error

Solution code:
import sys

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

UnderZeroA = tuple([a for a in A if a < 0])
ZeroA = tuple([a for a in A if a == 0])
OverZeroA = tuple([a for a in A if a > 0])

L_UnderZeroA = len(UnderZeroA)
L_ZeroA = len(ZeroA)
L_OverZeroA = len(OverZeroA)

L_UnderZero = L_UnderZeroA*L_OverZeroA
L_Zero = L_ZeroA*(L_UnderZeroA + L_OverZeroA) + L_ZeroA*(L_ZeroA-1)//2
L_OverZero = N*(N-1)//2 - L_UnderZero - L_Zero

if K <= L_UnderZero:
    arr = [None]*(L_UnderZeroA*L_OverZeroA)
    for i, u in enumerate(UnderZeroA):
        for j, o in enumerate(OverZeroA):
            arr[i*L_OverZeroA+j] = u*o
    arr.sort()
    print(arr[K-1])
elif K > L_UnderZero + L_Zero:
    arr1 = [None]*(L_UnderZeroA*(L_UnderZeroA - 1)//2)
    arr2 = [None]*(L_OverZeroA*(L_OverZeroA - 1)//2)
    if L_UnderZeroA > 1:
        for i in range(L_UnderZeroA - 1):
            for j in range(i+1, L_UnderZeroA):
                arr1[i*(L_UnderZeroA-1) + (j-i-1) - (i-1)*i//2] = UnderZeroA[i]*UnderZeroA[j]
    if L_OverZeroA > 1:
        for i in range(L_OverZeroA - 1):
            for j in range(i+1, L_OverZeroA):
                arr2[i*(L_OverZeroA-1) + (j-i-1) - (i-1)*i//2] = OverZeroA[i]*OverZeroA[j]
    arr = arr1 + arr2
    arr.sort()
    index = K - L_UnderZero - L_Zero
    print(arr[index-1])
else:
    print(0)