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: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def main():
    N, K = MI()
    A = LI()
    minus = [-a for a in A if a < 0]
    zero = [a for a in A if a == 0]
    plus = [a for a in A if a > 0]

    minus_max_idx = len(minus) * len(plus)
    zero_max_idx = minus_max_idx + len(zero) * (len(plus) + len(minus)) + cmb(len(zero), 2)

    # print(minus_max_idx, zero_max_idx)

    if K < minus_max_idx:
        plus.sort()
        minus.sort(reverse=True)
        high = 10 ** 19
        low = 0

        while high - low > 1:
            mid = (high + low) // 2
            r = 0
            ans = 0
            for l in range(len(minus)):
                while r < len(plus) and minus[l] * plus[r] < mid:
                    r += 1
                ans += len(plus) - r
            if ans < K:
                high = mid
            else:
                low = mid
        print(-low)
    elif K >= minus_max_idx and K < zero_max_idx:
        print(0)
    else:
        high = 10 ** 19
        low = 0
        plus.sort()
        minus.sort()

        while high - low > 1:
            mid = (high + low) // 2
            r = 0
            ans = 0
            for num in minus[::-1]:
                if num * num <= mid:
                    ans -= 1
                while r < len(minus) and minus[r] * num <= mid:
                    r += 1
                ans += r
            r = 0
            for num in plus[::-1]:
                if num * num <= mid:
                    ans -= 1
                while r < len(plus) and plus[r] * num <= mid:
                    r += 1
                ans += r
            ans //= 2
            # print('ans', ans, 'mid', mid, 'low', low, 'high', high, K - zero_max_idx)

            if ans < K - zero_max_idx:
                low = mid
            else:
                high = mid
        print(high)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def main():
    N, K = MI()
    A = LI()
    minus = [-a for a in A if a < 0]
    zero = [a for a in A if a == 0]
    plus = [a for a in A if a > 0]

    minus_max_idx = len(minus) * len(plus)
    zero_max_idx = minus_max_idx + len(zero) * (len(plus) + len(minus)) + cmb(len(zero), 2)

    # print(minus_max_idx, zero_max_idx)

    if K < minus_max_idx:
        plus.sort()
        minus.sort(reverse=True)
        high = 10 ** 19
        low = 0

        while high - low > 1:
            mid = (high + low) // 2
            r = 0
            ans = 0
            for l in range(len(minus)):
                while r < len(plus) and minus[l] * plus[r] < mid:
                    r += 1
                ans += len(plus) - r
            if ans <= K:
                high = mid
            else:
                low = mid
        print(-low)
    elif K >= minus_max_idx and K < zero_max_idx:
        print(0)
    else:
        high = 10 ** 19
        low = 0
        plus.sort()
        minus.sort()

        while high - low > 1:
            mid = (high + low) // 2
            r = 0
            ans = 0
            for num in minus[::-1]:
                if num * num <= mid:
                    ans -= 1
                while r < len(minus) and minus[r] * num <= mid:
                    r += 1
                ans += r
            r = 0
            for num in plus[::-1]:
                if num * num <= mid:
                    ans -= 1
                while r < len(plus) and plus[r] * num <= mid:
                    r += 1
                ans += r
            ans //= 2
            # print('ans', ans, 'mid', mid, 'low', low, 'high', high, K - zero_max_idx)

            if ans < K - zero_max_idx:
                low = mid
            else:
                high = mid
        print(high)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

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

A.sort()
Nn = bisect.bisect_left(A, 0) # 負の数の数
Nz = bisect.bisect_left(A, 1) - Nn # 0の数
Np = N - Nn - Nz # 正の数の数
An = A[:Nn]
Ap = A[Nn+Nz:]


if Nn*Np >= K: # 答えが負の数
  left = -10**18-1 # False
  right = -1 # True
  n = Nn*Np - K # midより大きくなるのがn個より多いとmid以下のペアがK個以上にならない
  while left+1 < right:
    mid = (left+right) // 2
    i = j = 0
    c = 0
    while i < Nn and j < Np:
      if An[i]*Ap[j] > mid:
        c += 1
        j += 1
      else:
        c += j
        i += 1
      if c > n:
        break
    if c > n:
      left = mid
    else:
      right = mid
  ans = -10**20
  for an in An:
    idx = bisect.bisect_left(Ap, right/an)
    if idx < Np:
      ans = max(ans, Ap[idx]*an)
      if ans == right:
        break 
elif Nn*Np + Nz*(Nn+Np) + Nz*(Nz-1)//2 >= K: # 答えが0
  ans = 0
else: # 答えが正
  An = [-an for an in An][::-1]
  N = Nn*(Nn-1)//2 + Np*(Np-1)//2 # 積が正となる組合せ
  k = K - Nn*Np - Nz*(Nn+Np) - Nz*(Nz-1)//2 # 正の数の中でk番目に小さい数が答え
  n = N - k
  left = 0 # False
  right = 10**18 + 1 # True
  while left+1 < right:
    mid = (left+right) // 2
    i = 0
    j = Nn - 1
    c = 0
    while i < j:
      if An[i]*An[j] > mid:
        c += 1
        j -= 1
      else:
        c += Nn - 1 - j
        i += 1
      if i == j:
          c += (Nn-i-1)*(Nn-i-2) // 2
      if c > n:
        break
    
    if c > n:
      left = mid
    else:
      i = 0
      j = Np - 1
      while i < j:
        if Ap[i]*Ap[j] > mid:
          c += 1
          j -= 1
        else:
          c += Np - 1 - j
          i += 1
        if i == j:
            c += (Np-i-1)*(Np-i-2) // 2
        if c > n:
          break
      if c > n:
        left = mid
      else:
        right = mid
  ans = 10**20
  for an in An:
    idx = bisect.bisect_left(An, right/an)
    if idx < Nn:
      ans = min(ans, An[idx]*an)
      if ans == right:
        break
  for ap in Ap:
    idx = bisect.bisect_left(Ap, right/ap)
    if idx < Np:
      ans = min(ans, Ap[idx]*ap)
      if ans == right:
        break


print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

A.sort()
Nn = bisect.bisect_left(A, 0) # 負の数の数
Nz = bisect.bisect_left(A, 1) - Nn # 0の数
Np = N - Nn - Nz # 正の数の数
An = A[:Nn]
Ap = A[Nn+Nz:]


if Nn*Np >= K: # 答えが負の数
  left = -10**18-1 # False
  right = -1 # True
  n = Nn*Np - K # midより大きくなるのがn個より多いとmid以下のペアがK個以上にならない
  while left+1 < right:
    mid = (left+right) // 2
    i = j = 0
    c = 0
    while i < Nn and j < Np:
      if An[i]*Ap[j] > mid:
        c += 1
        j += 1
      else:
        c += j
        i += 1
      if c > n:
        break
    if c > n:
      left = mid
    else:
      right = mid
  ans = right  
elif Nn*Np + Nz*(Nn+Np) + Nz*(Nz-1)//2 >= K: # 答えが0
  ans = 0
else: # 答えが正
  An = [-an for an in An][::-1]
  N = Nn*(Nn-1)//2 + Np*(Np-1)//2 # 積が正となる組合せ
  k = K - Nn*Np - Nz*(Nn+Np) - Nz*(Nz-1)//2 # 正の数の中でk番目に小さい数が答え
  n = N - k
  left = 0 # False
  right = 10**18 + 1 # True
  while left+1 < right:
    mid = (left+right) // 2
    i = 0
    j = Nn - 1
    c = 0
    while i < j:
      if An[i]*An[j] > mid:
        c += 1
        j -= 1
      else:
        c += Nn - 1 - j
        i += 1
      if i == j:
          c += (Nn-i-1)*(Nn-i-2) // 2
      if c > n:
        break
    
    if c > n:
      left = mid
    else:
      i = 0
      j = Np - 1
      while i < j:
        if Ap[i]*Ap[j] > mid:
          c += 1
          j -= 1
        else:
          c += Np - 1 - j
          i += 1
        if i == j:
            c += (Np-i-1)*(Np-i-2) // 2
        if c > n:
          break
      if c > n:
        left = mid
      else:
        right = mid
  ans = right


print(ans)

Submission status: Wrong Answer

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

num = list(map(int, input().split(" ")))
multiplication_list = []
i = 0
while i < len(num):
    j = i + 1
    while j < len(num):
        multiplication_list.append(num[i] * num[j])
        j += 1
    i += 1

sorted(multiplication_list)
print(multiplication_list[k-1])

Submission status: Wrong Answer

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

m=[]
z=[]
p=[]

for i in A:
    if i<0:
        m.append(i)
    elif i==0:
        z.append(i)
    else:
        p.append(i)
if len(m)*len(p)>=K:
    A=list(it.combinations(m+p,2))
    B=sorted(A,reverse=True)
    print(B[K-1][0]*B[K-1][1])
elif len(m)*len(p)<K and len(m)*len(p)+(len(m)+len(p))*len(z)+(len(z)-1)*len(z)/2>=K:
    print(0)
else:
    k=K-1-(len(m)*len(p))-(len(m)+len(p))*len(z)-(len(z)-1)*len(z)/2
    A=list(it.combinations(-1*m,2))+list(it.combinations(p,2))
    B=sorted(A)
    #print(B[k][0]*B[k][1])
    #print((len(m)*len(p))+(len(m)+len(p))*len(z)+comb(len(z),2,exact=True))
    print(len(A))
    print(k)
    print(len(z)*(len(z)-1)/2)

Submission status: Wrong Answer

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def cnt(x,A,An,Ap,N,Nz):
    res = 0
    if x >= 0:
        res += N * Nz
    res += np.searchsorted(A,x//Ap,side='right').sum()
    res += N * len(An) - np.searchsorted(A,-(-x//An),side='left').sum()
    res -= np.count_nonzero(A*A<=x)
    return res//2


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

    print(len(A))

    A = np.array(A)
    A.sort()

    An = A[A<0]
    Az = A[A==0]
    Ap = A[A>0]

    Nz = np.count_nonzero(A==0)

    INF = 10 ** 18

    l = - INF - 1
    r = INF

    while r-l > 1:
        m = (l+r)//2
        if cnt(m,A,An,Ap,N,Nz) >= K:
            r = m
        else:
            l = m

    print(r)





main()

Submission status: Wrong Answer

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

    S = []

    for i in range(N-1):
        for j in range(i+1, N):
            s = A[i]*A[j]
            S.append(s)
    
    Ns = len(S)
    flag = True
    k = 0

    while flag:
        flag = False
        for l in range(Ns-1, k, -1):
            if S[l] < S[l-1]:
                S[l], S[l-1] = S[l-1], S[l]
                flag = True
        k += 1
    
    print(S)
    print(S[K-1])

D()

Submission status: Wrong Answer

Solution code:
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0
    j = 0
    for a in neg:
        d = (m + 1) // a + 1
        j = bisect(pos, d, lo=j)
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    less = 0
    j = 0
    for i in range(1, len_pos):
        a = pos[i]
        d = m // a
        j = bisect(pos, d, hi=i)
        less += j
    for i in range(1, len_neg):
        a = neg[i]
        d = m // a
        j = bisect(neg, d, hi=i)
        less += j
    return less < 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))

Submission status: Wrong Answer

Solution code:

from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,k=LI()
a=LI()
neg,pos=[],[]
cz=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        cz+=1
pos=sorted(pos)[::-1]
neg=sorted(neg)[::-1]

pn=len(pos)
nn=len(neg)
show(pos,neg)
def check(z):
    c=0
    if z>0:
        for i in pos:
            x=z/i
            c+=bisect.bisect(pos,x)-1
        for i in neg:
            x=z/i
            c+=bisect.bisect(pos,x)-1
    elif z<0:
        for i in pos:
            x=z/i
            c+=bisect.bisect(neg,x)
        for i in neg:
            x=z/i
            c+=bisect.bisect(pos,x)
    elif z==0:
        for i in pos:
            x=z/i
            c+=bisect.bisect(neg,x)
        for i in neg:
            x=z/i
            c+=bisect.bisect(pos,x)
        c+=cz*(cz-1)//2+cz*(n-cz)
    return c

for i in range(-30,50):
    print(i,check(i))
    

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import bisect

n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
minuss = []
pluss = []
zeros = []
for item in a:
    if item > 0:
        pluss.append(item)
    elif item < 0:
        minuss.append(item)
    else:
        zeros.append(0)
pluss.sort()
minuss.sort()
a.sort()

p_len = len(pluss)
m_len = len(minuss)
z_len = len(zeros)

minus_num = p_len * m_len
zeros_num = z_len * (z_len - 1) // 2 + z_len * (m_len + p_len)

l = - 10**19; r = 10**19
while r - l > 1:
    mid = (l + r) // 2
    cnt = 0
    if mid > 0:
        # pluss
        ret = 0
        for item in pluss:
            ret += bisect.bisect_right(pluss, mid // item)
            if item * item <= mid:
                ret -= 1
        cnt += ret // 2
        ret = 0
        for item in minuss:
            ret += m_len - bisect.bisect_left(minuss, (mid + item - 1) // item)
            if item * item <= mid:
                ret -= 1
        cnt += ret // 2
        # minus
        cnt += minus_num
        # zeros
        cnt += zeros_num
    elif mid == 0:
        # minus
        cnt += minus_num
        # zeros
        cnt += zeros_num
    else:
        for item in pluss:
            cnt += bisect.bisect_right(minuss, mid // item)
    if cnt >= k:
        r = mid
    else:
        l = mid
print(r)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.readline

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

    minus = []
    plus = []
    zero = 0
    for a in A:
        if a > 0:
            plus.append(a)
        elif a < 0:
            minus.append(-a)
        else:
            zero += 1
    plus.sort()
    minus.sort()
    plus_num = len(plus)
    minus_num = len(minus)
    if plus_num * minus_num < K <= (N*(N-1))//2 - (plus_num*(plus_num-1))//2 - (minus_num*(minus_num-1))//2:
        print(0)
        exit()
    if plus_num * minus_num >= K:
        ng = 0
        ok = -10**18-1
        mid = (ng+ok)//2
        while ng - ok > 1:
            cnt = 0
            j = 0
            for a in minus:
                while True:
                    if j == plus_num:
                        break
                    if a * plus[j] < -mid:
                        #print(a, plus[j])
                        j += 1
                    else:
                        break
                cnt += plus_num - j
            if cnt < K:
                ok = mid
            else:
                ng = mid
            mid = (ok+ng)//2
        print(ng)
    else:
        K -= (N*(N-1))//2 - (plus_num*(plus_num-1))//2 - (minus_num*(minus_num-1))//2
        ng = 10**18+1
        ok = 0
        mid = (ok+ng)//2
        while ng - ok > 1:
            cnt = 0
            j = plus_num-1
            for a in plus:
                while True:
                    if j == -1:
                        break
                    if a * plus[j] > mid:
                        j -= 1
                    else:
                        break
                cnt += j+1
            for a in plus:
                if a**2 <= mid:
                    cnt -= 1
                else:
                    break
            j = minus_num-1
            for a in minus:
                while True:
                    if j == -1:
                        break
                    if a * minus[j] > mid:
                        j -= 1
                    else:
                        break
                cnt += j+1
            for a in minus:
                if a**2 <= mid:
                    cnt -= 1
                else:
                    break
            #print(cnt)
            assert cnt%2 == 0
            cnt //= 2
            if cnt < K:
                ok = mid
            else:
                ng = mid
            mid = (ok+ng)//2
        print(ng)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect


def check_neg(m, k, pos, neg, len_pos):
    less = 0
    j = 0
    for a in neg:
        d = m / a
        j = bisect(pos, d, lo=j)
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    less = 0
    for i in range(1, len_pos):
        a = pos[i]
        d = m // a
        j = bisect(pos, d, hi=i)
        less += j
    for i in range(1, len_neg):
        a = neg[i]
        d = m // a
        j = bisect(neg, d, hi=i)
        less += j
    return less < 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))

Submission status: Wrong Answer

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

    left_target=-10**18
    right_target=10**18
    while left_target<right_target-1:
        mid_target=(left_target+right_target)//2
        count=0
        for i in range(N-1):
            a=A[i]
            if a<0:
                if mid_target/a!=mid_target//a:
                    count+=(N-i-1)-bisect.bisect_right(A[i+1:],mid_target/a)
                else:
                    count+=(N-i-1)-bisect.bisect_right(A[i+1:],mid_target//a)
            elif a==0:
                if mid_target>0:
                    count+=(N-(i+1))
            elif a>0:
                if mid_target/a!=mid_target//a:
                    count+=bisect.bisect_left(A[i+1:],mid_target/a)
                else:
                    count+=bisect.bisect_left(A[i+1:],mid_target//a)
        if count<K:
            left_target=mid_target
        else:
            right_target=mid_target
        #print("m:",mid_target,"c:",count)
    print(left_target)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

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

    left_target=-10**18
    right_target=10**18
    while left_target<right_target-1:
        mid_target=(left_target+right_target)//2
        count=0
        for i in range(N-1):
            a=A[i]
            if a<0:
                if mid_target/a!=mid_target//a:
                    count+=(N-i-1)-bisect.bisect_right(A[i+1:],mid_target/a)
                else:
                    count+=(N-i-1)-bisect.bisect_right(A[i+1:],mid_target//a)
            elif a==0:
                if mid_target>0:
                    count+=(N-(i+1))
            elif a>0:
                if mid_target/a!=mid_target//a:
                    count+=bisect.bisect_left(A[i+1:],mid_target/a)
                else:
                    count+=bisect.bisect_left(A[i+1:],mid_target//a)
        if count<K:
            left_target=mid_target
        else:
            right_target=mid_target
        #print("m:",mid_target,"c:",count)
    print(left_target)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import bisect

n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
minuss = []
pluss = []
zeros = []
for item in a:
    if item > 0:
        pluss.append(item)
    elif item < 0:
        minuss.append(item)
    else:
        zeros.append(0)
pluss.sort()
minuss.sort()
a.sort()

p_len = len(pluss)
m_len = len(minuss)
z_len = len(zeros)

minus_num = p_len * m_len
zeros_num = z_len * (z_len - 1) // 2 + z_len * (m_len + p_len)

l = - 10**19; r = 10**19
while r - l > 1:
    mid = (l + r) // 2
    cnt = 0
    if mid > 0:
        # pluss
        ret = 0
        for item in pluss:
            ret += bisect.bisect_right(pluss, mid // item)
            if item * item <= mid:
                ret -= 1
        cnt += ret // 2
        ret = 0
        for item in minuss:
            ret += m_len - bisect.bisect_right(minuss, mid // item)
            if item * item <= mid:
                ret -= 1
        cnt += ret // 2
        # minus
        cnt += minus_num
        # zeros
        cnt += zeros_num
    elif mid == 0:
        # minus
        cnt += minus_num
        # zeros
        cnt += zeros_num
    else:
        for item in pluss:
            cnt += bisect.bisect_right(minuss, mid // item)
    if cnt >= k:
        r = mid
    else:
        l = mid
print(r)

Submission status: Wrong Answer

Solution code:
# これは500点では？
import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a) # numpy の array で高速化
a.sort()

def count(x): # 積が x 以下のペアは何個あるか？
  ans = 0
  for i in a:
    ans -= i * i <= x # 同じもの2つは選べない
    if i == 0:
      if x >= 0:
        ans += n
    elif i > 0:
      ans += np.searchsorted(a, x // i, side="right") # 二分探索
    else:
      ans += n - np.searchsorted(a, x // i, side="left")
  return ans // 2

ok = 10**18
ng = -ok - 1
while ok - ng > 1: # 二分探索
  cen = (ok + ng) // 2
  if count(cen) >= k:
    ok = cen
  else:
    ng = cen
print(ok)

Submission status: Wrong Answer

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

gl = -1e18
gr = 1e18

def ok():
  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]**2 < x):
      total -= 1
  total = total // 2
  return total < k
      

while (gl+1 < gr):
  x = (gl+gr) // 2
  if(ok()):
    gl = x
  else:
    gr = x
  
print(int(gl))

Submission status: Wrong Answer

Solution code:
import sys
# スペース区切りの整数入力
N,K = map(int, input().split())
# スペース区切りの整数をリストに入力
a = []
am = []
az = []
ap = []

for x in list(map(int, input().split())):
    if x > 0:
        ap.append(x)
    elif x == 0:
        az.append(x)
    else:
        am.append(x)
    a.append(x)

n = len(a)*(len(a)-1) // 2
nm = len(am)*len(ap)
nz = len(az)*(len(az)-1) // 2 + len(az)*(len(am)+len(ap))
np = len(am)*(len(am)-1) // 2 + len(ap)*(len(ap)-1) // 2

print(n,nm,nz,np,nm+nz+np)

xl = []
if K <= nm:
    for i in range(len(am)):
        for j in range(len(ap)):
            xl.append(am[i]*ap[j])
elif K - nm <= nz:
    print(0)
    sys.exit()
else:
    K = K - nm - nz
    for i in range(len(am)-1):
        for j in range(i+1,len(am)):
            xl.append(am[i]*am[j])
    for i in range(len(ap)-1):
        for j in range(i+1,len(ap)):
            xl.append(ap[i]*ap[j])

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