Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lm,2):
			if i == lm-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						cp -= 1
					else:
						count += 1
						cm += 1

				else:
					count += 1
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						cm += 1
					else:
						count += 1
						cp -= 1


				else:
					count += 1
					cm += 1
		elif cp != -1:
			cp -= 1
			count += 1
		elif cm != lm:
			cm += 1
			count += 1

		else:
			break
	if cm % 2 != 0:
		if cp == lp-1:
			cp -= 1
			cm -= 1

		else:
			if cp != -1 and cm != lm:
				if pra[cp+1] != 0: 
					cp += 1
					cm += 1
				elif pra[cp]/-mina[cm-1] <= -mina[cm]/pra[cp+1]:
					cp += 1
					cm += 1
				else:
					cp -= 1
					cm -= 1
			elif cp != -1:
				cp -= 1
				cm -= 1
			elif cm != lm:
				cp += 1
				cm += 1

		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		if i == cm-1:
			continue
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	ii = i
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod
	if ii == cm-1:
		ans *= mina[ii]
		ans %= mod

		
	print(ans)

Submission status: Runtime Error

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
if (len(pos) == 0 and k % 2 == 1) or n == k:
    ans = 1
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    min_num = 0
    good_num = 0
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = 0
        if i - 1 >= 0:
            m = abs(neg[i-1])
        if k-i-1 >= 0:
            m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans *= pos[i]
        ans %= mod
    print(ans % mod)

Submission status: Runtime Error

Solution code:
import sys

if(__name__ == "__main__"):

    N, K = map( int, input().strip().split() )
    divisor = 10**9+7
    list_a = list( map( int, input().strip().split() ) )
    multiplies = 1
    if(N==K):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
    else:
        list_a.sort()
        """
        解が負になるのはN>Kの時には
        正の項が1つもなく、Kが奇数の時
        """
        if(list_a[-1] < 0 and K % 2 != 0):
            """
            全て負の項
            list_a = [-5, -3, -1]のようにソートされている
            末尾の項から選んでいく
            """
            for i in range(K):
                multiplies = multiplies * list_a[N-1-i] % divisor
        elif(K==1):
            multiplies = list_a[N-1]
        else:
            left = 0
            right = N-1
            if(K%2!=0):
                multiplies = multiplies * list_a[right] % divisor
                right -= 1
            multiply_left = list_a[left] * list_a[left+1]
            multiply_right = list_a[right] * list_a[right-1]

            for s in range(K//2):
                if(multiply_left < multiply_right):
                    multiply_right %= divisor
                    multiplies = multiplies * multiply_right % divisor
                    right -= 2
                    multiply_right = list_a[right] * list_a[right-1]

                else:
                    multiply_left%=divisor
                    multiplies = multiplies * multiply_left % divisor
                    left += 2
                    multiply_left = list_a[left] * list_a[left+1]


    print(multiplies)

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9 + 7

def prod(X):
    ans = 1
    for x in X:
        ans = ans * x % M
    return ans

def solve():
    # Case 1: N == K
    if N == K:
        return prod(A)

    # Case 2: ans is negative
    if all(a < 0 for a in A) and K % 2 == 1:
        return prod(sorted(A)[-K:])

    # Case 3: ans is positive
    posA = np.int64(sorted([a for a in A if a >= 0]))
    negA = np.int64(sorted([a for a in A if a < 0]))

    ans = 1
    if K % 2 == 1: # keep the largest positive
        ans = ans * posA[-1] % M
        posA = posA[:-1]
    
    pos_pairs = posA[0::2] * posA[1::2]
    neg_pairs = negA[0::2] * negA[1::2]
    pairs = np.concatenate([pos_pairs, neg_pairs], axis=0)
    pairs = np.sort(pairs)[-(K//2):].tolist()
    ans = ans * prod(pairs) % M
    return ans

print(solve())

Submission status: Runtime Error

Solution code:
PRIME = 10 ** 9 + 7

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

_a = sorted(a,key=abs,reverse=True)

ans = 1
if n == k:
  for i in range(k):
    ans = (ans * _a[i]) % PRIME
else:
  minus_n = 0
  minus_k = 0
  zero = 0
  min_minus = -1
  min_plus = -1
  max_minus = -1
  min_plus = -1
  
  for i in range(n):
    if _a[i] < 0:
      minus_n += 1
      if i < k:
        minus_k += 1
        min_minus = i
      elif max_minus < 0:
        max_minus = i
    elif _a[i] == 0:
      zero += 1
    elif i < k:
      min_plus = i
    elif max_plus < 0:
      max_plus = i
  
  if minus_n + zero == n and k % 2 == 1:
    for i in range(1, k + 1):
      ans = (ans * _a[-i]) % PRIME
  elif minus_k % 2 == 0:
    for i in range(k):
      ans = (ans * _a[i]) % PRIME
  elif max_minus < 0 or min_plus < 0 or (max_plus >= 0 and (max_minus < 0 or abs(a[max_minus] / a[min_plus]) < abs(a[max_plus] / a[min_minus]))):
    for i in range(k):
      if i != min_minus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_plus]) % PRIME
  else:
    for i in range(k):
      if i != min_plus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_minus]) % PRIME
    
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [ x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)


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

D = int(1E9 + 7)
r = 1

if K == N:
    for a in As:
        r = (r * (a % D)) % D
    print(r)

elif K % 2 == 1 and all(a < 0 for a in As):
    As = HeapQueue(As, "max")
    for k in range(K):
        a = As.pop()
        r = (r * (a % D)) % D
    print(r)

else:

    k = 0

    Ps = [a for a in As if a >= 0]
    Qs = [a for a in As if a < 0]

    Ps = HeapQueue(Ps, "max")
    Qs = HeapQueue(Qs, "min")

    while k < K:
    
        if len(Ps) == len(Qs) == 0:
            print(0)
            exit()

        elif (K - k) == 1:
            p = Ps.pop()
            r = (r * p) % D
            k += 1

        elif len(Ps) == 0:
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            r = (r * q) % D
            k += 2

        elif len(Qs) < 2:
            p = Ps.pop()
            r = (r * p) % D
            k += 1

        else:
            p1 = Ps.pop()
            p2 = Ps.pop()
            p  = p1 * p2
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            if p > q:
                r = (r * p1) % D
                Ps.push(p2)
                Qs.push(q1)
                Qs.push(q2)
                k += 1
            else:
                r = (r * q) % D
                Ps.push(p1)
                Ps.push(p2)
                k += 2

    print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Runtime Error

Solution code:
import math
ln,k=list(map(int,input().split()))
l=list(map(int,input().split()))
lul = 10**9 + 7

neg = set()
temp = []
for i in range(ln):
	if l[i]<0:
		l[i]*=-1
		temp.append(l[i])
		neg.add(i)
l.sort(); l=l[::-1]
v = 1; ct = 0
p = -1; n = -1
ans = []
temp.sort()
for i in range(k):
	ans.append(i)
	if i in neg:
		ct+=1
		n = max(n,i)
	else:
		p = max(n,i)
print(ct)
if ct%2!=0:
	for i in range(k,ln):
		if i in neg and p!=-1:
			ans.remove(p)
			ans.append(i)
			ct+=1
			break
		elif i not in neg:
			ans.remove(n)
			ans.append(i)
			ct-=1
			break

if ct%2!=0:
	v = 1
	for i in range(k):
		v = (v*temp[i])%lul
	v = lul-v
else:
	v = 1
	for i in ans:
		v = (v*l[i])%lul
print(v)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

plus_zero = []
minus = []

for i in a:
    if i >= 0:
        plus_zero.append(i)
    if i < 0:
        minus.append(-i)

from collections import deque

plus_zero = deque(sorted(plus_zero, reverse=True))
minus = deque(sorted(minus, reverse=True))
ans = []

# 負
if len(plus_zero) == 0 and (k % 2) != 0:
    for _ in range(k):
        ans.append(-minus.pop())
# 正 or 0
else:
    while len(ans) != k:
        if len(ans) == k-1:
            ans.append(plus_zero.popleft())
        else:
            if len(plus_zero) < 2:
                ans.append(minus.popleft())
                ans.append(minus.popleft())
                continue
            elif len(minus) < 2:
                ans.append(plus_zero.popleft())
                continue
            else:
                if (plus_zero[0] * plus_zero[1]) >= (minus[0] * minus[1]):
                    ans.append(plus_zero.popleft())
                else:
                    ans.append(minus.popleft())
                    ans.append(minus.popleft())
                continue

import functools
print(functools.reduce(lambda x, y: x * y, ans))

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
N, K = map(int, input().split())
*A, = map(int, input().split())

allm = True
for a in A:
    if a > 0:
        allm = False
        break

if N == K:
    ans = 1
    for a in A:
        ans = (ans*a) % MOD
    print(ans)
elif allm and K % 2 == 1:
    A.sort()
    A.reverse()
    ans = 1
    for a in A[:K]:
        ans = (ans*a) % MOD
    print(ans)
else:
    p, m = [], []
    for a in A:
        if a > 0:
            p.append(a)
        if a < 0:
            m.append(-a)
    p.sort(key=lambda k: -k)
    m.sort(key=lambda k: -k)

    pi, mi = 0, 0
    ans = 1
    while K > 0:
        if K == 1:
            ans = (ans*p[pi]) % MOD
            break
        elif pi < len(p)-1 or mi < len(m)-1:
            pv, mv = 0, 0
            if pi < len(p)-1:
                pv = p[pi]*p[pi+1]
            if mv < len(m)-1:
                mv = m[mi]*m[mi+1]

            if pv > mv:
                ans = (ans*pv) % MOD
                pi += 2
            else:
                ans = (ans*mv) % MOD
                mi += 2
            K -= 2
        else:
            ans = 0
            break
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop, heapify, heappush
mod = 10**9 + 7
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
plus = []
minus = []
zero = []
ans = []
for a in A:
    if a > 0:
        plus.append(-a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(a)
heapify(plus)
heapify(minus)
cnt = 0
last_minus = 0
last_plus = 0
if len(plus) + len(minus) < K:
    print(0)
    sys.exit()

if len(plus) == 0:
    if K%2 == 1:
        print(0)
        sys.exit()
    else:
        num = 1
        minus.sort()
        for x in minus[:K]:
            if x < 0:
                x = -x
            num *= x
            num %= mod
        print(num%mod)
        sys.exit()

if len(minus) == 0:
    num = 1
    plus.sort(reverse=True)
    for x in plus[:K]:
        if x < 0:
            x = -x
        num *= x
        num %= mod
    print(num%mod)
    sys.exit()

flag = 0

for i in range(K):
    if len(plus) > 0 and len(minus) > 0:
        a = heappop(plus)
        b = heappop(minus)
    elif len(plus) == 0:
        flag = 1
        break
    else:
        flag = 2
        break
    if a >= b:
        ans.append(b)
        heappush(plus, a)
        cnt += 1
        last_minus = b
    else:
        ans.append(a)
        heappush(minus, b)
        last_plus = a

if flag == 1:
    for i in range(K - len(ans)):
        a = heappop(minus)
        last_minus = a
        cnt += 1
        ans.append(a)

if flag == 2:
    for i in range(K - len(ans)):
        a = heappop(plus)
        last_plus = a
        ans.append(a)

if cnt%2 == 0:
    num = 1
    for a in ans:
        if a < 0:
            a = -a
        num = (num * a%mod)%mod
    print(num%mod)
else:
    num = 1
    ls = []
    for a in ans:
        if a < 0:
            ls.append(-a)
        else:
            ls.append(a)

    if len(plus) != 0 and len(minus) != 0:
        a = heappop(plus)
        b = heappop(minus)
        if a < 0:
            a = -a
        if b < 0:
            b = -b
        if last_minus < 0:
            last_minus = -last_minus
        if last_plus < 0:
            last_plus = -last_plus
        
        if last_plus == 0:
            for c in ls[:-1]:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
        if last_minus == 0:
            for c in ls[:-1]:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)

        if a *last_plus >= b*last_minus:
            ls.remove(last_minus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
        else:
            ls.remove(last_plus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)
    elif len(plus) == 0 and len(minus) == 0:
        print(0)
        sys.exit()
    elif len(plus) == 0:
        c = heappop(minus)
        if c < 0:
            c = -c
        if last_plus < 0:
            last_plus = -last_plus
        ls.remove(last_plus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)
    elif len(minus) == 0:
        c = heappop(plus)
        if c < 0:
            c = -c
        if last_minus < 0:
            last_minus = -last_minus
        ls.remove(last_minus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))

abs_a = [(abs(x), x) for x in a]

abs_a.sort(reverse=True)

negs = [-x for x in a if x < 0]
non_negs = [x for x in a if x >= 0]

if len(non_negs) == 0 and k % 2 == 1:
    negs.sort()
    ans = 1
    for i in range(k):
        ans = ans * -negs[i] % mod
    print(ans)
    exit()

negs_p, non_negs_p = 0, 0

negs.sort(reverse=True)
non_negs.sort(reverse=True)
for i in range(k):
    if negs_p == len(negs):
        non_negs_p += 1
    elif non_negs_p == len(non_negs):
        negs_p += 1
    elif negs[negs_p] > non_negs[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1

if negs_p % 2 == 0 or k == n:
    pass
elif negs_p == len(negs_p) or non_negs_p == 0:
    negs_p -= 1
    non_negs_p += 1
elif non_negs_p == len(negs_p) or negs_p == 0:
    non_negs_p -= 1
    negs_p += 1
else:
    a = negs[negs_p - 1]
    b = negs[negs_p]
    c = non_negs[non_negs_p - 1]
    d = non_negs[non_negs_p]
    
    if a * b > c * d:
        negs_p += 1
        non_negs_p -= 1
    else:
        negs_p -= 1
        non_negs_p += 1

ans = 1
for i in range(negs_p):
    ans = ans * -negs[i] % mod
for i in range(non_negs_p):
    ans = ans * non_negs[i] % mod
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if t:
        A = min(a[k:])
        B = max(a[k:])
        if A >= 0:
            ans *= pow(L, mod - 2, mod)
            ans *= B
        else:
            if A * L > B * R:
                ans *= pow(R, mod - 2, mod)
                ans *= A
            else:
                ans *= pow(L, mod - 2, mod)
                ans *= B
        print(ans % mod)
        
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
PRIME = 10 ** 9 + 7

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

_a = sorted(a,key=abs,reverse=True)

ans = 1
if n == k:
  for i in range(k):
    ans = (ans * _a[i]) % PRIME
else:
  minus_n = 0
  minus_k = 0
  zero = 0
  min_minus = -1
  min_plus = -1
  max_minus = -1
  min_plus = -1
  
  for i in range(n):
    if _a[i] < 0:
      minus_n += 1
      if i < k:
        minus_k += 1
        min_minus = i
      else:
        max_minus = i
    elif _a[i] == 0:
      zero += 1
    elif i < k and min_plus < 0:
      min_plus = i
    elif max_plus < 0:
      max_plus = i
  
  if minus_n + zero == n and k % 2 == 1:
    for i in range(1, k + 1):
      ans = (ans * _a[-i]) % PRIME
  elif minus_k % 2 == 0:
    for i in range(k):
      ans = (ans * _a[i]) % PRIME
  elif max_minus < 0 or min_plus < 0 or (max_plus >= 0 and (max_minus < 0 or abs(a[max_minus] / a[min_plus]) < abs(a[max_plus] / a[min_minus]))):
    for i in range(k):
      if i != min_minus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_plus]) % PRIME
  else:
    for i in range(k):
      if i != min_plus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_minus]) % PRIME
    
print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
N, K = map(int, input().split())
*A, = map(int, input().split())

allm = True
for a in A:
    if a > 0:
        allm = False
        break

if N == K:
    ans = 1
    for a in A:
        ans = (ans*a) % MOD
    print(ans)
elif allm and K % 2 == 1:
    A.sort()
    A.reverse()
    ans = 1
    for a in A[:K]:
        ans = (ans*a) % MOD
    print(ans)
else:
    p, m = [], []
    for a in A:
        if a > 0:
            p.append(a)
        if a < 0:
            m.append(-a)
    p.sort(key=lambda k: -k)
    m.sort(key=lambda k: -k)

    pi, mi = 0, 0
    ans = 1
    while K > 0:
        if K == 1:
            ans = (ans*p[pi]) % MOD
            break
        elif pi < len(p)-1 or mi < len(m)-1:
            pv, mv = 0, 0
            if pi < len(p)-1:
                pv = p[pi]*p[pi+1]
            if mv < len(m)-1:
                mv = m[mi]*m[mi+1]
            print(pv, mv)
            if pv > mv:
                ans = (ans*pv) % MOD
                pi += 2
            else:
                ans = (ans*mv) % MOD
                mi += 2
            K -= 2
        else:
            ans = 0
            break
    print(ans)

Submission status: Runtime Error

Solution code:
import random
from collections import deque
import sys
n,k =map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()
P=deque()
Q=deque()
is_zero = False
for a in A:
    if a<0:
        P.append(a)
    elif a>0:
        Q.appendleft(a)
    else:
        is_zero = True
c=0
S=1
lim = 10**9+7

if len(Q) == 0 and k&1:
    for _ in range(k):
        S*=P.pop()
        S%=lim
    if is_zero:
        print(0)
    else:
        print(S)
    sys.exit()
    
while c < k:
    if len(P)>1:
        p = P[0]*P[1]
    elif len(P)==1:
        p = 0
    else:
        p = 0
        
    if len(Q)>1:
        q = Q[0]*Q[1]
    elif len(Q)==1:
        q = Q[0]
    else:
        q = 0
    #print(P,Q,p,q)  
    if p and q:
        if p<q or c == k-1:
            S*= Q.popleft()
            S%= lim
            c+=1
        else:
            S*= P.popleft()
            S%= lim
            S*= P.popleft()
            S%= lim
            c+=2
    elif p and (not q):
        S*= P.popleft()
        S%= lim
        S*= P.popleft()
        S%= lim
        c+=2
    elif (not p) and q:
        S*= Q.popleft()
        S%= lim
        c+=1
    else:
        break
print(S)

Submission status: Runtime Error

Solution code:
import random
from collections import deque
import sys
n,k =map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()
P=deque()
Q=deque()
is_zero = False
for a in A:
    if a<0:
        P.append(a)
    elif a<0:
        Q.appendleft(a)
    else:
        is_zero=True
c=0
S=1
lim = 10**9+7

if len(Q) == 0 and k&1:
    for _ in range(k):
        S*=P.pop()
        S%=lim
    if is_zero:
        print(0)
    else:
        print(S)
    sys.exit()
    
while c < k:
    if len(P)>1:
        p = P[0]*P[1]
    elif len(P)==1:
        p = 0
    else:
        p = 0
        
    if len(Q)>1:
        q = Q[0]*Q[1]
    elif len(Q)==1:
        q = Q[0]
    else:
        q = 0
    #print(P,Q,p,q)  
    if p and q:
        if p<q or c == k-1:
            S*= Q.popleft()
            S%= lim
            c+=1
        else:
            S*= P.popleft()
            S%= lim
            S*= P.popleft()
            S%= lim
            c+=2
    elif p and (not q):
        S*= P.popleft()
        S%= lim
        S*= P.popleft()
        S%= lim
        c+=2
    elif (not p) and q:
        S*= Q.popleft()
        S%= lim
        c+=1
    else:
        break
print(S)

Submission status: Runtime Error

Solution code:
import math
ln,k=list(map(int,input().split()))
l=list(map(int,input().split()))
lul = 10**9 + 7

neg = set()
temp = []
for i in range(ln):
	if l[i]<0:
		l[i]*=-1
		temp.append(l[i])
		neg.add(i)
	else:
		l.append(l[i])
l.sort(); l=l[::-1]
v = 1; ct = 0
p = -1; n = -1
ans = []
temp.sort()
for i in range(k):
	ans.append(i)
	if i in neg:
		ct+=1
		n = max(n,i)
	else:
		p = max(n,i)
# print(ct)
if ct%2!=0:
	for i in range(k,ln):
		if i in neg and p!=-1:
			ans.remove(p)
			ans.append(i)
			ct+=1
			break
		elif i not in neg:
			ans.remove(n)
			ans.append(i)
			ct-=1
			break

if ct%2!=0:
	v = 1
	for i in range(k):
		v = (v*temp[i])%lul
	v = lul-v
else:
	v = 1
	for i in ans:
		v = (v*l[i])%lul
print(v)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]


def sgn(x):
    if x >= 0:
        return 0
    elif x < 0:
        return 1


pl = []
mn = []

for x in a:
    if x >= 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)


b = [(abs(a[i]), sgn(a[i])) for i in range(n)]
b = sorted(b, reverse=True)

c = [0, 0]
for i in range(k):
    c[b[i][1]] += 1


def solve(c):
    ans = 1
    for i in range(c[0]):
        ans *= pl[i]
        ans %= mod
    for i in range(c[1]):
        ans *= mn[i]
        ans %= mod
    return ans


if c[1] % 2 == 0:
    print(solve(c))
    exit()

if len(mn) == n and k % 2:
    tmp = 1
    for i in range(k):
        tmp *= mn[-i-1]
        tmp %= mod
    ans = -tmp
    print(ans % mod)
    exit()

ans = 0

chk1 = False
chk2 = False

if c[0] <= len(pl) - 1:
    chk1 = True

if 0 < c[0] and c[1] <= len(mn)-1:
    chk2 = True

if chk1 and chk2:
    tmp1 = pl[c[0]]*pl[c[0]-1]
    tmp2 = mn[c[1]]*mn[c[1]-1]
    if tmp1 > tmp2:
        c[0] += 1
        c[1] -= 1
        print(solve())
    else:
        c[0] -= 1
        c[1] += 1
        print(solve())
elif chk1:
    c[0] += 1
    c[1] -= 1
    print(solve())
elif chk2:
    c[0] -= 1
    c[1] += 1
    print(solve())
else:
    print(solve())

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9 + 7

def prod(X):
    ans = 1
    for x in X:
        ans = ans * x % M
    return ans

def solve():
    # Case 1: N == K
    if N == K:
        return prod(A)

    # Case 2: ans is negative
    if all(a < 0 for a in A) and K % 2 == 1:
        return prod(sorted(A)[-K:])

    # Case 3: ans is positive
    posA = np.int64(sorted([a for a in A if a >= 0]))
    negA = np.int64(sorted([a for a in A if a < 0]))

    ans = 1
    if K % 2 == 1: # keep the largest positive
        ans = ans * posA[-1] % M
        posA = posA[:-1]
    
    pos_pairs = posA[0::2] * posA[1::2]
    neg_pairs = negA[0::2] * negA[1::2]
    pairs = np.concatenate([pos_pairs, neg_pairs], axis=0)
    pairs = np.sort(pairs)[-K//2:].tolist()
    ans = ans * prod(pairs) % M
    return ans

print(solve())

Submission status: Runtime Error

Solution code:
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort()
        AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()

        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (p+1 <= len(AP) and AP[p]*AP[p+1] >= AM[m]*AM[m+1]) or (K - cnt) == 1:
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
            if m+1 <= len(AM):
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 

            if cnt == K:
                print(ans%mod)
                break