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())
inList = list(map(int, input().split()))

inList.sort()

if inList[0] * inList[N-1] <= 0:
  r_ba = inList[0] * inList[N-1] - 1
else:
  r_ba = inList[0] * inList[1] - 1

r_first = r_ba

l_ba = max(inList[0] * inList[1], inList[N-2] * inList[N-1]) + 1

if r_ba == l_ba:
  print(r_ba)
else:
  
  x = int(0.5 * (r_ba + l_ba))
  
  for time in range(int(0.5 * N * (N-1))):
    count = 0
    Ans = r_first
    
    for indx in range(N):
      if inList[indx] <= 0:
        for mulIndx in range(indx, -1, -1):
          if inList[indx] * inList[mulIndx] <= x:
            if indx != mulIndx:
              count += 1
              Ans = max(Ans, inList[indx] * inList[mulIndx])
          else:
            break
      elif inList[indx] > 0:
        for mulIndx in range(indx):
          if inList[indx] * inList[mulIndx] <= x:
            if indx != mulIndx:
              count += 1
              Ans = max(Ans, inList[indx] * inList[mulIndx])
          else:
            break
    
    count = count
#    print(r_ba, x, l_ba, count)
    
    if count == K:
      break
    elif count < K:
      r_ba = x
    else:
      l_ba = x
    
    x = int(0.5 * (r_ba + l_ba))

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(x) for x in input().split(' ')]
A = [int(x) for x in input().split(' ')]
r = sorted([A[i] * A[j] for i in range(N) for j in range(i+1, N)])
print(r[K-1])

Submission status: Time Limit Exceeded

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

inList.sort()

if inList[0] * inList[N-1] <= 0:
  r_ba = inList[0] * inList[N-1]
else:
  r_ba = inList[0] * inList[1]

r_first = r_ba

l_ba = max(inList[0] * inList[1], inList[N-2] * inList[N-1])

x = int(0.5 * (r_ba + l_ba))

for time in range(int(0.5 * N * (N-1))):
  count = 0
  Ans = r_first
  
  for indx in range(N):
    if inList[indx] <= 0:
      for mulIndx in range(N):
        if inList[indx] * inList[N-(mulIndx+1)] <= x:
          if indx != N-(mulIndx+1):
            count += 1
            Ans = max(Ans, inList[indx] * inList[N-(mulIndx+1)])
    elif inList[indx] > 0:
      for mulIndx in range(N):
        if inList[indx] * inList[  mulIndx] <= x:
          if indx != mulIndx:
            count += 1
            Ans = max(Ans, inList[indx] * inList[  mulIndx])
  
  count = int(count / 2)
#  print(r_ba, x, l_ba, count)
  
  if count == K:
    break
  elif count < K:
    r_ba = x
  else:
    l_ba = x
  
  x = int(0.5 * (r_ba + l_ba))

print(Ans)

Submission status: Time Limit Exceeded

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

ans = []
for i in range(N-1):
    for j in range(i+1, N):
        # print(f"{i} {j}")
        ans.append(nums[i] * nums[j])

ans = sorted(ans)

print(ans[K-1])

Submission status: Time Limit Exceeded

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

inList.sort()

if inList[0] * inList[N-1] <= 0:
  r_ba = inList[0] * inList[N-1]
else:
  r_ba = inList[0] * inList[1]

l_ba = max(inList[0] * inList[1], inList[N-2] * inList[N-1])

x = int(0.5 * (r_ba + l_ba))

for time in range(int(0.5 * N * (N-1))):
  count = 0
  
  for indx in range(N):
    if inList[indx] <= 0:
      for mulIndx in range(N):
        if inList[indx] * inList[N-(mulIndx+1)] <= x:
          if indx != N-(mulIndx+1):
            count += 1
        else:
          break
    elif inList[indx] > 0:
      for mulIndx in range(N):
        if inList[indx] * inList[  mulIndx] <= x:
          if indx != mulIndx:
            count += 1
        else:
          break
  
  count = int(count / 2)
#  print(r_ba, x, l_ba, count)
  
  if count == K:
    break
  elif count < K:
    r_ba = x
  else:
    l_ba = x
  
  x = int(0.5 * (r_ba + l_ba))

if inList[0] * inList[N-1] <= 0:
  Ans = inList[0] * inList[N-1]
else:
  Ans = inList[0] * inList[1]

for indx in range(N):
  if inList[indx] <= 0:
    for mulIndx in range(N):
      if ((inList[indx] * inList[N-(mulIndx+1)] <= x) and 
          (inList[indx] * inList[N-(mulIndx+1)] >= Ans)):
        if indx != N-(mulIndx+1):
          Ans = inList[indx] * inList[N-(mulIndx+1)]
  elif inList[indx] > 0:
    for mulIndx in range(N):
      if ((inList[indx] * inList[  mulIndx] <= x) and 
          (inList[indx] * inList[  mulIndx] >= Ans)):
        if indx != mulIndx:
          Ans = inList[indx] * inList[  mulIndx]

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

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

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

comb_array = list(itertools.combinations(array, 2))
    
product_array = []

for i in range(len(comb_array)):
    product_array.append(comb_array[i][0] * comb_array[i][1])

product_array.sort()

print(product_array[k - 1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

# 積がc以下となる組み合わせの数を求める
def n_comb_lt(c):
    n_comb = 0
    # A[i] > 0であるA[i]について
    target = c // A[A > 0]  # target以下の値がA[i]の相方
    n_comb += sum(np.searchsorted(A, target, side="right"))

    # A[i] == 0であるA[i]について
    n_comb += n * len(A[A == 0]) if c >= 0 else 0

    # A[i] < 0であるA[i]について
    target = -(-c // A[A < 0])
    n_comb += sum(n - np.searchsorted(A, target, side="left"))

    # 組み合わせのうち、A[i]*A[i]となっているものを引いて、2で割る
    n_comb -= len(A[A * A <= c])
    n_comb //= 2

    return n_comb

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

# k番目の積は、積がm未満となる組み合わせがk個未満となる最大のm
# ←→積が(m-1)以下となる組み合わせがk個未満となる最大のm
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]
sall = lambda: [x.strip() for x in sys.stdin.readlines()]

def main():
    n, k = na()
    xs = na()

    ys = []
    for i in range(n):
        for j in range(i + 1, n):
            ys.append(xs[i] * xs[j])

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


main()

Submission status: Time Limit Exceeded

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

inf = int(1e+18) + 1
l = -inf
r = inf

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

print(l)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def solve1(m, minus, plus):
    minus = np.sort(minus)
    plus = np.sort(plus)[::-1]
    # ２分探索
    lo = minus[0] * plus[0]
    hi = minus[-1] * plus[-1]
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0
        j = minus.shape[0] - 1
        for i in range(plus.shape[0]):
            while j >= 0 and minus[j] * plus[i] > mid:
                j -= 1
            if j > -1:
                num += j + 1
            else:
                break
        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j = minus.shape[0] - 1
    res = minus[0] * plus[0]
    for i in range(plus.shape[0]):
        while j >= 0 and minus[j] * plus[i] > hi:
            j -= 1
        if j > -1:
            res = max(res, minus[j] * plus[i])
        else:
            break
    return res

def solve2(m, minus, plus):
    minus = np.sort(minus)[::-1]
    plus = np.sort(plus)
    # ２分探索
    lo = 0
    hi = plus[-1] * plus[-2] if len(plus) > 1 else 0
    hi += minus[-1] * minus[-2] if len(minus) > 1 else 0
    while hi - lo > 1:
        mid = (lo + hi) // 2
        num = 0

        j1 = plus.shape[0] - 1
        if j1 > 0:
            for i in range(plus.shape[0]):
                while j1 >= 0 and plus[j1] * plus[i] > mid:
                    j1 -= 1
                if j1 > i:
                    num += j1 - i

        j2 = minus.shape[0] - 1
        if j2 > 0:
            for i in range(minus.shape[0]):
                while j2 >= 0 and minus[j2] * minus[i] > mid:
                    j2 -= 1
                if j2 > i:
                    num += j2 - i

        if num > m:
            hi = mid
        elif num < m:
            lo = mid
        else:
            hi = mid
            break

    j1 = plus.shape[0] - 1
    j2 = minus.shape[0] - 1
    res = 0
    if j1 > 0:
        for i in range(plus.shape[0]):
            while j1 >= 0 and plus[j1] * plus[i] > hi:
                j1 -= 1
            if j1 > i:
                res = max(res, plus[j1] * plus[i])
            else:
                break
    if j2 > 0:
        for i in range(minus.shape[0]):
            while j2 >= 0 and minus[j2] * minus[i] > hi:
                j2 -= 1
            if j2 > i:
                res = max(res, minus[j2] * minus[i])
            else:
                break
    return res


def main():
    N, K = [int(x) for x in input().split()]
    A = np.fromstring(input(), np.int64, sep=' ')
    minus = A[A < 0]
    zero = A[A == 0]
    plus = A[A > 0]

    n_minus = len(minus)
    n_zero = len(zero)
    n_plus = len(plus)

    p_minus = n_minus * n_plus
    p_zero = n_zero * (n_minus + n_plus) + n_zero * (n_zero - 1) // 2

    if K <= p_minus:
        ans = solve1(K, minus, plus)
        print(ans)
    elif K <= p_minus + p_zero:
        print(0)
    else:
        ans = solve2(K - p_minus - p_zero, minus, plus)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

cmb=itertools.combinations(a,2)
lst=[k[0]*k[1] for k in cmb]
lst.sort()
print(lst[k-1])

Submission status: Time Limit Exceeded

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

lst=[k[0]*k[1] for k in itertools.combinations(a,2)]
lst.sort()
print(lst[k-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
n, k = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

anega = [i for i in a if i < 0]
aposi = [i for i in a if i > 0]

lennega = len(anega)
lenposi = len(aposi)

anslist = []

if k <= (lennega * lenposi):
  for x, y in itertools.product(anega, aposi):
    anslist.append(x*y)
    anslist.sort()
  answer = anslist[k-1]
else:
  k -= lennega * lenposi
  azero = [i for i in a if i ==0]
  notzero = [i for i in a if i != 0]
  lenzero = len(azero)
  zeroresults = (lenzero * len(notzero)) + ((lenzero * (lenzero-1))//2)
  if k <= zeroresults:
    answer = 0
  else:
    k -= zeroresults
    if lennega >= 2:
      for x, y in itertools.combinations(anega, 2):
        anslist.append(x*y)
    for x, y in itertools.combinations(aposi, 2):
      anslist.append(x*y)
    anslist.sort()
    answer = anslist[k-1]

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input=sys.stdin.readline
#aのリストの中で２つ選び積がb未満の組み合わせがいくつあるかを出力する
def ok(a,b):
    ans=0
    n=len(a)
    for i in range(n):
        l=0
        r=len(a)-1
        
        if(a[i]*a[i]<b):
            ans-=1
        
        if(a[i]<0):
            if(a[l]*a[i]<b):
                ans+=n
                
                continue
            if(a[r]*a[i]>=b):
                ans+=0
                continue
        
            while(l+1<r):
                middle=(l+r)//2
                if(a[i]*a[middle]<b):
                    r=middle
                else:
                    l=middle
            ans+=n-r
        else:
            
            if(a[r]*a[i]<b):
                ans+=n
                continue
            if(a[l]*a[i]>=b):
                ans+=0
                continue           
            while(l+1<r):
                middle=(l+r)//2
                if(a[i]*a[middle]<b):
                    l=middle
                else:
                    r=middle   
                    
            ans+=l+1

    ans/=2
    
    return ans


NK=list(map(int,input().split()))
N=NK[0]
K=NK[1]
A=np.array(list(map(int,input().split())))
A=sorted(A)
l=-10**18
r=10**18

while(l+1<r):

    middle=(l+r)//2
    if(ok(A,middle)<K):
        l=middle
    else:
        r=middle

print(l)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
n, k = map(int, sys.stdin.readline().split())
a = sorted(list(map(int, sys.stdin.readline().split())))

anega = [i for i in a if i < 0]
aposi = [i for i in a if i > 0]

lennega = len(anega)
lenposi = len(aposi)

anslist = []

if k <= (lennega * lenposi):
  for x, y in itertools.product(anega, aposi):
    anslist.append(x*y)
    anslist.sort()
  answer = anslist[k-1]
else:
  k -= lennega * lenposi
  azero = [i for i in a if i ==0]
  notzero = [i for i in a if i != 0]
  lenzero = len(azero)
  if k <= (lenzero * len(notzero)) + ((lenzero * (lenzero-1))//2):
    answer = 0
  else:
    k -= (lenzero * len(notzero)) + ((lenzero * (lenzero-1))//2)
    if lennega >= 2:
      for x, y in itertools.combinations(anega, 2):
        anslist.append(x*y)
    for x, y in itertools.combinations(aposi, 2):
      anslist.append(x*y)
    anslist.sort()
    answer = anslist[k-1]

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
first_line = True
for line in sys.stdin:
  if first_line:
    N, K = line.split()
    N = int(N)
    K = int(K)
    first_line = False
  else:
    nums = list(map(int, line.split()))
    negative_count = 0
    positive_count = 0
    for num in nums:
      if num <0:
        negative_count += 1
      if num > 0:
        positive_count += 1
    zero_count = len(nums) - negative_count - positive_count
    n_res_count = negative_count  * positive_count
    p_res_count = negative_count * (negative_count-1)//2 + positive_count * (positive_count-1)//2
    z_res_count = N*(N-1)//2 - n_res_count - p_res_count
    if K <= n_res_count:
      # find in negative nums
      cands = []
      pos =[]
      neg = []
      for n in nums:
        if n>0:
          pos.append(n)
        elif n<0:
          neg.append(n)
      for p in pos:
        for n in neg:
          cands.append(p*n)
      print(sorted(cands)[K-1])
    elif K <= n_res_count + z_res_count:
      print(0)
    else:
      K -= (n_res_count + z_res_count)
      cands = []
      pos =[]
      neg = []
      for n in nums:
        if n>0:
          pos.append(n)
        elif n<0:
          neg.append(n)
      for i in range(len(pos)-1):
        for j in range(i+1, len(pos)):
          cands.append(pos[i]*pos[j])
      for i in range(len(neg)-1):
        for j in range(i+1, len(neg)):
          cands.append(neg[i]*neg[j])
      print(sorted(cands)[K-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

#aのリストの中で２つ選び積がb未満の組み合わせがいくつあるかを出力する
def ok(a,b):
    ans=0
    n=len(a)
    for i in range(n):
        l=0
        r=len(a)-1
        
        if(a[i]*a[i]<b):
            ans-=1
        
        if(a[i]<0):
            if(a[l]*a[i]<b):
                ans+=n
                
                continue
            if(a[r]*a[i]>=b):
                ans+=0
                continue
        
            while(l+1<r):
                middle=(l+r)//2
                if(a[i]*a[middle]<b):
                    r=middle
                else:
                    l=middle
            ans+=n-r
        else:
            
            if(a[r]*a[i]<b):
                ans+=n
                continue
            if(a[l]*a[i]>=b):
                ans+=0
                continue           
            while(l+1<r):
                middle=(l+r)//2
                if(a[i]*a[middle]<b):
                    l=middle
                else:
                    r=middle   
                    
            ans+=l+1

    ans/=2
    
    return ans


NK=list(map(int,input().split()))
N=NK[0]
K=NK[1]
A=np.array(list(map(int,input().split())))
A=sorted(A)
l=-10**18
r=10**18

while(l+1<r):

    middle=(l+r)//2
    if(ok(A,middle)<K):
        l=middle
    else:
        r=middle

print(l)

Submission status: Time Limit Exceeded

Solution code:
#aのリストの中で２つ選び積がb未満の組み合わせがいくつあるかを出力する
def ok(a,b):
    ans=0
    n=len(a)
    for i in range(n):
        l=0
        r=len(a)-1
        
        if(a[i]*a[i]<b):
            ans-=1
        
        if(a[i]<0):
            if(a[l]*a[i]<b):
                ans+=n
                
                continue
            if(a[r]*a[i]>=b):
                ans+=0
                continue
        
            while(l+1<r):
                middle=(l+r)//2
                if(a[i]*a[middle]<b):
                    r=middle
                else:
                    l=middle
            ans+=n-r
        else:
            
            if(a[r]*a[i]<b):
                ans+=n
                continue
            if(a[l]*a[i]>=b):
                ans+=0
                continue           
            while(l+1<r):
                middle=(l+r)//2
                if(a[i]*a[middle]<b):
                    l=middle
                else:
                    r=middle   
                    
            ans+=l+1

    ans/=2
    
    return ans


NK=list(map(int,input().split()))
N=NK[0]
K=NK[1]
A=list(map(int,input().split()))
A=sorted(A)
l=-10**18
r=10**18

while(l+1<r):

    middle=(l+r)//2
    if(ok(A,middle)<K):
        l=middle
    else:
        r=middle

print(l)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
lines = [l for l in sys.stdin]
l = lines[0].split(' ')
N, K = int(l[0]), int(l[1])
 
nums = [int(s) for s in lines[1].split(' ')]
n_dict = {int(s): {} for s in lines[1].split(' ')}
for n1 in n_dict:
  for n2 in n_dict:
    n_dict[n1][n2] = n1 * n2

rets = [n_dict[n1][n2] for idx, n1 in enumerate(nums[:-1]) for n2 in nums[idx+1:]]
rets.sort()
print(rets[K-1])

Submission status: Time Limit Exceeded

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

    from bisect import bisect_left, bisect_right


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

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

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

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

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

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

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

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





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




if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

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

A.sort()
neg = []
zero = []
pos = []

for i in A:
    if i<0:
        neg.append(-1*i)
    elif i==0:
        zero.append(i)
    else:
        pos.append(i)

neg.sort()
pos.sort()

def cul_zero(a):
    if a > 0:
        return int(len(zero) * (len(pos)+ len(neg)) + (len(zero)*(len(zero)-1))/2)
    else:
        return 0

def rev_index(l,i):
    return len(l)-i-1

def cul_pos2(a,l):
    res = 0
    right = -1
    for i in range(len(l)):
        while(right+1<len(l) and l[rev_index(l,i)]*l[right + 1]<a):
            right = right + 1
        
        if rev_index(l,i) <= right:
            res = res + rev_index(l,i)
        else:
            res = res + (right + 1)

    return res

def cul_pos(a):
    if a <= 0:
        return 0

    res1 = cul_pos2(a,neg)
    res2 =  cul_pos2(a,pos)
    return res1+res2

def cul_neg(a):
    if a >= 0:
        return len(neg)*len(pos)
    
    res = 0
    right = -1
    for i in range(len(neg)):
        while(right+1 != len(pos) and -1 * neg[rev_index(neg,i)] * pos[right+1] >= a ):
            right = right + 1
    
        res = res + (right+1)
    return len(neg)*len(pos) - res

def get_under_a_num(a):
    c_neg = cul_neg(a)
    c_pos = cul_pos(a)
    c_zero = cul_zero(a)
    c_sum = c_neg + c_pos + c_zero
    #print("(get under a:",a,")",c_neg,c_zero,c_pos,c_sum)
    return c_sum


def binary_search(left,right,k):
    while True:
        mid = int((left+right)//2)
        k_mid = get_under_a_num(mid)
        #print("(l,r,m=",left,right,mid,")",k_mid)
        if (left==right or left+1==right):
            return left
        if(k_mid < k):
            left = mid
        elif(k <= k_mid):
            right = mid


def solve1():
    l = []
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            l.append(A[i]*A[j])

    l.sort()

    print(l[K-1])
    return l

def solve2():
    res = binary_search(-1*(10**9+1)**2,(10**9+1)**2,K)
    #print("K,",K,res)
    #print("K-1",binary_search(-1*(10**20)-1,10**20,K-1))
    return res

if __name__=="__main__":
    print(solve2())

Submission status: Time Limit Exceeded

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

A.sort()
neg = []
zero = []
pos = []

for i in A:
    if i<0:
        neg.append(-1*i)
    elif i==0:
        zero.append(i)
    else:
        pos.append(i)

neg.sort()
pos.sort()

def cul_zero(a):
    if a > 0:
        return int(len(zero) * (len(pos)+ len(neg)) + (len(zero)*(len(zero)-1))/2)
    else:
        return 0

def rev_index(l,i):
    return len(l)-i-1

def cul_pos2(a,l):
    res = 0
    right = -1
    for i in range(len(l)):
        while(right+1<len(l) and l[rev_index(l,i)]*l[right + 1]<a):
            right = right + 1
        
        if rev_index(l,i) <= right:
            res = res + rev_index(l,i)
        else:
            res = res + (right + 1)

    return res

def cul_pos(a):
    if a <= 0:
        return 0

    res1 = cul_pos2(a,neg)
    res2 =  cul_pos2(a,pos)
    return res1+res2

def cul_neg(a):
    if a >= 0:
        return len(neg)*len(pos)
    
    res = 0
    right = -1
    for i in range(len(neg)):
        while(right+1 != len(pos) and -1 * neg[rev_index(neg,i)] * pos[right+1] >= a ):
            right = right + 1
    
        res = res + (right+1)
    return len(neg)*len(pos) - res

def get_under_a_num(a):
    c_neg = cul_neg(a)
    c_pos = cul_pos(a)
    c_zero = cul_zero(a)
    c_sum = c_neg + c_pos + c_zero
    #print("(get under a:",a,")",c_neg,c_zero,c_pos,c_sum)
    return c_sum


def binary_search(left,right,k):
    mid = int((left+right)//2)
    k_mid = get_under_a_num(mid)
    #print("(l,r,m=",left,right,mid,")",k_mid)
    if (left==right or left+1==right):
        return left
    if(k_mid < k):
        return binary_search(mid,right,k)
    if(k <= k_mid):
        return binary_search(left,mid,k)


def solve1():
    l = []
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            l.append(A[i]*A[j])

    l.sort()

    print(l[K-1])
    return l

def solve2():
    res = binary_search(-1*(10**9+1)**2,(10**9+1)**2,K)
    #print("K,",K,res)
    #print("K-1",binary_search(-1*(10**20)-1,10**20,K-1))
    return res

if __name__=="__main__":
    print(solve2())

Submission status: Time Limit Exceeded

Solution code:
import sys
 
lines = [l for l in sys.stdin]
l = lines[0].split(' ')
N, K = int(l[0]), int(l[1])
 
nums = [int(s) for s in lines[1].split(' ')]
n_dict = {int(s): 0 for s in lines[1].split(' ')}
result_dict = {int(s): {} for s in lines[1].split(' ')}
for idx, n1 in enumerate(n_dict.keys()):
  for idy, n2 in enumerate(n_dict.keys()):
    result_dict[n1][n2] = n1 * n2

rets = []
for idx, n1 in enumerate(nums[:-1]):
  for idy, n2 in enumerate(nums[idx+1:]):
    rets.append(result_dict[n1][n2])
rets.sort()
print(rets[K-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
 
lines = [l for l in sys.stdin]
l = lines[0].split(' ')
N, K = int(l[0]), int(l[1])
 
nums = [int(s) for s in lines[1].split(' ')]
 
rets = [n1 * n2 for idx, n1 in enumerate(nums[:-1]) for idy, n2 in enumerate(nums[idx+1:])]
rets.sort()
print(rets[K-1])