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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 1000000007

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)

if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3


rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = -1000000000000
        
        if plus_target >= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1

    if minus_counter%2 == 1:
        """インデックスの有効範囲をよく考えること、勝手に-1とかなっちゃう"""
        if minus_now >= len(minuss) or plus_now == 0:
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        elif plus_now >= len(pluss) or minus_now == 0:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod
        """割り算の時は有効桁数よく考えること"""
        elif pluss[plus_now]*pluss[plus_now-1] > -minuss[minus_now]*(-minuss[minus_now-1]):
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        else:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod

elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = 10000000000000  
        
        if plus_target <= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
    answer = answer * -1
print(answer%mod)

Submission status: Runtime Error

Solution code:

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

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)

if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3


rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = -1000000000000
        
        if plus_target >= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1

    if minus_counter%2 == 1:
           """インデックスの有効範囲をよく考えること、勝手に-1とかなっちゃう"""
        if minus_now >= len(minuss) or plus_now == 0:
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        elif plus_now >= len(pluss) or minus_now == 0:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod
            """割り算の時は有効桁数よく考えること"""
        elif pluss[plus_now]*pluss[plus_now-1] > -minuss[minus_now]*(-minuss[minus_now-1]):
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        else:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod

elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = 10000000000000  
        
        if plus_target <= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
    answer = answer * -1
print(answer%mod)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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


def main():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())), np.int64)

    MOD = 10 ** 9 + 7

    pos = A[A >= 0]
    neg = A[A < 0]

    flag = False  # 積を正にできるか

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

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = np.sort(np.abs(A))
        for a in A[:K]:
            ans *= a % MOD
        ans *= -1
    else:
        pos = np.sort(pos)
        neg = np.sort(neg)[::-1]
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos[-1]
            pos = pos[:-1]

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        newpos = pos[::-1][::2] * pos[::-1][1::2]
        newneg = neg[::2] * neg[1::2]
        pairs = np.concatenate([newpos, newneg])

        pairs = np.sort(pairs)[::-1]
        for i in range(K // 2):
            ans *= pairs[i] % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

mod = 10 ** 9 + 7

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

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

plus = []
minus = []

for i in range(N):
    if A[i] < 0:
        minus.append(A[i])
    else:
        plus.append(A[i])

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

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

ans = 1
flag = 0
if K % 2 == 1:
    flag = 1
    K -= 1
    ans *= plus[0]

n_plus = [(plus[i+flag] * plus[i+flag+1]) % mod for i in range((len(plus)-flag)//2)]
n_minus = [(minus[i] * minus[i+1]) % mod for i in range(len(minus)//2)]

p = 0
m = 0
for i in range(K//2):
    if p == len(n_plus):
        ans *= n_minus[m]
        ans %= mod
        m += 1
    elif m == len(n_minus):
        ans *= n_plus[p]
        ans %= mod
        p += 1
    elif n_plus[p] > n_minus[m]:
        ans *= n_plus[p]
        ans %= mod
        p += 1
    else:
        ans *= n_minus[m]
        ans %= mod
        m += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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


def main():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())))

    MOD = 10 ** 9 + 7

    pos = A[A >= 0]
    neg = A[A < 0]

    flag = False  # 積を正にできるか

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

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = np.sort(np.abs(A))
        for a in A[:K]:
            ans *= a % MOD
        ans *= -1
    else:
        pos = np.sort(pos)
        neg = np.sort(neg)[::-1]
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos[-1]
            pos = pos[:-1]

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        newpos = pos[::-1][::2] * pos[::-1][1::2]
        newneg = neg[::2] * neg[1::2]
        pairs = np.concatenate([newpos, newneg])

        pairs = np.sort(pairs)[::-1]
        for i in range(K // 2):
            ans *= pairs[i] % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")



N, K = map(int, f.readline().split())
A = list(map(int, f.readline().split()))
mod = 1000000007

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)

if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3


rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = -1000000000000
        
        if plus_target >= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1

    if minus_counter%2 == 1:
        if minus_now >= len(minuss):
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        elif plus_now >= len(pluss):
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod
        elif pluss[plus_now]*pluss[plus_now-1] >= -minuss[minus_now]*(-minuss[minus_now-1]):
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        else:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod

elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = 10000000000000  
        
        if plus_target <= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
    answer = answer * -1
print(answer%mod)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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


def main():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())))

    MOD = 10 ** 9 + 7

    pos = A[A >= 0]
    neg = A[A < 0]

    flag = False  # 積を正にできるか

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

    if len(pos) > 0:
        flag = True
    else:
        if K % 2 == 0:
            flag = True

    ans = 1
    if not flag:
        # 積を正にできないとき
        # 絶対値の小さい方からK個とる
        A = np.sort(np.abs(A))
        for a in A[:K]:
            ans *= a % MOD
        ans *= -1
    else:
        pos = np.sort(pos)
        neg = np.sort(neg)[::-1]
        if K % 2 == 1:
            # Kが奇数の時
            # 一番大きい偶数を1つとる。
            ans *= pos[-1]
            pos = pos[:-1]

        # pos, neg sort -> 2個ずつペア -> 降順sort -> 上から K//2 個とる
        newpos = pos[::-1][::2] * pos[::-1][1::2]
        newneg = neg[::2] * neg[1::2]
        pairs = np.concatenate([newpos, newneg])

        pairs = np.sort(pairs)
        for p in pairs[: K // 2]:
            ans *= p % MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
negs = [-x for x in A if x < 0]
non_negs = [x for x in A if x >= 0]


def inv(a):
    return pow(a, mod - 2, mod)


# 負の数を選ばざるを得ない数を考える
# 選べる負の数の個数の最小
n_min = k - (max(n - len(negs), 0))
# 　選べる負の数の個数の最大
n_max = min(n, k)

# この2数が一致していて、更に奇数のときにのみ負になる。(はず)
if n_max == n_min and n_max % 2 == 1:
    negs.sort()
    non_negs.sort()
    cnt = 0
    ans = 1
    n_idx, nn_idx = 0, 0
    while cnt < k:
        if n_idx == len(negs):
            ans *= non_negs[nn_idx]
            nn_idx += 1
        elif nn_idx == len(non_negs):
            ans *= negs[n_idx]
            n_idx += 1
        else:
            if non_negs[nn_idx] < negs[n_idx]:
                ans *= non_negs[nn_idx]
                nn_idx += 1
            else:
                ans *= negs[n_idx]
                n_idx += 1
        ans %= mod
        cnt += 1
    ans *= -1
    print(ans % mod)
    exit()

negs.sort(reverse=True)
non_negs.sort(reverse=True)

cnt = 0
ans = 1
neg_cnt = 0
n_idx, nn_idx = 0, 0
# idx番号と配列の長さを比較して、その配列から取得可能かをみる
while cnt < k:
    if n_idx == len(negs):
        ans *= non_negs[nn_idx]
        nn_idx += 1
    elif nn_idx == len(non_negs):
        ans *= negs[n_idx]
        n_idx == 1
        neg_cnt += 1
    else:
        if non_negs[nn_idx] > negs[n_idx]:
            ans *= non_negs[nn_idx]
            nn_idx += 1
        else:
            ans *= negs[n_idx]
            n_idx += 1
            neg_cnt += 1
    ans %= mod
    cnt += 1

if neg_cnt % 2 == 0 or n == k:
    a=A[2*n]
    print(ans % mod)
else:
    
    # 次にかけるのはnegs[n_idx] or non_negs[nn_idx]
    # 一つ戻すならnegs[n_idx-1] or non_negs[nn_idx-1]

    # negsが右にずらせるかどうか
    if n_idx == len(negs) or nn_idx == 0:
        ans *= inv(negs[n_idx - 1])
        ans *= non_negs[nn_idx]
        ans %= mod
    # non_negsが右にずらせるか
    elif nn_idx == len(non_negs) or n_idx == 0:
        ans *= inv(non_negs[nn_idx - 1])
        ans *= negs[n_idx]
        ans %= mod
    else:
        # 両方ともずらせないのはすでに除外済み(のはず)
        if non_negs[nn_idx] * non_negs[nn_idx - 1] > negs[n_idx] * negs[n_idx - 1]:
            ans *= non_negs[nn_idx]
            ans *= inv(negs[n_idx - 1])
            ans %= mod
        else:
            ans *= negs[n_idx]
            ans *= inv(non_negs[nn_idx - 1])
            ans %= mod

    print(ans % mod)

Submission status: Runtime Error

Solution code:
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")



N, K = map(int, f.readline().split())
A = list(map(int, f.readline().split()))
mod = 1000000007

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)

if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3


#%%
rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = -1000000000000
        
        if plus_target >= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1

    if minus_counter%2 == 1:
        if minus_now >= len(minuss):
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        elif plus_now >= len(pluss):
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod
        elif pluss[plus_now]/(-minuss[minus_now-1]) >= -minuss[minus_now]/(pluss[plus_now-1]):
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        else:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod

elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = 10000000000000  
        
        if plus_target <= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
    answer = answer * -1
print(answer%mod)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
negs = [-x for x in A if x < 0]
non_negs = [x for x in A if x >= 0]


def inv(a):
    return pow(a, mod - 2, mod)


# 負の数を選ばざるを得ない数を考える
# 選べる負の数の個数の最小
n_min = k - (max(n - len(negs), 0))
# 　選べる負の数の個数の最大
n_max = min(n, k)

# この2数が一致していて、更に奇数のときにのみ負になる。(はず)
if n_max == n_min and n_max % 2 == 1:
    negs.sort()
    non_negs.sort()
    cnt = 0
    ans = 1
    n_idx, nn_idx = 0, 0
    while cnt < k:
        if n_idx == len(negs):
            ans *= non_negs[nn_idx]
            nn_idx += 1
        elif nn_idx == len(non_negs):
            ans *= negs[n_idx]
            n_idx += 1
        else:
            if non_negs[nn_idx] < negs[n_idx]:
                ans *= non_negs[nn_idx]
                nn_idx += 1
            else:
                ans *= negs[n_idx]
                n_idx += 1
        ans %= mod
        cnt += 1
    ans *= -1
    print(ans % mod)
    exit()

negs.sort(reverse=True)
non_negs.sort(reverse=True)

cnt = 0
ans = 1
neg_cnt = 0
n_idx, nn_idx = 0, 0
# idx番号と配列の長さを比較して、その配列から取得可能かをみる
while cnt < k:
    if n_idx == len(negs):
        ans *= non_negs[nn_idx]
        nn_idx += 1
    elif nn_idx == len(non_negs):
        ans *= negs[n_idx]
        n_idx == 1
        neg_cnt += 1
    else:
        if non_negs[nn_idx] > negs[n_idx]:
            ans *= non_negs[nn_idx]
            nn_idx += 1
        else:
            ans *= negs[n_idx]
            n_idx += 1
            neg_cnt += 1
    ans %= mod
    cnt += 1

if neg_cnt % 2 == 0 or n == k:
    print(ans % mod)
else:
    a=A[2*n]
    # 次にかけるのはnegs[n_idx] or non_negs[nn_idx]
    # 一つ戻すならnegs[n_idx-1] or non_negs[nn_idx-1]

    # negsが右にずらせるかどうか
    if n_idx == len(negs) or nn_idx == 0:
        ans *= inv(negs[n_idx - 1])
        ans *= non_negs[nn_idx]
        ans %= mod
    # non_negsが右にずらせるか
    elif nn_idx == len(non_negs) or n_idx == 0:
        ans *= inv(non_negs[nn_idx - 1])
        ans *= negs[n_idx]
        ans %= mod
    else:
        # 両方ともずらせないのはすでに除外済み(のはず)
        if non_negs[nn_idx] * non_negs[nn_idx - 1] > negs[n_idx] * negs[n_idx - 1]:
            ans *= non_negs[nn_idx]
            ans *= inv(negs[n_idx - 1])
            ans %= mod
        else:
            ans *= negs[n_idx]
            ans *= inv(non_negs[nn_idx - 1])
            ans %= mod

    print(ans % mod)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
arr = [int(x) for x in input().split()]

MOD = int(1e9) + 7

if k == n:
    res = 1
    for i in range(len(arr)):
        res = ((res % MOD) * (arr[i] % MOD)) % MOD
    print(res % MOD)
    exit(1)

pos = []
neg = []


for ele in arr:
    if ele < 0:
        neg.append(ele)
    else: #zero bhi hoga isme
        pos.append(ele)

max_prod = 1

#agar result mei negative sign ayega hi toh phir sabse chhote element lene pdhenge
contains_neg = False
required_neg = k - len(pos)
if required_neg % 2 != 0:
    contains_neg = True

if contains_neg:
    abs_arr = [abs(x) for x in arr]
    abs_arr.sort()
    for i in range(k):
        ele = abs_arr[i]
        max_prod = ((max_prod % MOD) * (ele % MOD)) % MOD
    max_prod *= -1
    print(max_prod % MOD)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    positive_pairs = []
    negative_pairs = []
    for i in range(0, len(pos), 2):
        if i + 1 >= len(pos):
            break
        positive_pairs.append(pos[i] * pos[i+1])
    for i in range(0, len(neg), 2):
        if i + 1 >= len(neg):
            break
        negative_pairs.append(neg[i] * neg[i+1])
    i, j = 0, 0
    for _ in range(k//2):
        if j == len(negative_pairs) and i < len(positive_pairs):
            best = positive_pairs[i] % MOD
            i += 1
        elif i == len(positive_pairs) and j < len(negative_pairs):
            best = negative_pairs[j] % MOD
            j += 1
        elif positive_pairs[i] > negative_pairs[j]:
            best = positive_pairs[i] % MOD
            i += 1
        else:
            best = negative_pairs[j] % MOD
            j += 1
        max_prod = ((max_prod % MOD) * (best % MOD)) % MOD
    if k % 2 != 0:
        if len(pos) % 2 == 1:
            max_prod = ((max_prod % MOD) * (pos[-1] % MOD)) % MOD
        else:
            max_prod = ((max_prod % MOD) * (neg[-1] % MOD)) % MOD
    print(max_prod % MOD)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
arr = [int(x) for x in input().split()]

MOD = int(1e9) + 7

if k == n:
    res = 1
    for i in range(len(arr)):
        res = ((res % MOD) * (arr[i] % MOD)) % MOD
    print(res % MOD)
    exit(1)

pos = []
neg = []


for ele in arr:
    if ele < 0:
        neg.append(ele)
    else: #zero bhi hoga isme
        pos.append(ele)

max_prod = 1

#agar result mei negative sign ayega hi toh phir sabse chhote element lene pdhenge
contains_neg = False
required_neg = k - len(pos)
if required_neg % 2 != 0:
    contains_neg = True

if contains_neg:
    abs_arr = [abs(x) for x in arr]
    abs_arr.sort()
    for i in range(k):
        ele = abs_arr[i]
        max_prod = ((max_prod % MOD) * (ele % MOD)) % MOD
    max_prod *= -1
    print(max_prod % MOD)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    positive_pairs = []
    negative_pairs = []
    for i in range(0, len(pos), 2):
        if i + 1 >= len(pos):
            break
        positive_pairs.append(pos[i] * pos[i+1])
    for i in range(0, len(neg), 2):
        if i + 1 >= len(neg):
            break
        negative_pairs.append(neg[i] * neg[i+1])
    i, j = 0, 0
    for _ in range(k//2):
        if j == len(negative_pairs) and i < len(positive_pairs):
            best = positive_pairs[i] % MOD
            i += 1
        elif i == len(positive_pairs) and j < len(negative_pairs):
            best = negative_pairs[j] % MOD
            j += 1
        elif positive_pairs[i] > negative_pairs[j]:
            best = positive_pairs[i] % MOD
            i += 1
        else:
            best = negative_pairs[j] % MOD
            j += 1
        max_prod = ((max_prod % MOD) * (best % MOD)) % MOD
    if k % 2 != 0:
        assert len(pos) % 2 != 0
        max_prod = ((max_prod % MOD) * (pos[-1] % MOD)) % MOD
    print(max_prod % MOD)

Submission status: Runtime Error

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
BC = []
for a in A:
    if a >= 0:
        B.append(a)
        BC.append(a)
    else:
        C.append(-a)
        BC.append(-a)
ans = 1
if len(B) == 0:
    C = sorted(C)
    for i in range(K):
        ans *= C[i]
        ans %= MOD
    ans *= -1
    ans %= MOD
    print(ans)
    sys.exit()
if N == K:
    for i in range(K):
        ans *= BC[i]
        ans %= MOD
    if len(C) % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    sys.exit()  
negs_p = 0
non_negs_p = 0
for i in range(K):
    if negs_p == len(C):
        non_negs_p += 1
    elif non_negs_p == len(B):
        negs_p += 1
    elif C[negs_p] > B[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)
BC = sorted(BC,reverse = True)

for i in range(K):
    ans *= BC[i]
    ans %= MOD
    
if negs_p % 2 == 1:
    if negs_p == len(C) and non_negs_p == len(B):
        pass
    elif negs_p == len(C):      
        b,c = C[negs_p-1],B[non_negs_p]
        ans = ans // b * c % MOD
    elif non_negs_p == len(B):
        a,d = C[negs_p],B[non_negs_p-1]
        ans = ans // d * a % MOD
    else:
        a,b,c,d = C[negs_p],C[negs_p-1],B[non_negs_p],B[non_negs_p-1]
        if a*b > c*d:
            ans = ans // d * a % MOD
        else:
            ans = ans // b * c % MOD
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

mod = 10 ** 9 + 7

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

if N == K:
    print(numpy.cumprod(A))
    sys.exit()

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

if len(minus) == N:
    np.sort(minus)[::-1]
    print(numpy.cumprod(A[:K]))
    sys.exit()

print(0)
sys.exit()

ans = 1
flag = 0
if K % 2 == 1:
    flag = 1
    K -= 1
    ans *= plus[0]

n_plus = [(plus[i+flag] * plus[i+flag+1]) % mod for i in range((len(plus)-flag)//2)]
n_minus = [(minus[i] * minus[i+1]) % mod for i in range(len(minus)//2)]

p = 0
m = 0
for i in range(K//2):
    if p == len(n_plus):
        ans *= n_minus[m]
        ans %= mod
        m += 1
    elif m == len(n_minus):
        ans *= n_plus[p]
        ans %= mod
        p += 1
    elif n_plus[p] > n_minus[m]:
        ans *= n_plus[p]
        ans %= mod
        p += 1
    else:
        ans *= n_minus[m]
        ans %= mod
        m += 1

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

mod = 10 ** 9 + 7

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

if N == K:
    print(numpy.cumprod(A))
    sys.exit()

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

if len(minus) == N:
    np.sort(minus)[::-1]
    print(numpy.cumprod(A[:K]))
    sys.exit()

ans = 1
flag = 0
if K % 2 == 1:
    flag = 1
    K -= 1
    ans *= plus[0]

n_plus = [(plus[i+flag] * plus[i+flag+1]) % mod for i in range((len(plus)-flag)//2)]
n_minus = [(minus[i] * minus[i+1]) % mod for i in range(len(minus)//2)]

p = 0
m = 0
for i in range(K//2):
    if p == len(n_plus):
        ans *= n_minus[m]
        ans %= mod
        m += 1
    elif m == len(n_minus):
        ans *= n_plus[p]
        ans %= mod
        p += 1
    elif n_plus[p] > n_minus[m]:
        ans *= n_plus[p]
        ans %= mod
        p += 1
    else:
        ans *= n_minus[m]
        ans %= mod
        m += 1

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
negs = [-x for x in A if x < 0]
non_negs = [x for x in A if x >= 0]


def inv(a):
    return pow(a, mod - 2, mod)


# 負の数を選ばざるを得ない数を考える
# 選べる負の数の個数の最小
n_min = k - (max(n - len(negs), 0))
# 　選べる負の数の個数の最大
n_max = min(n, k)

# この2数が一致していて、更に奇数のときにのみ負になる。(はず)
if n_max == n_min and n_max % 2 == 1:
    negs.sort()
    non_negs.sort()
    cnt = 0
    ans = 1
    n_idx, nn_idx = 0, 0
    while cnt < k:
        if n_idx == len(negs):
            ans *= non_negs[nn_idx]
            nn_idx += 1
        elif nn_idx == len(non_negs):
            ans *= negs[n_idx]
            n_idx += 1
        else:
            if non_negs[nn_idx] < negs[n_idx]:
                ans *= non_negs[nn_idx]
                nn_idx += 1
            else:
                ans *= negs[n_idx]
                n_idx += 1
        ans %= mod
        cnt += 1
    ans *= -1
    print(ans % mod)
    exit()

negs.sort(reverse=True)
non_negs.sort(reverse=True)

cnt = 0
ans = 1
neg_cnt = 0
n_idx, nn_idx = 0, 0
# idx番号と配列の長さを比較して、その配列から取得可能かをみる
while cnt < k:
    if n_idx == len(negs):
        ans *= non_negs[nn_idx]
        nn_idx += 1
    elif nn_idx == len(non_negs):
        ans *= negs[n_idx]
        n_idx == 1
        neg_cnt += 1
    else:
        if non_negs[nn_idx] > negs[n_idx]:
            ans *= non_negs[nn_idx]
            nn_idx += 1
        else:
            ans *= negs[n_idx]
            n_idx += 1
            neg_cnt += 1
    ans %= mod
    cnt += 1

if neg_cnt % 2 == 0:
    print(ans % mod)
else:
    # 次にかけるのはnegs[n_idx] or non_negs[nn_idx]
    # 一つ戻すならnegs[n_idx]-1 or non_negs[nn_idx-1]

    # negsが右にずらせるかどうか
    if n_idx == len(negs) or nn_idx == 0:
        ans *= inv(negs[n_idx - 1])
        ans *= non_negs[nn_idx]
        ans %= mod
    # non_negsが右にずらせるか
    elif nn_idx == len(non_negs) or n_idx == 0:
        ans *= inv(non_negs[nn_idx - 1])
        ans *= negs[n_idx]
        ans %= mod
    else:
        # 両方ともずらせないのはすでに除外済み(のはず)
        if non_negs[nn_idx] * non_negs[nn_idx - 1] > negs[n_idx] * negs[n_idx - 1]:
            ans *= non_negs[nn_idx]
            ans *= inv(negs[n_idx])
            ans %= mod

    print(ans % mod)