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:
# 上からk番目の数がxである。
# xとなる数はk個以上　かつ　x＋1となる数はk-1個以下
# xとなる数がk個以上となるxの最大値
from bisect import bisect_left, bisect_right
import sys

input = sys.stdin.buffer.readline


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

ng = -4 * (10 ** 10) - 1
ok = 4 * (10 ** 10) + 1


def count(x):
    cnt = 0
    for i in range(n):
        a = A[i]
        if a > 0:
            gendo = x // a
            pos = bisect_right(A, gendo)
            cnt += pos
            if pos >= i + 1:
                cnt -= 1
        elif a < 0:
            gendo = (-x + (-a - 1)) // (-a)
            pos = bisect_left(A, gendo)
            cnt += n - pos
            if pos <= i:
                cnt -= 1
        else:
            if x < 0:
                cnt += 0
            else:
                cnt += n - 1
    return cnt // 2


# x = mid 以上のものをカウントしたい
while ok - ng > 1:
    mid = (ok + ng) // 2
    cnt = count(mid)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Wrong Answer

Solution code:
# 上からk番目の数がxである。
# xとなる数はk個以上　かつ　x＋1となる数はk-1個以下
# xとなる数がk個以上となるxの最大値
from bisect import bisect_left, bisect_right
import sys

input = sys.stdin.buffer.readline


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

ng = -2 * (10 ** 10) - 1
ok = 2 * 10 ** 10 + 1


def count(x):
    cnt = 0
    for i in range(n):
        a = A[i]
        if a > 0:
            gendo = x // a
            pos = bisect_right(A, gendo)
            cnt += pos
            if pos >= i + 1:
                cnt -= 1
        elif a < 0:
            gendo = (-x + (-a - 1)) // (-a)
            pos = bisect_left(A, gendo)
            cnt += n - pos
            if pos <= i:
                cnt -= 1
        else:
            if x < 0:
                cnt += 0
            else:
                cnt += n - 1
    return cnt // 2


# x = mid 以上のものをカウントしたい
kouho = -(10 ** 10)
while ok - ng > 1:
    mid = (ok + ng) // 2
    cnt = count(mid)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Wrong Answer

Solution code:
import bisect
import numpy as np
n,k = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

zero = A.count(0)
inm = bisect.bisect_left(A,0)
inp = bisect.bisect_right(A,0)
mi = A[:inm]
pl = A[inp:]
numm = inm
nump = n-inp

def search(x):
    count = 0
    if x >= 0:
        count += zero*(n-zero)+numm*nump+(zero*(zero-1))//2
      
        for i in range(nump):
            a = bisect.bisect_right(pl,x/pl[i])    
            count += max(a-i-1,0)
            
        for i in range(numm):
            a = bisect.bisect_left(mi,x/mi[i])
            if a > i:
                count += max(0,numm-a)
            
        return count
    else:
        for i in mi:
            a = bisect.bisect_left(pl,x/i)
            count += nump-a
        return count

left = -10**18-1
right = 10**18+1
while right > left+1:
    mid = (left+right)//2
    a = search(mid)

    if a >= k:
        right = mid
    else:
        left = mid
print(right)

Submission status: Wrong Answer

Solution code:
# 上からk番目の数がxである。
# xとなる数はk個以上　かつ　x＋1となる数はk-1個以下
# xとなる数がk個以上となるxの最大値
from bisect import bisect_left, bisect_right
import sys

input = sys.stdin.buffer.readline


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

ng = -(10 ** 20)
ok = 10 ** 20


# x = mid * a 以上のものをカウントしたい
kouho = -(10 ** 10)
while ok - ng > 1:
    mid = (ok + ng) // 2
    cnt = 0
    for i in range(n):
        a = A[i]
        if a > 0:
            gendo = mid // a
            pos = bisect_right(A, gendo)
            cnt += pos
            if pos >= i + 1:
                cnt -= 1
        elif a < 0:
            gendo = mid // a
            pos = bisect_left(A, gendo)
            cnt += n - pos
            if pos <= i:
                cnt -= 1
        else:
            if mid < 0:
                cnt += 0
            else:
                cnt += n - 1
    print(ok, ng, mid, cnt)
    if cnt // 2 >= k:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Wrong Answer

Solution code:
from bisect import *

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
zl, zr = bisect_left(A, 0), bisect_right(A, 0)
minus_cnt = zl*(N-zr)
zero_cnt = N*(zr-zl)-(zr-zl+1)*(zr-zl)//2
if K <= minus_cnt:
    B, A = A[zr:], A[:zl]
    l, r = -10**18-1, -1
    while l+1 < r:
        m = (l+r)//2
        cnt = 0
        for a in A:
            cnt += (N-zr)-bisect_left(B, m/a)
        if cnt < K:
            l = m
        else:
            r = m
    print(r)
elif minus_cnt < K <= minus_cnt+zero_cnt:
    print(0)
else:
    B, A = A[zr:], [-x for x in A[:zl][::-1]]
    l, r = 0, 10**18
    while l+1 < r:
        m = (l+r)//2
        cnt = minus_cnt+zero_cnt
        for i, a in enumerate(A, 1):
            cnt += bisect_right(A[i:], m/a)
        for i, b in enumerate(B, 1):
            cnt += bisect_right(B[i:], m/b)
        if cnt == 412:
	        print(m, cnt)
        if cnt < K:
            l = m
        else:
            r = m
    print(r)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

A.sort()


def test(x):
    cnt = 0

    for a in A:
        if a == 0:
            if 0 <= x:
                t = N - 1
            else:
                t = 0

        elif a > 0:
            m = x / a
            i = bisect.bisect_right(A, m)
            t = i
            if a <= m:
                t -= 1
        elif a < 0:
            m = x / a
            i = bisect.bisect_left(A, m)
            t = N - i
            if m <= a:
                t -= 1

        cnt += t

    cnt //= 2

    return K <= cnt


l = -(10 ** 19)  # NG
r = 10 ** 19  # OK

while l + 1 != r:
    mid = (l + r) // 2

    if test(mid):
        r = mid
    else:
        l = mid

print(r)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# Not AC
# Code On Contest

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

A.sort()


def test(x):
    cnt = 0

    for a in A:
        if a == 0:
            if 0 <= x:
                t = N - 1
            else:
                t = 0

        elif a > 0:
            m = x / a
            i = bisect.bisect_right(A, m)
            t = i
            if a <= m:
                t -= 1
        elif a < 0:
            m = x / a
            i = bisect.bisect_left(A, m)
            t = N - i
            if m <= a:
                t -= 1

        cnt += t

    cnt //= 2

    return K <= cnt


l = -(10 ** 19)  # NG
r = 10 ** 19  # OK

while l + 1 != r:
    mid = (l + r) // 2

    if test(mid):
        r = mid
    else:
        l = mid

print(r)

Submission status: Wrong Answer

Solution code:
import sys

def f1(m):
    j=0
    num=0
    for x in ap:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    h,l=0,10**18
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        else: l=md
    print(-h-1)

elif pz>=k:
    print(0)

else:
    k-=pz
    h,l=10**20,0
    while h-l>1:
        md=(h+l)//2
        p=f2(md)
        if p>=k: h=md
        else: l=md
    print(h)

Submission status: Wrong Answer

Solution code:
import sys

def f1(m):
    j=0
    num=0
    for x in ap:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    h,l=-1,10**20
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        else: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    k-=pz
    h,l=10**20,0
    while h-l>1:
        md=(h+l)//2
        p=f2(md)
        if p>=k: h=md
        else: l=md
    print(h)

Submission status: Wrong Answer

Solution code:
import sys

def f1(m):
    j=0
    num=0
    for x in ap:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    h,l=-1,ap[-1]*am[-1]
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        else: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    k-=pz
    h,l=10**20,0
    while h-l>1:
        md=(h+l)//2
        p=f2(md)
        if p>=k: h=md
        else: l=md
    print(h)

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
import sys

def f1(m):
    j=0
    num=0
    for x in ap:
        while j<minus and x*am[j]<m:
            j+=1
        num+=j
    return plus*minus-num
            
def f2(m):
    return f3(m,ap)+f3(m,am)


def f3(m,l):
    nagasa=len(l)
    if nagasa<2: return 0
    j=nagasa-1
    num=0
    for i in range(nagasa):
        while j>-1 and l[i]*l[j]>m:
            j-=1
        num+=j+1
        if i<=j: num-=1
    return num//2

n,k=map(int,input().split())
a=list(map(int,input().split()))
ap=sorted([a[i] for i in range(n) if a[i]>0])
am=sorted([-a[i] for i in range(n) if a[i]<0])
az=sorted([a[i] for i in range(n) if a[i]==0])

plus,minus,zero=len(ap),len(am),len(az)
pz=plus*minus+zero*(zero-1)//2+zero*(n-zero)


if plus*minus>=k:
    h,l=0,ap[-1]*am[-1]
    while l-h>1:
        md=(h+l)//2
        p=f1(md)
        if p>=k: h=md
        elif p<k: l=md
    print(-h)

elif pz>=k:
    print(0)

else:
    try:
        k-=pz
        if ap: h,l=ap[-1]**2,ap[0]**2-1
        if am: h,l=max(h,am[-1]**2),min(l,am[0]**2-1)
        while h-l>1:

            md=(h+l)//2
            p=f2(md)
            if p>=k: h=md
            elif p<k: l=md
        print(h)
    except:
        b=1
        while True:
            b+=1

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

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

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

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

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

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

print(overEq)

Submission status: Wrong Answer

Solution code:
def getProduct(n, m):
    product = 1
    for i in range(2, len(n)):
        product *= pow(n[i], m[i])
    return product

Submission status: Wrong Answer

Solution code:
import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    minus = bisect.bisect_left(a, 0)
    zero = bisect.bisect_left(a, 1) - minus
    plus = n - (minus + zero)

    minus_product = minus * plus
    zero_product = zero * (minus + plus) + ((zero - 1) * zero) // 2

    a_minus = a[0:minus]
    a_minus.sort()
    a_plus = a[minus + zero:]

    if k <= minus_product:
        km = k
        m_min = a_minus[0] * a_plus[-1]
        m_max = a_minus[-1] * a_plus[0]

        ok = m_min
        ng = m_max + 1

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            cnt = 0
            mm = minus - 1
            pp = 0
            while mm >= 0 and pp < plus:
                x = a_minus[mm] * a_plus[pp]
                if x < mid:
                    cnt += (plus - pp)
                    mm -= 1
                else:
                    pp += 1

            if cnt < km:
                ok = mid
            else:
                ng = mid

        print(ok)

    elif k <= (minus_product + zero_product):
        print(0)

    else:
        kp = k - (minus_product + zero_product)
        ppmin, pmmin = INF, INF
        ppmax, pmmax = -1, -1
        if plus >= 2:
            ppmin = a_plus[0] * a_plus[1]
            ppmax = a_plus[-1] * a_plus[-2]
        if minus >= 2:
            pmmin = a_minus[-1] * a_minus[-2]
            pmmax = a_minus[0] * a_minus[1]

        p_absmin = min(ppmin, pmmin)
        p_absmax = max(ppmax, pmmax)

        ok = p_absmin
        ng = p_absmax + 1
        mid = (ok + ng) // 2

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            cnt = 0
            p1 = 0
            p2 = plus - 1

            while p2 - p1 > 0:
                x = a_plus[p1] * a_plus[p2]
                if x < mid:
                    cnt += (p2 - p1)
                    p1 += 1
                else:
                    p2 -= 1

            m1 = minus - 1
            m2 = 0
            while m1 - m2 > 0:
                x = a_minus[m1] * a_minus[m2]
                if x < mid:
                    cnt += (m1 - m2)
                    m1 -= 1
                else:
                    m2 += 1

            if cnt < kp:
                ok = mid
            else:
                ng = mid

        print(ok)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    minus = bisect.bisect_left(a, 0)
    zero = bisect.bisect_left(a, 1) - minus
    plus = n - (minus + zero)

    minus_product = minus * plus
    zero_product = zero * (minus + plus) + ((zero - 1) * zero) // 2

    a_minus = list(map(abs, a[0:minus]))
    a_minus.sort()
    a_plus = a[minus + zero:]

    if k <= minus_product:
        km = k - 1
        m_absmin = a_minus[0] * a_plus[0]
        m_absmax = a_minus[-1] * a_plus[-1]

        ok = m_absmax
        ng = m_absmin - 1

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            cnt = 0
            mm = 0
            pp = plus - 1
            while mm < minus - 1 and pp >= 0:
                x = a_minus[mm] * a_plus[pp]
                if x < mid:
                    cnt += pp
                    mm += 1
                else:
                    pp -= 1

            if cnt < km:
                ok = mid
            else:
                ng = mid

        print(-ok)

    elif k <= (minus_product + zero_product):
        print(0)
    else:
        kp = k - (minus_product + zero_product)
        ppmin, pmmin = INF, INF
        ppmax, pmmax = -1, -1
        if plus >= 2:
            ppmin = a_plus[0] * a_plus[1]
            ppmax = a_plus[-1] * a_plus[-2]
        if minus >= 2:
            pmmin = a_minus[0] * a_minus[1]
            pmmax = a_minus[-1] * a_minus[-2]

        p_absmin = min(ppmin, pmmin)
        p_absmax = max(ppmax, pmmax)

        ok = p_absmin
        ng = p_absmax + 1
        mid = (ok + ng) // 2

        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            cnt = 0
            p1 = 0
            p2 = plus - 1

            while p2 - p1 > 0:
                x = a_plus[p1] * a_plus[p2]
                if x < mid:
                    cnt += (p2 - p1)
                    p1 += 1
                else:
                    p2 -= 1

            m1 = 0
            m2 = minus - 1
            while m2 - m1 > 0:
                x = a_minus[m1] * a_minus[m2]
                if x < mid:
                    cnt += (m2 - m1)
                    m1 += 1
                else:
                    m2 -= 1

            if cnt < kp:
                ok = mid
            else:
                ng = mid

        print(ok)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


b=list()
for i in range(1,len(a)+1):
    for j in range(1,i):
        b.append(j*i)
b.sort()

print(b[k-1])

Submission status: Wrong Answer

Solution code:
import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))
res =[]
res = [int(x) * int(y) for x, y in itertools.permutations(a, 2)] # str型
res.sort()
print(res[k])

Submission status: Wrong Answer

Solution code:
import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))
res =[]
res = [int(x) * int(y) for x, y in itertools.permutations(a, 2)] # str型
res.sort()
print(res[2])

Submission status: Wrong Answer

Solution code:
import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))
res =[]
res = [int(x) * int(y) for x, y in itertools.permutations(a, 2)] # str型
res.sort()
print(res[3])

Submission status: Wrong Answer

Solution code:
a = True
if a:
  print(a)

Submission status: Wrong Answer

Solution code:
print('')

Submission status: Wrong Answer

Solution code:
def resolve():
    N,K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    pos,neg,zero = list(), list(), 0

    for a in A:
        if a>0: pos.append(a)
        elif a==0: zero += 1
        else: neg.append(a)

    pos.sort()
    neg.sort()

    negs = len(pos) * len(neg)
    zeros = (len(pos)+len(neg)) * zero + zero*(zero-1)//2

    # x未満になる組み合わせの個数
    def calc(x):
        result = 0
        if x < 0: # pos * neg
            i = len(pos)-1
            j = len(neg)-1
            while i >= 0:
                while j >= 0 and pos[i] * neg[j] >= x: j -= 1
                if j < 0: break
                result += j + 1
                i -= 1
            return result
        elif x == 0: # zero
            return negs + zeros
        else: # neg*neg or pos*pos
            # neg * neg
            i = len(neg)-1
            j = 0
            while i >= 0:
                while j < len(neg) and neg[i] * neg[j] >= x: j += 1
                if j >= len(neg): break
                result += len(neg)-j
                if neg[i]*neg[i] < x: result -= 1
                i -= 1

            # pos * pos
            i = 0
            j = len(pos)-1
            while i < len(pos):
                while j >= 0 and pos[i] * pos[j] >= x: j -= 1
                if j < 0: break
                result += j + 1
                if pos[i]*pos[i] < x: result -= 1
                i += 1
            return negs + zeros + result//2

    left = -10**18
    right = 10**18+1
    while right-left>1:
        mid = (right+left)//2
        val = calc(mid)
        if val<K:left = mid
        else: right = mid

    print(left)

resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N,K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    pos,neg,zero = list(), list(), 0

    for a in A:
        if a>0: pos.append(a)
        elif a==0: zero += 1
        else: neg.append(a)

    pos.sort()
    neg.sort()

    negs = len(pos) * len(neg)
    zeros = (len(pos)+len(neg)) * zero + zero*(zero-1)//2

    # x未満になる組み合わせの個数
    def calc(x):
        result = 0
        if x < 0: # pos * neg
            i = len(pos)-1
            while i >= 0:
                j = 0
                while j < len(neg):
                    if pos[i] * neg[j] >= x:
                        break
                    j += 1
                result += j
                i -= 1
            return result
        elif x == 0: # zero
            return negs + zeros
        else: # neg*neg or pos*pos
            # neg * neg
            i = len(neg)-1
            while i >= 0:
                j = i - 1
                while j >= 0:
                    if neg[i] * neg[j] >= x:
                        break
                    j -= 1
                if j != i - 1:
                    result += i-1-j
                i -= 1

            # pos * pos
            i = 0
            while i < len(pos):
                j = i + 1
                while j < len(pos):
                    if pos[i] * pos[j] >= x:
                        break
                    j += 1
                if j != i + 1:
                    result += j-(i+1)
                i += 1
            return negs + zeros + result

    left = -10**18
    right = 10**18+1
    while right-left>1:
        mid = (right+left)//2
        val = calc(mid)
        if val<K:left = mid
        else: right = mid

    print(left)

resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,K = map(int,input().split())
    a = np.array(list(map(int,input().split())))
    a.sort()
    posi,zero,nega = a[a>0],a[a==0],a[a<0]

    lp,lz,ln = len(posi),len(zero),len(nega)
    
    def ch(x):
        count = 0
        if x >= 0:
            count += lz*N
        count += np.searchsorted(a,x//posi,side="right").sum()
        count += (N-np.searchsorted(a,np.ceil(x/nega))).sum()
        count -= np.count_nonzero(a**2<=x)
        return count//2

    l,r = -10**18-1,10**18+1
    while r-l > 1:
        mid = (r+l)//2
        if ch(mid) >= K:
            r = mid
        else:
            l = mid

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,K = map(int,input().split())
    a = np.array(list(map(int,input().split())))
    a.sort()
    posi,zero,nega = a[a>0],a[a==0],a[a<0]

    lp,lz,ln = len(posi),len(zero),len(nega)
    
    def ch(x):
        count = 0
        if x >= 0:
            count += lz*N
        count += np.searchsorted(a,x//posi,side="right").sum()
        count += (N-np.searchsorted(a,np.ceil(x//nega))).sum()
        count -= np.count_nonzero(a**2<=x)
        return count//2

    l,r = -10**18-1,10**18+1
    while r-l > 1:
        mid = (r+l)//2
        if ch(mid) >= K:
            r = mid
        else:
            l = mid

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

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left, bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()


def countPair(N, A, x):
    """
    「積がx未満になる組」の個数を返す。

    一旦(Ai * Aj)と(Aj * Ai)は区別して、かつ(Ai * Ai)も許すことにする。
    そしてAiをfixしたとき、Ai * Aj < xなるjの個数をカウントしていけば良い。
    これも二分探索で数えられる。

    ただしAiがマイナスの時は大きい数から、プラスの時は小さい数からOKなことに注意。

    最後に重複分を処理して値を返す。
    """
    num1 = 0
    num2 = 0
    for i in range(N):
        if A[i] < 0:
            idx = bisect_right(A, x / A[i])
            num1 += N - idx
        elif A[i] > 0:
            idx = bisect_left(A, x / A[i])
            num1 += idx
        elif x > 0:
            num1 += N

        if A[i] * A[i] < x:
            num2 += 1

    return (num1 - num2) // 2


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    """
    (K個目の値) = (「積がx未満になる組がK個未満」であるようなxの最大値)
    として決め打ち二分探索を行う。
    """
    l = -10 ** 18 - 1
    r = 10 ** 18 + 1
    while r - l > 1:
        m = (l + r) // 2
        if countPair(N, A, m) < K:
            l = m
        else:
            r = m
    print(l)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

values = {
    '-': [],
    '0': [],
    '+': []
}
for i in range(len(aa)):
    for j in range(i + 1, len(aa)):
        if aa[i] == 0 or aa[j] == 0:
            values['0'].append(0)
        elif (aa[i] > 0 and aa[j] > 0) or (aa[i] < 0 and aa[j] < 0):
            values['+'].append(aa[i] * aa[j])
        else:
            values['-'].append(aa[i] * aa[j])
print(values)

if len(values['-']) + len(values['0']) < k:
    # 正
    values['+'].sort()
    print(values['+'][(k - (len(values['-']) + len(values['0']))) - 1])
elif len(values['-']) < k:
    # 0
    print('0')
else:
    # 負
    values['-'].sort()
    print(values['-'][k - 1])

Submission status: Wrong Answer

Solution code:
import bisect

def solve():
    N, K = [int(_) for _ in raw_input().split()]
    A = [int(_) for _ in raw_input().split()]
    A.sort()
    l = -10**18; r = 10**18
    while (l < r - 1):
        mid = (l + r) / 2
        total = 0
        for i in range(N):
            if A[i] > 0:
                up = bisect.bisect_right(A, mid*1.0/A[i])
                total += up
            elif A[i] < 0:
                low = bisect.bisect_left(A, mid*1.0/A[i])
                total += N - low
            else:
                if mid >= 0:
                    total += N
            if A[i] * A[i] <= mid:
                total -= 1
        total /= 2
        if total < K:
            l = mid
        else:
            r = mid
    print r

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import heapq
n,k = list(map(int, input().split()))
arr = list(map(int, input().split()))
lis=[]
for i in range(n):
  for j in range(i+1,n):
   heapq.heappush(lis,arr[i]*arr[j]);
   heapq.heapify(lis);
print(lis[k-1])

Submission status: Wrong Answer

Solution code:
import heapq
n,k = list(map(int, input().split()))
arr = list(map(int, input().split()))
lis=[]
for i in range(n):
  for j in range(i+1,n):
   heapq.heappush(lis,arr[i]*arr[j]);
print(lis[k-1])

Submission status: Wrong Answer

Solution code:
n,k = list(map(int, input().split()))
arr = list(map(int, input().split()))
lis=[];
for i in range(n):
  for j in range(i+1,n):
   lis.append(arr[i]*arr[j]);
print(lis)
lis.sort()
print(lis[k-1])

Submission status: Wrong Answer

Solution code:
import bisect
import heapq

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

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

A.sort()

index_left=bisect.bisect_left(A,0)
index_right=bisect.bisect_right(A,0)

n_plus=n-index_right
n_minus=index_left

P=A[-n_plus:]
M=A[:n_minus]

S=[]
heapq.heapify(S)
ANS=[]

def get_count(lim):
    c=0
    for i in range(len(P)-1):
        for j in range(i+1,len(P)):
            if P[i]*P[j]<=lim:
                c+=1
    for i in range(len(M)-1):
        for j in range(i+1,len(M)):
            if M[i]*M[j]<=lim:
                c+=1
    return c

if k<=n_plus*n_minus:
    cnt=0
    heapq.heappush(S,(P[-1]*M[0],-1,0))
    while cnt<=k:
        s,p,m=heapq.heappop(S)
        m+=1
        if m<len(M):
            heapq.heappush(S,(P[p]*M[m],p,m))
        m-=1
        p-=1
        if p>=-1*len(P):
            heapq.heappush(S,(P[p]*M[m],p,m))
        cnt+=1
        ANS.append(s)
    print(ANS[k-1])
    
    
elif k<=n*(n-1)//2-(n_plus*(n_plus-1)//2)-(n_minus*(n_minus-1)//2):
    print(0)
else:
    k-=n*(n-1)//2-(n_plus*(n_plus-1)//2)-(n_minus*(n_minus-1)//2)
    left=0
    right=10**18
    while left+1!=right:
        mid=(right+left)//2
        if k<=get_count(mid):
            right=mid
        else:
            left=mid
    print(right)

Submission status: Wrong Answer

Solution code:
import bisect

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
# 積がx未満となるペアの個数totがK個未満となるxの最大値を二分探索で求める
# lがOK,rがNG
l_x = -10**18 - 1
r_x = 10**18 + 1
while l_x + 1 < r_x:
    x = (l_x + r_x)//2
    tot = 0
    # 積がx未満となるペアの個数を求めてtotに追加する
    for i in range(N):
        a = A[i]
        if a > 0:
            n = bisect.bisect_left(A, (x+a-1)//a)
            tot += n
            if a*a < x:
                tot -= 1
        elif a < 0:
            n = bisect.bisect_right(A, (x+a-1)//a)
            tot += N-n
            if a*a < x:
                tot-= 1
        else:
            if x > 0:
                tot += N - 1
    tot /= 2
    if tot < K:
        l_x = x
    else:
        r_x = x
print(l_x)