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: Time Limit Exceeded

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

from itertools import combinations, starmap


multiple_list = list(combinations(A, 2))
multiple_result_list = list(starmap(lambda x, y: x*y, multiple_list))


result_sorted = sorted(multiple_result_list)

print(result_sorted[K-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

nk=[int(x) for x in raw_input().split()]
n=nk[0]
k=nk[1]
A=sorted([int(i) for i in raw_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: Time Limit Exceeded

Solution code:
import bisect

nk=[int(x) for x in raw_input().split()]
n=nk[0]
k=nk[1]
A=sorted([int(i) for i in raw_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: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**18+1
    n,k=MI()
    aa=LI()
    pp=[]
    mm=[]
    zero=0
    for a in aa:
        if a>0:pp.append(a)
        elif a<0:mm.append(a)
        else:zero+=1
    pp.sort()
    mm.sort()
    cm=len(mm)*len(pp)
    cz=zero*(zero-1)//2+zero*(n-zero)

    def ok1(c):
        i=0
        cnt=0
        for m in mm:
            while i<len(pp) and m*pp[i]>=c:i+=1
            if i==len(pp):break
            cnt+=len(pp)-i
        return cnt<k

    def ok2(c):
        cnt=0
        j=len(mm)-1
        for i,m in enumerate(mm):
            while j>i and m*mm[j]>=c:j-=1
            if i>=j:break
            cnt+=j-i
        j=len(pp)-1
        for i,p in enumerate(pp):
            while j>i and p*pp[j]>=c:j-=1
            if i>=j:break
            cnt+=j-i
        return cnt<k

    # 答えが負
    if k<=cm:
        l=-inf
        r=inf
        while l+1<r:
            c=(l+r)//2
            if ok1(c):l=c
            else:r=c
    # 答えが0
    elif k<=cm+cz:
        print(0)
        exit()
    # 答えが正
    else:
        mm.reverse()
        k-=cm+cz
        l=-inf
        r=inf
        while l+1<r:
            c=(l+r)//2
            if ok2(c):l=c
            else:r=c
    print(l)

main()

Submission status: Time Limit Exceeded

Solution code:
inp = input().split()
n,k = map(int, inp)
nums = list(input().split())
nums_list = list(map(int, nums))
a_list = []
for i in range(n):
    for l in range(n):
            if i < l:
                if l < n:
                    product = nums_list[i]*nums_list[l]
                    a_list.append(product)
a_list.sort()
print(a_list[k-1])

Submission status: Time Limit Exceeded

Solution code:
#D
import itertools
n,k=map(int, input().split())
a=list(map(int, input().split()))
l=[]
for x in itertools.combinations(a,2):
    l.append(x[0]*x[1])
l_sorted=sorted(l)
print(l_sorted[k-1])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = []
a.sort()
minus = 0
zero = 0
plus = 0
for i in range(n):
  if a[i] == 0:
    zero+=1
  elif a[i] >0:
    plus+=1
  else:
    minus+=1
minus_num = plus*minus
plus_num = plus*(plus-1)//2 + minus*(minus-1)//2
zero_num = (plus+minus)*zero+zero*(zero-1)//2
if minus_num >= k:###k番目はマイナス
  for i in range(n-1):
    for j in range(i+1,n):
      b.append(a[i]*a[j])
  b.sort()
  b = b[:minus_num]###このリストは負の数のみで構成されている
  print(b[k-1])
elif minus_num +zero_num >= k:###k番目は0
  for i in range(n-1):
    for j in range(i+1,n):
      b.append(a[i]*a[j])
  b.sort()
  b = b[minus_num:minus_num+zero_num]###このリストbは0で構成されている
  print(0)
else:###k番目はプラス
  for i in range(n-1):
    for j in range(i+1,n):
      b.append(a[i]*a[j])
  b.sort()
  b = b[minus_num+zero_num:minus_num+zero_num+plus_num]###このリストは正の数のみで構成されている
  print(b[k-1-minus_num-zero_num])

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = []
for i in itertools.combinations(A, r=2):
	ans.append(i[0]*i[1])
	
print(sorted(ans)[K-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(x):
    cnt = 0
    for i,j in enumerate(a):
        if j == 0:
            if x < 0:
                continue
            cnt += n-i-1
        elif j > 0:
            r =  br(a,x//j)
            if r <= i:
                continue
            cnt += r - i - 1
        else:
            l = bl(a,-(x//-j))
            if l <= i:
                l = i+1
            cnt += n - l
        if cnt >= k:
            return True
    return False

n,k = LI()
a = LI()
a.sort()

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(x):
    cnt = 0
    for i,j in enumerate(a):
        if j == 0:
            if x >= 0:
                cnt += n-i-1
        elif j > 0:
            r =  br(a,x//j)
            if r <= i:
                continue
            cnt += r - i - 1
        else:
            l = bl(a,-(x//-j))
            if l <= i:
                l = i+1
            cnt += n - l
    return cnt >= k

n,k = LI()
a = LI()
a.sort()

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = input().split()
N = int(N)
K = int(K)
A_list = input().split()
A_array = np.array([int(Ai) for Ai in A_list])
 
A_minus_array = A_array[A_array < 0]
A_zero_array = A_array[A_array == 0]
A_plus_array = A_array[A_array > 0]
 
A_minus_num = len(A_minus_array)
A_zero_num = len(A_zero_array)
A_plus_num = len(A_plus_array)
 
count_multi1 = int(A_minus_num*A_plus_num)
count_multi2 = int(A_minus_num*A_plus_num + A_zero_num*(A_minus_num+A_plus_num) + A_zero_num*(A_zero_num-1)/2 if A_zero_num > 1\
                else A_minus_num*A_plus_num + A_zero_num*(A_minus_num+A_plus_num))
 
if count_multi1 >= K:
    multi_A = []
    for A_minus in A_minus_array:
        for A_plus in A_plus_array:
            multi_A.append(A_minus*A_plus)
    print(sorted(multi_A)[K-1])
elif count_multi2 >= K:
    print(0)
else:
    K_ = K - count_multi2
    A_minus_array_ = sorted(np.abs(A_minus_array))
    A_plus_array_ = sorted(np.abs(A_plus_array))
    multi_A1 = []
    multi_A2 = []
    if A_minus_num > 1:
        for i in range(A_minus_num):
            for j in range(i+1, A_minus_num):
                multi_A1.append(A_minus_array_[i]*A_minus_array_[j])
    if A_plus_num > 1:
        for i in range(A_plus_num):
            for j in range(i+1, A_plus_num):
                multi_A2.append(A_plus_array_[i]*A_plus_array_[j])
    multi_A = multi_A1 + multi_A2
    multi_A = sorted(multi_A)
    print(multi_A[K_-1])

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

Submission status: Time Limit Exceeded

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

import bisect

def main():
  n, k = map(int, input().split())
  minus = []
  zero = 0
  plus = []
  lm = 0
  lp = 0
  for i in map(int, input().split()):
    if i < 0:
      minus.append(-i)
      lm += 1
    elif i == 0:
      zero += 1
    else:
      plus.append(i)
      lp += 1
  
  J = lm*lp + zero*(n-zero) + zero*(zero-1)//2

  minus.sort()
  plus.sort()

  def test(x):
    count = 0
    if x < 0:
      x = -x
      for i in minus:
        count += lp - bisect.bisect_left(plus, -(-x//i))
      return count >= k

    if x == 0:
      return J >= k

    count = J
    for i in range(lm-1):
      t = minus[i]
      count += bisect.bisect_right(minus[i+1:], x//t)
    for i in range(lp-1):
      t = plus[i]
      count += bisect.bisect_right(plus[i+1:], x//t)
    return count >= k

  if J < k:
    ng = 0
    ok = 10**18
  else:
    ng = -(10**18)
    ok = 0
  
  while ok-ng > 1:
    mid = (ok+ng)//2
    if test(mid):
      ok = mid
    else:
      ng = mid
  print(ok)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

Submission status: Time Limit Exceeded

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

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

index = [0] * (len(A)-1)
value = [0] * (len(A)-1)
for i in range(len(A)-1):
    if A[i] < 0:
        index[i] = len(A) - 1
    else:
        index[i] = i + 1
    value[i] = A[i] * A[index[i]]

def proceed(index, value):
    val = min(value)
    i = value.index(val)
    d = -1 if A[i] < 0 else 1
    index[i] = index[i] + d
    if index[i] <= i or len(A) <= index[i]:
        value[i] = 10**20
    else:
        value[i] = A[i] * A[index[i]]
    return val

for i in range(K):
    val = proceed(index, value)

print(val)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(x):
    cnt = 0
    for i in range(n):
        if a[i] == 0:
            if x >= 0:
                cnt += n-i-1
        elif a[i] > 0:
            r =  br(a,x//a[i])
            if r <= i:
                continue
            cnt += r - i - 1
        else:
            l = bl(a,-(x//-a[i]))
            if l <= i:
                l = i+1
            cnt += n - l
    return cnt >= k
n,k = LI()
a = LI()
a.sort()

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

P = itertools.combinations(AN, 2)

l = []

for p in P:
    l.append(p[0]*p[1])
l.sort()
print(l[K-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def hasbelow1(x,b,j):
    if b==0:
        ret = 0 if x<=0 else len(a)-j
    elif b>0:
        mn = j-1
        mx = len(a)
        while mx>mn+1:
            mid = (mx+mn)//2
            if b*a[mid]<x:
                mn = mid
            else:
                mx = mid
        ret = mx-j
    else:
        mn = j-1
        mx = len(a)
        while mx>mn+1:
            mid = (mx+mn)//2
            if b*a[mid]<x:
                mx = mid
            else:
                mn = mid
        ret = len(a)-mx
    #if b!=0:
    #    ddprint("x {} b {} j {} mn {} mx {} ret {}".format(x,b,j,mn,mx,ret))
    return ret

def hasbelow(x,m):
    #ddprint("hasb x {} m {}".format(x,m))
    sm = 0
    for i in range(n-1):
        h = hasbelow1(x,a[i],i+1)
        #ddprint("i {} ai {} h {}".format(i,a[i],h))
        sm += h
        if sm>=m:
            return True
    return False

n,k = inm()
a = inl()
a.sort()
mx = 10**20
mn = -mx
while mx>mn+1:
    mid = (mx+mn)//2
    if hasbelow(mid,k):
        mx = mid
    else:
        mn = mid
    #ddprint("mx {} mn {}".format(mx,mn))
print(mn)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def solve(mid):
    # mid以下の通り数を求める
    cnt = 0
    if mid > 0:
        # 正と正の組み合わせ
        for i, num in enumerate(plus):
            tmp = mid // num
            ind = bisect_right(plus, tmp, lo=i+1)
            cnt += ind - (i + 1)
        # 負と負の組み合わせ
        for i, num in enumerate(minus_plus):
            tmp = mid // num
            ind = bisect_right(minus_plus, tmp, lo=i+1)
            cnt += ind - (i + 1)
    #print(cnt)

    if mid >= 0:
        # 正と負の組み合わせ
        cnt += cnt_minus
    #print(cnt)

    if mid < 0:
        # 正と負の組み合わせ
        if len(plus) > len(minus_plus):
            for i, num in enumerate(plus):
                tmp = -((mid) // num)
                ind = bisect_left(minus_plus, tmp)
                cnt += len(minus_plus) - ind
        else:
            for i, num in enumerate(minus_plus):
                tmp = -((mid) // num)
                ind = bisect_left(plus, tmp)
                cnt += len(plus) - ind
    #print(cnt)
    
    if mid >= 0:
        cnt += cnt_0
    #print(cnt)

    return cnt >= k


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

plus = []
minus_plus = []
cnt0 = 0
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus_plus.append(-a[i])
    else:
        cnt0 += 1
plus = sorted(plus)
minus_plus = sorted(minus_plus)

# 答えが0になる場合
cnt_0 = (len(plus) + len(minus_plus)) * cnt0
cnt_0 += cnt0 * (cnt0 - 1) // 2

# 答えが負になるとき
cnt_minus = len(minus_plus) * len(plus)

ng = -10**18 - 1
ok = 10**18 + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)
"""
tmp = []
for i in range(n):
    for j in range(i + 1, n):
        tmp.append(a[i] * a[j])
tmp = sorted(tmp)
print(tmp[0:10])
print(tmp[10:20])
print(tmp[20:30])
print(tmp[30:40])
print(tmp[40:50])"""

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def solve(mid):
    # mid以下の通り数を求める
    cnt = 0
    if mid > 0:
        # 正と正の組み合わせ
        for i, num in enumerate(plus):
            tmp = mid // num
            ind = bisect_right(plus, tmp, lo=i+1)
            cnt += ind - (i + 1)
        # 負と負の組み合わせ
        for i, num in enumerate(minus_plus):
            tmp = mid // num
            ind = bisect_right(minus_plus, tmp, lo=i+1)
            cnt += ind - (i + 1)
    #print(cnt)

    if mid >= 0:
        # 正と負の組み合わせ
        cnt += cnt_minus
    #print(cnt)

    if mid < 0:
        # 正と負の組み合わせ
        if len(plus) < len(minus_plus):
            for i, num in enumerate(plus):
                tmp = -((mid) // num)
                ind = bisect_left(minus_plus, tmp)
                cnt += len(minus_plus) - ind
        else:
            for i, num in enumerate(minus_plus):
                tmp = -((mid) // num)
                ind = bisect_left(plus, tmp)
                cnt += len(plus) - ind
    #print(cnt)
    
    if mid >= 0:
        cnt += cnt_0
    #print(cnt)

    if cnt >= k:
        return True
    else:
        return False


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

plus = []
minus_plus = []
cnt0 = 0
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus_plus.append(-a[i])
    else:
        cnt0 += 1
plus = sorted(plus)
minus_plus = sorted(minus_plus)

# 答えが0になる場合
cnt_0 = (len(plus) + len(minus_plus)) * cnt0
cnt_0 += cnt0 * (cnt0 - 1) // 2

# 答えが負になるとき
cnt_minus = len(minus_plus) * len(plus)

ng = -10**18 - 1
ok = 10**18 + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)
"""
tmp = []
for i in range(n):
    for j in range(i + 1, n):
        tmp.append(a[i] * a[j])
tmp = sorted(tmp)
print(tmp[0:10])
print(tmp[10:20])
print(tmp[20:30])
print(tmp[30:40])
print(tmp[40:50])"""

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def hasbelow1(x,b,j):
    if b==0:
        ret = 0 if x<=0 else len(a)-j
    elif b>0:
        mn = j-1
        mx = len(a)
        while mx>mn+1:
            mid = (mx+mn)//2
            if b*a[mid]<x:
                mn = mid
            else:
                mx = mid
        ret = mx-j
    else:
        mn = j-1
        mx = len(a)
        while mx>mn+1:
            mid = (mx+mn)//2
            if b*a[mid]<x:
                mx = mid
            else:
                mn = mid
        ret = len(a)-mx
    if b!=0:
        ddprint("x {} b {} j {} mn {} mx {} ret {}".format(x,b,j,mn,mx,ret))
    return ret

def hasbelow(x,m):
    ddprint("hasb x {} m {}".format(x,m))
    sm = 0
    for i in range(n-1):
        h = hasbelow1(x,a[i],i+1)
        ddprint("i {} ai {} h {}".format(i,a[i],h))
        sm += h
        if sm>=m:
            return True
    return False

n,k = inm()
a = inl()
a.sort()
mx = 10**20
mn = -mx
while mx>mn+1:
    mid = (mx+mn)//2
    if hasbelow(mid,k):
        mx = mid
    else:
        mn = mid
    ddprint("mx {} mn {}".format(mx,mn))
print(mn)

Submission status: Time Limit Exceeded

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


def solve(mid):
    # mid以下の通り数を求める
    cnt = 0
    if mid > 0:
        # 正と正の組み合わせ
        for i, num in enumerate(plus):
            tmp = mid // num
            ind = bisect.bisect_right(plus, tmp, lo=i+1)
            cnt += ind - (i + 1)
        # 負と負の組み合わせ
        for i, num in enumerate(minus_plus):
            tmp = mid // num
            ind = bisect.bisect_right(minus_plus, tmp, lo=i+1)
            cnt += ind - (i + 1)
    #print(cnt)

    if mid >= 0:
        # 正と負の組み合わせ
        cnt += len(minus_plus) * len(plus)
    #print(cnt)

    if mid < 0:
        # 正と負の組み合わせ
        if len(plus) > len(minus_plus):
            for i, num in enumerate(plus):
                tmp = -((mid) // num)
                ind = bisect.bisect_left(minus_plus, tmp)
                cnt += len(minus_plus) - ind
        else:
            for i, num in enumerate(minus_plus):
                tmp = -((mid) // num)
                ind = bisect.bisect_left(plus, tmp)
                cnt += len(plus) - ind
    #print(cnt)
    
    if mid >= 0:
        cnt += cnt_0
    #print(cnt)

    if cnt >= k:
        return True
    else:
        return False


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

plus = []
minus_plus = []
cnt0 = 0
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus_plus.append(-a[i])
    else:
        cnt0 += 1
plus = sorted(plus)
minus_plus = sorted(minus_plus)

# 答えが0になる場合
cnt_0 = (len(plus) + len(minus_plus)) * cnt0
cnt_0 += cnt0 * (cnt0 - 1) // 2


ng = -10**20
ok = 10**20

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)
"""
tmp = []
for i in range(n):
    for j in range(i + 1, n):
        tmp.append(a[i] * a[j])
tmp = sorted(tmp)
print(tmp[0:10])
print(tmp[10:20])
print(tmp[20:30])
print(tmp[30:40])
print(tmp[40:50])"""

Submission status: Time Limit Exceeded

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()
    x=bisect_left(A,0)
    y=bisect_right(A,0)
    if K<=len(A[:x])*len(A[y:]):
        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
            for z in A[:x]:
                c+=len(A[y:])-bisect_left(A[y:],-(-mid//z))
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan1(0,-10**18+1))
    K-=len(A[:x])*len(A[y:])
    if 0<K<=len(A[x:y])*(N-len(A[x:y]))+(len(A[x:y])*(len(A[x:y])-1))//2:
        print(0)
    K-=len(A[x:y])*(N-len(A[x:y]))+(len(A[x:y])*(len(A[x:y])-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
            for z in A[:x]:
                c+=len(A[:x])-bisect_left(A[:x],-(-mid//z))
                if -(-mid//z)<=z:
                    c-=1
            for z in A[y:]:
                c+=bisect_right(A[y:],(mid//z))
                if (mid//z)>=z:
                    c-=1
            c//=2
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan2(10**18+1,0))

    
        
    

if __name__ == '__main__':
    main()