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 d_pairs():
    # 参考: https://maspypy.com/atcoder-参加感想-2019-02-16abc-155
    import numpy as np
    N, K = [int(i) for i in input().split()]
    A = np.array([int(i) for i in input().split()], np.int64)

    A = np.sort(A)
    zero = A[A == 0]
    positive = A[A > 0]
    negative = A[A < 0]

    def f(c):
        """数列 A から 2 要素を選んで積を取ったとき、c 以下となるようなペアの選び方"""
        count_pair = 0

        # a (数列の要素) == 0 かつ c >= 0 なら、a * x <= c となる x は数列の任意の要素
        if c >= 0:
            count_pair += len(zero) * N
        # a > 0 の場合
        count_pair += np.searchsorted(A, c // positive, side='right').sum()
        # a < 0 の場合 (全体から引くようにすると、見通しがよい)
        count_pair += (N - np.searchsorted(A, (-c) // (-negative), side='right')).sum()
        # 添字の順序に制約があることを反映する
        count_pair -= np.count_nonzero(A * A <= c)  # 「添字が同じ要素を 2 度選んだ場合」を引く
        return count_pair // 2

    # 数列から要素を 2 個選んで積を取ったとき、制約からあり得る値の範囲
    lower, upper = -10 ** 18, 10 ** 18
    while upper - lower > 1:
        x = (lower + upper) // 2
        if f(x) >= K:
            upper = x
        else:
            lower = x
    return upper

print(d_pairs())

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left, bisect_right
from math import ceil

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
#print("A={}".format(A))
"""
積がX以下になるような組がK個未満かを判定する。
    -> Xに関する二分探索をすることで、下位から丁度K番目の積の値がわかる！

これを判定するために、まずは下からK番目の積の値が0以上か0未満かを判定する。
zeros = (Aの中の0の個数)
over0 = (下からK番目の積の値が0以上ならTrue、0未満ならFalse)
"""

idx0 = bisect_left(A, 0)
idx1 = bisect_right(A, 0)
minus_prod = idx0 * (N - idx1)
zeros = idx1 - idx0
#print("idx0={}, idx1={}".format(idx0, idx1))

if minus_prod < K:
    over0 = True
else:
    over0 = False

"""
これを踏まえて、「小さい方の」値をfix(A[i]とする)して、
積がX以下になるような組を数え上げ。
"""

def within(X):
    """
    積がX以下になるような組がK個未満ならTrue、そうでなければFalseを返す。
    後から思ったけど、Xの正負で場合分けする必要なかった。
    """
    if over0 and X < 0:
        return True

    elif over0 and X >= 0:
        pair = 0
        for i in range(idx0): # A[i] < 0
            idx = bisect_left(A, ceil(X / A[i]))
            if i < idx:
                pair += N - idx
            else:
                pair += N - i - 1
        #print("pair={}".format(pair))

        pair += (N - idx0) * zeros - zeros * (zeros + 1) // 2 # A[i] == 0
        #print("pair={}".format(pair))

        for i in range(idx1, N): # A[i] > 0
            idx = bisect_right(A, X // A[i])
            #print("X={}, A[i]={}, X//A[i]={}, idx={}".format(X, A[i], X // A[i], idx))
            if i < idx:
                pair += idx - i - 1
        #print("X={}, pair={}".format(X, pair))
        if pair < K:
            return True
        else:
            return False

    elif X >= 0:
        return False

    elif X < 0:
        pair = 0
        for i in range(idx0): # A[i] < 0
            idx = bisect_left(A, ceil(X / A[i]))
            if i < idx:
                pair += N - idx
            else:
                pair += N - i - 1
        for i in range(idx1, N): # A[i] > 0
            idx = bisect_right(A, X // A[i])
            if i < idx:
                pair += idx - i - 1
        #print("X={}, pair={}".format(X, pair))
        if pair < K:
            return True
        else:
            return False

"""
Xに関する二分探索をおこなった結果、
leftXはwithin(leftX, over0) == Falseになる最小のX
"""
def main():
    if A[0] >= 0:
        leftX = A[0] * A[1]
        rightX = A[-1] * A[-2]
    elif A[-1] < 0:
        leftX = A[-1] * A[-2]
        rightX = A[0] * A[1]
    else:
        leftX = A[0] * A[-1]
        rightX = max(A[0] * A[1], A[-1] * A[-2])


    while leftX != rightX:
        #print("left={}, right={}".format(leftX, rightX))
        middleX = (leftX + rightX) // 2
        if within(middleX):
            leftX = middleX + 1
        else:
            rightX = middleX

    return leftX

if __name__ == "__main__":
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left, bisect_right
from math import ceil

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
#print("A={}".format(A))
"""
積がX以下になるような組がK個未満かを判定する。
    -> Xに関する二分探索をすることで、下位から丁度K番目の積の値がわかる！

これを判定するために、まずは下からK番目の積の値が0以上か0未満かを判定する。
zeros = (Aの中の0の個数)
over0 = (下からK番目の積の値が0以上ならTrue、0未満ならFalse)
"""

idx0 = bisect_left(A, 0)
idx1 = bisect_right(A, 0)
minus_prod = idx0 * (N - idx1)
zeros = idx1 - idx0

if minus_prod < K:
    over0 = True
else:
    over0 = False

"""
これを踏まえて、「小さい方の」値をfix(A[i]とする)して、
積がX以下になるような組を数え上げ。
"""

def within(X):
    """
    積がX以下になるような組がK個未満ならTrue、そうでなければFalseを返す。
    後から思ったけど、Xの正負で場合分けする必要なかった。
    """
    if over0 and X < 0:
        return True

    elif over0 and X >= 0:
        pair = 0
        for i in range(idx0): # A[i] < 0
            idx = bisect_left(A, ceil(X / A[i]))
            if i < idx:
                pair += N - idx
            else:
                pair += N - i - 1

        pair += (N - idx0) * zeros - zeros * (zeros + 1) // 2 # A[i] == 0

        for i in range(idx1, N): # A[i] > 0
            idx = bisect_right(A, X // A[i])
            if idx < i:
                continue
            else:
                pair += idx - i - 1
        #print("X={}, pair={}".format(X, pair))
        if pair < K:
            #print("pair={}<M".format(pair))
            return True
        else:
            #print("pair={}>=M".format(pair))
            return False

    elif X >= 0:
        return False

    elif X < 0:
        pair = 0
        for i in range(idx0): # A[i] < 0
            idx = bisect_left(A, ceil(X / A[i]))
            if i < idx:
                pair += N - idx
            else:
                pair += N - i - 1
        for i in range(idx1, N): # A[i] > 0
            idx = bisect_right(A, X // A[i])
            if idx < i:
                continue
            else:
                pair += idx - i - 1
        #print("X={}, pair={}".format(X, pair))
        if pair < K:
            #print("pair={}<M".format(pair))
            return True
        else:
            #print("pair={}>=M".format(pair))
            return False

"""
Xに関する二分探索をおこなった結果、
leftXはwithin(leftX, over0) == Falseになる最小のX
"""
def main():
    if A[0] >= 0:
        leftX = A[0] * A[1]
        rightX = A[-1] * A[-2]
    elif A[-1] < 0:
        leftX = A[-1] * A[-2]
        rightX = A[0] * A[1]
    else:
        leftX = A[0] * A[-1]
        rightX = max(A[0] * A[1], A[-1] * A[-2])


    while leftX != rightX:
        #print("left={}, right={}".format(leftX, rightX))
        middleX = (leftX + rightX) // 2
        if within(middleX):
            leftX = middleX + 1
        else:
            rightX = middleX

    return leftX

if __name__ == "__main__":
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left, bisect_right
from math import ceil

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
#print("A={}".format(A))
"""
積がX以下になるような組がK個未満かを判定する。
    -> Xに関する二分探索をすることで、下位から丁度K番目の積の値がわかる！

これを判定するために、まずは下からK番目の積の値が0以上か0未満かを判定する。
zeros = (Aの中の0の個数)
over0 = (下からK番目の積の値が0以上ならTrue、0未満ならFalse)
"""

idx0 = bisect_left(A, 0)
idx1 = bisect_right(A, 0)
minus_prod = idx0 * (N - idx0)
zeros = idx1 - idx0

if minus_prod < K:
    over0 = True
else:
    over0 = False

"""
これを踏まえて、「小さい方の」値をfix(A[i]とする)して、
積がX以下になるような組を数え上げ。
"""

def within(X):
    """
    積がX以下になるような組がK個未満ならTrue、そうでなければFalseを返す
    後から思ったけど、Xの正負で場合分けする必要なかった。
    """
    if over0 and X < 0:
        return True

    elif over0 and X >= 0:
        pair = 0
        for i in range(idx0): # A[i] < 0
            idx = bisect_left(A, ceil(X / A[i]))
            if i < idx:
                pair += N - idx
            else:
                pair += N - i - 1
        for i in range(idx0, idx1): # A[i] == 0
            pair += N - i - 1
        for i in range(idx1, N): # A[i] > 0
            idx = bisect_right(A, X // A[i]) - 1
            if idx < i:
                continue
            else:
                pair += idx - i
        #print("X={}, pair={}".format(X, pair))
        if pair < K:
            #print("pair={}<M".format(pair))
            return True
        else:
            #print("pair={}>=M".format(pair))
            return False

    elif X >= 0:
        return False

    elif X < 0:
        pair = 0
        for i in range(idx0): # A[i] < 0
            idx = bisect_left(A, ceil(X / A[i]))
            if i < idx:
                pair += N - idx
            else:
                pair += N - i - 1
        for i in range(idx1, N): # A[i] > 0
            idx = bisect_right(A, X // A[i])
            if idx < i:
                continue
            else:
                pair += idx - i
        #print("X={}, pair={}".format(X, pair))
        if pair < K:
            #print("pair={}<M".format(pair))
            return True
        else:
            #print("pair={}>=M".format(pair))
            return False

"""
Xに関する二分探索をおこなった結果、
leftXはwithin(leftX, over0) == Falseになる最小のX
"""
def main():
    if A[0] >= 0:
        leftX = A[0] * A[1]
        rightX = A[-1] * A[-2]
    elif A[-1] < 0:
        leftX = A[-1] * A[-2]
        rightX = A[0] * A[1]
    else:
        leftX = A[0] * A[-1]
        rightX = max(A[0] * A[1], A[-1] * A[-2])


    while leftX != rightX:
        #print("left={}, right={}".format(leftX, rightX))
        middleX = (leftX + rightX) // 2
        if within(middleX):
            leftX = middleX + 1
        else:
            rightX = middleX

    return leftX

if __name__ == "__main__":
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:

n,k = map(int,input().split())
arr = list(map(int,input().split()))
# arr.sort()
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) + pc*(pc-1))//2

if (k>ncc) and (k<=zcc+ncc):
    print(0)
elif 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.sort()
    arr2.sort()

    arr1len = len(arr1)
    arr2len = len(arr2)

    l = 0
    r = 10**18+1
    k = ncc - k
    while r-l!=1:

        cnt = 0
        mid = -((-r-l)//2)

        for m in range(arr1len):
            for p in range(arr2len):
                if arr1[m]*arr2[p] < mid:
                    cnt += 1
                else:
                    break

        if cnt < k:
            l = mid
        else:
            r = mid
    print(-l)

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.sort()
    arr2.sort()
    arr1len = len(arr1)
    arr2len = len(arr2)

    l = 0
    r = 10**18+1
    k -= (ncc+zcc)
    while r-l!=1:

        cnt = 0
        mid = -((-r-l)//2)

        for m1 in range(arr1len):
            for m2 in range(m1+1, arr1len):
                if arr1[m1]*arr1[m2] < mid:
                    cnt += 1
                else:
                    break

        for p1 in range(arr2len):
            for p2 in range(p1+1, arr2len):
                if arr2[p1]*arr2[p2] < mid:
                    cnt += 1
                else:
                    break

        if cnt < k:
            l = mid
        else:
            r = mid

    print(l)

Submission status: Wrong Answer

Solution code:

n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
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) + pc*(pc-1))//2

if (k>ncc) and (k<=zcc+ncc):
    print(0)
elif 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.sort()
    arr2.sort()

    arr1len = len(arr1)
    arr2len = len(arr2)

    l = 0
    r = 10**18+1
    k = ncc - k
    while r-l!=1:

        cnt = 0
        mid = (r+l)//2

        for m in range(arr1len):
            for p in range(arr2len):
                if arr1[m]*arr2[p] < mid:
                    cnt += 1
                else:
                    break

        if cnt < k:
            l = mid
        else:
            r = mid
    print(-l)

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.sort()
    arr2.sort()
    arr1len = len(arr1)
    arr2len = len(arr2)

    l = 0
    r = 10**18+1
    k -= (ncc+zcc)
    while r-l!=1:

        cnt = 0
        mid = (r+l)//2

        for m1 in range(arr1len):
            for m2 in range(m1+1, arr1len):
                if arr1[m1]*arr1[m2] < mid:
                    cnt += 1
                else:
                    break

        for p1 in range(arr2len):
            for p2 in range(p1+1, arr2len):
                if arr2[p1]*arr2[p2] < mid:
                    cnt += 1
                else:
                    break

        if cnt < k:
            l = mid
        else:
            r = mid

    print(l)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
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) + pc*(pc-1))//2

if (k>ncc) and (k<=zcc+ncc):
    print(0)
elif 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.sort()
    arr2.sort()
    arr1len = len(arr1)
    arr2len = len(arr2)

    cnt = 0
    mid = 0

    l = 0
    r = 10**18+1
    k = ncc - k
    while r-l!=1:

        cnt = 0

        mid = (r+l)//2

        for m in range(arr1len):
            for p in range(arr2len):
                if arr1[m]*arr2[p] < mid:
                    cnt += 1
                else:
                    break

        if cnt < k:
            l = mid
        else:
            r = mid
    print(-l)

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.sort()
    arr2.sort()
    arr1len = len(arr1)
    arr2len = len(arr2)

    l = 0
    r = 10**18+1
    cnt = 0
    mid = 0
    k -= (ncc+zcc)
    while r-l!=1:

        cnt = 0
        mid = (r+l)//2

        for m1 in range(arr1len):
            for m2 in range(arr1len):
                if m1 != m2:
                    if arr1[m1]*arr1[m2] < mid:
                        cnt += 1
                    else:
                        break

        for p1 in range(arr2len):
            for p2 in range(arr2len):
                if p1 != p2:
                    if arr2[p1]*arr2[p2] < mid:
                        cnt += 1
                    else:
                        break

        cnt = cnt// 2

        if cnt < k:
            l = mid
        else:
            r = mid

    print(l)

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/02/20

@author: fanta
'''
n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
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) + pc*(pc-1))//2

if (k>ncc) and (k<zcc+ncc):
    print(0)
elif 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.sort()
    arr2.sort()

    cnt = 0
    mid = 0

    l = 0
    r = 10**18+1
    k = ncc - k
    while r-l!=1:

        cnt = 0

        mid = (r+l)//2

        for m in range(len(arr1)):
            for p in range(len(arr2)):
                if arr1[m]*arr2[p] < mid:
                    cnt += 1
                else:
                    break

        if cnt < k:
            l = mid
        else:
            r = mid
    print(-l)

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

    l = 0
    r = 10**18+1
    cnt = 0
    mid = 0
    k -= (ncc+zcc)
    while r-l!=1:

        cnt = 0
        mid = (r+l)//2

        for m1 in range(len(arr1)):
            for m2 in range(len(arr1)):
                if m1 != m2:
                    if arr1[m1]*arr1[m2] < mid:
                        cnt += 1
                    else:
                        break

        for p1 in range(len(arr2)):
            for p2 in range(len(arr2)):
                if p1 != p2:
                    if arr2[p1]*arr2[p2] < mid:
                        cnt += 1
                    else:
                        break

        cnt = cnt// 2

        if cnt < k:
            l = mid
        else:
            r = mid

    print(l)

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/02/20

@author: fanta
'''
n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
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) + pc*(pc-1))//2

if (k>ncc) and (k<zcc+ncc):
    print(0)
elif 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.sort()
    arr2.sort()

    cnt = 0
    mid = 0

    l = 0
    r = 10**18+1
    k = ncc - k
    while r-l!=1:
        print()
        print("mid",mid)
        print("  l",l)
        print("  r",r)
        print("cnt",cnt)

        cnt = 0

        mid = (r+l)//2

        for m in range(len(arr1)):
            for p in range(len(arr2)):
                if arr1[m]*arr2[p] < mid:
                    cnt += 1
                else:
                    break

        if cnt < k:
            l = mid
        else:
            r = mid
    print(-l)

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

    l = 0
    r = 10**18+1
    cnt = 0
    mid = 0
    k -= (ncc+zcc)
    while r-l!=1:

        print()
        print("mid",mid)
        print("  l",l)
        print("  r",r)
        print("cnt",cnt)

        cnt = 0
        mid = (r+l)//2

        for m1 in range(len(arr1)):
            for m2 in range(len(arr1)):
                if m1 != m2:
                    if arr1[m1]*arr1[m2] < mid:
                        cnt += 1
                    else:
                        break

        for p1 in range(len(arr2)):
            for p2 in range(len(arr2)):
                if p1 != p2:
                    if arr2[p1]*arr2[p2] < mid:
                        cnt += 1
                    else:
                        break

        cnt = cnt// 2

        if cnt < k:
            l = mid
        else:
            r = mid

    print(l)

Submission status: Wrong Answer

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

AP=[]
AN=[]
Z=0
for i in range(N):
  if A[i]>0:
    AP.append(A[i])
  elif A[i]<0:
    AN.append(A[i])
  else:
    Z+=1
    
AP.sort()
AN.sort()
p=len(AP)
q=len(AN)

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

def f(nums, x): #numsの中でx以下の数字の数
  if nums[0]>x:
    return 0
  if nums[-1]<=x:
    return len(nums)
  a=0
  b=len(nums)-1
  while b-a>1:
    tmp=(b+a)//2
    if nums[tmp]<=x:
      a=tmp
    else:
      b=tmp
  return a+1

def g(nums, x): #numsの中でx以上の数字の数
  if nums[0]>x:
    return len(nums)
  if nums[-1]<x:
    return 0
  a=0
  b=len(nums)-1
  while b-a>1:
    tmp=(b+a)//2
    if nums[tmp]>=x:
      b=tmp
    else:
      a=tmp
    return len(nums)-b
  
if K<=a:
  x=AN[0]*AP[-1]
  y=AN[-1]*AP[0]
  if K==1:
    print(x)
    exit()
  if K==a:
    print(y)
    exit()
  while y-x>1:
    tmp=(y+x)//2
    counter=0
    for s in AP:
      counter+=f(AN, tmp/s)
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  K-=a+b
  if len(AP)>1 and len(AN)>1:
    x=min(AP[0]*AP[1], AN[-2]*AN[-1])
    y=max(AP[-2]*AP[-1], AN[0]*AN[1])
    while y-x>1:
      tmp=(y+x)//2
      counter1=0
      for s in AP:
        counter1+=g(AP, tmp/s)
      counter2=0
      for s in AN:
        counter2+=f(AN, tmp/s)
      counter=(counter1+1)//2+(counter2+1)//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
  elif len(AP)>1 and len(AN)<=1:
    x=AP[0]*AP[1]
    y=AP[-2]*AP[-1]
    while y-x>1:
      tmp=(y+x)//2
      counter=0
      for s in AP:
        counter+=g(AP, tmp/s)
      counter=(counter+1)//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
  else:
    x=AN[-2]*AN[-1]
    y=AN[0]*AN[1]
    while y-x>1:
      tmp=(y+x)//2
      counter=0
      for s in AN:
        counter+=f(AN, tmp/s)
      counter=(counter+1)//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)

Submission status: Wrong Answer

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

AP=[]
AN=[]
Z=0
for i in range(N):
  if A[i]>0:
    AP.append(A[i])
  elif A[i]<0:
    AN.append(A[i])
  else:
    Z+=1
    
AP.sort()
AN.sort()
p=len(AP)
q=len(AN)

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

def f(nums, x): #numsの中でx以下の数字の数
  if nums[0]>x:
    return 0
  if nums[-1]<=x:
    return len(nums)
  a=0
  b=len(nums)-1
  while b-a>1:
    tmp=(b+a)//2
    if nums[tmp]<=x:
      a=tmp
    else:
      b=tmp
  return a+1

def g(nums, x): #numsの中でx以上の数字の数
  if nums[0]>x:
    return len(nums)
  if nums[-1]<x:
    return 0
  a=0
  b=len(nums)-1
  while b-a>1:
    tmp=(b+a)//2
    if nums[tmp]>=x:
      b=tmp
    else:
      a=tmp
    return len(nums)-b
  

if K<=a:
  x=AN[0]*AP[-1]
  y=AN[-1]*AP[0]
  if K==1:
    print(x)
    exit()
  if K==a:
    print(y)
    exit()
  while y-x>1:
    tmp=(y+x)//2
    counter=0
    for s in AP:
      counter+=f(AN, tmp/s)
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  K-=a+b
  if len(AP)>1 and len(AN)>1:
    x=min(AP[0]*AP[1], AN[-2]*AN[-1])
    y=max(AP[-2]*AP[-1], AN[0]*AN[1])
    while y-x>1:
      tmp=(y+x)//2
      counter1=0
      for s in AP:
        counter1+=g(AP, tmp/s)
      counter2=0
      for s in AN:
        counter2+=f(AN, tmp/s)
      counter=(counter1+1)//2+(counter2+1)//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
  elif len(AP)>1 and len(AN)<=1:
    x=AP[0]*AP[1]
    y=AP[-2]*AP[-1]
    while y-x>1:
      tmp=(y+x)//2
      counter=0
      for s in AP:
        counter+=g(AP, tmp/s)
      counter=(counter+1)//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
  else:
    x=AN[-2]*AN[-1]
    y=AN[0]*AN[1]
    while y-x>1:
      tmp=(y+x)//2
      counter=0
      for s in AN:
        counter+=f(AN, tmp/s)
      counter=(counter+1)//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)

Submission status: Wrong Answer

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

d = []
for i in range(N):
  for j in range(N):
    if j == i:
      continue
    else:
      d.append(a[i]*a[j])
      
print(sorted(d)[K-1])

Submission status: Wrong Answer

Solution code:
import math

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

inList.sort()

if inList[0] * inList[N-1] <= 0:
  l_ba = inList[0] * inList[N-1]
else:
  l_ba = inList[0] * inList[1]

r_ba = max(inList[0] * inList[1], inList[N-2] * inList[N-1])

if l_ba == r_ba:
  print(l_ba)
else:
  
  l_ba = l_ba - 1
  r_ba = r_ba + 1
  l_first = l_ba
  r_first = r_ba
  
  x = int(0.5 * (l_ba + r_ba))
  
  for time in range(int(math.log2(r_first - l_first)) + 1):
    count = 0
    Ans = l_first
    
    for indx in range(N):
      if inList[indx] <= 0:
        for mulIndx in range(indx, -1, -1):
          if inList[indx] * inList[mulIndx] <= x:
            if indx != mulIndx:
              count += 1
              Ans = max(Ans, inList[indx] * inList[mulIndx])
          else:
            break
      elif inList[indx] > 0:
        for mulIndx in range(indx):
          if inList[indx] * inList[mulIndx] <= x:
            if indx != mulIndx:
              count += 1
              Ans = max(Ans, inList[indx] * inList[mulIndx])
          else:
            break
    
    print(l_ba, x, r_ba, count)
    
    if count == K:
      break
    elif count < K:
      l_ba = x
      x = int(0.5 * (l_ba + r_ba))
    else:
      r_ba = x
      x = int(0.5 * (l_ba + r_ba))
    
    if (r_ba - l_ba) == 1:
      x = r_ba
      l_ba = r_ba
      break
    elif l_ba == r_ba:
      break
    
  print(Ans)

Submission status: Wrong Answer

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

inList.sort()

#if inList[0] * inList[N-1] <= 0:
#  l_ba = inList[0] * inList[N-1] - 1
#else:
#  l_ba = inList[0] * inList[1] - 1

#r_ba = max(inList[0] * inList[1], inList[N-2] * inList[N-1]) + 1

l_ba = - 10 ** 18 - 1
r_ba =   10 ** 18 + 1

l_first = l_ba


if l_ba == r_ba:
  print(l_ba)
else:
  
  x = int(0.5 * (l_ba + r_ba))
  
  for time in range(int(0.5 * N * (N-1))):
    count = 0
    Ans = l_first
    
    for indx in range(N):
      if inList[indx] <= 0:
        for mulIndx in range(indx, -1, -1):
          if inList[indx] * inList[mulIndx] <= x:
            if indx != mulIndx:
              count += 1
              Ans = max(Ans, inList[indx] * inList[mulIndx])
          else:
            break
      elif inList[indx] > 0:
        for mulIndx in range(indx):
          if inList[indx] * inList[mulIndx] <= x:
            if indx != mulIndx:
              count += 1
              Ans = max(Ans, inList[indx] * inList[mulIndx])
          else:
            break
    
    count = count
#    print(l_ba, x, r_ba, count)
    
    if count == K:
      break
    elif count < K:
      l_ba = x
    else:
      r_ba = x
    
    x = int(0.5 * (l_ba + r_ba))

print(Ans)

Submission status: Wrong Answer

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

A = sorted(A)
num_minus, num_zero, num_plus = 0,0,0
for val in A:
  if val < 0:		num_minus+=1
  elif val == 0:	num_zero+=1
  else:				num_plus+=1

num_minus_pair = num_minus*num_plus
num_zero_pair = int(num_zero*(num_zero-1)/2+num_zero*(num_minus+num_plus))
num_plus_pair = int(num_minus*(num_minus-1)/2+num_plus*(num_plus-1)/2)
if num_minus_pair >= K:
  th0, th1 = min(A)*max(A), min(A)*max(A)/2
  pair_val_set = []
  count = 0
  while 1:
    for i in range(num_minus):
      for j in range(num_plus):
        val = A[i]*A[num_minus+num_zero+num_plus-1-j]
        if th0 <= val < th1:
          pair_val_set.append(val)
          count += 1
        else:
          break
    if count >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif count < K:
      th0 = th1
      #th1 /= th1 - th1/2
      th1 /= 2
elif num_minus_pair+num_zero_pair >= K:
  print(0)
elif num_minus_pair+num_zero_pair+num_plus_pair >= K:
  th0 = 0.0
  th1 = 0.0
  val0 = A[0]*A[1]
  val1 = A[num_minus+num_zero+num_plus-2]*A[num_minus+num_zero+num_plus-1]
  if val0 > val1:    th1 = float(val0/2)
  else:              th1 = float(val1/2)
  K = K - (num_minus_pair + num_zero_pair)
  pair_val_set = []
  count = 0
  while 1:
    for i in range(num_minus):
      for j in range(i+1,num_minus):
        val = A[num_minus-1-i]*A[num_minus-1-j]
        if th0 <= val < th1:
          pair_val_set.append(val)
          count += 1
        else:
          break
    for i in range(num_plus):
      for j in range(i+1,num_plus):
        val = A[num_minus+num_zero+i]*A[num_minus+num_zero+j]
        if th0 <= val < th1:
          pair_val_set.append(val)
          count += 1
        else:
          break
    if count >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif count < K:
      th0 = th1
      th1 = th1 + float((val0-th1)/2)