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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, k = LI()
A = LI()
flg = 1 if max(A) < 0 and k % 2 else 0
X = sorted(A, key=lambda x:abs(x), reverse=False if flg else True)
ans = 1
L = []
fflg = 0
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
    L += [X[i]]

rem = []
r1 = 0
r2 = 0
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    rem += [A[ii]]
    if A[ii] > 0:
        rem_plus = 1
        r1 = max(A[ii], 0)
    elif A[ii] < 0:
        rem_minus = 1
        r2 = max(abs(A[ii]), 0)

if fflg:
    for jj in range(len(L)-1, -1, -1):
        if L[jj] < 0 and rem_plus:
            ans = -ans * pow(L[jj], mod - 2, mod) % mod
            ans *= r1
            fflg ^= 1
            break
        elif L[jj] > 0 and rem_minus:
            -ans * pow(L[jj], mod - 2, mod) % mod
            ans *= r2
            fflg ^= 1
            break

print(ans % mod)

Submission status: Wrong Answer

Solution code:

def main():
  n, k = map(int, input().split())

  plus = [0] * n
  minus = [0] * n
  pn = mn = 0

  for num in input().split():
    num = int(num)
    if num >= 0:
      plus[pn] = num
      pn += 1
    else:
      minus[mn] = num
      mn += 1

  mod = 10 ** 9 + 7

  if pn == 0 and k % 2 == 1:
    minus.sort(reverse = True)
    ans = 1
    for i in range(k):
      ans = ans * minus[i]

    print(ans % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pi = 0
  mi = 0

  while k > 0:
    if pi + 1 == pn:
      if k % 2 == 0:
        mi += k
      else:
        pi += 1
        mi += k - 1
      break

    if pi == pn:
      mi += k
      break

    if mi + 1 >= mn:
      pi += k
      break

    if plus[pi] * plus[pi + 1] >= minus[mi] * minus[mi + 1]:
      pi += 1
      k -= 1
    else:
      mi += 2
      k -= 2

  ans = 1
  for i in range(pi):
    ans = (ans * plus[i]) % mod

  for i in range(mi):
    ans = (-ans * minus[i]) % mod

  print(ans % mod)


main()

Submission status: Wrong Answer

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


    B = []
    flg_m = 0
    flg_p = 0

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

        b = 0
        ans = -10**9

    if k == 1:
        for b in B:
            ans = max(ans,b[0])
    print(ans)
    exit()

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

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

    L = B[:k]
    ans = cal_ans(L)
    c = 0
    for n,sign in L:
        if sign == -1:
            c += 1
    if c % 2 == 0:
        print(ans)
        exit()
    if flg_p == 1 and flg_m == 1:
        if first_p * last_p >= first_m*last_m:
            a = first_p
            b = last_m
        else:
            a = first_m
            b = last_p
    elif flg_p == 1:
            a = first_p
            b = last_m
    elif flg_m == 1:
            a = first_m
            b = last_p
    else:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        exit()


    ans *= a
    ans %= MOD
    ans *= pow(b,MOD-2,MOD)
    ans %= MOD
    print(ans)

def cal_ans(L):
    MOD = 10**9+7
    ans = 1
    for i,j in L:
        ans *= i
        ans %= MOD
    return ans



main()

Submission status: Wrong Answer

Solution code:

def main():
  n, k = map(int, input().split())

  plus = [0] * n
  minus = [0] * n
  pn = mn = 0

  for num in input().split():
    num = int(num)
    if num >= 0:
      plus[pn] = num
      pn += 1
    else:
      minus[mn] = num
      mn += 1

  mod = 10 ** 9 + 7

  if pn == 0 and k % 2 == 1:
    minus.sort(reverse = True)
    ans = 1
    for i in range(k):
      ans = (ans * (-minus[i])) % mod

    print((-ans) % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pi = 0
  mi = 0

  while k > 0:
    if pi + 1 == pn:
      if k % 2 == 0:
        mi += k
      else:
        pi += 1
        mi += k - 1
      break

    if pi == pn:
      mi += k
      break

    if mi + 1 >= mn:
      pi += k
      break

    if plus[pi] * plus[pi + 1] >= minus[mi] * minus[mi + 1]:
      pi += 1
      k -= 1
    else:
      mi += 2
      k -= 2

  ans = 1
  for i in range(pi):
    ans = (ans * plus[i]) % mod

  for i in range(mi):
    ans = (ans * (-minus[i])) % mod

  print(ans % mod)


main()

Submission status: Wrong Answer

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

B=[]
for i in range(n):
    num=A[i]
    B.append([abs(num),num])
B.sort(reverse=True)

C=[]
ans,flag=1,1
for i in range(k):
    num=B[i][1]
    if num<0:flag *=-1
    ans *=num
    ans %=mod
    C.append(num)

if flag==1:print(ans);exit()

plus,negative=0,0
for i in range(k,n):
    if plus!=0 and negative!=0:break
    num=B[i][1]
    if num>0 and plus==0:plus=num
    elif num<0 and negative==0:negative=num

if plus==0 and negative!=0:
    ans=1
    for i in range(k):
        ans *=B[-(i+1)][1]
        ans %=mod
    print(ans)
elif plus!=0 and negative==0:
    ans=1
    C.pop()
    C.append(plus)
    for i in range(k):
        ans *=C[i]
        ans %=mod
    print(ans)
elif plus!=0 and negative!=0:
    x,y=0,0
    for i in range(k):
        num=C[i]
        if num>0:x=i
        else:y=i
    test1,test2=1,1
    for i in range(k):
        if i==x:
            test1 *=negative
            test2 *=C[i]
        elif i==y:
            test1 *=C[i]
            test2 *=plus
        else:
            test1 *=C[i]
            test2 *=C[i]
        test1 %=mod
        test2 %=mod
    print(max(test1,test2))
else:print(ans)

Submission status: Wrong Answer

Solution code:
#import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


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

    def prod(iter):
        ret = 1
        for i in range(len(iter)):
            ret *= iter[i]
            ret %= MOD
        return ret % MOD

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

    if k == n:
        print(prod(A))
    else:
        minus = 0
        plus = 0
        for i in A:
            if i < 0:
                minus += 1
            elif i > 0:
                plus += 1
        if minus == n and k % 2 == 1:
            A.sort(reverse=True)
            print(prod(A[:k]))
        else:
            A.sort(key=abs, reverse=True)
            p = prod(A[:k])
            if p >= 0:
                print(p)
            else:
                ans=p
                Mplus = 0
                mminus = 0
                for i in range(k):
                    mminus = min(mminus, A[i])
                for i in range(k, n):
                    Mplus = max(Mplus, A[i])
                if mminus<0 and Mplus>0:
                    ans = p//mminus*Mplus

                INF = 10**10

                mplus = INF
                Mminus = -INF
                for i in range(k):
                    if A[i]>0:
                        mplus = min(mplus, A[i])
                for i in range(k, n):
                    if A[i]<0:
                        Mminus = max(Mminus, A[i])
                
                ans = max(ans, p//mplus*Mminus)

                print(ans%MOD)


resolve()

Submission status: Wrong Answer

Solution code:

def main():
  n, k = map(int, input().split())

  plus = [0] * n
  minus = [0] * n
  pn = mn = 0

  for num in input().split():
    num = int(num)
    if num >= 0:
      plus[pn] = num
      pn += 1
    else:
      minus[mn] = num
      mn += 1

  mod = 10 ** 9 + 7

  if pn == 0 and k % 2 == 1:
    minus.sort(reverse=True)
    ans = 1
    for i in range(k):
      ans = (ans * (-minus[i])) % mod

    print((-ans) % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pi = 0
  mi = 0

  while k > 0:
    if pi + 1 == pn:
      pi += 1
      mi += k - 1
      break

    if pi == pn:
      mi += k
      break

    if mi + 1 >= mn:
      pi += k
      break

    if plus[pi] * plus[pi + 1] >= minus[mi] * minus[mi + 1]:
      pi += 1
      k -= 1
    else:
      mi += 2
      k -= 2

  ans = 1
  for i in range(pi):
    ans = (ans * plus[i]) % mod

  for i in range(mi):
    ans = (ans * (-minus[i])) % mod

  print(ans % mod)


main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


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

    def prod(iter):
        ret = 1
        for i in range(len(iter)):
            ret *= iter[i]
            ret %= MOD
        return ret % MOD

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

    if k == n:
        print(prod(A))
    else:
        minus = 0
        plus = 0
        for i in A:
            if i < 0:
                minus += 1
            elif i > 0:
                plus += 1
        if minus == n and k % 2 == 1:
            A.sort(reverse=True)
            print(prod(A[:k]))
        else:
            A.sort(key=abs, reverse=True)
            p = prod(A[:k])
            if p >= 0:
                print(p)
            else:
                Mplus = 0
                mminus = 0
                for i in range(k):
                    mminus = min(mminus, A[i])
                for i in range(k, n):
                    Mplus = max(Mplus, A[i])
                if mminus<0 and Mplus>0:
                    ans = p//mminus*Mplus

                INF = 10**10

                mplus = INF
                Mminus = -INF
                for i in range(k):
                    if A[i]>0:
                        mplus = min(mplus, A[i])
                for i in range(k, n):
                    if A[i]<0:
                        Mminus = max(Mminus, A[i])
                ans = max(ans, p//mplus*Mminus)

                print(ans)


resolve()

Submission status: Wrong Answer

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

B=[]
for i in range(n):
    num=A[i]
    B.append([abs(num),num])
B.sort(reverse=True)

C=[]
ans,flag=1,1
for i in range(k):
    num=B[i][1]
    if num<0:flag *=-1
    ans *=num
    ans %=mod
    C.append(num)

if flag==1:print(ans);exit()

plus,negative=0,0
for i in range(k,n):
    if plus!=0 and negative!=0:break
    num=B[i][1]
    if num>0:plus=num
    elif num<0:negative=num

if plus==0 and negative!=0:
    ans=1
    for i in range(k):
        ans *=B[-(i+1)][1]
        ans %=mod
    print(ans)
elif plus!=0 and negative==0:
    ans=1
    C.pop()
    C.append(plus)
    for i in range(k):
        ans *=C[i]
        ans %=mod
    print(ans)
elif plus!=0 and negative!=0:
    x,y=0,0
    for i in range(k):
        num=C[i]
        if num>0:x=i
        else:y=i
    test1,test2=1,1
    for i in range(k):
        if i==x:
            test1 *=negative
            test2 *=C[i]
        elif i==y:
            test1 *=C[i]
            test2 *=plus
        else:
            test1 *=C[i]
            test2 *=C[i]
        test1 %=mod
        test2 %=mod
    print(max(test1,test2))
else:print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
D=[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append((i,0))
  elif i>0:
    D.append((i,0))
    scnt+=1
  else:
    D.append((-i,1))
    fcnt+=1
D=D[::-1]
mod=10**9+7
ans=1
seihu=0
f,s,z=fcnt,scnt,zcnt
X,Y,Z=[],[],[]
for i in range(K):
  ans*=D[i][0]
  ans%=mod
  seihu+=D[i][1]
  if D[i][0]!=0 and D[i][1]==1:
    fcnt-=1
    Y.append(-D[i][0])
  elif D[i][0]!=0 and D[i][1]==0:
    scnt-=1
    X.append(D[i][0])
  else:
    zcnt-=1
F=D[K:]
if seihu%2==0:
  print(ans)
else:
  C=[]
  if len(X)>0 and fcnt>0:
    #正の数を取り除き、負の一番大きいのを加える
    for a,b in F:
      if b==1:
        g=-a
        break
    h=(ans*(pow(X[-1],mod-2,mod))*g)%mod
    C.append(h)
  if len(Y)>0 and scnt>0:
    #負の数を取り除き、正の一番大きいのを
    for a,b in F:
      if b==0:
        g=a
        break
    h=(ans*(pow(Y[-1],mod-2,mod))*g)%mod
    C.append(h)
  if zcnt>0:
    C.append(0)
  if len(C)==0:
    ans=1
    D=D[::-1]
    for i in range(K):
      ans*=(-D[i][0])
      ans%=mod
    print(ans)
  else:
    print(max(C))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, k = LI()
A = LI()
flg = 0
X = sorted(A, key=lambda x:abs(x), reverse=True)
for i in range(n):
    if X[i] > 0:
        flg = 1

if k % 2 and flg == 0:
    X.reverse()


ans = 1
L = []
fflg = 0
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
    L += [X[i]]

rem = []
r1 = 0
r2 = 0
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    rem += [A[ii]]
    if A[ii] > 0:
        rem_plus = 1
        r1 = max(abs(A[ii]), 0)
    elif A[ii] < 0:
        rem_minus = 1
        r2 = max(abs(A[ii]), 0)

if fflg:
    for jj in range(len(L)-1, -1, -1):
        if L[jj] < 0 and rem_plus:
            ans //= -L[jj]
            ans *= r1
            fflg ^= 1
            break
        elif L[jj] > 0 and rem_minus:
            ans //= L[jj]
            ans *= r1
            fflg ^= 1
            break

if fflg:
    ans = -ans
print(ans % mod)

Submission status: Wrong Answer

Solution code:
from copy import copy, deepcopy  # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
import unittest
from io import StringIO
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


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

    def prod(iter):
        B = copy(iter)
        ret = 1
        for i in range(len(B)):
            ret *= B[i]
            ret %= MOD
        return ret % MOD

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

    if k == n:
        print(prod(A))
    else:
        minus = 0
        plus = 0
        for i in A:
            if i < 0:
                minus += 1
            elif i > 0:
                plus += 1
        if minus == n and k % 2 == 1:
            A.sort(reverse=True)
            B = copy(A[:k])
            print(prod(B))
        else:
            A.sort(key=abs, reverse=True)
            B = copy(A[:k])

            p = prod(B)
            if p >= 0:
                print(p)
            else:
                Mplus = 0
                mminus = 0
                for i in range(k):
                    mminus = min(mminus, A[i])
                for i in range(k, n):
                    Mplus = max(Mplus, A[i])
                ans = p//mminus*Mplus

                INF = 10**10

                mplus = INF
                Mminus = -INF
                for i in range(k):
                    mplus = min(mplus, A[i])
                for i in range(k, n):
                    Mminus = max(Mminus, A[i])
                ans = max(ans, p//mplus*Mminus)

                print(ans)


resolve()

Submission status: Wrong Answer

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

B=[]
for i in range(n):
    num=A[i]
    B.append([abs(num),num])
B.sort(reverse=True)

C=[]
ans,flag=1,1
for i in range(k):
    num=B[i][1]
    if num<0:flag *=-1
    ans *=num
    ans %=mod
    C.append(num)

if flag==1:print(ans);exit()

plus,negative=0,0
for i in range(k,n):
    if plus!=0 and negative!=0:break
    num=B[i][1]
    if num>0:plus=num
    elif num<0:negative=num

if plus==0 and negative!=0:
    ans=1
    for i in range(k):
        ans *=B[-(i+1)][1]
        ans %=mod
    print(ans)
elif plus!=0 and negative==0:
    ans=1
    C.pop()
    C.append(plus)
    for i in range(k):
        ans *=C[i]
        ans %=mod
    print(ans)
else:print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, k = LI()
A = LI()
flg = 0
X = sorted(A, key=lambda x:abs(x), reverse=True)
for i in range(n):
    if X[i] > 0:
        flg = 1

if k % 2 and flg == 0:
    X.reverse()


ans = 1
L = []
for i in range(k):
    ans = ans * X[i] % mod
    L += [X[i]]

rem = []
r1 = 0
r2 = 0
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    rem += [A[ii]]
    if A[ii] > 0:
        rem_plus = 1
        r1 = max(abs(A[ii]), 0)
    elif A[ii] < 0:
        rem_minus = 1
        r2 = max(abs(A[ii]), 0)

if ans < 0:
    for jj in range(len(L), -1, -1):
        if L[jj] < 0 and rem_plus:
            ans //= L[jj]
            ans *= r1
            break
        elif L[jj] > 0 and rem_minus:
            ans //= L[jj]
            ans *= r1
            break

print(ans % mod)

Submission status: Wrong Answer

Solution code:
n, k = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
MOD = 10**9 + 7
A.sort()

l = 0
r = n - 1
flag = False  # マイナスになってしまうかフラグ
ans = 1
if k % 2 == 1:
    ans = A[r]
    r -= 1
    k -= 1
    if ans < 0:
        sign = True


if flag:  # どうしてもマイナスになってしまう場合(kが奇数で要素すべてがマイナスの場合)
    while k:
        ans *= A[r] * A[r - 1] % MOD
        ans %= MOD
        r -= 2
        k -= 2
else:  # 必ず0以上にできる場合
    while k:
        x = A[l] * A[l + 1]
        y = A[r] * A[r - 1]
        if x > y:
            ans *= x % MOD
            ans %= MOD
            l += 2
        else:
            ans *= y % MOD
            ans %= MOD
            r -= 2
        k -= 2

print(ans)

Submission status: Wrong Answer

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(k==n):
    for el in a:
        ans = (ans%mod*el%mod)%mod
else:

    if(len(pos)==0):
        if(k%2==0):
            temp = 0
            for i in range(len(neg)-1, -1, -1):
                if(temp==k):
                    break
                ans = (ans%mod*neg[i]%mod)%mod
                temp+=1
            if(temp<k):
                ans = 0
        else:
            temp = 0
            for i in range(len(neg) - 1):
                if (temp == k):
                    break
                ans = (ans%mod * neg[i]%mod) % mod
                temp += 1
            if (temp < k):
                ans = 0
    else:

        if(k%2==0):

            left = k

            i,j = 0, len(neg)-1

            while(left>0):
                temp, temp1 = 0, 0
                if(i<len(pos)-1):
                    temp = pos[i]*pos[i+1]
                    # i+=2
                if(j>=1):
                    temp1 = neg[j]*neg[j-1]
                    # j-=2
                if(temp==0 and temp1==0):
                    break
                if(temp1>temp):
                    ans = (ans*(temp1%mod))%mod
                    j-=2
                else:
                    ans = (ans*(temp%mod))%mod
                    i+=2
                left -= 2
            if(left>0):
                ans = 0

        else:
            if(len(pos) + len(neg)>=k):
                prefPos = [pos[0]]

                for i in range(1, len(pos)):
                    prefPos.append((pos[i]*prefPos[i-1])%mod)

                neg = neg[::-1]

                if(len(neg)>0):
                    prefNeg = [neg[0]]
                else:
                    prefNeg = []
                for i in range(1, len(neg)):
                    prefNeg.append((neg[i]*prefNeg[i-1])%mod)


                ans = prefPos[0]

                flag = 0

                for i in range(0, len(prefPos), 2):
                    used = i+1
                    if(k-i-2>=0 and k-i-2<len(neg)):
                        ans = max(ans, prefPos[i]*prefNeg[k-i-2])%mod

                    else:
                        if(k-i-2==-1):
                            ans = max(ans, prefPos[i]%mod)
                        else:
                            ans = max(ans, 0)
                    # print(ans, i)

            # print(prefPos, prefNeg)
            else:
                ans = 0
print(ans)

Submission status: Wrong Answer

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

MOD = 10**9+7


def main(input, print):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    plus = []
    neg = []
    for i in range(n):
        if a[i] < 0:
            neg.append(a[i])
        else:
            plus.append(a[i])
    is_ans_plus = False
    if len(plus) > 0:
        if n == k:
            is_ans_plus = len(neg) % 2 == 0
        else:
            is_ans_plus = True
    else:
        is_ans_plus = k % 2 == 0
    ans = 1
    if is_ans_plus:
        neg = sorted(neg, key=abs, reverse=True)
        plus = sorted(plus, key=abs, reverse=True)
        pair = []
        for i in range(1, len(neg), 2):
            pair.append(neg[i-1]*neg[i] % MOD)
        s = 1
        if k % 2 == 1:
            ans = plus[0]
            s = 2
        for i in range(s, len(plus), 2):
            pair.append(plus[i-1]*plus[i] % MOD)
        for i in range(k//2):
            ans = ans * pair[i] % MOD
    else:
        a = sorted(a, key=abs)
        for i in range(k):
            ans = ans * a[i] % MOD

    print(ans)


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

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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