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 bisect as bs
from decimal import Decimal
N, K = map(int,input().split())
a = sorted(list(map(int,input().split())))
INF = 10**18
l = -INF
r = INF
while (r - l > 1):
    mid = (l+r)//2
    cnt = 0
    for i in range(1,N):
        if a[i-1] < 0:
            cnt += N-i-bs.bisect_left(a[i:], Decimal(mid)/a[i-1])
        elif a[i-1] > 0:
            cnt += bs.bisect_right(a[i:], Decimal(mid)/a[i-1])
        else:
            if mid >= 0:
                cnt += N-i
    if cnt < K:
        l = mid
    else:
        r = mid
    print(l,r,mid)
    
for p in range(l+1, r+1):
    cnt = 0
    for i in range(1,N):
        if a[i-1] < 0:
            cnt += N-i-bs.bisect_left(a[i:], p/a[i-1])
        elif a[i-1] > 0:
            cnt += bs.bisect_right(a[i:], p/a[i-1])
        else:
            if p >= 0:
                cnt += N-i
    if K <= cnt:
        print(p)
        exit(0)

Submission status: Wrong Answer

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

B = []
for i in range(N):
  B = np.append(B,A[i+1:]*A[i])
B.sort()
print(int(B[K-1]))

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
def getlist2():
    return [int(x) * 100000 for x in input().split()]
import math
import bisect
import heapq
# from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15

def judge(nums, k, cand, n):
    ll, rr = 0,0
    for num in nums:
        if num == 0:
            if cand == 0:
                rr += n - 1
            elif cand > 0:
                ll += n - 1
                rr += n - 1
        else:
            l = bisect.bisect_left(nums, cand/num)
            r = bisect.bisect_right(nums, cand/num)
            if num > 0:
                if num < cand/num:
                    l -= 1
                if num <= cand/num:
                    r -= 1
                ll += l
                rr += r
            else:
                if num > cand/num:
                    r += 1
                if num >= cand/num:
                    l += 1
                ll += n - r
                rr += n - l
        # print(ll, rr, num)

    rr /= 2
    ll /= 2
    # print(ll, rr)
    if rr != ll and rr >= k and ll < k:
        return 0
    elif ll >= k:
        return -1
    else:
        return 1

"""
448283280358331113/834475626
10 46
5 4 3 2 -1 0 0 0 0 0
"""

def main():
    n, k = getlist()
    nums = getlist()
    nums.sort()
    mx = 10 ** 32
    mn = -(10 ** 32)
    while(mx - mn > 1):
        mid = (mx + mn) // 2
        # mid = 448283280358331064
        # print(mid)
        state = judge(nums, k, mid, n)
        if state == 0:
            print(mid)
            # print(mx, mn)
            return
        elif state == 1:
            mn = mid
        else:
            mx = mid
    # print(448283280358331064 / 537203564)
    # print("=====================")
    if judge(nums, k, mx, n) == 0:
        print(mx)
        return
    else:
        print(mn)
        return

if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
N,K = input().split()
N = int(N)
K = int(K)-1
A = input().split()

A1 = []
A2 = []
zeros = 0
for i in range(N):
    a = int(A[i])
    if a<0:
        A1.append(a)
    if a>0:
        A2.append(a)
    if a==0:
        zeros = zeros + 1

A1.sort()
A2.sort()
A2.reverse()

p1=0
p2=0
kt = 0
ktf = False

onaji = 0

while True:
#    print([A1,A2,p1,p2,K,len(A1),len(A2)])
    if p1==len(A1) or p2==len(A2):
        break
    elif p2>= len(A2) or p1 < len(A1) and -A1[p1]>A2[p2]:
        onaji = A1.count(A1[p1])        
        kohos = onaji * (len(A2) - p2)
        if K>=kohos:
            K = K - kohos
            p1 = p1 + onaji
            continue
        else:
            kt = A1[p1] * A2[p2+K//onaji] #
            ktf = True
            break
    elif p1>= len(A1) or -A1[p1]<A2[p2]:
        onaji = A2.count(A2[p2])        
        kohos = onaji*(len(A1) - p1)
        if K>=kohos:
            K = K - kohos
            p2 = p2 + onaji
            continue
        else:
            kt = A2[p2] * A1[p1+K//onaji]
            ktf = True
            break
    elif -A1[p1]==A2[p2]:
        o1 = A1.connt(A1[p1])
        o2 = A2.count(A2[p2])
        ayobi = A2[p2]
        koho12 = o1*o2
        if K>=koho12:
            K = K - koho12
            p1 = p1 + o1
            p2 = p2 + o2
        else:
            kt = ayobi * ayobi
            ktf = True
            break
        kohos = o2*(len(A1) - p1) + o1*(len(A2)-p2)
        if K>=kohos:
            K = K - kohos
            continue
        else:
            q1 = p1
            q2 = p2
            while True:
                if q2>= len(A2) or -A1[q1]>A2[q2]:
                    kohos = (len(A2) - q2)
                    if K>=kohos:
                        K = K - kohos
                        q1 = q1 + 1
                        continue
                    else:
                        kt = ayobi * A2[q2+K]
                        ktf = True
                        break
                elif q1>= len(A1) or -A1[q1]<A2[q2]:
                    onaji = A2.count(A2[q1])        
                    kohos = onaji*(len(A1) - q1)
                    if K>=kohos:
                        K = K - kohos
                        q2 = q2 + 1
                        continue
                    else:
                        kt = A2[q2] * A1[q1+K]
                        ktf = True
                        break
                else:
                    print("okasii")
                    break
            break
    else:
        break

if not ktf:
    kohos = zeros*(zeros-1)//2 + zeros * (len(A1)+len(A2))
    if K>=kohos:
        K = K - kohos
    else:
        kt = 0
        ktf = True

p1 =0
p2 =0

A1.reverse()
A2.reverse()

while True:
    if ktf:
        break
#    print([A1,A2,p1,p2,K,len(A1),len(A2)])

    if p2>= len(A2) or p1<len(A1) and -A1[p1]<A2[p2]:
        onaji = A1.count(A1[p1])
        ayobi = A1[p1]
        kohos = onaji*(onaji-1)//2
        if K>=kohos:
            K = K - kohos
            p1 = p1 + onaji
        else:
            kt = ayobi * ayobi
            ktf = True
            break
        kohos = onaji * (len(A1) - p1)
        if K>=kohos:
            K = K - kohos
            continue
        else:
            kt = ayobi * A1[p1+K] 
            ktf = True
            break
    elif p1>= len(A1) or -A1[p1]>A2[p2]:
        onaji = A2.count(A2[p2])
        ayobi = A2[p2]
        kohos = onaji*(onaji-1)//2
        if K>=kohos:
            K = K - kohos
            p2 = p2 + onaji
        else:
            kt = ayobi * ayobi
            ktf = True
            break
        kohos = onaji * (len(A2) - p2)
        if K>=kohos:
            K = K - kohos
            continue
        else:
            kt = ayobi * A2[p2+K] 
            ktf = True
            break
    elif -A1[p1]==A2[p2]:
        o1 = A1.connt(A1[p1])
        o2 = A2.count(A2[p2])
        ayobi = A2[p2]
        koho12 = o1*(o1-1)//2 + o2*(o2-1)//2
        if K>=koho12:
            K = K - koho12
            p1 = p1 + o1
            p2 = p2 + o2
        else:
            kt = ayobi * ayobi
            ktf = True
            break
        kohos = o1*(len(A1) - p1) + o2*(len(A2)-p2)
        if K>=kohos:
            K = K - kohos
            continue
        else:
            q1 = p1
            q2 = p2
            while True:
                if q2>= len(A2) or -A1[q1]>A2[q2]:
                    kohos = (len(A1) - q1)
                    if K>=kohos:
                        K = K - kohos
                        q1 = q1 + 1
                        continue
                    else:
                        kt = ayobi * A1[q1+K]
                        ktf = True
                        break
                elif q1>= len(A1) or -A1[q1]<A2[q2]:
                    kohos = (len(A2) - q2)
                    if K>=kohos:
                        K = K - kohos
                        q2 = q2 + 1
                        continue
                    else:
                        kt = ayobi * A2[q2+K]
                        ktf = True
                        break
                else:
                    print("okasii2")
                    break
            break
    else:
        break
        
print(kt)

Submission status: Wrong Answer

Solution code:
import sys, copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,K = MI()
	A = LI()
	A.sort()

	def bfm():
		start = 0
		end = len(A)
		mid = (end + start)//2
		while start < end - 1:
			mid = (end+start)//2
			if(A[mid] <= -1):
				start = mid
			else:
				end = mid
		return end

	def bf0():
		start = 0
		end = len(A)
		mid = (end + start)//2
		while start < end - 1:
			mid = (end+start)//2
			if(A[mid] <= 0):
				start = mid
			else:
				end = mid
		return end

	nom=bfm()
	if A[nom - 1] >= 0: nom-=1
	nou0=bf0()
	if A[nou0 - 1] != 0: nou0-=1
	ch = False
	for i,a in enumerate(A[:nom]):
		cnt = N-nou0
		if(cnt > K):
			print(a*A[N-nou0-K])
			ch=True
			break
		else:
			K-=cnt

	A.sort(key=lambda x: abs(x))
	if(ch!=True):
		for i,a in enumerate(A):
			if(a<0):
				cnt = max(nom - 1,0)
				nom-=1
			elif(a==0):
				cnt = N - (i+1)
			else:
				cnt = N - (i+1) - nom
			if(cnt >= K):
				for j in range(i+1,N):
					if(a<0 and A[j]<0):
						K-=1
					if(a>=0 and A[j]>=0):
						K-=1
					if(K==0):
						print(A[j]*a)
						ch=True
						break
				break
			else:
				K-=cnt




if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

k -= 1
cnt = [0] * 3

li_minus = []
li_zero = []
li_plus = []

a.sort()
for val in a:
    if val < 0:
        cnt[0] += 1
        li_minus.append(val)
    elif val > 0:
        cnt[2] += 1
        li_plus.append(val)
    else:
        cnt[1] += 1
        li_zero.append(val)
print(li_minus, li_zero, li_plus)
x, z, y = cnt

minus = x * y
zero = (2*n-z-1)*z//2
plus = (x-1)*x//2 + (y-1)*y//2

if k < minus:
    li = []
    li_ot = li_zero + li_plus
    for i in range(len(li_minus)):
        for j in range(len(li_ot)):
            li.append(li_minus[i] * li_ot[j])
    li.sort()
    print(li[k])
elif minus <= k+1 <= minus + zero:
    print(0)
else:
    li = []
    for i in range(len(li_minus)-1):
        for j in range(i+1, len(li_minus)):
            li.append(li_minus[i] * li_minus[j])
    for i in range(len(li_plus)-1):
        for j in range(i+1, len(li_plus)):
            li.append(li_plus[i] * li_plus[j])
    li.sort()
    s = n*(n-1)//2
    print(li[-(s-(k))])

Submission status: Wrong Answer

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

A.sort()

def count(m):
    res = 0
    for i in range(N):
        a = A[i]
        if a==0:
            if m>=0:
                res += N
        elif a>0:
            r = m/a
            j = bisect(A,r)
            res += j
        else:
            r = m/a
            j = bisect_left(A,r)
            res += N-j
        if a**2<=m:
            res -= 1
    res //= 2
    return res

def count1(m):
    res = 0
    cand = -10**19
    for i in range(N):
        a = A[i]
        if a==0:
            if m>=0:
                res += N
        elif a>0:
            r = m/a
            j = bisect(A,r)
            res += j
            if j!= 0:
                cand = max(cand,a*A[j-1])
        else:
            r = m/a
            j = bisect_left(A,r)
            res += N-j
            if j != N:
                cand = max(cand,a*A[j])
        if a**2<=m:
            res -= 1
    res //= 2
    return res,cand


l = -10**18
r = 10**18
m = (l+r)/2
for i in range(65):
    k = count(m)
    if k < K:
        l = m
    else:
        r = m
    m = (l+r)/2
k,ans = count1(r)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq


n, k = map(int, input().split())
order = n * (n - 1) / 2 / 2
if order - 1 > k:
    keisu = -1
else:
    keisu = 1

a = [int(x) for x in input().split()]
seki = []

for i in range(0, n - 1):
    ia = a[i]
    for j in a[i+1:]:
        seki.append(keisu * ia * j)
heapq.heapify(seki)
for i in range(k):
    ans = heapq.heappop(seki) * keisu

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,K = MI()
	A = LI()
	A.sort()

	def bfm():
		start = 0
		end = len(A)
		mid = (end + start)//2
		while start < end - 1:
			mid = (end+start)//2
			if(A[mid] <= -1):
				start = mid
			else:
				end = mid
		return end

	def bf0():
		start = 0
		end = len(A)
		mid = (end + start)//2
		while start < end - 1:
			mid = (end+start)//2
			if(A[mid] <= 0):
				start = mid
			else:
				end = mid
		return end

	nom=bfm()
	if A[nom - 1] >= 0: nom-=1
	nou0=bf0()
	if A[nou0 - 1] != 0: nou0-=1
	ch = False
	for i,a in enumerate(A[:nom]):
		cnt = N-nou0
		if(cnt > K):
			print(a*A[i+K])
			ch=True
			break
		else:
			K-=cnt

	A.sort(key=lambda x: abs(x))
	if(ch!=True):
		for i,a in enumerate(A):
			if(a<0):
				cnt = max(nom - 1,0)
				nom-=1
			elif(a==0):
				cnt = N - (i+1)
			else:
				cnt = N - (i+1) - nom
			if(cnt >= K):
				for j in range(i+1,N):
					if(a<0 and A[j]<0):
						K-=1
					if(a>=0 and A[j]>=0):
						K-=1
					if(K==0):
						print(A[j]*a)
						ch=True
						break
				break
			else:
				K-=cnt


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys, copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,K = MI()
	A = LI()
	A.sort()

	def bfm():
		start = 0
		end = len(A)
		mid = (end + start)//2
		while start < end - 1:
			mid = (end+start)//2
			if(A[mid] <= -1):
				start = mid
			else:
				end = mid
		return end

	def bf0():
		start = 0
		end = len(A)
		mid = (end + start)//2
		while start < end - 1:
			mid = (end+start)//2
			if(A[mid] <= 0):
				start = mid
			else:
				end = mid
		return end

	nom=bfm()
	if A[nom - 1] >= 0: nom-=1
	nou0=bf0()
	if A[nou0 - 1] != 0: nou0-=1
	ch = False
	print(nom, nou0)
	for i,a in enumerate(A[:nom]):
		cnt = N-nou0
		if(cnt > K):
			print(a*A[i+K])
			ch=True
			break
		else:
			K-=cnt
	A.sort(key=lambda x: abs(x))
	if(ch!=True):
		for i,a in enumerate(A):
			if(a<0):
				cnt = max(nom - 1,0)
				nom-=1
			elif(a==0):
				cnt = N - (i+1)
			else:
				cnt = N - (i+1) - nom
			if(cnt >= K):
				for j in range(i+1,N):
					if(a<0 and A[j]<0):
						K-=1
					if(a>=0 and A[j]>=0):
						K-=1
					if(K==0):
						print(A[j]*a)
						ch=True
						break
				break
			else:
				K-=cnt




if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import bisect


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

a.sort()
pos = bisect.bisect(a, 0)

def judge(cur):
    global n, k, a
    cnt, j = 0, 1
    for i in range(pos):
        while(j < len(a) and (i == j or a[i] * a[j] > cur)): j += 1
        if(j >= len(a)): break
        cnt += (len(a) - j)

    j = len(a) - 1
    for i in range(pos, len(a)):
        while(j > i and (i == j or a[i] * a[j] > cur)): j -= 1
        if(i >= j): break
        cnt += (j-i)

    if(cnt >= k): return True
    else: return False


l, r = int(-1e18), int(1e18)
while(l < r):
    m = (l+r)>>1
    if(judge(m)): r = m
    else: l = m + 1

print(r)

Submission status: Wrong Answer

Solution code:
import bisect


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

A.sort()

left = -10**18 - 1
right = 10**18 + 1

while left + 1 < right:
    num = (left + right) // 2
    count = 0
    for idx, a in enumerate(A):
        if a == 0:
            if num >= 0:
                count += n-idx-1
            else:
                pass
            continue

        pair = num / a
        if a > 0:
            smaller_idx = bisect.bisect_right(A, pair)
            pattern1 = max(smaller_idx-idx-1, 0)
            count += pattern1

        if a < 0:
            bigger_idx = bisect.bisect_left(A, pair)
            pattern2 = min(n-bigger_idx, n-idx-1)
            count += pattern2

    if count >= k:
        right = num
    else:
        left = num

print(right)

Submission status: Wrong Answer

Solution code:
def main():

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

    pos, neg, zero = [], [], []
    for v in A:
        if v < 0: neg.append(v)
        elif v == 0: zero.append(v)
        else: pos.append(v)

    if K <= len(pos) * len(neg):
        cand = []
        for i in range(len(pos)):
            for j in range(len(neg)):
                cand.append(pos[i] * neg[j])
        cand.sort()
        return cand[K-1]

    elif K <= len(pos) * len(neg) + (len(pos) + len(neg)) * len(zero) + len(zero) * (len(zero)  - 1)//2:
        return 0
    else:
        K -= len(pos) * len(neg) + (len(pos) + len(neg)) * len(zero)  + len(zero) * (len(zero)  - 1)//2
        cand = []
        for i in range(len(pos)):
            for j in range(i):
                cand.append(pos[i] * pos[j])
        for i in range(len(neg)):
            for j in range(i):
                cand.append(neg[i] * neg[j])
        cand.sort()
        print(cand)

        return cand[K-1]

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
def main():
  import sys
  import numpy as np

  sr = lambda: sys.stdin.readline().rstrip()
  ir = lambda: int(sr())
  lr = lambda: list(map(int, sr().split()))

  N, M = lr()
  A = np.array(lr())
  A.sort()
  Am=A[A<0]
  Az=A[A==0]
  Ap=A[A>0]
  l1=len(Az)
  l2=len(Am)

  def shake_cnt(x):
    X =np.searchsorted(Ap, x/Ap)
    print(X)
    Y =np.searchsorted(Am, -x/Am,side='right')
    if x<=0:
      ans=l1*N
    else:
      ans=0
    return N*(N-1)//2 - ans - X.sum() -l2+Y.sum()
      

  right = 10**6
  left = 0
  while right > left + 1:
      mid = (right+left) // 2
      if shake_cnt(mid) >= M:
        left = mid
      else:
        right = mid
  
  print(right)
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import os
import datetime

def main():
    a, b = map(int, input().split())
    val = list(map(lambda x: int(x), input().split()))

    print(val)

    result_dict = []

    for i in range(len(val)):
        for j in range(i+1, len(val)):
            result_dict.append(val[i] * val[j])

    min_list = sorted(result_dict)
    print(min_list[b-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

#read = sys.stdin.buffer.read
#input = sys.stdin.buffer.readline
#inputs = sys.stdin.buffer.readlines

import bisect

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	n,k=map(int,input().split())
	A=list(map(int,input().split()))
	A.sort()
	h=10**18
	l=-10**18
	x=0
	while l<h-1:
		x=(h+l)//2
		cnt=0
		for i in A:
			if i<0:
				cnt+=n-bisect.bisect_left(A,x/i)
				if i>=x/i:
					cnt-=1
			elif i>0:
				cnt+=bisect.bisect_right(A,x/i)
				if i<=x/i:
					cnt-=1
			else:
				if x>=0:
					cnt+=n-1
		cnt//=2
		if cnt<k:
			l=x
		else:
			h=x
		
	print(h)
	
	
	
	
	
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

arr.sort()

neg = []
pos = []

for i in arr:
	if i < 0:
		neg.append(i)
	else:
		pos.append(i)
neg.reverse()

arr = list(neg + pos)

beg = n - 1
count = 0
while k - beg > 0:
	count += 1
	k -= beg
	beg -= 1
	if beg == 0:
		break
print(arr[count] * arr[count + k])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
from bisect import bisect_left,bisect_right
mc=bisect_left(a,0)
pc=n-bisect_right(a,0)
zc=n-mc-pc
if pc*mc>=k:
  m=[]
  p=[]
  for i in a:
    if i<0:m.append(-i)
    elif i>0:p.append(i)
  m.sort()
  p.sort()
  if pc*mc==k:print(-m[0]*p[0]);exit()
  ng=10**19
  ok=0
  while ok+1!=ng:
    mid=(ok+ng)//2
    a=0
    for i in p:
      a+=bisect_right(m,mid//i)
    if a>k:ng=mid
    else:ok=mid
  a=0
  for i in p:
    a+=bisect_right(m,ok//i)
  if a!=mc*pc-k+1:print(-ng);exit()
  ans=10**19
  for i in p:
    j=bisect_right(m,ok//i)
    if j!=0:
      ans=min(ans,m[j-1]*i)
  print(-ans)
elif zc*(pc+mc)+pc*mc+zc*(zc-1)//2>=k:
  print(0)
  exit()
else:
  k-=zc*(pc+mc)+pc*mc+zc*(zc-1)//2
  m=[]
  p=[]
  for i in a:
    if i<0:m.append(-i)
    elif i>0:p.append(i)
  m.sort()
  p.sort()
  ng=10**19
  ok=0
  while ok+1!=ng:
    mid=(ok+ng)//2
    a=0
    for i in range(len(m)-1):
      a+=max(bisect_right(m,mid//m[i])-i,0)
    for i in range(len(p)-1):
      a+=max(bisect_right(p,mid//p[i])-i,0)
    if a>k:ng=mid
    else:ok=mid
  a=0
  for i in range(len(m)-1):
    a+=max(bisect_right(m,ok//m[i])-i-1,0)
  for i in range(len(p)-1):
    a+=max(bisect_right(p,ok//p[i])-i-1,0)
  if a!=k:print(ng);exit()
  ans=10**19
  for i in range(len(m)-1):
    j=bisect_right(m,ok//m[i])
    if i<j-1:
      ans=min(ans,m[j-1]*m[i])
  for i in range(len(p)-1):
    j=bisect_right(p,ok//p[i])
    if i<j-1:
      ans=min(ans,p[j-1]*p[i])
  print(ans)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log,ceil #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
# def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    A=LI()
    B=[-a for a in A]
    sort_A1 = sorted(A)
    # sort_A2 = sorted(A,reverse=True)

    def is_ok(x): #x以下の数がK個以下ならok
        cnt = 0
        for a in A:
            if a==0:
                if x<=0:
                    cnt += N-1
                continue
            need = x//a
            if need<0 and need!=x/a:
                need-=1
            if need>0 and need!=x/a:
                need+=1
            if a<0:
                cnt += N-bisect_right(sort_A1, need)
                if need<a:
                    cnt -= 1
            else:
                cnt += bisect_left(sort_A1, need)
                if need>a:
                    cnt -= 1
        cnt//=2
        return cnt <= K-1

    ok = -10**9
    ng =  10**9
    
    while abs(ng-ok)>1:
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    print(ng)        


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
List=list(map(int, input().split()))
List.sort()
print(List)
c=0
for idx in range(N):
    if (c+N-idx > K):
        print(List[idx] * List[K-c])
        break
    c+=N-idx

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
a_list = sorted(a_list, reverse=True)

ans = 0
count = 1
for i in range(N):
    for j in range(i+1, N):
        count = count + 1
        if count==K:
            ans = a_list[i]*a_list[j]

print(ans)

Submission status: Wrong Answer

Solution code:
def hersCode(l, r, n):
  ok = r
  ng = l
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(mid):
  ans = 0
  for i in M: 
    ans += nibutan(i, mid)
  return ans >= K

def nibutan(t, k):
  ok = len(P)
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if P[mid] * t >= k:
      ok = mid
    else:
      ng = mid
  return ok


def hersCode2(l, r, n):
  ok = r
  ng = l
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu2(mid):
  ans = 0
  for i in M: 
    ans += nibutan(i, mid)
  return ans >= K

def nibutan2(t, k):
  ok = len(P)
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if P[mid] * t >= k:
      ok = mid
    else:
      ng = mid
  return ok


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

A.sort()

M = []
P = []
for i in A:
  if i < 0:
    M.append(i)
  else:
    P.append(i)

T = len(M) * len(P)
if K < T:
  P.reverse()
  r = M[-1] * P[0]
  l = M[0] * P[-1]
  print(hersCode(l - 1, r, K))
else:
  K = K - T
  for i in range(len(M)):
    M[i] = -M[i]
  #maniauka------------------------------------------------------ibaka

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A1 = sorted(A)
A2 = sorted(A, key=lambda x: abs(x))
A3 = sorted(A, key=lambda x: -abs(x))
flg = True
while flg:
    if K < len(A1):
        x = A1[0]
        if x < 0:
            A3.remove(x)
            y = abs(A3.pop(K-1))
        else:
            A2.remove(x)
            y = A2.pop(K-1)
        print(x * y)
        flg = False
    else:
        target = A1[0]
        A1.remove(target)
        A2.remove(target)
        A3.remove(target)
        K = K - len(A1)

Submission status: Wrong Answer

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

B = []
for i in range(N):
  B = np.append(B,A[i+1:]*A[i])
B.sort()
print(B)
print(int(B[K-1]))

Submission status: Wrong Answer

Solution code:
N,K= map(int, input().split()) 
A = sorted(map(int, input().split())) 
M=A[0]*A[1]
C=0
for i in range(N):
  for j in range(1,N-i):
    C=C+1
    if C<=K:
      if A[i]*A[i+j]>=M:
        M=A[i]*A[i+j]
    if C==K:
      MK=M
    if C>K:
      if A[i]*A[i+j]<=MK:
        MK=A[i]*A[i+j]
          
print(MK)

Submission status: Wrong Answer

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

NG = []
ZERO = []
PS = []

for a in A:
    if a < 0:
        NG.append(a)
    elif a == 0:
        ZERO.append(a)
    else:
        PS.append(a)

NG = sorted(NG)
PS = sorted(PS)

k = 0
i = j = 0

nn = len(NG) * len(PS)
if len(ZERO) > 0:
    nz = len(ZERO) * len(NG) + len(ZERO) * (len(ZERO) - 1) // 2 + len(ZERO) * len(PS)
else:
    nz = 0
np = len(NG) * (len(NG) - 1) // 2 + len(PS) * (len(PS) - 1) // 2

assert(nn + nz + np == N * (N - 1) // 2)

if K <= nn:
    ni = 0
    pi = 0
    k = 1
    while True:
        if k == K:
            ans = NG[ni] * PS[pi]
            break
        if ni < len(NG) - 1:
            if -NG[ni + 1] < PS[pi]:
                ni += 1
                k += 1
                continue
        if pi < len(PS) - 1:
            pi += 1
            k += 1
            continue
    print(ans)
elif nn < K <= nn + nz:
    print(0)
else:
    C = []
    for i in range(len(NG) - 1):
        for j in range(i,len(NG)):
            C.append(NG[i] * NG[j])
    for i in range(len(PS) - 1):
        for j in range(i,len(PS)):
            C.append(PS[i] * PS[j])
    C = sorted(C)
    print(C[K - nn - nz - 1])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
plus = []
minus = []
zero = []
for x in a:
  if x > 0:
    plus.append(x)
  elif x == 0:
    zero.append(x)
  else:
    minus.append(-x)
p = len(plus)
m = len(minus)
z = len(zero)
plus.sort()
minus.sort()
if k <= p*m:
  pass
elif k <= n*(n-1)//2 - p*(p-1)//2 - m*(m-1)//2:
  print(0)
else:
  now = 0
  scale = 2**63
  import bisect
  while scale != 0:
    tmp = now + scale
    cnt = 0
    for i in range(p):
      targ = (tmp-1) // plus[i]
      b = bisect.bisect_right(plus,targ)
      cnt += min(b,i)
    for i in range(m):
      targ = (tmp-1) // minus[i]
      b = bisect.bisect_right(minus,targ)
      cnt += min(b,i)
    if cnt < k:
      now += scale
    scale //= 2
  print(now)