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()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = max(A[-1]**2+10,A[0]**2+10)
l = A[0]*A[-1]-10
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu):
      while True:
        if cou>=plu-i-1:
          num+=plu-i-1
          break
        x = A_plu_rev[i]*A_plu[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    cou = 0
    for i in range(0,mi):
      while True:
        if cou>=mi-i-1:
          num+=mi-i-1
          break
        x = A_mi[i]*A_mi_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break

    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    cou = 0
    for a in A_mi_rev:
      while True:
        if cou==plu:
          num+=cou
          break
        x = a*A_plu_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r = m
    else:
      l = m
      
print(l)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0  # かけたら m 未満になるペア数（負なので絶対値としては大きい）
    j = 0
    for a in neg:
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if len_pos == j:
            break
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    less_eq = 0  # かけたら m 以下になるペア数
    j = 0
    for i in range(len_pos - 1, -1, -1):
        d = m // pos[i]
        while j < len_pos and pos[j] <= d:
            j += 1
        if j == len_pos:
            less_eq += len_pos * (i + 1)
            break
        less_eq += j

    j = 0
    for i in range(len_neg - 1, -1, -1):
        d = m // neg[i]
        while j < len_neg and neg[j] <= d:
            j += 1
        if j == len_neg:
            less_eq += len_neg * (i + 1)
            break
        less_eq += j

    m_sqrt = int(m ** 0.5)
    less_eq -= bisect(pos, m_sqrt)
    less_eq -= bisect(neg, m_sqrt)

    less_eq //= 2

    return less_eq < k


def solve(n, k, aaa):
    pos, neg = [], []
    for a in aaa:
        if a > 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg):
                l = m
            else:
                r = m
        return r


n, k = map(int, sys.stdin.buffer.readline().split())
aaa = list(map(int, sys.stdin.buffer.readline().split()))
aaa.sort()
print(solve(n, k, aaa))

Submission status: Time Limit Exceeded

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

pos = []
neg = []
zero = []

A.sort()

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] == 0:
        zero.append(A[i])
    else:
        neg.append(A[i])
        
import bisect


#条件に合うものを重複して数えて後から重複しない組み合わせに変換
def fun(x):
    count = 0
    #xが0より大きいとき、後ろにある0は何個あるか
    if x >= 0:
        count += len(zero)*N
    #xを正で割ったとき、Aの中に何個それより大きいものがあるか
    for i in range(len(pos)):
        count += bisect.bisect_right(A,x//pos[i])
    #xを負で割ったとき、Aの中に何個それより小さいものがあるか(符合が逆転)
    #x+1にする(同じ数字がAにあるから)
    for i in range(len(neg)):
        count += N - bisect.bisect_right(A,(x+1)//neg[i])
    #条件に合う同じ要素を選ぶものを除く    
    for i in range(len(A)):
        if x >= A[i]**2:
            count-=1
    #半分にすれば重複しない組み合わせになる        
    return count//2

left = -10**18
right = 10**18

#二分探索する
while right - left > 1:
    mid = (left+right)//2
    
    if fun(mid) >= K:
        right = mid
    else:
        left = mid
        
print(right)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0  # かけたら m 未満になるペア数
    j = 0
    for a in neg:
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if len_pos == j:
            break
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    less_eq = 0  # かけたら m 以下になるペア数
    j = 0
    for i in range(len_pos - 1, -1, -1):
        a = pos[i]
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if j == len_pos:
            less_eq += len_pos * (i + 1)
            break
        less_eq += j

    j = 0
    for i in range(len_neg - 1, -1, -1):
        a = neg[i]
        d = m // a
        while j < len_neg and neg[j] <= d:
            j += 1
        if j == len_neg:
            less_eq += len_neg * (i + 1)
            break
        less_eq += j

    m_sqrt = int(m ** 0.5)
    less_eq -= bisect(pos, m_sqrt)
    less_eq -= bisect(neg, m_sqrt)

    less_eq //= 2

    return less_eq < k


def solve(n, k, aaa):
    pos = [a for a in aaa if a > 0]
    neg = [a for a in aaa if a < 0]
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg):
                l = m
            else:
                r = m
        return r


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(n, k, aaa))


def debug():
    mul = []
    for i in range(n):
        for j in range(i + 1, n):
            mul.append(aaa[i] * aaa[j])
    mul.sort()
    print(mul[k - 1], mul)

# debug()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left as bl
    from bisect import bisect_right as br

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

    inf = 10**18+1

    ok = -inf
    ng = inf
    start_0 = bl(a, 0)
    start_1 = bl(a, 1)

    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        cnt = 0
        for i in a[:start_0]:
            if mid % i == 0:
                cnt += n - br(a, mid//i)
            else:
                cnt += n - br(a, mid//i + 0.5)
        for i in a[start_1:]:
            if mid % i == 0:
                cnt += bl(a, mid//i)
            else:
                cnt += bl(a, mid//i + 0.5)
        if mid > 0:
            cnt += n * (start_1 - start_0)
        cnt -= len([None for i in a if i*i < mid])
        if cnt//2 < k:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def cnt_val(a, b, x):
    ai = 1 if a == b else 0
    ans = 0
    for i in range(len(a) - ai):
        xa = a[i]

        lo, hi = i+1 if ai else 0, len(b)
        lo0 = lo

        #print(i, xa, x)

        while lo < hi:
            mid = (lo + hi) // 2
            x1 = b[mid] * xa
            #print(i, (lo, hi), x1)

            if x1 <= x:
                lo = mid + 1
            else:
                hi = mid
        #print("x", (lo, lo0))
        ans += lo - lo0
    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        #print(A[0], A[2])
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        #print((lo, hi), K1)
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid)
            #print((lo, hi), mid, k, K1)
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    #print(A[0], A[2], a0, a1, K3)
    lo, hi = 0, 10**18
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid) + cnt_val(A[2], A[2], mid)
        #print((lo, hi), k3, K3)
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

pos = []
neg = []
zero = []

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] == 0:
        zero.append(A[i])
    else:
        neg.append(A[i])
        
A.sort()

import bisect

def fun(x):
    count = 0
    
    if x >= 0:
        count += len(zero)*N
        
    for i in range(len(pos)):
        count += bisect.bisect_right(A,x//pos[i])
        
    for i in range(len(neg)):
        count += N - bisect.bisect_right(A,(-x-1)//(-neg[i]))
        
    for i in range(len(A)):
        if x >= A[i]**2:
            count-=1
            
    return count//2

left = -10**18
right = 10**18

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

ans = sorted(a * b for a, b in combinations(A, 2))[K-1]

print(ans)

Submission status: Time Limit Exceeded

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

times = []

for n in range(N-1):
    for i in range(N-n-1):
        times.append(nums[n] * nums[i+n+1])

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

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n, k = input().split()
    k = int(k)
    val = input().split()
    a = [int(s) for s in val]
    b = []
    for i in range(len(a)):
        for j in range(i+1, len(a)):
            b.append(a[i] * a[j])
    b.sort()
    print(b[k-1])

Submission status: Time Limit Exceeded

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

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

while l + 1 < r:
    x = (l + r) // 2
    if judge():
        l = x
    else:
        r = x
print(l)

Submission status: Time Limit Exceeded

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

for i in A:
  if i > 0:
    plus.append(i)
  elif i == 0:
    zero.append(i)
  else:
    minus.append(i)
else:
  p = len(plus)
  z = len(zero)
  m = len(minus)
  c_p = int(p * (p-1) / 2 + m * (m-1) / 2)
  c_z = int(z * (z-1) / 2 + z * (p+m))
  c_m = int(p * m)
  p_p = []
  p_z = []
  p_m = []

  if c_m >= K:
    for i in plus:
      for j in minus:
        p_m.append(i * j)
    else:
      p_m.sort()
      print(p_m[K-1])
  elif c_m + c_z >= K:
    print(0)
  else:
    for i in range(p):
      for j in range(p-1-i):
        p_p.append(plus[i] * plus[i+j+1])
    else:
      for i in range(m):
        for j in range(m-1-i):
          p_p.append(minus[i] * minus[i+j+1])
      else:
        p_p.sort()
        print(p_p[K-1-c_m-c_z])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    def test(x):
        tmp = [None] * n
        for i in range(n):
            if a[i] == 0:
                tmp[i] = (n - 1, 0, 0)
            else:
                tmp[i] = (x / a[i], -1 if a[i] < 0 else 1, a[i])
        print(tmp)
        res = []
        for t, flg, ai in tmp:
            if flg == 0:
                res.append(0 if x < 0 else t)
            else:
                if flg == -1:
                    res.append(n - bisect_left(a, t) - (ai >= t))
                else:
                    res.append(bisect_right(a, t) - (ai <= t))
        # print(res, sum(res))
        return
    def f(x):
        res = 0
        for ai in a:
            if ai == 0:
                res += 0 if x < 0 else n - 1
            else:
                if ai <= -1:
                    res -= ai * ai <= x
                    ok = n
                    ng = -1
                    while ok - ng > 1:
                        mid = (ok + ng) // 2
                        if a[mid] * ai <= x:
                            ok = mid
                        else:
                            ng = mid
                    res += n - ok
                else:
                    res -= ai * ai <= x
                    ok = -1
                    ng = n
                    while abs(ok - ng) > 1:
                        mid = (ok + ng) // 2
                        if a[mid] * ai <= x:
                            ok = mid
                        else:
                            ng = mid
                    res += ok + 1
        # print(res // 2,x,ok,ng)
        return k <= res // 2
    n, k = LI()
    a = LI()
    a.sort()
    # print(a)
    # test(448283280358331063)
    # test(448283280358331064)
    # return
    ok = 10 ** 18
    ng = -10 ** 18 - 1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        # print(ok,ng,mid)
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

def binsearch(s, e, func):
    global n,k,a
    while(abs(s - e) > 1):
        m = int((s + e) / 2)
        if(func(m)): s = m
        else: e = m
    return s


def binsearch2(s, e, i, kk):
    global n,a
    while(abs(s - e) > 1):
        m = int((s + e) / 2)
        if(sampleFunc2(i, m, kk)): s = m
        else: e = m
    return s

def sampleFunc2(i, j, kk):
    global a
    return ((a[int(i)] * a[int(j)]) < kk)

def sampleFunc(m):
    global n,k,a
    cnt = 0
    for i, aa in enumerate(a):
        if aa >= 0:
            ok_tmp = i
            ng_tmp = n
            ans = binsearch2(ok_tmp, ng_tmp, i, m)
            cnt += (ans - i)
        else:
            ok_tmp = n
            ng_tmp = i
            ans = binsearch2(ok_tmp, ng_tmp, i, m)
            cnt += (n - ans)
    return (cnt < k)

ok = (-10e18)
ok += 1
ng = (10e18)
ng += 1

a.sort()

print(binsearch(ok, ng, sampleFunc))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
k=int(input().split()[1])
source = [int(i) for i in input().split()]

target = []
nagasa=len(source)

for j in range(nagasa):
    num=source[j]
    for i in range(j+1, nagasa):
        target.append(num*source[i])
#target=[source[y]*source[x]for y in range(nagasa) for x in range(y+1,nagasa)]
target.sort()
#print(sorted_target[k-1])
print(target[k-1])

Submission status: Time Limit Exceeded

Solution code:
k=int(input().split()[1])
source = [int(i) for i in input().split()]

#target = []
nagasa=len(source)

#for j in range(nagasa):
#    num=source[j]
#    for i in range(j+1, nagasa):
#        target.append(num*source[i])
target=[source[y]*source[x]for y in range(nagasa) for x in range(y+1,nagasa)]
sorted_target=sorted(target)
print(sorted_target[k-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n,k = map(int, input().split())
a = list(map(int, input().split()))
ans = [i[0]*i[1] for i in list(combinations(a, 2))]
ans.sort()
print(ans[k-1])

Submission status: Time Limit Exceeded

Solution code:
INF = 1001001001

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

A.sort()

def f(x):
  res = 0
  for i in range(N):
    a = A[i]
    if a < 0:
      l, r = i, N
      while r - l > 1:
        mid = (l + r) // 2
        if a * A[mid] < x: r = mid
        else: l = mid
      res += N - r
    elif a == 0:
      if 0 < x: res += N - (i+1)
    else:
      l, r = i, N
      while r - l > 1:
        mid = (l + r) // 2
        if a * A[mid] < x: l = mid
        else: r = mid
      res += l - i
  return res

l, r = -INF * INF, INF * INF
while r - l > 1:
  mid = (l + r) // 2
  if f(mid) < K: l = mid
  else: r = mid
print(l)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**18+5


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

    a = sorted(a)
    l = -INF
    r = INF
    while(l+1 < r):
        x = (l+r)//2
        total = 0
        for i in range(n):
            if a[i] < 0:
                l2 = -1
                r2 = n
                while(l2+1 < r2):
                    x2 = (l2+r2)//2
                    if a[x2]*a[i] >= x:
                        l2 = x2
                    else:
                        r2 = x2
                total += n-r2
            else:
                l2 = -1
                r2 = n
                while(l2+1 < r2):
                    x2 = (l2+r2)//2
                    if a[x2]*a[i] < x:
                        l2 = x2
                    else:
                        r2 = x2
                total += r2
            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:
[n,k] = [int(x) for x in input().split()]
data = [int(x) for x in input().split()]

nega_num_list = []
posi_num_list = []
zero_num_list = []

for i in data:
    if i == 0:
        zero_num_list.append(i)
    elif i < 0:
        nega_num_list.append(i)
    else:
        posi_num_list.append(i)

# それぞれのリストの個数を計る
n_nums =  len(nega_num_list)
p_nums =  len(posi_num_list)
z_nums =  len(zero_num_list)

# ペアをとって計算したときに、負、正、ゼロの値がそれぞれいくつあるか計算する
n_pair_nums = int(n_nums*p_nums)
p_pair_nums = int(n_nums*(n_nums-1)/2 + p_nums*(p_nums-1)/2)
z_pair_nums = int(z_nums*n_nums + z_nums*p_nums + z_nums*(z_nums-1)/2)

#pdb.set_trace()

# k番目の値が上記３つのどの領域か判定する
order_offset = None
temp = []

if  n_pair_nums < k <= n_pair_nums + z_pair_nums:
    print(0)
elif k <= n_pair_nums:
    for x in nega_num_list:
        for y in posi_num_list:
            temp.append(x*y)     
    temp.sort()
    print(temp[k-1])

else:
    list1 = []
    list2 = []
    n = len(nega_num_list)
    for i in range(n-1):
        for j in range(i+1,n):
            list1.append(nega_num_list[i]*nega_num_list[j])
            
    n = len(posi_num_list)
    for i in range(n-1):
        for j in range(i+1,n):
            list2.append(posi_num_list[i]*posi_num_list[j])
    temp = list1 + list2
    temp.sort()
    print(temp[k - n_pair_nums - z_pair_nums - 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
left = -INF
right = INF

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

while right-left > 1:
    middle = (right + left) // 2
    if solve(middle) < k:
        left = middle
    else:
        right = middle
print(left)

Submission status: Time Limit Exceeded

Solution code:
# 積が負で絶対値が T 以上の組合せ数を求める
# A, B は昇順
def count1(T, A, B):
	return count1_by_binsearch(T, A, B)
	
	if T <= 0 or len(A) == 0 or len(B) == 0:
		return 0

	count, it = 0, -1
	for i in range(len(A) - 1, -1, -1):
		while it + 1 < len(B) and A[i] * B[it + 1] < T:
			it += 1

		# A[i] * B[it], A[i] * B[it + 1], ... は条件を満たす
		count += len(B) - it - 1
	return count


# 積が正で絶対値が T 以下の組合せ数を求める
# 絶対値が T より大きいものの組合せ数を求めてから全体から引く
# A は昇順
def count2(T, A):
	count_all = len(A) * (len(A) - 1) // 2
	count = count1(T + 1, A, A)

	# A[i] * A[i] が余計にカウントされた分を減らす．
	for e in A:
		if e * e >= T + 1:
			count -= 1

	count /= 2 # 同じ配列を渡しているため (i, j) == (j, i) が二回カウントされる

	return count_all - count


def count1_by_binsearch(T, A, B):
	if T <= 0 or len(A) == 0 or len(B) == 0:
		return 0

	count = 0
	for i in range(len(A)):
		if A[i] * B[-1] < T:
			continue;
			
		ok, ng = len(B) - 1, -1
		while abs(ok - ng) > 1:
			mid = (ok + ng) // 2

			if A[i] * B[mid] >= T:
				ok = mid
			else:
				ng = mid
		count += len(B) - ok

	return count

if __name__ == "__main__":
	N, K = map(int, input().split())
	A = list(map(int, input().split()))

	# X: 負の数の絶対値の配列
	# Y: 正の数の配列
	# Z: 0 の個数
	X, Y, Z = [], [], 0
	for e in A:
		if e < 0:
			X.append(-e)
		elif e > 0:
			Y.append(e)
		else:
			Z += 1
	X.sort()
	Y.sort()


	# 積が T 以下な組合せ数が K 未満か？
	def check(T):
		count = 0
		if T < 0:
			count += count1(abs(T), X, Y)
		else:
			count += len(X) * len(Y) # 結果が負
			count += Z * (Z - 1) // 2 + Z * (N - Z) # 結果が 0
			count += count2(T, X) + count2(T, Y)

		return count < K


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

	print(ok + 1)

Submission status: Time Limit Exceeded

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

INF = 10 ** 18 + 1

l = -INF
r = INF


def f(x):
    global N, K
    total = 0
    for i in range(N):
        if A[i] < 0:
            l = -1
            r = N
            while l + 1 < r:
                c = (l + r) // 2
                if A[c] * A[i] < x:
                    r = c
                else:
                    l = c
            total += N - r
        else:
            l = -1
            r = N
            while l + 1 < r:
                c = (l + r) // 2
                if A[c] * A[i] < x:
                    l = c
                else:
                    r = c
            total += r
        if A[i] * A[i] < x:
            total -= 1
    total = total // 2
    return total < K


while r - l > 1:
    x = (l + r) // 2
    if f(x):
        l = x
    else:
        r = x

print(l)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
pA=[a for a in A if a>=0]
nA.sort(reverse=True)
pA.sort()

#積がx以下になる組み合わせの数
def f(x):
    ret=0
    for na in nA:
        ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        ret+=g2(pA,na,x)
    for pa in pA:
        ret+=g2(nA,pa,x)
        ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=len(L)
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=len(L)-1
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**19
r=10**19
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
numlist = list(map(int, input().split()))
pemlist = list(itertools.combinations(numlist, 2))
lengty = len(pemlist)

mullist = []
for i in range(lengty):
  mullist.append(pemlist[i][0]*pemlist[i][1])

finlist =sorted(mullist)
print(finlist[K-1])

Submission status: Time Limit Exceeded

Solution code:
#11:09
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
import bisect
now = - 2 ** 63
scale = 2 ** 63
while scale != 0:
  tmp = now + scale
  cnt = 0
  for x in a:
    if x == 0:
      if tmp > 0:
        cnt += n
      else:
        pass
    elif x > 0:
      targ = (tmp-1) // x
      b = bisect.bisect_right(a,targ)
      cnt += b
    else:
      targ = - ((tmp-1) // (-x))
      b = bisect.bisect_left(a,targ)
      cnt += n - b
    if x ** 2 < tmp:
      cnt -= 1
  #print(cnt,cnt//2)
  cnt //= 2
  if cnt < k:
    now = tmp
  scale //= 2
print(now)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
numlist = list(map(int, input().split()))
pemlist = list(itertools.combinations(numlist, 2))

mullist = []
for i in range(len(pemlist)):
  a =pemlist[i][0]*pemlist[i][1]
  mullist.append(a)

finlist =sorted(mullist)
print(finlist[K-1])

Submission status: Time Limit Exceeded

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

# multi_list.sort()

# print(multi_list[k - 1])

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

minus_nums = []
plus_nums = []
zeroes = []

for num in a :
    if num < 0 :
        minus_nums.append(num)
    elif num > 0 :
        plus_nums.append(num)
    elif num == 0 :
        zeroes.append(num)

minus_num = len(minus_nums)
plus_num = len(plus_nums)
zero_num = len(zeroes)

multi_minus_num = minus_num * plus_num
multi_plus_num = (minus_num * (minus_num - 1)) // 2 + (plus_num * (plus_num - 1)) // 2
zero_num = (minus_num + plus_num) * zero_num + (zero_num * (zero_num - 1)) // 2

ans = []

if k <= multi_minus_num :
    for minus in minus_nums :
        for plus in plus_nums :
            ans.append(plus * minus)
    ans.sort()
    print(ans[k - 1])
elif multi_minus_num < k <= multi_minus_num + zero_num :
    print(0)
elif multi_minus_num + zero_num < k :
    if minus_num != 1 :
        for i in range(minus_num - 1) :
            for j in range(i + 1, minus_num) :
                ans.append(minus_nums[i] * minus_nums[j])
    if plus_num != 1 :
        for i in range(plus_num - 1) :
            for j in range(i + 1, plus_num) :
                ans.append(plus_nums[i] * plus_nums[j])
    ans.sort()
    print(ans[k - (multi_minus_num + zero_num) - 1])

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k = [int(i) for i in input().split(" ")]
a = [int(i) for i in input().split(" ")]

p = itertools.combinations(a, 2)
m = sorted([i[0]*i[1] for i in list(p)])
print(m[k-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

def ok(x):
    res = 0
    for i in range(N):
        if A[i]<0:
            left, right = -1, N
            while left + 1 < right:
                c = (left + right) // 2
                if A[c]*A[i] < x: right = c
                else:             left  = c
            res += N - right
        else:
            left, right = -1, N
            while left + 1 < right:
                c = (left + right) // 2
                if A[c]*A[i] < x: left  = c
                else:             right = c
            res += right
        if A[i]*A[i] < x:
            res -= 1
    res //= 2
    return res < K

INF = 10**18+1
l, r = -INF, INF
while l+1<r:
    x = (l+r)//2
    if ok(x):
        l = x
    else:
        r = x
print(l)