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:
f=lambda:map(int,input().split())
n,k=f()
l=sorted(f())
INF=10**18+1
from bisect import *
tl=bisect_left(l,0)
tr=bisect(l,0)
tm,tz,tp=tl,tr-tl,n-tr
cm=tm*tp
cz=tz*(n*2-tz-1)//2
cp=(tm*(tm-1)+tp*(tp-1))//2
lm=l[:tl]
lma=list(map(lambda x:-x,lm))[::-1]
lp=l[tr:]
def bs(a,l,r):
  while r-l>1:
    c=(l+r)//2
    if i*a[c]<m: l=c
    else: r=c
  return r
if 0<k-cm<=cz:
  print(0)
elif k<=cm:
  l,r=-INF,0
  while r-l>1:
    m=(l+r)//2
    s=0
    for i in lp:
      s+=bs(lm,-1,tm)
    if s<k: l=m
    else: r=m
  print(l)
else:
  l,r=0,INF
  while r-l>1:
    m=(l+r)//2
    s=0
    for i in lma:
      s+=bs(lma,-1,tm)
      if i*i<m: s-=1
    for i in lp:
      s+=bs(lp,-1,tp)
      if i*i<m: s-=1
    if cm+cz+s//2<k: l=m
    else: r=m
  print(l)

Submission status: Time Limit Exceeded

Solution code:
f=lambda:map(int,input().split())
n,k=f()
l=sorted(f())
INF=10**18+1
from bisect import *
tl=bisect_left(l,0)
tr=bisect(l,0)
tm,tz,tp=tl,tr-tl,n-tr
cm=tm*tp
cz=tz*(n*2-tz-1)//2
cp=(tm*(tm-1)+tp*(tp-1))//2
lm=l[:tl]
lma=list(map(lambda x:-x,lm))[::-1]
lp=l[tr:]
if 0<k-cm<=cz:
  print(0)
elif k<=cm:
  l,r=-INF,0
  while r-l>1:
    m=(l+r)//2
    s=0
    for i in lp:
      li,ri=-1,tm
      while ri-li>1:
        mi=(li+ri)//2
        if i*lm[mi]<m: li=mi
        else: ri=mi
      s+=ri
    if s<k: l=m
    else: r=m
  print(l)
else:
  l,r=0,INF
  while r-l>1:
    m=(l+r)//2
    s=0
    for i in lma:
      li,ri=-1,tm
      while ri-li>1:
        mi=(li+ri)//2
        if i*lma[mi]<m: li=mi
        else: ri=mi
      s+=ri
      if i*i<m: s-=1
    for i in lp:
      li,ri=-1,tp
      while ri-li>1:
        mi=(li+ri)//2
        if i*lp[mi]<m: li=mi
        else: ri=mi
      s+=ri
      if i*i<m: s-=1
    if cm+cz+s//2<k: l=m
    else: r=m
  print(l)

Submission status: Time Limit Exceeded

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

a.sort()

def check(t):
    j = n - 1 if t > 0 else 0
    res = 0
    f = 1

    cond = lambda x, t, f:x <= t if f * t > 0 or (t == 0 and f == -1) else x > t
    shift = lambda x, t:x-1 if t > 0 else x+1
    count = lambda x, n, f:n-x if f == 1 else x

    for ai in a:
        if f == 1 and ai > 0:
            f = -1
            j = n - 1 if t > 0 else 0
        if ai:
            while j >= 0 and j < n and cond(ai * a[j], t, f):
                j = shift(j, t)
            if t > 0:
                res += count(j+1, n, f)
            else:
                res += count(j, n, f)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2
            

m = max(max(a)**2, min(a)**2)
l = -m
r = m

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

memo_r = {}
memo_l = {}

def check(t):
    res = 0
    tr = math.sqrt(abs(t))
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                if aj not in memo_r:
                    memo_r[aj] = bisect_right(a, aj)
                res += memo_r[aj]
            else:
                if t % ai:
                    if aj not in memo_r:
                        memo_r[aj] = bisect_right(a, aj)
                    res += n - memo_r[aj]
                else:
                    if aj not in memo_l:
                        memo_l[aj] = bisect_left(a, aj)
                    res += n - memo_l[aj]
        else:
            if t >= 0:
                res += n
        if t >= 0 and abs(ai) <= tr:
            res -= 1
    return res // 2


m = max(max(a)**2, min(a)**2)
l = -m
r = m

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(t):
    res = 0
    tr = math.sqrt(abs(t))
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                res += bisect_right(a, aj)
            else:
                if t % ai:
                    res += n - bisect_right(a, aj)
                else:
                    res += n - bisect_left(a, aj)
        else:
            if t >= 0:
                res += n
        if t >= 0 and abs(ai) <= tr:
            res -= 1
    return res // 2


m = max(max(a)**2, min(a)**2)
l = -m
r = m

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(t):
    res = 0
    tr = math.sqrt(abs(t))
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                res += bisect_right(a, aj)
            else:
                if t % ai:
                    res += n - bisect_right(a, aj)
                else:
                    res += n - bisect_left(a, aj)
        else:
            if t >= 0:
                res += n
        if t >= 0 and abs(ai) <= tr:
            res -= 1
    return res // 2

l = - 10 ** 18
r = 10 ** 18

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(t):
    res = 0
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                res += bisect_right(a, aj)
            else:
                if t % ai:
                    res += n - bisect_right(a, aj)
                else:
                    res += n - bisect_left(a, aj)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2

l = - 10 ** 18
r = 10 ** 18

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

Submission status: Time Limit Exceeded

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

def check(t):
    res = 0
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                res += bisect.bisect_right(a, aj)
            else:
                if t % ai:
                    res += n - bisect.bisect_right(a, aj)
                else:
                    res += n - bisect.bisect_left(a, aj)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2

l = - 10 ** 18
r = 10 ** 18

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ma = [sorted(list(map(lambda y: y*x, a))) for x in a]

def evl(x):
    cnt = 0
    for i in range(n):
        if a[i] == 0:
            cnt += n-i-1 if x >= 0 else 0
            continue
        if a[i] > 0:
            cnt += max(0, bisect_right(ma[i], x)-(i+1))
        else:
            cnt += min(n-i-1, bisect_right(ma[i], x))
    return cnt >= k

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

Submission status: Time Limit Exceeded

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


"""
最終的に、hiは条件を満たす最小の値となり、loは条件を満たさない最大の値になる
"""
hi = 10**18 + 1
lo = -1 * 10**18 -1

while hi - lo > 1:
    mid = (hi + lo) // 2
    cnt_under_mid = 0
    cnt_duplicate = 0

    """
    小さいものからK番目の値が欲しいので、
    Aの要素それぞれについて、積を取ってmid以下になるものの個数を合算して、
    ・K個以上の場合、midの値がまだ大きいのでhiをmidまで下げる（例えばmid=10**1000　以下の個数を数えるとすると、全てがこれ以下になるのでhi大きすぎるから下げる、みたいな）
    ・K個未満の場合、midの値が小さいので、loをmidまであげる（mid=-1*10**1000だとすると、どれもこの値以下にならないので、現行のlo~midまでは条件を満たさない）
    """
    # 
    for a in A:
        # a > 0であれば、a * A[m] >= mid を満たす最小のmについて、A[m~N-1]がaと積を取ってmid以上になる（積が単調増加になるから）
        if a > 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                
                if a * A[m] <= mid:
                    l = m
                else:
                    r = m
            # a * A[0:r-1]までのr個は、積をとってもmid未満
            cnt_under_mid += r
        # a < 0であれば、a * A[m] >= mid を満たす最大のmについて、A[0~m]がaと積を取ってmid以上になる（積が単調減少になるから）
        elif a < 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                if a * A[m] <= mid:
                    # rより後ろにあるものと積をとってもmid未満
                    r = m
                else:
                    l = m
            # a * A[r~N-1]のN-r個は、積をとってもmid未満
            cnt_under_mid += N - r 
        # a = 0 の場合、何と積をとっても0になるので、mid以下の個数を探すので、mid>=0であれば全てのAについて条件を満たす
        elif mid >= 0:
            cnt_under_mid += N

        # ↑で求めたものはA[i] * A[i]もペアとして扱ってるので、それがmid以下になる場合は取り除く
        if a * a <= mid:
            cnt_duplicate += 1

    cnt = (cnt_under_mid - cnt_duplicate) // 2

    #print("---", hi,lo,mid)
    # Kを超える場合は、midが大きすぎる（XXX以下の個数を求めてるので、hiをおろしてくる）
    if cnt >= K:
        hi = mid
    
    else:
        lo = mid




print(hi)

Submission status: Time Limit Exceeded

Solution code:

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


"""
最終的に、hiは条件を満たす最小の値となり、loは条件を満たさない最大の値になる
"""
hi = 10**20
lo = -1 * 10**20

while hi - lo > 1:
    mid = (hi + lo) // 2
    cnt_under_mid = 0
    cnt_duplicate = 0

    """
    小さいものからK番目の値が欲しいので、
    Aの要素それぞれについて、積を取ってmid以下になるものの個数を合算して、
    ・K個以上の場合、midの値がまだ大きいのでhiをmidまで下げる（例えばmid=10**1000　以下の個数を数えるとすると、全てがこれ以下になるのでhi大きすぎるから下げる、みたいな）
    ・K個未満の場合、midの値が小さいので、loをmidまであげる（mid=-1*10**1000だとすると、どれもこの値以下にならないので、現行のlo~midまでは条件を満たさない）
    """
    # 
    for a in A:
        # a > 0であれば、a * A[m] >= mid を満たす最小のmについて、A[m~N-1]がaと積を取ってmid以上になる（積が単調増加になるから）
        if a > 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                
                if a * A[m] <= mid:
                    l = m
                else:
                    r = m
            # a * A[0:r-1]までのr個は、積をとってもmid未満
            cnt_under_mid += r
        # a < 0であれば、a * A[m] >= mid を満たす最大のmについて、A[0~m]がaと積を取ってmid以上になる（積が単調減少になるから）
        elif a < 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                if a * A[m] <= mid:
                    # rより後ろにあるものと積をとってもmid未満
                    r = m
                else:
                    l = m
            # a * A[r~N-1]のN-r個は、積をとってもmid未満
            cnt_under_mid += N - r 
        # a = 0 の場合、何と積をとっても0になるので、mid以下の個数を探すので、mid>=0であれば全てのAについて条件を満たす
        elif mid >= 0:
            cnt_under_mid += N

        # ↑で求めたものはA[i] * A[i]もペアとして扱ってるので、それがmid以下になる場合は取り除く
        if a * a <= mid:
            cnt_duplicate += 1

    cnt = (cnt_under_mid - cnt_duplicate) // 2

    #print("---", hi,lo,mid)
    # Kを超える場合は、midが大きすぎる（XXX以下の個数を求めてるので、hiをおろしてくる）
    if cnt >= K:
        hi = mid
    
    else:
        lo = mid




print(hi)

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_start = bisect_right(A, 0)
 
positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)
 
negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)


# 答えが負の場合
if K <= negative_pairs_cnt:
    # にぶたん: X以下になるペアがK個以上あるか？
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)
 
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X
 
    print(ok)

# 答えが0の場合
elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)
 
# 答えが正の場合
else:
    # にぶたん: X以下になるペアがK個以上あるか？
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0
 
        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)
 
        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1
 
            or_higher_cnt += max(0, r - l)
 
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X
 
    print(ok)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#尺取り法

from bisect import bisect_left, bisect_right

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

    nega_end = bisect_left(A, 0)
    posi_start = bisect_right(A, 0)

    posi_cnt = N - posi_start
    nega_cnt = nega_end
    zero_cnt = N - (posi_cnt + nega_cnt)

    nega_pairs_cnt = posi_cnt * nega_cnt
    zero_pairs_cnt = zero_cnt * (posi_cnt + nega_cnt) + (zero_cnt * (zero_cnt-1) // 2)

    if K <= nega_pairs_cnt:
        ok, ng = 0, -10 ** 18

        while abs(ok - ng) > 1:

            X = (ok + ng) // 2
            or_higher_cnt, r = 0, posi_start

            for l in range(nega_end):
                while (r < N) and (A[l] * A[r] > X):
                    r += 1
                or_higher_cnt += posi_cnt - (r - posi_start)

            if or_higher_cnt >= K:
                ok = X
            else:
                ng = X
            #print(ok, ng)
        print(ok)

    elif nega_pairs_cnt < K <= nega_pairs_cnt + zero_pairs_cnt:
        print(0)
        return
    else:
        K -= (nega_pairs_cnt + zero_pairs_cnt)
        ok, ng = 10 ** 18, 0
        while abs(ok - ng) > 1:
            X = (ok + ng) // 2
            or_higher_cnt = 0
            r = N - 1
            for l in range(posi_start, N):
                while (r < N) and (A[l] * A[r] > X) and (l < r):
                    r -= 1
                or_higher_cnt += max(0, r - l)

            l = 0
            for r in range(nega_end - 1, -1, -1):
                while (l < N) and (A[l] * A[r] > X) and (l < r):
                    l += 1

                or_higher_cnt += max(0, r - l)

            if or_higher_cnt >= K:
                ok = X
            else:
                ng = X
        print(ok)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = map(int, input().split())
aa = np.array(list(map(int, input().split())))
bb = [aa[i]*aa[j] for i in range(len(aa)) for j in range(i+1, len(aa))]
bb.sort()
print(bb[k-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
iuput=sys.stdin.readline
n,k=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
s=bisect.bisect_left(A,0,lo=0,hi=len(A))
t=bisect.bisect_right(A,0,lo=0,hi=len(A))
An=A[0:s]
Ap=A[t:n]
if k<=s*(n-t):
  #二分探査
  ng=-10**19
  ok=1
  while ok-ng!=1:
    #積がmid以下になる組み合わせの数をカウント
    mid=(ok+ng)//2
    c=0
    j=0
    for i in range(s):
      if j<n-t:
        while An[i]*Ap[j]>mid:
          j=j+1
          if j==n-t:
            break
      if An[i]*Ap[-1]>mid:
        j=n-t
      c=c+(n-t-j)
    if c<k:
      ng=mid
    else:
      ok=mid
  print(ok)
elif k<=n*(n-1)//2-((n-t)*(n-t-1)//2)-s*(s-1)//2:
  print(0)
else:
  k=n*(n-1)//2-k+1#大きい順にk番目
  Ann=[0]*s
  for i in range(s):
    Ann[i]=An[i]*-1
  Ann=Ann[::-1]
  App=[0]*(n-t)
  for i in range(n-t):
    App[i]=Ap[i]*-1
  App=App[::-1]
  ng=-10**19
  ok=1
  while ok-ng!=1:
    #積がmid以下になる組み合わせの数をカウント
    mid=(ok+ng)//2
    c=0
    j=0
    for i in range(s):
      if j<s:
        while An[i]*Ann[j]>mid:
          j=j+1
          if j==s:
            break
      if An[i]*Ann[-1]>mid:
        j=s
      c=c+(s-j)
    cc=0
    for i in range(s):
      if An[i]*A[i]*-1<=mid:
        cc=cc+1
    j=0
    for i in range(n-t):
      if j<n-t:
        while App[i]*Ap[j]>mid:
          j=j+1
          if j==n-t:
            break
      if App[i]*Ap[-1]>mid:
        j=n-t
      c=c+(n-t-j)
    for i in range(n-t):
      if Ap[i]*Ap[i]*-1<=mid:
        cc=cc+1
    c=(c-cc)//2
    if c<k:
      ng=mid
    else:
      ok=mid
  print(-1*ok)

Submission status: Time Limit Exceeded

Solution code:
def do():
    n,m=map(int,input().split())
    l=list(map(int,input().split()))
    l1=[]
    # l=sorted(l)
    for i in range(n):
        for j in range(i+1,n):
            l1.append(l[i]*l[j])
    l1=sorted(l1)
    return l1[m-1]
print(do())

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

p = []
n = []
z = 0
for v in a:
    if v > 0:
        p.append(v)
    elif v == 0:
        z += 1
    else:
        n.append(v)
l_p = len(p)
l_n = len(n)

num_negative = l_p * l_n
if z != 0:
    num_zero = int((l_p + l_n) * z + z * (z-1) / 2)
else:
    num_zero = 0
num_positive = int(l_p * (l_p-1) / 2 + l_n * (l_n-1) / 2)

tmp = []
if k <= num_negative:
    for i in p:
        for j in n:
            tmp.append(i*j)
    ans = sorted(tmp)[k-1]
elif num_negative < k <= num_negative + num_zero:
    ans = 0
else:
    index = k - num_negative - num_zero - 1
    for i in range(l_p):
        for j in range(i+1, l_p):
            tmp.append(p[i]*p[j])
    for i in range(l_n):
        for j in range(i+1, l_n):
            tmp.append(n[i]*n[j])
    ans = sorted(tmp)[index]

print(ans)

Submission status: Time Limit Exceeded

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

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

mul_list = []
for i in range(N):
    for j in range(i+1, N):
        mul_list.append(a_list[i] * a_list[j])

print(merge_sort(mul_list)[K-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.sort(np.array(input().split(),np.int64))
B = np.copy(A)[::-1]
xl = -1000000000000000001
xr = -xl
X = (xl+xr)//2

while xr-xl > 1:
    tmpK = 0
    for i in range(N):
        if A[i] < 0:
            l = -1
            r = N-1-i
            t = (l+r)//2
            while r-l > 1:
                if A[i]*B[t] <= X:
                    l = t
                else:
                    r = t
                t = (l+r)//2
            tmpK += r
        else:
            l = i
            r = N
            t = (l+r)//2
            while r-l > 1:
                if A[i]*A[t] <= X:
                    l = t
                else:
                    r = t
                t = (l+r)//2
            tmpK += r-i-1
    if tmpK < K:
        xl = X
    else:
        xr = X
    X = (xl+xr)//2

print(xr)

Submission status: Time Limit Exceeded

Solution code:
#積がmid以下になるようなペアの数を求めるのが難しいところだが、うまく解決している
N, K = map(int, input().split())
zero, plus, minus = 0, [], []
for x in map(int, input().split()):
    if x == 0:
        zero += 1
    elif x > 0:
        plus.append(x)
    else:
        minus.append(x)

#絶対値が小さい順にソートしておく
plus.sort()
minus.sort(reverse=True)

#二分探索する
#cntは積がmid以下になるようなペアの数
ok, ng = 10**19, -10**19
while ok - ng > 1:
    mid = (ok + ng) // 2
    cnt = 0
    #この条件分岐で積が0になるペアの数を反映
    if mid >= 0:
        cnt += zero * (zero-1) // 2 + zero * (N-zero)

    if mid > 0:
        cnt += len(minus) * len(plus)
        #両方プラスと両方マイナスをまとめて扱っている
        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: Time Limit Exceeded

Solution code:
'''たのん「決め打ち2分探索」
各ペアの積を順番に並べたときのK番目の値を愚直に計算すると、
積の計算にO(N^2)、それらの値をソートするのにO(N^2logN)かかってしまう。
そこで考え方を変え、勝手に決めた値XがK番目の値になるかどうかを
判定することを考えてみます。
勝手に決めた値Xよりも積が小さくなるペアの個数を数え、
それがK個以上であればK番目の値はXより小さく、
K個未満であればK番目の値はXより大きいことが分かります。
1回の判定にかかる計算量は、2数の積の片方を決めたとき
もう片方として取ってこられる個数をしゃくとり法によって求めると
トータルO(N)、2分探索によって求めると1要素あたりの計算量がO(logN)なので
トータルO(NlogN)となります。
また判定を行う回数は、制約より0<=|Ai|<=10^9なので、
初期値として0と10^18+1を与えれば十分で、
判定の回数は高々log(10^18)回程度だと分かります。
今回の制約は-10^9<=Ai<=10^9より、
小さい方からK番目の要素の値が負になるか、それとも0になるか、
それとも正になるかで場合分けをして考える必要があります。
まずK番目の要素の値が負になる場合、2数の積の組み合わせとしては、
(負の数)x(正の数)のみがあり得ます。
このときは、負の数からある要素を取ってきたときもう片方として
正の数から取ってこられる個数を求めればよいです。
ただし以下の実装では負数のマイナスを取って計算しているため
2数の積の大小が逆転し、(負の数)x(正の数)の小さいほうからK番目の数は、
(負の数の絶対値)x(正の数)の小さいほうから
(負の数の個数-K)番目の数(=大きいほうからK番目の数)に相当します。
次にK番目の要素の値が正になる場合、2数の積の組み合わせとしては、
(負の数)x(負の数)と(正の数)x(正の数)の2つがあり得ます。
このときは、負の数からある要素を取ってきたとき
もう片方として負の数から取ってこられる個数と、
正の数からある要素を取ってきたとき、もう片方として正の数から
取ってこられる個数をそれぞれ求めて足し合わせればよいです。
ただし、同じ要素を2回選ぶ場合が含まれてしまっていることと、
そして各ペアが2回数えられることに注意し、個数を修正する必要があります。
'''

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:
import bisect

def main():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()

    INF = (10**18)+1

    l = -INF
    r = INF

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

        total //= 2
        if total < k:
            l = x
        else:
            r =x 
        
    print(l)

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

    ans = []

    for i in range(n):
        for j in range(i+1,n):
            x = a[i]*a[j]
            bisect.insort(ans,x)

    print(ans[k-1])

main()

Submission status: Time Limit Exceeded

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

from heapq import *
h = []
cnt = 0
for i in range(len(aa)):
    for j in range(i+1,len(aa)):
        heappush(h,-aa[i]*aa[j])
        cnt += 1
        if cnt > k:
            heappop(h)
print(-heappop(h))

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
from subprocess import*
call(("pypy3","-c","""
def main():
    N,K = map(int, input().split())
    l = list(map(int, input().split()))
    s = []
    for i in range(0,N):
        for j in range(i+1,N):
            s.append(l[i]*l[j])
    s.sort()
    print(s[K-1])


main()
"""))

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):
    b.append(A[i]*A[j])
c=sorted(b)
print(c[K-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
ini = lambda: int(input())
inl = lambda: list(map(int, input().split()))
ins = lambda: input().strip()

N, K = inl()
A = inl()

import itertools

ps = []
for c in itertools.combinations(A, 2):
	ps.append(c[0] * c[1])
ps.sort()
print(ps[K-1])

Submission status: Time Limit Exceeded

Solution code:
import functools
N,K = map(int, input().split())
@functools.lru_cache(None)
def main(N,K):
    l = list(map(int, input().split()))
    s = []
    for i in range(0,N):
        for j in range(i+1,N):
            s.append(l[i]*l[j])
    s.sort()
    return(s[K-1])
print(main(N,K))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
l = list(map(int, input().split()))
s = []
for i in range(0,N):
    for j in range(i+1,N):
        s.append(l[i]*l[j])
s.sort()
print(s[K-1])

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 a:
  if i>0: ap.append(i)
  elif i<0: an.append(-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)
elif k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
        mid=(ok+ng)//2
        cnt=0
        for i in an:
            if mid%i!=0: cnt+=np-bisect_left(ap,mid//i+1)
            else: cnt+=np-bisect_left(ap,mid//i)
        if cnt>=k: ok=mid
        else: ng=mid
    print(-ok)
else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    ok=10**18
    ng=0
    while ok-ng>1:
        mid=(ok+ng)//2
        cnt1,cnt2=0,0
        if np>=2:
            for i in ap:
                cnt1+=bisect_right(ap,mid//i)
                if i**2<=mid: cnt1-=1
        if nn>=2:
            for i in an:
                cnt2+=bisect_right(an,mid//i)
                if i**2<=mid: cnt2-=1
        if cnt1//2+cnt2//2>=k: ok=mid
        else: ng=mid
    print(ok)