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:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
p = []
z = []
m = []
for i in range(n):
    if a[i] > 0:
        p.append(a[i])
    elif a[i] == 0:
        z.append(a[i])
    else:
        m.append(a[i])
nb1 = -10**18-1
nb2 = 10**18+1
p1 = len(p)
z1 = len(z)
m1 = len(m)
#print(p,m)
#print(p1,z1,m1)
def sytr(x,p,z,m,p1,z1,m1):
    ans = 0
    ans2 = 0
    ans3 = -10**18
    if x > 0:
        m.sort(reverse=True)
        p.sort()
        ans += p1*m1 + (p1+m1)*z1 + (z1-1)*z1//2
        ans2 += ans
        now = 0
        #print(p)
        now1 = p1-1
        now2 = 0
        now3 = p1-1
        if p1 > 1:
            while now < now1:
                if p[now]*p[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,p[now]*p[now1])
                    ans += now1-now
                    now += 1
            while now2 < now3:
                if p[now2]*p[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3 - now2
                    now2 += 1
        if m1 > 1:
            now = 0
            now1 = m1-1
            now2 = 0
            now3 = m1-1
            while now < now1:
                if m[now]*m[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,m[now]*m[now1])
                    ans += now1 - now
                    now += 1
            while now2 < now3:
                if m[now2]*m[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3 - now2
                    now2 += 1
    elif x == 0:
        p.sort()
        m.sort()
        if p1 > 0 and m1 > 0:
            ans3 = p[0]*m[m1-1]
        if z1 > 0:
            ans3 = 0
        ans += p1*m1
        ans2 += (p1+m1)*z1 + ans
    else:
        p.sort(reverse=True)
        m.sort()
        now = 0
        now1 = m1-1
        now2 = 0
        now3 = m1-1
        if p1 > 0 and m1 > 0:
            while now < p1 and now1 >= 0:
                if p[now]*m[now1] > x:
                    now1 -= 1
                else:
                    ans3 = max(ans3,p[now]*m[now1])
                    ans += now1+1
                    now += 1
            while now2 < p1 and now3 >= 0:
                if p[now2]*m[now3] >= x:
                    now3 -= 1
                else:
                    ans2 += now3+1
                    now2 += 1
    return [ans,ans2,ans3]
while nb1 + 1 < nb2:
    #print(nb1,nb2)
    x = (nb1+nb2)//2
    #print(sytr(x,p,z,m,p1,z1,m1))
    if max(sytr(x,p,z,m,p1,z1,m1)[0],sytr(x,p,z,m,p1,z1,m1)[1]) < k:
        nb1 = x
    elif min(sytr(x,p,z,m,p1,z1,m1)[0],sytr(x,p,z,m,p1,z1,m1)[1]) > k:
        nb2 = x
    else:
        if abs(sytr(x,p,z,m,p1,z1,m1)[1]-sytr(x,p,z,m,p1,z1,m1)[0]) == 0:
            x = sytr(x,p,z,m,p1,z1,m1)[2]
            break
        else:
            break
print(x)

Submission status: Wrong Answer

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

count = -K
values = []
for i in range(N):
    for j in range(N-1, i, -1):
        values.append(A[i] * A[j])
        count += 1
        # if abs(A[i]) > abs(A[j]):
        #     break
        if K < count:
            break
    if K < count:
        break

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    s = [0]*n
    l, r = 0, 0
    if k <= num_neg_pair:
        l = neg_a[0] * pos_a[cnt_pos-1]
        r = neg_a[cnt_neg-1] * pos_a[0]+1
    elif k <= num_neg_pair + num_zro_pair:
        l = 0
        r = 0
    else:
        if cnt_neg >= 2 and cnt_pos >= 2:
            l = min(neg_a[cnt_neg-1]*neg_a[cnt_neg-2], pos_a[0]*pos_a[1])
        elif cnt_neg >= 2:
            l = neg_a[cnt_neg-1]*neg_a[cnt_neg-2]
        else:
            l = pos_a[0]*pos_a[1]
        if cnt_neg >= 2 and cnt_pos >= 2:
            r = max(neg_a[0]*neg_a[1], pos_a[cnt_pos-1]*pos_a[cnt_pos-2])+1
        elif cnt_neg >= 2:
            r = neg_a[0]*neg_a[1]+1
        else:
            r = pos_a[cnt_pos-1]*pos_a[cnt_pos-2]+1
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = 0
                if target < 0:
                    index = bisect_right(neg_a, target)
                elif target == 0:
                    index = cnt_neg + cnt_zro
                else:
                    index = bisect_right(pos_a, target)
                    index += cnt_neg + cnt_zro
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = 0
                if target < 0:
                    index = bisect_left(neg_a, target)
                elif target == 0:
                    index = cnt_neg + 1
                else:
                    index = bisect_left(pos_a, target)
                    index += cnt_neg + cnt_zro
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 < p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s = [0]*n
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        for i, v in enumerate(a):
            if v < 0:
                target = p // v
                index = bisect_right(a, target)
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif v > 0:
                target = (p+a[i]-1) // v
                index = bisect_left(a, target)
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                if 0 <= p:
                    s[i] = n - 1
                else:
                    s[i] = 0
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    l, r = -1*10**16, 10**16
    while l+1 < r:
        p = (l+r)//2
        tot = 0
        for i in range(n):
            sl, sr = -1, n
            if a[i] < 0:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sr = sp
                    else:
                        sl = sp
                tot += n-sr
            else:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sl = sp
                    else:
                        sr = sp
                tot += sr
            if a[i]**2 < p:
                tot -= 1
        tot //= 2
        if tot < k:
            l = p
        else:
            r = p
    print(l)
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s = [0]*n
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        for i in range(n):
            if a[i] < 0:
                target = p // a[i]
                index = bisect_right(a, target)
                s[i] = n - index
                if index <= i:
                    s[i] -= 1
            elif a[i] > 0:
                target = (p+a[i]-1) // a[i]
                index = bisect_left(a, target)
                s[i] = index
                if i < index:
                    s[i] -= 1
            else:
                s[i] = n - 1
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s = [0]*n
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        for i in range(n):
            if a[i] < 0:
                target = (-p-1) // (-a[i])
                index = bisect_right(a, target)
                s[i] = n - index
            elif a[i] > 0:
                target = p // a[i]
                index = bisect_right(a, target)
                s[i] = index
            else:
                s[i] = n
            if a[i]**2 < p or a[i] == 0:
                s[i] -= 1
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        tot = 0
        for i in range(n):
            if a[i] < 0:
                target = (p) // a[i]
                index = bisect_right(a, target)
                tot += n - index
            elif a[i] > 0:
                target = (p+a[i]-1) // a[i]
                index = bisect_left(a, target)
                tot += index
            else:
                tot += n
            if a[i]**2 < p:
                tot -= 1
        tot //= 2
        if tot < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mns = []
pls = []
for x in a:
  if x < 0: mns.append(x)
  if x > 0: pls.append(x)
zero = N - len(mns) - len(pls)

def mncheck(x):
  res = 0
  ng = 0
  for i in range(len(mns) - 1, -1, -1):
    while ng < len(mns) and (mns[i] * pls[ng]) <= x: ng += 1
    res += ng
  return res >= K

def plcheck(x):
  res = 0
  ng = 0
  for i in range(len(mns) - 1, -1, -1):
    while ng < len(mns) and (mns[i] * mns[ng]) <= x: ng += 1
    res += max(0, ng - i - 1)
  ng = 0
  for i in range(len(pls) - 1, -1, -1):
    while ng < len(pls) and (pls[i] * pls[ng]) <= x: ng += 1
    res += max(0, ng - i - 1)
  return res >= K - (len(mns) * len(pls) + zero * (zero - 1) // 2 + zero * (N - zero))


if len(mns) * len(pls) >= K:
  pls.append(0)
  ok = 0
  ng = -pow(10, 18)
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mncheck(m): ok = m
    else: ng = m
  print(ok)
elif len(mns) * len(pls) + zero * (zero - 1) // 2 + zero * (N - zero) >= K:
  print(0)
else:
  mns.reverse()
  for i in range(len(mns)): mns[i] = -mns[i]
  ng = 0
  ok = pow(10, 18)
  while ok - ng > 1:
    m = (ok + ng) // 2
    if plcheck(m): ok = m
    else: ng = m
  print(ok)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mns = []
pls = []
for x in a:
  if x < 0: mns.append(x)
  if x > 0: pls.append(x)
zero = N - len(mns) - len(pls)

def mncheck(x):
  res = 0
  ng = 0
  for i in range(len(mns) - 1, -1, -1):
    while ng < len(mns) and (mns[i] * pls[ng]) <= x: ng += 1
    res += ng
  return res >= K

def plcheck(x):
  res = 0
  ng = 0
  for i in range(len(mns) - 1, -1, -1):
    while ng < len(mns) and (mns[i] * mns[ng]) <= x: ng += 1
    res += max(0, ng - i - 1)
  ng = 0
  for i in range(len(pls) - 1, -1, -1):
    while ng < len(pls) and (pls[i] * pls[ng]) <= x: ng += 1
    res += max(0, ng - i - 1)
  return res >= K - (len(mns) * len(pls) + zero * (zero - 1) // 2 + zero * (N - zero))


if len(mns) * len(pls) >= K:
  pls.append(0)
  ok = 0
  ng = -pow(10, 18) - 1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mncheck(m): ok = m
    else: ng = m
  print(ok)
elif len(mns) * len(pls) + zero * (zero - 1) // 2 + zero * (N - zero) >= K:
  print(0)
else:
  mns.reverse()
  for i in range(len(mns)): mns[i] = -mns[i]
  ng = 0
  ok = pow(10, 18)
  while ok - ng > 1:
    m = (ok + ng) // 2
    if plcheck(m): ok = m
    else: ng = m
  print(ok)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
pY = []
mY = []
z = 0
for x in X:
    if x > 0:
        pY.append(x)
    elif x < 0:
        mY.append(x)
    else:
        z += 1

def bsearch(mn, mx, func):
    #func(i)=False を満たす最大のi
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mx = (idx + mn)//2, idx
            continue
        idx, mn = (idx + mx)//2, idx
    return idx


def count2(k):
    c = 0
    for y in pY:
        c = bsearch(-1, N, lambda i:X[i]*y>k) + 1
    for y in mY:
        c += N-(bsearch(-1, N, lambda i:X[i]*y<=k)+1)
    if k >= 0:
        c += N*z
    for x in X:
        if x*x <=k:
            c -= 1
    c = c//2
    return c


def count(k):
    # x*y <= k を満たすx,yの個数
    c = 0
    for i in range(N):
        for j in range(i+1, N):
            if X[i]*X[j] <= k:
                c += 1
    return c

x = bsearch(-10**18, 10**18, lambda x : count2(x)>=K)
print(x+1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
d1=[]
d2=[]
zeros=0
for i in range(N):
    if A[i]>0:
        d1.append(A[i])
    elif A[i]==0:
        zeros+=1
    else:
        d2.append(-A[i])
d1.sort()
d2.sort()
L1=len(d1)
L2=len(d2)

if L1*L2>=K:
    print(0)

    
elif L1*(L1-1)//2+L2*(L2-1)//2<=N*(N-1)//2-K:
    print(0)

else:
    K-=N*(N-1)//2-(L1*(L1-1)//2+L2*(L2-1)//2)
    #d1から二つ、d2から二つ選ぶ組のうちK番目に小さいもの
    
    low=0
    high=10**18+1
    while high-low>1:
        mid=(high+low)//2
        
        ind=L1-1
        cnt=0
        for i in range(L1):
            u=d1[i]
            nnn=mid//u
            ind=L1-1
            while ind>=0 and d1[ind]>nnn:
                ind-=1
            if ind==-1:
                break
            if ind>=i:
                cnt+=ind
            else:
                cnt+=ind+1
                
        ind=L2-1
        for i in range(L2):
            u=d2[i]
            nnn=mid//u
            ind=L2-1
            while ind>=0 and d2[ind]>nnn:
                ind-=1
            if ind==-1:
                break
            if ind>=i:
                cnt+=ind
            else:
                cnt+=ind+1
        
        if cnt//2<K:
            low=mid
        else:
            high=mid
    
    print(high)

Submission status: Wrong Answer

Solution code:
import numpy as np


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

A = list(map(int,input().split(' ')))
A = np.array(A)
A.sort()

#print(A)

l = -10**18
r = 10**18
#l=-100
#r = 100

num_pos = np.count_nonzero(A>0)
num_zero = np.count_nonzero(A==0)
num_neg = np.count_nonzero(A<0)

def count(mid):
    cnt = 0
    #print(f'mimdn:{mid}')
    for a in A:
        if a>0:
            cnt += np.searchsorted(A,mid//a,side="right")
            #print('search',end=" ")
            #print(mid//a)
        elif a==0:
            if mid>0:
                cnt += N 
        else:
            cnt += (N-np.searchsorted(A,(-mid-1)//(-a),side="right"))
            #print('search',end=" ")
            #print(mid//a)
        #print(cnt,end=" ")
    cnt -= np.count_nonzero(A*A<mid)
    #print('a',end=" ")
    #print(cnt,end=" ")
    cnt = cnt//2
    #print(cnt)
    return cnt



while l+1<r:
    mid = (r+l)//2
    cnt = count(mid)
    if cnt < K:
        l = mid
    else:
        r = mid
    #print(f'mid:{mid}: cnt{cnt}')
print(r)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mina = []
zera = []
plua = []
for x in a:
  if x > 0: plua.append(x)
  elif x == 0: zera.append(x)
  else: mina.append(x)
mina.reverse()
mlim = len(mina) * len(plua)
zlim = len(zera) * (len(mina) + len(plua)) + len(zera) * (len(zera) - 1) // 2 + mlim

def minacheck(x):
  res = 0
  j = 0
  for i in range(len(plua)):
    while j < len(mina) and (plua[i] * mina[j]) <= x: j += 1
    res += j
  return res >= K

def pluacheck(x):
  res = 0
  j = 0
  for i in range(len(mina) - 1, -1, -1):
    while j < len(mina) and (mina[i] * mina[j] <= x): j += 1
    res += max(0, j - i - 1)
  j = 0
  for i in range(len(plua) - 1, -1, -1):
    while j < len(plua) and (plua[i] * plua[j] <= x): j += 1
    res += max(0, j - i - 1)
  return res + zlim >= K

if K <= mlim:
  ng = -pow(10, 18)
  ok = 0
  while ok - ng > 1:
    m = (ok + ng) // 2
    if minacheck(m): ok = m
    else: ng = m
  print(ok)
elif K <= zlim: print(0)
else:
  ng = 0
  ok = pow(10, 18)
  while ok - ng > 1:
    m = (ok + ng) // 2
    if pluacheck(m): ok = m
    else: ng = m
  print(ok)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = np.array(a)
a.sort()
p = a[a>0]
z = a[a==0]
m = a[a<0]
low = -10**18
high = 10**18
while high-low>1:
    mid = (high + low) //2
    count = 0
    if mid >= 0:
        count += len(z)*n
    count += a.searchsorted(mid//p,side = "right").sum()
    count += (n-a.searchsorted(-(-mid//m),side = "left")).sum()
    count -= np.count_nonzero(a*a <= mid)
    count /= 2
    print(count)
    if count >= k:
        high = mid
    if count < k:
        low = mid
print(high)

Submission status: Wrong Answer

Solution code:
def inputs(): return [int(x) for x in input().split()]
import bisect
n,k = inputs()
n1 = (n-1)*n//2
a = inputs()
a.sort()
#print(a)
minus = int(bisect.bisect_left(a,0))
plus = int(bisect.bisect_right(a,0))
zero = plus-minus
#print(zero,plus,minus)
ok=10**20 #可能
ng=-10**20 #不可能
while 1<abs(ng-ok):
    mid=(ng+ok)//2
    if mid>=0:
        cnt=0
        cnt2=0
        for i in range(plus,len(a)):
            a1 = mid//a[i]
            cnt1 = int(bisect.bisect_right(a,a1))
            cnt+=cnt1-zero-(1 if a1>=a[i] else 0)
        #print(cnt,mid,cnt2)
        for i in range(0,minus):
            a1 = mid//a[i]
            if a1<=a[i]:
                cnt2+=1
            cnt1 = int(bisect.bisect_left(a,a1))
            #print(a1,cnt1,a[i])
            cnt += (n-cnt1)-zero-(1 if a1<=a[i] else 0)
        cnt = cnt//2+max((zero*(zero-1))//2,0)+zero*(n-zero)
        #print(cnt2,mid,cnt)
        if k<=cnt:#条件
            ok=mid
        else:
            ng=mid
    elif mid<0:
        cnt=0
        cnt2=0
        for i in range(plus,len(a)):
            a1 = (abs(mid)+abs(a[i])-1)//abs(a[i])
            a1 = a1*-1
            cnt1 = int(bisect.bisect_right(a,a1))
            cnt+=cnt1-(1 if a1>=a[i] else 0)
        #print(cnt,mid,cnt2)
        for i in range(0,minus):
            a1 = (abs(mid)+abs(a[i])-1)//abs(a[i])
            if a1<=a[i]:
                cnt2+=1
            cnt1 = int(bisect.bisect_left(a,a1))
            #print(a1,cnt1,a[i])
            cnt += (n-cnt1)-(1 if a1<=a[i] else 0)
        cnt = cnt//2#+max((zero*(zero-1))//2,0)+zero*(n-zero)
        #print(cnt2,mid,cnt)
        if k<=cnt:#条件
            ok=mid
        else:
            ng=mid
print(ok)

Submission status: Wrong Answer

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

# process/output

# マイナス、プラスに分類
Am = []
Ap = []
zeroNum = 0
for i in range(N):
    if A[i] < 0:
        Am.append(A[i])
    elif A[i] > 0:
        Ap.append(A[i])

# Kの数値で分岐し、結果を出力
B = []
mNum = len(Am)*len(Ap)
zNum = (N-len(Am)-len(Ap))*(N-1)

if K <= mNum:
    for i in range(len(Am)):
        for j in range(len(Ap)):
            B.append(Am[i]*Ap[j])
    B.sort()
    print(B[K-1])

elif K <= mNum+zNum:
    print(0)

else:
    for i in range(len(Am)-1):
        for j in range(i+1, len(Am)):
            B.append(Am[i]*Am[j])

    for i in range(len(Ap)-1):
        for j in range(i+1, len(Ap)):
            B.append(Ap[i]*Ap[j])

    B.sort()
    print(B[K-mNum-zNum-1])

Submission status: Wrong Answer

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

# process/output

# マイナス、プラスに分類
Am = []
Ap = []
zeroNum = 0
for i in range(N):
    if A[i] < 0:
        Am.append(A[i])
    elif A[i] > 0:
        Ap.append(A[i])

zeroNum = N-len(Am)-len(Ap)

# Kの数値で分岐し、結果を出力
B = []
if K <= len(Am)*len(Ap):
    for i in range(len(Am)):
        for j in range(len(Ap)):
            B.append(Am[i]*Ap[j])
    B.sort()
    print(B[K-1])

elif K <= len(Am)*len(Ap) + zeroNum*(N-1):
    print(0)

else:
    for i in range(len(Am)-1):
        for j in range(i+1, len(Am)):
            B.append(Am[i]*Am[j])

    for i in range(len(Ap)-1):
        for j in range(i+1, len(Ap)):
            B.append(Ap[i]*Ap[j])

    B.sort()
    print(B[K-N*(N-1)//2-1])

Submission status: Wrong Answer

Solution code:
def inputs(): return [int(x) for x in input().split()]
import bisect
n,k = inputs()
n1 = (n-1)*n//2
a = inputs()
a.sort()
#print(a)
minus = int(bisect.bisect_left(a,0))
plus = int(bisect.bisect_right(a,0))
zero = plus-minus
#print(zero,plus,minus)
if k>=minus*(len(a)-minus):
    k1 = n1-minus*(len(a)-minus)
    ok=10**20 #可能
    ng=-1 #不可能
    while 1<abs(ng-ok):
        mid=(ng+ok)//2
        cnt=0
        cnt2=0
        for i in range(plus,len(a)):
            a1 = mid//a[i]
            cnt1 = int(bisect.bisect_right(a,a1))
            cnt+=cnt1-zero-(1 if a1>=a[i] else 0)
        #print(cnt,mid,cnt2)
        for i in range(0,minus):
            a1 = mid//a[i]
            if a1<=a[i]:
                cnt2+=1
            cnt1 = int(bisect.bisect_left(a,a1))
            #print(a1,cnt1,a[i])
            cnt += (n-cnt1)-zero-(1 if a1<=a[i] else 0)
        cnt = cnt//2+max((zero*(zero-1))//2,0)+zero*(n-zero)
        #print(cnt2,mid,cnt)
        if k<=cnt:#条件
            ok=mid
        else:
            ng=mid
    print(ok)
elif k<minus*(len(a)-minus):
    ok=1 #可
    ng=-10**18 #不可能
    while 1<abs(ng-ok):
        mid=(ng+ok)//2
        cnt=0
        cnt2=0
        for i in range(plus,len(a)):
            a1 = mid//a[i]
            cnt1 = int(bisect.bisect_right(a,a1))
            cnt+=cnt1-(1 if a1>=a[i] else 0)
        #print(cnt,mid,cnt2)
        for i in range(0,minus):
            a1 = (abs(mid)+abs(a[i])-1)//abs(a[i])
            if a1<=a[i]:
                cnt2+=1
            cnt1 = int(bisect.bisect_left(a,a1))
            #print(a1,cnt1,a[i])
            cnt += (n-cnt1)-(1 if a1<=a[i] else 0)
        cnt = cnt//2#+max((zero*(zero-1))//2,0)+zero*(n-zero)
        #print(mid,cnt)
        if k<=cnt:#条件
            ok=mid
        else:
            ng=mid
    print(ok)

Submission status: Wrong Answer

Solution code:
def inputs(): return [int(x) for x in input().split()]
import bisect
n,k = inputs()
n1 = (n-1)*n//2
a = inputs()
a.sort()
#print(a)
minus = int(bisect.bisect_left(a,0))
plus = int(bisect.bisect_right(a,0))
zero = plus-minus
#print(zero,plus,minus)
if k>=minus*(len(a)-minus):
    k1 = n1-minus*(len(a)-minus)
    ok=10**20 #可能
    ng=-1 #不可能
    while 1<abs(ng-ok):
        mid=(ng+ok)//2
        cnt=0
        cnt2=0
        for i in range(plus,len(a)):
            a1 = mid//a[i]
            cnt1 = int(bisect.bisect_right(a,a1))
            cnt+=cnt1-zero-(1 if a1>=a[i] else 0)
        #print(cnt,mid,cnt2)
        for i in range(0,minus):
            a1 = mid//a[i]
            cnt1 = int(bisect.bisect_left(a,a1))
            #print(a1,cnt1,a[i])
            cnt += (n-cnt1)-zero-(1 if a1<=a[i] else 0)
        cnt = cnt//2+max((zero*(zero-1))//2,0)+zero*(n-zero)
        #print(cnt2,mid,cnt)
        if k<=cnt:#条件
            ok=mid
        else:
            ng=mid
    print(ok)
elif k<minus*(len(a)-minus):
    ok=1 #可
    ng=-10**18 #不可能
    while 1<abs(ng-ok):
        mid=(ng+ok)//2
        cnt=0
        cnt2=0
        for i in range(plus,len(a)):
            a1 = mid//a[i]
            cnt1 = int(bisect.bisect_right(a,a1))
            cnt+=cnt1-(1 if a1>=a[i] else 0)
        #print(cnt,mid,cnt2)
        for i in range(0,minus):
            a1 = (mid+a[i]-1)//a[i]
            if a1<=a[i]:
                cnt2+=1
            cnt1 = int(bisect.bisect_left(a,a1))
            #print(a1,cnt1,a[i])
            cnt += (n-cnt1)-(1 if a1<=a[i] else 0)
            #if mid==-13:
                #print(a1,a[i],cnt,cnt1)
        cnt = cnt//2#+max((zero*(zero-1))//2,0)+zero*(n-zero)
        #print(mid,cnt)
        if k<=cnt:#条件
            ok=mid
        else:
            ng=mid
    print(ok)

Submission status: Wrong Answer

Solution code:
def inputs(): return [int(x) for x in input().split()]
import bisect
n,k = inputs()
n1 = (n-1)*n//2
a = inputs()
a.sort()
#print(a)
minus = int(bisect.bisect_left(a,0))
plus = int(bisect.bisect_right(a,0))
zero = plus-minus
#print(zero,plus,minus)
if k>=minus*(len(a)-minus):
    k1 = n1-minus*(len(a)-minus)
    ok=10**20 #可能
    ng=-1 #不可能
    while 1<abs(ng-ok):
        mid=(ng+ok)//2
        cnt=0
        cnt2=0
        for i in range(plus,len(a)):
            a1 = mid//a[i]
            cnt1 = int(bisect.bisect_right(a,a1))
            cnt+=cnt1-zero-(1 if a1>=a[i] else 0)
        #print(cnt,mid,cnt2)
        for i in range(0,minus):
            a1 = mid//a[i]
            if a1<=a[i]:
                cnt2+=1
            cnt1 = int(bisect.bisect_left(a,a1))
            #print(a1,cnt1,a[i])
            cnt += (n-cnt1)-zero-(1 if a1<=a[i] else 0)
        cnt = cnt//2+max((zero*(zero-1))//2,0)+zero*(n-zero)
        #print(cnt2,mid,cnt)
        if k<=cnt:#条件
            ok=mid
        else:
            ng=mid
    print(ok)
elif k<minus*(len(a)-minus):
    ok=1 #可
    ng=-10**18 #不可能
    while 1<abs(ng-ok):
        mid=(ng+ok)//2
        cnt=0
        cnt2=0
        for i in range(plus,len(a)):
            a1 = mid//a[i]
            cnt1 = int(bisect.bisect_right(a,a1))
            cnt+=cnt1-(1 if a1>=a[i] else 0)
        #print(cnt,mid,cnt2)
        for i in range(0,minus):
            a1 = (mid+a[i]-1)//a[i]
            if a1<=a[i]:
                cnt2+=1
            cnt1 = int(bisect.bisect_left(a,a1))
            #print(a1,cnt1,a[i])
            cnt += (n-cnt1)-(1 if a1<=a[i] else 0)
            #if mid==-13:
                #print(a1,a[i],cnt,cnt1)
        cnt = cnt//2#+max((zero*(zero-1))//2,0)+zero*(n-zero)
        #print(mid,cnt)
        if k<=cnt:#条件
            ok=mid
        else:
            ng=mid
    print(ok)

Submission status: Wrong Answer

Solution code:
def inputs(): return [int(x) for x in input().split()]
import bisect
n,k = inputs()
n1 = (n-1)*n//2
a = inputs()
a.sort()
#print(a)
minus = int(bisect.bisect_left(a,0))
plus = int(bisect.bisect_right(a,0))
zero = plus-minus
#print(zero,plus,minus)
if k>=minus*(len(a)-minus):
    k1 = n1-minus*(len(a)-minus)
    ok=10**20 #可能
    ng=-1 #不可能
    while 1<abs(ng-ok):
        mid=(ng+ok)//2
        cnt=0
        cnt2=0
        for i in range(plus,len(a)):
            a1 = mid//a[i]
            cnt1 = int(bisect.bisect_right(a,a1))
            cnt+=cnt1-zero-(1 if a1>=a[i] else 0)
        #print(cnt,mid,cnt2)
        for i in range(0,minus):
            a1 = mid//a[i]
            if a1<=a[i]:
                cnt2+=1
            cnt1 = int(bisect.bisect_left(a,a1))
            #print(a1,cnt1,a[i])
            cnt += (n-cnt1)-zero-(1 if a1<=a[i] else 0)
        cnt = cnt//2+max((zero*(zero-1))//2,0)+zero*(n-zero)
        #print(cnt2,mid,cnt)
        if k<=cnt:#条件
            ok=mid
        else:
            ng=mid
    print(ok)
elif k<minus*(len(a)-minus):
    ok=1 #可
    ng=-10**18 #不可能
    while 1<abs(ng-ok):
        mid=(ng+ok)//2
        cnt=0
        cnt2=0
        for i in range(plus,len(a)):
            a1 = mid//a[i]
            cnt1 = int(bisect.bisect_right(a,a1))
            cnt+=cnt1-(1 if a1>=a[i] else 0)
        #print(cnt,mid,cnt2)
        for i in range(0,minus):
            a1 = (mid+a[i]-1)//a[i]
            if a1<=a[i]:
                cnt2+=1
            cnt1 = int(bisect.bisect_left(a,a1))
            #print(a1,cnt1,a[i])
            cnt += (n-cnt1)-(1 if a1<=a[i] else 0)
            if mid==-13:
                print(a1,a[i],cnt,cnt1)
        cnt = cnt//2#+max((zero*(zero-1))//2,0)+zero*(n-zero)
        #print(mid,cnt)
        if k<=cnt:#条件
            ok=mid
        else:
            ng=mid
    print(ok)

Submission status: Wrong Answer

Solution code:
import bisect
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
mib = -10 ** 18 * 2
mab = 10 ** 18 * 2
c = 0
while mib != mab:
    b = (mib + mab) // 2
    co = 0
    for i in a:
        mi = 0
        ma = n - 1
        if i > 0:
            if i * a[0] > b:
                continue
            co += bisect.bisect_left(a, b // i+1)
        elif i == 0:
            if 0 <= b:
                co += n
        else:
            if i * a[-1] > b:
                continue
            co += n - bisect.bisect_right(a, b // i)
        if i * i <= b:
            co -= 1
    if co//2 >= k:
        mab = b
    else:
        mib = b + 1
print(mib)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math as m

def main(**kwargs):
    A.sort()
    rs = []
    maxr = 10 ** 9

    for i in range(n):
        for j in range(i+1, n):
            rs.append(A[i] * A[j])

            if len(rs) >= k and maxr < A[i] * A[j]:
                break

        rs.sort()
        rs = rs[:k]
        maxr = rs[-1]
        
    r = rs[k-1]
    return r

if __name__ == "__main__":
    cin = np.array(input().split(" ")).astype("int")
    n, k, *_ = cin

    cin = np.array(input().split(" ")).astype("int")
    A = np.array(cin)
    
    cout = main(n=n, k=k, A=A)
    print(cout)