Problem:


Score: 400 points

Problem Statement

We have N integers A_1, A_2, ..., A_N.

There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \frac{N(N-1)}{2}

-10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 3
3 3 -4 -2

Sample Output 1

-6

There are six ways to form a pair. The products of those pairs are 9, -12, -6, -12, -6, 8.

Sorting those numbers in ascending order, we have -12, -12, -6, -6, 8, 9. The third number in this list is -6.

Sample Input 2

10 40
5 4 3 2 -1 0 0 0 0 0

Sample Output 2

6

Sample Input 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

Sample Output 3

448283280358331064



Sample input:
4 3
3 3 -4 -2


Sample output:
-6

Submission status: Wrong Answer

Solution code:
import itertools

n,k=map(int, input().split())
a=list(map(int, input().split()))
lst = []
for i in itertools.combinations(a, 2):
    if len(lst) > k:
        break
    else:
        lst.append(i[0]*i[1])
lst.sort()
print(lst[k-1])

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
mib = -10 ** 18 * 2
mab = 10**18*2
c = 0
o = 0
while mib != mab:
    b = (mib + mab) // 2
    
    maa = -10**18*2
    co = 0
    for i in a:
        mi = 0
        ma = n - 1
        if i >= 0:
            if i * a[0] > b:
                continue
            while mi != ma:
                mm = (mi + ma) // 2 + 1
                if i * a[mm] <= b:
                    mi = mm
                else:
                    ma = mm - 1
            co += mi + 1
            maa = max(maa,i*a[mi])
            if i * i <= b:
                co -= 1
        else:
            if i * a[-1] > b:
                continue
            while mi != ma:
                mm = (mi + ma) // 2
                if i * a[mm] <= b:
                    ma = mm
                else:
                    mi = mm + 1
            maa = max(maa, i*a[mi])
            co += n - mi
            if i * i <= b:
                co -= 1
    if co // 2 == k:
        break
    if co//2 >= k:
        mab = b
    else:
        mib = b + 1
    o += 1
print(maa)

Submission status: Wrong Answer

Solution code:
import itertools

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

comb_num = int(N * (N - 1) / 2)
reverse = K > comb_num / 2

sAs = sorted(As, reverse=reverse)

products = []
count = 0
for a, b in list(itertools.combinations(sAs, 2)):
    products.append(a * b)
    count += 1
    if count > K + 100:
        break

if not reverse:
    print(sorted(products)[K - 1])
else:
    print(sorted(products, reverse=reverse)[comb_num - K])

Submission status: Wrong Answer

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

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

n,k = LI()
a = LI()
a.sort()
if a[0] <= 0 and a[-1] <= 0:
    a.sort(reverse=1)
    x = n-1
    while k > x:
        k -= x
        x -= 1
    m = n - x - 1
    print(a[m]*a[m+k])
elif a[0] >= 0 and a[-1] >= 0:
    x = n-1
    while k > x:
        k -= x
        x -= 1
    m = n - x - 1
    print(a[m]*a[m+k])
else:
    minus = []
    plus = []
    m,p = 0,0
    for i in range(n):
        if a[i] < 0:
            minus.append(a[i])
            m += 1
        else:
            plus.append(a[i])
            p += 1
    if m*p >= k:
        h = k % p
        l = k // p
        print(minus[l]*plus[h])
    else:
        k -= m*p
        lst = []
        for i in range(p):
            for j in range(i+1,p):
                lst.append(plus[i]*plus[j])
        for i in range(m):
            for j in range(i+1,m):
                lst.append(minus[i]*minus[j])
        lst.sort()
        print(lst[k-1])

Submission status: Wrong Answer

Solution code:
import itertools
from functools import reduce

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

p = list(itertools.permutations(a, 2))
x = []

for i in range(n * (n - 1) // 2):
    x.append(reduce(lambda x, y: x * y, list(p[i])))

x.sort()
print(x[k-1])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
alist = list(map(int,input().split()))
blist = []

for i in range(n):
    a = alist[i]
    m = i + 1
    for h in range(m, n):
        b = alist[h]
        blist.append(a*b)

blist.sort()
print(blist)

print(blist[k-1])

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = sorted([int(i) for i in input().split()])
A_m = []
A_p = []
for a in A:
    if a < 0:
        A_m.append(a)
    else:
        A_p.append(a)
from itertools import combinations
# 負 * 正(大きい順)
if K <= len(A_m) * len(A_p):
    idx_m = K // len(A_p)
    idx_p = -(K % len(A_m))
    ans = A_m[idx_m] * A_p[idx_p]
# 負 * 負
# 正 * 正
else:
    test = []
    for a in combinations(A_p,2):
        test.append(a[0]*a[1])
    for a in combinations(A_m,2):
        test.append(a[0]*a[1])
    test = sorted(test)
    ans = test[K - (len(A_m) * len(A_p)) - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

def updiv(x,y):
    if x % y == 0:
        return x // y
    else:
        return x // y + 1

def wantA(m):

    ret = 0

    for l in L:

        if m % l == 0:
            B = m // l
        else:
            B = m / l

        ret += len(R) - bisect.bisect_left(R,B)

    return ret

def wantB(m):

    ret = 0

    for i in range(len(R)):

        if R[i] == 0:
            ret += i
            continue

        if m % R[i] == 0:
            B = m // R[i]
        else:
            B = m // R[i]
 
        ret += min(i , bisect.bisect_right(R , B))

    
    for i in range(len(L2)):

        if m % L2[i] == 0:
            B = m // L2[i]
        else:
            B = m // L2[i]
 
        ret += min(i , bisect.bisect_right(L2 , B))

    return ret
        

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

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

L = []
L2 = []
R = [] #0以上

for i in range(N):

    if A[i] < 0:
        L.append(A[i])
        L2.append(-1 * A[i])
    else:
        R.append(A[i])

L.sort()
R.sort()
L2.sort()

if K <= len(L) * len(R):

    l = L[0] * R[-1] - 1
    r = L[-1] * R[0] + 1

    while r - l != 1:

        m = (l+r) // 2

        num = wantA(m)

        if num >= K:
            r = m
        else:
            l = m

    print (r)

else:

    l = -1
    r = 10 ** 18 + 1

    K -= len(L) * len(R)

    while r-l != 1:

        m = (l+r)//2

        num = wantB(m)
        #print (m , num)


        if num >= K:
            r = m
        else:
            l = m

        #print (l,r)

    print (r)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = input().split()
A = [int(a) for a in A]

import itertools

A = sorted(A)
c = list(itertools.combinations(A,2))
print(c[K-1][0]*c[K-1][1])

Submission status: Wrong Answer

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

arr = []
for i in range(N):
    for j in range(i+1, N):
        arr.append(A[i]*A[j])

print(arr[K-1])

Submission status: Wrong Answer

Solution code:
import itertools

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

reverse = K > N * (N - 1) / 2

sAs = sorted(As, reverse=reverse)

products = []
count = 0
for a, b in list(itertools.combinations(sAs, 2)):
    products.append(a * b)
    count += 1
    if count > K + 10:
        break

print(sorted(products, reverse=reverse)[K - 1])

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
l = list()
for _ in range(len(A)):
    k = _ + 1
    while k != len(A):
        l.append(A[_]*A[k])
        k+=1
print(sorted(l, reverse=True)[K-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
import time

# t = time.time()

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

a = np.array(list(map(int, input().split())))

b = np.array([])

for i in range(len(a) - 1):
    x = a[i]
    b = np.append(b, a[i+1:] * x)


b.sort()
print(int(b[k-1]))

# print(time.time() - t)

Submission status: Wrong Answer

Solution code:
n,k=input().split(" ")
arr=input().split(" ")

list=[]
for i in range(len(arr)-1):
    for j in range(i+1,len(arr)):
        val=int(int(arr[i])*int(arr[j]))
        list.append(val)

print(sorted(list))
print(sorted(list)[int(k)-1])

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def check(s,A):
    N,K = map(int, s.split())
    A = [int(i) for i in A.split()]
    seki = []
    for a,b in combinations(A, 2):
        seki.append(a*b)
    print(seki[K-1])
    
s = input()
A = input()
check(s,A)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
listo = list(map(int, input().split()))
prod = []
for i in range(N):
    for j in range(i+1, N):
        prod.append(listo[i] * listo[j])
prod.sort()
print(prod)
print(prod[K-1])

Submission status: Wrong Answer

Solution code:
from itertools import chain
n, k = map(int, input().split())
a = list(map(int, input().split()))
products = list(chain(*((a[i] * a[j] for j in range(n) if i != j) for i in range(n))))
products.sort()
print(products[k - 1])

Submission status: Wrong Answer

Solution code:
import bisect

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

# eager

A.sort()

ret = []

for i in range(len(A) - 1):
  for j in range(i, len(A)):
    bisect.insort(ret, A[i] * A[j])

print(ret[K])

Submission status: Wrong Answer

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

s = []

for i in range(0, n - 1):
    for j in range(i + 1, n):
        s.append(a[i] * a[j])

sx = sorted(s)
print(sx)
print(sx[k - 1])

Submission status: Wrong Answer

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

C = list(itertools.combinations(A, 2))
ans = []
for c in C:
    ans.append(c[0] * c[1])
print(ans)
ans.sort()
print(ans[K-1])

Submission status: Wrong Answer

Solution code:
from heapq import *

n, k = map(int, input().split())
a = list(map(int, input().split()))
q = []
for i in range(n):
    for j in range(i+1, n):
        x = -a[i]*a[j]
        if len(q)<k:
            q.append(x)
        else:
            if len(q)==k:
                heapify(q)                
            heappushpop(q, x)
print(-q[0])

Submission status: Wrong Answer

Solution code:
from heapq import *

n, k = map(int, input().split())
a = list(map(int, input().split()))
q = []
for i in range(n):
    for j in range(i+1, n):
        x = -a[i]*a[j]
        if len(q)<k:
            q.append(x)
        else:
            heappushpop(q, x)
print(-q[0])

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort()
    l = -10**18-1
    r = 10**18+1
    while r-l > 1:
        m = (l+r) >> 1
        s = 0
        for i in range(n):
            ai = a[i]
            if ai == 0:
                if m > 0:
                    s += n-i-1
            elif ai > 0:
                b = m//ai
                j = bisect.bisect_right(a,b)
                if j <= i:
                    continue
                c = j-i-1
                s += c
            else:
                b = -(m//(-ai))
                j = bisect.bisect_left(a,b)
                if j < i+1:
                    j = i+1
                c = n-j
                s += c
        if s <= k-1:
            l = m
        else:
            r = m
    print(r)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort()
    l = -10**18-1
    r = 10**18+1
    while r-l > 1:
        m = (l+r) >> 1
        s = 0
        for i in range(n):
            ai = a[i]
            if ai == 0:
                if m > 0:
                    s += n-i-1
            elif ai > 0:
                b = m//ai
                j = bisect.bisect_right(a,b)
                if j <= i:
                    continue
                c = j-i-1
                s += c
            else:
                b = -(m//(-ai))
                j = bisect.bisect_left(a,b)
                j = max(i+1,j)
                c = n-j
                s += c
        if s <= k-1:
            l = m
        else:
            r = m
    print(r)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 無限 #####
# inf = float('inf')

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')

def main():
	N,K = inputMap()
	A = inputList()

	ans = []
	for i in range(N):
		for j in range(i+1,N):
			tmp = A[i] * A[j]
			ans.append(tmp)

	#ans.sort()
	print(ans[K-1])

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]

l = [int(i) for i in input().split()]
l.sort()

print(l)

Submission status: Wrong Answer

Solution code:
import sys
range = xrange
input = raw_input

n, k = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()

l = -10**18 - 100
r = 10**18 + 100
while l < r:
    mid = l + r >> 1

    counter = 0
    for i in range(n):
        L = 0
        R = i
        while L < R:
            MID = L + R >> 1
            if A[MID] * A[i] <= mid:
                L = MID + 1
            else:
                R = MID
        counter += L
        #j = 0
        #while j < i and A[j] * A[i] <= mid:
        #    j += 1
        #counter += j
    if counter >= k:
        r = mid
    else:
        l = mid + 1

print l

Submission status: Time Limit Exceeded

Solution code:
# ABC 155 D
f=lambda:map(int,input().split())
N,K=f()
A=list(f())
A.sort()
def br2(a,b):
    # a/b以下
    ok=-1
    ng=N
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if b>0:
            if b*A[mid]<=a:
                ok=mid
            else:
                ng=mid
        else:
            if b*A[mid]>=a:
                ok=mid
            else:
                ng=mid
    return ok+1

def bl2(a,b):
    # a/b未満
    ok=-1
    ng=N
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if b>0:
            if b*A[mid]<a:
                ok=mid
            else:
                ng=mid
        else:
            if b*A[mid]>a:
                ok=mid
            else:
                ng=mid
    return ok+1

def check(x):
    # 積のうちでx以下であるようなものがK個以上かどうか
    res=0
    for a in A:
        if a<0:
            res+=N-bl2(x,a)
        elif a>0:
            res+=br2(x,a)
        else:
            if x>=0:
                res+=N
            else:
                res+=0
        if a*a<=x:
            res-=1
    return res//2>=K
   
can=[A[0]*A[0],A[-1]*A[-1],A[0]*A[-1]]
ok=max(can)+1
ng=min(can)-1
while abs(ok-ng)>1:
    mid=(ok+ng)//3
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# ABC 155 D
f=lambda:map(int,input().split())
N,K=f()
A=list(f())
A.sort()
def br2(a,b):
    # a/b以下
    ok=-1
    ng=N
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if b>0:
            if b*A[mid]<=a:
                ok=mid
            else:
                ng=mid
        else:
            if b*A[mid]>=a:
                ok=mid
            else:
                ng=mid
    return ok+1

def bl2(a,b):
    # a/b未満
    ok=-1
    ng=N
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if b>0:
            if b*A[mid]<a:
                ok=mid
            else:
                ng=mid
        else:
            if b*A[mid]>a:
                ok=mid
            else:
                ng=mid
    return ok+1

def check(x):
    # 積のうちでx以下であるようなものがK個以上かどうか
    res=0
    for a in A:
        if a>0:
            res+=br2(x,a)
        elif a<0:
            res+=N-bl2(x,a)
        else:
            if x>=0:
                res+=N
            else:
                res+=0
        if a*a<=x:
            res-=1
    return res//2>=K
   
can=[A[0]*A[0],A[-1]*A[-1],A[0]*A[-1]]
ok=max(can)+1
ng=min(can)-1
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# ABC 155 D
f=lambda:map(int,input().split())
N,K=f()
A=list(f())
A.sort()
def br2(A,a,b):
    # a/b以下
    ok=-1
    ng=len(A)
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if b>0:
            if b*A[mid]<=a:
                ok=mid
            else:
                ng=mid
        else:
            if b*A[mid]>=a:
                ok=mid
            else:
                ng=mid
    return ok+1

def bl2(A,a,b):
    # a/b未満
    ok=-1
    ng=len(A)
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if b>0:
            if b*A[mid]<a:
                ok=mid
            else:
                ng=mid
        else:
            if b*A[mid]>a:
                ok=mid
            else:
                ng=mid
    return ok+1

def check(x):
    # 積のうちでx以下であるようなものがK個以上かどうか
    res=0
    for a in A:
        if a>0:
            res+=br2(A,x,a)
        elif a<0:
            res+=N-bl2(A,x,a)
        else:
            if x>=0:
                res+=N
            else:
                res+=0
        if a*a<=x:
            res-=1
    return res//2>=K
   
can=[A[0]*A[0],A[-1]*A[-1],A[0]*A[-1]]
ok=max(can)+1
ng=min(can)-1
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# ABC 155 D
from bisect import bisect_right as br
from bisect import bisect_left as bl
from fractions import Fraction as F

f=lambda:map(int,input().split())
N,K=f()
A=list(f())
A.sort()
def br2(A,a,b):
    # a/b以下
    ok=-1
    ng=len(A)
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if b>0:
            if b*A[mid]<=a:
                ok=mid
            else:
                ng=mid
        else:
            if b*A[mid]>=a:
                ok=mid
            else:
                ng=mid
    return ok+1

def bl2(A,a,b):
    # a/b未満
    if b==0:
        #ERROR
        return
    ok=-1
    ng=len(A)
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if b>0:
            if b*A[mid]<a:
                ok=mid
            else:
                ng=mid
        else:
            if b*A[mid]>a:
                ok=mid
            else:
                ng=mid
    return ok+1

def check(x):
    # 積のうちでx以下であるようなものがK個以上かどうか
    res=0
    for a in A:
        if a>0:
            res+=br2(A,x,a)
        elif a<0:
            res+=N-bl2(A,x,a)
        else:
            if x>=0:
                res+=N
            else:
                res+=0
        if a*a<=x:
            res-=1
    return res//2>=K
   
can=[A[0]*A[0],A[-1]*A[-1],A[0]*A[-1]]
ok=max(can)+1
ng=min(can)-1
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# ABC 155 D
from bisect import bisect_right as br
from bisect import bisect_left as bl
from fractions import Fraction as F

f=lambda:map(int,input().split())
N,K=f()
A=list(f())
A.sort()
def check(x):
    # 積のうちでx以下であるようなものがK個以上かどうか
    res=0
    for a in A:
        if a>0:
            res+=br(A,F(x,a))
        elif a<0:
            res+=N-bl(A,F(x,a))
        else:
            if x>=0:
                res+=N
            else:
                res+=0
        if a*a<=x:
            res-=1
    return res//2>=K
   
can=[A[0]*A[0],A[-1]*A[-1],A[0]*A[-1]]
ok=max(can)+1
ng=min(can)-1
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
# ABC 155 D
from bisect import bisect_right as br
from bisect import bisect_left as bl
from fractions import Fraction as F

f=lambda:map(int,input().split())
N,K=f()
A=list(f())
A.sort()
def check(x):
    # 積のうちでx以下であるようなものがK個以上かどうか
    res=0
    for a in A:
        if a>0:
            res+=br(A,F(x,a))
        elif a<0:
            res+=N-bl(A,F(x,a))
        else:
            if x>=0:
                res+=N
            else:
                res+=0
        if a*a<=x:
            res-=1
    return res//2>=K
    
ok=10**20
ng=-10**20
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
k=int(input().split()[1])-1
a=map(int,input().split())
print(sorted([i*j for i,j in combinations(a,2)])[k])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
Aminus=[]
Aplus=[]
negative=0
positive=0
posinega=0
for i in range(N):
    if A[i]>0:
        positive+=1
        Aplus.append(A[i])
    elif A[i]<0:
        negative+=1
        Aminus.append(A[i])
    else:
        posinega+=1
Aplus.sort()
Aminus.sort()
PLUS=positive*positive+negative*negative
MINUS=2*positive*negative
ZERO=N*N-PLUS-MINUS

PLUS=(PLUS-(N-posinega))//2
MINUS=MINUS//2
ZERO=(ZERO-posinega)//2
if K<=MINUS:
    #ans<0
    low=-10**30
    high=0
    while(high-low>1):
        mid=(high+low)//2
        '''
        A[i]*A[j]<lowとなる(i<j)の組み合わせはK個未満である
        A[i]*A[j]<highとなる(i<j)の組み合わせはK個以上である
        tmpはA[i]*A[j]<midとなる(i<j)の組み合わせである
        '''
        tmp=0
        for i in range(positive):
            low0=-1
            high0=negative
            while(high0-low0>1):
                mid0=(high0+low0)//2
                '''
                Aplus[i]*Aminus[j]はjについて単調増加である。
                Aplus[i]*Aminus[low0]<mid<=Aplus[i]*Aminus[high0]を常に満たす必要がある
                '''
                if Aplus[i]*Aminus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
        if tmp<K:
            low=mid
        else:
            high=mid
    print(low)
elif K<=MINUS+ZERO:
    print(0)
else:
    K-=MINUS+ZERO
    #ans>0
    low=0
    high=10**30
    Aminus=Aminus[::-1]
    while(high-low>1):
        mid=(high+low)//2
        '''
        A[i]*A[j]<lowとなる(i<j)の組み合わせはK個未満である
        A[i]*A[j]<highとなる(i<j)の組み合わせはK個以上である
        tmpはA[i]*A[j]<midとなる(i<j)の組み合わせである
        '''
        tmp=0
        for i in range(positive):
            low0=-1
            high0=positive
            while(high0-low0>1):
                mid0=(high0+low0)//2
                '''
                Aplus[i]*Aplus[j]はjについて単調増加である。
                Aplus[i]*Aplus[low0]<mid<=Aplus[i]*Aplus[high0]を常に満たす必要がある
                '''
                if Aplus[i]*Aplus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
            if Aplus[i]*Aplus[i]<mid:
                tmp-=1
        for i in range(negative):
            low0=-1
            high0=negative
            while(high0-low0>1):
                mid0=(high0+low0)//2
                if Aminus[i]*Aminus[mid0]<mid:
                    low0=mid0
                else:
                    high0=mid0
            tmp+=high0
            if Aminus[i]*Aminus[i]<mid:
                tmp-=1
        tmp=tmp//2
        if tmp<K:
            low=mid
        else:
            high=mid
    print(low)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
input = sys.stdin.readline

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

    minus, plus, zero = [], [], 0
    for i in range(n):
        if a[i] < 0:
            minus.append(a[i])
        elif a[i] > 0:
            plus.append(a[i])
        else:
            zero += 1
    
    minus_count = len(minus) * len(plus)
    zero_count = zero * (zero - 1) // 2 + zero * (len(minus) + len(plus))

    minus.sort()
    plus.sort()

    if k <= minus_count:
        l, r = -int(1e18), 0
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            border = 0
            for v in minus:
                while border < len(plus) and v * plus[border] > value:
                    border += 1 
                count += len(plus) - border

            if count >= k:
                r = value
            else:
                l = value

        ans = r

    elif k <= zero_count + minus_count:
        ans = 0
        
    else:
        l, r = 0, int(1e18)
        count_default = minus_count + zero_count
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            
            border = 0
            for v in minus:
                while border < len(minus) and v * minus[-border-1] <= value:
                    border += 1
                count += border
                if border > 0 and v >= minus[-border]:
                    count -= 1
            
            border = 0
            for v in plus:
                while border < len(plus) and v * plus[-border-1] > value:
                    border += 1
                count += len(plus) - border
                if border < len(plus) and v <= plus[-border-1]:
                    count -= 1

            count //= 2
            count += count_default

            if count >= k:
                r = value
            else:
                l = value
        ans = r
        
    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
input = sys.stdin.readline

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

    minus, plus, zero = [], [], 0
    for i in range(n):
        if a[i] < 0:
            minus.append(a[i])
        elif a[i] > 0:
            plus.append(a[i])
        else:
            zero += 1
    
    minus_count = len(minus) * len(plus)
    zero_count = zero * (zero - 1) // 2 + zero * (len(minus) + len(plus))

    minus.sort()
    plus.sort()

    if k <= minus_count:
        l, r = -int(1e18), 0
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            for v in minus:
                border = 0
                while border < len(plus) and v * plus[len(plus)-border-1] <= value:
                    border += 1 
                count += border

            if count >= k:
                r = value
            else:
                l = value

        ans = r

    elif k <= zero_count + minus_count:
        ans = 0
        
    else:
        l, r = 0, int(1e18)
        count_default = minus_count + zero_count
        while r-l > 1:
            value = (r + l) // 2
            count = 0
            
            border = 0
            for v in minus:
                while border < len(minus) and v * minus[-border-1] <= value:
                    border += 1
                count += border
                if border > 0 and v >= minus[-border]:
                    count -= 1
            
            border = 0
            for v in plus:
                while border < len(plus) and v * plus[-border-1] > value:
                    border += 1
                count += len(plus) - border
                if border < len(plus) and v <= plus[-border-1]:
                    count -= 1

            count //= 2
            count += count_default

            if count >= k:
                r = value
            else:
                l = value
        ans = r

    print(ans)

    
if __name__ == "__main__":
    main()