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:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N,K = LMIIS()
    A = LMIIS()
    positive = []
    negative = []
    zero = []
    for a in A:
        if a >0:
            positive.append(a)
        elif a == 0:
            zero.append(a)
        else:
            negative.append(a)
    positive.sort(reverse=True)
    negative.sort()
    ans = 1
    num_used = 0
    num_used_negative = 0

    if len(positive) + len(negative) < K:
        print(0)
        return

    if len(positive) >= K:

        if len(positive) >= 2:
            comp = positive[0] * positive[1]
        else:
            comp = positive[0]
        
        for i in range(0,min(len(negative),K//2),2):
            if negative[i] * negative[i+1] >= comp:
                ans = ans * negative[i] * negative[i+1] % P
                num_used += 2
                num_used_negative += 1
            else:
                break
        for i in range(K-num_used):
            ans = ans * positive[i] % P
            num_used += 1
        print(ans)
        return
    else:
        need = K - len(positive)
        dbg(need,positive,negative)
        #答えを正にできる
        if need%2 == 0:
            ans = 1
            for a in positive:
                ans = ans * a % P
            for i in range(0,need,2):
                ans = ans * negative[i] * negative[i+1] % P

            print(ans)
            return

        #答えが負
        else:
            if zero:
                print(0)
                return
            ans = 1
            for a in positive:
                ans = ans * a % P
            negative = negative[::-1]
            for i in range(K-len(positive)):
                ans = ans * negative[i] % P
            print(ans)
            return
                



    
main()

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]:
                    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)

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]:
                    ans = (ans*t1) % m
                    t1 = t2
                    if len(posi) > 0:
                        t2 = heappop(posi) * (-1)
                    else:
                        t2 = 1
                    count -= 1
                else:
                    if count == 3:
                        ans = (ans*dnp.popleft()) % m
                        count -= 2
                    else:
                        if t1 * t2 > dnp[0]:
                            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*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:
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]:
                    ans = (ans*t1) % m
                    t1 = t2
                    if len(posi) > 0:
                        t2 = heappop(posi) * (-1)
                    else:
                        t2 = 1
                    count -= 1
                elif t1 * t2 > dnp[0]:
                    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*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:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
MOD = 10**9 + 7
def main(N, K, A):
    negative = sorted([a for a in A if a < 0])
    neg = len(negative)
    zero = [a for a in A if a == 0]
    positive = sorted([a for a in A if a > 0])
    pos = len(positive)

    if N - K < len(zero):
        return 0
    N -= len(zero)
    A = sorted([a for a in A if a != 0], key=lambda x: abs(x))

    ans = Mint(1)
    if pos == 0 and K & 1:
        # マイナスになっちゃう
        if zero:
            ans *= 0
        else:
            for i in range(K):
                ans *= abs(A[i])
            ans = -ans
    else:
        # プラスにできる
        A.reverse()
        neg_cnt = 0
        last_pos = 0
        last_cnt = 0
        for i in range(K):
            ans *= abs(A[i])
            if A[i] < 0: neg_cnt += 1
            if neg_cnt & 1 == 0:
                last_pos = ans.value
                last_cnt = i + 1
        remain = K - last_cnt
        if remain == 1:
            for i in range(last_cnt, N):
                if A[i] > 0:
                    ans = Mint(last_pos * A[i])
                    break
        elif remain != 0:
            pospos = 1
            negneg = 1
            pos_rem = remain
            neg_rem = remain
            for i in range(last_cnt, N):
                if A[i] > 0 and pos_rem > 0:
                    pospos *= A[i]
                    pos_rem -= 1
                if A[i] < 0 and neg_rem > 0:
                    negneg *= abs(A[i])
                    neg_rem -= 1
                if pos_rem == neg_rem == 0:
                    break
            pospos = pospos if pos_rem == 0 else 1
            negneg = negneg if neg_rem == 0 else 1
            ans = Mint(last_pos * max(pospos, negneg))

    return ans

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    print(main(N, K, A))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
from copy import deepcopy
mod = 10**9 + 7

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a = sorted(a, key=lambda x: abs(x))[::-1]
a_plus = [int(x) for x in a if x > 0]
a_minus = [int(x) for x in a if x < 0]
a_abs = [abs(x) for x in a]

def calc(x):
    res = 1
    for i in x:
        res*=abs(i)
        res %= mod 
    return res

max_a = a[:k]
max_a_minus = []
max_a_plus = []
minus_cnt = 0

for i in max_a:
    if i == 0:
        print(0)
        sys.exit()
    if i < 0:
        minus_cnt += 1
        max_a_minus.append(i)
    else:
        max_a_plus.append(i)

if minus_cnt % 2 == 0:
    print(calc(max_a))
    sys.exit()

plus_cnt = k - minus_cnt

if len(a_minus) <= minus_cnt and len(a_plus) <= plus_cnt:
    ans = -float('inf')
elif len(a_minus) <= minus_cnt:
    if len(max_a_minus) == 0:
        ans = -float("inf")
    else:
        max_a_minus.pop()
        max_a_plus.append(a_plus[plus_cnt])
        ans = calc(max_a_plus + max_a_minus)
elif len(a_plus) <= plus_cnt:
    if len(max_a_plus) == 0:
        ans = -float("inf")
    else:
        max_a_plus.pop()
        max_a_minus.append(a_minus[minus_cnt])
        ans = calc(max_a_minus + max_a_plus)
else:
    flag1 = 1
    flag2 = 1
    if len(max_a_minus) == 0:
        ans1 = -float("inf")
        flag1 = 0
        diff1 = float("inf")
    if len(max_a_plus) == 0:
        ans2 = -float("inf")
        flag2 = 0
        diff2 = float("inf")
    if flag1:
        c1 = deepcopy(max_a_minus)
        c2 = deepcopy(max_a_plus)
        diff1 = abs(abs(c1.pop()) - abs(a_plus[plus_cnt]))
        c2.append(a_plus[plus_cnt])
        ans1 = calc(c1 + c2)
    if flag2:
        c3 = deepcopy(max_a_minus)
        c4 = deepcopy(max_a_plus)
        diff2 = abs(abs(c4.pop()) - abs(a_minus[minus_cnt]))
        c3.append(a_minus[minus_cnt])
        ans2 = calc(c3 + c4)
    ans = ans1 if diff1 <= diff2 else ans2
a_abs = a_abs[::-1]
ans2 = -calc(a_abs[:k])
if ans != -float("inf"):
    print(ans%mod)
else:
    print(ans2%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
from copy import deepcopy
mod = 10**9 + 7

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a = sorted(a, key=lambda x: abs(x))[::-1]
a_plus = [int(x) for x in a if x > 0]
a_minus = [int(x) for x in a if x < 0]
a_abs = [abs(x) for x in a]

def calc(x):
    res = 1
    for i in x:
        res*=abs(i)
        res %= mod 
    return res

max_a = a[:k]
max_a_minus = []
max_a_plus = []
minus_cnt = 0

for i in max_a:
    if i == 0:
        print(0)
        sys.exit()
    if i < 0:
        minus_cnt += 1
        max_a_minus.append(i)
    else:
        max_a_plus.append(i)

if minus_cnt % 2 == 0:
    print(calc(max_a))
    sys.exit()

plus_cnt = k - minus_cnt

if len(a_minus) <= minus_cnt and len(a_plus) <= plus_cnt:
    ans = -float('inf')
elif len(a_minus) <= minus_cnt:
    if len(max_a_minus) == 0:
        ans = -float("inf")
    else:
        max_a_minus.pop()
        max_a_plus.append(a_plus[plus_cnt])
        ans = calc(max_a_plus + max_a_minus)
elif len(a_plus) <= plus_cnt:
    if len(max_a_plus) == 0:
        ans = -float("inf")
    else:
        max_a_plus.pop()
        max_a_minus.append(a_minus[minus_cnt])
        ans = calc(max_a_minus + max_a_plus)
else:
    flag1 = 1
    flag2 = 1
    if len(max_a_minus) == 0:
        ans1 = -float("inf")
        flag1 = 0
        diff1 = float("inf")
    if len(max_a_plus) == 0:
        ans2 = -float("inf")
        flag2 = 0
        diff2 = float("inf")
    if flag1:
        c1 = deepcopy(max_a_minus)
        c2 = deepcopy(max_a_plus)
        diff1 = abs(c1.pop() - a_plus[plus_cnt])
        c2.append(a_plus[plus_cnt])
        ans1 = calc(c1 + c2)
    if flag2:
        c3 = deepcopy(max_a_minus)
        c4 = deepcopy(max_a_plus)
        diff2 = abs(c4.pop() - a_minus[minus_cnt])
        c3.append(a_minus[minus_cnt])
        ans2 = calc(c3 + c4)
    ans = ans1 if diff1 <= diff2 else ans2
a_abs = a_abs[::-1]
ans2 = -calc(a_abs[:k])
if ans != -float("inf"):
    print(ans%mod)
else:
    print(ans2%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
from copy import deepcopy
mod = 10**9 + 7

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a = sorted(a, key=lambda x: abs(x))[::-1]
a_plus = [int(x) for x in a if x > 0]
a_minus = [int(x) for x in a if x < 0]
a_abs = [abs(x) for x in a]

def calc(x):
    res = 1
    for i in x:
        res*=i
        res %= mod 
    return res

max_a = a[:k]
max_a_minus = []
max_a_plus = []
minus_cnt = 0

for i in max_a:
    if i == 0:
        print(0)
        sys.exit()
    if i < 0:
        minus_cnt += 1
        max_a_minus.append(i)
    else:
        max_a_plus.append(i)

if minus_cnt % 2 == 0:
    print(calc(max_a))
    sys.exit()

plus_cnt = k - minus_cnt

if len(a_minus) <= minus_cnt and len(a_plus) <= plus_cnt:
    ans = -float('inf')
elif len(a_minus) <= minus_cnt:
    if len(max_a_minus) == 0:
        ans = -float("inf")
    else:
        max_a_minus.pop()
        max_a_plus.append(a_plus[plus_cnt])
        ans = calc(max_a_plus + max_a_minus)
elif len(a_plus) <= plus_cnt:
    if len(max_a_plus) == 0:
        ans = -float("inf")
    else:
        max_a_plus.pop()
        max_a_minus.append(a_minus[minus_cnt])
        ans = calc(max_a_minus + max_a_plus)
else:
    flag1 = 1
    flag2 = 1
    if len(max_a_minus) == 0:
        ans1 = -float("inf")
        flag1 = 0
    if len(max_a_plus) == 0:
        ans2 = -float("inf")
        flag2 = 0
    if flag1:
        c1 = deepcopy(max_a_minus)
        c2 = deepcopy(max_a_plus)
        c1.pop()
        c2.append(a_plus[plus_cnt])
        ans1 = calc(c1 + c2)
    if flag2:
        c3 = deepcopy(max_a_minus)
        c4 = deepcopy(max_a_plus)
        c4.pop()
        c3.append(a_minus[minus_cnt])
        ans2 = calc(c3 + c4)
    ans = max(ans1, ans2)
a_abs = a_abs[::-1]
ans2 = -calc(a_abs[:k])
if ans > ans2:
    print(ans%mod)
else:
    print(ans2%mod)

Submission status: Wrong Answer

Solution code:
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a=sorted(a)[max(a)<0<k%2and-k:]
s=1
while k-y>1:
 if(t:=a[y]*a[y+1])>a[-1]*a[-2]:s=s*t%M;y+=2
 else:s=s*a.pop()%M;k-=1
if k-y:s*=a[-1]
print(s)

Submission status: Wrong Answer

Solution code:
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a=sorted(a)[a[0]<0<k%2and-k:]
s=1
while k-y>1:
 if(t:=a[y]*a[y+1])>a[-1]*a[-2]:s=s*t%M;y+=2
 else:s=s*a.pop()%M;k-=1
if k-y:s*=a[-1]
print(s%M)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())

        if (len(ans_neg) & 1) and ((not ans_pos) or (ans_pos[-1] != 0)):
            if not pos or not ans_neg:
                drop_pos = True
            elif not neg or not ans_pos:
                drop_pos = False
            else:
                drop_pos = pos[-1] * ans_pos[-1] < neg[-1] * ans_neg[-1]

            if drop_pos:
                ans_neg.append(neg.pop())
                ans_pos.pop()
            else:
                ans_pos.append(pos.pop())
                ans_neg.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        print(a)
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

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 * (-1 if neg else 1))
            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 == -1 * 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 * -1 * 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 a3

    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:
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 v > 0 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 a3

    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())
l=sorted(list(map(int,input().split())))
MOD=10**9+7

def maxProductSubarrayOfSizeK(A, n, k):
    t=1
    #case 1: when the max.element is 0 and k is odd
    if(max(l)==0 and k%2!=0):
        return 0
    #case 2:when the max.element is less than 0 and k is again odd
    if(l[n-1]<=0 and k%2!=0):
        for i in range(n-1,n-k+1,-1):
            t=(t*l[i])%MOD
        return t
    i=0
    j=n-1
    #case3: when the max.element is greater than 0 and k is odd
    if (k & 1): 
        t=t*A[j]%MOD 
        j-= 1
        k-=1
    k>>=1
    print(k)
    #case 4 when k is even
    for it in range(k):
        lp=l[i]*l[i+1]
        rp=l[j]*l[j-1]
        if(lp>rp):
            t=(t*lp)%MOD
            i=i+2   
        else:
            t=(t*rp)%MOD
            j=j-2
    return t
print(maxProductSubarrayOfSizeK(l,n,k))

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1


for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2


if pn == 0:
    if K == N and [0,0] in A:
        print(0)
        sys.exit()
    for i in range(K):
        prod = prod * A[i][0] % MOD
    print(prod)
    sys.exit()

elif pn == 1:
    if K == N:
        if [0,0] in A:
            print(0)
            sys.exit(0)
        for i in range(N):
            prod = prod * A[i][0] % MOD
            prod = prod * (-1) % MOD
        print(prod)
        sys.exit()
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp == N:
        if K % 2 == 0:
            for i in range(K):
                prod = prod * A[i][0] % MOD
        elif K % 2 == 1:
            for i in range(K):
                prod = prod * A[-1-i][0] % MOD
                prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif lastp == -1 or indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[indn][0] % MOD
            else:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
        prod = max(prod1,prod2)
    print(prod)

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1


for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2


if pn == 0:
    if K == N and [0,0] in A:
        print(0)
        sys.exit()
    for i in range(K):
        prod = prod * A[i][0] % MOD
    print(prod)
    sys.exit()

elif pn == 1:
    if K == N:
        if [0,0] in A:
            print(0)
            sys.exit(0)
        for i in range(N):
            prod = prod * A[i][0] % MOD
            prod = prod * (-1) % MOD
        print(prod)
        sys.exit()
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp == N:
        if K % 2 == 0:
            for i in range(K):
                prod = prod * A[i][0] % MOD
        elif K % 2 == 1:
            for i in range(K):
                B = list(reversed(A))
                prod = prod * B[i][0] % MOD
                prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[indn][0] % MOD
            else:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
        prod = max(prod1,prod2)
    print(prod)