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: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x):
    ans = 0
    la, lb = len(a), len(b)
    J = (i for i in range(lb)) if a == b else (-1 for i in range(la))

    j = lb - 1
    for i, k in enumerate(J):
        xa = a[i]

        for j in range(j, k, -1):
            x1 = b[j] * xa
            if x1 <= x:
                break
        else:
            break
        ans += j - k

    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        #print(A[0], A[2])
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        #print((lo, hi), K1)
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid)
            #print((lo, hi), mid, k, K1)
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    #print(A[0], A[2], a0, a1, K3)
    lo, hi = 0, 10**18
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid) + cnt_val(A[2], A[2], mid)
        #print((lo, hi), k3, K3)
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
n,k=map(int,stdin.readline().split())
l=list(map(int,stdin.readline().split()))
l.sort()
def cntofproductlessthanx(x):
	ans=0
	for i in range(n):
		if l[i]>0:
			lo,hi=i+1,n-1
			idx=i
			while lo<=hi:
				mid=(lo+hi)//2
				p=l[i]*l[mid]
				if p<x:
					idx=mid
					lo=mid+1
				else:
					hi=mid-1
			ans+=idx-i
		elif l[i]==0:
			if x>0:
				ans+=n-i-1
		else:
			lo,hi=i+1,n-1
			idx=n
			while lo<=hi:
				mid=(lo+hi)//2
				p=l[i]*l[mid]
				if p<x:
					idx=mid
					hi=mid-1
				else:
					lo=mid+1
			ans+=n-idx
	return ans
lo,hi=-int(1e18),int(1e18)
ans=None
while lo<=hi:
	mid=(lo+hi)//2
	c=cntofproductlessthanx(mid)
	if c<k:
		ans=mid
		lo=mid+1
	else:
		hi=mid-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
n,k=map(int,stdin.readline().split())
l=list(map(int,stdin.readline().split()))
l.sort()
def cntofproductlessthanx(x):
	ans=0
	for i in range(n):
		if l[i]>0:
			lo,hi=i+1,n-1
			idx=i
			while lo<=hi:
				mid=(lo+hi)//2
				p=l[i]*l[mid]
				if p<x:
					idx=mid
					lo=mid+1
				else:
					hi=mid-1
			ans+=idx-i
		else:
			lo,hi=i+1,n-1
			idx=n
			while lo<=hi:
				mid=(lo+hi)//2
				p=l[i]*l[mid]
				if p<x:
					idx=mid
					hi=mid-1
				else:
					lo=mid+1
			ans+=n-idx
	return ans
lo,hi=-int(1e18),int(1e18)
ans=None
while lo<=hi:
	mid=(lo+hi)//2
	c=cntofproductlessthanx(mid)
	if c<k:
		ans=mid
		lo=mid+1
	else:
		hi=mid-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
def cntofproductlessthanx(x):
	ans=0
	for i in range(n):
		if l[i]>0:
			lo,hi=i+1,n-1
			idx=i
			while lo<=hi:
				mid=(lo+hi)//2
				p=l[i]*l[mid]
				if p<x:
					idx=mid
					lo=mid+1
				else:
					hi=mid-1
			ans+=idx-i
		else:
			lo,hi=i+1,n-1
			idx=n
			while lo<=hi:
				mid=(lo+hi)//2
				p=l[i]*l[mid]
				if p<x:
					idx=mid
					hi=mid-1
				else:
					lo=mid+1
			ans+=n-idx
	return ans
lo,hi=-int(1e19),int(1e19)
ans=None
while lo<=hi:
	mid=(lo+hi)//2
	c=cntofproductlessthanx(mid)
	if c<k:
		ans=mid
		lo=mid+1
	else:
		hi=mid-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#標準入力からの値取得(N)
N, K = (int(x) for x in input().split())
TMP = [int(x) for x in input().split()]
#List:TMPから、値が0の要素を取り出して別Listに格納する
A = []
Z = 0
for row in TMP:
  if row == 0:
    Z += 1
  else:
    A.append(row)
#計算本体処理
ans = []
for i in range(0,len(A)-1):
  for j in range(i+1,len(A)):
    ans.append( A[i] * A[j] )
#0を突っ込む処理
ZC = ((N*(N-1))/2) - ((len(A)*(len(A)-1)/2))
for i in range(0, int(ZC) ):
  ans.append(0)
ans.sort()
print(ans[K-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x, cache):
    ai = 1 if a == b else 0
    ans = 0

    la, lb = len(a), len(b)

    for i in range(len(a) - ai):
        xa = a[i]

        lo = i + 1 if ai else 0

        cnt = 0
        for lo in range(lo, lb):
            x1 = b[lo] * xa
            #print(i, lo, x1)
            if x1 > x:
                break
            cnt += 1
        #print("x", (i, cnt, ai), x)
        ans += cnt

    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        #print(A[0], A[2])
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        cache1 = []
        #print((lo, hi), K1)
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid, cache1)
            #print((lo, hi), mid, k, K1)
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    #print(A[0], A[2], a0, a1, K3)
    lo, hi = 0, 10**18
    cache1, cache2 = [], []
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid, cache1) + cnt_val(A[2], A[2], mid, cache2)
        #print((lo, hi), k3, K3)
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
 
import numpy as np
 
A = np.array(A)
A.sort()
 
zero = list(A[A==0])
pos = list(A[A>0])
neg = list(A[A<0])
 
import bisect
 
#条件に合うものを重複して数えて後から重複しない組み合わせに変換
def fun(x):
    count = 0
    #xが0より大きいとき、後ろにある0は何個あるか
    if x >= 0:
        count += len(zero)*N
    #xを正で割ったとき、Aの中に何個それより大きいものがあるか
    for i in range(len(pos)):
        count += A.searchsorted(x//pos[i],side="right")
    #xを負で割ったとき、Aの中に何個それより小さいものがあるか(符合が逆転)
    #x+1にする(同じ数字がAにあるから)
    for i in range(len(neg)):
        count += (N - A.searchsorted((x+1)//neg[i],side="right"))
    #条件に合う同じ要素を選ぶものを除く    
    for i in range(len(A)):
        if x >= A[i]**2:
            count-=1
    #半分にすれば重複しない組み合わせになる        
    return count//2
 
left = -10**18
right = 10**18
 
#二分探索する
while right - left > 1:
    mid = (left+right)//2
    
    if fun(mid) >= K:
        right = mid
    else:
        left = mid
        
print(right)

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x, cache):
    ai = 1 if a == b else 0
    ans = 0

    la, lb = len(a), len(b)
    if len(cache) == 0:
        loa = [0] * la
        hia = [lb] * la
        mia = [0] * la

        cache.append([-inf, loa])
        cache.append([x, mia])
        cache.append([inf, hia])
    else:
        if x < cache[1][0]:
            cache[1], cache[2] = cache[2], cache[1]
        else:
            cache[0] ,cache[1] = cache[1], cache[0]

        cache[1][0] = x

        loa = cache[0][1]
        mia = cache[1][1]

    for i in range(len(a) - ai):
        xa = a[i]

        lo = i + 1 if ai else 0

        cnt = loa[i]
        for lo in range(lo+cnt, lb):
            x1 = b[lo] * xa
            #print(i, lo, x1)
            if x1 > x:
                break
            cnt += 1
        #print("x", (i, cnt, ai), x)
        mia[i] = cnt
        ans += cnt

    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        #print(A[0], A[2])
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        cache1 = []
        #print((lo, hi), K1)
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid, cache1)
            #print((lo, hi), mid, k, K1)
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    #print(A[0], A[2], a0, a1, K3)
    lo, hi = 0, 10**18
    cache1, cache2 = [], []
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid, cache1) + cnt_val(A[2], A[2], mid, cache2)
        #print((lo, hi), k3, K3)
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#標準入力からの値取得(N)
N, K = (int(x) for x in input().split())
A = [int(x) for x in input().split()]
#全探索して組合せ結果をlist:ansにため込む
ans = []
for i in range(0,N-1):
  for j in range(i+1,N):
    ans.append( A[i] * A[j] )
ans.sort()
print(ans[K-1])

Submission status: Time Limit Exceeded

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

pairs = [A[i] * A[j] for i in range(N) for j in range(i + 1, N)]
print(sorted(pairs)[K - 1])

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x, cache):
    ai = 1 if a == b else 0
    ans = 0

    la, lb = len(a), len(b)
    if len(cache) == 0:
        loa = [i+1 for i in range(la-1)] if ai else [0] * la
        hia = [lb] * la
        mia = [0] * la

        cache.append([-inf, loa])
        cache.append([x, mia])
        cache.append([inf, hia])
        ic = 1
    else:
        if x < cache[1][0]:
            cache[1], cache[2] = cache[2], cache[1]
        else:
            cache[0] ,cache[1] = cache[1], cache[0]

        cache[1][0] = x

        loa = cache[0][1]
        mia = cache[1][1]
        hia = cache[2][1]

    for i in range(len(a) - ai):
        xa = a[i]

        lo, hi = loa[i], hia[i]

        #print(ic, lo, hi)

        while lo < hi:
            mid = (lo + hi) // 2
            x1 = b[mid] * xa
            #print(i, (lo, hi), x1)

            if x1 <= x:
                lo = mid + 1
            else:
                hi = mid
        #print("x", (lo, lo0))
        mia[i] = lo
        ans += lo
        if ai:
            ans -= i + 1
    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        #print(A[0], A[2])
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        cache1 = []
        #print((lo, hi), K1)
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid, cache1)
            #print((lo, hi), mid, k, K1)
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    #print(A[0], A[2], a0, a1, K3)
    lo, hi = 0, 10**18
    cache1, cache2 = [], []
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid, cache1) + cnt_val(A[2], A[2], mid, cache2)
        #print((lo, hi), k3, K3)
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#!python3

from bisect import bisect
iim = lambda: map(int, input().rstrip().split())

inf = 10**18 + 1

def cnt_val(a, b, x, cache):
    ai = 1 if a == b else 0
    ans = 0

    la, lb = len(a), len(b)
    if len(cache) == 0:
        loa = [i+1 for i in range(la-1)] if ai else [0] * la
        hia = [lb]*la

        cache.append((-inf, loa))
        cache.append((inf, hia))
        ic = 1
    else:
        ic = bisect(cache, (x+1,))
        loa = cache[ic-1][1]
        hia = cache[ic][1]

    aa = [0] * len(a)
    for i in range(len(a) - ai):
        xa = a[i]

        lo, hi = loa[i], hia[i]

        #print(ic, lo, hi)

        while lo < hi:
            mid = (lo + hi) // 2
            x1 = b[mid] * xa
            #print(i, (lo, hi), x1)

            if x1 <= x:
                lo = mid + 1
            else:
                hi = mid
        #print("x", (lo, lo0))
        aa[i] = lo
        ans += lo
        if ai:
            ans -= i + 1
    cache.insert(ic, (x, aa))
    return ans

def resolve():
    N, K = iim()
    A = [[] for i in range(3)]
    for x in input().split():
        x = int(x)
        if x < 0:
            i = 0
        elif x == 0:
            i = 1
        else:
            i = 2

        A[i].append(x)

    a0 = len(A[0]) * len(A[2])
    s1 = len(A[1])
    a1 = s1 * (2*N - s1 -1) // 2
    K1 = K - 1

    if a0 < K1 < a0 + a1:
        print(0)
        return

    if K1 < a0:
        A[0].sort()
        A[2].sort(reverse=True)
        #print(A[0], A[2])
        lo, hi = A[0][0]*A[2][0], A[0][-1] * A[2][-1] + 1
        cache1 = []
        #print((lo, hi), K1)
        while lo < hi:
            mid = (lo + hi) // 2
            k = cnt_val(A[0], A[2], mid, cache1)
            #print((lo, hi), mid, k, K1)
            if k <= K1:
                lo = mid + 1
            else:
                hi = mid
        print(lo)
        return

    A0 = list(map(lambda x: -x, A[0]))
    A0.sort()
    A[2].sort()
    K3 = K - a0 - a1 - 1
    #print(A[0], A[2], a0, a1, K3)
    lo, hi = 0, 10**18
    cache1, cache2 = [], []
    while lo < hi:
        mid = (lo + hi) // 2
        k3 = cnt_val(A0, A0, mid, cache1) + cnt_val(A[2], A[2], mid, cache2)
        #print((lo, hi), k3, K3)
        if k3 <= K3:
            lo = mid + 1
        else:
            hi = mid
    print(lo)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

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

positive = [i for i in As if i > 0]
zero = [i for i in As if i == 0]
negative = [i for i in As if i < 0]

nega_area = int(len(positive) * len(negative))
zero_area = int((len(zero) * (len(positive)+len(negative))) + (len(zero)*(len(zero)-1)/2))

if k <= nega_area:
    nega_num = [i*j for i in positive for j in negative]
    print(sorted(nega_num)[k-1])
elif k <= nega_area + zero_area:
    print(0)
else:
    posi_num = []
    for i in range(len(positive)-1):
        for j in range(i+1,len(positive)):
            posi_num.append(positive[i]*positive[j])
    for i in range(len(negative)-1):
        for j in range(i+1,len(negative)):
            posi_num.append(negative[i]*negative[j])
    print(sorted(posi_num)[k-1-nega_area - zero_area])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += N-max(n+1, np.searchsorted(A, y, side='right'))
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += max(n+1, np.searchsorted(A, y, side='left')) - (n + 1)
        else:  # A[n]==0
            if x > 0:
                cnt += N - n - 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += N - bisect.bisect_right(A, y, lo=n + 1)
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += bisect.bisect_left(A, y, lo=n + 1) - (n + 1)
        else:  # A[n]==0
            if x > 0:
                cnt += N - n - 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += N - bisect.bisect_right(A, y, lo=n + 1)
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += bisect.bisect_left(A, y, lo=n + 1) - (n + 1)
        else:  # A[n]==0
            if x > 0:
                cnt += N - n - 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
max_A = max(A)
min_A = min(A)
inf = max(max_A**2, min_A**2, abs(max_A*min_A))
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def count_lower(A, x):
    # Aの要素のうちxより小さいものの個数
    return np.searchsorted(A, x, side='left')


def count_higher(A, x):
    # Aの要素のうちxより大きいものの個数
    return len(A)-np.searchsorted(A, x, side='right')


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += count_higher(A[n+1:], y)
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += count_lower(A[n+1:], y)
        else:
            if x > 0:
                cnt += N - n - 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10 ** 18 + 1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def count_lower(A, x):
    # Aの要素のうちxより小さいものの個数
    return bisect.bisect_left(A, x)


def count_higher(A, x):
    # Aの要素のうちxより大きいものの個数
    return len(A)-bisect.bisect_right(A, x)


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += count_higher(A[n+1:], y)
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += count_lower(A[n+1:], y)
        else:
            if x > 0:
                cnt += N - n - 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
max_A = max(A)
min_A = min(A)
inf = max(max_A**2, min_A**2, abs(max_A*min_A))
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)

Submission status: Time Limit Exceeded

Solution code:
import bisect

INF=10**18+5

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

def calc(x):
    # ある数A[i]との積がx未満となる相方の個数を数える
    num=0
    for i in range(N):
        if A[i]<0:
            l,r=-1,N # r is OK, l is NG: xxxxxooooo
            while l+1<r:
                c=(l+r)//2
                if A[c]*A[i]<x:
                    r=c
                else:
                    l=c
            num+=N-r
        else:
            l,r=-1,N # l is OK, r is NG: oooooxxxxx
            while l+1<r:
                c=(l+r)//2
                if A[c]*A[i]<x:
                    l=c
                else:
                    r=c
            num+=r
        if A[i]*A[i]<x:
            num-=1
    num=num//2
    return num<K

l=-INF
r=INF
while l+1<r:
    c=(l+r)//2
    if calc(c):
        l=c
    else:
        r=c
print(l)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def count_lower(A, x):
    # Aの要素のうちxより小さいものの個数
    return bisect.bisect_left(A, x)


def count_higher(A, x):
    # Aの要素のうちxより大きいものの個数
    return len(A)-bisect.bisect_right(A, x)


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += count_higher(A[n+1:], y)
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += count_lower(A[n+1:], y)
        else:
            if x > 0:
                cnt += N - n - 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10 ** 18 + 1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def dominus(t):
    r = len(plus)-1
    ans = 0
    for m in minus:
        while r>=0 and m*plus[r] >= -t:
            r -= 1
            if r<0:
                break
        ans += len(plus)-r-1
        #ddprint("m {} r {} pr {}".format(m,r,plus[r]))
    #ddprint("domin t {} ans {}".format(t,ans))
    return ans

def doplus(t):
    return doplus1(t,plus)+doplus1(t,minus)

def doplus1(t,b):
    ans = 0
    r = 0
    for i in range(len(b)-1,0,-1):
        p = b[i]
        r = min(r,i-1)
        while p*b[r] <= t:
            r += 1
            if r>=i:
                break
        ans += r
    #ddprint("p1 t {} b {} ans {}".format(t,b,ans))
    return ans

n,k = inm()
a = inl()
plus = []
minus = []
nzero = 0
for x in a:
    if x<0:
        minus.append(-x)
    elif x>0:
        plus.append(x)
    else:
        nzero += 1
minus.sort()
plus.sort()
kminus = len(plus)*len(minus)
kzero = (2*n-1-nzero)*nzero//2
kmz = kminus+kzero
ddprint("n {} k {}".format(n,k))
ddprint("minus")
ddprint(minus)
ddprint(plus)
if kminus<k<=kminus+kzero:
    print(0)
else:
    dom = (kminus>=k)
    if not dom:
        mn = 0
        mx = 10**19
        while mx>mn+1:
            mid = (mx+mn)//2
            v = doplus(mid)
            if v>=k-kmz:
                mx = mid
            else:
                mn = mid
            #ddprint("ploop mn {} mx {} mid {} v {} k {} kmz {}".format(mn,mx,mid,v,k,kmz))
    else:
        mx = 0
        mn = -10**19
        while mx>mn+1:
            mid = (mx+mn)//2
            v = dominus(mid)
            if v>=k:
                mx = mid
            else:
                mn = mid
            #ddprint("mn {} mx {} mid {} v {} k {}".format(mn,mx,mid,v,k))
    print(mx)

Submission status: Time Limit Exceeded

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

n,k = map(int,input().split())
*a, = map(int,input().split())
pairs=[]
for i,x in enumerate(a):
    pairs = pairs + [x*y for y in a[i+1:]]
pairs.sort()
print(pairs[k-1])

Submission status: Time Limit Exceeded

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

n,k = map(int,input().split())
*a, = map(int,input().split())
pairs=[]
for i,x in enumerate(a):
    for y in a[i+1:]:
        pairs.append(x*y)
pairs.sort()
print(pairs[k-1])

Submission status: Time Limit Exceeded

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

n,k = map(int,input().split())
a = list(map(int,input().split()))
pairs=[]
for i,x in enumerate(a):
    for y in a[i+1:]:
        pairs.append(x*y)
pairs.sort()
print(pairs[k-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            ret+=g2(pA,na,x)*2
    elif x==0:
        ret+=neg
        ret+=zzz
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        pR=len(pA)
        for pa in pA:
            ret+=g1_2(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    if L[-1]*n<=x: return len(L)
    l=0
    over=pR
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    pR=over
    return l+1

import bisect
def g1_2(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    if L[-1]*n<=x: return len(L)
    l=bisect.bisect_right(L,x//n,0,min(len(L)-1,pR))
    pR=l+1
    return l

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    if L[0]*n<=x: return len(L)
    under=-1
    r=pR
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    pR=r
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            ret+=g2(pA,na,x)*2
    elif x==0:
        ret+=neg
        ret+=zzz
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        pR=len(pA)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=pR
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    pR=over
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    global pR
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=pR
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    pR=r
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)