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:
from bisect import bisect_right,bisect_left
import sys
input = sys.stdin.readline

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      cnt=0
      for i in range(nn):
        if mid%an[i]!=0:
          cnt+=np-bisect_left(ap,mid//an[i]+1)
        else:
          cnt+=np-bisect_left(ap,mid//an[i])
      #print(cnt)
      if cnt>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      cnt1,cnt2=0,0
      if np>=2:
        for i in range(np):
          cnt1+=bisect_right(ap,mid//ap[i])
          if ap[i]**2<=mid:
            cnt1-=1
      if nn>=2:
        for i in range(nn):
          cnt2+=bisect_right(an,mid//an[i])
          if an[i]**2<=mid:
            cnt2-=1
      if cnt1//2+cnt2//2>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right,bisect_left
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      cnt=0
      for i in range(nn):
        if mid%an[i]!=0:
          cnt+=np-bisect_left(ap,mid//an[i]+1)
        else:
          cnt+=np-bisect_left(ap,mid//an[i])
      #print(cnt)
      if cnt>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      cnt1,cnt2=0,0
      if np>=2:
        for i in range(np):
          cnt1+=bisect_right(ap,mid//ap[i])
          if ap[i]**2<=mid:
            cnt1-=1
      if nn>=2:
        for i in range(nn):
          cnt2+=bisect_right(an,mid//an[i])
          if an[i]**2<=mid:
            cnt2-=1
      if cnt1//2+cnt2//2>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right,bisect_left
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      cnt=0
      for i in range(nn):
        if mid%an[i]!=0:
          cnt+=np-bisect_left(ap,mid//an[i]+1)
        else:
          cnt+=np-bisect_left(ap,mid//an[i])
      #print(cnt)
      if cnt>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      cnt1,cnt2=0,0
      if np>=2:
        for i in range(np):
          cnt1+=bisect_right(ap,mid//ap[i])
          if ap[i]**2<=mid:
            cnt1-=1
      if nn>=2:
        for i in range(nn):
          cnt2+=bisect_right(an,mid//an[i])
          if an[i]**2<=mid:
            cnt2-=1
      if cnt1//2+cnt2//2>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right,bisect_left
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      cnt=0
      for i in range(nn):
        if mid%an[i]!=0:
          cnt+=np-bisect_left(ap,mid//an[i]+1)
        else:
          cnt+=np-bisect_left(ap,mid//an[i])
      #print(cnt)
      if cnt>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      cnt1,cnt2=0,0
      if np>=2:
        for i in range(np):
          cnt1+=bisect_right(ap,mid//ap[i])
          if ap[i]**2<=mid:
            cnt1-=1
      if nn>=2:
        for i in range(nn):
          cnt2+=bisect_right(an,mid//an[i])
          if an[i]**2<=mid:
            cnt2-=1
      if cnt1//2+cnt2//2>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k = map(int, input().split())
a = list(map(int, input().split()))
ls = []
for pair in itertools.combinations(a, 2):
    ls.append(pair[0] * pair[1])
print(sorted(ls)[k - 1])

Submission status: Time Limit Exceeded

Solution code:
def myfunc(p):
    return p[0]*p[1]

import itertools
n,k = list(map(int,input().split(" ")))
arr= list(map(int,input().split(" ")))

arr = list(itertools.combinations(arr,2))
#print(arr)

arr = sorted(arr,key=myfunc)
print(arr[k-1][0]*arr[k-1][1])

Submission status: Time Limit Exceeded

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

product = []
for i in range(n):
  for i_ in range(i+1, n):
    product.append(a[i] * a[i_])
product.sort()
    
print(product[k-1])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a_li = list(map(int,input().split()))
from itertools import combinations
from collections import deque
res = []
for x in combinations(a_li,2):
    tmp = x[0]*x[1]
    res.append(tmp)
    
res.sort()
print(res[k-1])

Submission status: Time Limit Exceeded

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

INF = 10**18 + 1

def binary_search(x):
    rec = 0
    for i in range(n):
        if A[i] > 0:
            l,r = -1,n
            while l+1<r:
                m = (l+r)//2
                if A[i]*A[m] < x:
                    l = m
                else:
                    r = m
            rec += l + 1
        else:
            l,r = -1,n
            while l+1<r:
                m = (l+r)//2
                if A[i]*A[m] < x:
                    r = m
                else:
                    l = m
            rec += n-r
        if A[i]*A[i] < x: rec-= 1
    return rec//2

l,r = -INF,INF
while l+1<r:
    m = (l+r)//2
    t = binary_search(m)
    if t<k:
        l = m
    else:
        r = m
print(l)

Submission status: Time Limit Exceeded

Solution code:

INF = int(1e18) + 1
def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()

    MIN = -INF
    MAX = INF
    while MAX-MIN > 1:
        x = (MIN+MAX)//2

        def ok(x):
            total = 0
            for i  in range(n):
                if a[i] < 0:
                    l = -1
                    r = n
                    while r - l > 1:
                        c = (r+l)//2
                        if a[i]*a[c] < x:
                            r = c
                        else:
                            l = c
                    total += n-r
                else:
                    l = -1
                    r = n
                    while r - l > 1:
                        c = (r+l)//2
                        if a[i]*a[c] < x:
                            l = c
                        else:
                            r = c
                    total += r 
                if a[i]*a[i] < x:
                    total -= 1
            total //= 2
            return total < k

        if ok(x):
            MIN = x
        else:
            MAX = x
    print(MIN)
main()

Submission status: Time Limit Exceeded

Solution code:
#python3
INF = int(1e18) + 1
def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()

    MIN = -INF
    MAX = INF
    while MAX-MIN > 1:
        x = (MIN+MAX)//2

        def ok(x):
            total = 0
            for i  in range(n):
                if a[i] < 0:
                    l = -1
                    r = n
                    while r - l > 1:
                        c = (r+l)//2
                        if a[i]*a[c] < x:
                            r = c
                        else:
                            l = c
                    total += n-r
                else:
                    l = -1
                    r = n
                    while r - l > 1:
                        c = (r+l)//2
                        if a[i]*a[c] < x:
                            l = c
                        else:
                            r = c
                    total += r 
                if a[i]*a[i] < x:
                    total -= 1
            total //= 2
            return total < k

        if ok(x):
            MIN = x
        else:
            MAX = x
    print(MIN)
main()

Submission status: Time Limit Exceeded

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

ans = []
for i in range(len(A)):
  for j in range(len(A)-i-1):
    ans.append(A[i]*A[N-j-1])

ans_sort = sorted(ans)
print(ans_sort[K-1])

Submission status: Time Limit Exceeded

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

def count_no_more_than(l):
    cnt = 0
    for x in a_plus:
        y_p = n
        while y_p-1 >= 0 and a[y_p-1] * x > l:
            y_p -= 1
        cnt += y_p

    for x in a_minus:
        y_p = -1
        while y_p+1 < n and a[y_p+1] * x > l:
            y_p += 1
        cnt += n-1 - y_p

    for x in a:
        if x * x <= l:
            cnt -= 1
        
    cnt //= 2
    return cnt

bottom = -(10**18)-1 # <k
top = 10**18 + 1     # >=k

while top - bottom > 1:
    mid = (top + bottom) // 2
    if count_no_more_than(mid) < k:
        bottom = mid
    else:
        top = mid

print(top)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
N=[];Z=[];P=[]
for i in range(n):
  if a[i]<0:
    N.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    P.append(a[i])

if k<=len(N)*len(P):
  for i in range(len(N)):
    N[i]*=-1
  N.sort()
  P.sort()
  L=0;R=10**18+1
  while R-L>1:
    x=(L+R)//2
    ct=0
    for j in range(len(N)):
      ct+=len(P)-bisect.bisect_left(P,(x+N[j]-1)//N[j])
    if ct<k:
      R=x
    else:
      L=x
  print(-L)

elif k<=len(N)*len(P)+(len(Z)*(len(Z)-1))//2+len(Z)*(len(N)+len(P)):
  print(0)

else:
  y=len(N)*len(P)+(len(Z)*(len(Z)-1))//2+len(Z)*(len(N)+len(P))
  for i in range(len(N)):
    N[i]*=-1
  N.sort()
  P.sort()
  L=0;R=10**18+1
  while R-L>1:
    x=(L+R)//2
    ct=0
    for j in range(1,len(N)):
      ct+=bisect.bisect_right(N[0:j],x//N[j])
    for j in range(1,len(P)):
      ct+=bisect.bisect_right(P[0:j],x//P[j])
    if ct<k-y:
      L=x
    else:
      R=x
  print(R)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D


'''
4 3
3 3 -4 -2
'''

from bisect import bisect_left, insort_left
import sys


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

# idx = bisect_left(res, temp)
l_positive = []
l_negative = []
l_negative_hat = []

num_positive, num_zero, num_negative = 0, 0, 0
for a in A:
    if a > 0:
        num_positive += 1
        l_positive.append(a)
    elif a == 0:
        num_zero += 1
    else:
        num_negative += 1
        l_negative.append(a)
        l_negative_hat.append(-a)

# print(num_positive, num_zero, num_negative)
num_nonzero = num_positive + num_negative

c_all = N * (N-1) / 2
c_nonzero = num_nonzero * (num_nonzero-1) / 2
c_zero = c_all - c_nonzero
c_negative = num_positive * num_negative


# これ以外はみる必要ない（必ず負の数）
if K <= c_negative:
    res = []
    for i in l_positive:
        for j in l_negative:
            # insort_left(res, i * j)
            res.append(i * j)
    res.sort()
    print(res[K - 1])
    sys.exit()

else:
    K = int(K - c_negative)
    if K <= c_zero:
        print(0)
        sys.exit()

# 正の数
K = int(K - c_zero)

res = []
for idx, i in enumerate(l_positive):
    for idx2, j in enumerate(l_positive):
        if idx <= idx2:
            continue
        # insort_left(res, i * j)
        res.append(i * j)

for idx, i in enumerate(l_negative):
    for idx2, j in enumerate(l_negative):
        if idx <= idx2:
            continue
        # insort_left(res, i * j)
        res.append(i * j)

res.sort()
print(res[K-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D


'''
4 3
3 3 -4 -2
'''

from bisect import bisect_left, insort_left
import sys


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

# idx = bisect_left(res, temp)
l_positive = []
l_negative = []
l_negative_hat = []

num_positive, num_zero, num_negative = 0, 0, 0
for a in A:
    if a > 0:
        num_positive += 1
        l_positive.append(a)
    elif a == 0:
        num_zero += 1
    else:
        num_negative += 1
        l_negative.append(a)
        l_negative_hat.append(-a)

# print(num_positive, num_zero, num_negative)
num_nonzero = num_positive + num_negative

c_all = N * (N-1) / 2
c_nonzero = num_nonzero * (num_nonzero-1) / 2
c_zero = c_all - c_nonzero
c_negative = num_positive * num_negative


# これ以外はみる必要ない（必ず負の数）
if K <= c_negative:
    res = []
    for i in l_positive:
        for j in l_negative:
            insort_left(res, i * j)
    print(res[K - 1])
    sys.exit()

else:
    K = int(K - c_negative)
    if K <= c_zero:
        print(0)
        sys.exit()

# 正の数
K = int(K - c_zero)

res = []
for idx, i in enumerate(l_positive):
    for idx2, j in enumerate(l_positive):
        if idx <= idx2:
            continue
        insort_left(res, i * j)

for idx, i in enumerate(l_negative):
    for idx2, j in enumerate(l_negative):
        if idx <= idx2:
            continue
        insort_left(res, i * j)

print(res[K-1])

Submission status: Time Limit Exceeded

Solution code:

from bisect import bisect_left, insort_left

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

# idx = bisect_left(res, temp)


res = []
for i in range(N):
    for j in range(N):
        if i <= j:
            continue
        temp = A[i]*A[j]
        insort_left(res, temp)


print(res[K-1])

Submission status: Time Limit Exceeded

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

for i in range(N-1):
    for j in range(i+1, N):
        times.append(A[i]*A[j])

times.sort()

print(times[K-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
nk=input().split()
N=int(nk[0])
K=int(nk[1])
list=input().split()
list1=[]
for item in list :
  list1.append(int(item))
list3=itertools.combinations(list1,2)
list4=[]
for item in list3 :
  list4.append(item[0]*item[1])
 
list4.sort()
print(list4[K-1])

Submission status: Time Limit Exceeded

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

product = []
cnt = 1
for i in range(n - 1):
    for j in range(cnt, n):
        product.append(a[i] * a[j])
    cnt += 1

product.sort()
print(product[k-1])

Submission status: Time Limit Exceeded

Solution code:
#155d
N,K = map(int, input().split())
A_list = [int(e) for e in input().split()]

all_comb = list()

for i in range(N-1):
    multiplied = [A_list[i]*A_list[j] for j in range(i+1,N)]
    all_comb += multiplied
    
all_comb.sort(reverse=False)
#print(all_comb)
print(all_comb[K-1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

negative_end = bisect_left(a, 0)
positive_begin = bisect_right(a, 0)

negative_cnt = negative_end
positive_cnt = n - positive_begin
zero_cnt = n - negative_cnt - positive_cnt

prod_negative = negative_cnt * positive_cnt
# prod_positive = negative_cnt * (negative_cnt - 1) // 2 + positive_cnt * (positive_cnt - 1) // 2
prod_zero = zero_cnt * (negative_cnt + positive_cnt) + zero_cnt * (zero_cnt - 1) // 2
# print(prod_negative, prod_zero, prod_positive)

if k <= prod_negative:
    high, low = 0, -10**18
    while high > low + 1:
        mid = (high + low) // 2
        or_higher = 0
        r = positive_begin
        for l in range(negative_end):
            while r < n and a[l] * a[r] > mid:
                r += 1
            or_higher += positive_cnt - (r - positive_begin)

        if or_higher >= k:
            high = mid
        else:
            low = mid

    res = high

elif k <= prod_negative + prod_zero:
    res = 0

else:
    k -= prod_negative + prod_zero
    high, low = 10**18, 0
    while high > low + 1:
        mid = (high + low) // 2
        or_higher = 0
        r = n - 1
        for l in range(positive_begin, n):
            while r < n and a[l] * a[r] > mid and l < r:
                r -= 1
            or_higher += r - l if l < r else 0
        l = 0
        for r in range(negative_end - 1, -1, -1):
            while l < n and a[l] * a[r] > mid and l < r:
                l += 1
            or_higher += r - l if l < r else 0

        if or_higher >= k:
            high = mid
        else:
            low = mid

    res = high

print(res)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))  # [1, 2, 3, 4] になる

import itertools

B = list(itertools.combinations(A,2))

num = list()

for a in B:
    num.append(a[0]*a[1])

num.sort()
print(num[K-1])

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
List=list(map(int,input().split()))
ans=[]
for i in range(a):
    for j in range(i+1,a):
        ans+=[List[i]*List[j]]
ans=sorted(ans)
print(ans[b-1])

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
List=list(map(int,input().split()))
ans=[]
for i in range(a):
    for j in range(a):
        if i>=j:
            continue
        else:
            ans+=[List[i]*List[j]]
ans=sorted(ans)
print(ans[b-1])

Submission status: Time Limit Exceeded

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

for i in range(N):
    for j in range(i+1,N):
        product.append(A[i]*A[j])
sort_product = sorted(product)
print(sort_product[K-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = [int(x) for x in input().split()]

product = []
for i in range(n):
    for j in range(i+1, n):
        product.append(A[i] * A[j])
product.sort()
print(product[k-1])

Submission status: Time Limit Exceeded

Solution code:
K=int(input().split()[1])
lst=list(map(int,input().split()))
lst2=[]
for i in range(len(lst)):
  for j in range(len(lst)):
        if i<j:
            lst2.append(lst[i]*lst[j])
lst2.sort()
print(lst2[K-1])

Submission status: Time Limit Exceeded

Solution code:
inp = input().split()
N = int(inp[0])
K = int(inp[1])

vals = [int(v) for v in input().split()]

print(sorted([vals[x] * vals[y] for x in range(N) for y in range(x+1, N)])[K-1])

Submission status: Time Limit Exceeded

Solution code:
inp = input().split()
N = int(inp[0])
K = int(inp[1])

vals = input().split()
lst = []

for x in range(N) :
  for y in range(x+1, N) :
    lst.append(int(vals[x]) * int(vals[y]))
    
    if len(lst) > K :
      lst.remove(max(lst))

print(sorted(lst)[K-1])

Submission status: Time Limit Exceeded

Solution code:
inp = input().split()
N = int(inp[0])
K = int(inp[1])

vals = input().split()
lst = []

for x in range(N) :
  for y in range(x+1, N) :
    lst.append(int(vals[x]) * int(vals[y]))

print(sorted(lst)[K-1])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    import bisect
    m = []
    for i in range(N-1):
        for j in range(i+1, N):
            #print(i, j, A[i]*A[j])
            bisect.insort_left(m, A[i]*A[j])
    #print(m)
    print(m[K-1])

resolve()

Submission status: Time Limit Exceeded

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

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): #負数の数(nc)、0の数(zc)、正数の数(pc)を数える
 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 #積が0となるペアの個数を求める
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2 #積が正となるペアの個数を求める
if k<=ncc: #K番目の値が負の場合
 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 #負数のマイナスを取って計算しているため積の大小が逆転するので、大きなほうからK番目、すなわち、小さなほうから(積が負となるペアの個数-K)番目の値を求める
 while r-l!=1:
   mid=(l+r)//2
   cnt=0
   pos=c2-1
   for i in range(c1): #各負数ごとに積が勝手に決めた値midよりも小さくなる正数の個数を求め足し合わせる(しゃくとり法)
     while pos!=-1:
       if arr2[pos]>mid//arr1[i]:
         pos-=1
       else:
         break        
     cnt+=pos+1
   if cnt>k: #勝手に決めた値mid以下の個数が(積が負となるペアの個数-K)個以上であれば真の値はmid以下
     r=mid
   else: #そうでなければ真の値はmid以上
     l=mid
 print(-r) #負数のマイナスを取って計算したので最後にマイナスを付けて出力する
elif k<=(ncc+zcc): #K番目の値が0の場合
 print(0)
else: #K番目の値が正の場合
 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) #正数の中で小さい順にK番目の数を調べたいので負数、0の数を取り除く
 while r-l!=1:
   mid=(l+r)//2
   cnt1=0
   pos1=c1-1
   for i in range(c1): #各負数ごとに積が勝手に決めた値midよりも小さくなる負数の個数を求め足し合わせる(しゃくとり法)
     tmp=0
     while pos1!=-1:
       if arr1[pos1]>mid//arr1[i]:
         pos1-=1
       else:
         break
     tmp+=pos1+1
     if arr1[i]**2<mid: #各要素について、自身を2回選んだ場合の積が勝手に決めた値mid以下なら条件を満たすペアの個数を1減らす
       tmp-=1
     cnt1+=tmp
   cnt1=cnt1//2 #上記の処理では同じペアが2回数えられているので個数を半分にする
   cnt2=0
   pos2=c2-1
   for i in range(c2): #各正数ごとに積が勝手に決めた値midよりも小さくなる正数の個数を求め足し合わせる(しゃくとり法)
     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 #各要素について、自身を2回選んだ場合の積が勝手に決めた値mid以下なら条件を満たすペアの個数を1減らす
     cnt2+=tmp
   cnt2=cnt2//2 #上記の処理では同じペアが2回数えられているので個数を半分にする
   cnt=cnt1+cnt2
   if cnt>=k: #勝手に決めた値mid以下の個数がK個以上であれば真の値はmid以下
     r=mid
   else: #そうでなければ真の値はmid以上
     l=mid
 print(r)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# N枚から２枚を選んだ積を小さい順に並び替えてK番目にくるものは何か
n = list(map(int, input().split()))  # N K
m = list(map(int, input().split()))  # A1 A2...AN

sekiList = []

for i1 in range(len(m)):
    for i2 in range(len(m)):
        if (i1 < i2):
            sekiList.append(m[i1] * m[i2])

sekiList = sorted(sekiList)

print(sekiList[n[1] - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,k=nl()
a=nl()
muls=[]
for i in range(n):
    for j in range(i+1,n):
        muls.append(a[i]*a[j])

muls.sort()
print(muls[k-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
x,y = map(int,input().split())
li = list(map(int,input().split()))
s = []
for i in range(len(li)):
    for k in range(len(li)):
        if i > k:
            s.append(li[k] * li[i])
s.sort()
print(s[y-1])

Submission status: Time Limit Exceeded

Solution code:
x,y = map(int,input().split())
li = list(map(int,input().split()))
s = []
for i in range(len(li)):
    for k in range(len(li)):
        if i > k:
          s.append(li[k] * li[i])
s.sort()
print(s[y-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
products = []
for i in combinations(a, 2):
    products.append(i[0] * i[1])
print(sorted(products)[k - 1])

Submission status: Time Limit Exceeded

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


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

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

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

while left+1 < right:
    mid = (left + right)//2

    if cnt(mid) < k:
        left = mid
    else:
        right = mid

print(int(right))

Submission status: Time Limit Exceeded

Solution code:
# 上からk番目の数がxである。
# xとなる数はk個以上　かつ　x＋1となる数はk-1個以下
# xとなる数がk個以上となるxの最大値
from bisect import bisect_left, bisect_right
import sys

input = sys.stdin.buffer.readline


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

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


def count(x):
    cnt = 0
    for i in range(n):
        a = A[i]
        if a > 0:
            gendo = x // a
            pos = bisect_right(A, gendo)
            cnt += pos
            if pos >= i + 1:
                cnt -= 1
        elif a < 0:
            gendo = (-x + (-a - 1)) // (-a)
            pos = bisect_left(A, gendo)
            cnt += n - pos
            if pos <= i:
                cnt -= 1
        else:
            if x < 0:
                cnt += 0
            else:
                cnt += n - 1
    return cnt // 2


# x = mid 以上のものをカウントしたい
while ok - ng > 1:
    mid = (ok + ng) // 2
    cnt = count(mid)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 上からk番目の数がxである。
# xとなる数はk個以上　かつ　x＋1となる数はk-1個以下
# xとなる数がk個以上となるxの最大値
from bisect import bisect_left, bisect_right
import sys

input = sys.stdin.buffer.readline


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

ng = -(10 ** 20)
ok = 10 ** 20


def count(x):
    cnt = 0
    for i in range(n):
        a = A[i]
        if a > 0:
            gendo = x // a
            pos = bisect_right(A, gendo)
            cnt += pos
            if pos >= i + 1:
                cnt -= 1
        elif a < 0:
            gendo = (-x + (-a - 1)) // (-a)
            pos = bisect_left(A, gendo)
            cnt += n - pos
            if pos <= i:
                cnt -= 1
        else:
            if x < 0:
                cnt += 0
            else:
                cnt += n - 1
    return cnt // 2


# x = mid 以上のものをカウントしたい
kouho = -(10 ** 10)
while ok - ng > 1:
    mid = (ok + ng) // 2
    cnt = count(mid)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

print(ok)