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:
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)
  l=0
  r=10**18+1
  k=ncc-k
  while r-l!=1:
    mid=(l+r)//2
    cnt=0
    pos=c2-1
    for i in range(c1):
      while pos!=-1:
        if arr2[pos]>mid//arr1[i]:
          pos-=1
        else:
          break        
      cnt+=pos+1
    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
    pos1=c1-1
    for i in range(c1):
      tmp=0
      while pos1!=-1:
        if arr1[pos1]>mid//arr1[i]:
          pos1-=1
        else:
          break
      tmp+=pos1+1
      if arr1[i]**2<mid:
        tmp-=1
      cnt1+=tmp
    cnt1=cnt1//2
    cnt2=0
    pos2=c2-1
    for i in range(c2):
      tmp=0
      while pos2!=-1:
        if arr2[pos2]>mid//arr2[i]:
          pos2-=1
        else:
          break
      tmp+=pos2+1
      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)

Submission status: Accepted

Solution code:
import numpy as np

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

zero = A[A==0]
pos = A[A>0]
neg = A[A<0]

def f(x):
    ans = 0
    if x >= 0:
        ans += n * len(zero)
    ans += np.searchsorted(A, x// pos, side="right").sum()
    ans += (n - np.searchsorted(A, (-x-1)//(-neg), side="right")).sum()
    ans -= np.count_nonzero(A*A<=x)
    return ans // 2

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

Submission status: Accepted

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

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    P = []
    Z = 0
    N = []
    for a in A:
        if a == 0:
            Z += 1
        elif a < 0:
            N.append(a)
        else:
            P.append(a)
    N.sort()
    P.sort()

    NN = len(N) * len(P)
    ZN = len(N) * Z + len(P) * Z + Z * (Z-1) // 2
    if M <= NN:
        N.reverse()
        def f(n):
            ans = 0
            i = bisect.bisect_left(P, -(n // -N[0]))
            for nn in N:
                m = -(n // -nn)
                while i != 0 and P[i-1] >= m:
                    i -= 1
                ans += len(P) - i
            return ans
        bs = Bisect(f)

        return bs.bisect_right(M-1, -INF, 0)

    elif M <= NN + ZN:
        return 0
    else:
        M -= NN + ZN
        N = [-v for v in N]
        N.sort()

        def f(n):
            ans = 0
            if N:
                i = bisect.bisect_right(N, n//N[0])
                for nn in N:
                    m = n // nn
                    while i != 0 and N[i-1] > m:
                        i -= 1
                    ans += i
                    if i > 0 and N[i-1] >= nn:
                        ans -= 1
            if P:
                i = bisect.bisect_right(P, n//P[0])
                for pn in P:
                    m = n // pn
                    while i != 0 and P[i-1] > m:
                        i -= 1
                    ans += i
                    if i > 0 and P[i-1] >= pn:
                        ans -= 1
            ans //= 2
            return ans
        bs = Bisect(f)
        return bs.bisect_right(M-1, 1, INF)

def f(N, M, A):
    ans = []
    for i in range(N):
        for j in range(i+1, N):
            ans.append((A[i]*A[j], A[i], A[j]))
    ans.sort()
    for i, r in enumerate(ans):
        print(i, r)

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import groupby

def sgn(num):
    if num<0:
        return -1
    elif num==0:
        return 0
    else:
        return 1


N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
a=0
b=0
c=0
B=[sgn(A[i]) for i in range(0,N)]
B=groupby(B)
for key,group in B:
    g=len(list(group))
    if key==-1:
        a=g
    elif key==0:
        b=g
    else:
        c=g
if a*c>=K:
    def condition(num):
        s=0
        t=a+b
        set=0
        while a+b+c-1>=t and a-1>=s:
            if A[s]*A[t]>num:
                t+=1
            else:
                set+=a+b+c-t
                s+=1
        if set>=K:
            return True
        else:
            return False
    start=-10**18
    end=-1
    while end-start>1:
        test=(start+end)//2
        if condition(test):
            end=test
        else:
            start=test
    if condition(start):
        print(start)
    else:
        print(end)
elif a*c+a*b+b*c+b*(b-1)//2>=K:
    print(0)
else:
    K-=a*c+a*b+b*c+b*(b-1)//2
    def condition(num):
        set=0
        s=a-1
        t=0
        while a-1>=t and s>=0:
            if A[s]*A[t]>num:
                t+=1
            else:
                set+=a-t
                if s>=t:
                    set-=1
                s-=1
        s=a+b
        t=a+b+c-1
        while t>=a+b and a+b+c-1>=s:
            if A[s]*A[t]>num:
                t-=1
            else:
                set+=t-a-b+1
                if t>=s:
                    set-=1
                s+=1
        if set>=2*K:
            return True
        else:
            return False
    start=1
    end=10**18
    while end-start>1:
        test=(end+start)//2
        if condition(test):
            end=test
        else:
            start=test
    if condition(start):
        print(start)
    else:
        print(end)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
plus = []
minus = []
zero = 0
for i in map(int, input().split()):
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1
plus.sort()
minus.sort(reverse=True)


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok, ng = -10 ** 19, 10 ** 19
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    cnt = 0
    if mid >= 0:
        cnt += len(plus) * len(minus)
        if mid > 0:
            cnt += zero * (zero - 1) // 2 + zero * (N - zero)
            for a in (plus, minus):
                l, r = 0, len(a) - 1
                while l < r:
                    while l < r and a[l] * a[r] >= mid:
                        r -= 1
                    cnt += r - l
                    l += 1
    else:
        r = len(minus) - 1
        for l in range(len(plus)):
            while r >= 0 and plus[l] * minus[r] < mid:
                r -= 1
            cnt += len(minus) - (r + 1)

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

print(ok)

Submission status: Accepted

Solution code:
import sys

n, k = map(int, sys.stdin.readline().strip().split())
a = map(int, sys.stdin.readline().strip().split())

def main(n, k, a):
    nega = []
    posi = []
    zeros = 0

    for ai in a:
        if ai < 0:
            nega.append(ai)
        elif ai > 0:
            posi.append(ai)
        else:
            zeros += 1

    posi.sort()
    nega.sort(reverse=True)

    ng = - (10 ** 18)-1
    ok = 10 ** 18 + 1

    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0

        if mid >= 0:
            cnt += zeros * (zeros - 1) // 2 + zeros * (n - zeros)

        if mid > 0:
            cnt += len(nega) * len(posi)
            for a in (posi, nega):
                l = 0
                r = len(a)-1
                while l < r:
                    while l < r and a[l] * a[r] > mid:
                        r -= 1
                    cnt += r - l
                    l += 1
        else:
            r = len(nega) - 1
            for l in range(len(posi)):
                while r >= 0 and posi[l] * nega[r] <= mid:
                    r -= 1
                cnt += len(nega) - r - 1

        if cnt >= k:
            ok = mid
        else:
            ng = mid
    print(ok)


main(n, k, a)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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) # 同じもの2つは選べない
        return ans // 2

    ok = 10**18
    ng = -ok - 1
    while ok - ng > 1: # 二分探索
        cen = (ok + ng) // 2
        if count(cen) >= k:
            ok = cen
        else:
            ng = cen
    print(ok)

if __name__ == '__main__':
    main()

Submission status: Accepted

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()))

    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

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

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def count(x):
    cnt = 0
    if x >= 0:
        cnt += N * len(zero)
    cnt += np.searchsorted(A, x // pos, side='right').sum()
    cnt += N * len(neg) - np.searchsorted(A, -(-x // neg), side='left').sum()
    cnt -= np.count_nonzero(A * A <= x)

    return cnt // 2


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

neg = A[A < 0]
zero = A[A == 0]
pos = A[A > 0]

r = 10**18
l = -r

while r - l > 1:
    m = (r + l) // 2
    if count(m) >= K:
        r = m
    else:
        l = m

print(r)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = np.sort(np.array([int(x) for x in stdin.readline().rstrip().split()]))
MINUS = A[A<0]
ZERO = A[A==0]
PLUS = A[A>0]

def solve(x):
    count_tpl = 0
    if x >= 0:
        count_tpl += len(ZERO) * N
    count_tpl += np.searchsorted(A, x // PLUS, side='right').sum()
    count_tpl += (N - np.searchsorted(A, (-x-1)//(-MINUS), side='right')).sum()
    count_tpl -= np.count_nonzero(A * A <= x)
    assert count_tpl % 2 == 0
    return count_tpl // 2

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

Submission status: Accepted

Solution code:
def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.readline

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

    minus = []
    plus = []
    zero = 0
    for a in A:
        if a > 0:
            plus.append(a)
        elif a < 0:
            minus.append(-a)
        else:
            zero += 1
    plus.sort()
    minus.sort()
    plus_num = len(plus)
    minus_num = len(minus)
    if plus_num * minus_num < K <= (N*(N-1))//2 - (plus_num*(plus_num-1))//2 - (minus_num*(minus_num-1))//2:
        print(0)
        exit()
    if plus_num * minus_num >= K:
        ng = 0
        ok = -10**18-1
        mid = (ng+ok)//2
        while ng - ok > 1:
            cnt = 0
            j = 0
            for a in reversed(minus):
                while True:
                    if j == plus_num:
                        break
                    if a * plus[j] < -mid:
                        j += 1
                    else:
                        break
                #print(mid, a, j)
                cnt += plus_num - j
            #print(mid, cnt)
            if cnt < K:
                ok = mid
            else:
                ng = mid
            mid = (ok+ng)//2
        print(ng)
    else:
        K -= (N*(N-1))//2 - (plus_num*(plus_num-1))//2 - (minus_num*(minus_num-1))//2
        ng = 10**18+1
        ok = 0
        mid = (ok+ng)//2
        while ng - ok > 1:
            cnt = 0
            j = plus_num-1
            for a in plus:
                while True:
                    if j == -1:
                        break
                    if a * plus[j] > mid:
                        j -= 1
                    else:
                        break
                cnt += j+1
            for a in plus:
                if a**2 <= mid:
                    cnt -= 1
                else:
                    break
            j = minus_num-1
            for a in minus:
                while True:
                    if j == -1:
                        break
                    if a * minus[j] > mid:
                        j -= 1
                    else:
                        break
                cnt += j+1
            for a in minus:
                if a**2 <= mid:
                    cnt -= 1
                else:
                    break
            #print(cnt)
            assert cnt%2 == 0
            cnt //= 2
            if cnt < K:
                ok = mid
            else:
                ng = mid
            mid = (ok+ng)//2
        print(ng)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

def main():
    n, k = [int(s) for s in input().strip().split()]
    A = [int(s) for s in input().strip().split()]
    
    P = sorted(a for a in A if a > 0)
    N = sorted(a for a in A if a < 0)
    pp, nn = len(P), len(N)
    negpair = pp * nn
    pospair = pp * (pp - 1) // 2 + nn * (nn - 1) // 2

    if negpair < k <= n * (n - 1) // 2 - pospair:
        print(0)
        return
    
    if k <= negpair:
        lo, hi = -(10 ** 18), -1
        while lo < hi:
            x = (lo + hi) // 2

            j = 0
            cnt = 0
            for i in range(pp):
                while j < nn and P[i] * N[j] <= x:
                    j += 1
                cnt += j

            if cnt >= k:
                hi = x
            else:
                lo = x + 1
        print(lo)
    
    else:
        class Helper:
            def __getitem__(self, x):
                j = pp - 1
                cnt = 0
                for i in range(pp):
                    while j > i and P[i] * P[j] > x:
                        j -= 1
                    cnt += max(j - i, 0)
                j = nn - 1
                for i in range(nn):
                    while j > i and N[i] * N[j] <= x:
                        j -= 1
                    cnt += nn - 1 - max(i, j)
                return cnt
        
        x = bisect_left(Helper(), k - (n * (n - 1) // 2 - pospair), lo=1, hi=10 ** 18)
        print(x)


main()

Submission status: Accepted

Solution code:
# これは500点では？
import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a) # numpy の array で高速化
a.sort()

zero = np.count_nonzero(a == 0)
positive = a[a > 0] # numpy の特徴的な記法
negative = a[a < 0]

def count(x): # 積が x 以下のペアは何個あるか？
  ans = 0
  if x >= 0: # 片側が 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() # 片側が負の場合 切り上げは -(-a//b)
  ans -= np.count_nonzero(a * a <= x) # 同じもの2つは選べない
  return ans // 2

ok = 10**18
ng = -ok - 1
while ok - ng > 1: # 二分探索
  cen = (ok + ng) // 2
  if count(cen) >= k:
    ok = cen
  else:
    ng = cen
print(ok)

Submission status: Accepted

Solution code:
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()))
A.sort()
mA, nA, zc = [], [], 0
dd = []
for a in A:
    if a<0:
        mA.append(a)
    elif a>0:
        nA.append(a)
    else:
        zc += 1
    dd.append(a*a)
#rA = A[::-1]
#print(mA, nA)
lnA = len(nA)
lmA = len(mA)

def F(idx):
    j = lnA-1
    r = 0
    for a in nA:
        while j >= 0:
            if nA[j]*a <= idx:
                break
            j -= 1
        r += j+1
    if idx >= 0:
#        print(2*(zc*N) - zc*zc)
        r += 2*(zc*N) - zc*zc
#    print(r, zc)
    j = 0
    for a in mA[::-1]:
        while j < lmA:
            if mA[j]*a <= idx:
                break
            j += 1
        r += lmA-j
    j = 0
    for a in mA:
        while j < lnA:
            if nA[j]*a <= idx:
                break
            j += 1
        r += 2*(lnA-j)

    for a in dd:
        if a <= idx:
            r-=1
    return r//2
#print(F(448283280358331064))

mx, mn = 2*10**18, -2*10**18
idx = (mx + mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        idx, mn = (idx + mx)//2, idx
        continue
    idx, mx = (idx + mn)//2, idx
print(idx+1)

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 solve(x):
    ans = 0
    if x < 0:
        x = -x
        r = 0
        for mi in minus[::-1]:
            while r < len(plus) and plus[r]* mi < x:
                r += 1
            ans += len(plus) - r
        return ans

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

    ans //= 2
    ans += len(minus)*len(plus)
    return ans

low = -10**18-1
high = 10**18+1
while high - low > 1:
    mid = (high + low) // 2
    if solve(mid) < k:
        low = mid
    else:
        high = mid

print(high)

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
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

plus = minus = zero = 0
ps = []
ms = []
for i in a:
    if i == 0:
        zero += 1
    elif i > 0:
        plus += 1
        ps.append(i)
    else:
        minus += 1
        ms.append(-i)

ps.sort()
ms.sort()

def check(m):
    if m == 0:
        return plus*minus + zero*(zero-1)//2 + zero*(plus+minus) >= k
    elif m > 0:
        tmp = plus*minus + zero*(zero-1)//2 + zero*(plus+minus)
        for l in [ps, ms]:
            X = len(l)
            cur = X-1
            for i in range(X):
                while cur >= 0 and l[i]*l[cur] > m:
                    cur -= 1
                if cur <= i:
                    break
                tmp += cur-i
        return tmp >= k
    else:
        tmp = 0
        cur = 0
        for i in reversed(range(plus)):
            while cur < minus and ms[cur]*ps[i] < -m:
                cur += 1
            tmp += minus-cur
        return tmp >= k

left = -10**20
right = 10**20

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

print(right)

Submission status: Accepted

Solution code:

import sys

def wantA(m):

    ind = len(Pl)
    ret = 0

    for i in Mi:

        while ind > 0 and Pl[ind-1] * i > m:
            ind -= 1

        ret += ind

    return ret

def wantB(m):

    ans = 0
    ret = 0

    ind = len(Pl)

    for i in Pl:

        while ind > 0 and Pl[ind-1] * i > m:
            ind -= 1

        ret += ind

        if i ** 2 <= m:
            ret -= 1

    ans += ret // 2

    ret = 0

    ind = len(Mi)

    for i in Mi:

        while ind > 0 and Mi[ind-1] * i > m:
            ind -= 1

        ret += ind

        if i ** 2 <= m:
            ret -= 1

    ans += ret // 2

    return ans
   


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

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

Mi = []
znum = 0
Pl = []

for i in A:

    if i < 0:
        Mi.append(-1 * i)
    elif i == 0:
        znum += 1
    else:
        Pl.append(i)

Mi.sort()
Pl.sort()

if len(Mi) * len(Pl) >= K:

    #小さい方からMi*Pl-K+1番目を求める
    K = len(Mi) * len(Pl) - K + 1

    l = Mi[0] * Pl[0] - 1
    r = Mi[-1] * Pl[-1]

    while r - l != 1:

        m = (r + l) // 2

        num = wantA(m)

        if num >= K:
            r = m
        else:
            l = m

    print (-1 * r)
    sys.exit()


K -= len(Mi) * len(Pl)

K -= znum * (len(Pl) + len(Mi) ) + znum * (znum-1) // 2

if K <= 0:
    print (0)
    sys.exit()



#小さい方からK番目を求める

l = 0
r = 10 ** 18 + 1

while r - l != 1:

    m = (r + l) // 2

    num = wantB(m)

    #print (m,num)

    if num >= K:
        r = m
    else:
        l = m

print (r)

Submission status: Accepted

Solution code:
#incited numpy source code from 'https://atcoder.jp/contests/abc155/submissions/10155744'

import numpy

n,k=map(int,input().split())
arr=list(map(int,input().split()))
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 ncc<k<=(ncc+zcc):
  print(0)
else:
  arr=numpy.array(arr,dtype=int)
  ms=numpy.msort(numpy.abs(arr[arr<0]))
  ps=numpy.msort(arr[arr>0])
  if k<=ncc:
    k=ncc-k
    l=0
    r=10**18+1
    while r-l!=1:
      mid=(l+r)//2
      cnt=numpy.searchsorted(ps,mid//ms,side='right')
      if cnt.sum()>k:
        r=mid
      else:
        l=mid
    print(-r)
  elif k<=(ncc+zcc):
    print(0)
  else:
    l=0
    r=10**18+1
    k-=(ncc+zcc)
    while r-l!=1:
      mid=(l+r)//2
      cnt1=numpy.searchsorted(ps,mid//ps,side='right')
      dup1=ps**2<=mid
      cnt2=numpy.searchsorted(ms,mid//ms,side='right')
      dup2=ms**2<=mid
      if (cnt1.sum()-dup1.sum()+cnt2.sum()-dup2.sum())//2>=k:
        r=mid
      else:
        l=mid
    print(r)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus, zero, minus = [], [], []
for x in a:
	if x > 0:
		plus.append(x)
	elif x == 0:
		zero.append(x)
	else:
		minus.append(x)
m, z, p = len(minus), len(zero), len(plus)
mm, zz, pp = m * p, z * (m + p) + (z * (z - 1)) // 2, (m * (m-1)) // 2 + (p * (p-1)) // 2
plus.sort()
plus2 = plus[::-1]
minus.sort()
minus2 = minus[::-1]
#print(mm, zz, pp)

if mm + zz >= k and mm < k:
	print(0)
elif mm >= k:
	ok, ng = -10**19, 0
	while ng-ok > 1:
		x = (ng+ok)//2
		res = 0
		l = 0
		for c in plus:
			if l == m:
				res += m
			elif minus[l] * c >= x:
				res += l
			else:
				while minus[l] * c < x:
					l += 1
					if l == m:
						break
				res += l
		if res < k:
			ok = x
		else:
			ng = x
	print(ng-1)
else:
	ok, ng = 0, 10**19
	while ng-ok > 1:
		x = (ng+ok)//2
		lm, lp = 0, 0
		res = 0
		for c in minus:
			if c*c < x:
				res -= 1
			if lm == m:
				res += m
			elif minus2[lm] * c >= x:
				res += lm
			else:
				while minus2[lm] * c < x:
					lm += 1
					if lm == m:
						break
				res += lm
		for c in plus2:
			if c*c < x:
				res -= 1
			if lp == p:
				res += p
			elif plus[lp] * c >= x:
				res += lp
			else:
				while plus[lp] * c < x:
					lp += 1
					if lp == p:
						break
				res += lp
		res //= 2
		res += zz + mm
		#print(x, res)
		if res < k:
			ok = x
		else:
			ng = x
	print(ng-1)

Submission status: Accepted

Solution code:
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
n,k=map(int,input().split())
a=np.sort(np.array(list((map(int,input().split())))))
q=len(a[a==0])
d=a[a<0]
e=a[a>0]
l,r=10**18,-10**18
while l-r>1:
    t=(l+r)//2
    p=0
    if t>=0:
        p+=q*n
    p+=np.searchsorted(a,t//e,side="right").sum()+(n-np.searchsorted(a,(-t-1)//(-d),side="right")).sum()
    p-=np.count_nonzero(a*a<=t)
    p//=2
    if p>=k:
        l=t
    else:
        r=t
print(l)