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:
#!/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 len(Ps) == 0:
            q1 = Qs.pop()
            q2 = Qs.pop()
            q  = q1 * q2
            r = (r * (q % D)) % D
            k += 2

        elif len(Qs) < 2:
            p = Ps.pop()
            r = (r * (p % D)) % 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)) % D
                Ps.push(p2)
                Qs.push(q1)
                Qs.push(q2)
                k += 1
            else:
                r = (r * (q % D)) % 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 sys
n,k=map(int,input().split())
a = list(map(int,input().split()))
plus = sorted([i for i in a if i > 0],reverse=True)
minus = sorted([i for i in a if i < 0])
b = []
p = 0
m = 0
MOD = 10**9 + 7
if(len(plus) + len(minus) < k):
    print(0)
    sys.exit()

while(True):
    if(len(plus) != 0 and len(minus) != 0):
        if(plus[p] >= -minus[m]):
            b.append(plus[p])
            p += 1
        else:
            b.append(minus[m])
            m += 1
    if(p == len(plus)):
        for i in range(k-p-m):
            b.append(minus[m])
            m += 1
        break
    if(m == len(minus)):
        for i in range(k-p-m):
            b.append(plus[p])
            p += 1
        break
    if(p+m == k):
        if(m % 2 == 1):
            if(minus[m]*minus[m-1] > plus[p]*plus[p-1]):
                b[b.index(plus[p-1])] = minus[m]
            else:
                b[b.index(minus[m-1])] = plus[p]
        break
if(len([i for i in b if i<0]) %2 != 0):
    if(0 in a):
        print(0)
        sys.exit()
    else:
        ans = 1
        p,m = len(plus)-1,len(minus)-1
        b = []
        if(len(plus) != 0 and len(minus) != 0):
            for i in range(k):
                if(plus[p] > -minus[m]):
                    b.append(minus[m])
                    m -= 1
                else:
                    b.append(plus[p])
                    p -= 1
                if(p == 0):
                    for j in range(k-i):
                        b.append(minus[m])
                        m -= 1
                    break
                if(m==0):
                    for j in range(k-i):
                        b.append(plus[p])
                        p -= 1
                    break
        
            for i in range(k):
                ans = ans*b[i] % MOD
            #ans = -((-ans) % -MOD)
            ans = (-ans % MOD)
            print(ans)
            sys.exit()
        if(len(plus) == 0):
            a = sorted(a,reverse=True)
            for i in range(k):
                ans = ans*a[i] % MOD
            print(ans)
            sys.exit()
ans = 1
for i in b:
    ans = ans*i % MOD
print(ans)

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(-1*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)

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 numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and sum([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            if max(positive_small)/max(negative_big) < min(negative_small)/min(positive_big):
                remove = max(negative_big)
                add = max(positive_small)
            else:
                remove = positive_big
                add = negative_small
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

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()
for a in A:
    if a<0:
        P.append(a)
    else:
        Q.appendleft(a)
c=0
S=1
lim = 10**9+7

if len(Q) == 0 and k&1:
    for _ in range(k):
        S*=P.pop()
        S%=lim
    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.pop()
            S%= lim
            c+=1
        else:
            S*= P.pop()
            S%= lim
            S*= P.pop()
            S%= lim
            c+=2
    elif p and (not q):
        S*= P.pop()
        S%= lim
        S*= P.pop()
        S%= lim
        c+=2
    elif (not p) and q:
        S*= Q.pop()
        S%= lim
        c+=1
    else:
        break
print(S)

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

Submission status: Runtime Error

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(sorted(A,key=lambda x: abs(x), reverse=True))

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans % MOD)
    exit()
if K % 2 == 1 and len(list(filter(lambda x: x >= 0, A))) == 0:
    ans = 1
    for i in range(K):
        ans *= B[len(B) - 1 - i]
        ans %= MOD
    print(ans % MOD)
    exit()


ps = list(filter(lambda x: x >= 0, B))
ns = list(filter(lambda x: x < 0, B))

X = []
pi = 0
ni = 0
while len(X) < K:
    if pi + 1 < len(ps) and ni + 1 < len(ns):
        p = ps[pi] * ps[pi + 1]
        neg = ns[ni] * ns[ni + 1]
        if p > neg or K - 1 == len(X):
            X.append(ps[pi])
            pi += 1
        else:
            X.append(ns[ni])
            X.append(ns[ni + 1])
            ni += 2
    elif pi + 1 == len(ps):
        X.append(ps[pi + 1])
        pi += 1
ans = 1
for x in X:
    ans *= x
    ans %= MOD
print(ans % MOD)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and sum([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        nagative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        if len(negative_big)==0 or len(positive_small):
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small):
            remove = max(negative_big)
            add = max(positive_small)
        else:
            if max(positive_small)/max(negative_big) < min(negative_small)/min(positive_big):
                remove = max(negative_big)
                add = max(positive_small)
            else:
                remove = positive_big
                add = negative_small
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

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(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)
    
    else:
        
        AP.sort(reverse=True)
        AM.sort()

        AP = AP[:K]
        AM = AM[:K]

        P = reduce(mul, AP)
        M = 1
        ans = P
        for i in range(0, len(AM)):
            if i < len(AP): 
                M *= AM[i]
                ans = max(ans, P*M/AP[-(i+1)])

        print(int(ans%mod))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
pos = [*filter(lambda x: x >= 0, A)]
neg = [*filter(lambda x: x < 0, A)]
pos.sort(reverse=True)
neg.sort()

ans = 1
i,j = 0,0
while i+j < K:
    flag = True
    if i == len(pos):
        flag = False
    elif j == len(neg):
        flag = True
    elif pos[i] >= -neg[j]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pos[i] % m
        i += 1
    else:
        ans = ans * neg[j] % m
        j += 1
if j % 2 == 0 or N==K:
    print(ans)
elif len(pos) == 0:
    ans = 1
    for i in range(K):
        ans = ans * neg[len(neg)-1-i] % m
    print(ans)
else:
    flag = True
    if i >= len(pos)-1:
        flag = False
    elif j >= len(neg)-1:
        flag = True
    elif pos[i]*pos[i+1] >= neg[j]*neg[j+1]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pow(neg[j],m-2,m) % m
        ans = ans * pos[i+1] % m
    else:
        ans = ans * pow(pos[i],m-2,m) % m
        ans = ans * neg[j+1] % m
    print(ans)

Submission status: Runtime Error

Solution code:
import time
s = time.time()
import random as rnd
MOD = 1000000007

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

A.sort(key=abs)
A.reverse()

ans = A[0]
fact = 0

for i in range(1, K):
    ans = (ans * A[i])

indexes = [x for x in range(K)]

t = 0
while t <= 1.900:
    index1 = rnd.choice(indexes)
    while True:
        index2 = rnd.randint(0, N-1)
        if not (index2 in indexes):
            break


    old = ans
    
    ans //= A[index1]
    ans *= A[index2]

    if old >= ans:
        ans = old
    else:
        indexes.remove(index1)
        indexes.append(index2)
    t = time.time() - s

print(ans % 1000000007)

Submission status: Runtime Error

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

plu = []; mai = []
for i in range(N):
    if A[i] < 0:
        mai.append(A[i])
    else:
        plu.append(A[i])
plu.sort(reverse=True)

ans = 1

if N == K:
    for i in range(N):
        ans = ans * A[i] % MOD

elif len(mai) == N:# and K%2 == 1:
    mai.sort(reverse=True)
    for i in range(K):
        ans = ans * mai[i] % MOD

else:
    mai.sort()
    B = []
    for i in range(0, len(mai)//2, 2):
        B.append(mai[i] * mai[i+1] % MOD)
    if K%2 == 0:
        for i in range(0, len(plu)//2, 2):
            B.append(mai[i] * mai[i+1] % MOD)
        B.sort(reverse=True)
        for i in range(K//2):
            ans = ans * B[i] % MOD
    else:
        for i in range(1, len(plu)//2, 2):
            B.append(mai[i] * mai[i+1] % MOD)
        ans = plu[0] % MOD
        for i in range(K//2):
            ans = ans * B[i] % MOD

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2!=1) or (k==n and sum([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        nagative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        if len(negative_big)==0 or len(positive_small):
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small):
            remove = max(negative_big)
            add = max(positive_small)
        else:
            if max(positive_small)/max(negative_big) < min(negative_small)/min(positive_big):
                remove = max(negative_big)
                add = max(positive_small)
            else:
                remove = positive_big
                add = negative_small
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

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:
        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)
    else:
        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:
            last_plus = 1
        if last_minus == 0:
            last_minus = 1

        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)

Submission status: Runtime Error

Solution code:
MOD = pow(10, 9) + 7
def solve():
    positive = sorted([a for a in A if 0 < a], reverse=True)
    negative = sorted([a for a in A if a <= 0])
    ret = 1

    if not positive:
        negative.reverse()
        for n in negative[: K]:
            ret *= n
        print(ret)
        return

    p_idx, n_idx = 0, 0
    k = 0

    while k < K:
        if k == K - 1:
            if p_idx < len(positive):
                print(ret * positive[p_idx] % MOD)
            else:
                print(ret * negative[n_idx] % MOD)
            return

        if p_idx == len(positive) or (1 <= len(negative) and positive[p_idx] * positive[p_idx + 1] < negative[n_idx] * negative[n_idx + 1]):
            ret *= negative[n_idx] * negative[n_idx + 1]
            n_idx += 2
            k += 2
        else:
            ret *= positive[p_idx]
            p_idx += 1
            k += 1
    print(ret % MOD)

if __name__ == "__main__":
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    solve()

Submission status: Runtime Error

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

P = []
M = []
zero = 0
for a in A:
    if a > 0:
        P.append(a)
    elif a < 0:
        M.append(a)
    else:
        zero += 1

# 0 を選ぶしかない場合
if len(P) + len(M) < K:
    print(0)
    exit()

P.sort(reverse=True)
M.sort()

# a >= 0 のとき
if len(P) + zero == N:
    ans = 1
    for k in range(K):
        ans *= P[k]
        ans %= MOD
    print(ans)
    exit()

# a <= 0 のとき
if len(M) + zero == N:
    ans = 1
    if K % 2 == 0:
        for k in range(K):
            ans *= M[k]
            ans %= MOD
        print(ans)
    else:
        if zero > 0:
            print(0)
        else:
            M.sort(reverse=True)
            for k in range(K):
                ans *= M[k]
                ans %= MOD
            print(ans)
    exit()

# a に正・負両方含まれる場合
cur_p = 0
cur_m = 0
ans = 1
for k in range(K):
    if cur_p == len(P):
        ans *= M[cur_m]
        cur_m += 1
    elif cur_m == len(M):
        ans *= P[cur_p]
        cur_p += 1
    else:
        if P[cur_p] < abs(M[cur_m]):
            ans *= M[cur_m]
            cur_m += 1
        else:
            ans *= P[cur_p]
            cur_p += 1
    ans %= MOD

if cur_m % 2 == 0:
    print(ans)
else:
    if cur_p == len(P):
        ans *= M[cur_m]
        ans *= pow(P[cur_p - 1], MOD - 2, MOD)
        ans %= MOD
    elif cur_m == len(M):
        ans *= P[cur_p]
        ans *= pow(M[cur_m - 1], MOD - 2, MOD)
        ans %= MOD
    else:
        m1 = M[cur_m - 1]
        p1 = P[cur_p]
        m2 = M[cur_m]
        p2 = P[cur_p - 1]
        if abs(p1 * p2) > abs(m1 * m2):
            ans *= p1
            ans *= pow(m1, MOD - 2, MOD)
            ans %= MOD
        else:
            ans *= m2
            ans *= pow(p2, MOD - 2, MOD)
            ans %= MOD
    print(ans)

Submission status: Runtime Error

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

plu = []; mai = []
for i in range(N):
    if A[i] < 0:
        mai.append(A[i])
    else:
        plu.append(A[i])
plu.sort(reverse=True)

ans = 1

if N == K:
    for i in range(N):
        ans = ans * A[i] % MOD

elif len(mai) == N and K%2 == 1:
    mai.sort(reverse=True)
    for i in range(K):
        ans = ans * mai[i] % MOD

else:
    mai.sort()
    B = []
    for i in range(0, len(mai)//2, 2):
        B.append(mai[i] * mai[i+1] % MOD)
    if K%2 == 0:
        for i in range(0, len(plu)//2, 2):
            B.append(mai[i] * mai[i+1] % MOD)
        B.sort(reverse=True)
        for i in range(K//2):
            ans = ans * B[i] % MOD
    else:
        for i in range(1, len(plu)//2, 2):
            B.append(mai[i] * mai[i+1] % MOD)
        ans = plu[0] % MOD
        for i in range(K//2):
            ans = ans * B[i] % MOD

print(ans)

Submission status: Runtime Error

Solution code:
import sys
n,k=map(int,input().split())
a = list(map(int,input().split()))
plus = sorted([i for i in a if i > 0],reverse=True)
minus = sorted([i for i in a if i < 0])
b = []
p = 0
m = 0
MOD = 10**9 + 7
if(len(plus) + len(minus) < k):
    print(0)
    sys.exit()

while(True):
    if(len(plus) != 0 and len(minus) != 0):
        if(plus[p] >= -minus[m]):
            b.append(plus[p])
            p += 1
        else:
            b.append(minus[m])
            m += 1
    if(p == len(plus)):
        for i in range(k-p-m):
            b.append(minus[i+m])
        break
    if(m == len(minus)):
        for i in range(k-p-m):
            b.append(plus[i+p])
        break
    if(p+m == k):
        if(m % 2 == 1):
            if(minus[m]*minus[m-1] > plus[p]*plus[p-1]):
                b[b.index(plus[p-1])] = minus[m]
            else:
                b[b.index(minus[m-1])] = plus[p]
        break
if(len([i for i in b if i<0]) %2 != 0):
    if(0 in a):
        print(0)
        sys.exit()
    else:
        ans = 1
        p,m = len(plus)-1,len(minus)-1
        b = []
        if(len(plus) != 0 and len(minus) != 0):
            for i in range(k):
                if(plus[p] > -minus[m]):
                    b.append(minus[m])
                    m -= 1
                else:
                    b.append(plus[m])
                    p -= 1
        
            for i in range(k):
                ans = ans*b[i] % MOD
            #ans = -((-ans) % -MOD)
            ans = (-ans % MOD)
            print(ans)
            sys.exit()
        if(len(plus) == 0):
            a = sorted(a,reverse=True)
            for i in range(k):
                ans = ans*a[i] % MOD
            print(ans)
            sys.exit()
ans = 1
for i in b:
    ans = ans*i % MOD
print(ans)