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:
# Contest No.: ABC173
# Problem No.: E
# Solver:      JEMINI
# Date:        20200705

import sys
import heapq

def main():
    modVal = 10 ** 9 + 7
    n, k = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    
    if max(nums) == 0:
        print(0)
        return
    elif max(nums) < 0:
        nums.sort()
        ans = 1
        for i in range(k):
            ans *= nums[-i - 1] % modVal
            ans %= modVal
        print(ans)
        return
    
    absNums = []
    zeroCnt = 0
    for i in nums:
        if i == 0:
            zeroCnt += 1
        else:
            absNums.append([abs(i), i])
    absNums.sort()
    
    if len(absNums) < k:
        print(0)
        return

    posOverK = []
    posLessK = []
    negOverK = []
    negLessK = []
    for i in range(k):
        temp = absNums.pop()
        if temp[1] > 0:
            posOverK.append(temp[0])
        else:
            negOverK.append(temp[0])
    while absNums:
        temp = absNums.pop()
        if temp[1] > 0:
            posLessK.append(temp[0])
        else:
            negLessK.append(temp[0])
    
    # all values are abs val
    posOverK.sort()
    posLessK.sort()
    negOverK.sort()
    negLessK.sort()
    
    ans = 1

    # odd negative numbers
    if len(negOverK) % 2:
        minNeg = None
        minPos = None
        if posOverK:
            minPos = posOverK[0]
        if negOverK:
            minNeg = negOverK[0]

        maxNeg = None
        maxPos = None
        if posLessK:
            maxPos = posLessK[0]
        if negLessK:
            maxNeg = negLessK[0]
        
        if (minNeg and maxPos) and (minPos and maxNeg):
            if maxPos / minNeg > maxNeg / minPos:
                negOverK[0] = maxPos
            else:
                posOverK[0] = maxNeg
        elif (not minNeg or not maxPos) and (minPos and maxNeg):
            posOverK[0] = maxNeg
        elif (minNeg and maxPos) and (not minPos or not maxNeg):
            negOverK[0] = maxPos
        elif zeroCnt:
            ans = 0
        

    # even negative numbers; not need to fix
    else:
        for i in posOverK:
            ans *= i % modVal
            ans = ans % modVal
        for i in negOverK:
            ans *= i % modVal
            ans = ans % modVal
    
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, k = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
MOD = 10**9 + 7
P = []
M = []
Z = []
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        Z.append(a)
P.sort()
M.sort(reverse=True)
lp = len(P)
lm = len(M)
lz = len(Z)

# どうしてもマイナスになるとき
if (lp + lm < k) or (lm == n and k % 2 == 1):
    if lz > 0:
        print(0)
        exit()
    else:
        tmp = 1
        M.sort(reverse=True)
        for m in M[:k]:
            tmp *= -m
            tmp %= MOD
        if tmp == 0:
            print(0)
        else:
            print(MOD - tmp)
        exit()

if lp + lm == k and lm % 2 == 1:
    if lz > 0:
        print(0)
        exit()
    else:
        tmp = 1
        P += [-m for m in M]
        for p in P:
            tmp *= p
            tmp %= MOD
        print(-tmp % MOD)
        exit()

# プラスにできそうなとき
ans = 1
pindex = lp - 1
mindex = lm - 1
for _ in range(k // 2):
    if pindex > 0 and mindex > 0:
        p = P[pindex] * P[pindex - 1]
        m = M[mindex] * M[mindex - 1]
        if p > m:
            ans *= p
            ans %= MOD
            pindex -= 2
        else:
            ans *= m
            ans %= MOD
            mindex -= 2
    else:
        if pindex > 0:
            ans *= P[pindex] * P[pindex - 1]
            ans %= MOD
            pindex -= 2
        elif mindex > 0:
            ans *= M[mindex] * M[mindex - 1]
            ans %= MOD
            mindex -= 2

if k % 2 == 0:
    print(ans)
    exit()
else:
    if pindex >= 0:
        ans *= P[pindex]
        ans %= MOD
        print(ans)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import sys
from math import log2
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N, K = MAP()
A = LIST()

A1 = []
A2 = []
B1 = []
B2 = []
zero = 0
for a in A:
    if a > 0:
        A1.append(a)
        B1.append(log2(a))
    elif a < 0:
        A2.append(-a)
        B2.append(log2(-a))
    else:
        zero += 1

A1.sort()
A2.sort()
B1.sort()
B2.sort()
acc1 = [0] + list(accumulate(B1))
accrev1 = [0] + list(accumulate(B1[::-1]))
acc2 = [0] + list(accumulate(B2))
accrev2 = [0] + list(accumulate(B2[::-1]))
mx = -INF
mn = INF
idx1 = (-1, -1)
idx2 = (-1, -1)
for i in range(K+1):
    j = K - i
    if len(B1) < i or len(B2) < j:
        continue
    if j % 2 == 0:
        sm = accrev1[i] + accrev2[j]
        if sm + EPS > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn + EPS:
            mn = sm
            idx2 = (i, j)

if mx != -INF:
    ans = 1
    n, m = idx1
    A1.reverse()
    A2.reverse()
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)
elif zero:
    print(0)
else:
    ans = 1
    n, m = idx2
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))
    MOD = 10**9+7

    B = []
    flg_m = 0
    flg_p = 0
    for a in A:
        if a < 0:
            B.append([abs(a),-1])
            flg_m = 1
        else:
            B.append([abs(a),1])
            flg_p = 1

    B.sort(reverse=True)
    if flg_p == 0 and k%2 == 1:
        B.sort()
        L = B[:k]
        ans = cal_ans(L)
        ans *=-1
        print(ans%MOD)
        exit()
    elif flg_p * flg_m == 0:
        L = B[:k]
        ans = cal_ans(L)
        print(ans)
        exit()

    flg_p = 0
    flg_m = 0
    # print(B)
    for i,(n,sign) in enumerate(B):
        if i < k:
            if sign == -1:
                last_m = n
            else:
                last_p = n

        else:
            if sign == -1:
                if flg_m == 0:
                    first_m = n
                    flg_m = 1
            else:
                if flg_p == 0:
                    first_p = n
                    flg_p = 1

    L = B[:k]
    ans = cal_ans(L)
    c = 0
    for n,sign in L:
        if sign == -1:
            c += 1
    if c % 2 == 0:
        print(ans)
        exit()

    if first_p * last_p >= first_m*last_m:
        a = first_p
        b = last_m
    else:
        a = first_m
        b = last_p

    ans *= a
    ans %= MOD
    ans *= pow(b,MOD-2,MOD)
    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()))
A.sort(key=lambda x:abs(x),reverse=True)
MOD=10**9+7

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

if K==N:
    ans= A[0]
    for j in range(1,K):
        ans = (ans*A[j])%MOD
  
       
elif len(M)==N and K%2==1:
    ans= M[-1]
    for j in range(1,K):
        ans = (ans*M[-1-j])%MOD
       
else:
    Q=deque(P)
    R=deque(M)
    cnt=0
    ans_list=[]

    while cnt<K:

        if Q:
            tmp_p=Q.popleft()
        else:
            tmp_p=0

        if len(R)>=2 and K-cnt>=2:
            x= R.popleft()
            y= R.popleft()
            tmp_q= x*y
        else:
            tmp_q=0

        if tmp_p>=tmp_q:
            ans_list.append(tmp_p)
            if tmp_q>0:
                R.appendleft(y)
                R.appendleft(x)
            cnt +=1
        else:
            ans_list.append(x)
            ans_list.append(y)
            Q.appendleft(tmp_p)
            cnt +=2

    #print(cnt, tmp_p, tmp_q,Q,R,ans_list)
    ans=ans_list[0]
    for j in range(1,len(ans_list)):
        ans = (ans*ans_list[j])%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()))
A.sort(key=lambda x:abs(x),reverse=True)
MOD=10**9+7

P=[]
M=[]
for num in A:
    if num>=0:
        P.append(num)
    else:
        M.append(num)
       
#print(P,M)
       
if len(M)==N and K%2==1:
    ans= M[-1]
    for j in range(1,K):
        ans = (ans*M[-1-j])%MOD
       
else:
    Q=deque(P)
    R=deque(M)
    cnt=0
    ans_list=[]

    while cnt<K:

        if Q:
            tmp_p=Q.popleft()
        else:
            tmp_p=0

        if len(R)>=2 and K-cnt>=2:
            x= R.popleft()
            y= R.popleft()
            tmp_q= x*y
        else:
            tmp_q=0

        if tmp_p>=tmp_q:
            ans_list.append(tmp_p)
            if tmp_q>0:
                R.appendleft(y)
                R.appendleft(x)
            cnt +=1
        else:
            ans_list.append(x)
            ans_list.append(y)
            Q.appendleft(tmp_p)
            cnt +=2

    #print(cnt, tmp_p, tmp_q,Q,R,ans_list)
    ans=ans_list[0]
    for j in range(1,len(ans_list)):
        ans = (ans*ans_list[j])%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()))
A.sort(key=lambda x:abs(x),reverse=True)
MOD=10**9+7

P=[]
M=[]
for num in A:
    if num>=0:
        P.append(num)
    else:
        M.append(num)
       
#print(P,M)
       
if len(M)==N and K%2==1:
    ans= M[-1]
    for j in range(1,K):
        ans = (ans*M[-1-j])%MOD
       
else:
    Q=deque(P)
    R=deque(M)
    cnt=0
    ans_list=[]

    while cnt<K:

        if Q:
            tmp_p=Q.popleft()
        else:
            tmp_p=0

        if len(R)>=2 and K-cnt>=2:
            x= R.popleft()
            y= R.popleft()
            tmp_q= x*y
        else:
            tmp_q=0

        if tmp_p>=tmp_q:
            ans_list.append(tmp_p)
            if tmp_q>0:
                R.appendleft(y)
                R.appendleft(x)
            cnt +=1
        else:
            ans_list.append(x)
            ans_list.append(y)
            Q.appendleft(tmp_p)
            cnt +=2

        #print(cnt, tmp_p, tmp_q,Q,R,ans_list)
       
        ans=ans_list[0]
        for j in range(1,len(ans_list)):
            ans = (ans*ans_list[j])%MOD
       
       
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

MOD = 10**9+7


def main(input, print):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    nc = 0
    zc = 0
    for i in range(n):
        if a[i] < 0:
            nc += 1
        elif a[i] == 0:
            zc += 1
    negative = 0
    cnt = 0
    ans = 1
    a = sorted(a, key=abs, reverse=True)
    y = 0
    for i in range(n):
        if k == cnt:
            break
        if a[i] < 0:
            if negative % 2 == 1 and k-cnt > 1:
                ans = ans * y * a[i] % MOD
                cnt += 2
            else:
                y = a[i]
            negative += 1
        elif a[i] > 0:
            ans = ans * a[i] % MOD
            cnt += 1
    if cnt == k:
        print(ans)
        return
    if zc > 0:
        print(0)
        return
    ans = 1
    a = sorted(a, key=abs)
    y = 0
    for i in range(k):
        ans = ans * a[i] % MOD

    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

Solution code:
import heapq
n,k = map(int, input().split())
mod = 10**9 + 7
As = list(map(int, input().split()))
ms = [-a for a in As if a < 0]
ps = [a for a in As if a >= 0]
n_zero = As.count(0)

ms.sort(reverse=True)
ps.sort(reverse=True)
mind = 0
pind = 0
cnt = 0
ans = 1
dp = [0] * n
dp[0] = 1
mnq = []
plq = []
heapq.heapify(mnq)
heapq.heapify(plq)
if k-len(ps)>2 and (k-len(ps))%2 == 1:
    flg = True
else:
    flg = False
if flg:
    # この場合は最小値構成
    for m in ms:
        heapq.heappush(mnq, m)
    for p in ps:
        heapq.heappush(plq, p)
else:
    for m in ms:
        heapq.heappush(mnq, -m)
    for p in ps:
        heapq.heappush(plq, -p)
cnt = 0
# print(len(ps),len(ms),"debug",flg)
while cnt < k:
    # print(cnt,ans)
    if k - cnt > 1:
        if len(mnq) >= 2 and len(plq) >= 2:
            m1 = heapq.heappop(mnq)
            m2 = heapq.heappop(mnq)
            q1 = heapq.heappop(plq)
            q2 = heapq.heappop(plq)
            if flg:
                if m1 * m2 < q1 * q2:
                    ans *= (m1*m2)
                    heapq.heappush(plq,q1)
                    heapq.heappush(plq,q2)
                    cnt += 2
                else:
                    ans *= q1
                    heapq.heappush(mnq,m1)
                    heapq.heappush(mnq,m2)
                    heapq.heappush(plq,q2)
                    cnt += 1
            else:
                if m1 * m2 > q1 * q2:
                    ans *= (m1*m2)
                    heapq.heappush(plq,q1)
                    heapq.heappush(plq,q2)
                    cnt += 2
                else:
                    ans *= -q1
                    heapq.heappush(mnq,m1)
                    heapq.heappush(mnq,m2)
                    heapq.heappush(plq,q2)
                    cnt += 1
        elif len(mnq) == 1 and len(plq) >= 2:
            if flg:
                m1 = heapq.heappop(mnq)
                ans *= -m1
            else:
                q1 = heapq.heappop(plq)
                ans *= (-q1)
            cnt += 1
        elif len(mnq) >= 2 and len(plq) == 1:
            m1 = heapq.heappop(mnq)
            m2 = heapq.heappop(mnq)
            q1 = heapq.heappop(plq)
            if flg:
                if q1 <= m1 * m2:
                    ans *= q1
                    heapq.heappush(mnq,m1)
                    heapq.heappush(mnq,m2)
                    cnt += 1
                else:
                    ans *= (m1*m2)
                    heapq.heappush(plq,q1)
                    cnt += 2
            else:
                if -q1 >= m1 * m2:
                    ans *= q1
                    heapq.heappush(mnq,m1)
                    heapq.heappush(mnq,m2)
                    cnt += 1
                else:
                    ans *= (m1*m2)
                    heapq.heappush(plq,q1)
                    cnt += 2
        elif len(mnq) == 1 and len(plq) == 1:
            m1 = heapq.heappop(mnq)
            q1 = heapq.heappop(plq)
            ans *= m1*q1
            cnt += 2
        elif len(mnq) == 0:
            q1 = heapq.heappop(plq)
            if flg: ans *= q1
            else: ans *= (-q1)
            cnt += 1
        elif len(plq) == 0:
            m1 = heapq.heappop(mnq)
            m2 = heapq.heappop(mnq)
            ans *= (m1*m2)
            cnt += 2
    elif k - cnt == 1:
        if len(plq) >= 1:
            q1 = heapq.heappop(plq)
            if flg: ans *= q1
            else: ans *= -q1
            cnt += 1
        elif len(plq) == 0:
            m1 = heapq.heappop(mnq)
            if flg: ans *= -m1
            else: ans *= m1
            cnt += 1
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n,k = map(int, input().split())
mod = 10**9 + 7
As = list(map(int, input().split()))
ms = [-a for a in As if a < 0]
ps = [a for a in As if a >= 0]
n_zero = As.count(0)

ms.sort(reverse=True)
ps.sort(reverse=True)
mind = 0
pind = 0
cnt = 0
ans = 1
dp = [0] * n
dp[0] = 1
mnq = []
plq = []
heapq.heapify(mnq)
heapq.heapify(plq)
if k-len(ps)>2 and (k-len(ps))%2 == 1:
    flg = True
else:
    flg = False
if flg:
    # この場合は最小値構成
    for m in ms:
        heapq.heappush(mnq, m)
    for p in ps:
        heapq.heappush(plq, p)
else:
    for m in ms:
        heapq.heappush(mnq, -m)
    for p in ps:
        heapq.heappush(plq, -p)
cnt = 0
while cnt < k:
    # print(cnt,ans)
    if k - cnt > 1:
        if len(mnq) >= 2 and len(plq) >= 2:
            m1 = heapq.heappop(mnq)
            m2 = heapq.heappop(mnq)
            q1 = heapq.heappop(plq)
            q2 = heapq.heappop(plq)
            if m1 * m2 > q1 * q2:
                ans *= (m1*m2)
                heapq.heappush(plq,q1)
                heapq.heappush(plq,q2)
                cnt += 2
            else:
                if flg:
                    ans *= q1
                else:
                    ans *= -q1
                heapq.heappush(mnq,m1)
                heapq.heappush(mnq,m2)
                heapq.heappush(plq,q2)
                cnt += 1
        elif len(mnq) == 1 and len(plq) >= 2:
            q1 = heapq.heappop(plq)
            if flg: ans *= q1
            else: ans *= (-q1)
            cnt += 1
        elif len(mnq) >= 2 and len(plq) == 1:
            m1 = heapq.heappop(mnq)
            m2 = heapq.heappop(mnq)
            q1 = heapq.heappop(plq)
            if -q1 > m1 * m2:
                if flg: ans *= q1
                else: ans *= (-q1)
                heapq.heappush(mnq,m1)
                heapq.heappush(mnq,m2)
                cnt += 1
            else:
                ans *= (m1*m2)
                heapq.heappush(plq,q1)
                cnt += 2
        elif len(mnq) == 0:
            q1 = heapq.heappop(plq)
            if flg: ans *= q1
            else: ans *= (-q1)
            cnt += 1
        elif len(plq) == 0:
            m1 = heapq.heappop(mnq)
            m2 = heapq.heappop(mnq)
            ans *= (m1*m2)
            cnt += 2
        elif len(mnq) == 1 and len(plq) == 1:
            m1 = heapq.heappop(mnq)
            q1 = heapq.heappop(plq)
            ans *= m1*q1
            cnt += 2
    elif k - cnt == 1:
        if len(plq) >= 1:
            q1 = heapq.heappop(plq)
            if flg: ans *= q1
            else: ans *= -q1
            cnt += 1
        elif len(plq) == 0:
            m1 = heapq.heappop(mnq)
            if flg: ans *= -m1
            else: ans *= m1
            cnt += 1
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
N, K, *A = map(int, open(0).read().split())

MOD = 10 ** 9 + 7
s = []  # v >= 0
t = []  # v < 0
for i in range(N):
    if A[i] < 0:
        t.append(A[i])
    else:
        s.append(A[i])
        
ok = False  # ans > 0
if len(s) > 0:
    if N == K:
        ok = len(t) % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    x = sorted(A, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * x[i] % MOD
else:
    s.sort()
    t.sort(key=lambda x: abs(x))
    if K % 2 == 1:
        ans = ans * s.pop() % MOD
        
    p = []
    while len(s) >= 2:
        x = s.pop() * s.pop() % MOD
        p.append(x)
    
    while len(t) >= 2:
        x = t.pop() * t.pop() % MOD
        p.append(x)

    p.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * p[i] % MOD
    
print(ans)

Submission status: Wrong Answer

Solution code:
N, K, *A = map(int, open(0).read().split())

MOD = 10 ** 9 + 7
s = []  # v >= 0
t = []  # v < 0
for i in range(N):
    if A[i] < 0:
        t.append(A[i])
    else:
        s.append(A[i])
        
ok = False  # ans > 0
if len(s) > 0:
    if N == K:
        ok = len(t) % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    x = sorted(A, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * x[i] % MOD
else:
    s.sort()
    t.sort()
    if K % 2 == 1:
        ans = ans * s.pop() % MOD
        
    p = []
    while len(s) >= 2:
        x = s.pop() * s.pop() % MOD
        p.append(x)
    
    while len(t) >= 2:
        x = t.pop() * t.pop() % MOD
        p.append(x)

    p.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * p[i] % MOD
    
print(ans)

Submission status: Wrong Answer

Solution code:
N, K, *A = map(int, open(0).read().split())

MOD = 10 ** 9 + 7
s = []  # v >= 0
t = []  # v < 0
for i in range(N):
    if A[i] < 0:
        t.append(A[i])
    else:
        s.append(A[i])
        
ok = False  # ans > 0
if len(s) > 0:
    if N == K:
        ok = len(t) % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    x = sorted([abs(v) for v in A], reverse=True)
    for i in range(K):
        ans = ans * x[i] % MOD
else:
    s.sort()
    t.sort()
    if K % 2 == 1:
        ans = ans * s.pop() % MOD
        
    p = []
    while len(s) >= 2:
        x = s.pop() * s.pop() % MOD
        p.append(x)
    
    while len(t) >= 2:
        x = t.pop() * t.pop() % MOD
        p.append(x)

    p.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * p[i] % MOD
    
print(ans)

Submission status: Wrong Answer

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

z_num = sum(v == 0 for v in A)
p_num = sum(v > 0 for v in A)
m_num = sum(v < 0 for v in A)

if p_num + m_num < K:
    print(0)
    exit()

if p_num == 0 and m_num >= K and K % 2 == 1:
    if z_num > 0:
        print(0)
    else:
        x = sorted([v for v in A if v < 0], reverse=True)
        ans = 1
        n = len(x)
        for i in range(K):
            ans = ans * x[i] % MOD
        print(ans)
    exit()

x = []
for v in A:
    if v != 0:
        x.append((abs(v), v // abs(v)))
    else:
        x.append((0, 0))
x.sort()

plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s >= 0:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s >= 0 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v

    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_org = plus.pop()
        m_org = minus.pop()
        if p_org * p_cand > m_org * m_cand:
            plus.append(p_org)
            plus.append(p_cand)
        else:
            minus.append(m_org)
            minus.append(m_cand)


ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * (-v) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import *
from collections import deque

N,K,*A = map(int, open(0).read().split())
pos = []
zero = 0
neg = []
count = K
m = 1000000007
for x in A:
    if x > 0:
        pos.append(x)
    elif x == 0:
        zero += 1
    else:
        neg.append(x)
if K == N:
    ans = A[0] % m
    for x in A[1:]:
        ans = (ans*x) % m
    print(ans)
elif K % 2 == 1 and len(pos) == 0:
    if zero > 0:
        print(0)
    else:
        ai = [x * (-1) for x in A]
        heapify(ai)
        ans = (heappop(ai)*(-1)) % m
        for i in range(K-1):
            ans = (ans*heappop(ai)*(-1)) % m
        print(ans)
elif K > N - zero:
    print(0)
else:
    heapify(neg)
    ans = 1
    negpos = []
    for i in range(len(neg)//2):
        temp = heappop(neg)
        negpos.append(temp*heappop(neg))
    dnp = deque(negpos)
    posi = [x * (-1) for x in pos]
    heapify(posi)
    if len(posi) > 0:
        t1 = heappop(posi) * (-1)
    else:
        t1 = 1
    if len(posi) > 0:
        t2 = heappop(posi) * (-1)
    else:
        t2 = 1
    for i in range(K):
        if count > 1:
            if len(dnp) > 0:
                if t1 > dnp[0]:
                    if count > 2:
                        ans = (ans*t1) % m
                        t1 = t2
                        if len(posi) > 0:
                            t2 = heappop(posi) * (-1)
                        else:
                            t2 = 1
                        count -= 1
                    else:
                        if t2 == 1 and len(posi) == 0:
                            ans = (ans*dnp.popleft()) % m
                            count -= 2
                        else:
                            ans = (ans*t1) % m
                            t1 = t2
                            if len(posi) > 0:
                                t2 = heappop(posi) * (-1)
                            else:
                                t2 = 1
                            count -= 1
                else:
                    if t1 * t2 > dnp[0]:
                        if count != 3:
                            ans = (ans*t1*t2) % m
                            if len(posi) > 0:
                                t1 = heappop(posi) * (-1)
                            else:
                                t1 = 1
                            if len(posi) > 0:
                                t2 = heappop(posi) * (-1)
                            else:
                                t2 = 1
                            count -= 2
                        else:
                            ans = (ans*dnp.popleft()) % m
                            count -= 2
                    else:
                        ans = (ans*dnp.popleft()) % m
                        count -= 2
            else:
                ans = (ans*t1) % m
                if len(posi) > 0:
                    t1 = t2
                    t2 = heappop(posi) * (-1)
                else:
                    t1 = t2
                count -= 1
        elif count == 1:
            ans = (ans*t1) % m
            break
        else:
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
aPlus = []
aMinus = []
ans = 0
for aa in a:
    if aa < 0:
        aMinus.append(-aa)
    else:
        aPlus.append(aa)

i = -1
j = -1
if k==n:
    i = len(aPlus)-1
    j = len(aMinus)-1
elif len(aPlus)==0 and k%2==1:
    aMinus.sort()
    j = k-1
else:
    aPlus.sort(reverse = True)
    aMinus.sort(reverse = True)
    for _ in range(k):
        if i+1 <= len(aPlus)-1 and not j+1 <= len(aMinus)-1:
            i += 1
        elif not i+1 <= len(aPlus)-1 and j+1 <= len(aMinus)-1:
            j += 1
        elif aPlus[i+1] > aMinus[j+1]:
            i += 1
        else:
            j += 1
    if j%2 == 0:
        if i+1 <= len(aPlus)-1 and not j+1 <= len(aMinus)-1:
            i += 1
            j -= 1
        elif not i+1 <= len(aPlus)-1 and j+1 <= len(aMinus)-1:
            j += 1
            i -= 1
        elif aPlus[i] > aMinus[j]:
            i += 1
            j -= 1
        else:
            j += 1
            i -= 1

ans = 1
mod = 10**9+7
for ii in range(i+1):
    ans *= aPlus[ii]
    ans %= mod
for jj in range(j+1):
    ans *= -aMinus[jj]
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import *
from collections import deque

N,K,*A = map(int, open(0).read().split())
pos = []
zero = 0
neg = []
count = K
m = 1000000007
for x in A:
    if x > 0:
        pos.append(x)
    elif x == 0:
        zero += 1
    else:
        neg.append(x)
if K == N:
    ans = A[0] % m
    for x in A[1:]:
        ans = (ans*x) % m
    print(ans)
elif K % 2 == 1 and len(pos) == 0:
    if zero > 0:
        print(0)
    else:
        ai = [x * (-1) for x in A]
        heapify(ai)
        ans = (heappop(ai)*(-1)) % m
        for i in range(K-1):
            ans = (ans*heappop(ai)*(-1)) % m
        print(ans)
elif K > N - zero:
    print(0)
else:
    heapify(neg)
    ans = 1
    negpos = []
    for i in range(len(neg)//2):
        temp = heappop(neg)
        negpos.append(temp*heappop(neg))
    dnp = deque(negpos)
    posi = [x * (-1) for x in pos]
    heapify(posi)
    if len(posi) > 0:
        t1 = heappop(posi) * (-1)
    else:
        t1 = 1
    if len(posi) > 0:
        t2 = heappop(posi) * (-1)
    else:
        t2 = 1
    for i in range(K):
        if count > 1:
            if len(dnp) > 0:
                if t1 > dnp[0]:
                    if count > 2:
                        ans = (ans*t1) % m
                        t1 = t2
                        if len(posi) > 0:
                            t2 = heappop(posi) * (-1)
                        else:
                            t2 = 1
                        count -= 1
                    else:
                        if t2 == 1 and len(posi) == 0:
                            ans = (ans*dnp.popleft()) % m
                            count -= 2
                        else:
                            ans = (ans*t1) % m
                            t1 = t2
                            if len(posi) > 0:
                                t2 = heappop(posi) * (-1)
                            else:
                                t2 = 1
                            count -= 1
                else:
                    if t1 * t2 > dnp[0]:
                        if count != 3:
                            ans = (ans*t1*t2) % m
                            if len(posi) > 0:
                                t1 = heappop(posi) * (-1)
                            if len(posi) > 0:
                                t2 = heappop(posi) * (-1)
                            else:
                                t2 = 1
                            count -= 2
                        else:
                            ans = (ans*dnp.popleft()) % m
                            count -= 2
                    else:
                        ans = (ans*dnp.popleft()) % m
                        count -= 2
            else:
                ans = (ans*t1) % m
                if len(posi) > 0:
                    t1 = t2
                    t2 = heappop(posi) * (-1)
                else:
                    t1 = t2
                count -= 1
        elif count == 1:
            ans = (ans*t1) % m
            break
        else:
            break
    print(ans)