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:
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    from collections import Counter
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    posi = [a for a in A if a > 0]
    nega = [a for a in A if a < 0]
    posi.sort(reverse=True)
    nega.sort(reverse=True)
    A.sort(reverse=True, key=abs)
    if len(posi) + len(nega) < K:
        # 0を含まなければいけないとき
        return print(0)

    ans = modint(1)
    if K % 2 == 1 and len(posi) < K:
        # 結果が負数
        # 絶対値が小さいやつをK個取ってくる
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
    else:
        # 結果が正になるように注意しなければいけない
        # skipしてかけるものがなくなったらこわい
        # 負数がK以下の奇数個しかないとハマる
        if sum(a < 0 for a in A[:K]) % 2 == 0:
            for a in A[:K]:
                ans *= a
        else:
            ans1 = 1  # 正を取り除く
            ans2 = 1  # 負を取り除く
            posi = [a for a in A[:K] if a > 0]
            nega = [a for a in A[:K] if a < 0]
            p_remove = False
            for a in A[:K][::-1]:
                if a > 0 and not p_remove:
                    p_remove = True
                    continue
                ans1 *= a
            n_remove = False
            for a in A[:K][::-1]:
                if a < 0 and not n_remove:
                    n_remove = True
                    continue
                ans2 *= a
            mul1 = 0  # 一番大きい正
            mul2 = 0  # 　一番大きい負
            for a in A[K:]:
                if mul1 == 0 and a > 0:
                    mul1 = a
                if mul2 == 0 and a < 0:
                    mul2 = a
                if mul1 != 0 and mul2 != 0:
                    break
            if len(posi) == 0 or mul2 == 0:
                ans = ans2 * mul1
            elif len(nega) == 0 or mul1 == 0:
                ans = ans1 * mul2
            else:
                ans = max(int(ans1*mul2), int(ans2*mul1))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

# Author : raj1307 - Raj Singh
# Date   : 05.07.2020

from __future__ import division, print_function

import os,sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def msi(): return map(str,input().strip().split(" "))
def li():  return list(mi())

def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import log,sqrt,factorial,cos,tan,sin,radians
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *
#import threading
#from itertools import permutations
#Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[1] 
def sort2(l):return sorted(l, key=getKey,reverse=True)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))

def ceil(x,y):
    if x%y==0:
        return x//y
    else:
        return x//y+1

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



def read():
    sys.stdin  = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 




def main():
    


    #for _ in range(ii()):


    n,k=mi()
    a=li()
    if n==k:

        ans=1

        for i in range(n):

            x=(a[i]%mod+mod)%mod;
            ans=(ans*x)%mod
        print(ans)
        return







    x=[]
    y=[]

    for i in range(n):
        if a[i]<0:
            y.append(a[i])
        else:
            x.append([a[i],1])

    neg=[]


    y.sort()
    ex=-1

    for i in range(0,len(y),2):
        if i==len(y)-1:
            ex=y[i]
            continue

        x.append([y[i]*y[i+1],2])



    x.sort(reverse=True)
   


    ans=1
    cnt=0


    p=[]
    q=[]

    ext=-1


    for i in range(len(x)):
        #print(cnt,x[i][1],cnt)


        if cnt+x[i][1]<=k:

            if x[i][1]==1:
                p.append(x[i][0])
            else:
                q.append(x[i][0])

            ans=(ans*x[i][0])%mod
            cnt+=x[i][1]

        elif cnt!=k:

            ext=max(ext,x[i][0])



    if cnt==k:
        print(ans)
        return



    if len(p)!=0:

        ans=1

        for i in range(len(p)-1):
            ans=(ans*p[i])%mod
        for j in range(len(q)):
            ans=(ans*q[i])%mod
        ans=ans*ext
        ans%=mod
        print(ans)
        return

    ans=1
    cnt=0
    for i in range(len(y)-1,-1,-1):
        if cnt==k:
            break

        x=(mod+y[i]%mod)%mod
        ans*=x
        ans%=mod
        cnt+=1
    print(ans)












    









    








# region fastio
# template taken from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
    #read()
    main()
    #dmain()

# Comment Read()

Submission status: Wrong Answer

Solution code:
import itertools


def out(X):
    return list(itertools.accumulate(X, func=lambda x, y: x * y % mod))[-1]


N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()], key=lambda x: -abs(x))
mod = 10**9 + 7
cnt = 0
ipos = ineg = -1
for i, a in enumerate(A[:K]):
    if a < 0:
        cnt += 1
        ineg = i
    else:
        ipos = i
if cnt % 2 == 0:
    print(out(A[:K]))
else:
    oneg = opos = -10**10
    for i, a in enumerate(A[K:]):
        if a < 0 and ipos != -1:
            X = A[:ipos] + A[ipos + 1:K] + [A[K + i]]
            oneg = out(X)
            ipos = -1
        elif a > 0 and ineg != -1:
            X = A[:ineg] + A[ineg + 1:K] + [A[K + i]]
            opos = out(X)
            ineg = -1
    if oneg != -10**10 or opos != -10**10:
        print(max(opos, oneg))
    else:
        C = A[::-1]
        print(out(C[:K]))

Submission status: Wrong Answer

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

    plus = [A[i] for i in range(N) if A[i] >= 0]
    minus = [A[i] for i in range(N) if A[i] < 0]

    ans = 1

    id = 0
    id2 = 0
    P = len(plus)
    M = len(minus)
    plus.sort(reverse=True)

    mod = 10**9 + 7

    if P == 0:
        if K % 2 == 0:
            minus.sort()
            for i in range(K):
                ans *= minus[i]
                ans %= mod
        else:
            minus.sort(reverse=True)
            for i in range(K):
                ans *= minus[i]
                ans %= mod

    elif M == 0:
        for i in range(K):
            ans *= plus[i]
            ans %= mod

    else:

        p = P // 2
        m = M // 2
        if K > (p+m)*2 and (K % 2 == 1 and P % 2 == 0):  # 絶対値が小さい方から貪欲
            A.sort(key=lambda x: abs(x))
            for i in range(K):
                ans *= A[i]
                ans %= mod

        else:  # 絶対値が大きい方から貪欲
            minus.sort()
            pp = [plus[i]*plus[i+1] for i in range(P // 2)]
            mm = [minus[i] * minus[i+1] for i in range(M//2)]

            id = 0
            id2 = 0

            pp.sort(reverse=True)
            mm.sort(reverse=True)
            pp.append(1)
            mm.append(1)
            for i in range((K // 2) - 1):
                if id == p - 1:
                    ans *= mm[id2]
                    id2 += 1
                elif id2 == m:
                    ans *= pp[id]
                    id += 1
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                    id += 1
                else:
                    ans *= mm[id2]
                    id2 += 1

                ans %= mod

            if K % 2 == 1:
                if id >= p-1:
                    ans *= mm[id2]
                    ans *= plus[id*2]
                else:
                    ans *= pp[id]
                    id += 1
                    ans *= plus[id*2]
            else:
                if id >= p:
                    ans *= mm[id2]
                elif id2 >= m:
                    ans *= pp[id]
                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                else:
                    ans *= mm[id2]

    print(ans % mod)


main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[]
m=[]
z=0
a.sort(reverse=True)
for i in range(n):
    if a[i]>0:
        p.append(a[i])
    elif a[i]==0:
        z+=1
    else:
        m.append(a[i])
nump=len(p)
numm=len(m)
ans=1
if nump+numm<k and z!=0:
    print(0)
elif numm<2 and nump>=k:
    for i in range(k):
        ans*=p[i]
        ans%=10**9+7
    print(ans)
elif 2*(numm//2)+nump<k:
    if z!=0:
        print(0)
    else:
        a.sort()
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0:
    if z!=0:
        print(0)
    else:
        for i in range(k):
            ans*=m[i]
            ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
    m.sort()
    nump=(nump-1)//2
    numm=numm//2
    nump1=0
    nump2=0
    numm1=0
    numm2=0
    for i in range(k//2):
        if nump2==nump:
            nump1=0
        else:
            nump1=p[nump2*2]*p[nump2*2+1]
        if numm2==numm:
            numm1=0
        else:
            numm1=m[numm2*2]*m[numm2*2+1]
        if numm1>nump1:
            num=numm1
            numm2+=1
        else:
            num=nump1
            nump2+=1
        ans*=num
        ans%=10**9+7
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    mod = 10**9+7
    n,k = map(int,input().split())
    arr = list(map(int,input().split()))
    pos = []
    neg = []
    zero = 0
    for i in arr:
        if i > 0:
            pos.append(i)
        elif i < 0:
            neg.append(i)
        else:
            zero += 1

    pos.sort()
    neg.sort()
    if not pos:
        prod = 1
        if k%2 == 0:
            while neg and k > 0:
                prod *= neg.pop(0)
                k -= 1
                prod %= mod
        else:
            while neg and k > 0:
                prod *= neg.pop()
                k -= 1
                prod %= mod

        while k > 0:
            prod *= 0
            zero -= 1
            k -= 1

        print(prod)
        return 
    
    heap = []
    while pos:
        heapq.heappush(heap,(-pos.pop(),1))

    while len(neg) >= 2:
        a = neg.pop(0)
        b = neg.pop(0)
        heapq.heappush(heap,(-(a*b/2),2))
        heapq.heappush(heap,(-a,1))
        heapq.heappush(heap,(-b,1))

    while neg:
        heapq.heappush(heap,(-neg.pop(),1))

    prod = 1
    while k > 0 and heap:
        cost,count = heapq.heappop(heap)
        cost = -cost
        if count == 2:
            if k >= 2:
                cost *= 2
                cost = int(cost)
                prod *= cost
                k -= 2
        else:
            prod *= cost
            k -= 1

        prod %= mod

    if k > 0:
        prod = 0
        
    print(prod)

main()

Submission status: Wrong Answer

Solution code:
def task():
    n,k=[int(i) for i in input().split()]
    arr=[int(i) for i in input().split()]
    arr.sort()
    mini=-9999999999
    for i in range(0,n-k+1):
        temp=1
        for j in range(i,i+k):
            temp=temp*arr[j]
        mini=max(temp,mini)
    print(mini%1000000007)
def default():
    t=1
    while(t):
        t-=1
        task()
if(__name__=="__main__"):
    default()

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

mod = 10**9+7

cp = 0
cm = 0
for i in range(N):
    n = 1
    if A[i] < 0:
        n = -1
    elif A[i] == 0:
        n = 0
    A[i] = (abs(A[i]), n)
    if n > 0:
        cp += 1
    elif n < 0:
        cm += 1

f = -1
for i in range(0, K+1, 2):
    if i <= cm and K-i <= cp:
        f = 1
        break


if K > cp+cm:
    ans = 0
elif f == -1:
    A.sort()
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
    ans *= -1
    ans %= mod
else:
    A.sort(reverse=True)
    cnt = 0
    ans = 1
    for i in range(K):
        ans *= A[i][0]
        ans %= mod
        if A[i][1] < 0:
            cnt += 1

    if cnt % 2 == 1:
        a1 = 1
        if cnt < K < cm:
            for i in range(K, N):
                if A[i][1] < 0:
                    a1 *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] > 0:
                    a1 /= A[i][0]
                    break
        else:
            a1 = 0
        a2 = 1
        if 0 < cnt < cp:
            for i in range(K, N):
                if A[i][1] > 0:
                    a2 *= A[i][0]
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] < 0:
                    a2 /= A[i][0]
                    break
        else:
            a2 = 0

        if a1 > a2 > 0 or (a1 > 0 and a2 == 0):
            for i in range(K, N):
                if A[i][1] < 0:
                    ans *= A[i][0]
                    ans %= mod
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] > 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        elif a2 > a1 > 0 or (a2 > 0 and a1 == 0):
            for i in range(K, N):
                if A[i][1] > 0:
                    ans *= A[i][0]
                    ans %= mod
                    break
            for i in range(K-1, -1, -1):
                if A[i][1] < 0:
                    ans *= pow(A[i][0], mod-2, mod)
                    ans %= mod
                    break
        else:
            A.sort()
            ans = 1
            for i in range(K):
                ans *= A[i][0]
                ans %= mod
            ans *= -1
            ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
PRIME = 10 ** 9 + 7

n, k = map(int, input().split())
a = list(map(int, input().split()))

_a = sorted(a,key=abs,reverse=True)

ans = 1
if n == k:
  for i in range(k):
    ans = (ans * _a[i]) % PRIME
else:
  minus_n = 0
  minus_k = 0
  zero = 0
  min_minus = -1
  min_plus = -1
  
  for i in range(n):
    if _a[i] < 0:
      minus_n += 1
      if i < k:
        minus_k += 1
        min_minus = i
    elif _a[i] == 0:
      zero += 1
    elif i < k:
      min_plus = i
  
  if minus_n + zero == n and k % 2 == 1:
    for i in range(1, k + 1):
      ans = (ans * _a[-i]) % PRIME
  elif minus_k % 2 == 0:
    for i in range(k):
      ans = (ans * _a[i]) % PRIME
  elif minus_n == minus_k:
    for i in range(k):
      if i != min_minus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[k]) % PRIME
  else:
    for i in range(k):
      if i != min_plus:
        ans = (ans * _a[i]) % PRIME
    for i in range(k, n):
      if a[i] < 0:
        ans = (ans * _a[i]) % PRIME
        break
    
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
minus=[]
plus=[]
cnt=Counter(a)
zerocnt=cnt[0]
minuscnt=0
pluscnt=0
for i in range(n):
    if a[i]<0:
        minuscnt+=1
        minus.append(a[i])
    elif a[i]>0:
        pluscnt+=1
        plus.append(a[i])


if n==k:
    ans=1
    for i in range(n):
        ans*=a[i]
        ans%=mod
    print(ans%mod)
    quit()

if minuscnt==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=a[i]
            ans%=mod
        print(ans)
    else:
        for i in range(k):
            ans*=a[-1-i]
            ans%=mod
        print(ans)
    quit()

if minuscnt%2==1:
    minuscnt-=1

# print(minus)
plus.reverse()
# plus.append(0)
# plus.append(0)
# print(plus)

ans=1
nokori=k
m,p=0,0
# minuscnt=max(minuscnt,1)

while nokori:
    # print(pluscnt,p)
    if m==minuscnt:
        if p!=pluscnt:
            ans*=plus[p]
            p+=1
            nokori-=1
        else:
            ans=0
            nokori=0
    elif p==pluscnt:
        if nokori==1:
            ans=0
            nokori-=1
        else:
            ans*=minus[m]*minus[m+1]
            m+=2
            nokori-=2
    elif p+1==pluscnt:
        if nokori%2==0:
            ans*=minus[m]*minus[m+1]
            m+=2
            nokori-=2
        else:
            if nokori==1:
                ans*=plus[p]
                p+=1
                nokori-=1
            elif plus[p]>minus[m]*minus[m+1]:
                ans*=plus[p]
                p+=1
                nokori-=1
            else:
                ans*=minus[m]*minus[m+1]
                m+=2
                nokori-=2

    elif plus[p]*plus[p+1]>minus[m]*minus[m+1]:
        # if nokori%2==0:
        #     ans*=plus[p]*plus[p+1]
        #     p+=2
        #     nokori-=2
        # else:
        ans*=plus[p]
        p+=1
        nokori-=1
    else:
        ans*=minus[m]*minus[m+1]
        m+=2
        nokori-=2
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))

p, m = [], []
for x in a:
    if x == 0: continue
    elif x >= 0: p.append(x)
    else: m.append(x)

if len(p) == 0 and len(m) == 0:
    print(0)
    exit()

p.sort(reverse=True)
m.sort()
mr = list(reversed(m))


def mmod(x):
    if x < 0: return -(MOD - x % MOD)
    return x % MOD

def cum(s):
    n = len(s)
    cs = [1] * (n+1)
    for i in range(n):
        cs[i+1] = mmod(cs[i] * s[i])
    return cs

pc = cum(p)
mc = cum(m)
mrc = cum(mr)

ans = -float("inf")
pl, ml = len(p), len(m)

d = min(pl, k)

for pn in range(d+1)[::-1]:
    mn = k - pn
    if mn > ml: continue
    tmp = mmod(pc[pn] * mc[mn])
    tmp1 = mmod(pc[pn] * mrc[mn])
    ans = max(ans, tmp, tmp1)


print(ans % MOD)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
A = sorted(A, reverse = True, key = lambda x:abs(x))
 
ans = 1
for i in range(K):
  ans *= A[i]
  ans = ans%(10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7
A1 = []  
A2 = []
for i in range(N):
    if A[i] > 0:
        A1.append(A[i])
    if A[i] < 0:
        A2.append(-A[i])
A1.sort(reverse=True)
A2.sort(reverse=True)
ans = 1
if max(A)< 0:
    if K%2 == 0:
        for i in range(K):
            ans = (ans * A2[i])%mod
    else:
        A2.sort()
        for i in range(K):
            ans = (ans * A2[i])%mod
            ans = (mod - ans)%mod
elif max(A) == 0:
    if K%2 == 1:
        ans = 0
    else:
        if len(A2) >= K:
            for i in range(K):
                ans = (ans * A2[i])%mod
        else:
            ans = 0
else:
    A3 = []
    for i in range(len(A2)//2):
        A3.append(A2[2 * i] * A2[2 * i + 1])
    A4 = []
    A5 = []
    for i in range(len(A1)//2):
        A4.append(A1[2 * i] * A1[2 * i + 1])
    for i in range((len(A1) - 1)//2):
        A5.append(A1[2 * i + 1] * A1[2 * i + 2])
    if len(A1) + 2 * len(A3) < K:
        ans = 0
    else:
        if K%2 == 0:
            A6 = A3 + A4
            A6.sort(reverse=True)
            for i in range(K//2):
                ans = (ans * A6[i])%mod
        else:
            A6 = A3 + A5
            A6.sort(reverse=True)
            ans = A1[0]
            for i in range((K - 1)//2):
                ans = (ans * A6[i])% mod
print(ans)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
temp = IL()
IS_Z = None
A = []
for a in temp:
  if a!=0:
    A.append(a)
  if a==0:
    IS_Z = True
A = sorted(A,key= lambda x:(-abs(x),-x))
S = [a//abs(a) if abs(a)!=0 else 0 for a in A]

NA = len(A)
if NA<K:
  print(0)
  exit()
  
count_M = 0
last_M = None
last_P = None
for i in range(K):
  if S[i] == -1:
    last_M = i
    count_M += 1
  if S[i] == 1:
    last_P = i

if count_M%2 == 0:
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans %= MOD
  print(ans)
  exit()

else:
  ANS1 = -INF
  ANS2 = -INF
  if last_M!=None:
    for i in range(K,NA):
      if S[i] == 1:
        ans = 1
        for ii in range(K):
          if ii != last_M:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        ANS1 = ans
        break
  if last_P!=None:
    for i in range(K,NA):
      if S[i] == -1:
        ans = 1
        for ii in range(K):
          if ii != last_P:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        ANS2 = ans
        break
  if max(ANS1,ANS2)!=-INF:
    print(max(ANS1,ANS2))
    exit()
  if IS_Z:
    print(0)
    exit()
  else:
    ans = 1
    for i in range(K):
      ans *= A[NA-1-i]
      ans %= MOD
    print(ans)