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():
    import sys
    from math import ceil
    from bisect import bisect_left, bisect_right
    N, K = map(int, sys.stdin.readline().split())
    A = sorted(list(map(int, sys.stdin.readline().split())))

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

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

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

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

        print(-ok)

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

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

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

            if or_higher_cnt >= K:
                ok = X
                continue

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

            if or_higher_cnt >= K:
                ok = X
                continue

            ng = X

        print(ok)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
z = 0
while a[z] < 0:
    z += 1
am = a[:z]
ap = a[z:]

if k <= len(am)*len(ap):
    ap = ap[::-1]
    a = -(10**18)-10
    b = 0
    while True:
        if b-a <= 1:
            break
        m = (a+b)//2
        count = 0
        r = 0
        while r+1 < len(am) and ap[0]*am[r] <= m:
            r += 1
        for i in range(len(ap)):
            while r > 0 and ap[i]*am[r] > m:
                r -= 1
            if ap[i]*am[r] <= m:
                count += r+1
            else:
                count += r
        if count < k:
            a = m
        else:
            b = m
    print(b)
else:
    k -= len(am)*len(ap)
    am = list(map(lambda x: -x, am[::-1]))
    a = 0
    b = 10**18+10
    while True:
        if b-a <= 1:
            break
        m = (a+b)//2
        count = 0
        r = len(ap)-1
        for i in range(len(ap)):
            while r > 0 and ap[i]*ap[r] > m:
                r -= 1
            if ap[i]*ap[r] <= m:
                if i <= r:
                    count -= 1
                count += r+1
            else:
                if i < r:
                    count -= 1
                count += r
        r = len(am)-1
        for i in range(len(am)):
            while r > 0 and am[i]*am[r] > m:
                r -= 1
            if am[i]*am[r] <= m:
                if i <= r:
                    count -= 1
                count += r+1
            else:
                if i < r:
                    count -= 1
                count += r
        if count//2 < k:
            a = m
        else:
            b = m
    print(b)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
z = 0
while a[z] < 0:
    z += 1
am = a[:z]
ap = a[z:]

if k <= len(am)*len(ap):
    ap = ap[::-1]
    a = -(10**18)-10
    b = 0
    while True:
        if b-a <= 1:
            break
        m = (a+b)//2
        count = 0
        for i in range(len(ap)):
            _a = 0
            _b = len(am)
            while True:
                if _b-_a <= 1:
                    break
                _m = (_a+_b)//2
                if ap[i]*am[_m] <= m:
                    _a = _m
                else:
                    _b = _m
            if ap[i]*am[0] > m:
                _b = 0
            count += _b
        if count < k:
            a = m
        else:
            b = m
    print(b)
else:
    k -= len(am)*len(ap)
    am = list(map(lambda x: -x, am[::-1]))
    a = 0
    b = 10**18+10
    while True:
        if b-a <= 1:
            break
        m = (a+b)//2
        count = 0
        for i in range(len(ap)):
            _a = 0
            _b = len(ap)
            while True:
                if _b-_a <= 1:
                    break
                _m = (_a+_b)//2
                if ap[i]*ap[_m] <= m:
                    _a = _m
                else:
                    _b = _m
            if ap[i]*ap[0] > m:
                _b = 0
            if i < _b:
                _b -= 1
            count += _b
        for i in range(len(am)):
            _a = 0
            _b = len(am)
            while True:
                if _b-_a <= 1:
                    break
                _m = (_a+_b)//2
                if am[i]*am[_m] <= m:
                    _a = _m
                else:
                    _b = _m
            if am[i]*am[0] > m:
                _b = 0
            if i < _b:
                _b -= 1
            count += _b
        if count//2 < k:
            a = m
        else:
            b = m
    print(b)

Submission status: Wrong Answer

Solution code:
import itertools

def resolve():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))

    multi_list = []

    A_per = itertools.permutations(A_list, 2)

    for a in A_per:
        multi_list.append(a[0] * a[1])

    multi_list = sorted(multi_list)
    print(multi_list[K-1])

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import itertools

def resolve():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))

    multi_list = []

    A_per = itertools.permutations(A_list, 2)

    for a in A_per:
        multi_list.append(a[0] * a[1])

    multi_list = sorted(multi_list)
    print(multi_list[K])

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

A = [A[i] for i in range(N) if A[i]!=0]
c = (N+len(A)-1)*(N-len(A))
N = len(A)
A.sort()
B = A[::-1]

def count(m):
    res = 0
    if m>=0:
        res += c
        j = N
        for i in range(N):
            if A[i]>0:
                break
            while j>0:
                if A[i]*A[j-1]<=m:
                    j -= 1
                else:
                    break
            res += N-j
        if A[i]>0:
            j = N-1
            for i in range(i,N):
                while j>=0:
                    if A[i]*A[j]>m:
                        j -= 1
                    else:
                        break
                res += j+1
    else:
        j = N
        for i in range(N):
            if B[i]<0:
                break
            while j>0:
                if B[i]*B[j-1]<=m:
                    j -= 1
                else:
                    break
            res += N-j
        if B[i]<0:
            j = -1
            for i in range(i,N):
                while j<N-1:
                    if B[i]*B[j+1]<=m:
                        j += 1
                    else:
                        break
                res += j+1
    for i in range(N):
        if A[i]*A[i]<=m:
            res -= 1
    res //= 2
    return res

ng = -10**18
ok = 10**18
m = (ng+ok)//2
if N==0:
    ans = 0
else:
    for n in range(100):
        if count(m)<K:
            ng = m
        else:
            ok = m
        m = (ng+ok)//2
    ans = int(ok)
print(ans)

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()

iplus = bisect.bisect_right(A,0)
izeros = bisect.bisect_left(A,0)

pluss = np.array(A[iplus:]).astype(np.int64)
zeros = A[izeros:iplus]
minuss = np.array(A[:izeros]).astype(np.int64)

nplus = len(pluss)
nzero = len(zeros)
nminus = len(minuss)

npminus = nplus * nminus
npzeros = nzero * (nplus + nminus) + nzero * (nzero-1)//2

if npminus < K <= npminus + npzeros:
    print( 0)
elif K <= npminus:
    mn = A[-1] * A[0]
    mx = 0
    while mx-mn > 1:
        mid = (mn+mx)//2
        #cnt = 0
        #for m in minuss:
        #    x = -(-mid//m)
        #    k = bisect.bisect_left(pluss,x)
        #    cnt += (nplus-k)
        #    if cnt >= K:
        #        break
        xs = -(-mid//minuss)
        cnt = nplus * nminus - np.sum(np.searchsorted(pluss,xs))
        if cnt >= K:
            mx = mid
        else:
            mn = mid
    print(mx)
else:
    nK = K - npminus - npzeros
    pluss2 = (-minuss)[::-1]
    mn = -1
    mx = A[-1]**2
    pluss_p2 = pluss**2
    pluss2_p2 = pluss2**2
    while mx-mn > 1:
        mid = (mn+mx)//2
        cnt = 0
        xs = mid//pluss
        cnt += np.sum(np.searchsorted(pluss,xs,side='right'))
        cnt -= np.count_nonzero(pluss_p2 <= mid)

        xs2 = mid//pluss2
        cnt += np.sum(np.searchsorted(pluss2,xs2,side='right'))
        cnt -= np.count_nonzero(pluss2_p2 <= mid)

        '''
        cnt2 = 0
        for m in pluss:
            x = mid//m
            k = bisect.bisect_right(pluss,x)
            cnt2 += k - (m**2 <= mid)
            if cnt2 >= 2*nK:
                break
        for m in pluss2:
            x = mid//m
            k = bisect.bisect_right(pluss2,x)
            cnt2 += k - (m**2 <= mid)
            if cnt2 >= 2*nK:
                break
        print(cnt,cnt2)
        '''
        cnt = cnt //2
        #print(mn,mid,mx,cnt)
        if nK <= cnt:
            mx = mid
        else:
            mn = mid
    print(mx)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import math

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

plus=[]
minus=[]
zero=[]
plus_cnt=0
minus_cnt=0
zero_cnt=0

for a in A:
    if 0<a: plus.append(a);plus_cnt+=1
    elif a==0: zero.append(a);zero_cnt+=1
    else: minus.append(a);minus_cnt+=1


plus_combi=plus_cnt*(plus_cnt-1)/2+minus_cnt*(minus_cnt-1)/2
minus_combi=minus_cnt*plus_cnt
zero_combi=N*(N-1)/2-plus_combi-minus_combi


if minus_combi<K<minus_combi+zero_combi:
    print 0
elif K<=minus_combi:
    minus=map(lambda x: x*-1, minus)  #計算をしやすくするため、マイナスの数字の配列をすべてプラスに符号転換する
    minus.sort(reverse=True) 
    plus.sort(reverse=True)
    #マイナスの数の尺取り
    def get_minus_count(n):
        cnt=0
        l=0
        for l in range(plus_cnt):
            r=minus_cnt-1
            while 0<=r:
                if n<=plus[l]*minus[r]:
                    cnt+=r+1
                    break
                else:
                    r-=1
        return cnt
    ng=0
    ok=10**18
    while ok-ng!=1:
        m=(ng+ok)/2
        if K<get_minus_count(m):
            ng=m
        else:
            ok=m
    print ng*-1

else:
    K-=minus_combi
    K-=zero_combi
    minus=map(lambda x: x*-1, minus)  #計算をしやすくするため、マイナスの数字の配列をすべてプラスに符号転換する
    minus.sort()

    def get_plus_count(n):
        cnt=0
        r=plus_cnt-1
        #尺取り
        for l in range(plus_cnt-1):
            while 0<r-l:
                if plus[l]*plus[r]<=n:
                    cnt+=(r-l)
                    break
                else:
                    r-=1

        r=minus_cnt-1

        #マイナスの数の配列から、n以下となる組み合わせ数をカウント
        for l in range(minus_cnt-1):
            while 0<r-l:
                if minus[l]*minus[r]<=n:
                    cnt+=(r-l)
                    break
                else:
                    r-=1
        return cnt


    ok=0
    ng=10**18
    while ng-ok!=1:
        m=(ng+ok)/2
        if get_plus_count(m)<=K-1:
            ok=m
        else:
            ng=m
    
    print ng

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import math

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

plus=[]
minus=[]
zero=[]
plus_cnt=0
minus_cnt=0
zero_cnt=0

for a in A:
    if 0<a: plus.append(a);plus_cnt+=1
    elif a==0: zero.append(a);zero_cnt+=1
    else: minus.append(a);minus_cnt+=1

#print "plus :: ",plus
#print "minus :: ",minus
#print "zero :: ",zero
#print "plus_cnt :: ",plus_cnt
#print "minus_cnt :: ",minus_cnt
#print "zero_cnt :: ",zero_cnt

plus_combi=plus_cnt*(plus_cnt-1)/2+minus_cnt*(minus_cnt-1)/2
minus_combi=minus_cnt*plus_cnt
zero_combi=N*(N-1)/2-plus_combi-minus_combi

K-=minus_combi
K-=zero_combi

#print "plus_combi,minus_combi,zero_combi :: ",plus_combi,minus_combi,zero_combi
#print "K :: ",K

if minus_combi<K<minus_combi+zero_combi:
    print 0
    quit()

minus=map(lambda x: x*-1, minus)  #計算をしやすくするため、マイナスの数字の配列をすべてプラスに符号転換する
minus.sort()

def getcount(n):
    cnt=0
    r=plus_cnt-1
    #尺取り
    for l in range(plus_cnt-1):
        while 0<r-l:
            if plus[l]*plus[r]<=n:
                cnt+=(r-l)
                break
            else:
                r-=1

    r=minus_cnt-1

    #マイナスの数の配列から、n以下となる組み合わせ数をカウント
    for l in range(minus_cnt-1):
        while 0<r-l:
            if minus[l]*minus[r]<=n:
                cnt+=(r-l)
                break
            else:
                r-=1
    return cnt


ok=0
ng=10**18
while ng-ok!=1:
    m=(ng+ok)/2
    if getcount(m)<=K-1:
        ok=m
    else:
        ng=m
 
print ng

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import math

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

plus=[]
minus=[]
zero=[]
plus_cnt=0
minus_cnt=0
zero_cnt=0

for a in A:
    if 0<a: plus.append(a);plus_cnt+=1
    elif a==0: zero.append(a);zero_cnt+=1
    else: minus.append(a);minus_cnt+=1

#print "plus :: ",plus
#print "minus :: ",minus
#print "zero :: ",zero
#print "plus_cnt :: ",plus_cnt
#print "minus_cnt :: ",minus_cnt
#print "zero_cnt :: ",zero_cnt

plus_combi=plus_cnt*(plus_cnt-1)/2+minus_cnt*(minus_cnt-1)/2
minus_combi=minus_cnt*plus_cnt
zero_combi=N*(N-1)/2-plus_combi-minus_combi

K-=minus_combi
K-=zero_combi

#print "plus_combi,minus_combi,zero_combi :: ",plus_combi,minus_combi,zero_combi
#print "K :: ",K

minus=map(lambda x: x*-1, minus)  #計算をしやすくするため、マイナスの数字の配列をすべてプラスに符号転換する
minus.sort()

def getcount(n):
    cnt=0
    r=plus_cnt-1
    #尺取り
    for l in range(plus_cnt-1):
        while 0<r-l:
            if plus[l]*plus[r]<=n:
                cnt+=(r-l)
                break
            else:
                r-=1

    r=minus_cnt-1

    #マイナスの数の配列から、n以下となる組み合わせ数をカウント
    for l in range(minus_cnt-1):
        while 0<r-l:
            if minus[l]*minus[r]<=n:
                cnt+=(r-l)
                break
            else:
                r-=1
    return cnt


ok=0
ng=10**18
while ng-ok!=1:
    m=(ng+ok)/2
    if getcount(m)<=K-1:
        ok=m
    else:
        ng=m
 
print ng

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import math

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

plus=[]
minus=[]
zero=[]
plus_cnt=0
minus_cnt=0
zero_cnt=0

for a in A:
    if 0<a: plus.append(a);plus_cnt+=1
    elif a==0: zero.append(a);zero_cnt+=1
    else: minus.append(a);minus_cnt+=1

#print "plus :: ",plus
#print "minus :: ",minus
#print "zero :: ",zero
#print "plus_cnt :: ",plus_cnt
#print "minus_cnt :: ",minus_cnt
#print "zero_cnt :: ",zero_cnt

plus_combi=plus_cnt*(plus_cnt-1)/2+minus_cnt*(minus_cnt-1)/2
minus_combi=minus_cnt*plus_cnt
zero_combi=N*(N-1)/2-plus_combi-minus_combi

K-=minus_combi
K-=zero_combi

#print "plus_combi,minus_combi,zero_combi :: ",plus_combi,minus_combi,zero_combi
#print "K :: ",K

def getcount(n):
    cnt=0
    r=plus_cnt-1
    #尺取り
    for l in range(plus_cnt-1):
        while 0<r-l:
            if plus[l]*plus[r]<=n:
                cnt+=(r-l)
                break
            else:
                r-=1
    return cnt


ok=0
ng=10**18
while ng-ok!=1:
    m=(ng+ok)/2
    if getcount(m)<=K-1:
        ok=m
    else:
        ng=m
 
print ng

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import math

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

plus=[]
minus=[]
zero=[]
plus_cnt=0
minus_cnt=0
zero_cnt=0

for a in A:
    if 0<a: plus.append(a);plus_cnt+=1
    elif a==0: zero.append(a);zero_cnt+=1
    else: minus.append(a);minus_cnt+=1


plus_combi=plus_cnt*(plus_cnt-1)/2+minus_cnt*(minus_cnt-1)/2
minus_combi=minus_cnt*plus_cnt
zero_combi=N*(N-1)/2-plus_combi-minus_combi

K-=minus_combi
K-=zero_combi

minus=map(lambda x: x*-1, minus)  #計算をしやすくするため、マイナスの数字の配列をすべてプラスに符号転換する
minus.sort()

def getcount(n):
    cnt=0
    for i in range(plus_cnt-1):
        x=plus[i]
        #nn=math.ceil(n/x)
        nn=(n+1)//x
        cnt+=bisect_right(plus[i+1:],nn)

    for i in range(minus_cnt-1):
        x=minus[i]
        #nn=math.ceil(n/x)
        nn=(n+1)//x
        cnt+=bisect_right(minus[i+1:],nn)
    return cnt

ok=0
ng=10**18
while ng-ok!=1:
    m=(ng+ok)/2
    if getcount(m)<=K-1:
        ok=m
    else:
        ng=m

print ng

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import math

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

plus=[]
minus=[]
zero=[]
plus_cnt=0
minus_cnt=0
zero_cnt=0

for a in A:
    if 0<a: plus.append(a);plus_cnt+=1
    elif a==0: zero.append(a);zero_cnt+=1
    else: minus.append(a);minus_cnt+=1


plus_combi=plus_cnt*(plus_cnt-1)/2+minus_cnt*(minus_cnt-1)/2
minus_combi=minus_cnt*plus_cnt
zero_combi=N*(N-1)/2-plus_combi-minus_combi

K-=minus_combi
K-=zero_combi

minus=map(lambda x: x*-1, minus)  #計算をしやすくするため、マイナスの数字の配列をすべてプラスに符号転換する
minus.sort()

def getcount(n):
    cnt=0
    for i in range(plus_cnt-1):
        x=plus[i]
        nn=math.ceil(n/x)
        cnt+=bisect_right(plus[i+1:],nn)

    #for i in range(minus_cnt-1):
    #    x=minus[i]
    #    nn=math.ceil(n/x)
    #    cnt+=bisect_right(minus[i+1:],nn)
    return cnt

ok=0
ng=10**18
while ng-ok!=1:
    m=(ng+ok)/2
    if getcount(m)<=K-1:
        ok=m
    else:
        ng=m

print ng

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import math

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

plus=[]
minus=[]
zero=[]
plus_cnt=0
minus_cnt=0
zero_cnt=0

for a in A:
    if 0<a: plus.append(a);plus_cnt+=1
    elif a==0: zero.append(a);zero_cnt+=1
    else: minus.append(a);minus_cnt+=1


plus_combi=plus_cnt*(plus_cnt-1)/2+minus_cnt*(minus_cnt-1)/2
minus_combi=minus_cnt*plus_cnt
zero_combi=N*(N-1)/2-plus_combi-minus_combi

K-=minus_combi
K-=zero_combi

minus=map(lambda x: x*-1, minus)  #計算をしやすくするため、マイナスの数字の配列をすべてプラスに符号転換する
minus.sort()

def getcount(n):
    cnt=0
    for i in range(plus_cnt-1):
        x=plus[i]
        nn=math.ceil(n/x)
        cnt+=bisect_right(plus[i+1:],nn)

    for i in range(minus_cnt-1):
        x=minus[i]
        nn=math.ceil(n/x)
        cnt+=bisect_right(minus[i+1:],nn)
    return cnt

ok=0
ng=10**18
while ng-ok!=1:
    m=(ng+ok)/2
    if getcount(m)<=K-1:
        ok=m
    else:
        ng=m

print ng

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import math

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

plus=[]
minus=[]
zero=[]
for a in A:
    if 0<a: plus.append(a)
    elif a==0: zero.append(a)
    else: minus.append(a)

plus_cnt=len(plus)
minus_cnt=len(minus)
zero_cnt=len(zero)

plus_combi=plus_cnt*(plus_cnt-1)/2+minus_cnt*(minus_cnt-1)/2
minus_combi=minus_cnt*plus_cnt
zero_combi=N*(N-1)/2-plus_combi-minus_combi

K-=minus_combi
K-=zero_combi

minus=map(lambda x: x*-1, minus)  #計算をしやすくするため、マイナスの数字の配列をすべてプラスに符号転換する
minus.sort()

def getcount(n):
    cnt=0
    for i in range(plus_cnt-1):
        x=plus[i]
        nn=math.ceil(n/x)
        cnt+=bisect_right(plus[i+1:],nn)

    for i in range(minus_cnt-1):
        x=minus[i]
        nn=math.ceil(n/x)
        cnt+=bisect_right(minus[i+1:],nn)
    return cnt

ok=0
ng=10**18
while ng-ok!=1:
    m=(ng+ok)/2
    if getcount(m)<=K-1:
        ok=m
    else:
        ng=m

print ng

Submission status: Wrong Answer

Solution code:
N = list(map(int,input().rstrip().split()))
num = N[0]
k = N[1]

X = list(map(int,input().split()))
res_list = []
i = 0
for xi in X:
  j = 0
  for xj in X:
    if i != j :
      res = xi*xj
      res_list.append(res)
    j += 1
  
  i += 1

res_list=sorted(res_list)
print(res_list[k+1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right


def main():
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    minus_arr = [-x for x in arr]
    arr.sort()
    minus_arr.sort()

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

        smaller = 0
        smaller_or_same = 0
        for i, a in enumerate(arr, 1):
            if a > 0:
                b = mid // a
                smaller_or_same += max(0, bisect_right(arr, b) - i)
                if mid % a:
                    b += 1
                smaller += max(0, bisect_left(arr, b) - i)
            if a < 0:
                b = mid // (-a)
                smaller_or_same += min(n - i, bisect_right(minus_arr, b))
                if mid % a:
                    b += 1
                smaller += min(n - i, bisect_left(minus_arr, b))
            if a == 0:
                if mid >= 0:
                    smaller_or_same += n - i
                if mid > 0:
                    smaller += n - i
        print(mid, smaller, smaller_or_same)
        if smaller < k and k <= smaller_or_same:
            print(mid)
            return
        elif smaller_or_same < k:
            ok = mid + 1
        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()))

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 = []
  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)
        else:
          break
    if len(pair_val_set) >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif len(pair_val_set) < K:
      th0 = th1
      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)
  #print('K:', K)
  pair_val_set = []
  while 1:
    for i in range(num_minus-1):
      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)
        else:
          break
    for i in range(num_plus-1):
      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)
        else:
          break
    if len(pair_val_set) >= K:
      pair_val_set = sorted(pair_val_set)
      print(pair_val_set[K-1])
      break
    elif len(pair_val_set) < K:
      th0 = th1
      th1 = th1 + float((val0-th1)/2)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

q=np.searchsorted(A, -1, side='right')
Z=np.searchsorted(A, 0, side='right')-q
p=N-q-Z
AP=A[-p:]
if q>0:
  AN=A[:q]

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

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

Submission status: Wrong Answer

Solution code:
import bisect

N, K = map(int, input().split())
A = [int(x) for x in input().split()]

# Aを正負で分け、「積が負、積が0、積が正」それぞれのペア数を求める
A_minus = sorted([a for a in A if a < 0])
A_plus = sorted([a for a in A if a > 0])
len_minus = len(A_minus)
len_plus = len(A_plus)
len_zero = N - len_minus - len_plus
pairs_num = (len_minus * len_plus,
             (len_minus + len_plus) * len_zero + len_zero * (len_zero - 1) // 2,
             len_minus * (len_minus - 1) // 2 + len_plus * (len_plus - 1) // 2)
assert sum(pairs_num) == N * (N - 1) // 2

if K <= pairs_num[0]:
    L = -10 ** 18
    R = -1
    while True:
        M = (L + R) // 2
        count = 0
        j = 0
        for i in range(len_plus):
            while j < len_minus and A_plus[i] * A_minus[j] <= M:
                j += 1
            count += j
        
        if count < K and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M
            
elif pairs_num[0] < K <= pairs_num[0] + pairs_num[1]:
    print(0)
    
else:
    K -= pairs_num[0] + pairs_num[1]
    A_minus = list(map(lambda x: -x, reversed(A_minus)))
    L = 1
    R = 10 ** 18
    while True:
        M = (L + R) // 2
        count = 0
        j = 0
        for i in range(len_minus-1, -1, -1):
            while j < len_minus and A_minus[i] * A_minus[j] <= M:
                j += 1
            count += max(0, j - i - 1)
        j = 0
        for i in range(len_plus-1, -1, -1):
            while j < len_plus and A_plus[i] * A_plus[j] <= M:
                j += 1
            count += max(0, j - i - 1)
            
        print(K, L, R, M, count)
            
        if count < K and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M

Submission status: Wrong Answer

Solution code:
import numpy as np


def partsolve(A, x, positive, zero, negative):
    """
    :param A:
    :param x:
    :return: Aの積のペアの中で、x以下となるペアの個数
    """
    count = 0
    if x >= 0:
        count = len(zero) * len(A)
    P = x // positive
    Pc = np.searchsorted(A, P, side='right')
    count += Pc.sum()

    N = (-x-1) // -negative
    Nc = np.searchsorted(A, N, side='right')
    Nc = len(A) - Nc
    count += Nc.sum()

    count -= np.count_nonzero(A * A <= x)
    return count // 2

def solve(N, K, As):
    A = np.array(sorted(As), np.int64)
    positive = A[A > 0]
    zero = A[A == 0]
    negative = A[A < 0]

    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(A, mid, positive, zero, negative)
        print(mid, c)
        if c < K:
            left = mid
        else:
            right = mid
    return right


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Submission status: Wrong Answer

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

p=np.searchsorted(A, -1, side='right')
Z=np.searchsorted(A, 0, side='right')-p
q=N-p-Z
AP=A[:p]
AN=A[p+Z:]

c=p*(p-1)//2+q*(q-1)//2
b=(N-Z)*Z+Z*(Z-1)//2
a=p*q
  
if K<=a:
  x=-10**18
  y=-1
  if K==1:
    print(x)
    exit()
  if K==a:
    print(y)
    exit()
  while y-x>1:
    tmp=(y+x)//2
    counter=sum([np.searchsorted(AP, tmp/AN[i], side='right') for i in range(q)])
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  K-=a+b
  x=1
  y=10**18
  if len(AP)>1 and len(AN)>1:
    while y-x>1:
      tmp=(y+x)//2
      counter1=sum([np.searchsorted(AP[:i], tmp/AP[i], side='right') for i in range(1, p)])
      counter2=sum([q-1-i-np.searchsorted(AN[i+1:], tmp/AN[i], side='left') for i in range(q-2, -1, -1)])
      counter=counter1+counter2
      if counter<K:
        x=tmp
      else:
        y=tmp
  elif len(AP)>1 and len(AN)<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=sum([np.searchsorted(AP[:i], tmp/AP[i], side='right') for i in range(1, p)])
      if counter<K:
        x=tmp
      else:
        y=tmp
  else:
    while y-x>1:
      tmp=(y+x)//2
      counter=sum([q-1-i-np.searchsorted(AN[i+1:], tmp/AN[i], side='left') for i in range(q-2, -1, -1)])
      if counter<K:
        x=tmp
      else:
        y=tmp
  print(y)