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:
MOD = 10**9+7


def least_product(negatives, k):
    ret = 1
    for i in negatives[-k:]:
        ret *= i
    return ret % MOD


def max_product(positives, negatives, k):
    num_products = 0
    pos_index = 0
    neg_index = 0
    ret = 1
    while k - num_products > 1:
        if pos_index + 1 < len(positives) and neg_index + 1 < len(negatives) and positives[pos_index] * positives[pos_index + 1] <= negatives[neg_index] * negatives[neg_index + 1]:
            ret *= negatives[neg_index] * negatives[neg_index + 1]
            ret %= MOD
            num_products += 2
            neg_index += 2
        elif neg_index + 1 < len(negatives) and pos_index == len(positives):
            ret *= negatives[neg_index] * negatives[neg_index + 1]
            ret %= MOD
            num_products += 2
            neg_index += 2
        else:
            ret *= positives[pos_index]
            ret %= MOD
            num_products += 1
            pos_index += 1
    if k - num_products == 1:
        ret *= positives[pos_index]
        ret %= MOD
    return ret


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    negatives = list(filter(lambda x: x < 0, A))
    positives = list(filter(lambda x: x > 0, A))
    negatives.sort()
    positives.sort()
    positives.reverse()
    if len(positives) + len(negatives) < K:
        print(0)
    elif len(positives) + len(negatives) == K:
        if len(negatives) % 2 == 1:
            if N - len(positives) - len(negatives) > 0:
                print(0)
            else:
                # print(least_product(positives, negatives, K))
                ans = 1
                for a in A:
                    ans *= a
                    ans %= MOD
                print(ans)
                # negative
        else:
            print(max_product(positives, negatives, K))
            # postive
    elif len(positives) + len(negatives) > K:
        if len(positives) > 0:
            print(max_product(positives, negatives, K))
            # postive
        else:
            print(least_product(negatives, K))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
a =  list(map(int,input().split()))

list.sort(a, reverse=True)
total = 1
count_a = 0
count_b = N-1


if a[K-1]<0 and K%2 != 0:
	for i in range(N):
		a[i] = abs(a[i])
	list.sort(a, reverse=False)
	for i in range(K):
		total *= a[i]
		total  =total%(10**9 +7)
	total *= -1
	total  =total%(10**9 +7)
else:
	while K>0:
		if K> 1:
			if a[count_a]*a[count_a+1] >a[count_b]*a[count_b-1]:
				total *= a[count_a] * a[count_a+1]
				total  =total%(10**9 +7)
				count_a += 2
			else:
				total *= a[count_b]*a[count_b-1]
				count_b += 2
				total  =total%(10**9 +7)
			K-=2
		else:
			total *= max( a[count_a], a[count_b])
			total  =total%(10**9 +7)
		K -= 1
print(total)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right
from collections import deque

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

idx = bisect_left(A, 0)
idx2 = bisect_right(A, 0)
minus_A = A[:idx]
plus_A = A[idx2:][::-1]
# print(f'{plus_A=}, {minus_A=}')

ans = 1
if len(plus_A) == 0:
    if K % 2 == 1:
        if idx != idx2:
            print(0)
            exit()
        minus_A = minus_A[::-1]
    for i in range(K):
        ans *= minus_A[i]
        ans %= MOD
    print(ans)
    exit()

len_minus_A = len(minus_A)
len_plus_A = len(plus_A)
if len_minus_A == 0:
    for i in range(K):
        ans *= plus_A[i]
        ans %= MOD
    print(ans)
    exit()

minus_A = deque(minus_A)
plus_A = deque(plus_A)
if K > len_plus_A:
    while len_minus_A >= 2 and K >= 2:  # len_plus_A >= 2 and K >= 2:
        if minus_A[0] * minus_A[1] > plus_A[0] * plus_A[1]:
            v1 = minus_A.popleft()
            v2 = minus_A.popleft()
            len_minus_A -= 2
        else:
            v1 = plus_A.popleft()
            v2 = plus_A.popleft()
            len_plus_A -= 2
        ans *= v1
        ans %= MOD
        ans *= v2
        ans %= MOD
        K -= 2
    if len_plus_A == 1 and K >= 2:
        for i in range(K):
            ans *= minus_A[i]
            ans %= MOD
    elif len_puls_A >= 2:
        for i in range(K):
            ans *= plus_A[i]
            ans %= MOD
    elif K % 2 == 1:
        if idx != idx2:
            ans = 0
else:
    while len_minus_A >= 2 and K >= 2:  # len_plus_A >= 2 and K >= 2:
        if minus_A[0] * minus_A[1] > plus_A[0] * plus_A[1]:
            v1 = minus_A.popleft()
            v2 = minus_A.popleft()
            len_minus_A -= 2
        else:
            v1 = plus_A.popleft()
            v2 = plus_A.popleft()
            len_plus_A -= 2
        # print(f'v = {v1}')
        # print(f'v = {v2}')
        ans *= v1
        ans %= MOD
        ans *= v2
        ans %= MOD
        K -= 2
    if K >= 1:
        for i in range(K):
            ans *= plus_A[i]
            ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np

# 標準入力を取得
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

# 求解処理
A = sorted(A, reverse=True)
ans = 1
if A[0] <= 0:
    if K % 2 == 0:
        ans = np.prod(A[:K])
    else:
        ans = np.prod(A[-K:])
else:
    k = 0
    if K % 2 != 0:
        ans *= A[0]
        A = A[1:]
        k += 1
    A = sorted(A, key=abs, reverse=True)
    A_sign = np.sign(A)
    while k < K:
        if K - k == 2:
            ans *= A[k] * A[k + 1]
            break
        sign_k = A_sign[k]
        sign_k1 = A_sign[k + 1]
        sign_k2 = A_sign[k + 2]
        if sign_k == sign_k1:
            ans *= A[k] * A[k + 1]
        elif sign_k == sign_k2:
            ans *= A[k] * A[k + 2]
        else:
            ans *= A[k + 1] * A[k + 2]
            
        k += 2
    
# 結果出力
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True,key=lambda x: abs(x))

def main(n,k,a):
    a = np.array(a)
    if (a<0).all() and k%2==1 : return np.prod(a[-1*k:])
    prod = np.prod(a[:k-2])

    if prod<0:
        p_flag,n_flag = False,False
        p_done,n_done = False,False
        p,n = 0,0
        for i in range(k-2,len(a)):
            if a[i] > 0 :
                if not p_flag:
                    p = a[i]
                    p_flag =True
                if n_flag and not n_done:
                    n *= a[i]
                    n_done = True
            if a[i] < 0:
                if not n_flag:
                    n = a[i]
                    n_flag =True
                if p_flag and not p_done:
                    p *= a[i]
                    p_done = True
    if prod>0:
        p_flag,n_flag = False,False
        p_done,n_done = False,False
        p,n = 0,0
        for i in range(k-2,len(a)):
            if a[i] > 0 :
                if not p_flag:
                    p = a[i]
                    p_flag =True
                else:
                    p *= a[i]
                    p_done = True
            if a[i] < 0:
                if not n_flag:
                    n = a[i]
                    n_flag =True
                else:
                    n *= a[i]
                    n_done = True
    return max(prod*n,prod*p)
print(main(n,k,a))

Submission status: Runtime Error

Solution code:
mod = 10**9+7

import sys
input = sys.stdin.buffer.readline

def main():

    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    P = []
    N = []

    for a in A:
        if a >= 0:
            P.append(a)
        else:
            N.append(a)
    P.sort(reverse=True)
    N.sort()
    #print(P)
    #print(N)

    if len(P) == 0:
        if k%2 == 0:
            N.sort()
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
        else:
            N.sort(reverse=True)
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
        print(ans)
        exit()

    if len(P) == 1:
        if k%2 == 0:
            N.sort()
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
        else:
            ans = P[0]
            N.sort(reverse=True)
            for i in range(k-1):
                ans *= N[i]
                ans %= mod
        print(ans)
        exit()


    if len(N) == 0:
        ans = 1
        for i in range(k):
            ans *= P[i]
            ans %= mod
        print(ans)
        exit()

    if len(N) == 1:
        if len(P) >= k:
            ans = 1
            for i in range(k):
                ans *= P[i]
                ans %= mod
            print(ans)
            exit()
        else:
            print(N[0])
            exit()

    import heapq
    if k%2 == 0:
        P_ = []
        N_ = []
        if len(P) != 1:
            for i in range(len(P)):
                if i%2 == 1:
                    continue
                if i+1 <= len(P)-1:
                    P_.append(-P[i]*P[i+1])
            for i in range(len(N)):
                if i%2 == 1:
                    continue
                if i+1 <= len(N)-1:
                    N_.append(-N[i]*N[i+1])
            heapq.heapify(P_)
            heapq.heapify(N_)
            q = k//2
            ans = 1
            for i in range(q):
                if P_:
                    x = heapq.heappop(P_)*(-1)
                else:
                    x = -1
                if N_:
                    y = heapq.heappop(N_)*(-1)
                else:
                    y = -1
                if x >= y:
                    ans *= x
                    ans %= mod
                    if y >= 0:
                        heapq.heappush(N_, y*(-1))
                else:
                    ans *= y
                    ans %= mod
                    if x >= 0:
                        heapq.heappush(P_, x*(-1))
        else:
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
    else:
        p = P[0]
        P = P[1:]
        P_ = []
        N_ = []
        if len(P) != 1:
            for i in range(len(P)):
                if i%2 == 1:
                    continue
                if i+1 <= len(P)-1:
                    P_.append(-P[i]*P[i+1])
            for i in range(len(N)):
                if i%2 == 1:
                    continue
                if i+1 <= len(N)-1:
                    N_.append(-N[i]*N[i+1])
            heapq.heapify(P_)
            heapq.heapify(N_)
            q = k//2
            ans = p
            for i in range(q):
                if P_:
                    x = heapq.heappop(P_)*(-1)
                else:
                    x = -1
                if N_:
                    y = heapq.heappop(N_)*(-1)
                else:
                    y = -1
                if x >= y:
                    ans *= x
                    ans %= mod
                    if y >= 0:
                        heapq.heappush(N_, y*(-1))
                else:
                    ans *= y
                    ans %= mod
                    if x >= 0:
                        heapq.heappush(P_, x*(-1))
        else:
            ans = p
            N.sort(reverse=True)
            for i in range(k):
                ans *= N[i]
                ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-1*a)

pos.sort(reverse=True)
neg.sort(reverse=True)
p_l = len(pos)
n_l = len(neg)
sign = 1
i, j = 0, 0
for _ in range(K):
    if pos[i] > neg[j] and i < p_l - 1:
        i += 1
    elif pos[i] <= neg[j] and j < n_l - 1:
        j += 1
        sign *= -1
    elif i < p_l - 1:
        j += 1
        sign *= -1
    elif j < n_l - 1:
        i += 1
if sign == -1:
    a, b = -1, -1
    if i < p_l - 1:
        a = pos[i+1]/neg[j]
    if j < n_l - 1:
        b = neg[j+1]/pos[i]
    if a > b:
        i += 1
        j -= 1
    else:
        i -= 1
        j += 1

ans = 1
for p in pos[:i]:
    ans *= p
for n in neg[:j]:
    ans *= n

print(ans)

Submission status: Runtime Error

Solution code:
import bisect

n, k = [int(i) for i in input().split()]
a  = [int(i) for i in input().split()]

minus = []
positive = []
aller = []
zero = 0
for i in a:
    if i < 0:
        minus.append(-i)
    elif i > 0:
        positive.append(i)
    else:
        zero += 1


positive.sort()
minus.sort()

aller = positive + minus[:-2]
aller.sort()

if n == k:
    if zero >= 1:
        print(0)
    else:
        res = 1
        for i in a:
            res *= i
            res %= 10**9 + 7
        print(res)   
elif n - k < zero:
    print(0)
elif minus == 1:
    if k == len(positive) + 1 and zero >= 1:
        print(0)
    elif k == len(positive) + 1 and zero == 0:
        res = 1
        for i in a:
            res *= i
            res %= 10**9 + 7
        print(res)   
    else:
        res = 1
        for i in positive[::-1][:k]:
            res *= i
            res %= 10**9 + 7
        print(res)  
elif minus == 0:
    if k - len(positive) > 0:
        print(0)
    else:
        res = 1
        for i in positive[:k]:
            res *= i
            res %= 10**9 + 7
        print(res)  
elif k - positive == 2:
    aller = []

    for i in a:
        if i < 0:
            aller.append([i, -i])
        elif i > 0:
            aller.append([i, i])
        else:
            aller.append([0, 0])

    aller.sort(key=lambda student: student[0])

    aller = aller[::-1]

    cur = 0
    res = 1
    while cur < k - 2:
        res *= aller[cur][0]
        res %= 10**9 + 7
        cur += 1

    aller = aller[k - 2:]
    now = cur
    while cur < k:
        if aller[now][1] > 0:
            now += 1
        else:
            res *= aller[now][1]
            res %= 10**9 + 7
            cur += 1

    print(res)
else:
    aller = []

    for i in a:
        if i < 0:
            aller.append([i, -i])
        elif i > 0:
            aller.append([i, i])
        else:
            aller.append([0, 0])

    aller.sort(key=lambda student: student[0])

    aller = aller[::-1]

    cur = 0
    res = 1
    while cur < k - 2:
        res *= aller[cur][0]
        res %= 10**9 + 7
        cur += 1

    aller = aller[k - 2:]
    now = cur
    while cur < k:
        if aller[now][1] > 0:
            now += 1
        else:
            res *= aller[now][1]
            res %= 10**9 + 7
            cur += 1

    print(res)

Submission status: Runtime Error

Solution code:
from collections import deque

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

check = 0
abs_li = []
ans = 1

for i in range(n):
    if li[i] < 0:
        li[i] = abs(li[i])
        check += 1
        abs_li.append(li[i])
        
li.sort(reverse=True)

ans_li = li[:k]

swich = 0

if len(abs_li) == 0:
    for i in range(k):
        ans *= li[i]
        ans %= mod
    print(ans)
    exit()

if len(abs_li) == n:
    if k%2 == 1:
        for i in range(1, k+1):
            ans *= -li[i]
            ans %= mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans *= li[i]
            ans %= mod
        print(ans)
        exit()


for i in ans_li:
    if i in abs_li:
        swich += 1
        tmp = i
        
if swich%2 == 0:
    pass

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7

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

A_pos = [a for a in As if a >= 0]
A_pos.sort()
A_pos.reverse()

A_neg = [a for a in As if a < 0]
A_neg.sort()

ans = 1

pos_used = 0
neg_used = 0

pos_total = len(A_pos)
neg_total = len(A_neg)

# 答えが負になるかチェック
if pos_total < K and (K-pos_total)%2 == 1:
    # 小さい方から取る
    A_pos.reverse()
    A_neg.reverse()


k = K
# 二つずつペアで見てゆく
while (pos_used+neg_used) < K:
    # Kが1
    if K == 1:
        if N == 1:
            if pos_total == 1:
                ans = (ans * A_pos[0]) % MOD
            else:
                ans = (ans * A_neg[0]) % MOD
        else:
            if pos_total > 0:
                ans = (ans * A_pos[0]) % MOD
            else:
                ans = (ans * A_neg[0]) % MOD
        break

    # のこり2以上のとき
    if K-(pos_used+neg_used) >= 2:
        # 正の数，負の数とも二つ以上残っているとき
        if (pos_total-pos_used)>=2 and (neg_total-neg_used)>=2:
            if A_neg[neg_used]*A_neg[neg_used+1] >= A_pos[pos_used]*A_pos[pos_used+1]:
                ans = (ans * A_neg[neg_used] * A_neg[neg_used+1]) % MOD
                neg_used += 2
            else:
                ans = (ans * A_pos[pos_used] * A_pos[pos_used+1]) % MOD
                pos_used += 2

        # もう正の数しか残っていない時
        elif neg_total == neg_used:
            ans = (ans * A_pos[pos_used] * A_pos[pos_used+1]) % MOD
            pos_used += 2

        # もう負の数しか残っていない時
        else:
            ans = (ans * A_neg[neg_used] * A_neg[neg_used+1]) % MOD
            neg_used += 2

    # のこり一つのとき
    else:
        # もう正の数しか残っていない時
        if neg_total == neg_used:
            ans = (ans * A_pos[pos_used]) % MOD
            pos_used += 1

        # もう負の数しか残っていない時
        else:
            ans = (ans * A_neg[neg_used]) % MOD
            neg_used += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import reduce
from operator import mul
from bisect import bisect_left


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def sign(x):
    if x == 0:
        return 0
    if x < 0:
        return -1
    return 1


class ModInt(int):
    
    MOD = 10**9+7

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)

    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)

    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)

    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)

    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()

    def __truediv__(self, other):
        inv = ModInt(other).inverse()
        return ModInt(super().__mul__(inv) % ModInt.MOD)

    def __floordiv__(self, other):
        return self.__truediv__(other)

    def __rtruediv__(self, other):
        return ModInt(self.inverse().__mul__(other))

    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)

    def _extgcd(self, a, b):
        assert not isinstance(a, ModInt) and not isinstance(b, ModInt)
        if a < b:
            m, y, x = self._extgcd(b, a)
            return (m, x, y)
        if b == 0:
            x = 1
            y = 0
            return (a, x, y)
        m, y, x = self._extgcd(b, a % b)
        y = y - a // b * x
        return (m, x, y)

    def inverse(self):
        a = int(self)
        m = int(ModInt.MOD)
        n, x, y = self._extgcd(a, m)
        if n != 1:
            raise ValueError("{} and {} are not mutually prime.".format(a, m))
        return ModInt(x)


def solve(N, K, A, p=10**9+7):
    A.sort(key=lambda x: -abs(x))
    n_zero = 0
    n_minus = 0
    for a in A:
        if a == 0:
            n_zero += 1
        elif a < 0:
            n_minus += 1
    n_plus = N - n_zero - n_minus

    # 全て0以下のとき
    if n_plus == 0:
        # マイナスを偶数個選べる -> それが最大値
        if n_minus <= K and n_minus % 2 == 0:
            base = 1
            for i in range(K):
                base *= A[N-i]
            return base
        elif n_zero > 0:
            return 0
        else:
            base = 1
            for i in range(K):
                base *= A[i]
            return base % p
    # プラスが1つ以上あるとき
    # 0を選ばざるを得ないなら0
    if n_plus + n_minus < K:
        return 0
    # 0を選ばなくて良いとき: A[n_zero:] から選ぶ
    B = A[n_zero:]
    sn = 1
    base = 1
    r0 = 0
    r1 = 0
    for i in range(K):
        a = A[i]
        if a < 0:
            r0 = i
            r1 = r0
        sn *= sign(a)
        base *= abs(a)
        base %= p
    if sn == 1:
        return base % p
    
    sn = 1
    base = 1
    for i in range(r1):
        a = A[i]
        sn *= sign(a)
        base *= abs(a)
        base %= p
    for i in range(r1, N):
        if A[i] > 0:
            base *= a
            base %= p
    return base % p
        




if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())

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

A_minus = []
A_plus = []
A_zero_count = 0

for a in A:
    if a > 0:
        A_plus.append(a)
    elif a == 0:
        A_zero_count += 1
    else:
        A_minus.append(a)

A_plus.sort(reverse=True)
A_minus.sort()

MOD = 10 ** 9 + 7


# aの-1乗をmで割ったときの商を求める
def mod_inv(mod_a, m=10 ** 9 + 7):
    b = m
    u = 1
    v = 0
    while b > 0:
        t = mod_a // b
        mod_a -= t * b
        c = mod_a
        mod_a = b
        b = c

        u -= t * v
        c = u
        u = v
        v = c
    u %= m
    return u


def get_all_mul(area):
    ans = 1
    for a_check in area:
        ans = mul(ans, a_check)
    return ans


def mul(mul_a, mul_b):
    return (mul_a * mul_b) % MOD


def solve():
    ans = 1
    if N == K:
        return get_all_mul(A)

    if K + A_zero_count > N:
        return 0

    if len(A_plus) == 0:
        if A_zero_count == 0:
            if K & 1:
                return get_all_mul(A_minus[-K:])
            else:
                return get_all_mul(A_minus[:K])
        else:
            if K & 1:
                return 0
            else:
                return get_all_mul(A_minus[:K])
    elif len(A_minus) == 0:
        return get_all_mul(A_plus[:K])
    else:
        if K + A_zero_count == N:
            if len(A_minus) & 1:
                return 0
            else:
                return mul(get_all_mul(A_minus), get_all_mul(A_plus))

        A_plus.append(0)
        A_minus.append(0)
        plus_choice_num = 0
        minus_choice_num = 0
        last_plus_choice = 0
        last_minus_choice = 0
        for _ in range(K):
            if A_plus[plus_choice_num] > -A_minus[minus_choice_num]:
                ans = mul(ans, A_plus[plus_choice_num])
                last_plus_choice = A_plus[plus_choice_num]
                plus_choice_num += 1
            else:
                ans = mul(ans, A_minus[minus_choice_num])
                last_minus_choice = A_minus[minus_choice_num]
                minus_choice_num += 1
        if minus_choice_num & 1 == 0:
            return ans
        else:
            if last_plus_choice * A_plus[plus_choice_num] >= last_minus_choice * A_minus[minus_choice_num]:
                change = mul(mod_inv(last_minus_choice), A_plus[plus_choice_num])
            else:
                change = mul(mod_inv(last_plus_choice), A_plus[minus_choice_num])
            return mul(ans, change)

print(solve())

Submission status: Runtime Error

Solution code:
from operator import add


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x

N, K = map(int, input().split())
*A, = map(int, input().split())
la, lb, lc = [], [], []
MOD = 10**9+7


for i in A:
    if i<0:
        la.append(i)
    elif i==0:
        lb.append(i)
    else:
        lc.append(i)
ka, kb, kc = len(la), len(lb), len(lc)
la.sort()
lb.sort()
lc.sort()

tree1 = SegTree(ka, 1, lambda x,y:(x*y)%MOD)
tree1.set_list(la)
tree2 = SegTree(kc, 1, lambda x,y:(x*y)%MOD)
tree2.set_list(lc)

ans = -10**20
ap = 0
am = 10**12

for i in range(2, min(ka, K)+1, 2):
    if K-i>kc:continue
    #plus
    ap = max(ap, tree1.get(ka-i, ka)*tree2.get(kc-(K-i), kc)%MOD)

for i in range(1, min(ka, K)+1, 2):
    if K-i>kc:continue
    am = min(am, tree1.get(0, i)*tree2.get(0, K-i)%MOD)
if kc>=K:
    ap = max(ap, tree2.get(kc-K, kc))

if K%2:
    if kc>=K:
        am = min(am, tree1.get(kc-K, kc)%MOD)
else:
    if kc>=K:
        ap = max(ap, tree1.get(kc-K, kc)%MOD)

if lb:
    am = max(am, 0)

if ap:
    print(ap)
else:
    print(am)

Submission status: Runtime Error

Solution code:

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

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

a.sort()

from bisect import bisect_left, bisect_right
zerostart = bisect_left(a, 0)
posstart = bisect_right(a, 0)

aneg = a[:zerostart]
cntzero = posstart - zerostart
apos = a[posstart:]

cntneg = len(aneg)
cntpos = len(apos)

# 答えが0になる時
if k > n-cntzero:
    print(0)
    exit()

cntneg = len(aneg)
cntpos = len(apos)

mix = [(-neg,-1) for neg in aneg] + [(pos,1) for pos in apos]
mix.sort(key=lambda x:x[0],reverse=True)


# 答えが正になる時
if k <= cntpos or (k%2==0 and  k <= (cntneg//2)*2 + cntpos) or (k%2==1 and cntpos%2==1 and k <= (cntneg//2)*2 + cntpos-1):
    pos_pair_mix=[]
    apos.sort(reverse=True)
    for i in range(cntpos//2):
        pos_pair_mix.append((apos[2*i]*apos[2*i+1],+1,i))

    for i in range(cntneg//2):
        pos_pair_mix.append((aneg[2*i]*aneg[2*i+1],-1,i))

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

    ans = 1
    last_apos=0

    for i in range(k//2):
        ans*=pos_pair_mix[i][0]%p
        ans%=p
        if pos_pair_mix[i][1]==1:
            last_apos = pos_pair_mix[i][2]+1
    if k%2==0:
        print(ans%p)
        exit()
    else:
        print((ans*apos[last_apos])%p)
        exit()

# 答えが負になる時
mix = [(neg,-neg,-1) for neg in aneg] + [(pos,,pos,1) for pos in apos]
mix.sort(key=lambda x:x[1])

ans = 1
for i in range(k-cntzero):
    ans*=mix[i][0]
    ans%=p

if ans <0 and cntzero>0:
    ans = 0

print(ans%p)

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import numpy as np
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,K = I()
A = l()
hu = []
sei = []
ans = A[0]
for i in range(N):
    if A[i] > 0:
        sei.append(A[i])
    elif A[i] < 0:
        hu.append(A[i]*-1)
sei.sort(reverse=True)
hu.sort()
ruiseki = [1]
cnt = 1
for i in range(len(hu)):
    cnt *= hu[i]
    if i%2 == 1:
        ruiseki.append(cnt)
if K%2 == 0:
    for i in range(K//2):
        ans = max(ans,np.prod(sei[:i*2])*ruiseki[len(ruiseki)-i-1])
else:
    for i in range(K//2-1):
        ans = max(ans, np.prod(sei[:i * 2+1])* ruiseki[len(ruiseki) - i - 1])
print(int(ans))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = sorted([int(x) for x in input().strip().split()])
    zeros = A.count(0)
    max_A = max(A)
    mod = 10 ** 9 + 7
    if N == K:
        ans = 1
        for k in range(K):
            ans = (ans * A[k]) % mod
        print(ans)
        return
    if max_A < 0:
        if K % 2:
            ans = 1
            for k in range(K):
                ans = (ans * A[-1-k]) % mod
            print(ans)
            return
        else:
            for k in range(K):
                ans = (ans * A[k]) % mod
            print(ans)
            return
    elif max_A == 0:
        if A[K-1] == 0:
            print(0)
            return
        else:
            if len([a for a in A if a < 0]) % 2:
                print(0)
                return
            else:
                ind = A.index(0)
                for k in range(K):
                    ans = (ans * A[ind-k-1]) % mod
                print(ans)
                return
    else:
        if N - zeros < K:
            print(0)
            return
        if N - zeros == K:
            if len([a for a in A if a < 0]) % 2:
                print(0)
                return
            else:
                ans = 1
                for a in A:
                    if a != 0:
                        ans = (ans * a) % mod
                print(ans)
                return
        ans = 1
        A.sort(key=lambda x: abs(x), reverse=True)
        minus = 0
        for k in range(K):
            if A[k] < 0:
                minus += 1
                minus_last_index = k
            ans = (ans * A[k]) % mod
        if minus % 2:
            for k in range(minus_last_index):
                ans = (ans * A[k]) % mod
            k = minus_last_index + 2
            k2 = k
            while k2 < K:
                if A[k] >= 0:
                    ans = (ans * A[k]) % mod
                    k += 1
                    K2 = k
                else:
                    k += 1

        print(ans)

if __name__ == '__main__':
    main()