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:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
MOD = 10**9 + 7
def main(N, K, A):
    neg = pos = zer = 0
    for a in A:
        if a < 0: neg += 1
        elif a > 0: pos += 1
        else: zer += 1

    if N - K < zer:
        # ゼロになっちゃう
        return 0
    N -= zer
    A = sorted([a for a in A if a != 0], key=lambda x: abs(x))

    if pos == 0 and K & 1:
        # マイナスになっちゃう
        if zer:
            # ゼロにもできるじゃん
            return 0
        else:
            ans = Mint(1)
            for i in range(K):
                ans *= abs(A[i])
            return -ans

    # プラスにできる
    A.reverse()
    positives = []
    negatives = []
    # 絶対値の大きい方からK個取る
    for i in range(K):
        if A[i] > 0: positives.append(A[i])
        else: negatives.append(A[i])

    if len(negatives) & 1:
        # マイナスになっちゃった
        # 1手戻す
        nn = [negatives.pop()]
        pp = [positives.pop()]

        # 残りの人たちからマイナスのペアかプラスのペアを作る
        for i in range(K, N):
            if A[i] < 0: nn.append(A[i])
            else: pp.append(A[i])

        if len(nn) >= 2 and len(pp) < 2:
            # マイナスのペアだけ作れる
            negatives.append(nn[0])
            negatives.append(nn[1])
        elif len(pp) >= 2 and len(nn) < 2:
            # プラスのペアだけ作れる
            positives.append(pp[0])
            positives.append(pp[1])
        elif len(pp) >= 2 and len(nn) >= 2:
            # どっちも作れるなら掛けて大きい方
            if pp[0] * pp[1] > nn[0] * nn[1]:
                positives.append(pp[0])
                positives.append(pp[1])
            else:
                negatives.append(nn[0])
                negatives.append(nn[1])
        else:
            # どっちも作れないなんてことはない
            assert False

    # 答えを計算
    ans = Mint(1)
    for p in positives:
        ans *= p
    for n in negatives:
        ans *= abs(n)
    return ans

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    print(main(N, K, A))

Submission status: Runtime Error

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N,K = LMIIS()
    A = LMIIS()
    positive = []
    negative = []
    zero = []
    for a in A:
        if a >0:
            positive.append(a)
        elif a == 0:
            zero.append(a)
        else:
            negative.append(a)
    positive.sort(reverse=True)
    negative.sort()
    ans = 1
    num_used = 0
    num_used_negative = 0

    if len(positive) + len(negative) < K:
        print(0)
        return

    if len(positive) >= K or (K-len(positive))%2 == 0:

        if len(positive) >= 2:
            comp = positive[0] * positive[1]
        else:
            comp = positive[0]
        
        for i in range(0,min(len(negative),K//2),2):
            if negative[i] * negative[i+1] >= comp:
                ans = ans * negative[i] * negative[i+1] % P
                num_used += 2
                num_used_negative += 1
            else:
                break
        for i in range(K-num_used):
            ans = ans * positive[i] % P
            num_used += 1
        print(ans)
        return
    else:

        #答えが負
        if zero:
            print(0)
            return
        ans = 1
        for a in positive:
            ans = ans * a % P
        negative = negative[::-1]
        for i in range(K-len(positive)):
            ans = ans * negative[i] % P
        print(ans)
        return
                



    
main()

Submission status: Runtime Error

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

z_num = sum(v == 0 for v in A)
p_num = sum(v > 0 for v in A)
m_num = sum(v < 0 for v in A)

if p_num + m_num < K:
    print(0)
    exit()

if p_num == 0 and m_num >= K and K % 2 == 1:
    if z_num > 0:
        print(0)
    else:
        x = sorted([v for v in A if v < 0], reverse=True)
        ans = 1
        n = len(x)
        for i in range(K):
            ans = ans * x[i] % MOD
        print(ans)
    exit()

x = []
for v in A:
    if v != 0:
        x.append((abs(v), v // abs(v)))
    else:
        x.append((0, 0))
x.sort()

plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s >= 0:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0 and 0 not in v:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s == 1 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v

    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_org = plus.pop()
        m_org = minus.pop()
        if p_org * p_cand > m_org * m_cand:
            plus.append(p_org)
            plus.append(p_cand)
        else:
            minus.append(m_org)
            minus.append(m_cand)


ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * (-v) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
list = list(map(int,input().split()))
list.sort(reverse=True)
seki = 1
seki1 = 1
seki2 = 1
if list[0] <= 0 and K % 2 != 0:
    for i in range(K):
        seki *= list[i]
elif N == K:
    for i in range(K):
        seki *= list[i]
else:
    for i in range(K):
        seki1 *= list[i]
    list.sort()
    for i in range(K):
        seki2 *= list[i]
    if (seki2 >= seki1) and (seki2 >= 0):
        seki = seki2
    elif (seki2 >= seki1) and (seki2 < 0):
        while seki2 < 0:
            i = 0
            seki2 = seki2 / list[i] * list[K+1+i]
            i += 1
        seki = seki2
    elif (seki1 > seki2) and (seki1 >= 0):
        seki = seki1
    else:
        list.sort(reverse=True)
        while seki1 < 0:
            i=0
            seki1 = seki1 / list[i] * list[K+1+i]
            i += 1
        seki = seki1

print(seki % ((10**9)+7))

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
from copy import deepcopy
mod = 10**9 + 7

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a = sorted(a, key=lambda x: abs(x))[::-1]
a_plus = [int(x) for x in a if x > 0]
a_minus = [int(x) for x in a if x < 0]
a_abs = [abs(x) for x in a]

def calc(x):
    res = 1
    for i in x:
        res*=abs(i)
        res %= mod 
    return res

max_a = a[:k]
max_a_minus = []
max_a_plus = []
minus_cnt = 0

for i in max_a:
    if i == 0:
        print(0)
        sys.exit()
    if i < 0:
        minus_cnt += 1
        max_a_minus.append(i)
    else:
        max_a_plus.append(i)

if minus_cnt % 2 == 0:
    print(calc(max_a))
    print(5)
    sys.exit()

plus_cnt = k - minus_cnt

if len(a_minus) <= minus_cnt and len(a_plus) <= plus_cnt:
    ans = -float('inf')
elif len(a_minus) <= minus_cnt:
    if len(max_a_minus) == 0:
        ans = -float("inf")
    else:
        max_a_minus.pop()
        max_a_plus.append(a_plus[plus_cnt])
        ans = calc(max_a_plus + max_a_minus)
elif len(a_plus) <= plus_cnt:
    if len(max_a_plus) == 0:
        ans = -float("inf")
    else:
        max_a_plus.pop()
        max_a_minus.append(a_minus[minus_cnt])
        ans = calc(max_a_minus + max_a_plus)
else:
    flag1 = 1
    flag2 = 1
    if len(max_a_minus) == 0:
        ans1 = -float("inf")
        flag1 = 0
        diff1 = float("inf")
    if len(max_a_plus) == 0:
        ans2 = -float("inf")
        flag2 = 0
        diff2 = float("inf")
    if flag1:
        c1 = deepcopy(max_a_minus)
        c2 = deepcopy(max_a_plus)
        d1 = abs(c1.pop()); d2 = abs(a_plus[plus_cnt])
        c2.append(a_plus[plus_cnt])
        ans1 = calc(c1 + c2)
    if flag2:
        c3 = deepcopy(max_a_minus)
        c4 = deepcopy(max_a_plus)
        d3 = abs(c4.pop()); d4 = abs(a_minus[minus_cnt])
        c3.append(a_minus[minus_cnt])
        ans2 = calc(c3 + c4)
    ans = ans1 if d2*d3 > d1*d4 else ans2

a_abs = a_abs[::-1]
ans2 = -calc(a_abs[:k])
if ans != -float("inf"):
    print(ans%mod)
else:
    print(ans2%mod)

Submission status: Runtime Error

Solution code:
from heapq import *
from collections import deque

N,K,*A = map(int, open(0).read().split())
pos = []
zero = 0
neg = []
count = K
m = 1000000007
for x in A:
    if x > 0:
        pos.append(x)
    elif x == 0:
        zero += 1
    else:
        neg.append(x)
if K == N:
    ans = A[0] % m
    for x in A[1:]:
        ans = (ans*x) % m
    print(ans)
elif K % 2 == 1 and len(pos) == 0:
    if zero > 0:
        print(0)
    else:
        ai = [x * (-1) for x in A]
        heapify(ai)
        ans = (heappop(ai)*(-1)) % m
        for i in range(K-1):
            ans = (ans*heappop(ai)*(-1)) % m
        print(ans)
elif K > N - zero:
    print(0)
else:
    heapify(neg)
    ans = 1
    negpos = []
    for i in range(len(neg)//2):
        temp = heappop(neg)
        negpos.append(temp*heappop(neg))
    dnp = deque(negpos)
    posi = [x * (-1) for x in pos]
    heapify(posi)
    if len(posi) > 0:
        t1 = heappop(posi) * (-1)
    if len(posi) > 0:
        t2 = heappop(posi) * (-1)
    else:
        t2 = 1
    for i in range(K):
        if count > 1:
            if len(dnp) > 0:
                if t1 > dnp[0]:
                    ans = (ans*t1) % m
                    t1 = t2
                    if len(posi) > 0:
                        t2 = heappop(posi) * (-1)
                    else:
                        t2 = 1
                    count -= 1
                elif t1 * t2 > dnp[0]:
                    ans = (ans*t1*t2) % m
                    if len(posi) > 0:
                        t1 = heappop(posi) * (-1)
                    if len(posi) > 0:
                        t2 = heappop(posi) * (-1)
                    else:
                        t2 = 1
                    count -= 2
                else:
                    ans = (ans*dnp.popleft()) % m
                    count -= 2
            else:
                ans = (ans*t1) % m
                if len(posi) > 0:
                    t1 = t2
                    t2 = heappop(posi) * (-1)
                else:
                    t1 = t2
                count -= 1
        elif count == 1:
            ans = (ans*t1) % m
            break
        else:
            break
    print(ans)

Submission status: Runtime Error

Solution code:
from heapq import *
from collections import deque

N,K,*A = map(int, open(0).read().split())
pos = []
zero = 0
neg = []
count = K
m = 1000000007
for x in A:
    if x > 0:
        pos.append(x)
    elif x == 0:
        zero += 1
    else:
        neg.append(x)
if K == N:
    ans = A[0] % m
    for x in A[1:]:
        ans = (ans*x) % m
    print(ans)
elif K % 2 == 1 and len(pos) == 0:
    if zero > 0:
        print(0)
    else:
        ai = [x * (-1) for x in A]
        heapify(ai)
        ans = (heappop(ai)*(-1)) % m
        for i in range(K-1):
            ans = (ans*heappop(ai)*(-1)) % m
        print(ans)
elif K > N - zero:
    print(0)
else:
    heapify(neg)
    ans = 1
    negpos = []
    for i in range(len(neg)//2):
        temp = heappop(neg)
        negpos.append(temp*heappop(neg))
    dnp = deque(negpos)
    posi = [x * (-1) for x in pos]
    heapify(posi)
    if len(posi) > 0:
        t1 = heappop(posi) * (-1)
    if len(posi) > 0:
        t2 = heappop(posi) * (-1)
    else:
        t2 = 1
    for i in range(K):
        if count > 1:
            if len(dnp) > 0:
                if t1 >= dnp[0]:
                    ans = (ans*t1) % m
                    t1 = t2
                    if len(posi) > 0:
                        t2 = heappop(posi) * (-1)
                    else:
                        t2 = 1
                    count -= 1
                if t1 * t2 >= dnp[0]:
                    ans = (ans*t1*t2) % m
                    if len(posi) > 0:
                        t1 = heappop(posi) * (-1)
                    if len(posi) > 0:
                        t2 = heappop(posi) * (-1)
                    else:
                        t2 = 1
                    count -= 2
                else:
                    ans = (ans*dnp.popleft()) % m
                    count -= 2
            else:
                ans = (ans*t1) % m
                if len(posi) > 0:
                    t1 = t2
                    t2 = heappop(posi) * (-1)
                else:
                    t1 = t2
                count -= 1
        elif count == 1:
            ans = (ans*t1) % m
            break
        else:
            break
    print(ans)

Submission status: Runtime Error

Solution code:
from heapq import *
from collections import deque

N,K,*A = map(int, open(0).read().split())
pos = []
zero = 0
neg = []
count = K
m = 1000000007
for x in A:
    if x > 0:
        pos.append(x)
    elif x == 0:
        zero += 1
    else:
        neg.append(x)
if K == N:
    ans = A[0] % m
    for x in A[1:]:
        ans = (ans*x) % m
    print(ans)
elif K % 2 == 1 and len(pos) == 0:
    if zero > 0:
        print(0)
    else:
        ai = [x * (-1) for x in A]
        heapify(ai)
        ans = (heappop(ai)*(-1)) % m
        for i in range(len(ai)):
            ans = (ans*heappop(ai)*(-1)) % m
        print(ans)
elif K > N - zero:
    print(0)
else:
    heapify(neg)
    ans = 1
    negpos = []
    for i in range(len(neg)//2):
        temp = heappop(neg)
        negpos.append(temp*heappop(neg))
    dnp = deque(negpos)
    posi = [x * (-1) for x in pos]
    heapify(posi)
    if len(posi) > 0:
        t1 = heappop(posi) * (-1)
    if len(posi) > 0:
        t2 = heappop(posi) * (-1)
    else:
        t2 = 1
    for i in range(K):
        if count > 1:
            if len(dnp) > 0:
                if t1 >= dnp[0]:
                    ans = (ans*t1) % m
                    t1 = t2
                    if len(posi) > 0:
                        t2 = heappop(posi) * (-1)
                    else:
                        t2 = 1
                    count -= 1
                if t1 * t2 >= dnp[0]:
                    ans = (ans*t1*t2) % m
                    if len(posi) > 0:
                        t1 = heappop(posi) * (-1)
                    if len(posi) > 0:
                        t2 = heappop(posi) * (-1)
                    else:
                        t2 = 1
                    count -= 2
                else:
                    ans = (ans*dnp.popleft()) % m
                    count -= 2
            else:
                ans = (ans*t1) % m
                if len(posi) > 0:
                    t1 = t2
                    t2 = heappop(posi) * (-1)
                else:
                    t1 = t2
                count -= 1
        elif count == 1:
            ans = (ans*t1) % m
            break
        else:
            break
    print(ans)

Submission status: Runtime Error

Solution code:
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a.sort()
x=s=1
r=k
while r>0:
 if(t:=a[y]*a[y+1])>a[-x]*a[~x]:s=s*t%M;y+=2;r-=2
 else:s=s*a[-x]%M;x+=1;r-=1
if r:s*=a[-x]
if a[-1]<0<k%2:
 s=1
 for i in a[-k:]:s=s*i%M
print(s%M)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())

        if (len(ans_neg) & 1) and ((not ans_pos) or (ans_pos[-1] != 0)):
            s1 = s2 = 0
            if pos and ans_neg:
                s1 = -pos[-1] / ans_neg[-1]
            if neg and ans_pos:
                s2 = -neg[-1] / ans_pos[-1]

            if s1 > s2:
                ans_pos.append(pos.pop())
                ans_neg.pop()
            else:
                ans_neg.append(neg.pop())
                ans_pos.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())

        if len(ans_neg) & 1 and not (ans_pos and ans_pos[-1] == 0):
            s1 = s2 = 0
            if pos and ans_neg:
                s1 = -pos[-1] / ans_neg[-1]
            if neg and ans_pos:
                s2 = -neg[-1] / ans_pos[-1]

            if s1 > s2:
                ans_pos.append(pos.pop())
                ans_neg.pop()
            else:
                ans_neg.append(neg.pop())
                ans_pos.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())
                
        if len(ans_neg) & 1 and ans_pos[-1] != 0:
            s1 = s2 = 0
            if pos and ans_neg:
                s1 = -pos[-1] / ans_neg[-1]
            if neg and ans_pos:
                s2 = -neg[-1] / ans_pos[-1]

            if s1 > s2:
                ans_pos.append(pos.pop())
                ans_neg.pop()
            else:
                ans_neg.append(neg.pop())
                ans_pos.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1
if K == N:
    for i in range(N):
        prod = prod * A[i][0] % MOD

for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2

if pn == 0:
    for i in range(K):
        prod = prod * A[i][0] % MOD

elif pn == 1:
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp >= N:
        if K % 2 == 0:
            for i in range(K):
                prod = prod * A[i][0] % MOD
        elif K % 2 == 1:
            for i in range(K):
                B = list(reversed(A))
                prod = prod * B[i][0] % MOD
                prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[indn][0] % MOD
            else:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
        prod = max(prod1,prod2)
print(prod)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())
                
        if len(ans_neg) & 1 and ans_pos[-1] != 0:
            s1 = s2 = 0
            if pos and ans_neg:
                s1 = -pos[-1] / ans_neg[-1]
            if neg and ans_neg:
                s2 = -neg[-1] / ans_pos[-1]

            if s1 > s2:
                ans_pos.append(pos.pop())
                ans_neg.pop()
            else:
                ans_neg.append(neg.pop())
                ans_pos.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1
for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2

if pn == 0:
    for i in range(K):
        prod = prod * A[i][0] % MOD

elif pn == 1:
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp >= N:
        if K % 2 == 0:
            for i in range(K):
                prod = prod * A[i][0] % MOD
        elif K % 2 == 1:
            for i in range(K):
                B = list(reversed(A))
                prod = prod * B[i][0] % MOD
                prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[indn][0] % MOD
            else:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
        prod = max(prod1,prod2)
print(prod)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1
for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2

if pn == 0:
    for i in range(K):
        prod = prod * A[i][0] % MOD

elif pn == 1:
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp >= N:
        for i in range(K):
            B = list(reversed(A))
            prod = prod * B[i][0] % MOD
            prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[indn][0] % MOD
            else:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
        prod = max(prod1,prod2)
print(prod)

Submission status: Runtime Error

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

for i in a:
    if i>0:
        m=1
    elif i==0:
        m=0
    else:
        m=-1
    b.append([abs(i),m])

b.sort(key=lambda x: x[0], reverse=True)

mod=10**9+7
ans=1
judge=1
seisaisyou=0
seisaidai=0
husaisyou=0
husaidai=0

for i in range(k):
    ans*=b[i][0]%mod
    judge*=b[i][1]
if judge>0:
    print(ans)
if judge<=0:
    
    for j in range(k-1,-1,-1):
        if b[i][1]==1:
            ss=b[i][0]#正の最小
            seisaisyou=1
            break
            
    for j in range(k-1,-1,-1):
        if b[i][1]==-1:
            hs=b[i][0]#負の最小
            husaisyou=1
            break
        
    
    #正の最小と　範囲外の負の最大を交換する
    for j in range(k,n):
        if b[i][1]==-1:
            h=b[i][0]#負の最大
            husaidai=1
            break
    
    #負の最小と　範囲外の正の最大を交換する
    for j in range(k,n):
        if b[i][1]==1:
            s=b[i][0]#正の最大
            seisaidai=1
            break
    
    if husaidai==1and seisaisyou==1:
        pre1=ans*h/ss
    if seisaidai==1and husaisyou==1:
        pre2=ans*s/hs
    if (husaidai==1and seisaisyou==1)or (seisaidai==1and husaisyou==1):
        ans=max(pre1,pre2)
        print(ans%mod)
    else:
        ans=1
        for i in range(n-1,n-k-1,-1):
            ans*=b[i][0]%mod
        print(mod-1*ans)