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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
sA = sorted(A, reverse=True)

f = 0
b = -1
k = 0
if K == 1:
    print(max(sA)%(10**9+7))
    exit()

res = 1
m = max(sA)
while k < K:
    if m > 0 | (K % 2 == 0):
        if K - k >= 2:
            if A[f]*A[f+1] <= A[b]*A[b-1]:
                res *= A[b]*A[b-1]
                b = b - 2
                k += 2
            else:
                res *= A[f]
                f = f + 1
                k += 1
        else:
            res *= A[f]
            f = f + 1
            k += 1
    else:
        k = K
        for a in range(K):
            res *= sA[a]

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:33:15 2020

"""

N, K = map(int,input().split())
A = list(map(int, input().split())) 
A = sorted(A, key=abs, reverse=True)
mod = 10**9+7
ans = 1
lp = 10**6
lm = 10**6
lpflag = 0
lmflag = 0
rp = 10**6
rm = 10**6
rpflag = 0
rmflag = 0
ans1 = 0
ans2 = 0
minus = 0
flag0 = 0
for i in range(K):
    if A[i] < 0:
        minus = (minus+1)%2
    ans = ans * A[i] % mod
if not minus:
    print(ans)
else:
    for i in range(K-1,-1,-1):
        if lp < 10**6 and lm < 10**6:
            break
        if A[i] > 0 and lpflag == 0:
            lpflag = 1
            lp = i
        elif A[i] < 0 and lmflag == 0:
            lmflag = 1
            lm = i
    for i in range(K,N):
        if rp < 10**6 and rm < 10**6:
            break
        if A[i] > 0 and rpflag == 0:
            rpflag = 1
            rp = i
        elif A[i] < 0 and rmflag == 0:
            rmflag = 1
            rm = i
        elif A[i] == 0:
            flag0 = 1
    if lpflag*rmflag == 1:
        ans = 1
        for i in range(K):
            if not i == lp:
                ans = ans * A[i] % mod
        ans = ans * A[rm] % mod
        ans1 = ans
    if lmflag*rpflag == 1:
        ans = 1
        for i in range(K):
            if not i == lm:
                ans = ans * A[i] % mod
        ans = ans * A[rp] % mod    
        ans2 = ans
    if lpflag*rmflag == 0 and lmflag*rpflag == 0:
        ans = 1
        for i in range(N-1,N-1-K,-1):
            ans = ans * A[i] % mod
        if flag0:
            print(0)
        else:
            print(ans)

    else:
        print(max(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
#import bisect
#import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
import itertools
import heapq

def input():
    return sys.stdin.readline().rstrip()


def main():
    N,K =map(int,input().split())
    A =list(map(int,input().split()))
    mod =10**9+7
    A.sort()
    A = deque(A)
#    print(A)
    A_minus = deque([s for s in A if s <0])
    A_plus =deque( [s for s in A if s >=0])

#    print(A_plus)
#    print(A_minus)
    AA = []
    if N==K:
        ans =1
        for i in A:
            ans *=i %mod
        print(ans)

    elif K%2 ==0:
        while len(A_minus)>=2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1*a2)

        while len(A_plus)>=2:
            a1 =A_plus.pop()
            a2 =A_plus.pop()
            AA.append(-a1*a2)
        ans =1
        heapq.heapify(AA)
        for i in range(K//2):
            ans *= (-1 * heapq.heappop(AA)) %mod
        print(ans%mod)

    elif len(A_plus)==0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop() %mod
        print(ans)

    else:
        ans = A_plus.pop()
        while len(A_minus)>=2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1*a2)

        while len(A_plus)>=2:
            a1 =A_plus.pop()
            a2 =A_plus.pop()
            AA.append(-a1*a2)

        heapq.heapify(AA)
        for i in range(K//2):
            ans *= (-1 * heapq.heappop(AA)) %mod
        print(ans)









if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
from functools import reduce

MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus = [i for i in a if i > 0]
plus.sort(reverse=True)
minus = [i for i in a if i < 0]
minus.sort(reverse=True)
zero = [i for i in a if i == 0]

res = 1
if len(plus) + len(minus) < k:
    res = 0
    print(res % MOD)
    exit()
if len(plus) + len(minus) == k:
    if len(minus) % 2 == 0:
        res = reduce(lambda a, b: a * b, plus, 1) * reduce(lambda a, b: a * b, minus, 1)
        print(res % MOD)
        exit()
    else:
        res = 0
        print(res % MOD)
        exit()
elif len(minus) == 0:
    res = reduce(lambda a,b: a*b, plus[:k])
    print(res%MOD)
    exit()
elif len(plus) == 0:
    if k % 2 == 0:
        res = reduce(lambda a, b: a*b, minus[-k:])
        print(res%MOD)
        exit()
    else:
        if len(zero) > 0:
            res = 0
        else:
            res = reduce(lambda a,b: a*b, minus[:k])
        print(res%MOD)
        exit()
else:
    plus = [-i for i in plus]
    heapq.heapify(plus)
    heapq.heapify(minus)
    c_p = []
    c_m = []
    last_p = False
    while len(c_p)+len(c_m) < k:
        if len(plus) > 0:
            can_p = heapq.heappop(plus)
        else:
            can_p = 10**9+1
        if len(minus) > 0:
            can_m = heapq.heappop(minus)
        else:
            can_m = 10**9+1
        if can_p < can_m:
            heapq.heappush(c_p, -can_p)
            heapq.heappush(minus, can_m)
            last_p = True
        else:
            heapq.heappush(c_m, -can_m)
            heapq.heappush(plus, can_p)
            last_p = False
    if len(c_m) % 2 == 0:
        res = reduce(lambda a, b: a * b, c_p, 1) * reduce(lambda a, b: a * b, c_m, 1)
        print(res % MOD)
        exit()
    if last_p:
        # 最大の負を入れる/一番小さい負を除いて最大の正を入れる
        if len(minus) > 0:
            heapq.heappop(c_p)
            can_m = heapq.heappop(minus)
            heapq.heappush(c_m, -can_m)
        else:
            heapq.heappop(c_m)
            can_p = heapq.heappop(plus)
            heapq.heappush(c_p, -can_p)
    else:
        # 最大の正を入れる/一番小さい正を除いて最大の負を入れる
        if len(plus) > 0:
            heapq.heappop(c_m)
            can_p = heapq.heappop(plus)
            heapq.heappush(c_p, -can_p)
        else:
            heapq.heappop(c_p)
            can_m = heapq.heappop(minus)
            heapq.heappush(c_m, -can_m)
    res = reduce(lambda a, b: a * b, c_p, 1) * reduce(lambda a, b: a * b, c_m, 1)
    print(res % MOD)

Submission status: Wrong Answer

Solution code:
mod = 1000000007

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

A_des = sorted(A, key=lambda x: abs(x), reverse=True)
A_ase = sorted(A, key=lambda x: abs(x))

res_d = 1
res_a = 1

for i in range(K):
    res_d *= A_des[i]
    res_a *= A_ase[i]

res = int(max(res_d, res_a) % mod)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

B.sort(reverse=True)
C.sort(reverse=True)

if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod

    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

if K>len(B)+len(C):
    print(0)
    sys.exit()

if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
            
    elif Z==[] and K%2==1:
        C.reverse()
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(-ANS%mod)
        
    elif K%2==1:
        print(0)
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod

    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)

        while True:
            if c_start+ind+1<len(C) and len(B)-2-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)+1

        while True:
            if c_start+ind+1<len(C) and len(B)-3-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-2-ind]*B[len(B)-3-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-2-ind]*B[len(B)-3-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    print(S%mod)

Submission status: Wrong Answer

Solution code:
def resolve():
    def addans(i, ans):
        return ans * i % mod
    import sys
    import bisect
    from collections import deque
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    inf = float("inf")
    n, k = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    l = bisect.bisect_left(a, 0)
    r = bisect.bisect_right(a, 0)
    ans = 1
    d = deque(a)
    if k % 2 == 1:
        ans = d.pop()
        k -= 1
    try:
        m = d.popleft() * d.popleft()
    except:
        m = -inf
    try:
        p = d.pop() * d.pop()
    except:
        p = -inf
    for _ in range(k // 2):
        if p >= m:
            ans = addans(p, ans)
            try:
                p = d.pop() * d.pop()
            except:
                p = -inf
        else:
            ans = addans(m, ans)
            try:
                m = d.popleft() * d.popleft()
            except:
                m = -inf
    print(ans)


if __name__ == '__main__':
    resolve()

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 ((neg & (~1)) + pos < K) or (neg & 1 and K == N) or (pos == 0 and K & 1):
        # マイナスになっちゃう
        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 != 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:
def solve():
    ret = 1
    for i in range(n):
        if L[i][2]:
            ret *= L[i][0]
            ret %= MOD
    return ret % MOD

n, k = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
INF = float('inf')
L = []
p, m = 0, 0
for a in A:
    if a < 0:
        m += 1
        L.append([abs(a), -1, False])
    else:
        L.append([a, 1, False])
L = sorted(L, key= lambda x: x[0], reverse=True)
pm = 1
lp, lm = None, None
for i in range(k):
    L[i][2] = True
    pm *= L[i][1]
    if L[i][1] >= 0:
        lp = i
    else:
        lm = i
if pm >= 0:
    ans = solve()
else:
    ans1, ans2 = -INF, -INF
    if lp:
        j = k
        while j < n:
            if L[j][1] < 0:
                L[lp][2] = False
                L[j][2] = True
                ans1 = solve()
                L[lp][2] = True
                L[j][2] = False
                break
            j += 1
    if lm:
        j = k
        while j < n:
            if L[j][1] >= 0:
                L[lm][2] = False
                L[j][2] = True
                ans2 = solve()
                L[lm][2] = True
                L[j][2] = False
                break
            j += 1
    ans = max(ans1, ans2)
    if ans1 == ans2 == -INF:
        L = sorted(L, key=lambda x: x[0])
        ans = 1
        for i in range(k):
            ans *= L[i][0]
        ans = -1 * ans % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
cnt=1
if a[-1]<0 and k%2!=0:
  for j in range(k):
    cnt*=a[-(j+1)]
    cnt%=1000000007
  print(cnt)
else:
  for i in range(k//2):
    if a[0]*a[1]>a[-1]*a[-2] and a[1]<0:
      cnt*=a[0]*a[1]
      cnt%=1000000007
      a.pop(0)
      a.pop(0)
    else:
      cnt*=a[-1]*a[-2]
      cnt%=1000000007
      a.pop(-1)
      a.pop(-1)
  if k%2!=0:
    cnt*=a[-1]
    cnt%=1000000007
    print(cnt)
  else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from operator import mul
from functools import reduce
n, k = map(int, input().split())
arr = list(map(int, input().split()))


MOD = 10**9 + 7

# negを奇数個選ばないといけないシチュエーションかどうか
neg = [x < 0 for x in arr]

if all(neg) and k % 2 == 1:
    arr.sort(reverse=True)
    print(reduce(mul, arr[:k]) % MOD)
    sys.exit()

arr_p = [x for x in arr if x >= 0]
arr_n = [x for x in arr if x < 0]

arr_p.sort(reverse=True)
arr_n.sort()

ans = -1 << 60
for i in range(0, min(k, len(arr_n)) + 1, 2):
    if i > len(arr_n) or k - i > len(arr_p):
        continue
    if i == 0:
        neg = 1
    else:
        neg = reduce(mul, arr_n[:i])
    if k - i == 0:
        pos = 1
    else:
        pos = reduce(mul, arr_p[:k - i])
    ans = max(ans, neg * pos)

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
p=1000000007
product = 1
t=0


def moduloMultiplication(a, b, mod):
    res = 0  # Initialize result

    # Update a if it is more than
    # or equal to mod
    a = a % mod

    while (b):

        # If b is odd, add a with result
        if (b & 1):
            res = (res + a) % mod

            # Here we assume that doing 2*a
        # doesn't cause overflow
        a = (2 * a) % mod

        b >>= 1  # b = b / 2

    return res
if A[n - 1] == 0 and (k & 1):
      print(0)
if A[n - 1] <= 0 and (k & 1):
        for i in range(n - 1, n - k - 1, -1):
            product *=A[i]
        print(product%p)


else:

    i = 0
    j = n - 1
    if k & 1:
                product = moduloMultiplication(A[j],product,p)
                j -= 1
                k -= 1

    k >>= 1
    for itr in range(k):

                left_product = moduloMultiplication(A[i] , A[i + 1],p)

                right_product = moduloMultiplication(A[j] , A[j - 1],p)

                if left_product > right_product:
                    product = moduloMultiplication(product,left_product,p)
                    i += 2

                else:
                    product = moduloMultiplication(product,right_product,p)
                    j -= 2

    print(product%p)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=abs, reverse=True)

mod = 10**9+7
res = 1
last_plus_index = -1
last_minus_index = -1
# 
# for i in range(K):
#     res *= A[i]
#     if A[i] < 0:
#         last_minus_index = i
#     if A[i] > 0:
#         last_plus_index = i

if res >= 0:
    print(res % mod)
    exit()

# if K-1 == last_minus_index:
#     for i in range(K, N):
#         if A[i] > 0:
#             res = res // A[last_minus_index] * A[i]
#             print(res % mod)
#             exit()
#         if i == N-1:
#             if last_plus_index != -1:
#                 res = res // A[last_plus_index] * A[K]
#                 print(res % mod)
#                 exit()
#             else:
#                 # 解が0以下
#                 A = sorted(A, reverse=True)
#                 res = 1
#                 for i in range(K):
#                     res *= A[i]
#                 print(res % mod)
#                 exit()
#
# else:
#     for i in range(K, N):
#         if A[i] < 0:
#             res = res // A[K-1] * A[i]
#             print(res % mod)
#             exit()
#         if i == N-1:
#             res = res // A[last_minus_index] * A[K]
#             print(res % mod)
#             exit()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10**9+7
M = []
P = []
Z = []
for i in a:
    if i < 0:
        M.append(i)
    elif i > 0:
        P.append(i)
    else:
        Z.append(i)
P.sort(reverse=True)
M.sort()
lenZ = len(Z)
lenM = len(M)
lenP = len(P)
if n - k < lenZ:
    print(0)
    exit()
elif lenZ != 0 and n - k == lenZ and lenM % 2 == 1:
    print(0)
    exit()
elif n - k == lenZ:
    ans = 1
    for i in P:
        ans*=i
        ans%=MOD
    for i in M:
        ans*=i
        ans%=MOD
    if lenZ != 0 and lenM % 2 == 1: #必要ないと思うけど頭の中がこんがらがって居るので一応
        print(0)
        exit()
    print(ans)
    exit()
elif lenP == 0:
    M = M[::-1]
    ans = 1
    for i in range(k):
        ans*=M[i]
        ans%=MOD
    print(ans)
    exit()
count = 0
ans = []
i = 0
j = 0
if k % 2 == 1:
    ans.append(P[0])
    i+=1
    k-=1
    if k == 0:
        print(P[0])
        exit()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

N , K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
MN = 1000000007

tA = [abs(a) for a in A]
num = tA
indices = [*range(len(num))]
sorted_indices = sorted(indices, key=lambda i: -num[i])
sorted_num = [num[i] for i in sorted_indices]
#print(sorted_num)      # ==> [9, 7, 6, 5, 1]
target = [0]*N
for i,j in enumerate(sorted_indices):
    target[i] = A[j]
#print(target)

if all([i < 0 for i in target]):
    ans = 1
    for s, t in enumerate(reversed(target)):
        if s < K:
            ans = ans * t  % MN
        else:
            break

else:
    ans = 1
    flag = 1
    for s, t in enumerate(target):
        if s < K-1:
            if t < 0:
                flag *= -1
            ans = ans * t  % MN

        else:
            if flag * t >= 0:
                ans = ans * t  % MN
                break
            else:
                continue
        #print(ans)
print(ans)

Submission status: Wrong Answer

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

a_plus = []
a_minus = []
cnt_0 = 0

for ai in a:
    if(ai==0):
        cnt_0 += 1
    elif(ai > 0):
        a_plus.append(ai)
    else:
        a_minus.append(ai)

a_plus.sort(reverse = True)
a_minus.sort()

cnt_p = len(a_plus)
cnt_m = len(a_minus)

if(cnt_p + cnt_m < k):
    print(0)
    exit()


if(cnt_m == n)&(k%2==1):
    ans = 1
    for i in range(k):
        ans *= a_minus[cnt_m - 1 - i]
        ans %= mod
    print(ans)
    exit()
elif(cnt_p == 0)&(k%2==1):
    print(0)
    exit()

p_ind = 0
m_ind = 0

ans = 1
if(k%2==1):
    ans = a_plus[0]
    p_ind = 1

for i in range(k//2):
    tmp_p = 0
    tmp_m = 0
    if(p_ind + 2 <= cnt_p ):
        tmp_p = a_plus[p_ind] * a_plus[p_ind+1]

    if(m_ind + 2 <= cnt_m ):
        tmp_m = a_minus[m_ind] * a_minus[m_ind+1]

    if(tmp_p > tmp_m):
        ans *= tmp_p
        p_ind += 2
    else:
        ans *= tmp_m
        m_ind += 2
    ans %= mod


ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9 + 7

def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)

def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]

def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

def prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= abs(A[i])
        prod %= MOD
    if add != None:
        prod *= abs(A[add])
        prod %= MOD
    return prod

N, K = read_int_list()
A = read_int_list()

A.sort(key=lambda i: -abs(i))

last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove_plus = None
add_plus = None
remove_minus = None
add_minus = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None and remove_minus == None:
            remove_minus = last_minus
            add_minus = i
            sig = 1
        elif A[i] < 0 and last_plus != None and remove_plus == None:
            remove_plus = last_plus
            add_plus = i
            sig = 1
        elif A[i] == 0:
            sig = 0
            break

if sig == 0:
    print(0)
elif sig > 0:
    if remove_plus != None and remove_minus != None:
        if abs(A[remove_plus]/A[add_plus]) > abs(A[remove_minus]/A[add_minus]):
            ap = prod(A, K, add_minus, remove_minus)
        else:
            ap = prod(A, K, add_plus, remove_plus)
    elif remove_plus != None:
        ap = prod(A, K, add_plus, remove_plus)
    else:
        ap = prod(A, K, add_minus, remove_minus)
    print(ap)
else:
    ap = prod(A[::-1], K, None, None)
    print((MOD-ap) % MOD)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 1000000007

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)


if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3

rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -100000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = 10000000000    
        
        if plus_target >= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
        
    if answer < 0:
        answer = answer * pow(minuss[minus_now-1],mod-2,mod)
        answer = answer * pluss[plus_now]
elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss, reverse = True)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 100000000000
        
        if minus_now < len(minuss):
            minus_target = minuss[minus_now]
        else:
            minus_target = -10000000000    
        
        if plus_target <= -minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
print(answer%mod)

Submission status: Wrong Answer

Solution code:
from math import log, log10, log2

def solve():
    MOD = 10**9 + 7

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

    numPos, num0, numNeg = 0, 0, 0
    for A in As:
        if A > 0:
            numPos += 1
        elif A == 0:
            num0 += 1
        else:
            numNeg += 1
#    print('numPos:', numPos, '/ num0:', num0, '/ numNeg:', numNeg)

    if numPos + numNeg < K:
        ans = 0
    else:
        posAs, negAs = [], []
        for A in As:
            if A > 0:
                posAs.append(A)
            elif A < 0:
                negAs.append(A)
        N = numPos + numNeg
#        print('posAs:', posAs, '/ negAs:', negAs)

        if K == N and numNeg%2 != 0:
            if num0 > 0:
                ans = 0
            else:
                ans = 1
                for A in posAs:
                    ans *= A
                    ans %= MOD
                for A in negAs:
                    ans *= A
                    ans %= MOD

        elif K%2 != 0 and numPos == 0:
            if num0 > 0:
                ans = 0
            else:
                negAs.sort(reverse=True)
#                print('negAs:', negAs)
                ans = 1
                for A in negAs[:K]:
                    ans *= A
                    ans %= MOD

        else:
            posAs.sort(reverse=True)
            negAs.sort()
            acc = 0
            accPoss = [acc]
            for A in posAs:
                acc += log(A)
                accPoss.append(acc)
            acc = 0
            accNegs = [acc]
            for A in negAs:
                acc += log(-A)
                accNegs.append(acc)
#            print('accPoss:', accPoss)
#            print('accNegs:', accNegs)

            ans = -1
            xMax = -1
            for x in range(0, K+1, 2):
                y = K - x
                if x > numNeg or y > numPos:
                    continue
                prod = accNegs[x] + accPoss[y]
                if prod > ans:
                    ans = prod
                    xMax = x

            ans = 1
            for A in negAs[:xMax]:
                ans *= A
                ans %= MOD
            for A in posAs[:K-xMax]:
                ans *= A
                ans %= MOD

    print(ans % MOD)


solve()

Submission status: Wrong Answer

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

from bisect import bisect_left


def solve():
    N, K = map(int, input().split())

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

    As.sort()
    index = bisect_left(As, 0)

    # neg = As[:index]
    # pos = As[index:]
    # pos = pos[bisect_left(pos, 1):]
    # pos.sort(reverse=True)
    # print(pos, neg)

    pos = sorted(As, reverse=True)
    ans = 1
    mod = 10 ** 9 + 7

    if N == K:
        for p in pos:
            ans *= p
            ans %= mod
        return ans

    if index == N:
        for p in pos[:K]:
            ans *= p
            ans %= mod
        return ans

    pl = 0
    pr = N - 1

    for i in range(K//2):
        left = pos[pl] * pos[pl+1]
        right = pos[pr] * pos[pr-1]

        if left > right:
            ans *= left
            ans %= mod
            pl += 2
        else:
            ans *= right
            ans %= mod
            pr -= 2

    if K % 2:
        ans *= max(pos[pl], pos[pr])
        ans %= mod

    return ans


def main():
    print(solve())


if __name__ == "__main__":
    main()