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

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

nafter = list()
zafter = list()
pafter = list()

for i in range(N):
  if A[i] < 0:
    nega.append(A[i])
  elif A[i] == 0:
    zero.append(A[i])
  if A[i] > 0:
    posi.append(A[i])

nnum = len(nega) 
znum = len(zero)
pnum = len(posi)

    
if K <= nnum * pnum:
  for i in range(nnum):
    for j in range(pnum):
      nafter.append(nega[i] * posi[j])
  nafter.sort()
  print(nafter[K-1])
elif K <= nnum*pnum + znum * (nnum + pnum) + znum * (znum - 1) // 2:
  print(0)
else:
  for v in itertools.combinations(nega, 2):
    for k in range(len(v) // 2):
      pafter.append(v[2*k] * v[2*k+1])
  for w in itertools.combinations(posi, 2):
    for l in range(len(w) // 2):
      pafter.append(w[2*l] * w[2*l+1])
  pafter.sort()
  print(pafter[K - (nnum*pnum + znum * (nnum + pnum) + znum * (znum - 1) // 2) - 1])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())  #数字
A = map(int, input().split())  #数字

B = []
import itertools
for i, j in itertools.combinations(A, 2):
    B.append(i*j)
B = sorted(B, reverse=False)

print(B[K-1])

Submission status: Time Limit Exceeded

Solution code:
# Problem D - Pairs

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

# initialization
a_nums = sorted(a_nums)
left = -10**18
right = 10**18

# binary search
while right-left>1:
    x = (right + left) // 2
    S = 0
    T = 0
    # 判定部分
    for a in a_nums:
        if a>0:
            r2 = N
            l2 = -1
            while r2-l2>1:
                mid = (r2 + l2) // 2
                if a*a_nums[mid]<=x:
                    l2 = mid
                else:
                    r2 = mid
            S += r2
        elif a<0:
            r2 = N
            l2 = -1
            while r2-l2>1:
                mid = (r2 + l2) // 2
                if a*a_nums[mid]<=x:
                    r2 = mid
                else:
                    l2 = mid
            S += N - r2
        elif x>=0: # a==0の時
            S += N
        # 重複を数える
        if a*a<=x:
            T += 1
    # 判定部分（大元）
    check_nums = (S - T) // 2
    if check_nums>=K:
        right = x
    else:
        left = x

# output
print(right)

Submission status: Time Limit Exceeded

Solution code:
# Problem D - Pairs

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

# initialization
a_nums = sorted(a_nums)
left = -10**19
right = 10**19

# binary search
while right-left>1:
    x = (right + left) // 2
    S = 0
    T = 0
    # 判定部分
    for a in a_nums:
        if a>0:
            r2 = N
            l2 = -1
            while r2-l2>1:
                mid = (r2 + l2) // 2
                if a*a_nums[mid]<=x:
                    l2 = mid
                else:
                    r2 = mid
            S += r2
        elif a<0:
            r2 = N
            l2 = -1
            while r2-l2>1:
                mid = (r2 + l2) // 2
                if a*a_nums[mid]<=x:
                    r2 = mid
                else:
                    l2 = mid
            S += N - r2
        elif x>=0: # a==0の時
            S += N
        # 重複を数える
        if a*a<=x:
            T += 1
    # 判定部分（大元）
    check_nums = (S - T) // 2
    if check_nums>=K:
        right = x
    else:
        left = x

# output
print(right)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect
def resolve():
    n, k = map(int,input().split())
    A = list(map(int,input().split()))
    pos_A = []
    neg_A = []
    pos = neg = zero = 0
    for a in A:
        if a > 0:
            pos += 1
            pos_A.append(a)
        elif a < 0:
            neg += 1
            neg_A.append(-a)
        else:
            zero += 1
    pos_A.sort()
    neg_A.sort()

    pair_pos = pos * (pos - 1) // 2 + neg * (neg - 1) // 2
    pair_neg = pos * neg
    pair_zero = zero * (pos + neg) + zero * (zero - 1) // 2

    # 答えが 0
    if pair_neg < k <= pair_neg + pair_zero:
        print(0)
        return

    # 答えが negative
    if k <= pair_neg:
        def count(x): # A[i] * A[j] <= x
            res = 0
            for a in pos_A:
                res += bisect(neg_A, x // a)
            return res

        k = pair_neg - k + 1
        left = 0
        right = 10 ** 18 + 1
        while right - left > 1:
            mid = (left + right) // 2
            if count(mid) < k:
                left = mid
            else:
                right = mid
        print(-right)
        return

    # 答えが positive
    def count(x, A):
        res = 0
        for i in range(1, len(A)):
            target = x // A[i] # 0 ... i - 1 で x // a 以下のものの個数
            if A[i - 1] <= target:
                res += i
                continue
            elif A[0] > target:
                continue
            left = 0
            right = i - 1
            while right - left > 1:
                mid = (left + right) // 2
                if A[mid] <= target:
                    left = mid
                else:
                    right = mid
            res += left + 1
        return res

    k -= pair_neg + pair_zero
    left = 0
    right = 10 ** 18 + 1
    while right - left > 1:
        mid = (left + right) // 2
        if count(mid, pos_A) + count(mid, neg_A) < k:
            left = mid
        else:
            right = mid
    print(right)
resolve()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
Pos = []
Neg = []
m, z, p = 0, 0, 0
for i in range(N):
  if A[i] < 0:
    m += 1
    Neg.append(-A[i])
  elif A[i] == 0:
    z += 1
  elif A[i] > 0:
    p += 1
    Pos.append(A[i])
Neg.sort()
mm, zz, pp = p*m, z*(N-z)+(z*(z-1))//2, (p*(p-1)+m*(m-1))//2
if K <= mm:
  cnt = 1
  L, R = 0, -(A[0] * A[-1]) + 1
  D = (L + R) // 2
  tmp = R
  while tmp != 0:
    cnt += 1
    tmp //= 2
  ccnt = 1
  tmp1 = p
  while tmp1 != 0:
    ccnt += 1
    tmp1 //= 2
  for i in range(cnt+1):
    pnt = 0
    for j in range(m):
      # search #{x|-A[j] * A[x] >= D, m+z <= x < N}
      l, r = m + z, N
      d = (l + r) // 2
      if A[l] * (-A[j]) >= D:
        pnt += r - l
      elif A[N-1] * (-A[j]) < D:
        pnt += 0
      else:
        for k in range(ccnt+2):
          if A[d] * (-A[j]) < D:
            l = d
            d = (l + r) // 2
          else:
            r = d
            d = (l + r) // 2
        pnt += N - d - 1
    if pnt >= K:
      L = D
      D = (L + R) // 2
    else:
      R = D
      D = (L + R) // 2
  print(-D)
elif mm < K <= mm + zz:
  print(0)
else:
  cnt = 1
  if m <= 1:
    L, R = 0, Pos[-1] * Pos[-2] + 1
  elif p <= 1:
    L, R = 0, Neg[-1] * Neg[-2] + 1
  else:
    L, R = 0, max(Pos[-1] * Pos[-2], Neg[-1] * Neg[-2]) + 1
  D = (L + R) // 2
  tmp = R
  while tmp != 0:
    cnt += 1
    tmp //= 2
  ccnt = 1
  tmp1 = m*(m-1)//2
  while tmp1 != 0:
    ccnt += 1
    tmp1 //= 2
  cccnt = 1
  tmp2 = p*(p-1)//2
  while tmp2 != 0:
    cccnt += 1
    tmp2 //= 2
  for i in range(cnt+1):
    pnt = 0
    for j in range(m-1):
      l, r = j+1, m
      d = (l + r) // 2
      if Neg[j] * Neg[j+1] > D:
        pnt += 0
      elif Neg[j] * Neg[m-1] <= D:
        pnt += m - j - 1
      else:
        for k in range(ccnt+1):
          if Neg[d] * Neg[j] <= D:
            l = d
            d = (l + r) // 2
          else:
            r = d
            d = (l + r) // 2
        pnt += d - j
    for j in range(p-1):
      l, r = j + 1, p
      d = (l + r) // 2
      if Pos[j] * Pos[j+1] > D:
        pnt += 0
      elif Pos[j] * Pos[p-1] <= D:
        pnt += p - j - 1
      else:
        for k in range(cccnt+1):
          if Pos[d] * Pos[j] <= D:
            l = d
            d = (l + r) // 2
          else:
            r = d
            d = (l + r) // 2
        pnt += d - j
    if pnt < K - mm - zz:
      L = D + 1
      D = (L + R) // 2
    else:
      R = D
      D = (L + R) // 2
  print(D)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left

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

    negative = bisect_left(A, -0.5)
    zero = A.count(0)
    positive = N - bisect_left(A, 0.5)

    Nlst = A[:negative]
    Plst = A[bisect_left(A, 0.5):]

    # print (Nlst)
    # print (Plst)

    def calc(x): #x以下が何個になるかを数える
        tmp = 0
        if x == 0:
            tmp += zero * (negative + positive) + zero * (zero - 1) // 2 #0になるもの
            tmp += negative * positive #負になるもの
            return tmp
        elif x > 0:
            tmp += zero * (negative + positive) + zero * (zero - 1) // 2 #0になるもの
            tmp += negative * positive #負になるもの

            for index, p in enumerate(Plst):
                tmp += min(index, bisect_left(Plst, x // p + 0.5))

            for index, n in enumerate(Nlst):
                tmp += max(0, index - bisect_left(Nlst, -(x // (-n)) - 0.5))
            return tmp 
        else:
            for index, n in enumerate(Nlst):
                tmp += positive - bisect_left(Plst, ((-x) + (-n) - 1) // (-n) - 0.5)
            return tmp



    l = -10 ** 20
    r = 10 ** 20

    # l = -20
    # r = 20
    while r - l > 1:
        mid = (r + l) // 2
        # print ('mid =', mid, calc(mid))
        if calc(mid) >= K:
            r = mid
        else:
            l = mid

    print (r)

    # print (Nlst)
    # print (Plst)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

negative = bisect_left(A, -0.5)
zero = A.count(0)
positive = N - bisect_left(A, 0.5)

Nlst = A[:negative]
Plst = A[bisect_left(A, 0.5):]

# print (Nlst)
# print (Plst)

def calc(x): #x以下が何個になるかを数える
    tmp = 0
    if x == 0:
        tmp += zero * (negative + positive) + zero * (zero - 1) // 2 #0になるもの
        tmp += negative * positive #負になるもの
        return tmp
    elif x > 0:
        tmp += zero * (negative + positive) + zero * (zero - 1) // 2 #0になるもの
        tmp += negative * positive #負になるもの

        for index, p in enumerate(Plst):
            tmp += min(index, bisect_left(Plst, x // p + 0.5))

        for index, n in enumerate(Nlst):
            tmp += max(0, index - bisect_left(Nlst, -(x // (-n)) - 0.5))
        return tmp 
    else:
        for index, n in enumerate(Nlst):
            tmp += positive - bisect_left(Plst, ((-x) + (-n) - 1) // (-n) - 0.5)
        return tmp



l = -10 ** 20
r = 10 ** 20

# l = -20
# r = 20
while r - l > 1:
    mid = (r + l) // 2
    # print ('mid =', mid, calc(mid))
    if calc(mid) >= K:
        r = mid
    else:
        l = mid

print (r)

# print (Nlst)
# print (Plst)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

negative = bisect_left(A, -0.5)
zero = A.count(0)
positive = N - bisect_left(A, 0.5)

Nlst = A[:negative]
Plst = A[bisect_left(A, 0.5):]

# print (Nlst)
# print (Plst)

def calc(x): #x以下が何個になるかを数える
    tmp = 0
    if x == 0:
        tmp += zero * (negative + positive) + zero * (zero - 1) // 2 #0になるもの
        tmp += negative * positive #負になるもの
        return tmp
    elif x > 0:
        tmp += zero * (negative + positive) + zero * (zero - 1) // 2 #0になるもの
        tmp += negative * positive #負になるもの

        for index, p in enumerate(Plst):
            tmp += bisect_left(Plst[:index], x // p + 0.5)

        for index, n in enumerate(Nlst):
            tmp += max(0, index - bisect_left(Nlst[:index], -(x // (-n)) - 0.5))
        return tmp 
   
    else:
        for index, n in enumerate(Nlst):
            tmp += positive - bisect_left(Plst, ((-x) + (-n) - 1) // (-n) - 0.5)
        return tmp



l = -10 ** 20
r = 10 ** 20

# l = -20
# r = 20
while r - l > 1:
    mid = (r + l) // 2
    # print ('mid =', mid, calc(mid))
    if calc(mid) >= K:
        r = mid
    else:
        l = mid

print (r)

# print (Nlst)
# print (Plst)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    C = [SI()for _ in range(3)]
    ans = C[0][0]+C[1][1]+C[2][2]
    print(ans)
    return

def examB():
    N, M = LI()
    P = [0]*N
    S = [LSI()for _ in range(M)]
    pena = 0
    ac = set()
    for p,s in S:
        p = int(p)-1
        if s=="WA":
            P[p] += 1
        else:
            if p in ac:
                continue
            ac.add(p)
            pena += P[p]

    print(len(ac),pena)
    return

def examC():
    W, H, N = LI()
    lx, rx, ly, ry = 0, W, 0, H
    A = [LI()for _ in range(N)]
    for x,y,a in A:
        if a==1:
            lx = max(lx,x)
        elif a==2:
            rx = min(rx,x)
        elif a==3:
            ly = max(ly,y)
        elif a==4:
            ry = min(ry,y)
    ans = max(0,rx-lx)*max(0,ry-ly)
    print(ans)
    return

def examD():
    N, H = LI()
    B = [0]*N
    maxa = 0
    ans = 0
    for i in range(N):
        a, B[i] = LI()
        if a>maxa:
            maxa = a
    B.sort(reverse=True)
    for b in B:
        if b<maxa:
            break
        H -= b
        ans += 1
        if H<=0:
            print(ans)
            return
    ans += -(-H//maxa)
    print(ans)
    return

def examE():
    A, B = LI()
    ans = [["#"]*100 for _ in range(50)] + [["."]*100 for _ in range(50)]
    i = 0; j = 0
    for _ in range(A-1):
        ans[i][j] = "."
        j += 2
        if j>=100:
            j = 0; i += 2
    i = 0; j = 0
    for _ in range(B-1):
        ans[99-i][j] = "#"
        j += 2
        if j>=100:
            j = 0; i += 2
    print(100,100)
    for v in ans:
        print("".join(map(str,v)))
    return

def examF():
    def search_1(need):
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            for b in neg:
                cur += len(pos)-bisect.bisect_right(pos, now//b)
            if cur>=need:
                l = now
            else:
                r = now
            #print(cur)
        return r
    def search_2(need):
        need *= 2
        #print(need)
        l = 0; r = inf
        while(r-l)>1:
            now = (l+r)//2
            cur = 0
            for b in neg:
                cur += bisect.bisect_right(neg, now//b)
                if now>=b**2:
                    cur -= 1
            #print("途中",cur,now)
            for b in pos:
                cur += bisect.bisect_right(pos, now//b)
                if now>=b**2:
                    cur -= 1
            if cur>=need:
                r = now
            else:
                l = now
            #print(cur,now)
        return r
    N, K = LI()
    A = LI()
    neg = []; pos = []; arr_0 = 0
    for a in A:
        if a<0:
            neg.append(-a)
        elif a==0:
            arr_0 += 1
        else:
            pos.append(a)
    neg.sort(); pos.sort()
    #print(pos)
    if len(neg)*len(pos)>=K:
        ans = -search_1(K)
    elif len(neg)*len(pos)+arr_0*(len(neg)+len(pos))+arr_0*(arr_0-1)//2>=K:
        ans = 0
    else:
        ans = search_2(K-len(neg)*len(pos)-arr_0*(len(neg)+len(pos))-arr_0*(arr_0-1)//2)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
87940638538504699
448283280358331064
"""

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

negative = bisect_left(A, -0.5)
zero = A.count(0)
positive = N - bisect_left(A, 0.5)

Nlst = A[:negative]
Plst = A[bisect_left(A, 0.5):]

# print (Nlst)
# print (Plst)

def calc(x): #x以下が何個になるかを数える
    tmp = 0
    if x == 0:
        tmp += zero * (negative + positive) + zero * (zero - 1) // 2 #0になるもの
        tmp += negative * positive #負になるもの
        return tmp
    elif x > 0:
        tmp += zero * (negative + positive) + zero * (zero - 1) // 2 #0になるもの
        tmp += negative * positive #負になるもの

        for index, p in enumerate(Plst):
            tmp += bisect_left(Plst[:index], x // p + 0.5)

        for index, n in enumerate(Nlst):
            tmp += max(0, index - bisect_left(Nlst[:index], -(x // (-n)) - 0.5))
        return tmp 
   
    else:
        for index, n in enumerate(Nlst):
            tmp += positive - bisect_left(Plst, ((-x) + (-n) - 1) // (-n) - 0.5)
        return tmp



l = -10 ** 20
r = 10 ** 20

# l = -20
# r = 20
while r - l > 1:
    mid = (r + l) // 2
    # print ('mid =', mid, calc(mid))
    if calc(mid) >= K:
        r = mid
    else:
        l = mid

print (r)

# print (Nlst)
# print (Plst)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

def kake(a,i,j,wk):
    if j<i+1:
        return 0
    wk.append(a[i]*a[j])
#    print(wk)
    kake(a,i,j-1,wk)
    return wk

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

seki=[]

for i in range(n-1):
    j=n-1
    wk =[]
    seki += (kake(a,i,j,wk))

seki.sort()

print(seki[k-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

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

n,k = nm()
l = nl()
f = list(filter(lambda x:x>0, l))
g = list(filter(lambda x:x<0, l))
f.sort(); g.sort(reverse=True)
pl = len(f); mi = len(g)
ze = n - pl - mi
tomi = pl*mi
if tomi >= k:
    def jud(z):
        ret = 0
        i = mi
        for x in f:
            while i and x*g[i-1] <= z: i -= 1
            ret += mi - i
        return ret
    ok,ng = 0,max(f)*min(g)-1
    while ok - ng > 1:
        mid = (ok+ng)//2
        if jud(mid) < k:
            ng = mid
        else:
            ok = mid
    print(ok)
    exit(0)

tomi += ze*(n-ze) + (ze-1)*ze//2
if tomi >= k:
    print(0); exit(0)

else:
    k -= tomi
    def jud2(z):
        ret = 0
        i = pl
        for e,x in enumerate(f):
            while i and f[i-1]*x > z: i -= 1
            ret += i - (e<=i-1)
        i = mi
        for e,x in enumerate(g):
            while i and g[i-1]*x > z: i -= 1
            ret += i - (e<=i-1)
        return ret//2
    ok,ng = 0,max(max(f+[0])**2, min(g+[0])**2)
    while ng - ok > 1:
        mid = (ok+ng)//2
        if jud2(mid) < k:
            ok = mid
        else:
            ng = mid
    print(ng)

Submission status: Time Limit Exceeded

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

# https://atcoder.jp/contests/abc155/submissions/12182341
def main(N, K, Ap, Am):
    p = len(Ap)
    m = len(Am)
    Ap.sort()
    Am.sort(reverse=True)
    U = 10 ** 18
    L = - 10 ** 18

    while U - L > 1:
        # print("U: {}  L:{}".format(U, L))
        mid = (U+L)//2
        cnt = 0
        if mid >= 0:
            cnt += p*m
            i = p
            t = 0
            for a in Ap:
                while i and Ap[i-1] * a > mid: i -= 1
                t += i
                if a*a <= mid: t -= 1
            cnt += t//2
            i = m
            t = 0
            for a in Am:
                while i and Am[i-1] * a > mid: i -= 1
                t += i
                if a*a <= mid: t -= 1
            cnt += t//2
        else:
            i = m
            for a in Ap:
                while i and Am[i-1] * a <= mid: i -= 1
                cnt += m - i   
        
        if cnt < K:
            L = mid
        else:
            U = mid
        # print("after U: {}  L:{}".format(U, L))
    
    print(U)


    return

if __name__ == '__main__':
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    Ap = []
    Am = []
    # A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    for _ in range(N):
        t = int(next(tokens))
        if t>=0:
            Ap.append(t)
        elif t<0:
            Am.append(t)
    main(N, K, Ap, Am)

Submission status: Time Limit Exceeded

Solution code:
#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################
import itertools
ans = []
N,K =  map(int,input().split())	
l = list(map(int,input().split()))	
for v in itertools.combinations(l, 2):
    #print(list(v))
    #print(list(v)[0])
    #print(list(v)[1])
    ans.append(list(v)[1]*list(v)[0])
#print(ans)
b = sorted(ans)
#print(b)
print(b[K-1])

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
A = list(map(int, input().split()))

#
A.sort()
A_product =[]
for i in range(N):
    for j in range(i+1,N):
        A_product.append(( (i,j),A[i]*A[j] ))
A_product_sort =sorted(A_product ,key=lambda x:x[1])
print(A_product_sort[K-1][1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations as com
n, k = map(int, input().split())
a = list(map(int, input().split()))
e = []
for i, j in com(a, 2):
    e.append(i*j)
e.sort()
print(e[k-1])

Submission status: Time Limit Exceeded

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

def solve_m(S, T, K):
    def count(x):
        ret, ti = 0, 0
        for s in S:
            # 積がxを初めて下回るtiを求める。なければlen(T)
            while ti < len(T) and s * T[ti] > x:
                ti += 1
            if ti == len(T):
                break
            ret += len(T) - ti
        return ret
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid) < K:
            left = mid
        else:
            right = mid
    return right

def solve(S, mS, K):
    def count(x, T):
        ret, j = 0, len(T) - 1
        for i, t in enumerate(T):
            while j >= 0 and t * T[j] > x:
                j -= 1
            if j == -1:
                break
            ret += j + 1 - (1 if i <= j else 0)
        return ret // 2
    left, right = -(10**18)-1, 10**18+1
    while abs(right - left) > 1:
        mid = (left + right) // 2
        if count(mid, S) + count(mid, mS) < K:
            left = mid
        else:
            right = mid
    return right

def main():
    N, K = list(map(int, input().split()))
    A = sorted(map(int, input().split()), reverse=True)
    B = {-1:[], 0:[], 1:[]}
    for a in A:
        if a == 0:
            B[0].append(0)
        else:
            B[a//abs(a)].append(a)
    m = len(B[-1]) * len(B[1])
    z = len(B[0]) * (N-len(B[0])) + len(B[0]) * (len(B[0])-1) // 2
    if K <= m:
        print(solve_m(B[1], B[-1], K))
    elif K <= m + z:
        print(0)
    else:
        print(solve(sorted(B[1]), B[-1], K - m - z))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ap, am, a0 = [], [], []
for i in a:
    if i > 0:
        ap.append(i)
    elif i < 0:
        am.append(i)
    else:
        a0.append(i)
lp, lm, l0 = len(ap), len(am), len(a0)
ap.sort()
am.sort(reverse=True)

# binary search
if k <= lp * lm:
    start = max(ap) * min(am)
    stop = -1
    while start < stop:
        # i以下になるペアがnum個ある
        # 尺取法
        num = 0
        i = (start + stop) // 2
        j = 0
        flag = True
        for l in range(lm-1, -1, -1):
            while flag and am[l] * ap[j] > i:
                j += 1
                if j == lp:
                    flag = False
                    break
            num += lp - j
        if num < k:
            start = i + 1
        else:
            stop = i
    print(start)

elif k <= lp * lm + (lp + lm) * l0 + l0 * (l0 - 1) // 2:
    print(0)

else:
    k -= lp * lm + (lp + lm) * l0 + l0 * (l0 - 1) // 2
    start = 1
    if ap == []:
        stop = min(am) * min(am)
    elif am == []:
        stop = max(ap) * max(ap)
    else:
        stop = max([max(ap) * max(ap), min(am) * min(am)])
    while start < stop:
        # 1以上i以下になるペアがnum個ある
        # 尺取法
        num = 0
        i = (start + stop) // 2

        # 正の数
        j = 0
        flag = True
        flag2 = True
        for l in range(lp-1, -1, -1):
            while flag and ap[l] * ap[j] <= i:
                if flag2 and l <= j:
                    num -= l + 1
                    flag2 = False
                j += 1
                if j == lp:
                    flag = False
            num += j

        # 負の数
        j = 0
        flag = True
        flag2 = True
        for l in range(lm-1, -1, -1):
            while flag and am[l] * am[j] <= i:
                if flag2 and l <= j:
                    num -= l + 1
                    flag2 = False
                j += 1
                if j == lm:
                    flag = False
            num += j

        num //= 2
        if num < k:
            start = i + 1
        else:
            stop = i
    print(start)

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort

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):
        num = A[i]*A[j]
        insort(ans,num)
#print(ans)
print(ans[K-1])

Submission status: Time Limit Exceeded

Solution code:
def ok():
    tot = 0
    for i in range(N):
        if A[i] < 0:
            l, r = -1, 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, r = -1, 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


N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
INF = 10 ** 18 + 1
l, r = -INF, INF
while l + 1 < r:
    x = (l + r) // 2
    if ok():
        l = x
    else:
        r = x
print(l)

Submission status: Time Limit Exceeded

Solution code:
f=lambda:map(int,input().split())
n,k=f()
a=sorted(f())
INF=10**18+1
l,r=-INF,INF
while r-l>1:
  m=(l+r)//2
  s=0
  for i in a:
    li,ri=-1,n
    if i<0:
      while ri-li>1:
        mi=(li+ri)//2
        if i*a[mi]<m: ri=mi
        else: li=mi
      s+=n-ri
    else:
      while ri-li>1:
        mi=(li+ri)//2
        if i*a[mi]<m: li=mi
        else: ri=mi
      s+=ri
    if i*i<m: s-=1
  if s//2<k: l=m
  else: r=m
print(l)

Submission status: Time Limit Exceeded

Solution code:
def main():
  f=lambda:map(int,input().split())
  n,k=f()
  la=sorted(f())
  INF=10**18+1
  import bisect
  tl=bisect.bisect_left(la,0)
  tr=bisect.bisect(la,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
  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 range(tp):
        i=la[tr+i]
        li,ri=-1,tm
        while ri-li>1:
          mi=(li+ri)//2
          if i*la[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 range(tm):
        i=la[i]
        li,ri=-1,tm
        while ri-li>1:
          mi=(li+ri)//2
          if i*la[mi]<m: ri=mi
          else: li=mi
        s+=tm-ri
        if i*i<m: s-=1
      for i in range(tp):
        i=la[tr+i]
        li,ri=-1,tp
        while ri-li>1:
          mi=(li+ri)//2
          if i*la[tr+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)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
f=lambda:map(int,input().split())
n,k=f()
la=sorted(f())
INF=10**18+1
from bisect import *
tl=bisect_left(la,0)
tr=bisect(la,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
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 range(tp):
      i=la[tr+i]
      li,ri=-1,tm
      while ri-li>1:
        mi=(li+ri)//2
        if i*la[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 range(tm):
      i=la[i]
      li,ri=-1,tm
      while ri-li>1:
        mi=(li+ri)//2
        if i*la[mi]<m: ri=mi
        else: li=mi
      s+=tm-ri
      if i*i<m: s-=1
    for i in range(tp):
      i=la[tr+i]
      li,ri=-1,tp
      while ri-li>1:
        mi=(li+ri)//2
        if i*la[tr+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)