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:

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

A.sort()


def bisect(i,V):
    if A[i] > 0:
        l = 0
        r = N-1
        if A[i]*A[r]<V:
            return N
        if A[i]*A[l]>=V:
            return 0
        while r-l>1:
            if A[i]*A[(l+r)//2]<V:
                l = (l+r)//2
            else:
                r = (l+r)//2
        return l
    elif A[i]<0:
        l = 0
        r = N-1
        if A[i]*A[r]>=V:
            return 0
        if A[i]*A[l]<V:
            return N
        while r-l>1:
            if A[i]*A[(l+r)//2]>=V:
                l = (l+r)//2
            else:
                r = (l+r)//2
        return N-l
    else:
        if V>0:
            return N
        else:
            return 0

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

while r-l>1:
    count = 0
    for i in range(N):
        count+=bisect(i,(l+r)//2)
    if count//2>K:
        r = (l+r)//2
    else:
        l = (l+r)//2

print(l)

Submission status: Wrong Answer

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

A.sort()
ans = []
for i, v in enumerate(A[:-1]):
    for j in A[i+1:]:
        ans.append(v * j)
        if len(ans) > K:
            ans.sort()
            print(ans[K-1])
            exit()

Submission status: Wrong Answer

Solution code:
a,b =map(int,input().split())
c=sorted([int(x) for x in input().split()])
f=0
ok=False
while f<b:
    for i in range(len(c)-1):
        for i1 in range(1,len(c)-i):
            d=c[i]*c[i1+i]
            f+=1
            if f==b:
                ok=True
                break
        if ok:
            break
print(d)

Submission status: Wrong Answer

Solution code:
n, k  = map(int, input().split())
plst = []
mlst = []
zlst = []
lst = map(int,input().split())
lst = sorted(lst, key=int)
abslst = []

p = len(plst)
m = len(mlst)
z = len(zlst)
a = len(abslst)

if k <= p * m:
    h = k // p + 1
    w = k - (h -1) * p
    print(mlst[h-1] * plst[w-1])
elif k <= (p + m) * z:
    print(0)
else:
  print(0)

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
		ch = False
		while start < end - 1:
			mid = (end+start)//2
			if(A[mid] <= -1):
				start = mid
				ch = True
			else:
				end = mid

		if ch:
			return end
		else :
			return start

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

	nom=bfm()
	nou0=bf0()
	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:
[n, K]= map(int, input().rstrip().split(" "))
As = list(map(int, input().rstrip().split(" ")))

As.sort()

plus = []
zeros = []
minus = []

for num in As:
    if num > 0:
        plus.append(num)
    elif num == 0:
        zeros.append(num)
    else:
        minus.append(num)

plus.sort(reverse=True)
minus.sort()
k = 0
min = 0

for m in minus:
    for p in plus:
        min = m * p
        print(str(m) + " " + str(p) + " " + str(min))
        k += 1
        if k >= K:
            break

if k < K:
  for m in minus:
      for z in zeros:
          min = 0
          k += 1
          print(str(m) + " " + str(min) + " " + str(k))
          if k >= K:
              break
if k < K:
  for p in plus:
      for z in zeros:
          min = 0
          k += 1
          print(str(p) + " " +  str(min) + " " + str(k))
          if k >= K:
              break

if k < K:
    for i in range(len(zeros) - 1):
        j = i + 1
        while j < len(zeros):
            min = zeros[i] * zeros[j]
            k += 1
            print(k)
            j += 1
            if k >= K:
                break
        if k >= K:
            break

plus.sort()
if k < K:
    for i in range(len(plus)-1):
        j = i + 1
        while j < len(plus):
            min = plus[i] * plus[j]
            print(str(plus[i]) + " " + str(plus[j]) + " " + str(min) + " " + str(k))
            k += 1
            j += 1
            if k >= K:
                break
        if k >= K:
            break

print(min)

Submission status: Wrong Answer

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

neg = [abs(a) for a in a_list if a < 0]
pos = list(filter(lambda x: x >= 0, a_list))
neg.sort()
pos.sort()

neg_num = len(neg)
pos_num = len(pos)

if k <= neg_num * pos_num:
    # マイナス、大きい方からkばんめ
    result_list = []
    count = 0
    for num in neg:
        for p in pos:
            result_list.append(num*p)
        count += pos_num
        if count >= k:
            result_list.sort()
            print((-1)*result_list[-k])
            break 
else:
    # プラス、小さい方からk-(neg_num * pos_num)番目
    k = k - neg_num * pos_num
    result_list = []
    count = 0
    while len(neg) >= 1:
        num = neg[0]
        result_list.extend([num*x for x in neg[1:]])
        count += len(neg)-1
        neg = neg[1:]
        if count >= k:
            break
    while len(pos) >= 1:
        num = pos[0]
        result_list.extend([num*x for x in pos[1:]])
        count += len(pos)-1
        pos = pos[1:]
        if count >= k:
            break
    result_list.sort()
    print(result_list[k-1])

Submission status: Wrong Answer

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

list = []
head = 0

for i in range(len(a)):
    for j in range(i+1, len(a)):
        list.append(a[i] * a[j])
list.sort()
print(list)
print(list[k-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    A = np.array(A)

    res = np.array([])

    for i in range(N-1):
        temp = A[i] * A[i+1:]
        res = np.concatenate([res,temp])

    res = np.sort(res)

    print(int(res[K-1]))



main()

Submission status: Wrong Answer

Solution code:
import bisect

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

l = -(10 ** 18)
r = 10 ** 18
m = (l + r) // 2
while r - l > 1:
  cnt = 0
  for i in a:
    if i == 0:
      if m > 0:
        cnt += len(a) - 1
    else:
      if i >= 0:
        cnt += bisect.bisect_left(a, m / i)
#        if i ** 2 < m:
#          cnt -= 1
      else:
        cnt += len(a) - bisect.bisect_right(a, m / i) 
#        if i ** 2 > m:
#          cnt -= 1
  if cnt // 2 <= k - 1:
    l = m
  else:
    r = m
  m = (l + r) // 2
print(l)

Submission status: Wrong Answer

Solution code:
tmp = input().split()
N = int(tmp[0])
K = int(tmp[1])
A = list(map(int, input().split()))

A.sort()
# print(A)
ans = []
n = 0
for i in range(N - 1):
    # print(A[i])
    for j in range(N-1, i, -1):
        # print("\t"+str(A[j]))
        ans.append(A[i] * A[j])
        if not(A[i] < 0 and A[j] < 0):
            n += 1
        if n == K:
            break
    if n == K:
        break
ans.sort()
# print(ans)
print(ans[K-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N,K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    coord = bisect_left(A,0)
    A_left = A[:coord]
    A_right = A[coord:]
    num_left = len(A_left)
    num_right = len(A_right)
    kyoukaisen = num_left * num_right
    #print("A:",A)
    #print("coord:",coord)
    #print(kyoukaisen)
    if K <= kyoukaisen:
        i = K // num_right
        j = (N-1) - (K % num_right)
        return A[i] * A[j]
    else:
        K -= kyoukaisen
        A_left = list(map(abs, reversed(A_left)))
        #print("After K:",K)
        #print("l comb:", num_left * (num_left-1)//2)
        #print("r comb:", num_right * (num_right-1)//2)
        #print("leftk:", K//num_left)
        #print("rightk:", K//num_right)
        nidx_left = []
        nidx_right = []
        #print("New A_left", list(A_left))
        #print("New A_right", list(A_right))
        li,ri = 0,0
        for i in range(N):
            if li < num_left and ri < num_right:
                if A_left[li] < A_right[ri]:
                    nidx_right.append(i)
                    ri += 1
                else:
                    nidx_left.append(i)
                    li += 1
            elif li < num_left:
                nidx_left.append(i)
                li += 1
            else:
                nidx_right.append(i)
                ri += 1
        #print(nidx_left)
        #print(nidx_right)
        comb_left = combinations(nidx_left,2)
        comb_right = combinations(nidx_right,2)
        comb = list(comb_left) + list(comb_right)
        comb = sorted(comb)
        #print(comb)
        #print(comb[K-1])
        ans = 1
        try:
            ans *= A_left[nidx_left.index(comb[K-1][0])]
            ans *= A_left[nidx_left.index(comb[K-1][1])]
            #print("hoge")
        except:
            pass
        try:
            ans *= A_right[nidx_right.index(comb[K-1][0])]
            ans *= A_right[nidx_right.index(comb[K-1][1])]
            #print("fuga")
        except:
            pass
        return ans

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

Submission status: Wrong Answer

Solution code:
import itertools
import heapq

N,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
plus=[]
minus=[]
zeros=0
for a in A:
    if a>0:
        plus.append(a)
    elif a==0:
        zeros+=1
    else:
        minus.append(a)

q=[]
heapq.heapify(q)

if len(minus)*len(plus)>=K:
    minus=sorted(minus,reverse=True)[:max(K,2)]
    plus=sorted(plus)[:max(K,2)]
    for m in minus:
        for p in plus:
            heapq.heappush(q,m*p)
    for i in range(K):
        a=heapq.heappop(q)
    print(a)
else:
    K-=len(minus)*len(plus)
    zeros=zeros*(len(minus)+len(plus))+zeros*(zeros-1)//2
    if K<=zeros:
        print(0)
    else:
        K-=zeros
        minus=sorted(minus,reverse=True)[:max(K,2)]
        plus=sorted(plus)[:max(K,2)]
        for i in itertools.combinations(minus,2):
            heapq.heappush(q,i[0]*i[1])
        for i in itertools.combinations(plus,2):
            heapq.heappush(q,i[0]*i[1])
        for i in range(K):
            a=heapq.heappop(q)

        print(a)

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
		ch = False
		while start < end - 1:
			mid = (end+start)//2
			if(A[mid] <= -1):
				start = mid
				ch = True
			else:
				end = mid

		if ch:
			return end
		else :
			return 0

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

	nom=bfm()
	nou0=bf0()
	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:
n,k = map(int,input().split())
a = list(map(int,input().split()))

b = []
for i in range(n):
    for j in range(i+1,n):
        b.append(a[i]*a[j])
        
b = sorted(b)
print(b)
print(b[k-1])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
L = list(map(int, input().split()))
from itertools import product
L.sort()
#print(L)
L1 = [x for x in L if x > 0]
L1.sort(reverse = True)
L2 = [x for x in L if x<0]
L2.sort(reverse = True)
L3 = [x for x in L if x==0]
LL = L1+L3+L2

cnt = 0
for i in range(len(LL)//2):
    a = LL[i]*LL[-(i+1)]
    cnt +=1
    if cnt == k:
        print(a)
        exit()
    b = min(LL[i]*LL[-(i+2)],LL[i+1] * LL[-(i+1)])
    cnt +=1
    if cnt == k:
        print(b)
        exit()
    c = max(LL[i] * LL[-(i+2)],LL[i+1]*LL[-(i+1)])
    cnt +=1
    if cnt == k:
        print(c)
        exit()
    d = LL[i+1] *LL[-(i+2)]
    cnt +=1
    if cnt == k:
        print(d)
        exit()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import math


def count(mid, A, N):
    ret = 0
    for a in A:
        if a == 0:
            if mid >= 0:
                ret += N - 1
            continue
        if a >= 0:
            tmp = math.floor(mid / a)
            cnt = bisect_right(A, tmp)
            if a <= tmp:
                cnt -= 1
        else:
            tmp = math.ceil(mid / a)
            cnt = N - bisect_left(A, tmp)
            if tmp <= a:
                cnt -= 1
        ret += cnt
#        print(mid, a, cnt)
#    print(mid, ret//2)
    return ret // 2


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    lo = -int(10e18)
    hi = int(10e18)
    while lo < hi:
        mid = (lo + hi) // 2
        cnt = count(mid, A, N)
        if cnt < K:
            lo = mid + 1
        else:
            hi = mid
#        print(lo, hi)
    print(lo)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
N, K = list(map(int, input().split()))
A_N = list(map(int, input().split()))
B = []
b = 0
for i in range(N-1):
    for j in range(N-1):
        if i <= j:
            b = A_N[i] * A_N[j+1]
            B.append(b)
            b = 0
B = sorted(B)
print(B)
print(B[K-1])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
s = 0
for i in range(n):
    for j in range(i+1, n):
        s += 1
        if k == s:
            print(a[i] * a[j])
            break

Submission status: Wrong Answer

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

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

multi_list = []

for i in range(n):
    for j in range(i, n, 1):
        multi_list.append(num_list[i] * num_list[j])

print(sorted(multi_list)[k+1])

Submission status: Wrong Answer

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

#print(A)
count = 0
flag = 0
for i in range(len(A)):
    for j in reversed(range(i+1,len(A))):
        if(K+1 == count):
            print(A[i]*A[j])
            flag = 1
            break
        else:
            count += 1
    if(flag == 1):
        break

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()
neg,zer,pos=0,0,0
for a in A:
  if a<0:
    neg+=1
  elif a==0:
    zer+=1
  else:
    pos+=1
N,P=A[:neg],A[neg+zer:]
import bisect

a=neg*pos
b=a+zer*(neg+pos)+zer*(zer-1)//2

if k<=a:
  l,r=N[0]*P[-1],N[-1]*P[0]
  while r-l>1:
    mid=(l+r)//2
    ct=0
    for nn in N:
      nn=-nn
      x=(-mid)//nn
      ct+=pos-bisect.bisect_right(P,x)
    if ct>=k:
      r=mid
    else:
      l=mid
  print(r)
elif k<=b:
  print(0)
else:
  k-=b
  if N and P:
    l,r=min(N[-1]**2,P[0]**2),max(N[0]**2,P[-1]**2)
  elif P:
    l,r=P[0]**2,P[-1]**2
  else:
    l,r=N[0]**2,N[-1]**2
  while r-l>1:
    mid=(l+r)//2
    ct=0
    if N:
      for nn in N:
        nn=-nn
        x=mid//nn
        ct+=neg-bisect.bisect_left(N,-x)
        if nn**2<=mid:
          ct-=1
    if P:
      for pp in P:
        x=mid//pp
        ct+=bisect.bisect_right(P,x)
        if pp**2<=mid:
          ct-=1
    if ct>=2*k:
      r=mid
    else:
      l=mid
  print(r)

Submission status: Wrong Answer

Solution code:
import itertools

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

multis = []
max_value = 0
for combination in itertools.combinations(A, 2):
    if len(multis) <= K:
        multis.append(combination[0] * combination[1])
    else:
        m = combination[0] * combination[1]
        if m < max_value:
            multis.append(m)
            max_value = max(max_value, m)

result = sorted(multis)[K - 1]
print(result)

Submission status: Wrong Answer

Solution code:
from bisect import bisect, bisect_left


def check_neg(m, k, pos, neg, len_pos):
    less = 0
    for a in neg:
        d = m / a
        j = bisect(pos, d)
        less += len_pos - j
    return less < k


def check_pos(m, k, pos, neg, len_pos, len_neg):
    less = 0
    for i in range(len_pos):
        a = pos[i]
        d = m // a
        j = bisect(pos, d)
        less += max(0, j - i - 1)
    for i in range(len_neg):
        a = neg[i]
        d = m // a
        j = bisect(neg, d)
        less += max(0, j - i - 1)
    return less < k


def solve(n, k, aaa):
    pos = [a for a in aaa if a > 0]
    neg = [a for a in aaa if a < 0]
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg  # 負となるペア数
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg):
                l = m
            else:
                r = m
        return r


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(n, k, aaa))

Submission status: Wrong Answer

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

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

multi_list = []

for i in range(n):
    for j in range(i, n, 1):
        multi_list.append(num_list[i] * num_list[j])

print(sorted(multi_list)[k-1])

Submission status: Wrong Answer

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

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

MAX=max(abs(A[0]),abs(A[-1]))
OK=-MAX**2-1
NG=MAX**2+1

t=bisect.bisect_left(A,0)
u=N-bisect.bisect_right(A,0)
if t*u>K:
    NG=0
else:
    OK=0

while NG-OK>1:
    mid=(OK+NG)//2
    SC=0
    for i in range(N):
        if A[i]>0:
            x=bisect.bisect_left(A,-(-mid//A[i]))
            SC+=max(0,x-i-1)

        elif A[i]<0:
            x=bisect.bisect_right(A,mid//A[i])
            SC+=min(N-i-1,N-x)
        else:
            if mid>0:
                SC+=N-i-1
            else:
                SC+=0
                
        if SC>=K:
            NG=mid
            break
    else:
        OK=mid
        
print(OK)

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:], mid/a[i-1])
        elif a[i-1] > 0:
            cnt += bs.bisect_right(a[i:], mid/a[i-1])
        else:
            if mid >= 0:
                cnt += N-i
    if cnt < K:
        l = mid
    else:
        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())
A = list(map(int, input().split()))
M = [i for i in A if i < 0]
m = len(M)
Z = [i for i in A if i == 0]
z = len(Z)
P = [i for i in A if i > 0]
p = len(P)
 
B = []
D = 0
for i in range(z):
  D += N - i -1
 
if (K > m*p) and (K <= m*p + D):
  print(0)
  
if K < m*p:
  for i in range(len(M)):
    for j in range(len(P)):
   		 B.append(M[i]*P[j])
  b = sorted(B)
  print(b[K-1])

if K > m*p + D:
  for i in range(len(M)-1):
    for j in range(i+1,len(M)):
    	B.append(M[i]*M[j])
  for i in range(len(P)-1):
    for j in range(i+1,len(P)):
    	B.append(P[i]*P[j])
  b = sorted(B)
  print(b[K-1-m*p - D])

Submission status: Wrong Answer

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

nega=[]
posi=[]

if n*(n-1)/2>=k:
  for i in l:
    if i<0:
      nega.append(i)
    else:
      posi.append(i)
  nega.sort(reverse=True)
  posi.sort()
  
  stock1=[]
  stock2=[]
  for i in range(len(nega)):
    for j in range(len(posi)):
      stock1.append(nega[-i-1]*posi[-j-1])
  l1=len(stock1)
  if l1>=k:
    stock1.sort()
    print(stock1[k])
  else:
    for i in range(1,int(len(posi))):
      for j in range(i):
        stock2.append(posi[i]*posi[j])
    for i in range(1,int(len(nega))):
      for j in range(i):
        stock2.append(nega[i]*nega[j])
    stock2.sort()
    print(stock2[k-l1-1])

Submission status: Wrong Answer

Solution code:
n,K = map(int,input().split())

al = list(map(int,input().split()))
al = sorted(al)
p = min(al)
lb = min(al) * max(al) if p < 0 else min(al) * min(al)
ub = max(max(al) * max(al), min(al) * min(al))

import bisect
def ceil(a, b):
   return a // b + (a % b > 0)


while True:
    if ub == lb:
        print(ub)
        exit()
    target = (ub+lb) // 2
    tmp = 0
    for a in al:
        if a * a <= target:
            tmp -= 1
        if a == 0:
            if target >= 0:
                tmp += n
        elif a < 0:
            k = target // a  + 1
            idx = bisect.bisect_left(al, k)
            tmp += n - idx
        else:
            k = target // a
            idx = bisect.bisect_right(al, k)
            tmp += idx
    tmp = tmp // 2
    if tmp >= K:
        ub = target
    else:
        lb = target + 1

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
L = list(map(int, input().split()))
L2 = []
i = 0
while len(L2) < k+1:
    for j in range(i + 1,len(L)):
        L2.append(L[i] * L[j])
    i = i + 1
print(L2[k-1])

Submission status: Wrong Answer

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

pos = 0
answer = []
num = int(n*(n-1)/2)
if k < num/2:
    k = num-k
    select = min
    flag = True
else:
    select = max
    flag = False

for i, x in enumerate(a):
    for y in a[i+1:]:
        now = x*y
        if pos < k:
            answer += [now]
            pos += 1
        else:
            sel = select(answer)
            if (flag and now > sel) or (flag==False and now < sel):
                answer.remove(sel)
                answer += [now]
print(select(answer))

Submission status: Wrong Answer

Solution code:
import sys
import functools
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A_minus,A_zero,A_plus=[],[],[]
    x=bisect_left(A,0)
    y=bisect_right(A,0)
    A_minus=A[:x]
    A_zero=A[x:y]
    A_plus=A[y:]
    if K<=len(A_minus)*len(A_plus):
        def nibutan1(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve1(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        @functools.lru_cache()
        def solve1(mid):
            c=0
            for x in A_minus:
                c+=len(A_plus)-bisect_left(A_plus,-(-mid//x))
            if c>=K:
                return True
            else:
                return False
        
        print(nibutan1(0,A_minus[0]*A_plus[-1]+1))
    K-=len(A_minus)*len(A_plus)
    if 0<K<=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2:
        print(0)
    K-=len(A_zero)*(N-len(A_zero))+(len(A_zero)*(len(A_zero)-1))//2
    if K>0:
        def nibutan2(ok,ng):
            while abs(ok-ng) > 1:
                mid = (ok + ng) // 2
                if solve2(mid):
                    ok = mid
                else:
                    ng = mid
            return ok
        
        @functools.lru_cache()
        def solve2(mid):
            c=0
            for x in A_minus:
                c+=len(A_minus)-bisect_left(A_minus,-(-mid//x))
                if -(-mid//x)<=x:
                    c-=1
            for x in A_plus:
                c+=bisect_right(A_plus,(mid//x))
                if (mid//x)>=x:
                    c-=1
            c//=2
            if c>=K:
                return True
            else:
                return False
        z1,z2=0,0
        try:
            z1=A_minus[0]*A_minus[1]
        except:
            pass
        try:
            z2=A_plus[-1]*A_plus[-2]
        except:
            pass
        z=max(z1,z2)
        print(nibutan2(z+1,0))

    
        
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,K = map(int,input().split())

al = list(map(int,input().split()))
al = sorted(al)
p = min(al)
lb = min(al) * max(al) if p < 0 else min(al) * min(al)
ub = max(max(al) * max(al), min(al) * min(al))
import bisect
def ceil(a, b):
   return a // b + (a % b > 0)


while True:
    if ub == lb:
        print(ub)
        exit()
    target = (ub+lb) // 2
    tmp = 0
    for a in al:
        if a * a <= target:
            tmp -= 1
        if a == 0:
            if target >= 0:
                tmp += n
        elif a < 0:
            k = ceil(target,a) + 1
            idx = bisect.bisect_left(al, k)
            tmp += n - idx
        else:
            k = target // a
            idx = bisect.bisect_right(al, k)
            tmp += idx
    tmp = tmp // 2
    if tmp >= K:
        ub = target
    else:
        lb = target + 1

Submission status: Wrong Answer

Solution code:
from itertools import permutations, combinations

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

l.sort()

index = N
ans = 0

for i in range(N):
    if l[i] >= 0:
        index = i
        break
    
minus_num = index * (N-index)

cnt = 0
ans = 0
if minus_num >= K:
    for i in range(index):
        for k in range(N-index):
            cnt+=1
            if cnt == K:
                ans = l[i] * l[index + k]
else:
    l1 = l[:index]
    l2 = l[index:]
    l_ans=[]
    for i,k in list(combinations(l1,2)):
        l_ans.append(i*k)
    for i,k in list(combinations(l2,2)):
        l_ans.append(i*k)
    l_ans.sort()
    ans = (l_ans[K-minus_num-1])
    
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

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

combi = list(itertools.combinations(A,2))
combi = np.array(combi)
print(combi)

product_list = combi.prod(axis=1)
product_list = sorted(product_list)
print(product_list)

print("%d" % product_list[K-1])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a_p, a_0, a_n = [], [], []
for ai in a:
    if ai < 0:
        a_n.append(ai)
    elif ai == 0:
        a_0.append(ai)
    else:
        a_p.append(ai)
len_p, len_0, len_n = len(a_p), len(a_0), len(a_n)
if k <= len_p * len_n:
    b = [i*j for i in a_p for j in a_n]
    b.sort()
    ans = b[k - 1]
k -= len_p * len_n
if 0 < k <= len_0 * (len_p + len_n) + ((len_0 * (len_0 - 1)) // 2):
    ans = 0
k -= (len_0 * (len_p + len_n) + ((len_0 * (len_0 - 1)) // 2))
try:
    ans += 1
except NameError:
    a_pc = a_p.copy()
    if 2 <= len_p: 
        b_1 = [ a_p[i]*a_p[j]  for i in range(len_p) for j in range(i + 1, len_p)]
    else:
        b_1 = []
    if 2 <= len_n:
        b_2 = [ a_n[i]*a_n[j] for i in range(len_n) for j in range(i + 1, len_n)]
    else:
        b_2 = []
    b = b_1 + b_2
    b.sort()
    ans = b[k - 1]
print(ans)