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:
import math


def can_plus(PLUSS, MINUSS, K):
    PLUSS = list(reversed(sorted(PLUSS)))
    MINUSS = list(sorted(MINUSS))

    cumul = 1

    plus_idx = 0
    minus_idx = 0

    cnt = 0
    while True:
        if cnt == K:
            break
        elif cnt == K-1:
            cumul = cumul * PLUSS[plus_idx]
            plus_idx += 1
            cnt += 1
        elif (plus_idx <= len(PLUSS) - 3) and (minus_idx <= len(MINUSS) - 2):
            plus_pair = PLUSS[plus_idx] * PLUSS[plus_idx + 1]
            minus_pair = MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            if plus_pair >= minus_pair:
                cumul = cumul * plus_pair
                plus_idx += 2
            else:
                cumul = cumul * minus_pair
                minus_idx += 2
            cnt += 2
        elif minus_idx >= len(MINUSS) - 1:
            cumul = cumul * PLUSS[plus_idx]
            plus_idx += 1
            cnt += 1
        else:
            cumul = cumul * MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            minus_idx += 2
            cnt += 2
    return cumul


def main():
    a = input()
    aa = a.split()
    K = int(aa[1])

    b = input()
    A = [int(bb) for bb in b.split()]

    PLUSS = []
    MINUSS = []
    ZEROS = []
    for a in A:
        if a > 0:
            PLUSS.append(a)
        elif a < 0:
            MINUSS.append(a)
        else:
            ZEROS.append(a)

    # ゼロ以下になることが避けられない場合
    if len(MINUSS) + len(PLUSS) < K:
        print("0")
        return
    elif (len(PLUSS) == 0 or (len(MINUSS) + len(PLUSS) == K)) and (len(MINUSS) % 2) == 1:
        if len(ZEROS) > 0:
            print("0")
            return
        elif len(PLUSS) == 0:
            cumul = 1
            m = list(reversed(sorted(MINUSS)))
            for i in range(K):
                cumul = cumul*m[i]
        else:
            cumul = 1
            for a in A:
                cumul = cumul * a
    else:
        cumul = can_plus(PLUSS, MINUSS, K)

    DIV = 1_000_000_007
    print(cumul % DIV)


main()

Submission status: Runtime Error

Solution code:
import math


def can_plus(PLUSS, MINUSS, K):
    PLUSS = list(reversed(sorted(PLUSS)))
    MINUSS = list(sorted(MINUSS))

    cumul = 1

    plus_idx = 0
    minus_idx = 0

    cnt = 0
    while True:
        if cnt == K:
            break
        elif cnt == K-1:
            cumul = cumul * PLUSS[plus_idx]
            cnt += 1
            break
        elif (plus_idx <= len(PLUSS) - 2) and (minus_idx <= len(MINUSS) - 2):
            plus_pair = PLUSS[plus_idx] * PLUSS[plus_idx + 1]
            minus_pair = MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            if plus_pair >= minus_pair:
                cumul = cumul * plus_pair
                plus_idx += 2
            else:
                cumul = cumul * minus_pair
                minus_idx += 2
            cnt += 2
        elif minus_idx >= len(MINUSS) - 1:
            cumul = cumul * PLUSS[plus_idx]
            cnt += 1
        else:
            cumul = cumul * MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            cnt += 2
    return cumul


def main():
    a = input()
    aa = a.split()
    K = int(aa[1])

    b = input()
    A = [int(bb) for bb in b.split()]

    PLUSS = []
    MINUSS = []
    ZEROS = []
    for a in A:
        if a > 0:
            PLUSS.append(a)
        elif a < 0:
            MINUSS.append(a)
        else:
            ZEROS.append(a)

    # ゼロ以下になることが避けられない場合
    if len(MINUSS) + len(PLUSS) < K:
        print("0")
        return
    elif (len(PLUSS) == 0 or (len(MINUSS) + len(PLUSS) == K)) and (len(MINUSS) % 2) == 1:
        if len(ZEROS) > 0:
            print("0")
            return
        elif len(PLUSS) == 0:
            cumul = 1
            m = list(reversed(sorted(MINUSS)))
            for i in range(K):
                cumul = cumul*m[i]
        else:
            cumul = 1
            for a in A:
                cumul = cumul * a
    else:
        cumul = can_plus(PLUSS, MINUSS, K)

    DIV = 1_000_000_007
    print(cumul % DIV)


main()

Submission status: Runtime Error

Solution code:
import math

def can_plus(PLUSS, MINUSS, K):
    PLUSS = list(reversed(sorted(PLUSS)))
    MINUSS = list(sorted(MINUSS))

    cumul = 1

    plus_idx = 0
    minus_idx = 0

    cnt = 0
    while True:
        if cnt == K:
            break
        elif cnt == K-1:
            cumul = cumul * pluss[plus_idx]
            cnt += 1
            break
        elif (plus_idx <= len(PLUSS) - 2) and (minus_idx <= len(MINUSS) - 2):
            plus_pair = PLUSS[plus_idx] * PLUSS[plus_idx + 1]
            minus_pair = MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            if plus_pair >= minus_pair:
                cumul = cumul * plus_pair
                plus_idx += 2
            else:
                cumul = cumul * minus_pair
                minus_idx += 2
            cnt += 2
        elif minus_idx >= len(MINUSS) - 1:
            cumul = cumul * pluss[plus_idx]
            cnt += 1
        else:
            cumul = cumul * MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            cnt += 2
    return cumul


def main():
    a = input()
    aa = a.split()
    K = int(aa[1])

    b = input()
    A = [int(bb) for bb in b.split()]

    PLUSS = []
    MINUSS = []
    ZEROS = []
    for a in A:
        if a > 0:
            PLUSS.append(a)
        elif a < 0:
            MINUSS.append(a)
        else:
            ZEROS.append(a)

    # ゼロ以下になることが避けられない場合
    if len(MINUSS) + len(PLUSS) < K:
        print("0")
        return
    elif (len(PLUSS) == 0 or (len(MINUSS) + len(PLUSS) == K)) and (len(MINUSS) % 2) == 1:
        if len(ZEROS) > 0:
            print("0")
            return
        elif len(PLUSS) == 0:
            cumul = 1
            m = list(reversed(sorted(MINUSS)))
            for i in range(K):
                cumul = cumul*m[i]
        else:
            cumul = 1
            for a in A:
                cumul = cumul * a
    else:
        cumul = can_plus(PLUSS, MINUSS, K)

    DIV = 1_000_000_007
    print(cumul % DIV)

main()

Submission status: Runtime Error

Solution code:
import math

def can_plus(PLUSS, MINUSS):
    PLUSS = list(reversed(sorted(PLUSS)))
    MINUSS = list(sorted(MINUSS))

    cumul = 1

    plus_idx = 0
    minus_idx = 0

    cnt = 0
    while True:
        if cnt == K:
            break
        elif cnt == K-1:
            cumul = cumul * pluss[plus_idx]
            cnt += 1
            break
        elif (plus_idx <= len(PLUSS) - 2) and (minus_idx <= len(MINUSS) - 2):
            plus_pair = PLUSS[plus_idx] * PLUSS[plus_idx + 1]
            minus_pair = MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            if plus_pair >= minus_pair:
                cumul = cumul * plus_pair
                plus_idx += 2
            else:
                cumul = cumul * minus_pair
                minus_idx += 2
            cnt += 2
        elif minus_idx >= len(MINUSS) - 1:
            cumul = cumul * pluss[plus_idx]
            cnt += 1
        else:
            cumul = cumul * MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            cnt += 2
    return cumul


def main():
    a = input()
    aa = a.split()
    K = int(aa[1])

    b = input()
    A = [int(bb) for bb in b.split()]

    PLUSS = []
    MINUSS = []
    ZEROS = []
    for a in A:
        if a > 0:
            PLUSS.append(a)
        elif a < 0:
            MINUSS.append(a)
        else:
            ZEROS.append(a)

    # ゼロ以下になることが避けられない場合
    if len(MINUSS) + len(PLUSS) < K:
        print("0")
        return
    elif (len(PLUSS) == 0 or (len(MINUSS) + len(PLUSS) == K)) and (len(MINUSS) % 2) == 1:
        if len(ZEROS) > 0:
            print("0")
            return
        elif len(PLUSS) == 0:
            cumul = 1
            m = list(reversed(sorted(MINUSS)))
            for i in range(K):
                cumul = cumul*m[i]
        else:
            cumul = 1
            for a in A:
                cumul = cumul * a
    else:
        cumul = can_plus(PLUSS, MINUSS)

    DIV = 1_000_000_007
    print(cumul % DIV)

main()

Submission status: Runtime Error

Solution code:
import math

def can_plus(PLUSS, MINUSS):
    PLUSS = list(reversed(sorted(PLUSS)))
    MINUSS = list(sorted(MINUSS))

    cumul = 1

    plus_idx = 0
    minus_idx = 0

    cnt = 0
    while True:
        if cnt == K:
            break
        elif cnt == K-1:
            cumul = cumul * pluss[PLUS_IDX]
            cnt += 1
            break
        elif (plus_idx <= len(PLUSS) - 2) and (minus_idx <= len(MINUSS) - 2):
            plus_pair = PLUSS[plus_idx] * PLUSS[plus_idx + 1]
            minus_pair = MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            if plus_pair >= minus_pair:
                cumul = cumul * plus_pair
                plus_idx += 2
            else:
                cumul = cumul * minus_pair
                minus_idx += 2
            cnt += 2
        elif minus_idx >= len(MINUSS) - 1:
            cumul = cumul * pluss[PLUS_IDX]
            cnt += 1
        else:
            cumul = cumul * MINUSS[minus_idx] * MINUSS[minus_idx + 1]
            cnt += 2
    return cumul


def main():
    a = input()
    aa = a.split()
    K = int(aa[1])

    b = input()
    A = [int(bb) for bb in b.split()]

    PLUSS = []
    MINUSS = []
    ZEROS = []
    for a in A:
        if a > 0:
            PLUSS.append(a)
        elif a < 0:
            MINUSS.append(a)
        else:
            ZEROS.append(a)

    # ゼロ以下になることが避けられない場合
    if len(MINUSS) + len(PLUSS) < K:
        print("0")
        return
    elif (len(PLUSS) == 0 or (len(MINUSS) + len(PLUSS) == K)) and (len(MINUSS) % 2) == 1:
        if len(ZEROS) > 0:
            print("0")
            return
        elif len(PLUSS) == 0:
            cumul = 1
            m = list(reversed(sorted(MINUSS)))
            for i in range(K):
                cumul = cumul*m[i]
        else:
            cumul = 1
            for a in A:
                cumul = cumul * a
    else:
        cumul = can_plus(PLUSS, MINUSS)

    DIV = 1_000_000_007
    print(cumul % DIV)

main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    P, M = [], []
    for a in A:
        P.append(a) if a >= 0 else M.append(a)

    res = 1
    if len(P) == n:
        A.sort(reverse=True)
        for i in range(k):
            res = (res * A[i]) % mod
    elif len(M) == n:
        if k % 2:
            A.sort(reverse=True)
        else:
            A.sort()
        res = 1
        for i in range(k):
            res = (res * A[i]) % mod
    else:
        P.sort(reverse=True)
        M.sort()
        B = []
        if k % 2:
            k -= 1
            b = P.pop(0)
            res = (res * b) % mod
        for i in range(0, len(P), 2):
            if i + 1 < len(P):
                B.append(P[i] * P[i + 1])
        for j in range(0, len(M), 2):
            if j + 1 < len(M):
                B.append(M[j] * M[j + 1])
        B.sort(reverse=True)
        for i in range(k // 2):
            res = (res * B[i]) % mod

    print(res)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n:
    if len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    3/0

Submission status: Runtime Error

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif len(pos)==0:
    res=1
    if k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np-1]*neg[k-np-2]):
        np-=2
        if np+len(neg)<k:
            np+=2
            break
    print((ruip[np]*ruin[k-np])%MOD)

Submission status: Runtime Error

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif len(pos)==0:
    res=1
    if k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np-1]*neg[k-np-2]):
        np-=2
        if np+len(neg)<n:
            np+=2
            break
    print((ruip[np]*ruin[k-np])%MOD)

Submission status: Runtime Error

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif len(pos)==0:
    res=1
    if k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
    print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np-1]*neg[k-np-2]):
        np-=2
    print((ruip[np]*ruin[k-np])%MOD)

Submission status: Runtime Error

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


def solve(N, K, A):
    ans = 1
    # K = N の場合は明らか
    if K == N:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    # Ai の全ての数が負かつ K が奇数のとき、
    elif max(A) < 0 and K % 2 == 1:
        A.sort(reverse=True)
        # 絶対値が小さい方から K 個の積
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    # それ以外の場合、積は必ず非負
    else:
        # {Ai} を絶対値の降順にソート
        A.sort(key=abs, reverse=True)
        # 最初の K 個の積
        sign = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
            if A[i] < 0:
                sign *= -1
            elif A[i] == 0:
                sign *= 0
        # P が負の場合
        if sign < 0:
            small_nonneg = [a for a in A[K:] if a >= 0]
            small_neg = [a for a in A[K:] if a < 0]
            large_nonneg = [a for a in A[:K] if a >= 0]
            large_neg = [a for a in A[:K] if a < 0]
            if not small_neg:
                ans *= max(small_nonneg)
                ans %= MOD
                ans *= pow(max(large_neg), MOD - 2, MOD)
                ans %= MOD
            elif not small_nonneg:
                ans *= min(small_neg)
                ans %= MOD
                ans *= pow(min(large_nonneg), MOD - 2, MOD)
                ans %= MOD
            else:
                if min(small_neg) * max(large_neg) > max(small_nonneg) * min(
                    large_nonneg
                ):
                    # (2) 正の数を 1 つ取り除き、負の数を 1 つ加える
                    ans *= min(small_neg)
                    ans %= MOD
                    ans *= pow(min(large_nonneg), MOD - 2, MOD)
                    ans %= MOD
                else:
                    # (1) 負の数を 1 つ取り除き、非負の数を 1 つ加える
                    ans *= max(small_nonneg)
                    ans %= MOD
                    ans *= pow(max(large_neg), MOD - 2, MOD)
                    ans %= MOD
    return ans


print(solve(N, K, A))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:#kは奇数
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:#kは偶数
  if n%2 == 0:#nは偶数
    A = n//2
    a_new = [a[2*i]*a[2*i+1] for i in range(A)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:#nは奇数
    a_plus =[]
    a_minus = []
    pos = 0
    neg = 0
    for i in range(n):
      if a[i] > 0 :
        a_plus.append(a[i])
        pos += 1
      if a[i] < 0 :
        a_minus.append(a[i])
        neg += 1
    if k > pos + neg :
      ans = 0
    print(ans % w)
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(pos//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(neg//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:#kは奇数
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:#kは偶数
  if n%2 == 0:#nは偶数
    A = n//2
    a_new = [a[2*i]*a[2*i+1] for i in range(A)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:#nは奇数
    a_plus =[]
    a_minus = []
    pos = 0
    neg = 0
    for i in range(n):
      if a[i] > 0 :
        a_plus.append(a[i])
        pos += 1
      if a[i] < 0 :
        a_minus.append(a[i])
        neg += 1
    if k > pos + neg :
      print(0)
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(pos//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(neg//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:#kは奇数
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:#kは偶数
  if n%2 == 0:#nは偶数
    A = n//2
    a_new = [a[2*i]*a[2*i+1] for i in range(A)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:#nは奇数
    a_plus =[]
    a_minus = []
    pos = 0
    neg = 0
    for i in range(n):
      if a[i] > 0 :
        a_plus.append(a[i])
        pos += 1
      else :
        a_minus.append(a[i])
        neg += 1
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(pos//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(neg//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= (a_new[j]%mod)
    print(ans % w)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:#kは奇数
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:#kは偶数
  if n%2 == 0:#nは偶数
    A = n//2
    a_new = [a[2*i]*a[2*i+1] for i in range(A)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:#nは奇数
    a_plus =[]
    a_minus = []
    pos = 0
    neg = 0
    for i in range(n):
      if a[i] > 0 :
        a_plus.append(a[i])
        pos += 1
      if a[i] < 0 :
        a_minus.append(a[i])
        neg += 1
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(pos//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(neg//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:#kは奇数
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:#kは偶数
  if n%2 == 0:#nは偶数
    for i in range(k):
      ans *= a_new[i]
    print(ans % w)
      
  else:#nは奇数
    a_plus =[]
    a_minus = []
    for i in range(n):
      if a[i] >= 0 :
        a_plus.append(a[i])
      else:
        a_minus.append(a[i])
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(len(a_plus)//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(len(a_minus)//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:
  if n%2 == 0:
    A = n//2
    a_new = [a[2*i]*a[2*i+1] for i in range(A)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:
    a_plus = heapq.nlargest(k, a)
    a_minus = heapq.nsmallest(k, a)
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(len(a_plus)//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(len(a_minus)//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(revserse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:
  if n%2 == 0:
    A = n//2
    a_new = [a[2*i]*a[2*i+1] for i in range(A-2)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:
    a_plus = heapq.nlargest(k, a)
    a_minus = heapq.nsmallest(k, a)
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(len(a_plus)//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(len(a_minus)//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(revserse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:
  if n%2 == 0:
    A = n//2
    a_new = [a[2*i]*a[2*i+1] for i in range(A-1)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:
    a_plus = heapq.nlargest(k, a)
    a_minus = heapq.nsmallest(k, a)
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(len(a_plus)//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(len(a_minus)//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(revserse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:
  if n%2 == 0:
    a_new = [a[2*i]*a[2*i+1] for i in range(n//2)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:
    a_plus = heapq.nlargest(k, a)
    a_minus = heapq.nsmallest(k, a)
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(len(a_plus)//2)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(len(a_minus)//2)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(revserse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:
  if n%2 == 0:
    a_new = [a[2*i]*a[2*i+1] for i in range(n//2)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:
    a_plus = heapq.nlargest(k, a)
    a_minus = heapq.nsmallest(k, a)
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(len(a_plus)-1)]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(len(a_minus)-1)]
    a_new = a_plus_new + a_minus_new
    a_new.sort(revserse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort(reverse = True)
w = 10**9 + 7
ans = 1
if k%2 == 1:
  for i in range(k):
    ans *= a[i]
  print(ans % w)

else:
  if n%2 == 0:
    a_new = [a[2*i]*a[2*i+1] for i in range(n//2)]
    a_new.sort(reverse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)
      
  else:
    a_plus = heapq.nlargest(k, a)
    a_minus = heapq.nsmallest(k, a)
    a_plus.sort(reverse = True)
    a_minus.sort()
    a_plus_new = [a_plus[2*i]*a_plus[2*i+1] for i in range(len(a_plus))]
    a_minus_new = [a_minus[2*i]*a_minus[2*i+1] for i in range(len(a_minus))]
    a_new = a_plus_new + a_minus_new
    a_new.sort(revserse = True)
    for j in range(k//2):
      ans *= a_new[j]
    print(ans % w)