Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Runtime Error

Solution code:
from copy import deepcopy
import sys

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

# print(f'{A=}')

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

if K % 2 == 1:
    if max(A) < 0:
        ans = 1
        for a in A[::-1][:K]:
            ans *= a
            ans %= MOD
        print(ans)
        exit()

P = 1
for a in A[:K]:
    if a >= 0:
        P *= 1
    else:
        P *= -1
# print(f'{P=}')

if P > 0:
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# print(f'{A[K:]=}')

# (1) 負の数を 1 つ取り除き、非負の数を 1 つ加える
patern_one = True
plus1, minus1 = 0, 0
for plus1 in A[K:]:
    if plus1 >= 0:
        break
else:
    patern_one = False
for minus1 in A[:K][::-1]:
    if minus1 < 0:
        break
else:
    patern_one = False
# print(f'{plus1=}, {minus1=}, {patern_one=}')

# (2) 正の数を 1 つ取り除き、負の数を 1 つ加える
patern_two = True
plus2, minus2 = 0, 0
for plus2 in A[:K][::-1]:
    if plus2 >= 0:
        break
else:
    patern_two = False
for minus2 in A[K:]:
    if minus2 < 0:
        break
else:
    patern_two = False
# print(f'{plus2=}, {minus2=}, {patern_two=}')


def f1():
    subset = deepcopy(A[:K])
    subset.remove(minus1)
    subset.append(plus1)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


def f2():
    subset = deepcopy(A[:K])
    subset.remove(plus2)
    subset.append(minus2)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


if patern_one and patern_two:
    # print(f'plus2 * minus1={plus2 * minus1}')
    # print(f'plus1 * minus2={plus1 * minus2}')
    if abs(plus2 * minus1) <= abs(plus1 * minus2):
        # (1)
        ans = f1()
        # ans2 = f2()
    else:
        # (2)
        ans2 = f1()
        # ans = f2()
elif patern_one:
    ans = f1()
else:
    ans = f2()
print(ans)
# print(ans, ans2)

Submission status: Runtime Error

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

plus = []
minus = []
zero = 0
ans = 1

for i in a:
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(-i)
    else:
        zero += 1
        
plus.sort(reverse=True)
minus.sort(reverse=True)
plus_l = len(plus)
minus_l = len(minus)
plus_p = 0
minus_p = 0
plus_b = 1
minus_b = 1

if zero > n - k:
    print(0)
elif len(plus) == 0:
    for j in range(k):
        ans *= (minus[(j + 1)]) % num
    if k % 2 == 0:
        print(ans % num)
    else:
        print(-ans % num)
else:
    if k % 2 == 0:
        while plus_l >= 2 and minus_l >= 2 and k >= 2:
            plus_b = plus[plus_p] * plus[plus_p + 1]
            minus_b = minus[minus_p] * minus[minus_p + 1]
            if plus_b >= minus_b:
                ans *= plus_b % num
                plus_p += 2
                plus_l -= 2
                
            else:
                ans *= minus_b % num
                minus_p += 2
                minus_l -= 2
                
            k -= 2
        if k >= 2:
            if plus_l < 2 and minus_l >= 2:
                while k >= 2:
                    minus_b = minus[minus_p] * minus[minus_p + 1]
                    ans *= minus_b % num
                    minus_p += 2
                    minus_l -= 2
                    k -= 2
            elif plus_l >= 2 and minus_l < 2:
                while k >= 2:
                    plus_b = plus[plus_p] * plus[plus_p + 1]
                    ans *= plus_b % num
                    plus_p += 2
                    plus_l -= 2
                    k -= 2
            if k == 2 and plus_l == 1 and minus_l == 1:
                ans *= (plus[plus_p] * minus[minus_p]) % num
    else:
        while plus_l >= 3 and minus_l >= 3 and k >= 2:
            plus_b = plus[plus_p] * plus[plus_p + 1]
            minus_b = minus[minus_p] * minus[minus_p + 1]
            if plus_b >= minus_b:
                ans *= plus_b % num
                plus_p += 2
                plus_l -= 2
                
            else:
                ans *= minus_b % num
                minus_p += 2
                minus_l -= 2
                
            k -= 2
        if k >= 2:
            if plus_l < 2 and minus_l >= 3:
                while k >= 2:
                    minus_b = minus[minus_p] * minus[minus_p + 1]
                    ans *= minus_b % num
                    minus_p += 2
                    minus_l -= 2
                    k -= 2
            elif plus_l >= 3 and minus_l < 2:
                while k >= 2:
                    plus_b = plus[plus_p] * plus[plus_p + 1]
                    ans *= plus_b % num
                    plus_p += 2
                    plus_l -= 2
                    k -= 2
        if k == 1:
            ans *= plus[plus_p]  % num
    print(ans % num)

Submission status: Runtime Error

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


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    return N, K, A


def main(N: int, K: int, A: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 整数
        K (int): 整数
        A (list): 整数列
    """
    # 求解処理
    # 積を0以上にできるかどうか確認
    S, T = [], []
    for a in A:
        if a >= 0:
            S.append(a)
        else:
            T.append(a)
    size_S = len(S)
    size_T = len(T)
    can_plus = True
    if size_S > 0:
        if (N == K) and (size_T % 2 == 1):
            can_plus = False
    if size_S == 0:
        if K % 2 == 1:
            can_plus = False

    ans = 1
    if can_plus:
        S = sorted(S, reverse=True)
        T = sorted(T, key=abs, reverse=True)
        if K % 2 == 1:
            ans *= S[0]
            S = S[1:]

        S = [S[2 * i] * S[2 * i + 1] for i in range(size_S // 2)]
        T = [T[2 * i] * T[2 * i + 1] for i in range(size_T // 2)]
        L = []
        L.extend(S)
        L.extend(T)
        L = sorted(L, reverse=True)
        for l in L[:K // 2]:
            ans *= l
    else:
        A = sorted(A, key=abs)
        for a in A[:K]:
            ans *= a
    ans %= pow(10, 9) + 7

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, K, A = get_input()

    # メイン処理
    main(N, K, A)

Submission status: Runtime Error

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))
    ans_cand=[v for v in absL[:K]]
    remain=[v for v in absL[K:]]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        #ans_candはabsの大きさでsortされている
        #できるだけ絶対ちが小さいやつ
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a
                break

        #できるだけ絶対値が大きいやつ
        remain_cand_max_pos=None
        for a in remain:
            if a>=0:
                remain_cand_max_pos=a

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる
        ans_cand_min_pos=None
        remain_cand_max_neg=None

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_neg*remain_cand_max_pos)
            B = abs(ans_cand_min_pos*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg
        else:
            assert 1==2


        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
            else:
                NG=None
print(ans)

Submission status: Runtime Error

Solution code:
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))
    cand=[v for v in absL[:K]]
    
    ans_cand=cand[-K:]
    remain=cand[:-K]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        assert 1==2
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a

        remain_cand_max_pos=None
        for a in remain:
            if a>0:
                remain_cand_max_pos=a

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる
        ans_cand_min_pos=None
        remain_cand_max_neg=None

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a
                break

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_neg*remain_cand_max_pos)
            B = abs(ans_cand_min_pos*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg

        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
print(ans)

Submission status: Runtime Error

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

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

if len(ng)%2 == 0:
    ans = 1
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is not None and b is not None) or (c is not None and d is not None):
    assert False

ans = 1
if a is None or b is None:
    ans = d
    for v in ng[:-1]:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
elif c is None or d is None:
    ans = a
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz[:-1]:
        ans *= v
        ans %= MOD
else:
    if a*c > b*d:
        ans = a
        for v in ng:
            ans *= v
            ans %= MOD
        for v in pz[:-1]:
            ans *= v
            ans %= MOD
    else:
        ans = d
        for v in ng[:-1]:
            ans *= v
            ans %= MOD
        for v in pz:
            ans *= v
            ans %= MOD
ans %= MOD
print(ans)

Submission status: Runtime Error

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

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is not None and b is not None) or (c is not None and d is not None):
    print(ans)
    exit()

if a is None or b is None:
    ans *= d * pow(c,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*c > b*d:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= d * pow(c,-1,MOD)
ans %= MOD
print(ans)

Submission status: Runtime Error

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

if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is not None and b is not None) or (c is not None and d is not None):
    print(ans)
    exit()

if a is None or b is None:
    ans *= d * pow(c,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*c > b*d:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= d * pow(c,-1,MOD)
ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce

mod = 10**9+7

def modcumprod(*args):
    return reduce(lambda x, y: x*y%mod, args)

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

if n == k:
    print(modcumprod(*a))
elif max(a) < 0 and k % 2 == 1:
    a.sort(reverse=True)
    print(modcumprod(*a[:k]))
else:
    a.sort(key=abs, reverse=True)
    res = 1
    cnt_neg = 0
    pos1 = neg1 = 0
    for e in a[:k]:
        res *= e
        res %= mod
        if e > 0:
            pos1 = e
        else:
            cnt_neg += 1
            neg1 = e

    if res == 0 or cnt_neg % 2 == 0:
        print(res)
    else:
        pos2 = neg2 = 0
        for e in a[k:]:
            if e > 0 and not pos2:
                pos2 = e
            elif e < 0 and not neg2:
                neg2 = e
            if pos2 and neg2:
                break
        if abs(pos1 * pos2) < abs(neg1 * neg2):
            res *= pow(pos1, -1, mod)
            res *= neg2
            res %= mod
        else:
            res *= pow(neg1, -1, mod)
            res *= pos2
            res %= mod
        print(res)

Submission status: Runtime Error

Solution code:
from functools import reduce

mod = 10**9+7

def modcumprod(*args):
    return reduce(lambda x, y: x*y%mod, args)

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

if n == k:
    print(modcumprod(*a))
elif max(a) < 0 and k % 2 == 1:
    a.sort(reverse=True)
    print(modcumprod(*a[:k]))
else:
    a.sort(key=abs, reverse=True)
    res = 1
    cnt_neg = 0
    pos1 = neg1 = 0
    for e in a[:k]:
        res *= e
        res %= mod
        if e > 0:
            pos1 = e
        else:
            cnt_neg += 1
            neg1 = e

    if cnt_neg % 2 == 0:
        print(res)
    else:
        pos2 = neg2 = 0
        for e in a[k:]:
            if e > 0 and not pos2:
                pos2 = e
            elif e < 0 and not neg2:
                neg2 = e
            if pos2 and neg2:
                break
        if abs(pos1 * pos2) < abs(neg1 * neg2):
            res *= pow(pos1, -1, mod)
            res *= neg2
            res %= mod
        else:
            res *= pow(neg1, -1, mod)
            res *= pos2
            res %= mod
        print(res)

Submission status: Runtime Error

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

mainasu=[]
purasu=[]
for aa in a:
    if aa>=0:
        purasu.append(aa)
    else:
        mainasu.append(aa*(-1))



mod=10**9+7

#回答がプラスになるケース
if (k<n and len(purasu)>0) or (k<n and k%2==0) or (k==n and len(mainasu)%2==0):
    p_pos=0
    m_pos=0
    mainasu.sort(reverse=True)
    purasu.sort(reverse=True)
    ans=1
    cnt=0
    while cnt<k:
        ans=ans%mod
        #どっちからでも選べる
        if p_pos<len(purasu) and m_pos < len(mainasu):
            #もし最後から2つ目
            if cnt==k-2:
                if p_pos==len(purasu)-1:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
                elif purasu[p_pos]*purasu[p_pos+1]>mainasu[m_pos]*mainasu[m_pos+1]:
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    cnt+=2
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
            else:
                if purasu[p_pos]>mainasu[m_pos+1]:
                    ans=ans*purasu[p_pos]%mod
                    cnt+=1
                    p_pos+=1
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
        elif p_pos<len(purasu):
            ans=ans*purasu[p_pos]%mod
            cnt+=1
            p_pos+=1
        else:
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            cnt+=2
    print(ans%mod)









#回答がマイナスになるケース
else:
    pm=purasu+mainasu
    pm.sort()
    ans=1
    for i in range(k):
        ans=ans*pm[i]%mod
        ans=ans%mod
    #print(-1*ans)
    print((-1*ans)%mod)

Submission status: Runtime Error

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

mainasu=[]
purasu=[]
for aa in a:
    if aa>=0:
        purasu.append(aa)
    else:
        mainasu.append(aa*(-1))



mod=10**9+7

#回答がプラスになるケース
if (k<n and len(purasu)>0) or (k<n and k%2==0) or (k==n and len(mainasu)%2==0):
    p_pos=0
    m_pos=0
    mainasu.sort(reverse=True)
    purasu.sort(reverse=True)
    ans=1
    cnt=0
    while cnt<k:
        #どっちからでも選べる
        if p_pos<len(purasu) and m_pos < len(mainasu):
            #もし最後から2つ目
            if cnt==k-2:
                if p_pos==len(purasu)-1:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
                elif purasu[p_pos]*purasu[p_pos+1]>mainasu[m_pos]*mainasu[m_pos+1]:
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    cnt+=2
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
            else:
                if purasu[p_pos]>mainasu[m_pos+1]:
                    ans=ans*purasu[p_pos]%mod
                    cnt+=1
                    p_pos+=1
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
        elif p_pos<len(purasu):
            ans=ans*purasu[p_pos]%mod
            cnt+=1
            p_pos+=1
        else:
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            cnt+=2
    print(ans%mod)









#回答がマイナスになるケース
else:
    pm=purasu+mainasu
    pm.sort()
    ans=1
    for i in range(k):
        ans=ans*pm[i]%mod
    #print(-1*ans)
    print((-1*ans)%mod)

Submission status: Runtime Error

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

mainasu=[]
purasu=[]
for aa in a:
    if aa>=0:
        purasu.append(aa)
    else:
        mainasu.append(aa*(-1))



mod=10**9+7

#回答がプラスになるケース
if (k<n and len(purasu)>0) or (k<n and k%2==0) or (k==n and len(mainasu)%2==0):
    p_pos=0
    m_pos=0
    mainasu.sort(reverse=True)
    purasu.sort(reverse=True)
    ans=1
    cnt=0
    while cnt<k:
        #どっちからでも選べる
        if p_pos<len(purasu) and m_pos < len(mainasu):
            #もし最後から2つ目
            if cnt==k-2:
                if p_pos==len(purasu)-1:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
                elif purasu[p_pos]*purasu[p_pos+1]>mainasu[m_pos]*mainasu[m_pos+1]:
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    ans*=purasu[p_pos]%mod
                    p_pos+=1
                    cnt+=2
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
            else:
                if purasu[p_pos]>mainasu[m_pos+1]:
                    ans=ans*purasu[p_pos]%mod
                    cnt+=1
                    p_pos+=1
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
        elif p_pos<len(purasu):
            ans=ans*purasu[p_pos]%mod
            cnt+=1
            p_pos+=1
        else:
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            cnt+=2
    print(ans%mod)









#回答がマイナスになるケース
else:
    pm=purasu+mainasu
    pm.sort()
    ans=1
    for i in range(k):
        ans=ans*pm[i]
    #print(-1*ans)
    print((-1*ans)%mod)

Submission status: Runtime Error

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

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is not None and b is not None) or (c is not None and d is not None):
    print(ans)
    exit()

if a is None or b is None:
    ans *= c * pow(d,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*d > b*c:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= c * pow(d,-1,MOD)
ans %= MOD
print(ans)

Submission status: Runtime Error

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

if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is not None and b is not None) or (c is not None and d is not None):
    print(ans)
    exit()

if a is None or b is None:
    ans *= c * pow(d,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*d > b*c:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= c * pow(d,-1,MOD)
ans %= MOD
print(ans)

Submission status: Runtime Error

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

if all(a<0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is not None and b is not None) or (c is not None and d is not None):
    print(ans)
    exit()

if a is None or b is None:
    ans *= c * pow(d,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*d > b*c:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= c * pow(d,-1,MOD)
ans %= MOD
print(ans)

Submission status: Runtime Error

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

if all(a<0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

assert (a is not None and b is not None) or (c is not None and d is not None)

if a is None or b is None:
    ans *= c * pow(d,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*d > b*c:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= c * pow(d,-1,MOD)
ans %= MOD
print(ans)