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 bisect import bisect_left,bisect_right
n,k=map(int,input().split())
a=list(map(int,input().split()))
inf=10**20
a.sort()
mc=zc=pc=0
m=[]
p=[]
for i in a:
  if i<0:
    mc+=1
    m.append(i)
  elif i==0:
    zc+=1
  else:
    pc+=1
    p.append(i)
if mc*pc>=k:
  #ans<0
  for i in range(len(m)):m[i]*=-1
  k=mc*pc-k+1
  m=m[::-1]
  p=[0]+p
  ng=0
  ok=10**19+7
  mi=10**19+7
  while ng+1!=ok:
    ma=0
    mid=(ng+ok)//2
    co=0
    j=len(p)-1
    for i in m:
      while p[j]*i>mid:j-=1
      co+=j
      ma=max(ma,p[j]*i)
    if co<k:ng=mid
    else:
      ok=mid
      mi=min(mi,ma)
  print(-mi)
elif mc*pc+zc*(zc-1)//2+zc*(pc+mc)>=k:
  #ans=0
  print(0)
else:
  k-=mc*pc+zc*(zc-1)//2+zc*(pc+mc)
  for i in range(len(m)):m[i]*=-1
  m=m[::-1]
  m=[0]+m
  p=[0]+p
  ng=0
  ok=10**19+7
  mi=10**19+7
  while ng+1!=ok:
    ma=0
    mid=(ng+ok)//2
    co=0
    jjj=0
    j=len(p)-1
    for i in range(len(p)):
      if p[i]==0:continue
      while p[j]*p[i]>mid:j-=1
      jj=j-jjj
      if i<=j:jj-=1
      jjj=jj
      co+=jj
      ma=max(ma,p[j]*p[i])
    jjj=0
    j=len(m)-1
    for i in range(len(m)):
      if m[i]==0:continue
      while m[j]*m[i]>mid:j-=1
      jj=j-jjj
      if i<=j:jj-=1
      jjj=jj
      co+=jj
      ma=max(ma,m[j]*m[i])
    if co<k:ng=mid
    else:
      ok=mid
      mi=min(mi,ma)
  print(mi)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
n,k=map(int,input().split())
a=list(map(int,input().split()))
inf=10**20
a.sort()
mc=zc=pc=0
m=[]
p=[]
for i in a:
  if i<0:
    mc+=1
    m.append(i)
  elif i==0:
    zc+=1
  else:
    pc+=1
    p.append(i)
if mc*pc>=k:
  #ans<0
  for i in range(len(m)):m[i]*=-1
  k=mc*pc-k+1
  m=m[::-1]
  p=[0]+p
  print(m)
  print(p)
  ng=0
  ok=10**19+7
  mi=10**19+7
  while ng+1!=ok:
    ma=0
    mid=(ng+ok)//2
    co=0
    j=len(p)-1
    for i in m:
      while p[j]*i>mid:j-=1
      co+=j
      ma=max(ma,p[j]*i)
    if co<k:ng=mid
    else:
      ok=mid
      mi=min(mi,ma)
  print(-mi)
elif mc*pc+zc*(zc-1)//2+zc*(pc+mc)>=k:
  #ans=0
  print(0)
else:
  k-=mc*pc+zc*(zc-1)//2+zc*(pc+mc)
  for i in range(len(m)):m[i]*=-1
  m=m[::-1]
  m=[0]+m
  p=[0]+p
  print(m)
  print(p)
  print(k)
  ng=0
  ok=10**19+7
  mi=10**19+7
  while ng+1!=ok:
    ma=0
    mid=(ok+ng)//2
    co=0
    j=len(p)-1
    for i in range(len(p)):
      if p[i]==0:continue
      while p[j]*p[i]>mid:j-=1
      jj=j
      if i<=j:jj-=1
      co+=jj
      ma=max(ma,p[j]*p[i])
    j=len(m)-1
    for i in range(len(m)):
      if m[i]==0:continue
      while m[j]*m[i]>mid:j-=1
      jj=j
      if i<=j:jj-=1
      co+=jj
      ma=max(ma,m[j]*m[i])
    if co<k:ng=mid
    else:
      ok=mid
      mi=min(mi,ma)
  print(mi)

Submission status: Wrong Answer

Solution code:
#abc_155_d
import numpy as np
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = np.array(a)
a.sort()

plus = a[a>0]
zero = a[a==0]
minus= a[a<0]

left = -10**9
right = 10**9

while left+1 < right:
    mid = (left+right)//2
    cnt = 0
    
    if mid >=0:
        cnt += len(zero) * n
    
    cnt += a.searchsorted(mid//plus, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//minus), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt /= 2
    
    if cnt >= k:
        right = mid
    if cnt < k:
        left=mid
        
print(right)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

N,K = map(int,input().split())
A_s = list(map(int,input().split()))
minus = [-x for x in A_s if x < 0]
plus = [x for x in A_s if x >= 0]
minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        r = 0
        x -= x
        for num in minus[::-1]:
            while r < len(plus) and plus[r] * num < x:
                r += 1
            ans += len(minus) - r
        return ans
    r = 0
    for num in plus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(plus) and plus[r] * num <= x:
            r += 1
        ans += r
    r = 0
    for num in minus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(minus) and minus[r] * num <= x:
            r += 1
        ans += r
    ans //= 2
    ans += len(minus) * len(plus)
    return ans


top = 2 * (10**18) + 2
bottom = 0

while top - bottom  > 1:
    mid = (top + bottom) // 2
    if cnt(mid-(10**18+1)) < K:
        bottom = mid
    else:
        top = mid
print(int(top-(10**18+1)))

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mul = []
    for i in range(N):
        for j in range(i+1,N):
            mul.append(A[i]*A[j])
    mul = sorted(mul)
    print(mul)
    print(mul[K-1])
main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

minus = []
plus = []
zero = 0
for a in A:
    if a == 0:
        zero += 1
    elif a > 0:
        plus.append(a)
    else:
        minus.append(-a)

minus.sort()
plus.sort()
M = len(minus)
P = len(plus)
Z = zero * (M + P) + P * M + zero * (zero - 1) // 2

def cnt(x):
    if x == 0:
        return M * P
    elif x > 0:
        ret = 0
        for i, a in enumerate(plus):
            ret += max(bisect_right(plus, x // a) - i - 1, 0)
        for i, a in enumerate(minus):
            ret += max(bisect_right(minus, x // a) - i - 1, 0)
        return ret + Z
    else:
        x = -x
        ret = 0
        for a in minus:
            ret += P - bisect_left(plus, -(-x // a))
        return ret

overEq = 10**20
less = -10**20

for _ in range(100):
    mid = (overEq + less) // 2
    if cnt(mid) < K:
        less = mid
    else:
        overEq = mid

print(overEq)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

minus = []
plus = []
zero = 0
for a in A:
    if a == 0:
        zero += 1
    elif a > 0:
        plus.append(a)
    else:
        minus.append(-a)

minus.sort()
plus.sort()

def cnt(x):
    if x == 0:
        return len(minus) * len(plus)
    elif x > 0:
        ret = 0
        for i, a in enumerate(plus):
            ret += max(bisect_right(plus, x // a) - i - 1, 0)
        for i, a in enumerate(minus):
            ret += max(bisect_right(minus, x // a) - i - 1, 0)
        return ret + zero * (len(minus) + len(plus)) + len(plus) * len(minus) + zero * (zero - 1) // 2
    else:
        x = -x
        ret = 0
        for a in minus:
            ret += len(plus) - bisect_left(plus, -(-x // a))
        return ret

overEq = 10**20
less = -10**20

while overEq - less > 1:
    mid = (overEq + less) // 2
    if cnt(mid) < K:
        less = mid
    else:
        overEq = mid

print(overEq)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

minus = []
plus = []
zero = 0
for a in A:
    if a == 0:
        zero += 1
    elif a > 0:
        plus.append(a)
    else:
        minus.append(-a)

minus.sort()
plus.sort()

def cnt(x):
    if x == 0:
        return len(minus) * len(plus)
    elif x > 0:
        ret = 0
        for i, a in enumerate(plus):
            ret += bisect_right(plus[i + 1:], x // a)
        for i, a in enumerate(minus):
            ret += bisect_right(minus[i + 1:], x // a)
        return ret + zero * (len(minus) + len(plus)) + len(plus) * len(minus) + zero * (zero - 1) // 2
    else:
        x = -x
        ret = 0
        for a in minus:
            ret += len(plus) - bisect_left(plus, -(-x // a))
        return ret

overEq = 10**20
less = -10**20

while overEq - less > 1:
    mid = (overEq + less) // 2
    if cnt(mid) < K:
        less = mid
    else:
        overEq = mid

print(overEq)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
INF = 10**18+5
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a = np.sort(a)
    ap = a[a > 0]
    an = a[a < 0]
    zc = n * (n - ap.size - an.size)

    l = -INF
    r = INF
    while(l+1 < r):
        x = (l+r)//2

        total = (n-np.searchsorted(a, x // an, side='right')).sum()
        if x >= 0:
            total += zc
        total += np.searchsorted(a, x // ap, side='right').sum()
        total -= a[a*a <= x].size
        total //= 2
        if total < k:
            l = x
        else:
            r = x

    print(r)


main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:]
if q>0:
  AN=A[:q]
else:
  AN=[]

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  x=0
  y=10**18
  K=K-a-b
  if q<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()

  AN=AN[::-1]
  AN=-AN
  while y-x>1:
    tmp=(y+x)//2
    counter1=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
    counter2=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:]
if q>0:
  AN=A[:q]
else:
  AN=[]

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  x=0
  y=10**18
  K=K-a-b
  if q<=0:
    while y-x>1:
      tmp=(y+x)//2
      counter=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()

  AN=AN[::-1]
  AN=-AN
  while y-x>1:
    tmp=(y+x)//2
    counter1=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
    counter2=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)

Submission status: Wrong Answer

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

A_pos = []
A_neg = []
for i in range(len(A)):
    if (A[i] >= 0):
        A_pos.append(A[i])
    else:
        A_neg.append(A[i])

product = []

# product is negative
A_pos.sort(reverse=True)
A_neg.sort()
flag = False
for i in range(len(A_neg)):
    if ((K <= len(product)) and (product[K-1] <= A_neg[i]*A_pos[0])):
        flag = True
        break
    for j in range(len(A_pos)):
        product.append(A_neg[i]*A_pos[j])
    if (K <= len(product)):
        product.sort()

if (flag == True):
    print(product[K-1])
    exit(0)

# product is positive
A_pos.sort()
if (len(A_pos) < len(A_neg)):
    lim = "neg"
else:
    lim = "pos"

if (lim == "pos"):
    for i in range(len(A_pos)-1):
        if (K <= len(product)):
            if (product[K-1] <= A_pos[i]*A_pos[i+1]):
                if ((i+1) < len(A_neg)):
                     if (product[K-1] <= A_neg[i]*A_neg[i+1]):
                         break
        for j in range(i+1, len(A_pos)):
            if (i < len(A_neg) and j < len(A_neg)):
                product.append(A_neg[i]*A_neg[j])
                product.append(A_pos[i]*A_pos[j])
            else:
                product.append(A_pos[i]*A_pos[j])
        if (K <= len(product)):
            product.sort()
else:
    for i in range(len(A_neg)-1):
        if (K <= len(product)):
            if (product[K-1] <= A_neg[i]*A_neg[i+1]):
                if ((i+1) < len(A_pos)):
                     if (product[K-1] <= A_pos[i]*A_pos[i+1]):
                         break
        for j in range(i+1, len(A_neg)):
            if (i < len(A_pos) and j < len(A_pos)):
                product.append(A_neg[i]*A_neg[j])
                product.append(A_pos[i]*A_pos[j])
            else:
                product.append(A_neg[i]*A_neg[j])
        if (K <= len(product)):
            product.sort()

print(product[K-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:]
if q>0:
  AN=A[:q]
else:
  AN=[]

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  x=0
  y=10**18
  K=K-a-b
  if q<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  AN=AN[::-1]
  AN=-AN
  while y-x>1:
    tmp=(y+x)//2
    counter1=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
    counter2=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:]
if q>0:
  AN=A[:q]
else:
  AN=[]

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  x=0
  y=10**18
  if q<=1:
    K=K-b
    while y-x>1:
      tmp=(y+x)//2
      counter=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  K=K-a-b
  AN=AN[::-1]
  AN=-AN
  while y-x>1:
    tmp=(y+x)//2
    counter1=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
    counter2=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)

Submission status: Wrong Answer

Solution code:
n, k = (int(x) for x in input().split())
list = list(int(x) for x in input().split())
mul_1 = []
mul_2 = []


list.sort()
count_0 = list.count(0)
for cnt in range(count_0):
    list.remove(0)
for cnt in range(count_0):
    list.insert(0, 0)

count = int(count_0 * (2 * n - count_0 - 1) / 2)
for i in range(count):
    mul_1.append(0)


for i in range(count_0, n - 1):
    for j in range(i + 1, n):
        mul_2.append(list[i] * list[j])

mul_2.sort()
mul_1.extend(mul_2)

print(mul_1[k - 1])

Submission status: Wrong Answer

Solution code:
import sys
INF = 10**18+5
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    plus = 0
    minus = 0
    zero = 0
    for i in range(n):
        if a[i] > 0:
            plus += 1
        elif a[i] < 0:
            minus += 1
        else:
            zero += 1

    mc = minus*plus
    zc = (zero*(zero-1)/2) + (zero * (plus+minus))
    pc = (plus*(plus-1)/2) + (minus*(minus-1)/2)
    if mc >= k:
        l = -INF
        r = 0
        while(l+1 < r):
            x = (l+r)//2
            total = 0
            for i in range(minus):
                if a[i] < 0:
                    l2 = minus+zero-1
                    r2 = n
                    while(l2+1 < r2):
                        x2 = (l2+r2)//2
                        if a[x2]*a[i] >= x:
                            l2 = x2
                        else:
                            r2 = x2
                    total += n-r2
                if a[i]*a[i] < x:
                    total -= 1
            total //= 2
            if total < k:
                l = x
            else:
                r = x
        ans = l
    elif mc + zc >= k:
        ans = 0
    else:
        l = 0
        r = INF
        while(l+1 < r):
            x = (l+r)//2
            total = 0
            for i in range(n):
                if a[i] < 0:
                    l2 = -1
                    r2 = minus
                    while(l2+1 < r2):
                        x2 = (l2+r2)//2
                        if a[x2]*a[i] >= x:
                            l2 = x2
                        else:
                            r2 = x2
                    total += n-r2
                else:
                    l2 = minus+zero-1
                    r2 = n
                    while(l2+1 < r2):
                        x2 = (l2+r2)//2
                        if a[x2]*a[i] < x:
                            l2 = x2
                        else:
                            r2 = x2
                    total += r2
                if a[i]*a[i] < x:
                    total -= 1
            total //= 2
            if total < k:
                l = x
            else:
                r = x
        ans = l

    print(ans)


main()

Submission status: Wrong Answer

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


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


ans = []
for x in range(len(A)):
    for y in range(x+1, len(A)):
        ans.append(A[x]*A[y])
ans.sort()
print(ans)
print(ans[K-1])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
pa = []
ma = []
for x in A:
    if x > 0:
        pa.append(x)
    elif x < 0:
        ma.append(x)
P = len(pa)
M = len(ma)
pa.sort()
ma.sort()
T = n*(n-1)//2 - P*(P-1)//2 - M*(M-1)//2
if k <= P*M:
    u = pa[0]*ma[-1]
    l = pa[-1]*ma[0]
    while u - l >1:
        cnt = 0
        x = (u+l)//2
        i = j = 0
        while i < P and j < M:
            if pa[i]*ma[j] < x:
                cnt += 1
                j += 1
            else:
                i += 1
        if cnt < k:
            l = x
        else:
            u = x
    print(u)
elif T < k:
    if P > 1 and M > 1:
        u = max(pa[-1]*pa[-2], ma[-1]*ma[-2])
        l = min(pa[0]*pa[1], ma[0]*ma[1])
        while u - l > 1:
            cnt = 0
            x = (u+l)//2
            i = j = 0
            while i != P-1-j:
                if pa[i]*pa[P-1-j] < x:
                    i += 1
                    cnt += P-1-j-i
                else:
                    j += 1
            i = j = 0
            while i != M-1-j:
                if ma[i]*ma[M-1-j] < x:
                    j += 1
                    cnt += M-1-j-i
                else:
                    i += 1
            if cnt < k - T:
                l = x
            else:
                u = x
            print(x)
        print(l)
    elif P > 1:
        u = pa[-1]*pa[-2]
        l = pa[0]*pa[1]
        while u - l > 1:
            cnt = 0
            x = (u+l)//2
            i = j = 0
            while i != P-1-j:
                if pa[i]*pa[P-1-j] < x:
                    i += 1
                    cnt += 1
                else:
                    j += 1
            if cnt < k - T:
                l = x
            else:
                u = x
        print(l)
    else:
        u = ma[-1]*ma[-2]
        l = ma[0]*ma[1]
        while u - l > 1:
            cnt = 0
            x = (u+l)//2
            i = j = 0
            while i != M-1-j:
                if ma[i]*ma[M-1-j] < x:
                    i += 1
                    cnt += 1
                else:
                    j += 1
            if cnt < k - T:
                l = x
            else:
                u = x
        print(l)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
N, K = input().split(' ')
nums = input().split(' ')

products = []
for i in range(len(nums)):
  for j in range(len(nums)):
    if i != j:
    	products.append(int(nums[i])*int(nums[j]))
    
ranking = sorted(products)
print(ranking[int(K)-1])

Submission status: Wrong Answer

Solution code:
N, K = input().split(' ')
nums = input().split(' ')

products = []
for i in nums:
  for j in nums:
    products.append(int(i)*int(j))
    
ranking = sorted(products)
print(ranking[int(K)-1])

Submission status: Wrong Answer

Solution code:
N, K= map(int, input().split())
A = list(map(int, input().split()))
posi = []
zero = []
nega = []
for i in A:
    if i == 0:
        zero.append(i) 
    elif i == abs(i):
        posi.append(i)
    else:
        nega.append(i)

sign = len(nega), len(zero), len(posi) # 掛けて負，0，正になるもの
sign_pair = [0]*3
sign_pair[0] = sign[0]*sign[2]
sign_pair[1] = (sign[0]+sign[2])*sign[1] + (sign[1]*(sign[1]-1))//2
# sign_pair[2] = (sign[0]*(sign[0]-1))//2 + (sign[2]*(sign[2]-1))//2

print(sign_pair)

seki = []
if K <= sign_pair[0]:
    for i in nega:
        for j in posi:
            seki.append(i*j)
    seki.sort()
    print(seki[K-1])

elif sign_pair[0]+sign_pair[1] < K:
    for i in range(sign[0]):
        for j in range(i+1, sign[0]):
            seki.append(nega[i]*nega[j])
    for i in range(sign[2]):
        for j in range(i+1, sign[2]):
            seki.append(posi[i]*posi[j])
    seki.sort()
    print(seki[K-sign_pair[0]-sign_pair[1]-1])

else:
    print("0")

Submission status: Wrong Answer

Solution code:
import itertools
import time
import sys
sys.setrecursionlimit(5000)

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

minus=[x for x in A if x < 0]
zero=[x for x in A if x == 0]
plus=[x for x in A if x > 0]

minus_num = len(minus)*len(plus)
zero_num = len(zero)*(len(minus)+len(plus)) + len(zero)*(len(zero)-1)//2

minus_products=[]
plus_products=[]

#再帰　実装途中　return しない場合がある。　
def binary_search(data,target):
    #print(len(data))
    searching = True
    #for i in range(100000000000000):
    while True:
        pivot = data[int(len(data)//2)]
        min = [i for i in data if i <pivot]
        max = [i for i in data if i >=pivot]
        #for i in data:
        #    if i < pivot:
        #        min.append(i)
        #    else:
        #        max.append(i)
        #print(f"minの数：{len(min)}")
        #print(f"maxの数：{len(max)}")
        #print(f"target：{target}")
        if len(min) == target:
            break
        if len(min) < target:
            if len(min)==0:
                #print(len(data))
                data.sort()
                return data[target-1]
            data = max
            target= target-len(min)
        else:
            data = min
    return min[target-1]


if K <= minus_num:
    #負×正=負のリスト
    for m in minus:
        for j in plus:
            minus_products.append(m*j)
    print(binary_search(minus_products,K))
elif K <= (minus_num+zero_num):
    print(0)
else:
    #負＊負=正のリストと正＊正＝正のリストを合算して、正のリストを作る

    minus_by_minus=list(itertools.combinations(minus, 2))
    plus_by_plus=list(itertools.combinations(plus, 2))
    for m in minus_by_minus:
        plus_products.append(m[0]*m[1])
    for p in plus_by_plus:
        plus_products.append(p[0]*p[1])
    #start = time.time()
    print(binary_search(plus_products,K-minus_num-zero_num))
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Wrong Answer

Solution code:
import itertools
import time
import sys
sys.setrecursionlimit(5000)

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

minus=[x for x in A if x < 0]
zero=[x for x in A if x == 0]
plus=[x for x in A if x > 0]

minus_num = len(minus)*len(plus)
zero_num = len(zero)*(len(minus)+len(plus)) + len(zero)*(len(zero)-1)//2

minus_products=[]
plus_products=[]

#再帰　実装途中　return しない場合がある。　
def binary_search(data,target):
    #print(len(data))
    searching = True
    #for i in range(100000000000000):
    while True:
        pivot = data[int(len(data)//2)]
        min = [i for i in data if i <pivot]
        max = [i for i in data if i >=pivot]
        #for i in data:
        #    if i < pivot:
        #        min.append(i)
        #    else:
        #        max.append(i)
        #print(f"minの数：{len(min)}")
        #print(f"maxの数：{len(max)}")
        #print(f"target：{target}")
        if len(min) == target:
            break
        if len(min) < target:
            if len(min)==0:
                #print(len(data))
                data.sort()
                return data[target-1]
            data = max
            target= target-len(min)
        else:
            data = min
    return min[target-1]


if K <= minus_num:
    #負×正=負のリスト
    for m in minus:
        for j in plus:
            minus_products.append(m*j)
    print(binary_search(minus_products,K))
elif K <= (minus_num+zero_num):
    print(0)
else:
    #負＊負=正のリストと正＊正＝正のリストを合算して、正のリストを作る

    minus_by_minus=list(itertools.combinations(minus, 2))
    plus_by_plus=list(itertools.combinations(plus, 2))
    for m in minus_by_minus:
        plus_products.append(m[0]*m[1])
    for p in plus_by_plus:
        plus_products.append(p[0]*p[1])
    start = time.time()
    print(binary_search(plus_products,K-minus_num-zero_num))
    elapsed_time = time.time() - start
    print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Wrong Answer

Solution code:
import itertools
import time
import sys
sys.setrecursionlimit(5000)

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

minus=[x for x in A if x < 0]
zero=[x for x in A if x == 0]
plus=[x for x in A if x > 0]

minus_num = len(minus)*len(plus)
zero_num = len(zero)*(len(minus)+len(plus)) + len(zero)*(len(zero)-1)//2

minus_products=[]
plus_products=[]

#再帰　実装途中　return しない場合がある。　
def binary_search(data,target):
    #print(len(data))
    searching = True
    while searching:

        min=[]
        max=[]
        pivot = data[int(len(data)//2)]
        for i in data:
            if i < pivot:
                min.append(i)
            else:
                max.append(i)
        #print(f"minの数：{len(min)}")
        #print(f"maxの数：{len(max)}")
        #print(f"target：{target}")
        if len(min) == target:
            break
        if len(min) < target:
            if len(min)==0:
                #print(len(data))
                data.sort()
                return data[target-1]
            data = max
            target= target-len(min)
        else:
            data = min
    return min[target-1]


if K <= minus_num:
    #負×正=負のリスト
    for m in minus:
        for j in plus:
            minus_products.append(m*j)
    print(binary_search(minus_products,K))
elif K <= (minus_num+zero_num):
    print(0)
else:
    #負＊負=正のリストと正＊正＝正のリストを合算して、正のリストを作る
    start = time.time()
    minus_by_minus=list(itertools.combinations(minus, 2))
    plus_by_plus=list(itertools.combinations(plus, 2))
    for m in minus_by_minus:
        plus_products.append(m[0]*m[1])
    for p in plus_by_plus:
        plus_products.append(p[0]*p[1])
    print(binary_search(plus_products,K-minus_num-zero_num))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from math import ceil
    from bisect import bisect_left, bisect_right
    N, K = map(int, sys.stdin.readline().split())
    A = sorted(list(map(int, sys.stdin.readline().split())))

    positives = [a for a in A if a > 0]
    negatives = [a for a in A if a < 0]
    positive_cnt = len(positives)
    negative_cnt = len(negatives)
    zero_cnt = N - (positive_cnt + negative_cnt)

    negative_pairs_cnt = positive_cnt * negative_cnt
    zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

    # 考えにくいので、負の値も正になおしてソートしておく
    negatives = sorted([-a for a in negatives])

    if K <= negative_pairs_cnt:
        # にぶたん: X以上になるペアがK個以上あるか？
        ok, ng = 0, 10 ** 18 + 1
        while abs(ok - ng) > 1:
            X = (ok + ng) // 2
            or_higher_cnt = 0
            for a in negatives:
                or_higher_cnt += (positive_cnt - bisect_left(positives, ceil(X / a)))
                if or_higher_cnt >= K:
                    ok = X
                    break
            else:
                ng = X

        print(-ok == -6)

    elif K <= negative_pairs_cnt + zero_pairs_cnt:
        print(0)

    else:
        # にぶたん: X以下になるペアがK個以上あるか？
        K -= (negative_pairs_cnt + zero_pairs_cnt)
        ok, ng = 10 ** 18, 0
        while abs(ok - ng) > 1:
            X = (ok + ng) // 2
            or_higher_cnt = 0

            for i, a in enumerate(positives):
                j = bisect_right(positives, X // a)
                if i > j:
                    or_higher_cnt += j
                else:
                    or_higher_cnt += i

            if or_higher_cnt >= K:
                ok = X
                continue

            for i, a in enumerate(negatives):
                j = bisect_right(negatives, X // a)
                if i > j:
                    or_higher_cnt += j
                else:
                    or_higher_cnt += i

            if or_higher_cnt >= K:
                ok = X
                continue

            ng = X

        print(ok)


if __name__ == '__main__':
    main()