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: Wrong Answer

Solution code:
from heapq import heappush, heappop


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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできるので、絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    # 候補テーブルを作成
    A1 = []  # 非負要素のリスト
    A2 = []  # 負要素を絶対値の大きい順に2つずつ掛けたリスト
    tmp = 1
    for a in A:
        if a >= 0:
            heappush(A1, -a)
        else:
            if tmp != 1:
                heappush(A2, -tmp*a)
                tmp = 1
            else:
                tmp *= a

    # cost が K を上回らなように大きいものから埋めていく〜
    cost = 0
    ans = 1
    while cost < K:
        if (K - cost) >= 2:
            # このときは A2 からも入れてよし
            if A1 and A2:
                if -A1[0] >= -A2[0]:
                    cost += 1
                    ans *= -heappop(A1)
                else:
                    cost += 2
                    ans *= -heappop(A2)
            elif A1:
                cost += 1
                ans *= -heappop(A1)
            else:
                cost += 2
                ans *= -heappop(A2)
            ans %= MOD
        else:
            cost += 1
            ans *= -heappop(A1)
            ans %= MOD

    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop


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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできるので、絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    # 候補テーブルを作成
    A1 = []  # 非負要素のリスト
    A2 = []  # 負要素を絶対値の大きい順に2つずつ掛けたリスト
    tmp = 1
    for a in A:
        if a >= 0:
            heappush(A1, -a)
        else:
            if tmp != 1:
                heappush(A2, tmp*a)
                tmp = 1
            else:
                tmp *= a

    # cost が K を上回らなように大きいものから埋めていく〜
    cost = 0
    ans = 1
    while cost < K:
        if (K - cost) >= 2:
            # このときは A2 からも入れてよし
            if A1 and A2:
                if A1[0] >= A2[0]:
                    cost += 1
                    ans *= -heappop(A1)
                else:
                    cost += 2
                    ans *= -heappop(A2)
            elif A1:
                cost += 1
                ans *= -heappop(A1)
            else:
                cost += 2
                ans *= -heappop(A2)
            ans %= MOD
        else:
            cost += 1
            ans *= -heappop(A1)
            ans %= MOD

    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

P = deque(sorted(P, key=lambda a: abs(a)))
N = deque(sorted(N, key=lambda a: abs(a)))

ans = 1
M = K
while M > 0:
    if M == 1:
        if ans >= 0:
            if P: ans *= P.pop()
            else: ans *= N.popleft()
        else:
            if N: ans *= N.pop()
            else: ans *= P.popleft()
        break
    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        M -= 2
    elif len(P) >= 2 and len(N) <= 1:
        ans *= P.pop() * P.pop()
        M -= 2
    else:
        if len(P) >= 1:
            ans *= P.pop()
        else:
            ans *= N.popleft()
        M -= 1
    ans %= MOD

if ans < 0:
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    if N == K:
        ans = 1
        for i in range(N):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return

    B = []
    all_m = True
    cnt_z = 0
    for a in A:
        if a > 0:
            B.append((a,1))
            all_m = False
        elif a < 0:
            B.append((a,-1))
        else:
            B.append((a,0))
            all_m = False
            cnt_z += 1
    
    if all_m:
        if K%2 == 1:
            ans = 1
            B.sort(key = lambda x:x[0],reverse = True)
            for i in range(K):
                ans *= B[i][0]
                ans %= MOD
            print(ans)
            return  
    
    B.sort(key = lambda x:abs(x[0]),reverse = True)
    ans = 1
    cnt_m = 0
    last_m = 1
    last_p = -1
    for i,(b,typ) in enumerate(B):
        if i >= K:
            break
        if typ == 0:
            ans = 0
            print(ans)
            return
        elif typ > 0:
            ans *= b
            ans %= MOD
            last_p = b
        else:
            ans *= b
            ans %= MOD
            cnt_m += 1
            last_m = b

    if cnt_m%2 == 0:
        print(ans)
    else:
        if last_p > 0:
            diff1 = last_p
        else:
            diff1 = -INF
        diff2 = last_m
        inv1 = 1
        inv2 = 1

        find1 = False
        inv1 *= pow(last_m,MOD - 2,MOD)
        for j in range(K,N):
            if B[j][1] > 0:
                if diff1 > 0:
                    find1 = True
                    diff1 *= B[j][0]
                    inv1 *= B[j][0]
                    inv1 %= MOD
                else:
                    find1 = False
                break
        
        find2 = False
        inv2 *= pow(last_p,MOD - 2,MOD)
        for j in range(K,N):
            if B[j][1] < 0:
                find2 = True
                diff2 *= B[j][0]
                inv2 *= B[j][0]
                inv2 %= MOD
                break
            
        if find1 and find2:
            if diff1 > diff2:
                ans *= inv1
                ans %= MOD
            else:
                ans *= inv2
                ans %= MOD
        elif find1:
            ans *= inv1
            ans %= MOD
        elif find2:
            ans *= inv2
            ans %= MOD
        else:
            ans = 0
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    if N == K:
        ans = 1
        for i in range(N):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return

    B = []
    all_m = True
    cnt_z = 0
    for a in A:
        if a > 0:
            B.append((a,1))
            all_m = False
        elif a < 0:
            B.append((a,-1))
        else:
            B.append((a,0))
            all_m = False
            cnt_z += 1
    
    if all_m:
        if K%2 == 1:
            ans = 1
            B.sort(key = lambda x:x[0],reverse = True)
            for i in range(K):
                ans *= B[i][0]
                ans %= MOD
            print(ans)
            return  
    
    B.sort(key = lambda x:abs(x[0]),reverse = True)
    ans = 1
    cnt_m = 0
    last_m = 1
    last_p = -1
    for i,(b,typ) in enumerate(B):
        if i >= K:
            break
        if typ == 0:
            ans = 0
            print(ans)
            return
        elif typ > 0:
            ans *= b
            ans %= MOD
            last_p = b
        else:
            ans *= b
            ans %= MOD
            cnt_m += 1
            last_m = b

    if cnt_m%2 == 0:
        print(ans)
    else:
        if last_p > 0:
            diff1 = last_p
        else:
            diff1 = -10000000000
        diff2 = last_m
        inv1 = 1
        inv2 = 1

        find = False
        inv1 *= pow(last_m,MOD - 2,MOD)
        for j in range(K,N):
            if B[j][1] > 0:
                find = True
                diff1 *= B[j][0]
                inv1 *= B[j][0]
                inv1 %= MOD
                break
            if j == N - 1:
                diff1 = -10000000000

        inv2 *= pow(last_p,MOD - 2,MOD)
        for j in range(K,N):
            if B[j][1] < 0:
                find = True
                diff2 *= B[j][0]
                inv2 *= B[j][0]
                inv2 %= MOD
                break
            if j == N - 1:
                diff2 = -10000000000
        if find:
            if diff1 > diff2:
                ans *= inv1
                ans %= MOD
            else:
                ans *= inv2
                ans %= MOD
        else:
            if B[-1][0] == 0:
                ans = 0
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできるので、絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    # 候補テーブルを作成
    A1 = []  # 非負要素のリスト（降順）
    A2 = []  # 負要素を絶対値の大きい順に2つずつ掛けたリスト（降順）
    tmp = 1
    for a in A:
        if a >= 0:
            A1.append(a)
        else:
            if tmp != 1:
                A2.append(tmp*a)
                tmp = 1
            else:
                tmp *= a

    # cost が K を上回らなように大きいものから埋めていく〜
    cost = 0
    ans = 1
    while cost < K:
        if (K - cost) >= 2:
            # このときは A2 からも入れてよし
            if A1 and A2:
                if A1[0] >= A2[0]:
                    cost += 1
                    ans *= A1.pop(0)
                else:
                    cost += 2
                    ans *= A2.pop(0)
            elif A1:
                cost += 1
                ans *= A1.pop(0)
            else:
                cost += 2
                ans *= A2.pop(0)
            ans %= MOD
        else:
            cost += 1
            ans *= A1.pop(0)
            ans %= MOD

    print(ans)

Submission status: Wrong Answer

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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt = cnt * mia.pop()
            elif len(pla) > 0:
                cnt = cnt * pla.pop()
            k -= 1
        elif len(pla) <= 1:
            cnt = cnt * mia.pop() * mia.pop()
            k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop()
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop()
                k -= 2
        cnt %= mod
print(cnt)

Submission status: Wrong Answer

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt *= i
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt *= mia.pop()
            elif len(pla) > 0:
                cnt *= pla.pop()
            k -= 1
        elif len(pla) <= 1:
            cnt *= mia.pop() * mia.pop()
            k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt *= pla.pop()
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt *= mia.pop() * mia.pop()
                k -= 2
        cnt %= mod
print(cnt)

Submission status: Wrong Answer

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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできるので、絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    # とりあえず大きい順に K 個掛けてみる
    ans = 1
    for i in range(K):
        ans *= A[i]
    if ans >= 0:
        ans %= MOD
        print(ans)
    else:
        # 取り除く対象を old, 取り込む対象を new とする
        new1, new2, old1, old2 = float("inf"), float("inf"), float("inf"), float("inf")
        cand1, cand2 = float("inf"), float("inf")
        # case3-1. 負数を取り除いて非負数を取り込む
        # まずは new を探す
        j = K
        while j < N and A[j] < 0:
            j += 1
        if j < N:
            new1 = A[j]
        # old を探す
        l = K-1
        while A[l] >= 0:
            l -= 1
        old1 = A[l]
        if new1 != float("inf") and old1 != float("inf"):
            cand1 = ans // old1 * new1
        # case3-2. 非負数を取り除いて負数を取り込む
        # まずは new を探す
        j = K
        while j < N and A[j] >= 0:
            j += 1
        if j < N:
            new2 = A[j]
        # old を探す
        l = K-1
        while A[l] < 0:
            l -= 1
        old2 = A[l]
        if new2 != float("inf") and old2 != float("inf"):
            cand2 = ans // old2 * new2

        if cand1 != float("inf") and cand2 != float("inf"):
            ans = max(cand1, cand2) % MOD
        elif cand1 != float("inf"):
            ans = cand1 % MOD
        else:
            ans = cand2 % MOD
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, K = inm()
A = inl()
B = [(abs(a), a < 0) for a in A]
B.sort(reverse=True)

MOD = 10 ** 9 + 7


def solve():
    fs = []
    negmin = posrep = None
    posmin = negrep = None
    negcnt = 0
    for i in range(N):
        v, neg = B[i]
        if len(fs) < K:
            fs.append(v)
            if neg:
                negcnt += 1
                negmin = v
            else:
                posmin = v
        elif neg and negrep is None:
            negrep = v
        elif not neg and posrep is None:
            posrep = v
    if negcnt % 2 == 0:
        a0 = 1
        for x in fs:
            a0 = (a0 * x) % MOD
        return a0

    a1 = a2 = None
    if negmin is not None and posrep is not None:
        a1 = 1
        for x in fs:
            if x == negmin:
                a1 = (a1 * posrep) % MOD
            else:
                a1 = (a1 * x) % MOD
    if posmin is not None and negrep is not None:
        a2 = 1
        for x in fs:
            if x == posmin:
                a2 = (a2 * negrep) % MOD
            else:
                a2 = (a2 * x) % MOD

    if a1 is None and a2 is None:
        a3 = 1
        for (x, neg) in list(reversed(B))[:K]:
            if neg:
                a3 *= x
            else:
                a3 *= x
            a3 %= MOD
        return (MOD - a3) % MOD

    if a1 is None:
        return a2
    if a2 is None:
        return a1

    if posrep * posmin < negrep * negmin:
        return a2
    else:
        return a1


print(solve())

Submission status: Wrong Answer

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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
else:
    while k > 0:
        if k == 1 or len(mia) <= 1:
            if len(pla) == 0:
                cnt = cnt * mia.pop() % mod
            elif len(pla) > 0:
                cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) <= 1:
            if k == 1:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif k > 1:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and len([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max*positive_big_min < negative_small_min*negative_big_max:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    if N == K:
        ans = 1
        for i in range(N):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return

    B = []
    all_m = True
    cnt_z = 0
    cnt_m = 0
    for a in A:
        if a > 0:
            B.append((a,1))
            all_m = False
        elif a < 0:
            B.append((a,-1))
            cnt_m += 1
        else:
            B.append((a,0))
            all_m = False
            cnt_z += 1
    
    if all_m:
        if K%2 == 1:
            ans = 1
            B.sort(key = lambda x:x[0],reverse = True)
            for i in range(K):
                ans *= B[i][0]
                ans %= MOD
            print(ans)
            return  
    
    B.sort(key = lambda x:abs(x[0]),reverse = True)
    ans = 1
    cnt_m = 0
    last_m = 1
    last_p = -1
    for i,(b,typ) in enumerate(B):
        if i >= K:
            break
        if typ == 0:
            ans = 0
            break
        elif typ > 0:
            ans *= b
            ans %= MOD
            last_p = b
        else:
            ans *= b
            ans %= MOD
            cnt_m += 1
            last_m = b

    if cnt_m%2 == 0 or ans == 0:
        print(ans)
    else:
        if last_p > 0:
            diff1 = last_p
        else:
            diff1 = -10000000000
        diff2 = -last_m
        inv1 = 1
        inv2 = 1

        find = False
        inv1 *= pow(last_m,MOD - 2,MOD)
        for j in range(K,N):
            if B[j][1] > 0:
                find = True
                diff1 *= B[j][0]
                inv1 *= B[j][0]
                inv1 %= MOD
                break
            if j == N - 1:
                diff1 = -1000000000

        inv2 *= pow(last_p,MOD - 2,MOD)
        for j in range(K,N):
            if B[j][1] < 0:
                find = True
                diff2 *= -B[j][0]
                inv2 *= B[j][0]
                inv2 %= MOD
                break
            if j == N - 1:
                diff2 = -10000000000
        if find:
            if diff1 > diff2:
                ans *= inv1
                ans %= MOD
            else:
                ans *= inv2
                ans %= MOD
        else:
            if B[-1][0] == 0:
                ans = 0
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
    print(cnt)
else:
    while k > 0:
        if len(mia) <= 1:
            if len(pla) == 0:
                cnt = cnt * mia.pop() % mod
            elif len(pla) > 0:
                cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) <= 1:
            if k == 1:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif k > 1:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
    else:
        print(cnt)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    mod = 10**9 + 7
    p = 1
    if n == k:
        for ai in a:
            p = p * ai % mod
        print(p)
        return
    if a[0] < 0 and k % 2:
        for ai in a[:k]:
            p = p * ai % mod
        print(p)
        return
    b = sorted([(abs(ai), ai) for ai in a], reverse=True)
    s = 0
    for ba, bb in b[:k]:
        p = p * ba % mod
        if bb < 0:
            s += 1
    if s % 2 == 0:
        print(p)
        return
    pa, na, pb, nb = [-1] * 4
    for ba, bb in b[:k]:
        if bb < 0:
            na = ba
        else:
            pa = ba
    for ba, bb in b[k:][::-1]:
        if bb < 0:
            nb = ba
        else:
            pb = ba
    if pa == -1 or nb == -1:
        print((p * pb % mod) * pow(na, mod - 2, mod) % mod)
    elif pb == -1 or na == -1:
        print((p * nb % mod) * pow(pa, mod - 2, mod) % mod)
    elif pb / na > nb / pa:
        print((p * pb % mod) * pow(na, mod - 2, mod) % mod)
    else:
        print((p * nb % mod) * pow(pa, mod - 2, mod) % mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    mod = 10**9 + 7
    p = 1
    if n == k:
        for ai in a:
            p = p * ai % mod
        print(p)
        return
    if a[0] < 0 and k % 2:
        for ai in a[:k]:
            p = p * ai % mod
        print(p)
        return
    b = sorted([(abs(ai), ai) for ai in a], reverse=True)
    s = 0
    for ba, bb in b[:k]:
        p = p * bb % mod
        if ba < 0:
            s += 1
    if s % 2 == 0:
        print(p)
        return
    pa, na, pb, nb = [-1] * 4
    for ba, bb in b[:k]:
        if bb < 0:
            na = ba
        else:
            pa = ba
    for ba, bb in b[k:][::-1]:
        if bb < 0:
            nb = ba
        else:
            pb = ba
    if pa == -1 or nb == -1:
        print((p * pb % mod) * pow(na, mod - 2, mod) % mod)
    elif pb == -1 or na == -1:
        print((p * nb % mod) * pow(pa, mod - 2, mod) % mod)
    elif pb / na > nb / pa:
        print((p * pb % mod) * pow(na, mod - 2, mod) % mod)
    else:
        print((p * nb % mod) * pow(pa, mod - 2, mod) % mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
    print(cnt)
else:
    while k > 0:
        if len(mia) <= 1:
            if len(pla) == 0:
                cnt = cnt * mia.pop() % mod
            elif len(pla) > 0:
                cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) <= 1:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
    else:
        print(cnt)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    mod = 10**9 + 7
    p = 1
    if n == k:
        for ai in a:
            p = p * ai % mod
        print(p)
        return
    if a[0] < 0 and k % 2:
        for ai in a[:k]:
            p = p * ai % mod
        print(p)
        return
    b = sorted([(abs(ai), ai) for ai in a], reverse=True)
    for _, bi in b[:k]:
        p = p * bi % mod
    if p >= 0:
        print(p)
        return
    pa, na, pb, nb = [-1] * 4
    for _, bi in b[:k]:
        if bi < 0:
            na = bi
        else:
            pa = bi
    for _, bi in b[k:][::-1]:
        if bi < 0:
            nb = bi
        else:
            pb = bi
    if pa == -1 or nb == -1:
        print((p * pb % mod) * pow(na, mod - 2, mod) % mod)
    elif pb == -1 or na == -1:
        print((p * nb % mod) * pow(pa, mod - 2, mod) % mod)
    elif pb / na > nb / pa:
        print((p * pb % mod) * pow(na, mod - 2, mod) % mod)
    else:
        print((p * nb % mod) * pow(pa, mod - 2, mod) % mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    mod = 10**9 + 7
    p = 1
    if n == k:
        for ai in a:
            p = p * ai % mod
        print(p)
        return
    if a[0] < 0 and k % 2:
        for ai in a[:k]:
            p = p * ai % mod
        print(p)
        return
    b = sorted([(abs(ai), ai) for ai in a], reverse=True)
    for _, bi in b[:k]:
        p = p * bi % mod
    if p >= 0:
        print(p)
        return
    pa, na, pb, nb = [-1] * 4
    for bi, _ in b[:k]:
        if bi < 0:
            na = bi
        else:
            pa = bi
    for bi, _ in b[k:][::-1]:
        if bi < 0:
            nb = bi
        else:
            pb = bi
    if pa == -1 or nb == -1:
        print((p * pb % mod) * pow(na, mod - 2, mod) % mod)
    elif pb == -1 or na == -1:
        print((p * nb % mod) * pow(pa, mod - 2, mod) % mod)
    elif pb / na > nb / pa:
        print((p * pb % mod) * pow(na, mod - 2, mod) % mod)
    else:
        print((p * nb % mod) * pow(pa, mod - 2, mod) % mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
n, k = map(int, input().split())
A = [*map(int, input().split())]

B = []
for a in A:
    B.append((abs(a), ([0,1][a<0])))
B.sort(reverse=True)

ss = [0]*(n+1)
for i in range(n):
    ss[i+1] = ss[i] + B[i][1]

# print(n,k)
# print(A)
# print(B)
# print(ss)
# print('---')

mx_ix_pr = [0, 0]
for i in range(k,n+1):
    if (ss[i]-ss[i-k])%2 == 0:
        mx_ix_pr[0] = i-k
        mx_ix_pr[1] = i
        break

mn_ix_pr = [0, 0]
for i in range(n,k-1,-1):
    if (ss[i]-ss[i-k])%2 == 1:
        mn_ix_pr[0] = i-k
        mn_ix_pr[1] = i
        break

# print(mx_ix_pr)
# print(mn_ix_pr)

mx_flag = False
mx_ans = 1
for i in range(mx_ix_pr[0],mx_ix_pr[1]):
    mx_ans *= B[i][0]
    mx_ans %= mod
    mx_flag = True

mn_flag = False
mn_ans = 1
for i in range(mn_ix_pr[0],mn_ix_pr[1]):
    mn_ans *= B[i][0]
    mn_ans %= mod
    mn_flag = True

# print(mx_ans)
# print(mn_ans)

if mx_flag:
    mx_ans += mod
    mx_ans %= mod
    print(mx_ans)
else:
    mn_ans *= -1
    mn_ans %= mod
    mn_ans += mod
    mn_ans %= mod
    print(mn_ans)