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 itertools import accumulate as acc

MOD = 10**9 + 7

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

A.sort()

plus_list = []
minus_list = []

zero_count = 0
for a in A:
    # print(a)
    if a > 0:
        plus_list.append(a)
    elif a < 0:
        minus_list.append(a)
    else:
        zero_count += 1

plus_list.sort()
minus_list.sort()

# def solve():
#     # FIX: 大小を比べる方法 or 比べずに解決できる方法
#     plus_list_reverse_acc = [1]
#     for a in plus_list[::-1]:
#         plus_list_reverse_acc.append(
#             (plus_list_reverse_acc[-1] * a) % MOD
#         )
#     minus_list_acc = [1]
#     for a in minus_list:
#         minus_list_acc.append(
#             (minus_list_acc[-1] * a) % MOD
#         )
#     # print(plus_list_reverse_acc, minus_list_acc)
#     r = -(10**18)
#     for minus_count in range(0, K+1, 2):
#         if not (0 <= minus_count <= len(minus_list)):
#             continue
#         plus_count = K-minus_count
#         if not (0 <= plus_count <= len(plus_list)):
#             continue
#         x = (minus_list_acc[minus_count] * plus_list_reverse_acc[plus_count]) % MOD
#         r = max(r, x)
#     return r

def solve():
    # print("A")
    r = 1
    minus_list_reverse = reversed(minus_list)
    minus_pair_list = []
    for i in range(0, len(minus_list), 2):
        if i+1 < len(minus_list):
            x = minus_list[i] * minus_list[i+1]
            minus_pair_list.append(x)
    minus_pair_list.reverse()
    print(plus_list, minus_pair_list)
    q_num = 1
    q_len = 0
    while q_len < K:
        if len(minus_pair_list) == 0 or plus_list[-2]*plus_list[-1] >= minus_pair_list[-1] or q_len + 1 == K:
            # print("{P")
            q_num = (q_num * plus_list.pop()) % MOD
            q_len += 1
            # print(q_len)
        else:
            # print("P")
            q_num = (q_num * minus_pair_list.pop())
            q_len += 2
    return q_num

if plus_list and (not minus_list):
    # print("plus")
    if len(plus_list) < K:
        r = 0
    else:
        r = 1
        for a in plus_list[-K:]:
            # print(r*a)
            r = (r * a) % MOD
        # print(A[-K:], r)
elif (not plus_list) and minus_list:
    # print("minus")
    if K%2 == 1:
        if zero_count:
            r = 0
        else:
            r = 1
            for a in minus_list[-K:]:
                r = (r * a) % MOD
    else:
        if len(minus_list) < K:
            r = 0
        else:
            r = 1
            for a in minus_list[:K]:
                r = (r * a) % MOD
elif (not plus_list) and (not minus_list):
    # print("zero")
    r = 0
else:
    # print("plus minus zero")
    # 2要素以上
    if K == N:
        r = (zero_count == 0)
        for a in plus_list:
            r = (r * a) % MOD
        for a in minus_list:
            r = (r * a) % MOD
    else:
        # K <= N-1:
        # print(zero_count)
        if zero_count:
            # 3要素以上
            if K > N-zero_count:
                r = 0
            elif K == N-zero_count:
                if len(minus_list)%2 == 1:
                    r = 0
                else:
                    r = 1
                    for a in plus_list:
                        r = (r * a) % MOD
                    for a in minus_list:
                        r = (r * a) % MOD
            else:
                r = solve()
        else:
            # 2要素以上 
            r = solve()

print(r)

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    A = list(map(int, input().split()))
    B = [(abs(x), x) for x in A]
    B.sort(reverse=True)
    plus = []
    minus = []

    ans = 1

    if N == K:
        for x in A:
            ans *= x
            ans %= mod
        print(ans)
        return
    minus_count = 0
    for i in range(K):
        if B[i][-1] < 0:
            minus_count += 1
            minus.append(B[i][-1])
        else:
            plus.append(B[i][-1])
        ans *= B[i][-1]
        ans %= mod

    if minus_count % 2 == 0:
        print(ans)
        return

    else:
        if len(plus) > 0 and len(minus) > 0:
            S = 1
            for i in range(len(plus)-1):
                S *= plus[i]
                S %= mod
            for i in range(len(minus)-1):
                S *= minus[i]
                S %= mod
            plus_sub = -1
            minus_sub = -1
            for i in range(K, N):
                if B[i][-1] >= 0:
                    plus_sub = B[i][-1]*plus[-1]
                    break
            for i in range(K, N):
                if B[i][-1] < 0:
                    minus_sub = B[i][-1]*minus[-1]
            print(S*max(plus_sub, minus_sub) % mod)
            return

        else:
            for i in range(K, N):
                if B[i][-1] >= 0:
                    minus.append(B[i][-1])
                    break
            if minus[-1] >= 0:
                res = 1
                for i in range(K-1):
                    res *= minus[i]
                    res %= mod
                res *= mimus[-1]
                print(res % mod)
                return
            else:
                A.sort(reverse=True)
                res = 1
                for i in range(K):
                    res *= A[i]
                    res %= mod
                print(res)
                return


main()

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    A = list(map(int, input().split()))
    B = [(abs(x), x) for x in A]
    B.sort(reverse=True)
    plus = []
    minus = []

    ans = 1

    if N == K:
        for x in A:
            ans *= x
            ans %= mod
        print(ans)
        return
    minus_count = 0
    for i in range(K):
        if B[i][-1] < 0:
            minus_count += 1
            minus.append(B[i][-1])
        else:
            plus.append(B[i][-1])
        ans *= B[i][-1]
        ans %= mod

    if minus_count % 2 == 0:
        print(ans)
        return

    else:
        if len(plus) > 0 and len(minus) > 0:
            S = 1
            for i in range(len(plus)-1):
                S *= plus[i]
                S %= mod
            for i in range(len(minus)-1):
                S *= minus[i]
                S %= mod
            plus_sub = -1
            mimus_sub = -1
            for i in range(K, N):
                if B[i][-1] >= 0:
                    plus_sub = B[i][-1]*plus[-1]
                    break
            for i in range(K, N):
                if B[i][-1] < 0:
                    minus_sub = B[i][-1]*minus[-1]
            print(S*max(plus_sub, minus_sub) % mod)
            return

        else:
            for i in range(K, N):
                if B[i][-1] >= 0:
                    minus.append(B[i][-1])
                    break
            if minus[-1] >= 0:
                res = 1
                for i in range(K-1):
                    res *= minus[i]
                    res %= mod
                res *= mimus[-1]
                print(res % mod)
                return
            else:
                A.sort(reverse=True)
                res = 1
                for i in range(K):
                    res *= A[i]
                    res %= mod
                print(res)
                return


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()))

det = -1###Aのすべての要素が負か否か
for i in range(K):
    if A[i] >= 0:
        det = 1
        break

if det == -1 and K%2 == 1:
    value = 1
    A.sort(reverse = True)
    for i in range(K):
        value *= A[i]
        value %= mod
    print(value)
    sys.exit(0)

A.sort(key = lambda x:abs(x), reverse = True)
#print(A[:(K+1)])

value = 1
sgn = 1
for i in range(K):
    value *= A[i]
    value %= mod
    if A[i] < 0:
        sgn *= -1
    elif A[i] == 0:
        sgn = 0

#print(sgn,value)

if N==K:
    print(value)

elif sgn >=0:
    print(value)
else:
    ###この場合、A[0],...,A[K-1]の中に0はないと断言できることに注意

    X = ['','']###A[K-1],A[K-2],...の中にある絶対値最小の正の数、負の数の絶対値
    num = K
    while (X[0] == '' or X[1] == '') and num > 0:
        num -= 1
        if A[num] > 0 and X[0] != '':
            X[0] = A[num]
        elif A[num] < 0 and X[1] != '':
            X[1] = - A[num]
    
    Y = ['','']###A[K], A[k+1],...の中にある絶対値最大の非負の数、負の数
    ###こちらでは0が登場しないとは言えない
    ###前者にだけ0を入れることでカバー
    num = K-1
    while (Y[0] == '' or Y[1] == '') and num < N-1:
        num += 1
        if A[num] > 0 and Y[0] != '':
            Y[0] = A[num]
        elif A[num] < 0 and Y[1] != '':
            Y[1] = -A[num]
    
    #print(X)
    #print(Y)

    if X[0] != '' and X[1] != '' and Y[0] != '' and Y[1] != '':
        if X[0]*Y[0] >= X[1]*Y[1]:
            value *= Y[0]
            value *= pow(X[1],mod-2,mod)
            value %= mod
            print(value)
        else:
            value *= Y[1]
            value *= pow(X[0],mod-2,mod)
            value %= mod
            print(value)

    elif X[1] != '' and Y[0] != '':
        value *= Y[0]
        value *= pow(X[1],mod-2,mod)
        value %= mod
        print(value)
    
    else:
        value *= Y[1]
        value *= pow(X[0],mod-2,mod)
        value %= mod
        print(value)

Submission status: Runtime Error

Solution code:
import sys

mod = 10**9+7

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

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

det = -1###Aのすべての要素が負か否か
for i in range(K):
    if A[i] >= 0:
        det = 1
        break

if det == -1 and K%2 == 1:
    value = 1
    A.sort(reverse = True)
    for i in range(K):
        value *= A[i]
        value %= mod
    print(value)
    sys.exit(0)

A.sort(key = lambda x:abs(x), reverse = True)

value = 1
sgn = 1
for i in range(K):
    value *= A[i]
    value %= mod
    if A[i] < 0:
        sgn *= -1
    elif A[i] == 0:
        sgn == 0

if N==K:
    print(value)

elif sgn >=0:
    print(value)
else:
    ###この場合、A[0],...,A[K-1]の中に0はないと断言できることに注意

    X = ['','']###A[K-1],A[K-2],...の中にある絶対値最小の正の数、負の数の絶対値
    num = K
    while (X[0] == '' or X[1] == '') and num > 0:
        num -= 1
        if A[num] > 0 and X[0] != '':
            X[0] = A[num]
        elif A[num] < 0 and X[1] != '':
            X[1] = - A[num]
    
    Y = ['','']###A[K], A[k+1],...の中にある絶対値最大の非負の数、負の数
    ###こちらでは0が登場しないとは言えない
    ###前者にだけ0を入れることでカバー
    num = K-1
    while (Y[0] == '' or Y[1] == '') and num < N-1:
        num += 1
        if A[num] > 0 and Y[0] != '':
            Y[0] = A[num]
        elif A[num] < 0 and Y[1] != '':
            Y[1] = -A[num]

    if X[0] != '' and X[1] != '' and Y[0] != '' and Y[1] != '':
        if X[0]*Y[0] >= X[1]*Y[1]:
            value *= Y[0]
            value *= pow(X[1],mod-2,mod)
            value %= mod
            print(value)
        else:
            value *= Y[1]
            value *= pow(X[0],mod-2,mod)
            value %= mod
            print(value)

    elif X[1] != '' and Y[0] != '':
        value *= Y[0]
        value *= pow(X[1],mod-2,mod)
        value %= mod
        print(value)
    
    else:
        value *= Y[1]
        value *= pow(X[0],mod-2,mod)
        value %= mod
        print(value)

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    if (firstA is not None and A[K][0]/A[lastA][0] < A[firstA][0]/A[K-1][0]) or lastA == -1:
        res = prod(A[:K - 1]) * A[firstA][0]
    else:
        res = prod(A[:lastA]) * prod(A[lastA + 1:K + 1])
print(res%MOD)
"""
6 3
5 -3 -3 -3 -3 -2

10 7
-10 -10 -10 -10 10 10 10 10 10 10
"""

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    if firstA is not None and A[K][0]/A[lastA][0] < A[firstA][0]/A[K-1][0]:
        res = prod(A[:K - 1]) * A[firstA][0]
    else:
        res = prod(A[:lastA]) * prod(A[lastA + 1:K + 1])
print(res%MOD)
"""
6 3
5 -3 -3 -3 -3 -2

10 7
-10 -10 -10 -10 10 10 10 10 10 10
"""

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
raise Exception('Error!')
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

5 3
-1 -2 -3 -4 -5
"""

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        raise Exception('Error!')
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

5 3
-1 -2 -3 -4 -5
"""

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
if N==K:
    res = 1
    for a in map(int, input().split()):
        res *= a
        res %= MOD
    print(res)
    exit()
A = []
allsgn = 0
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
    allsgn += a<0
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if allsgn==N:
    if K%2==1:
        raise Exception('Error!')
        print((-prod(A[-K:]))%MOD)
        exit()
    else:
        print(prod(A[:K])%MOD)
        exit()
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

5 3
-1 -2 -3 -4 -5
"""

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N:
    print(-prod(A[-K:])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

3 3
-1 -1 0
"""

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
lasts = s0
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N:
    print(-prod(A[-K:])%MOD)
    exit()
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    print(firstA)
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)
"""
6 4
5 -3 -3 -3 -3 -2

3 3
-1 -1 0
"""

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N:
    print(-prod(A[-K:])%MOD)
    exit()
lasts = s
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0 and lastA == -1:
        lastA = i-1
    s0 = s
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N:
    print(-prod(A[-K:])%MOD)
    exit()
lasts = s
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
print(res%MOD)

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N:
    print(-prod(A[-K:])%MOD)
    exit()
lasts = s
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    firstA = None
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
            break
    res1 = prod(A[:K-1])*A[firstA][0] if firstA is not None else -float("inf")
    res2 = prod(A[:lastA])*prod(A[lastA+1:K+1]) if lastA != -1 else -float("inf")
    res = max(res1, res2)
    print(firstA)
print(res%MOD)

Submission status: Runtime Error

Solution code:
def prod(array):
    res = 1
    for a, _ in array:
        res *= a
        res %= MOD
    return res

MOD = 10**9 + 7
N, K = map(int, input().split())
A = []
for a in map(int, input().split()):
    A.append((abs(a), a < 0))
A.sort(reverse=True)
sgn = 0
s0 = -1
lastA = -1
for i, p in enumerate(A[:K]):
    a, s = p
    sgn += s
    if s != s0:
        lastA = i-1
    s0 = s
if sgn%2==0:
    print(prod(A[:K])%MOD)
    exit()
if sgn + sum(s for _, s in A[K:])==N:
    print(-prod(A[-K:])%MOD)
    exit()
lasts = s
if lasts != A[K][1]:
    res = prod(A[:K-1])*A[K][0]
else:
    for i, p in enumerate(A[K:],start=K):
        a, s = p
        if s != lasts:
            firstA = i
    res = max(prod(A[:lastA])*prod(A[lastA+1:K+1]), prod(A[:K-1])*A[firstA][0])
print(res%MOD)

Submission status: Runtime Error

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

minus = []
plus = []

for i in range(N):
    if(A[i] >= 0):
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True)
minus.sort()
cnt = K
i = 0
j = 0
ans = 1

if(len(plus) == N):
    for i in range(K):
        ans *= plus[i]
        ans %= mod
elif(len(minus) == N):
    c = 0
    for i in minus[::-1]:
        if(c == K):
            break
        ans *= i
        ans %= mod
        c += 1
else:
    while cnt > 0:
        if(j+1 > len(minus)-1):
            ans *= plus[i]
            ans %= mod
            i += 1
            cnt -= 1
        elif(i > len(plus)-1):
            ans *= minus[j]*minus[j+1]
            ans %= mod
            j += 2
            cnt -= 2
        elif(plus[i] > minus[j]*minus[j+1]):
            ans *= plus[i]
            ans %= mod
            i += 1
            cnt -= 1
        else:
            ans *= minus[j]*minus[j+1]
            ans %= mod
            j += 2
            cnt -= 2

print(ans)

Submission status: Runtime Error

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

nums = [int(i) for i in input().split(' ')]

pluses = [n for n in nums if n >= 0]
minuses = [n for n in nums if n < 0]
abs_sorted_pluses = sorted(pluses, key=abs, reverse=True)
abs_sorted_minuses = sorted(minuses, key=abs, reverse=True)

if len(pluses) == 0:
    sorted_minuses = sorted(minuses, key=abs)
    mul = 1
    for i in range(K):
        mul *= sorted_minuses[i]
    print(mul%(10**9+7))
    exit(0)



uses = []
while len(uses) < K:
    
    if len(abs_sorted_minuses) < 2:
        uses.append(abs_sorted_pluses.pop(0))
        continue

    plus = abs_sorted_pluses[0]
    minus = abs_sorted_minuses[0] * abs_sorted_minuses[1]
    if plus > minus:
        uses.append(abs_sorted_pluses.pop(0))
    else:
        uses.append(abs_sorted_minuses.pop(0))
        uses.append(abs_sorted_minuses.pop(0))


mul = 1
for i in range(len(uses)):
    mul *= uses[i]

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

Submission status: Runtime Error

Solution code:
x = list(input().split())
a = list((int(i) for i in input().split()))
n, k = int(x[0]), int(x[1])
#import random
#n = random.choice(range(10000))
#k = random.choice(range(n))
#a = random.choices(range(-1000000, 1000000, 1), k=n)
#print('n =', n, 'k =', k)

MOD = 10**9 + 7

a_abs = []
for i in range(len(a)): a_abs.append(abs(a[i]))

res = sorted(list(zip(a_abs, a)))
val = []
for i in range(len(res)): val.append(res.pop()[1])

# check negative mode
signA, signB, neg = True, False, False
for i in range(len(val)):
    if val[i] < 0:
        signA = not signA
    else:
        signB = True
if (n==k and not signA) or (not signB and k%2 == 1):
    neg = True # answer will be negative

index_replaced, index_replace = None, None
index_replaced_a, index_replace_a = None, None
if (not neg): # positive
    # take top k
    ans = val[0:k]
    sign = True
    for i in range(len(ans)):
        if ans[i] < 0:
            sign = not sign
            
    # replace if necessary
    if (not sign):
        # find smallest negative
        for i in range(len(ans), 0, -1):
            if ans[i-1] < 0:
                index_replaced = i-1
                break
        # find largest positive
        for i in range(k, len(val)):
            if val[i] > 0:
                index_replace = i
                break
        # find smallest positive
        for i in range(len(ans), 0, -1):
            if ans[i-1] > 0:
                index_replaced_a = i-1
                break
        # find largest negative
        for i in range(k, len(val)):
            if val[i] < 0:
                index_replace_a = i
                break

        if index_replaced==None or index_replace==None:
            ans[index_replaced_a] = val[index_replace_a]
        elif index_replaced_a==None or index_replace_a==None:
            ans[index_replaced] = val[index_replace]
        elif (ans[index_replaced]/val[index_replace] > 
            ans[index_replaced_a]/val[index_replace_a]):
            ans[index_replaced] = val[index_replace]
        else:
            ans[index_replaced_a] = val[index_replace_a]

    # multiplication
    result = 1
    for i in range(len(ans)):
        result = (result * ans[i]) % MOD

    print(result)

else: # negative case
    ans = val[len(val)-k:]
    result = 1
    for i in range(len(ans)):
        result = (result * ans[i]) % MOD

    print(result)

Submission status: Runtime Error

Solution code:
x = list(input().split())
a = list((int(i) for i in input().split()))
n, k = int(x[0]), int(x[1])
#import random
#n = random.choice(range(10000))
#k = random.choice(range(n))
#a = random.choices(range(-1000000, 1000000, 1), k=n)
#print('n =', n, 'k =', k)

MOD = 10**9 + 7

a_abs = []
for i in range(len(a)): a_abs.append(abs(a[i]))

res = sorted(list(zip(a_abs, a)))
val = []
for i in range(len(res)): val.append(res.pop()[1])

# check negative mode
signA, signB, neg = True, False, False
for i in range(len(val)):
    if val[i] < 0:
        signA = not signA
    else:
        signB = True
if (n==k and not signA) or (not signB):
    neg = True # answer will be negative

index_replaced, index_replace = None, None
index_replaced_a, index_replace_a = None, None
if (not neg): # positive
    # take top k
    ans = val[0:k]
    sign = True
    for i in range(len(ans)):
        if ans[i] < 0:
            sign = not sign
            
    # replace if necessary
    if (not sign):
        # find smallest negative
        for i in range(len(ans), 0, -1):
            if ans[i-1] < 0:
                index_replaced = i-1
                break
        # find largest positive
        for i in range(k, len(val)):
            if val[i] > 0:
                index_replace = i
                break
        # find smallest positive
        for i in range(len(ans), 0, -1):
            if ans[i-1] > 0:
                index_replaced_a = i-1
                break
        # find largest negative
        for i in range(k, len(val)):
            if val[i] < 0:
                index_replace_a = i
                break

        if index_replaced==None or index_replace==None:
            ans[index_replaced_a] = val[index_replace_a]
        elif index_replaced_a==None or index_replace_a==None:
            ans[index_replaced] = val[index_replace]
        elif (ans[index_replaced]/val[index_replace] > 
            ans[index_replaced_a]/val[index_replace_a]):
            ans[index_replaced] = val[index_replace]
        else:
            ans[index_replaced_a] = val[index_replace_a]

    # multiplication
    result = 1
    for i in range(len(ans)):
        result = (result * ans[i]) % MOD

    print(result)

else: # negative case
    ans = val[len(val)-k:]
    result = 1
    for i in range(len(ans)):
        result = (result * ans[i]) % MOD

    print(result)