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 = map(int, input().split())
numlist = [int(i) for i in input().split()]
for j in range(len(numlist)-1) :
    for k in range(j+1, len(numlist)) :
        numlist.append(numlist[j]*numlist[k])
numlist.sort()
print(numlist[k])

Submission status: Wrong Answer

Solution code:
import sys
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
        
        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
        
        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:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left,bisect_right

N,K = LI()
A = LI()

plus = []
minus = []
zeros = []
for i in range(N):
    if A[i]==0:
        zeros.append(0)
    elif A[i]>0:
        plus.append(A[i])
    else:
        minus.append(A[i])

plus.sort()
minus.sort()

nump = len(plus)*(len(plus)-1)//2 + len(minus)*(len(minus)-1)//2
num0 = len(zeros)*(len(zeros)-1)//2 + len(zeros)*(len(minus)+len(plus))
numm = len(minus)*len(plus)

if K <= numm:
    ok = -10**18-1
    ng = 0
    while abs(ok-ng)>1:
        now = 0
        for j in range(len(plus)):
            x = bisect_right(minus,ok/plus[j])
            now += x
        if now < K:
            ng = ok
            ok = ok//2
        else:
            ok = (ok+ng)//2
    print(ok)

elif K <= numm+num0:
    print(0)
    exit()
else:
    K = N*(N-1)//2 -K + 1
    ng = 0
    ok = 10**18+1
    while abs(ok-ng)>1:
        now = 0
        for j in range(len(plus)):
            x = bisect_left(plus,ok/plus[j])
            now += len(plus)-max(x,j+1)
        for j in range(len(minus)):
            x = bisect_right(minus,ok/minus[j])
            now += min(x,j)
        if now < K:
            ng = ok
            ok = ok//2
        else:
            ok = (ok+ng)//2
    print(ok)

Submission status: Wrong Answer

Solution code:
# Show me the WA
from bisect import bisect_right as br, bisect_left as bl

n, k = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())

pos = []
neg = []

for num in a:
    if num <= 0: neg.append(num)
    else: pos.append(num)

pos.sort()
neg.sort()

blocks = []
runner = []
for i in xrange(len(neg)):
    blocks.append(len(pos))
    runner.append(neg[i])

if k <= len(neg) * len(pos):
    sz = len(blocks)
    pre = [0] * (sz + 1)

    for i in xrange(1, sz + 1):
        pre[i] = pre[i - 1] + blocks[i - 1]

    idx = bl(pre, k)
    if pre[idx] == k:
        print runner[idx - 1] * pos[-1]
    else:
        diff = k - pre[idx - 1]
        print runner[idx - 1] * pos[diff - 1]

    exit()

k -= (len(neg) * len(pos))

for i in xrange(len(neg)): neg[i] = -neg[i]
neg.sort()

# binary search
lo, hi = 1, 10 ** 18
while lo < hi:
    mid = (lo + hi) / 2

    # if check(mid)
    # hi = mid
    # else
    # lo = mid + 1

    cur = 0
    for i in xrange(1, len(pos)):
        if pos[i] > mid: break
        y = mid / pos[i]
        cnt = br(pos, y)
        cnt = min(cnt, i)
        cur += cnt

    for i in xrange(1, len(neg)):
        if neg[i] > mid:
            break
        if neg[i] == 0:
            cur += i
            continue
        
        y = mid / neg[i]
        cnt = br(neg, y)
        cnt = min(cnt, i)
        cur += cnt

    if cur >= k: hi = mid
    else: lo = mid + 1

print lo

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

N, K = np.fromstring(input(), int, sep=" ")
As = np.fromstring(input(), np.int64, sep=" ")

# i, j = np.tril_indices(N, -1)
# print(sorted(As[i] * As[j])[K-1])


def count_combination(n):
    return n * (n - 1) // 2


pos = As[As > 0]
neg = As[As < 0]

n_pos = count_combination(len(pos)) + count_combination(len(neg))
n_neg = len(pos) * len(neg)
n_zero = count_combination(N) - (n_pos + n_neg)

print("debug")
sys.exit()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
a, *D, = [list(map(int, s.split())) for s in open(0)] 
D = D[0]
print(([D[i] * D[j] for i in range(len(D)) for j in range(i + 1, len(D))])[a[1] - 1])

Submission status: Wrong Answer

Solution code:
import bisect
n, k = map(int,input().split())
a = sorted(list(map(int,input().split())))
p = len(a) - bisect.bisect_right(a, 0)
m = bisect.bisect_left(a, 0)
z = a.count(0)
ans = []
if k <= p*m:
    for i in range(m):
        for j in range(p):
            ans.append(a[i]*a[m+z])
    print(sorted(ans)[k-1])
elif p*m < k <= (p+m)*z + z*(z-1)//2:
    print(0)
else:
    for i in range(m-1):
        for j in range(i+1, m):
            ans.append(a[i]*a[j])
    for i in range(p - 1):
        for j in range(i + 1, p):
            ans.append(a[i+m+z] * a[j+m+z])
    print(sorted(ans)[k-p*m-(p+m)*z - z*(z-1)//2-1])

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def run():
  N, K = map(int, input().split())
  As = list(map(int, input().split()))
  ans_li = []
  for A1, A2 in combinations(As, 2):
    ans_li.append(A1*A2)
  print(5)

if __name__ == '__main__':
  run()

Submission status: Wrong Answer

Solution code:
from sys import stdin
import itertools

def cmb(n, r):
    if n < 2: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result

if __name__ == '__main__':
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    A = [int(x) for x in stdin.readline().rstrip().split()]
    A = sorted(A)
    MINUS = [x for x in A if x < 0]
    ZERO = [x for x in A if x == 0]
    PLUS = [x for x in A if x > 0]
    # print(MINUS)
    # print(ZERO)
    # print(PLUS)

    num_minus = len(MINUS) * len(PLUS)
    num_zero = len(MINUS) * len(ZERO) + len(PLUS) * len(ZERO) + cmb(len(ZERO), 2)
    num_plus = cmb(len(PLUS), 2) + cmb(len(MINUS), 2)

    # print(num_minus)
    # print(num_zero)
    # print(num_plus)

    # print('ALL {}'.format(num_minus + num_zero + num_plus))

    if K <= num_minus:
        counter = len(PLUS)
        for i, m in enumerate(MINUS):
            if counter < K:
                counter += len(PLUS)
            else:
                index = counter - K
                print(m * PLUS[index])
    elif K <= num_minus + num_zero:
        print(0)
    else:
        index = K - num_minus - num_zero - 1
        a = list(itertools.combinations(PLUS, 2)) + list(itertools.combinations(MINUS, 2))
        a = sorted([c[0] * c[1] for c in a])
        print(a[index])

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()
	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
	Ac = copy.deepcopy(A)
	Ac.sort(key=lambda x: abs(x))
	if(ch!=True):
		for i,a in enumerate(Ac):
			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 Ac[j]<0):
						K-=1
					if(a>=0 and Ac[j]>=0):
						K-=1
					if(K==0):
						print(Ac[j]*a)
						ch=True
						break
				break
			else:
				K-=cnt




if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
NK = input().split()
N = int(NK[0])
K = int(NK[1])
 
AN = input().split()
AN = [int(a) for a in AN]
AN2 = [AN]*N
 
import numpy as np
AN = np.array([AN])
AN2 = np.array(AN2)
AN = AN.reshape(N,-1)
pro = AN * AN2
num = []
for i in range(N):
  for l in range(i+1):
      num.append(i*N+l)
pro2 = pro.flatten()
pro2 = np.delete(pro2, num,0)
pro2 = np.sort(pro2, kind='quick_sort')
print(len(pro2))
print(pro2[K-1])

Submission status: Wrong Answer

Solution code:
import math

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

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

    def combinations_count(n, r):
        if n < r:
            return 0
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    minus_num = len(plus) * len(minus)
    zeros_num = sum([len(A) - i - 1 for i in range(len(zeros))])
    plus_num = combinations_count(len(plus), 2) + combinations_count(len(minus), 2)

    if K <= minus_num:
        m_idx = K // len(minus)
        p_idx = K % len(minus)
        minus.sort(reverse=True)
        plus.sort(reverse=True)
        res = minus[m_idx - 1] * plus[p_idx - 1]
    elif K <= zeros_num:
        res = 0
    else:
        store = []
        for i in range(len(plus)):
            for j in range(i+1, len(plus)):
                store.append(plus[i] * plus[j])
        for i in range(len(minus)):
            for j in range(i+1, len(minus)):
                store.append(minus[i] * minus[j])
        store.sort()
        idx = K - (minus_num + zeros_num)
        res = store[idx - 1]        

    print(res)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

N, K = np.fromstring(input(), int, sep=" ")
As = np.fromstring(input(), np.int64, sep=" ")

print("debug")
sys.exit()

Submission status: Wrong Answer

Solution code:
import sys
import math
import bisect

def query_number_less_than_or_equal_to_k(A, B, cnt_zero, k):
    na = len(A)
    nb = len(B)
    ans = 0
    if 0 <= k:
        ans += cnt_zero * (na + nb)
    ans += cnt_zero * (cnt_zero - 1) // 2
    for i in range(na):
        first = i + 1
        last = bisect.bisect_right(A, k // A[i], lo = i + 1)
        ans += last - first
    for i in range(nb):
        first = i + 1
        last = bisect.bisect_right(B, k // B[i], lo = i + 1)
        ans += last - first
    for a in A:
        tmp = -k // a
        if -k % a:
            tmp += 1
        first = bisect.bisect_left(B, tmp)
        last = nb
        ans += last - first
    return ans

def solve(A, m):
    n = len(A)
    B = []
    C = []
    cnt_zero = 0
    for a in A:
        if a == 0:
            cnt_zero += 1
        elif a > 0:
            B.append(a)
        elif a < 0:
            C.append(-a)
    B.sort()
    C.sort()
    '''
    print('A: %s' % str(A))
    print('m: %d' % m)
    print('B: %s' % str(B))
    print('C: %s' % str(C))
    for i in range(-10, 0, 1):
        val = query_number_less_than_or_equal_to_k(B, C, cnt_zero, i)
        print('i: %d, val: %d' % (i, val))
    return -1
    '''
    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = (left + right) // 2
        val = query_number_less_than_or_equal_to_k(B, C, cnt_zero, mid)
        #print('left: %d, right: %d, mid: %d, val: %d' % (left, right, mid, val))
        if val >= m:
            right = mid
        else:
            left = mid
    return right

def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    ans = solve(A, m)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = [int(i) for i in input().split()]
As = sorted([int(i) for i in input().split()])
Ws = []
for i in range(N[0]-1):
  for j in range(i+1, N[0]):
    if len(Ws) > N[1] + 10:
      break
    Ws.append(As[i]*As[j])
print(sorted(Ws)[N[1]-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left,bisect_right

N,K = LI()
A = LI()

plus = []
minus = []
zeros = []
for i in range(N):
    if A[i]==0:
        zeros.append(0)
    elif A[i]>0:
        plus.append(A[i])
    else:
        minus.append(A[i])

plus.sort()
minus.sort()

nump = len(plus)*(len(plus)-1)//2 + len(minus)*(len(minus)-1)//2
num0 = len(zeros)*(len(zeros)-1)//2 + len(zeros)*(len(minus)+len(plus))
numm = len(minus)*len(plus)

if K <= numm:
    ok = -10**18-1
    ng = 0
    while abs(ok-ng)>1:
        now = 0
        for j in range(len(plus)):
            x = bisect_right(minus,ok/plus[j])
            now += x
        if now < K:
            ng = ok
            ok = ok//2
        else:
            ok = (ok+ng)//2
    print(ok)

elif K <= numm+num0:
    print(0)
    exit()
else:
    K = N*(N-1)//2 -K + 1
    ng = 0
    ok = 10**18+1
    while abs(ok-ng)>1:
        now = 0
        for j in range(len(plus)):
            x = bisect_left(plus,ok/plus[j])
            now += len(plus)-max(x,j+1)
        for j in range(len(minus)):
            x = bisect_right(minus,ok/minus[j])
            now += min(x,max(j-1,0))
        if now < K:
            ng = ok
            ok = ok//2
        else:
            ok = (ok+ng)//2
    print(ok)

Submission status: Wrong Answer

Solution code:
import itertools

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

P = itertools.permutations(AN, 2)

l = []

for p in P:
    l.append(p[0]*p[1])

l.sort()
print(l[K+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

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
            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())
b = []
for i in range(1):
    a = map(int , input().split())
a =list(a) 
for i in range(n):
    for j in range(i+1,n):
        b.append(a[i]*a[j])
sorted(b)
#print(b)
print(b[k-1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n,k = map(int, input().split())
a = list(map(int, input().split()))
plus = []
minus = []
z = 0
for ai in a:
    if ai == 0:
        z += 1
    elif ai < 0:
        minus.append(ai)
    else:
        plus.append(ai)
plus.sort()
minus.sort()
p = len(plus)
m = len(minus)
max_ = n*(n-1)//2

def check(mid):
    cnt = 0
    if mid == 0:
        return max_ - p*(p-1)//2 >= k
    elif mid > 0:
        cnt = p*m + z*(z-1)//2 + z*(p+m)
        cnt *= 2
        for ai in plus:
            x = mid//ai
            cnt += bisect_left(plus, x+1)
            if ai <= x:
                cnt -= 1
            if cnt//2 >= k:
                return True
        for ai in minus:
            x = -(-mid//ai)
            cnt += m - bisect_left(minus, x)
            if ai >= x:
                cnt -= 1
            if cnt//2 >= k:
                return True
        return False
    else:
        for ai in plus:
            x = mid//ai
            cnt += bisect_left(minus, x+1)
            if cnt >= k:
                return True
        return False

left = -10**20
right = 10**20
while right-left>1:
    mid = (right+left)//2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

import bisect
import math
def func(x):
    C = 0
    for p in l:
        if p > 0:
            q = math.ceil(x/p)
            j = bisect.bisect_left(l, q)
            C += n-j
            if p ** 2 >= x:
                C -= 1
        elif p < 0:
            q = int(x/p)
            j = bisect.bisect_right(l, q)
            #print(q, j)
            C += j
            if p ** 2 >= x:
                C -= 1
        else:
            if x <= 0:
                C += n-1
        #print(C)
    C = C//2
    return C

t = (n*(n-1))//2
l_ = -(10**9)*2 -1 # 満たす
r_ = (10**9)*2 +1 # 満たさない
while l_+1 < r_:
  c_ = (l_+r_)//2
  if func(c_) >= t-k+1:
    l_ = c_
  else:
    r_ = c_
print(l_)

Submission status: Wrong Answer

Solution code:
import sys 

envs_input = input()
envs = envs_input.split(' ')
nums = [int(a) for a in input().split(' ')]

# print(nums)
nums = sorted(nums,key=abs)
products = []
negative_products = []
positive_products = []
i = 0
j = 0
# print(nums)
for a in nums:
    for b in nums[int(i+1):]:
        product = int(a) * int(b)
        if product < 0:
            negative_products.append(product)
        else:
            positive_products.append(product)
        j += 1
    i += 1
# products_sorted = sorted(products)
negative_products_sorted = sorted(negative_products)
products = negative_products_sorted + positive_products
# print(products)
# print(products_sorted[int(envs[1])-1])
print(products[int(envs[1])-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

Aarray = np.array(A, dtype=float)

mul_list = []
for i in range(N):
    mul_list += list(Aarray[i] * Aarray[(i+1):])

ans = int(sorted(mul_list)[K-1])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import bisect

def query_number_less_than_or_equal_to_k(A, B, cnt_zero, k):
    na = len(A)
    nb = len(B)
    ans = 0
    if 0 <= k:
        ans += cnt_zero * (na + nb)
    ans += cnt_zero * (cnt_zero - 1) // 2
    for i in range(na):
        first = i + 1
        last = bisect.bisect_right(A, k // A[i], lo = i + 1)
        ans += last - first
    for i in range(nb):
        first = i + 1
        last = bisect.bisect_right(B, k // B[i], lo = i + 1)
        ans += last - first
    for a in A:
        first = bisect.bisect_left(B, math.ceil(-k/ a))
        last = nb
        ans += last - first
    return ans

def solve(A, m):
    n = len(A)
    B = []
    C = []
    cnt_zero = 0
    for a in A:
        if a == 0:
            cnt_zero += 1
        elif a > 0:
            B.append(a)
        elif a < 0:
            C.append(-a)
    B.sort()
    C.sort()
    '''
    print('A: %s' % str(A))
    print('m: %d' % m)
    print('B: %s' % str(B))
    print('C: %s' % str(C))
    for i in range(-10, 0, 1):
        val = query_number_less_than_or_equal_to_k(B, C, cnt_zero, i)
        print('i: %d, val: %d' % (i, val))
    return -1
    '''
    left = -10 ** 19
    right = 10 ** 19
    while right - left > 1:
        mid = (left + right) // 2
        val = query_number_less_than_or_equal_to_k(B, C, cnt_zero, mid)
        #print('left: %d, right: %d, mid: %d, val: %d' % (left, right, mid, val))
        if val >= m:
            right = mid
        else:
            left = mid
    return right

def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    ans = solve(A, m)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys 

envs_input = input()
envs = envs_input.split(' ')
nums = [int(a) for a in input().split(' ')]

# print(nums)
nums = sorted(nums,key=abs)
products = []
negative_products = []
positive_products = []
i = 0
j = 0
print(nums)
for a in nums:
    for b in nums[int(i+1):]:
        product = int(a) * int(b)
        if product < 0:
            negative_products.append(product)
        else:
            positive_products.append(product)
        j += 1
    i += 1
# products_sorted = sorted(products)
negative_products_sorted = sorted(negative_products)
products = negative_products_sorted + positive_products
print(products)
# print(products_sorted[int(envs[1])-1])
print(products[int(envs[1])-1])

Submission status: Wrong Answer

Solution code:
import itertools
N, K = map(int, input().split())
input_n = list(map(int, input().split()))
pair = itertools.combinations(input_n, 2)
print(pair)
res = [i[0] * i[1] for i in pair]
res.sort()
print(res[K-1])

Submission status: Wrong Answer

Solution code:
import platform
import numpy
import scipy

print('Python:', platform.python_version())
print('NumPy: ', numpy.__version__)
print('SciPy: ', scipy.__version__)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop


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

d = {}

h = []
for i in range(len(a)):
    if i == 0:
        heappush(h, (a[i] * a[0], i, 0, False))
    else:
        heappush(h, (a[i] * a[0], i, 0, True))


res = []
for _ in range(k):
    seki, i, j, flag = (0, 0, 0, 0)
    while True:
        seki, i, j, flag = heappop(h)
        if flag is True:
            break
    res.append(seki)
    if j+1 < len(a):
        if j+1 == i:
            pass
        else:
            heappush(h, (a[i] * a[j+1], i, j+1, True))

print(res[-1])

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:
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

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
            idx = bisect.bisect_right(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 = [int(x) for x in input().split()]
A_plus = []
A_minus = []
A_zero = []
for x in input().split():
    x = int(x)
    if x > 0:
        A_plus.append(x)
    if x == 0:
        A_zero.append(x)
    if x < 0:
        A_minus.append(x)

len_low = len(A_minus) * len(A_plus)
len_middle = len(A_zero) * (len(A_plus) + len(A_minus)) + (len(A_zero) * (len(A_zero) - 1) // 2)

if K <= len_low:
    A_plus = list(sorted(A_plus))
    A_minus = list(sorted(A_minus))
    multi = []
    for x in A_plus:
        for y in A_minus:
            multi.append(x * y)
    res = list(sorted(multi))[K-1]
elif len_low < K <= len_low + len_middle:
    res = 0
else:
    def get(lst):
        start = 0
        while start < len(lst)-1:
            x = lst[start]
            for y in lst[start+1:]:
                yield x * y
            start += 1

    multi = []
    for x in get(A_plus):
        multi.append(x)
    for y in get(A_minus):
        multi.append(x)

    k = K - (len_low + len_middle) - 1
    res = list(sorted(multi))[k]

print(res)

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]
A_plus = []
A_minus = []
A_zero = []
for x in input().split():
    x = int(x)
    if x > 0:
        A_plus.append(x)
    if x == 0:
        A_zero.append(x)
    if x < 0:
        A_minus.append(x)

len_low = len(A_minus) * len(A_plus)
len_middle = len(A_zero) * (len(A_plus) + len(A_minus)) + (len(A_zero) * (len(A_zero) - 1) // 2)

if K <= len_low:
    A_plus = list(sorted(A_plus))
    A_minus = list(sorted(A_minus))
    multi = []
    for x in A_plus:
        for y in A_minus:
            multi.append(x * y)
    res = list(sorted(multi))[K-1]
elif len_low < K <= len_low + len_middle:
    res = 0
else:
    def get(lst):
        start = 0
        while start < len(lst)-1:
            x = lst[start]
            for y in lst[start+1:]:
                yield x * y
            start += 1

    multi = []
    for x in get(A_plus):
        multi.append(x)
    for y in get(A_minus):
        multi.append(x)

    k = K - (len_low + len_middle) - 1
    print(K, k, multi)
    res = list(sorted(multi))[k]

print(res)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop


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

d = {}

h = []
for i in range(len(a)):
    if i == 0:
        heappush(h, (a[i] * a[0], i, 0, False))
    else:
        heappush(h, (a[i] * a[0], i, 0, True))


res = []
for _ in range(k):
    seki, i, j, flag = (0, 0, 0, 0)
    while True:
        seki, i, j, flag = heappop(h)
        if flag is True:
            break
    res.append(seki)
    if j+1 < len(a):
        if j+1 == i:
            heappush(h, (a[i] * a[j+1], i, j+1, False))
        else:
            heappush(h, (a[i] * a[j+1], i, j+1, True))

print(res[-1])

Submission status: Wrong Answer

Solution code:
N, K = [int(num) for num in input().split()]
A = [int(num) for num in input().split()]
C = []
for i, a1 in enumerate(A):
    for j, a2 in enumerate(A):
        if j <= i:
            continue
        C.append(a1 * a2)
sorted_C = sorted(C)
print(C[K-1])