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:
from collections import Counter, deque

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

MOD = 10 ** 9 + 7

c = Counter()
for a in A:
    if a == 0:
        c['0'] += 1
    elif a < 0:
        c['-'] += 1
    else:
        c['+'] += 1

if c['-'] + c['+'] < K:
    print(0)
elif (c['-'] == N and K % 2 == 1) or (N == K and c['-'] % 2 == 1):
    def f(x):
        if x == 0:
            return 10 ** 9
        else:
            return abs(x)


    A = sorted(A, key=f)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD

    print(ans)
else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    plus = deque()
    minus = deque()

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

    is_minus = False
    if len(minus) % 2 == 1:
        p = None
        m = None
        for i in range(K, N):
            if A[i] >= 0 and p is None:
                if len(plus) == 0:
                    plus.append(p)
                else:
                    p = A[i]
            if A[i] < 0 and m is None:
                m = A[i]
            if p is not None and m is not None:
                break
        if m is None and p is None:
            pass
        elif len(plus) == 0:
            is_minus = True

            # def f(x):
            #     if x == 0:
            #         return 10 ** 9
            #     else:
            #         return abs(x)

            # A = sorted(A, key=f)
            # ans = 1
            # for i in range(K):
            #     ans *= A[i]
            #     ans %= MOD

            # print(ans)
            print(0)
        elif m is None and p is not None:
            minus.pop()
            plus.append(p)
        elif m is not None and p is None:
            plus.pop()
            minus.append(m)
        elif minus[-1] * m > plus[-1] * p:
            plus.pop()
            minus.append(m)
        else:
            minus.pop()
            plus.append(p)

    ans = 1
    while plus:
        ans *= plus.popleft()
        ans %= MOD
    while minus:
        ans *= minus.popleft()
        ans %= MOD

    if not is_minus:
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7

    plus = []
    minus = []
    for a in A:
        if a >= 0:
            heapq.heappush(plus, -a)
        else:
            heapq.heappush(minus, a)

    ans = 1

    # 絶対マイナスになる場合
    if len(plus) < K - min((K - K % 2), (len(minus) - len(minus) % 2)):
        plus = []
        minus = []
        for a in A:
            if a >= 0:
                heapq.heappush(plus, a)
            else:
                heapq.heappush(minus, -a)

        while K > 0:
            if plus:
                x = plus[0]
            else:
                x = float("inf")

            if minus:
                y = -minus[0]
            else:
                y = float("inf")

            if abs(x) <= abs(y):
                ans *= x
                if plus:
                    heapq.heappop(plus)
            else:
                ans *= y
                if minus:
                    heapq.heappop(minus)

            ans %= MOD
            K -= 1

        print(ans)

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

        plusruiseki = [0]
        minusruiseki = [0]
        for i, v in enumerate(plus):
            if i == 0:
                plusruiseki.append(v)
            else:
                plusruiseki.append((plusruiseki[-1] * v) % MOD)

        for i, v in enumerate(minus):
            if i == 0:
                minusruiseki.append(v)
            else:
                minusruiseki.append((minusruiseki[-1] * v) % MOD)

        ans = 0
        for i in range(0, len(minus) + 1, 2):
            if i == 0:
                if K <= len(plusruiseki) - 1:
                    ans = max(ans, plusruiseki[K])
            else:
                if i > len(minusruiseki):
                    break

                if K - i > len(plusruiseki):
                    continue

                if K - i == 0:
                    ans = max(ans, minusruiseki[i])
                else:
                    ans = max(ans, minusruiseki[i] * plusruiseki[K - i])

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7
    As = [(abs(a), a<0) for a in A]
    As.sort()
    As = As[::-1]


    # 大きい順
    last_plus = None
    last_minus = None
    is_minus = False
    ans = 1
    for a, m in As[:K]:
        ans = (ans * a) % MOD
        is_minus ^= m
        if m:
            last_minus = a
        else:
            last_plus = a
    
    # print(As)
    # print(ans, is_minus)
    # print(last_minus, last_plus)
    # 絶対値の大きい順に選択して、答えが負のとき
    if is_minus:
        # 答えが負の場合はK番目以降の最も絶対値の大きい正負の数を探す
        next_plus = None
        next_minus = None
        for a, m in As[K:]:
            if m and next_minus == None:
                next_minus = a
            elif not m and next_plus == None:
                next_plus = a
        # print(next_minus, next_plus)
        # Aが負の数だけの場合
        if next_plus == None and next_plus == None:
            ans = 1
            for a, m in As[-K:]:
                ans = (ans * a) % MOD
            ans = MOD - ans
        elif next_plus == None:
            if last_plus == None:
                ans = 1
                for a, m in As[-K:]:
                    ans = (ans * a) % MOD
                ans = MOD - ans
            else:
                ans = (ans * modinv(last_plus)) % MOD
                ans = (ans * next_minus) % MOD
        elif next_minus == None:
            ans = (ans * modinv(last_minus)) % MOD
            ans = (ans * next_plus) % MOD
        else:
            a = last_plus * next_plus
            b = last_minus * next_minus
            if a > b:
                ans = (ans * modinv(last_minus)) % MOD
                ans = (ans * next_plus) % MOD
            else:
                ans = (ans * modinv(last_plus)) % MOD
                ans = (ans * next_minus) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
 
def findMaxProduct(arr, n, k) : 
	
	
	MaxProduct = 1
	for i in range(0, k) : 
		MaxProduct = MaxProduct * arr[i] 
		
	prev_product = MaxProduct 

	
	for i in range(1, n - k + 1) : 
		curr_product = (prev_product // arr[i-1]) * arr[i+k-1] 
		MaxProduct = max(MaxProduct, curr_product) 
		prev_product = curr_product 
	
	
	
	return MaxProduct 
	
# Driver code 
n,k=map(int,input().split())
lol=[int(n) for n in input().split()]
x=(findMaxProduct(lol, n, k))%1000000007 
print(x)

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)
min_num = -1
good_num = -1
if k % 2 == 1 and len(pos) == 0:
    ans = 1
    neg.sort(reverse = True)
    for i in range(k):
        ans *= neg[i]
        ans %= mod
    print(ans)
else:
    #最大化するとき
    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
sys.setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, K = ZZ()
    A = ZZ()
    p = []
    z = []
    m = []
    for a in A:
        if a > 0: p.append(a)
        elif a == 0: z.append(a)
        else: m.append(a)

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        return

    elif (len(p) == 0 and len(z) == 0 and K%2 == 1):
        m = sorted(m)[::-1]
        ans = 1
        for i in range(K):
            ans *= m[i]
            ans %= MOD
        print(ans)
        return

    else:
        if K - len(p) - len(m) > 0:
            print(0)
            return
        else:
            p.sort(reverse=True)
            m.sort()
            ans = 1
            itr = itrp = 0
            while K > 0:
                if itr+1 < len(m): c1 = (m[itr] * m[itr+1])
                else: c1 = 0
                if itrp+1 < len(p): c2 = (p[itrp] * p[itrp+1])
                else: c2 = 0

                if c1 > c2 and K >= 2:
                    ans *= c1
                    ans %= MOD
                    itr += 2
                    K -= 2
                else:
                    ans *= p[itrp]
                    ans %= MOD
                    itrp += 1
                    K -= 1
            print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heapify,heappush,heappop
N, K = map(int,input().split())
A = list(map(int, input().split()))
MOD =1_000_000_007

B = [a for a in A if a > 0]
C = [a for a in A if a<= 0]
B.sort()
C.sort(reverse = True)
ans = 1
if N == K:
  for a in A:
    ans *= a
    ans %= MOD
elif len(B) == 0 and K % 2 == 1:
  for i in range(K):
    ans *= C[i]
    ans %= MOD
else:
  if K % 2 == 1:
    ans *= B[-1]
    B.pop()
    K -= 1
  i = 0 
  j = 0
  k = 0
  while k < K:
    if len(C) < 2 or B[-1-j]*B[-2-j] > C[j] * C[j+1]:
      ans *= B[-1]*B[-2]
      ans %= MOD
      B.pop()
      B.pop()
    else:
      ans *= C[-1]*C[-2]
      ans %= MOD
      C.pop()
      C.pop()
    print(B,C)
    k += 2

print(ans)

Submission status: Runtime Error

Solution code:
def mult(lis):
  ret=1
  for i in lis:
    ret*=i
    ret%=1000000007
  return ret
n,k=map(int,input().split())
a=list(map(int,input().split()))
minus=[]
plus=[]
ch=[]
for i in a:
  if i<0:
    minus.append(i)
  else:
    plus.append(i)
if len(plus)==0 and k%2:
  minus.sort(reverse=True)
  ch.extend(minus[:k])
else:
  pls=True
  a.sort(key=lambda x: abs(x), reverse=True)
  while k>0:
    inp=a.pop()
    if inp<0:
      if k==1 and pls:
        continue
      pls^=1
    ch.append(inp)
    k-=1
print(mult(ch))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
po = sorted([ai for ai in a if ai > 0], reverse=True)
ne = sorted(ai for ai in a if ai < 0)
ze = 0 in a
mod = 10**9 + 7
c = 1
if len(po) == 0 or len(po) + len(ne) // 2 * 2 < k:
    if ze:
        print(0)
    else:
        for bi in sorted(po + ne, key=abs)[:k]:
            c = c * bi % mod
        print(c)
elif len(ne) < 2:
    for ai in sorted(a, reverse=True)[:k]:
        c = c * ai % mod
    print(c)
else:
    if len(po) >= k:
        pi = k - 1
        ni = -1
        pc = po[:k]
        nc = []
    else:
        if (k - len(po)) % 2:
            pi = len(po) - 2
            pc = po[:-1]
        else:
            pi = len(po) - 1
            pc = po
        ni = k - len(pc) - 1
        nc = ne[:k - len(pc)]
    for _ in range(len(pc) // 2):
        if ne[ni + 1] * ne[ni + 2] < po[pi - 1] * po[pi - 2]:
            break
        nc = nc + ne[ni + 1:ni + 3]
        pc = pc [:-2]
        ni += 2
        pi -= 2
    for pp in pc:
        c = c * pp % mod
    for nn in nc:
        c = c * nn % mod
    print(c)

Submission status: Runtime Error

Solution code:
import sys
from math import log2
from itertools import accumulate
from decimal import Decimal

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N, K = MAP()
A = LIST()

A1 = []
A2 = []
B1 = []
B2 = []
zero = 0
for a in A:
    if a > 0:
        A1.append(a)
        B1.append(Decimal(a).log10())
    elif a < 0:
        A2.append(-a)
        B2.append(log2(-a).log10())
    else:
        zero += 1

A1.sort()
A2.sort()
B1.sort()
B2.sort()
acc1 = [0] + list(accumulate(B1))
accrev1 = [0] + list(accumulate(B1[::-1]))
acc2 = [0] + list(accumulate(B2))
accrev2 = [0] + list(accumulate(B2[::-1]))
mx = -INF
mn = INF
idx1 = (-1, -1)
idx2 = (-1, -1)
for i in range(K+1):
    j = K - i
    if len(B1) < i or len(B2) < j:
        continue
    if j % 2 == 0:
        sm = accrev1[i] + accrev2[j]
        if sm > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn:
            mn = sm
            idx2 = (i, j)

if mx != -INF:
    ans = 1
    n, m = idx1
    A1.reverse()
    A2.reverse()
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)
elif zero:
    print(0)
else:
    ans = 1
    n, m = idx2
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

def L(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())

def anser(prod):
    print(prod%(10**9+7))
    exit()

def solver(N,K,A):
    #print(A)
    all_minus = False
    minus_count = sum( [1 if i<=0 else 0 for i in A] )
    if minus_count == len(A):
        _sort = sorted(A,reverse=True)
        all_minus = True
    else:
        _sort = sorted(A, key=lambda x: abs(x),reverse=True)

    #print(_sort)

    prod = 1
    last_idx = -1
    stack = []
    for i in range(K):
        stack.append(_sort[i])
        prod *= _sort[i]
        last_idx = i

    if prod >= 0 or all_minus:
        anser(prod)

    else:
        #print(last_idx)
        #print(stack, prod)
        bef_prod = prod

        for i in range(last_idx, N+1):
            if _sort[i] >= 0:
                continue

            prod = prod // _sort[i] * _sort[i+1]

            stack.pop()
            stack.append(_sort[last_idx+1])

            if prod >= 0:
                anser(prod)

        anser(bef_prod)


def main():

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

    solver(N,K,A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

if N - A.count(0) < K:
    print(0)
    exit(0)

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


ans = 1
if K % 2 == 1 and len(plus) == 0:
    minus.sort(reverse=True)
    for i in range(K):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit(0)

plus.sort(reverse=True)
minus.sort()

i = 0
j = 0

if K % 2 == 1 and len(plus) > 0:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
# 
import sys

from sys import stdin
input = lambda: stdin.readline().rstrip()


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

tl = []
for A in map(int,input().split()):
    tl.append((abs(A), A > 0))

tl.sort()
l = list(reversed(tl))

f = True
answer = 1
M = 10**9 + 7

last_Posi_idx = -1
last_Nega_idx = -1

answers = []
for i in range(K):
    A, F = l[i]
    answers.append(A)
    f = f == F
    if F:
        last_Posi_idx = i
    else:
        last_Nega_idx = i

# end with positive
if f:
    answer = 1
    for num in answers:
        answer = answer * num % M
    print(answer)
    exit()

alt_p_answer = -1
alt_n_answer = -1

alt_p = 'NOTFOUND'
alt_n = 'NOTFOUND'

# alt p
if last_Posi_idx > -1:
    for i in range(K,len(l)):
        A, F = l[i]
        if not F:
            alt_p = A
    if alt_p != 'NOTFOUND':
        alt_p_answer = 1
        for i in range(answers):
            num = answers[i] if i != last_Posi_idx else alt_p
            alt_p_answer = alt_p_answer * num % M

if last_Nega_idx > -1:
    for i in range(K,len(l)):
        A, F = l[i]
        if F:
            alt_n = A
    if alt_n != 'NOTFOUND':
        alt_n_answer = 1
        for i in range(answers):
            num = answers[i] if i != last_Posi_idx else alt_p
            alt_p_answer = alt_p_answer * num % M

if alt_p == alt_n:
    answer = 1
    for i in range(K):
        A, F = tl[i]
        f = 1 if F else -1
        answer = answer * A * f % M
    print(answer)
else:
    answer = max(alt_n_answer, alt_p_answer)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left,bisect_right
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
minus=bisect_left(a,0) #負の数の個数
plus=n-bisect_right(a,0) #正の数の個数
neg=a[:minus] #負の数(絶対値大きい順)
pog=a[n-plus::][::-1] #正の数(絶対値大きい順)
zer=n-plus-minus #ゼロの数
ans=1
poi=0
nei=0
flag=0
co=0
sgn=1
if plus==1:
  alartp=1
else:
  alartp=0
if minus==1:
  alartn=1
else:
  alartn=0
if plus==0:
  if zer!=0 and k%2==1:
    print(0)
  else:
    for i in range(k):
      ans=ans*neg[-1-i]%p
    print(ans)
elif plus+minus<k:
  print(0)
elif minus==0:
  for _ in range(k):
    ans=ans*pog[poi]%p
    poi+=1
  print(ans)
else:
  i=0
  while (i<k-2) and (not alartn) and (not alartp):
    i+=1
    if -neg[nei]>pog[poi]:
      ans=ans*neg[nei]%p
      sgn*=-1
      nei+=1
      if nei==minus-1:
        alartn=1
    else:
      ans=ans*pog[poi]%p
      poi+=1
      if poi==plus-1:
        alartp=1
  if alartn:
    if sgn==-1:
      ans=ans*neg[nei]%p
      i+=1
    for _ in range(k-i):
      ans=ans*pog[poi]%p
      poi+=1
  elif alartp==1:
    if (sgn==1 and (k-i)%2==1) or (sgn==-1 and (k-i)%2==0):
      ans=ans*pog[poi]
      i+=1
    for _ in range(k-i):
      ans=ans*neg[nei]
      nei+=1
  else:
    if sgn==1:
      a=max(pog[poi]*pog[poi+1],neg[nei]*neg[nei+1])
      ans=ans*a%p
    else:
      ans=ans*pog[poi]*neg[nei]%p
  print(ans)

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    print(0/0)
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    print(-ans % mod)
    exit()
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans%mod)
    exit()
if n==k:
    print(-ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

mod = int(10e8+7)

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

a_ = np.abs(a)
isN = (a!=a_).astype(int)

a = a[np.argsort(a_)[::-1]]
isN = isN[np.argsort(a_)[::-1]]
a_ = np.sort(a_)[::-1]

numN = np.sum(isN)
numP = n-numN

if k==1:
    print(np.max(a))
    sys.exit()

if np.sum(isN[:k])%2==0:
    ans = 1
    for i in range(k):
        ans *= a_[i]
        ans %= mod
    print(int(ans))
    sys.exit()

if not numP:
    ans = 1
    for i in range(1, k+1)[::-1]:
        ans *= -a_[-i]
        ans %= mod

    print(int(ans))
    sys.exit()

k = isP
maxN = 0
maxP = 0

for i in range(k, n):
    if isN[i]:
        maxN = i
        break

for i in range(k, n):
    if not isN[i]:
        maxP = i
        break

minN = n
minP = n

for i in range(k)[::-1]:
    if isN[i]:
        minN = i
        break

for i in range(k)[::-1]:
    if not isN[i]:
        minP = i
        break

ans_1 = 1

for i in range(k):
    if i == minP:
        if maxN:
            ans_1 *= a_[maxN]
            ans_1 %= mod
        continue

    ans_1 *= a_[i]
    ans_1 %= mod

ans_2 = 1

for i in range(k):
    if i == minN:
        if maxP:
            ans_2 *= a_[maxP]
            ans_2 %= mod
        continue

    ans_2 *= a_[i]
    ans_2 %= mod

print(int(max(ans_1, ans_2)))

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

p = []
m = []
for i in a:
    if i > 0:p.append(i)
    elif i < 0:p.append(i)

flag = 0
if len(p) < k:
    flag = 1
    p, m = m, p

p.sort(reverse=True)
m.sort()
double = []
    
for i in range(len(p) - 1):
    if i % 2 == 0:
        temp = p[i] * p[i + 1]
        double.append([temp, 1])
for i in range(len(m) - 1):
    if i % 2 == 0:
        temp = m[i] * m[i + 1]
        double.append([temp, 2])

if p[0] < 0:
    double.sort()
else:
    double.sort(reverse=True)

res = 1
p = deque(p)
m = deque(m)
double = deque(double)
while k:
    if double and k - 2 >= 0:
        temp, ind = double.popleft()
        if ind == 1:
            p.popleft()
            p.popleft()
        else:
            m.popleft()
            m.popleft()
        res = (res * temp) 
        k -= 2
    else:
        if not flag:
            if p:
                res = (res * p.popleft()) 
            else:
                res = (res * m.pop()) 
        else:
            if not m:
                res = (res * p.popleft())
            else:
                temp1 = m.popleft()
                temp2 = p.popleft()
                if temp1 <= -temp2:
                    res = (res * temp1)
                    p.appendleft(temp2)
                else:
                    res = (res * temp2)
                    m.appendleft(temp1)
        k -= 1
        
print(res%mod)

Submission status: Runtime Error

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

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(i)

ans = 1
if k > len(plus) + len(minus):
    ans = 0
elif len(minus) == 0:
    plus.sort(reverse=True)
    if k > len(plus):
        ans = 0
    else:
        for i in range(k):
            ans = (ans * plus[i]) % mod
elif len(plus) == 0:
    if k % 2 == 0:
        if k > len(minus):
            ans = 0
        else:
            minus.sort()
            for i in range(k):
                ans = (ans * minus[i]) % mod
    else:
        if n != len(minus) or k > len(minus):
            ans = 0
        else:
            minus.sort(reverse=True)
            for i in range(k):
                ans = (ans * minus[i]) % mod
elif k == len(plus) + len(minus) and (len(minus) % 2) == 1:
    if n != len(plus) + len(minus):
        ans = 0
    else:
        for x in plus:
            ans = (ans * x) % mod
        for y in minus:
            ans = (ans * y) % mod
else:
    plus.sort(reverse=True)
    minus.sort()
    i, j = 0, 0
    if k % 2 == 1:
        ans = plus[0]
        i = 1
    while i + j < k:
        tmp_p = plus[i] * plus[i + 1] if i <= len(plus) - 2 else 1
        tmp_m = minus[j] * minus[j + 1] if j <= len(plus) - 2 else 1
        if tmp_p >= tmp_m:
            ans = (ans * (tmp_p % mod)) % mod
            i += 2
        else:
            ans = (ans * (tmp_m % mod)) % mod
            j += 2
print(ans)

Submission status: Runtime Error

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

MOD = 10 ** 9 + 7

AA = sorted(A, key=lambda x: -abs(x))

ans = []
mns = []
pls = []
itr = 0
while itr < k:
  ans.append(AA[itr])
  if AA[itr] < 0:
    mns.append(AA[itr])
  else:
    pls.append(AA[itr])
  itr += 1

mflg = False
pflg = False
zflg = False
if all(a < 0 for a in A) and k % 2 == 1:
  AA = sorted(A, key=lambda x: abs(x))
  mns = []
  for itr in range(k):
    mns.append(AA[itr])

elif len(mns) % 2 != 0:
  mm = mns[-1]
  pp = pls[-1]
  for i in range(itr, n):
    nn = AA[i]
    if nn > 0 and not pflg:
      pp *= nn
      pflg = True
      pv = nn
    elif nn < 0 and not mflg:
      mm *= nn
      mflg = True
      mv = nn
    elif nn == 0:
      zflg = True
  if mflg and not pflg:
    del pls[-1]
    mns.append(mv)
  elif pflg and not mflg:
    del mns[-1]
    pls.append(pv)

a = 1
for m in mns:
  a = (a * m) % MOD
for p in pls:
  a = (a * p) % MOD

print(a)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

mod = 10 ** 9 + 7

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

if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

A = np.array(A)

plus = A[A>0]
minus = A[A<0]
zero = A[A==0]

if len(zero) > N - K:
    print(0)
    sys.exit()

if len(minus) == N:
    if K % 2 == 0:
        minus = np.sort(minus)
    else:
        minus = np.sort(minus)[::-1]
    ans = 1
    for i in range(K):
        ans *= minus[i]
        ans %= mod
    print(ans)
    sys.exit()

plus = np.sort(plus)[::-1]
minus *= -1
minus = np.sort(minus)[::-1]

if K % 2 == 1:
    ans = plus[0]
    K -= 1
    p = (len(plus)-1) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i+1] * plus[2*i+2] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]
else:
    ans = 1
    p = len(plus) // 2
    m = len(minus) // 2
    
    n_p = [plus[2*i] * plus[2*i+1] for i in range(p)]
    n_m = [minus[2*i] * minus[2*i+1] for i in range(m)]

K //= 2

p_index = 0
m_index = 0
for i in range(K):
    if p_index == len(n_p):
        ans *= n_m[m_index]
        ans %= mod
        m_index += 1
    elif m_index == len(n_m):
        ans *= n_p[p_index]
        ans %= mod
        p_index += 1
    else:
        if n_p[p_index] > n_m[m_index]:
            ans *= n_p[p_index]
            ans %= mod
            p_index += 1
        else:
            ans *= n_m[m_index]
            ans %= mod
            m_index += 1
print(ans)