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:
def main():
    from bisect import bisect_left as bl
    from bisect import bisect_right as br

    def b_search(ok, ng, value):
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if value(mid):
                ok = mid
            else:
                ng = mid
        return ok

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

    inf = 10**18+1

    def check(x):
        cnt = 0
        for i in a:
            if i < 0:
                if x % i == 0:
                    cnt += n - br(a, x//i)
                else:
                    cnt += n - br(a, x//i + 1)
            elif i > 0:
                if x % i == 0:
                    cnt += bl(a, x//i)
                else:
                    cnt += bl(a, x//i + 1)
            else:
                if x > 0:
                    cnt += n
                else:
                    cnt += 0
        for i in a:
            if i*i < x:
                cnt -= 1
        return cnt//2 < k

    print(b_search(-inf, inf, check))


main()

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
# これは500点では？
import bisect

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

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

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

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left as bl
    from bisect import bisect_right as br

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                a = med
            else:
                b = med-1
        if a == b:
            return a
        elif a+1 == b:
            if value(b):
                return b
            else:
                return a

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

    inf = 10**18+1

    def check(x):
        cnt = 0
        for i in a:
            if i < 0:
                if x % i == 0:
                    cnt += n - br(a, x//i)
                else:
                    cnt += n - br(a, x//i + 1)
            elif i > 0:
                if x % i == 0:
                    cnt += bl(a, x//i)
                else:
                    cnt += bl(a, x//i + 1)
            else:
                if x > 0:
                    cnt += n
                else:
                    cnt += 0
        for i in a:
            if i*i < x:
                cnt -= 1
        return cnt//2 < k

    print(b_search(-inf, inf, check))


main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A_minus,A_zero,A_plus=[],[],[]
    x=bisect_left(A,0)
    y=bisect_right(A,0)
    A_minus=A[:x]
    A_zero=A[x:y]
    A_plus=A[y:]
    if K<=len(A_minus)*len(A_plus):
        def nibutan1(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve1(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve1(mid):
            c=0
            z=bisect_left(A_plus,-(-mid//A_minus[0]))
            c+=len(A_plus)-z
            for x in A_minus[1:]:
                if z<=len(A_plus) and A_plus[z-1] < -(-mid//x):
                    while z<=len(A_plus) and A_plus[z-1] < -(-mid//x):
                        z+=1
                c+=len(A_plus)-z
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan1(0,-10**18+1))
    K-=len(A_minus)*len(A_plus)
    if 0<K<=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2:
        print(0)
    K-=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2
    if K>0:
        def nibutan2(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve2(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        def solve2(mid):
            c=0
            if A_minus:
                z=bisect_left(A_minus,-(-mid//A_minus[0]))
                c+=len(A_minus)-z
                if -(-mid//A_minus[0])<=A_minus[0]:
                    c-=1
                if len(A_minus)>1:
                    for x in A_minus[1:]:
                        if 0<z and A_minus[z-1] >= -(-mid//x):
                            while 0<z and A_minus[z-1] >= -(-mid//x):
                                z-=1
                        c+=len(A_minus)-z
                        if -(-mid//x)<=x:
                            c-=1
            if A_plus:
                z=bisect_right(A_plus,(mid//A_plus[0]))
                c+=z
                if (mid//A_plus[0])>=A_plus[0]:
                    c-=1
                if len(A_plus)>1:
                    for x in A_plus[1:]:
                        if 0<z and A_plus[z-1] > (mid//x):
                            while 0<z and A_plus[z-1] > (mid//x):
                                z-=1
                        c+=z
                        if (mid//x)>=x:
                            c-=1
            c//=2
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan2(10**18+1,0))

    
        
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left as bl
    from bisect import bisect_right as br

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                a = med
            else:
                b = med-1
        if a == b:
            return a
        elif a+1 == b:
            if value(b):
                return b
            else:
                return a

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

    inf = 10**18+1

    def check(x):
        cnt = 0
        for i in a:
            if i < 0:
                cnt += n - br(a, x//i)
            elif i > 0:
                cnt += br(a, x//i)
            else:
                if x > 0:
                    cnt += n
                else:
                    cnt += 0
        for i in a:
            if i*i < x:
                cnt -= 1
        return cnt//2 < k

    print(b_search(-inf, inf, check)+1)


main()

Submission status: Wrong Answer

Solution code:
import bisect

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

left=-10**18
right=10**18
count=0

a=bisect.bisect_left(A,0)
b=bisect.bisect_right(A,0)

if n*(n-1)-b*(n-a)-(b-a)>=2*k:
    right=0
else:
    left=1

while right!=left:
    pos=(left+right)//2
    count=0
    for idx,a in enumerate(A):
        if a==0:
            if pos>0:
                count+=n-1
        elif a<0:
            i=bisect.bisect_left(A,pos/a)
            count+=n-i + (-1 if idx>=i else 0)
        else:
            i=bisect.bisect_right(A,pos/a)
            count+=i + (-1 if idx<i else 0)
    if count>=2*k:
        right=pos
    else:
        left=pos+1

print(left)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
m = max(max(A),-min(A))
u = m**2
d = -m**2
import bisect
import copy
import math
while u - d > 1:
    B = copy.deepcopy(A)
    x = (u+d)//2
    k = 0
    for j in range(N):
        a = B.pop(0)
        if x < 0:
            if a < 0:
                y = math.ceil((-x)/(-a))
                b = len(B) - bisect.bisect_left(B,y)
            else:
                break
            k += b
        elif x == 0:
            if a < 0:
                b = len(B) - bisect.bisect_left(B,0)
            elif a == 0:
                b = len(B)
            else: 
                break
            k += b
        else:
            if a < 0:
                y = -((x)//(-a))
                b = len(B) - bisect.bisect_left(B,y)
            elif a == 0:
                b = len(B)
            else:
                y = x//a
                b = bisect.bisect_right(B,y)
            k += b
    if k >= K:
        u = x
    else:
        d = x
print(u)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
u = 4*10**18
d = -4*10**18
import bisect
import copy
import math
for i in range(100):
    B = copy.deepcopy(A)
    x = (u+d)//2
    k = 0
    for j in range(N):
        a = B.pop(0)
        if x < 0:
            if a < 0:
                y = math.ceil((-x)/(-a))
                b = len(B) - bisect.bisect_left(B,y)
            else:
                break
            k += b
        elif x == 0:
            if a < 0:
                b = len(B) - bisect.bisect_left(B,0)
            elif a == 0:
                b = len(B)
            else: 
                break
            k += b
        else:
            if a < 0:
                y = -((x)//(-a))
                b = len(B) - bisect.bisect_left(B,y)
            elif a == 0:
                b = len(B)
            else:
                y = x//a
                b = bisect.bisect_right(B,y)
            k += b
    if k >= K:
        u = x
    else:
        d = x
print(u)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
u = 4*10**18
d = -4*10**18
import bisect
import copy
import math
for i in range(100):
    B = copy.deepcopy(A)
    x = (u+d)//2
    k = 0
    for j in range(N):
        a = B.pop(0)
        if x < 0:
            if a < 0:
                y = math.ceil((-x)/(-a))
                b = len(B) - bisect.bisect_left(B,y)
            else:
                break
            k += b
        elif x == 0:
            if a < 0:
                b = len(B) - bisect.bisect_left(B,0)
            elif a == 0:
                b = len(B)
            else: 
                break
            k += b
        else:
            if a < 0:
                y = -((x)//(-a))
                b = len(B) - bisect.bisect_left(B,y)
            elif a == 0:
                b = len(B)
            else:
                y = x//a
                b = bisect.bisect_right(B,y)
            k += b
    if k >= K:
        u = x
    else:
        d = x
print(u)

Submission status: Wrong Answer

Solution code:
import bisect

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

left=-10**18
right=10**18
count=0

a=bisect.bisect_left(A,0)
b=bisect.bisect_right(A,0)

if b*(n-a)-(b-a)>=2*k:
    right=0
else:
    left=1

while right!=left:
    pos=(left+right)//2
    count=0
    for idx,a in enumerate(A):
        if a==0:
            if pos>0:
                count+=len(A)-1
        elif a<0:
            i=bisect.bisect_left(A,pos/a)
            count+=len(A)-i + (-1 if idx>=i else 0)
        else:
            i=bisect.bisect_right(A,pos/a)
            count+=i + (-1 if idx<i else 0)
    if count>=2*k:
        right=pos
    else:
        left=pos+1

print(left)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
u = 4*10**18
d = -4*10**18
import bisect
import copy
import math
for i in range(100):
    B = copy.deepcopy(A)
    x = (u+d)//2
    k = 0
    for j in range(N):
        a = B.pop(0)
        y = 0
        if a != 0:
            if x/a >= 0:
                y = x//a
            else:
                y = -math.ceil(-(x/a))
        if x < 0:
            if a < 0:
                y = (-x)//(-a)
                b = len(B) - bisect.bisect_right(B,y)
            else:
                break
            k += b
        elif x == 0:
            if a < 0:
                b = len(B) - bisect.bisect_left(B,0)
            elif a == 0:
                b = len(B)
            else: 
                break
            k += b
        else:
            if a < 0:
                y = -((x)//(-a))
                b = len(B) - bisect.bisect_left(B,y)
            elif a == 0:
                b = len(B)
            else:
                b = bisect.bisect_right(B,y)
            k += b
    if k >= K:
        u = x
    else:
        d = x
print(d+1)

Submission status: Wrong Answer

Solution code:
import bisect

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

left=-10**9
right=10**9
count=0

if n*n-n>=k:
    right=0
else:
    left=1

while right!=left:
    pos=(left+right)//2
    count=0
    for idx,a in enumerate(A):
        if a==0:
            if pos<0:
                count+=len(A)-1
        elif a<0:
            i=bisect.bisect_left(A,pos/a)
            count+=len(A)-i + (-1 if idx>=i else 0)
        else:
            i=bisect.bisect_right(A,pos/a)
            count+=i + (-1 if idx<i else 0)
    if count//2>=k:
        right=pos
    else:
        left=pos+1

print(left)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def solve(mid):
    # mid以下の通り数を求める
    cnt = 0
    if mid > 0:
        # 正と正の組み合わせ
        for i, num in enumerate(plus):
            tmp = mid // num
            ind = bisect_right(plus, tmp, lo=i+1)
            cnt += ind - (i + 1)
        # 負と負の組み合わせ
        for i, num in enumerate(minus_plus):
            tmp = mid // num
            ind = bisect_right(minus_plus, tmp, lo=i+1)
            cnt += ind - (i + 1)
    #print(cnt)

    if mid >= 0:
        # 正と負の組み合わせ
        cnt += cnt_minus
    #print(cnt)

    if mid < 0:
        # 正と負の組み合わせ
        pos = 0
        for num in plus:
            while True:
                if pos == len(minus_plus):
                    break
                if num * minus_plus[pos] < -mid:
                    pos += 1
                else:
                    break
            cnt += len(minus_plus) - pos
    #print(cnt)
    
    if mid >= 0:
        cnt += cnt_0
    #print(cnt)

    return cnt >= k


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

plus = []
minus_plus = []
cnt0 = 0
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus_plus.append(-a[i])
    else:
        cnt0 += 1
plus = sorted(plus)
minus_plus = sorted(minus_plus)

# 答えが0になる場合
cnt_0 = (len(plus) + len(minus_plus)) * cnt0
cnt_0 += cnt0 * (cnt0 - 1) // 2

# 答えが負になるとき
cnt_minus = len(minus_plus) * len(plus)

ng = -10**18 - 1
ok = 10**18 + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)
"""
tmp = []
for i in range(n):
    for j in range(i + 1, n):
        tmp.append(a[i] * a[j])
tmp = sorted(tmp)
print(tmp[0:10])
print(tmp[10:20])
print(tmp[20:30])
print(tmp[30:40])
print(tmp[40:50])"""

Submission status: Wrong Answer

Solution code:
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
n,k=map(int,input().split())
a=np.sort(np.array(list((map(int,input().split())))))
q=len(a[a==0])
d=a[a<0]
e=a[a>0]
l,r=10**18,-10**18
while l-r>1:
    t=(l+r)//2
    p=0
    if t>=0:
        p+=q*n
    p+=np.searchsorted(a,t//e,side="right").sum()+(n-np.searchsorted(a,(-t-1)//(-d),side="right")).sum()
    p-=np.count_nonzero(a*a<=t)
    p//=2
    if p>=k:
        l=t
    else:
        r=t
print(r)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mA, nA, zc = [], [], 0
dd = []
for a in A:
    if a<0:
        mA.append(a)
    elif a>0:
        nA.append(a)
    else:
        zc += 1
    dd.append(a*a)
rA = A[::-1]
#print(mA, nA)
lnA = len(nA)
lmA = len(mA)

def F(idx):
    j = lnA-1
    r = 0
    for a in nA:
        while j >= 0:
            if nA[j]*a <= idx:
                break
            j -= 1
        r += j+1
    if idx > 0:
        r += 2*(zc*N) - zc*zc
    j = 0
    for a in mA:
        while j < lmA:
            if mA[j]*a <= idx:
                break
            j += 1
        r += lmA-j
    j = 0
    for a in mA:
        while j < lnA:
            if nA[j]*a <= idx:
                break
            j += 1
        r += 2*(lnA-j)

    for a in dd:
        if idx < a:
            break
        r -= 1
    return r//2
#print(F(5))

mx, mn = 10**18+1, -10**18-1
idx = (mx + mn)//2
target = K
while mx - mn > 1:
    if F(idx) < target:
        idx, mn = (idx + mx)//2, idx
        continue
    idx, mx = (idx + mn)//2, idx
print(idx+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
n,k=map(int,input().split())
a=np.sort(np.array(list((map(int,input().split())))))
q=len(a[a==0])
d=a[a<0]
e=a[a>0]
l,r=10**18,-10**18
while l-r>1:
    t=(l+r)//2
    p=0
    if t>=0:
        p+=q*n
    p+=np.searchsorted(a,t//e,side="right").sum()+(n-np.searchsorted(a,(-t-1)//(-d),side="right")).sum()
    p-=np.count_nonzero(a*a<=t)
    p//=2
    if p>=k:
        l=t
    else:
        r=t
g=-float("INF")
for i in range(n):
    if a[i]<0:
        c=bl(a,l/a[i])
        if c==i:
            c+=1
        if c<n:
            g=max(g,a[c]*a[i])
    elif a[i]==0:
        g=max(g,0)
    else:
        c=br(a,l/a[i])-1
        if c==i:
            c-=1
        if c>0:
            g=max(g,a[c]*a[i])
print(g)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
u = 4*10**18
d = -4*10**18
import bisect
import copy
import math
for i in range(100):
    B = copy.deepcopy(A)
    x = (u+d)//2
    k = 0
    for j in range(N):
        a = B.pop(0)
        y = 0
        if a != 0:
            if x/a >= 0:
                y = math.ceil(x/a)
            else:
                y = -math.ceil(-(x/a))
        if x < 0:
            if a < 0:
                b = len(B) - bisect.bisect_left(B,y)
            else:
                break
            k += b
        elif x == 0:
            if a < 0:
               b = len(B) - bisect.bisect_left(B,y)
            else:
               b = len(B)
            k += b
        else:
            if a < 0:
                b = len(B) - bisect.bisect_left(B,y)
            elif a == 0:
                b = len(B)
            else:
                b = bisect.bisect_right(B,y)
            k += b
    if k >= K:
        u = x
    else:
        d = x+1
print(d)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import collections

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = []
for i in itertools.combinations(A, r=2):
	ans.append(i[0]*i[1])
	
print(sorted(ans)[2])

Submission status: Wrong Answer

Solution code:
import bisect

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
for i in range(n):
  if arr[i]<0:
    nc+=1
  elif arr[i]==0:
    zc+=1
  else:
    pc+=1
ncc=nc*pc
zcc=zc*(nc+pc)+(zc*(zc-1))//2
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
if k<=ncc:
  arr1=[]
  arr2=[]
  for i in range(n):
    if arr[i]<0:
      arr1.append(-arr[i])
    elif arr[i]>0:
      arr2.append(arr[i])
  arr1=arr1[::-1]
  c1=len(arr1)
  c2=len(arr2)
  l=0
  r=10**18+1
  k=ncc-k
  while r-l!=1:
    mid=(l+r)//2
    cnt=0
    for i in range(c1):
      cnt+=bisect.bisect_right(arr2,mid//arr1[i])
    if cnt>k:
      r=mid
    else:
      l=mid
  print(-r)
elif k<=(ncc+zcc):
  print(0)
else:
  arr1=[]
  arr2=[]
  for i in range(n):
    if arr[i]<0:
      arr1.append(-arr[i])
    elif arr[i]>0:
      arr2.append(arr[i])
  arr1=arr1[::-1]
  c1=len(arr1)
  c2=len(arr2)
  l=0
  r=10**18+1
  k-=(ncc+zcc)
  print(k)
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    for i in range(c1):
      tmp=bisect.bisect_right(arr1,mid//arr1[i])
      if arr1[i]**2<mid:
        tmp-=1
      cnt1+=tmp
    cnt1=cnt1//2
    cnt2=0
    for i in range(c2):
      tmp=bisect.bisect_right(arr2,mid//arr2[i])
      if arr2[i]**2<mid:
        tmp-=1
      cnt2+=tmp
    cnt2=cnt2//2
    cnt=cnt1+cnt2
    if cnt>=k:
      r=mid
    else:
      l=mid
  print(r)

Submission status: Wrong Answer

Solution code:
import itertools

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

P = itertools.combinations(AN, 2)

l = []

for p in P:
    l.append(p[0]*p[1])
l.sort()
print(l)
print(l[K-1])

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(x):
    cnt = 0
    for i in range(n):
        if a[i] == 0:
            if x >= 0:
                cnt += n-i-1
        elif a[i] > 0:
            r =  br(a,x//a[i])
            if r <= i:
                continue
            cnt += r - i - 1
        else:
            l = bl(a,math.ceil(x/a[i]))
            if l <= i:
                l = i+1
            cnt += n - l
    return cnt >= k
n,k = LI()
a = LI()
a.sort()

ok = 10**18
ng = -10**18
while ok-ng > 1:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f(x):
    cnt = 0
    for i in range(n):
        if a[i] == 0:
            if x >= 0:
                cnt += n-i-1
        elif a[i] > 0:
            r =  br(a,x//a[i])
            if r <= i:
                continue
            cnt += r - i - 1
        else:
            l = bl(a,math.ceil(x/a[i]))
            if l <= i:
                l = i+1
            cnt += n - l
    if x == 6:
        print("cnt",cnt)
    return cnt >= k
n,k = LI()
a = LI()
a.sort()

ok = 10**18
ng = -10**18
while ok-ng > 1:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

Solution code:
a, b = map(int, input().split())
List = list(map(int, input().split()))

flag = True
res = []
List = sorted(List)
minus = 0
plus = 0

for i in range(a):
    if List[i] < 0:
        minus += 1
    else:
        plus += 1
        
if minus * plus > b:
    for i in range(minus):
        for j in range(minus, a):
            res.append(List[i] * List[j])
else:
    flag = False
    for i in range(minus):
        for j in range(minus):
            res.append(List[i] * List[j])
    
    for i in range(minus, a):
        for j in range(i+1, a):
            res.append(List[i] * List[j])

res = sorted(res)
if flag:
    print(res[b-1])
else:
    print(res[(b-1)-((minus*plus)-1)-1])
#print(res)

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right as br
from bisect import bisect_left as bl
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
l,r=10**18,-10**18-1
while l-r>1:
    t=(l+r)//2
    p=0
    for i in a:
        if i<0:
            p+=n-bl(a,t/i)
        elif i==0:
            if t>=0:
                p+=n
        else:
            p+=br(a,t/i)
        if i**2<=t:
            p-=1
    p//=2
    if p>=k:
        l=t
    else:
        r=t
g=-float("INF")
for i in range(n):
    if a[i]<0:
        c=bl(a,l/a[i])
        if c==i:
            c+=1
        if c<n:
            g=max(g,a[c]*a[i])
    elif a[i]==0:
        g=max(g,0)
    else:
        c=br(a,l/a[i])-1
        if c==i:
            c-=1
        if c>0:
            g=max(g,a[c]*a[i])
print(g)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
n,k=map(int,input().split())
l=[int(i) for i in input().split()]
l.sort()
a=min(0,l[0]*l[-1])
b=max(l[0]*l[0],l[-1]*l[-1])+2
while b-a>1:
    c=(a+b)//2
    cntl=0
    cntg=0
    for i in l:
        if i>0:
            x=c//i
            ind=bisect_left(l,x)
            if ind==n:
                cntl+=n-1
            else:
                if i*l[ind]==c:
                    cntl+=ind
                    ind=bisect_right(l,x)
                else:
                    ind=bisect_right(l,x)
                    cntl+=ind
                cntg+=n-ind
                if i*i>c:
                    cntg-=1
                elif i*i<c:
                    cntl-=1
        elif i==0:
            if c<0:
                cntg+=n-1
            elif c>0:
                cntl+=n-1
        else:
            x=c//i
            ind=bisect_left(l,x)
            if ind==n:
                cntg+=n-1
            else:
                if i*l[ind]==c:
                    cntg+=ind
                    ind=bisect_right(l,x)
                else:
                    ind=bisect_right(l,x)
                    cntg+=ind
                cntl+=n-ind
                if i*i>c:
                    cntg-=1
                elif i*i<c:
                    cntl-=1
    cntl//=2
    cntg//=2
    if cntl>=k:
        b=c
    elif n*(n-1)//2-cntg<k:
        a=c
    else:
        print(c)
        break

Submission status: Wrong Answer

Solution code:
import bisect

N, K = tuple(map(int, input().split()))
a = sorted(map(int, input().split()))

i = bisect.bisect_left(a, 0)

c = 0
if (N-i) * i > K:
    for j in a[0:i]:
        for k in a[i+1:i-1:-1]:
            c += 1
            if c == K:
                print(k * j)
else:
    c = (N - i) * i
    it = iter(a[::-1])
    temp = next(it)
    for j in it:
        c += 1
        if c == K:
            print(j * temp)
        temp=j