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:
import numpy as np
N, K = map(int, input().split())
A = np.sort(np.array(list(map(int, input().split()))))

def count_under_i(i):
    ans = 0
    for k in range(1, N - 1):
        if A[k] > 0:
            if k != 0:
                if A[k] * A[0] <= i and A[k] * A[N - 1] > i:
                    left = 0
                    right = N
                    while left + 1 < right:
                        c = (left + right) // 2
                        if A[c] <= i:
                            left = c
                        else:
                            right = c
                    ans += left + 1
                    if left >= k:
                        ans -= 1
                elif A[k] * A[N - 1] <= i:
                    ans += N - 1
            else:
                if A[0] * A[1] <= i and A[k] * A[N - 1] > i:
                    left = 1
                    right = N
                    while left + 1 < right:
                        c = (left + right) // 2
                        if A[c] <= i:
                            left = c
                        else:
                            right = c
                    ans += left + 1
                    if left >= k:
                        ans -= 1
                elif A[k] * A[N - 1] <= i:
                    ans += N - 1
        if A[k] < 0:
            A_reversed = A[:: -1]
            k = N - 1 - k
            if k != 0:
                if A_reversed[k] * A_reversed[0] <= i and A_reversed[k] * A_reversed[N - 1] > i:
                    left = 0
                    right = N
                    while left + 1 < right:
                        c = (left + right) // 2
                        if A_reversed[c] <= i:
                            left = c
                        else:
                            right = c
                    ans += left + 1
                    if left >= k:
                        ans -= 1
                elif A_reversed[k] * A_reversed[N - 1] <= i:
                    ans += N - 1
            else:
                if A_reversed[0] * A_reversed[1] <= i and A_reversed[k] * A_reversed[N - 1] > i:
                    left = 1
                    right = N
                    while left + 1 < right:
                        c = (left + right) // 2
                        if A_reversed[c] <= i:
                            left = c
                        else:
                            right = c
                    ans += left + 1
                    if left >= k:
                        ans -= 1
                elif A_reversed[k] * A_reversed[N - 1] <= i:
                    ans += N - 1
            
        if A[k] == 0:
            if i >= 0:
                ans += N - 1
        print(ans)
    return ans
        
left = - 10 ** 20
right = 10 ** 20
while left + 1 < right:
    c = (left + right) // 2 
    print(c, count_under_i(c))
    if count_under_i(c) >= K:
        right = c
    else:
        left = c
print("="*10)      
print(left, right)

Submission status: Wrong Answer

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

seki = []
seki =[a[i]*a[j] for i in range(n-1) for j in range(i+1,n)]
seki.sort()

print(seki,seki[k-1])

Submission status: Wrong Answer

Solution code:
f=lambda:map(int,input().split())
n,k=f()
lm,lp=[],[]
for i in f():
  if i<0: lm.append(-i)
  else: lp.append(i)
lm.sort()
lp.sort()
cm=len(lm)
cp=len(lp)
def cnt(x):
  c=0
  if x<0:
    r=cp
    for i in lm:
      while r and i*lp[r-1]>-x: r-=1
      c+=cp-r
    return c
  r=cm
  for i in lm:
    while r and i*lm[r-1]>=x: r-=1
    c+=r
    if i*i<x: c-=1
  r=cp
  for i in lp:
    while r and i*lp[r-1]>=x: r-=1
    c+=r
    if i*i<x: c-=1
  return cm*cp+c//2
INF=10**18+1
l,r=-INF,INF
while r-l>1:
  m=l+r>>1
  if cnt(m)<k: l=m
  else: r=m
print(l)

Submission status: Wrong Answer

Solution code:
f=lambda:map(int,input().split())
n,k=f()
lm,lp=[],[]
for i in f():
  if i<0: lm.append(-i)
  else: lp.append(i)
lm.sort()
lp.sort()
cm=len(lm)
cp=len(lp)
def cnt(x):
  c=0
  if x<0:
    r=cp
    for i in lm:
      while r>0 and i*lp[r-1]>-x: r-=1
      c+=cp-r
    return c
  r=0
  for i in lm[::-1]:
    while r<cm and i*lm[r]<x: r+=1
    c+=r
    if i*i<x: c-=1
  r=0
  for i in lp[::-1]:
    while r<cp and i*lp[r]<x: r+=1
    c+=r
    if i*i<x: c-=1
  return cm*cp+c//2
INF=10**18+1
l,r=-INF,INF
while r-l>1:
  m=l+r>>1
  if cnt(m)<k: l=m
  else: r=m
print(l)

Submission status: Wrong Answer

Solution code:
f=lambda:map(int,input().split())
n,k=f()
lm,lp=[],[]
for i in f():
  if i<0: lm.append(-i)
  else: lp.append(i)
lm.sort()
lp.sort()
cm=len(lm)
cp=len(lp)
def cnt(x):
  c=0
  if x<0:
    r=0
    for i in lm[::-1]:
      while r<cp and i*lp[r]<=-x: r+=1
      c+=cp-r
    return c
  r=0
  for i in lm[::-1]:
    while r<cm and i*lm[r]<x: r+=1
    c+=r
    if i*i<=x: c-=1
  r=0
  for i in lp[::-1]:
    while r<cp and i*lp[r]<x: r+=1
    c+=r
    if i*i<=x: c-=1
  return cm*cp+c//2
INF=10**18+1
l,r=-INF,INF
while r-l>1:
  m=l+r>>1
  if cnt(m)<k: l=m
  else: r=m
print(l)

Submission status: Wrong Answer

Solution code:
f=lambda:map(int,input().split())
n,k=f()
lm,lp=[],[]
for i in f():
  if i<0: lm.append(-i)
  else: lp.append(i)
lm.sort()
lp.sort()
cm=len(lm)
cp=len(lp)
def cnt(x):
  c=0
  if x<0:
    r=cp
    for i in lm:
      while r>0 and i*lp[r-1]>-x: r-=1
      c+=cp-r
    return c
  r=0
  for i in lm[::-1]:
    while r<cm and i*lm[r]<x: r+=1
    c+=r
    if i*i<=x: c-=1
  r=0
  for i in lp[::-1]:
    while r<cp and i*lp[r]<x: r+=1
    c+=r
    if i*i<=x: c-=1
  return cm*cp+c//2
INF=10**18+1
l,r=-INF,INF
while r-l>1:
  m=l+r>>1
  if cnt(m)<k: l=m
  else: r=m
print(l)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
pos = np.sort(a[a>0])
neg = np.sort(np.abs(a[a<0]))
zero = (a==0).sum()

INF = 2*(10**18)
l = -INF
r = INF

while(r-l>1):
    mid = (l+r)//2
    cnt = 0
    if mid >= 0:
        cnt = len(pos)*len(neg)  #(+) * (-)
        cnt += (len(pos)+len(neg)) * zero # 0 * (non-zero)
        cnt += (zero*(zero-1))//2 # 0 * 0
        x = np.searchsorted(pos, mid//pos, side='right').sum() #(+) * (+)
        x += np.searchsorted(neg, mid//neg, side='right').sum() #(-) * (-)
        x -= (pos*pos<=mid).sum()
        x -= (neg*neg<=mid).sum()
        cnt += x/2
    else:
        cnt = (len(neg) - np.searchsorted(neg, abs(mid)/pos, side='left')).sum()
    #print(l, r, mid, cnt)
    if cnt < k:
        l = mid
    else:
        r = mid
print(r)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

memo_r = {}
memo_l = {}

def check(t):
    res = 0
    tr = math.sqrt(abs(t))
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                if aj not in memo_r:
                    memo_r[aj] = bisect_right(a, aj)
                res += memo_r[aj]
            else:
                if t % ai:
                    if aj not in memo_r:
                        memo_r[aj] = bisect_right(a, aj)
                    res += n - memo_r[aj]
                else:
                    if aj not in memo_l:
                        memo_l[aj] = bisect_right(a, aj)
                    res += n - memo_l[aj]
        else:
            if t >= 0:
                res += n
        if t >= 0 and abs(ai) <= tr:
            res -= 1
    return res // 2


m = max(max(a)**2, min(a)**2)
l = -m
r = m

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

Submission status: Wrong Answer

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

def check(t):
    res = 0
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                res += bisect.bisect_right(a, aj)
            else:
                res += n - bisect.bisect_left(a, aj)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2

l = - 10 ** 18
r = 10 ** 18

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

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()))
a.sort()

def evl(val):
    cnt = 0
    for i in range(n):
        if a[i] == 0:
            cnt += n-i-1 if val >= 0 else 0
            continue
        x = val / a[i]
        if a[i] > 0:
            cnt += max(0, bisect_right(a, x)-(i+1))
        else:
            cnt += n - max(i+1, bisect_left(a, x))
    return cnt >= k
    
r = 10**18*2
l = -r
while r-l > 1:
    x = (l+r) // 2
    if evl(x): r = x
    else: l = x
print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = [int(i) for i in input().split(' ')]

A = np.array([int(i) for i in input().split(' ')])

A.sort()
zero = A[A==0]
minus = A[A<0]
plus = A[A>0]

def index_count(x):
    cnt = 0
    if x >= 0:
        cnt += len(zero) * N
    cnt += np.searchsorted(A,x//plus,side='right').sum()
    cnt += (N - np.searchsorted(A,x//minus,side='right')).sum()
    cnt -= np.count_nonzero(A*A <= x)

    return cnt //2


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

while left + 1 < right:
    mid = (left +right) //2
    a = index_count(mid)
    if a >= K:
        right = mid
    else:
        left = mid

print(right)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
p = 0
ne = 0
z = 0
a.sort()
for i in range(n):
    if a[i] > 0:
        p += 1
    elif a[i] == 0:
        z += 1
    else:
        ne += 1
a_ne = a[:ne]
a_z = a[ne:ne+z]
a_p = a[ne+z:]

def C(k):
    if k == 0:
        return p*ne+z*(p+ne)+z*(z-1)//2
    elif k > 0:
        cnt = 0
        lo = 0
        hi = len(a_p)-1
        while lo < len(a_p) and hi >= 0:
            if a_p[lo]*a_p[hi] <= k:
                if lo <= hi:
                    cnt += hi
                else:
                    cnt += hi+1
                lo += 1
            else:
                hi -= 1
        lo = 0
        hi = len(a_ne)-1
        while lo < len(a_ne) and hi >= 0:
            if a_ne[lo]*a_ne[hi] <= k:
                if lo <= hi:
                    cnt += len(a_ne)-lo-1
                else:
                    cnt += len(a_ne)-lo
                hi -= 1
            else:
                lo += 1
        cnt //= 2
        return p*ne+z*(p+ne)+z*(z-1)//2+cnt
    else:
        p_lo = 0
        ne_lo = len(a_ne)-1
        cnt = 0
        while p_lo < len(a_p) and ne_lo >= 0:
            if a_p[p_lo]*a_ne[ne_lo] <= k:
                cnt += ne_lo+1
                p_lo += 1
            else:
                ne_lo -= 1
        return cnt

if k > p*ne+z*(p+ne)+z*(z-1)//2:
    lo = 0
    hi = 10**18
    while hi-lo > 1:
        mid = (hi+lo)//2
        if C(mid) < k:
            lo = mid
        else:
            hi = mid
    print(hi)
elif k <= p*ne+z*(p+ne)+z*(z-1)//2 and k > p*ne:
    print(0)
else:
    lo = -10**18
    hi = 0
    while hi-lo > 1:
        mid = (lo+hi)//2
        if C(mid) < k:
            lo = mid
        else:
            hi = mid
    print(hi)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
p = 0
ne = 0
z = 0
a.sort()
for i in range(n):
    if a[i] > 0:
        p += 1
    elif a[i] == 0:
        z += 1
    else:
        ne += 1
a_ne = a[:ne]
a_z = a[ne:ne+z]
a_p = a[ne+z:]

def C(k):
    if k == 0:
        return p*ne+z*(p+ne)+z*(z-1)//2
    elif k > 0:
        cnt = 0
        lo = 0
        hi = len(a_p)-1
        while lo < len(a_p) and hi >= 0:
            if a_p[lo]*a_p[hi] <= k:
                if lo <= hi:
                    cnt += hi
                else:
                    cnt += hi+1
                lo += 1
            else:
                hi -= 1
        lo = 0
        hi = len(a_ne)-1
        while lo < len(a_ne) and hi >= 0:
            if a_ne[lo]*a_ne[hi] <= k:
                if lo <= hi:
                    cnt += len(a_ne)-lo-1
                else:
                    cnt += len(a_ne)-lo
                hi -= 1
            else:
                lo += 1
        cnt //= 2
        return p*ne+z*(p+ne)+z*(z-1)//2+cnt
    else:
        p_lo = 0
        ne_lo = len(a_ne)-1
        cnt = 0
        while p_lo < len(a_p) and ne_lo >= 0:
            if a_p[p_lo]*a_ne[ne_lo] <= k:
                cnt += ne_lo+1
                p_lo += 1
            else:
                ne_lo -= 1
        return cnt

if k > p*ne+z*(p+ne)+z*(z-1)//2:
    lo = 0
    hi = 10**20
    while hi-lo > 1:
        mid = (hi+lo)//2
        if C(mid) < k:
            lo = mid
        else:
            hi = mid
    print(hi)
elif k == p*ne+z*(p+ne)+z*(z-1)//2:
    print(0)
else:
    lo = -10**20
    hi = 0
    while hi-lo > 1:
        mid = (lo+hi)//2
        if C(mid) < k:
            lo = mid
        else:
            hi = mid
    print(hi)

Submission status: Wrong Answer

Solution code:
import bisect
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort()
negnum=bisect.bisect_left(ls,0)
posnum=N-bisect.bisect_right(ls,0)
zeronum=N-negnum-posnum

negmul=negnum*posnum
posmul=(negnum*(negnum-1)+posnum*(posnum-1))//2
zeromul=N*(N-1)//2-negmul-posmul

negls=ls[:negnum]
posls=ls[negnum+zeronum:]
  
def negpair(x): #x未満の個数
  paircount=0
  i1=0
  i2=0
  while i1<negnum and i2<posnum:
    while negls[i1]*posls[i2]>=x:
      i2+=1
      if i2==posnum:
        break
    paircount+=posnum-i2
    i1+=1
  return paircount

def pospair_pos(x): #x未満の個数
  if posnum<2:
    return 0
  paircount=0
  i1=0
  i2=posnum-1
  while posls[i1]*posls[i2]<x:
    i1+=1
    if i1==i2:
      return paircount
      break
  while i1<i2:
    while posls[i1]*posls[i2]>=x and i1<i2:
      i2-=1
   #   print(posls[i1],posls[i2])
    if i1==i2:
      break
    paircount+=posnum-i2-1
   # print(paircount,i1,i2)
    i1+=1
  paircount+=(posnum-i1)*(posnum-i1-1)//2
  return posnum*(posnum-1)//2-paircount

def pospair_neg(x): #x未満の個数
  if negnum<2:
    return 0
  paircount=0
  i1=0
  i2=negnum-1
  while negls[i1]*negls[i2]<x:
    i2-=1
    if i1==i2:
      return paircount
      break
  while i1<i2:
    while negls[i1]*negls[i2]>=x and i1<i2:
   #   print(negls[i1]*negls[i2])
      i1+=1
    if i1==i2:
      break
    paircount+=i1
    #   print(paircount,i1,i2)
    i2-=1
  paircount+=i1*(i1+1)//2
  return negnum*(negnum-1)//2-paircount

def pair(x):
  if x>0:
    return pospair_neg(x)+pospair_pos(x)+negmul+zeromul
  else:
    return negpair(x)

#print(ls)
a=ls[0]*ls[-1]
b=max([ls[0]*ls[0],ls[-1]*ls[-1]])
#print(a,b)

while b-a>1:
  c=(a+b)//2
 # print(a,b,c,pair(c))
  if pair(c)>K-1:
    b=c
  else:
    a=c

if pair(a)==K-1:
  print(a)
else:
  print(a-1)

Submission status: Wrong Answer

Solution code:
import bisect
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort()
negnum=bisect.bisect_left(ls,0)
posnum=N-bisect.bisect_right(ls,0)
zeronum=N-negnum-posnum

negmul=negnum*posnum
posmul=(negnum*(negnum-1)+posnum*(posnum-1))//2
zeromul=N*(N-1)//2-negmul-posmul

negls=ls[:negnum]
posls=ls[negnum+zeronum:]
  
def negpair(x): #x未満の個数
  paircount=0
  i1=0
  i2=0
  while i1<negnum and i2<posnum:
    while negls[i1]*posls[i2]>=x:
      i2+=1
      if i2==posnum:
        break
    paircount+=posnum-i2
    i1+=1
  return paircount

def pospair_pos(x): #x未満の個数
  if posnum<2:
    return 0
  paircount=0
  i1=0
  i2=posnum-1
  while posls[i1]*posls[i2]<x:
    i1+=1
    if i1==i2:
      return paircount
      break
  while i1<i2:
    while posls[i1]*posls[i2]>=x and i1<i2:
      i2-=1
   #   print(posls[i1],posls[i2])
    if i1==i2:
      break
    paircount+=posnum-i2-1
   # print(paircount,i1,i2)
    i1+=1
  paircount+=(posnum-i1)*(posnum-i1-1)//2
  return posnum*(posnum-1)//2-paircount

def pospair_neg(x): #x未満の個数
  if negnum<2:
    return 0
  paircount=0
  i1=0
  i2=negnum-1
  while negls[i1]*negls[i2]<x:
    i2-=1
    if i1==i2:
      return paircount
      break
  while i1<i2:
    while negls[i1]*negls[i2]>=x and i1<i2:
   #   print(negls[i1]*negls[i2])
      i1+=1
    if i1==i2:
      break
    paircount+=i1
    #   print(paircount,i1,i2)
    i2-=1
  paircount+=i1*(i1+1)//2
  return negnum*(negnum-1)//2-paircount

def pair(x):
  if x>0:
    return pospair_neg(x)+pospair_pos(x)+negmul+zeromul
  else:
    return negpair(x)

#print(ls)
a=ls[0]*ls[-1]
b=max([ls[0]*ls[0],ls[-1]*ls[-1]])
#print(a,b)

while b-a>1:
  c=(a+b)//2
 # print(a,b,c,pair(c))
  if pair(c)>K-1:
    b=c
  else:
    a=c

if pair(a)==K-1:
  print(a)
else:
  print(b)

Submission status: Wrong Answer

Solution code:
import bisect
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort()
negnum=bisect.bisect_left(ls,0)
posnum=N-bisect.bisect_right(ls,0)
zeronum=N-negnum-posnum

negmul=negnum*posnum
posmul=(negnum*(negnum-1)+posnum*(posnum-1))//2
zeromul=N*(N-1)//2-negmul-posmul

negls=ls[:negnum]
posls=ls[negnum+zeronum:]
  
def negpair(x): #x未満の個数
  paircount=0
  i1=0
  i2=0
  while i1<negnum and i2<posnum:
    while negls[i1]*posls[i2]>=x:
      i2+=1
      if i2==posnum:
        break
    paircount+=posnum-i2
    i1+=1
  return paircount

def pospair_pos(x): #x未満の個数
  if posnum<2:
    return 0
  paircount=0
  i1=0
  i2=posnum-1
  while posls[i1]*posls[i2]<x:
    i1+=1
    if i1==i2:
      return paircount
      break
  while i1<i2:
    while posls[i1]*posls[i2]>=x and i1<i2:
      i2-=1
   #   print(posls[i1],posls[i2])
    if i1==i2:
      break
    paircount+=posnum-i2-1
   # print(paircount,i1,i2)
    i1+=1
  paircount+=(posnum-i1)*(posnum-i1-1)//2
  return posnum*(posnum-1)//2-paircount

def pospair_neg(x): #x未満の個数
  if negnum<2:
    return 0
  paircount=0
  i1=0
  i2=negnum-1
  while negls[i1]*negls[i2]<x:
    i2-=1
    if i1==i2:
      return paircount
      break
  while i1<i2:
    while negls[i1]*negls[i2]>=x and i1<i2:
   #   print(negls[i1]*negls[i2])
      i1+=1
    if i1==i2:
      break
    paircount+=i1
    #   print(paircount,i1,i2)
    i2-=1
  paircount+=i1*(i1+1)//2
  return negnum*(negnum-1)//2-paircount

def pair(x):
  if x>0:
    return pospair_neg(x)+pospair_pos(x)+negmul+zeromul
  else:
    return negpair(x)

#print(ls)
a=ls[0]*ls[-1]
b=max([ls[0]*ls[0],ls[-1]*ls[-1]])
#print(a,b)

while b-a>1:
  c=(a+b)//2
 # print(a,b,c,pair(c))
  if pair(c)>K-1:
    b=c
  else:
    a=c
print(a)

Submission status: Wrong Answer

Solution code:
import bisect
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort()
negnum=bisect.bisect_left(ls,0)
posnum=N-bisect.bisect_right(ls,0)
zeronum=N-negnum-posnum

negmul=negnum*posnum
posmul=(negnum*(negnum-1)+posnum*(posnum-1))//2
zeromul=N*(N-1)//2-negmul-posmul

negls=ls[:negnum]
posls=ls[negnum+zeronum:]
  
def negpair(x): #x未満の個数
  paircount=0
  i1=0
  i2=0
  while i1<negnum and i2<posnum:
    while negls[i1]*posls[i2]>=x:
      i2+=1
      if i2==posnum:
        break
    paircount+=posnum-i2
    i1+=1
  return paircount

def pospair_pos(x): #x未満の個数
  if posnum<2:
    return 0
  paircount=0
  i1=0
  i2=posnum-1
  while posls[i1]*posls[i2]<x:
    i1+=1
    if i1==i2:
      return paircount
      break
  while i1<i2:
    while posls[i1]*posls[i2]>=x and i1<i2:
      i2-=1
   #   print(posls[i1],posls[i2])
    if i1==i2:
      break
    paircount+=posnum-i2-1
   # print(paircount,i1,i2)
    i1+=1
  paircount+=(posnum-i1)*(posnum-i1-1)//2
  return posnum*(posnum-1)//2-paircount

def pospair_neg(x): #x未満の個数
  if negnum<2:
    return 0
  paircount=0
  i1=0
  i2=negnum-1
  while negls[i1]*negls[i2]<x:
    i2-=1
    if i1==i2:
      return paircount
      break
  while i1<i2:
    while negls[i1]*negls[i2]>=x and i1<i2:
   #   print(negls[i1]*negls[i2])
      i1+=1
    if i1==i2:
      break
    paircount+=i1
    #   print(paircount,i1,i2)
    i2-=1
  paircount+=i1*(i1+1)//2
  return negnum*(negnum-1)//2-paircount

def pair(x):
  if x>0:
    return pospair_neg(x)+pospair_pos(x)+negmul+zeromul
  else:
    return negpair(x)

#print(ls)
a=ls[0]*ls[-1]
b=max([ls[0]*ls[0],ls[-1]*ls[-1]])
#print(a,b)

while b-a>1:
  c=(a+b)//2
 # print(a,b,c,pair(c))
  if pair(c)>K-1:
    b=c
  else:
    a=c
print(a)

Submission status: Wrong Answer

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

import bisect

idx_zero = bisect.bisect_left(A, 0)
idx_posi = bisect.bisect_right(A, 0)

num_nega = idx_zero
num_zero = idx_posi-idx_zero
num_posi = n-idx_posi

A_nega = A[:idx_zero]
A_nega_r = [-1*A_nega[i] for i in range(num_nega)]
A_nega_r.sort()
A_posi = A[idx_posi:]

def under_x(x):
  res = 0
  if x>0:
    res += num_nega*num_posi
    res += num_zero*(num_nega + num_posi)
    res += num_zero*(num_zero - 1)//2
    res *= 2
    for i in range(num_posi):
      v = A_posi[i]
      r = bisect.bisect_right(A_posi, x/v)
      res += r
    for i in range(num_nega):
      v = A_nega_r[i]
      r = bisect.bisect_right(A_nega_r, x/v)
      res += r
    for i in range(n):
      if A[i]**2<=x and A[i]!=0:
        res -= 1
    return res//2
  elif x==0:
    res += num_nega*num_posi
    res += num_zero*(num_nega + num_posi)
    res += num_zero*(num_zero - 1)//2
    return res
  elif x<0:
    for i in range(num_posi):
      v = A_posi[i]
      l = bisect.bisect_left(A_nega_r, abs(x)/v)
      res += num_nega - l
    return res
  
l = -10**18
r = 10**18
while r-l>1:
  m = (l+r)//2
  #print(m, under_x(m))
  if under_x(m)<k:
    l = m
  else:
    r = m
    
print(r)

Submission status: Wrong Answer

Solution code:
def do():
    n,m=map(int,input().split())
    l=list(map(int,input().split()))
    l1=[]
    # l=sorted(l)
    for i in range(n):
        for j in range(i+1,n):
            l1.append(l[i]*l[j])
    l1=sorted(l1)
    print(l1[m-1])
print(do())

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = np.sort(A)

G = A[A > 0]
Z = A[A == 0]
L = A[A < 0]

l, r = 10**18, -10**18

while l-r > 1:
  # 「積がm以下になるペアの数」を調べる。
  m = (l+r) // 2

  # A[A > 0]内から条件を満たすものの数?
  Pk = np.searchsorted(A, m//G, side="right").sum()

  # A[A < 0]内から条件を満たすものの数?
  Nk = (N - np.searchsorted(A, (-m-1)//(-L), side="right")).sum()

  # 同じ要素同士の積は重複しているため、条件を満たしていたら減らす
  duplicate = np.count_nonzero(A*A < m)

  # A[0]内から条件を満たすものの数?
  Zk = 0
  if m >= 0:
    Zk += len(Z) * N

  # 条件を満たす要素の数を合わせる
  k = Pk + Nk + Zk - duplicate
  
  # 全要素が二重になっている。重複要素を削除
  k //= 2

  # 条件を満たさないならmを低く、満たすならmを高くする
  if k >= K:
    l = m
  else:
    r = m
#lとrが一致すればmが一意に定まる
print(l)

Submission status: Wrong Answer

Solution code:
from bisect import *
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
U = 10 ** 18
L = - 10 ** 18
while U - L > 1:
    m = (U+L)//2
    cnt = 0
    for i in range(N):
        if m < 0:
            if A[i] < 0:
                cnt += N-i-1 - bisect_left(A[i+1:], m//A[i])
        elif m == 0:
            if A[i] < 0:
                cnt += N-i-1 - bisect_left(A[i+1:], 0)
            elif A[i] == 0:
                cnt += N-i-1
        else:
            if A[i] < 0:
                cnt += N-i-1 - bisect_left(A[i+1:], m//A[i])
            elif A[i] > 0:
                cnt += bisect_right(A[i+1:], m//A[i])
            else:
                cnt += N-i-1
    if cnt < K:
        L = m
    else:
        U = m
print(U)

Submission status: Wrong Answer

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

cnt = 0
for i, a in enumerate(a_lst):
  for b in a_lst[i+1:]:
    if cnt == k:
      print(a * b)
      break
    cnt += 1
  else:
    continue
  break

Submission status: Wrong Answer

Solution code:
import bisect
def check(m,n):
    res=0
    for i in range(n):
        l,r=-1,i
        if(A[i]==0):
            if(m>=0):
                res+=n-1
            continue
        if(A[i]>0):
            j=bisect.bisect_left(A,m/A[i])
            res+=j
        elif(A[i]<0):
            j=bisect.bisect_right(A,m/A[i])
            res+=(n-j)
    return res//2

n,k=map(int,input().split())
A=sorted(map(int,input().split()))
left=-10**18-1;right=10**18+1
while right-left>1:
    mid=(left+right)//2
    ch=check(mid,n)
    if(ch<=k):
        left=mid
    else:
        right=mid
print(left)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

def comb(n, k):
	p, q = 1, 1
	for i in range(1, k+1):
		p = p * (n-i+1)
		q = q * i
	return p // q

def binsearch(l, r, f):
    while r - l > 1:
        c = (r + l) // 2
       	if f(c):
            r = c
        else:
            l = c
    return r

N, K = rl()
A = rl()

pos = 0
neg = 0
zero = 0
Ap = []
An = []
for a in A:
	if a > 0:
		pos += 1
		Ap.append(a)
	elif a < 0:
		neg += 1
		An.append(a)
	else:
		zero += 1
Ap.sort()
An.sort()
n_pos = comb(pos, 2) + comb(neg, 2)
n_neg = pos * neg
n_zero = zero*(N-zero) + comb(zero, 2)

def num_gt(A, x):
	j = len(A) - 1
	cnt = 0
	for i in range(len(A)):
		while i < j and A[i] * A[j] > x:
			j -= 1
		if i >= j:
			break
		cnt += max(j - i, 0)
	return cnt

def num_gt2(A, B, x):
	j = len(B) - 1
	cnt = 0
	for i in range(len(A)):
		while j > 0 and A[i] * B[j] > x:
			j -= 1
		if j < 0:
			break
		cnt += max(j+1, 0)
	return cnt

def check_plus(x):
	cnt = n_neg + n_zero
	cnt += num_gt(Ap, x)
	cnt += num_gt(list(reversed(An)), x)
	return cnt >= K

def check_minus(x):
	cnt = num_gt2(Ap, An, x)
	return cnt >= K

ans = 0
if K <= n_neg:
	l = An[0] * Ap[-1] - 1
	r = 0
	ans = binsearch(l, r, check_minus)
elif K <= n_neg + n_zero:
	ans = 0
else:
	l = 0
	r = 1
	if len(Ap) >= 2:
		r = max(r, Ap[-1] * Ap[-2]) + 1
	if len(An) >= 2:
		r = max(r, An[0] * An[1]) + 1
	ans = binsearch(l, r, check_plus)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
l = list(map(int, input().split()))
s = []
for i in range(0,N):
    for j in range(i,N):
        s.append(l[i]*l[j])
s.sort()
print(s[K])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
np,nn=len(ap),len(an)
def fminus(x):
  j=0
  cnt=0
  for i in range(np):
    cnt+=min(j,np-1)
    while j<np and an[j]*ap[i]>=x:
      j+=1
      cnt+=1
  return cnt
def fplus(x,length,lis):
  r=length-1
  cnt=0
  for l in range(length):
    while lis[r]*lis[l]>x:
      if r==l:
        break
      r-=1
    if r==l:
      break
    elif lis[r]*lis[l]<=x:
      cnt+=r-l
  return cnt
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    an.sort(reverse=True)
    ap.sort()
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      if fminus(mid)>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    an.sort()
    ap.sort()
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      if fplus(mid,nn,an)+fplus(mid,np,ap)>=k:
        ok=mid
      else:
        ng=mid
    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()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
np,nn=len(ap),len(an)
def fminus(x):
  j=0
  cnt=0
  for i in range(np):
    cnt+=j
    while j<np and an[j]*ap[i]>=x:
      j+=1
      cnt+=1
  return cnt
def fplus(x,length,lis):
  r=length-1
  cnt=0
  for l in range(length):
    while lis[r]*lis[l]>x:
      if r==l:
        break
      r-=1
    if r==l:
      break
    elif lis[r]*lis[l]<=x:
      cnt+=r-l
  return cnt
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    an.sort(reverse=True)
    ap.sort()
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      if fminus(mid)>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    an.sort()
    ap.sort()
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      if fplus(mid,nn,an)+fplus(mid,np,ap)>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
ans_list = []
for i in range(len(a)):
    for j in range(i, len(a)):
        ans_list.append(a[i]*a[j])

ans_list.sort()
print(ans_list[k-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()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
np,nn=len(ap),len(an)
def fminus(x):
  j=0
  cnt=0
  for i in range(np):
    cnt*=2
    while j<np and an[j]*ap[i]>=x:
      j+=1
      cnt+=1
  return cnt
def fplus(x,length,lis):
  r=length-1
  cnt=0
  for l in range(length):
    while lis[r]*lis[l]>x:
      if r==l:
        break
      r-=1
    if r==l:
      break
    elif lis[r]*lis[l]<=x:
      cnt+=r-l
  return cnt
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  an.sort(reverse=True)
  ap.sort(reverse=True)
  #print(ap)
  #print(an)
  if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      if fminus(mid)>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    an.sort()
    ap.sort()
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      if fplus(mid,nn,an)+fplus(mid,np,ap)>=k:
        ok=mid
      else:
        ng=mid
    print(ok)