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
    # parsing
    n, k = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    
    # edge case; n == k
    if n == k:
        ans = 1
        for i in nums:
            ans *= i % modVal
            ans %= modVal
        print(ans)
        return
    
    # edge case; all neg
    if max(nums) < 0:
        nums.sort()
        ans = 1
        # odd k
        if k % 2:
            for i in range(k):
                ans *= nums[-i - 1] % modVal
                ans %= modVal
        # even k
        else:
            for i in range(k):
                ans *= nums[i] % modVal
                ans %= modVal
        print(ans)
        return
    
    # convert to absolute value & count zeros
    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 absolute 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[-1]
        if negLessK:
            maxNeg = negLessK[-1]
        
        if (minNeg and maxPos) and (minPos and maxNeg):
            if maxPos / minNeg > maxNeg / minPos:
                negOverK[0] = maxPos
            else:
                posOverK[0] = maxNeg
        elif not (minNeg and maxPos) and (minPos and maxNeg):
            posOverK[0] = maxNeg
        elif (minNeg and maxPos) and not (minPos and maxNeg):
            negOverK[0] = maxPos
        #elif zeroCnt:
        #    print(0)
        #    return
    
    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:
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)
val = [1]*(n+1)
sign = [0]*(n+1)
for i in range(n): val[i+1] = B[i][0]
for i in range(n): sign[i+1] = sign[i] + B[i][1]
# minus = []
# plus = []
# for i in range(n):
#     if B[i][1]: minus.append(B[i][0])
#     else: plus.append(B[i][0])

# print(n,k)
# print(B)
# print(sign)
# print(val)
# # print(plus)
# # print(minus)

if (sign[k]-sign[0])%2 == 0:
    a = 1
    for v in val[1:k+1]:
        a *= v; a %= mod
    a += mod; a %= mod
    print(a)
    exit()

a = 1
for i in range(n):
    if sign[i] == sign[k]: break
    a *= val[i]; a %= mod
c = k - 1
for i in range(k,n):
    if B[i][1] == 0:
        a *= val[i]; a %= mod
        c += 1
        break
if c == k:
    a += mod; a %= mod
    print(a)
    exit()

# print('====')

B.sort()
val = [1]*(n+1)
sign = [0]*(n+1)
for i in range(n): val[i+1] = B[i][0]
for i in range(n): sign[i+1] = sign[i] + B[i][1]
# minus = []
# plus = []
# for i in range(n):
#     if B[i][1]: minus.append(B[i][0])
#     else: plus.append(B[i][0])

# print(n,k)
# print(B)
# print(sign)
# print(val)
# # print(plus)
# # print(minus)

if (sign[k]-sign[0])%2 == 1:
    a = -1
    for v in val[1:k+1]:
        a *= v; a %= mod
    a += mod; a %= mod
    print(a)
    exit()

a = -1
for i in range(n):
    if sign[i] == sign[k]: break
    a *= val[i]; a %= mod
c = k - 1
for i in range(k,n):
    if B[i][1] == 1:
        a *= val[i]; a %= mod
        c += 1
        break
if c == k:
    a += mod; a %= mod
    print(a)
    exit()

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]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
sign = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if sign < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        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()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            sign *= -1
            continue

        if len(P) == len(N) == 1:
            ans *= P.pop() * N.pop()
            K -= 2
            sign *= -1
            continue

        if len(N) == 1:
            n = N.pop()
            if sign < 0:
                ans *= n
                K -= 1
                sign *= -1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1 and sign > 0 or K % 2 == 0 and sign < 0:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10**9+7
if k%2==1 and len(pa)==0:
    print(sum(na[::-1][:k])%mod)
    exit(0)
na += [0,0]
pa += [0]*n
nn = 0
pn = 0
ans = 1
for i in range(k//2):
    if pa[pn]*pa[pn+1]>=na[nn]*na[nn+1]:
        ans *= pa[pn]*pa[pn+1]
        pn += 2
    else:
        ans *= na[nn]*na[nn+1]
        nn += 2
    ans %= mod
if k%2==1:
    ans *= pa[pn]
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 = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    if len(mia) > 0 and cnt != k:
        for i in num[::-1]:
            if i >= 0:
                p, q = i, mia[-1]
                break
        if len(pla) == 0:
            ans *= q * pow(p, mod - 2, mod)
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                r, s = i, pla[-1]
                break
        if len(mia) == 0 or cnt == k:
            ans *= s * pow(r, mod - 2, mod)
    if len(mia) > 0 and len(pla) > 0 and cnt != k:
        print(p, q, r, s)
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, 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()))
MOD = 10**9 + 7

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

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        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()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(P) == len(N) == 1:
            ans *= P.pop() * N.pop()
            K -= 2
            continue

        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(P) == 1 and len(N) == 0:
            p = P.pop()
            if K % 2 == 1 and ans > 0 or K % 2 == 0 and ans < 0:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)
from heapq import heappush, heappop

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

if all(a < 0 for a in A) and K % 2 == 1:
    A.sort(reverse=True)
    ans = 1
    for a in A[:K]:
        ans = ans * a % MOD
    print(ans)
    exit(0)

p = []
n = []
for a in A:
    if a < 0:
        heappush(n, a)
    else:
        heappush(p, -a)

ans = 1
cnt = 0
while cnt < K:
    if cnt == K - 1:
        if len(p) > 0:
            ans = ans * -heappop(p) % MOD
        else:
            ans = ans * max(n) % MOD
        cnt += 1
        break
    if len(p) < 1:
        ans = ans * heappop(n) * heappop(n) % MOD
        cnt += 2
    elif len(n) < 2:
        ans = ans * -heappop(p) % MOD
        cnt += 1
    else:
        if -p[0] >= n[0] * n[1]:
            ans = ans * -heappop(p) % MOD
            cnt += 1
        else:
            ans = ans * heappop(n) * heappop(n) % MOD
            cnt += 2
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]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

if len(N) % 2 == 1:
    N.popleft()

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        elif P:
            ans *= P.pop()
        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()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(P) == len(N) == 1:
            ans *= P.pop() * N.pop()
            K -= 2
            continue

        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1 and ans > 0 or K % 2 == 0 and ans < 0:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

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])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) < pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) >= pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    if len(mia) > 0 and cnt != k:
        for i in num[::-1]:
            if i >= 0:
                p, q = i, mia[-1]
                break
        if len(pla) == 0:
            ans *= q * pow(p, mod - 2, mod)
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                r, s = i, pla[-1]
                break
        if len(mia) == 0 or cnt == k:
            ans *= s * pow(r, mod - 2, mod)
    if len(mia) > 0 and len(pla) > 0 and cnt != k:
        if p * r >= q * s:
            ans *= s * pow(r, mod - 2, mod)
        if p * r < q * s:
            ans *= q * pow(p, mod - 2, mod)
    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 = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    if len(mia) > 0 and cnt != k:
        for i in num[::-1]:
            if i >= 0:
                p, q = i, mia[-1]
                break
        if len(pla) == 0:
            ans *= q * pow(p, mod - 2, mod)
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                r, s = i, pla[-1]
                break
        if len(mia) == 0 or cnt == k:
            ans *= s * pow(r, mod - 2, mod)
    if len(mia) > 0 and len(pla) > 0 and cnt != k:
        if p * r >= q * s:
            ans *= s * pow(r, mod - 2, mod)
        if p * r < q * s:
            ans *= q * pow(p, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:

t=1
# t=int(input())
for _ in range(t):
    from bisect import bisect_left
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    m=bisect_left(a,0)
    MOD=10**9+7
    ans=1
    if m==0 or (m==n and k%2==1):
        for i in a[-k:]:
            ans=(ans*i)%MOD
    elif m==n and k%2==0:
        for i in a[:k]:
            ans=(ans*i)%MOD
    else:
        ans=1
        l,r=0,-1
        lm=a[0]*a[1]
        rm=a[-1]*a[-2]
        for i in range(k//2):
            if lm>=rm:
                ans*=lm%MOD
                l+=2
                if l<=n-2:
                    lm=a[l]*a[l+1]
            else:
                ans*=rm%MOD
                r-=2
                if 1<=n+r:
                    rm=a[r]*a[r-1]
            ans%=MOD
        if k%2==1:
            ans*=a[r]
            ans%=MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("out.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# @lru_cache(None)

t=1
# t=int(input())
for _ in range(t):
    n,k=L()
    A=L()
    while(0 in A):
        del(A[A.index(0)])
    if max(A)<0:
        A.sort(reverse=True)
        if len(A)<k:
            print(0)
            exit()
        prod=1
        if k%2==0:
            A=A[::-1]
        for i in range(k):
            prod=(prod*A[i])%mod
        print(prod%mod)
        exit()
    pos=[]
    neg=[]
    for i in range(len(A)):
        if A[i]>0:
            pos.append(A[i])
        else:
            neg.append(A[i])
    pos.sort(reverse=True)
    neg.sort()
    prod=1
    i=0
    j=0
    lastpos=0
    lastneg=0
    while(k>0):
        # print(i,pos)
        # print(j,neg)
        if i<len(pos) and j<len(neg):
            if pos[i]>abs(neg[j]):
                prod=(prod*pos[i])%mod
                lastpos=pos[i]
                i+=1
            else:
                prod=(prod*abs(neg[j]))%mod
                lastneg=neg[j]
                j+=1
        else:
            if i<len(pos):
                prod=(prod*pos[i])%mod
                lastpos=pos[i]
                i+=1
            elif j<len(neg):
                prod=(prod*abs(neg[j]))%mod
                lastneg=neg[j]
                j+=1
        k-=1
    if prod>0:
        print(prod%mod)
    else:
        p1=-1
        p2=-1
        if j<len(neg):
            p1=prod//lastpos*neg[j]
        if i<len(pos):
            p2=prod//lastneg*pos[i]
        print(max(p1,p2)%mod)

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]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        if ans >= 0:
            ans *= P.pop()
        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()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(P) == 1:
            print(-1)
            exit()
            p = P.pop()
            if K % 2 == 0 and ans < 0 or K % 2 == 1 and ans > 0:
                ans *= p
                K -= 1

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("out.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# @lru_cache(None)

t=1
# t=int(input())
for _ in range(t):
    n,k=L()
    A=L()
    while(0 in A):
        del(A[A.index(0)])
    if max(A)<0:
        A.sort(reverse=True)
        if len(A)<k:
            print(0)
            exit()
        prod=1
        if k%2==0:
            A=A[::-1]
        for i in range(k):
            prod*=A[i]
        print(prod%mod)
        exit()
    pos=[]
    neg=[]
    for i in range(len(A)):
        if A[i]>0:
            pos.append(A[i])
        else:
            neg.append(A[i])
    pos.sort(reverse=True)
    neg.sort()
    prod=1
    i=0
    j=0
    lastpos=0
    lastneg=0
    while(k>0):
        # print(i,pos)
        # print(j,neg)
        if i<len(pos) and j<len(neg):
            if pos[i]>abs(neg[j]):
                prod*=pos[i]
                lastpos=pos[i]
                i+=1
            else:
                prod*=abs(neg[j])
                lastneg=neg[j]
                j+=1
        else:
            if i<len(pos):
                prod*=pos[i]
                lastpos=pos[i]
                i+=1
            elif j<len(neg):
                prod*=abs(neg[j])
                lastneg=neg[j]
                j+=1
        k-=1
    if prod>0:
        print(prod%mod)
    else:
        p1=-1
        p2=-1
        if j<len(neg):
            p1=prod//lastpos*neg[j]
        if i<len(pos):
            p2=prod//lastneg*pos[i]
        print(max(p1,p2)%mod)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("out.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# @lru_cache(None)

t=1
# t=int(input())
for _ in range(t):
    n,k=L()
    A=L()
    while(0 in A):
        del(A[A.index(0)])
    A.sort(reverse=True)
    if A[0]<0:
        if len(A)<k:
            print(0)
            exit()
        prod=1
        if k%2==0:
            A=A[::-1]
        for i in range(k):
            prod*=A[i]
        print(prod%mod)
        exit()
    pos=[]
    neg=[]
    for i in range(len(A)):
        if A[i]>0:
            pos.append(A[i])
        else:
            neg.append(A[i])
    pos.sort(reverse=True)
    neg.sort()
    prod=1
    i=0
    j=0
    lastpos=0
    lastneg=0
    while(k>0):
        # print(i,pos)
        # print(j,neg)
        if i<len(pos) and j<len(neg):
            if pos[i]>abs(neg[j]):
                prod*=pos[i]
                lastpos=pos[i]
                i+=1
            else:
                prod*=abs(neg[j])
                lastneg=neg[j]
                j+=1
        else:
            if i<len(pos):
                prod*=pos[i]
                lastpos=pos[i]
                i+=1
            elif j<len(neg):
                prod*=abs(neg[j])
                lastneg=neg[j]
                j+=1
        k-=1
    if prod>0:
        print(prod%mod)
    else:
        p1=-1
        p2=-1
        if j<len(neg):
            p1=prod//lastpos*neg[j]
        if i<len(pos):
            p2=prod//lastneg*pos[i]
        print(max(p1,p2)%mod)

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]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if ans < 0 and N:
            ans *= N.pop()
            break
        if ans >= 0 and P:
            ans *= P.pop()
            break
        print(-1)
        exit()

    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()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue

        if len(P) == 1:
            p = P.pop()
            if ans < 0 and K % 2 == 0 or ans >= 0 and K % 2 == 1:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

A.sort(key=lambda a: abs(a), reverse=True)
Msgn = 1
Mval = 1
for a in A[:K]:
    if a < 0:
        Msgn *= -1
    elif a == 0:
        Msgn = 0
    Mval = Mval * a % MOD

if Msgn >= 0:
    print(Mval)
    exit()

A = list(filter(lambda a: a != 0, A))
A.sort(key=lambda a: abs(a))
mval = 1
for a in A[:K]:
    mval = mval * a % MOD
print(mval)