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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

A = LIST()
if N == 1:
    print(A[0])
    exit()

plus0 = []
minus = []
zero = []

for a in A:
    if a >= 0:
        plus0.append(a)
    if a == 0:
        zero.append(a)
    if a < 0:
        minus.append(a)

# print(plus0)
# print(minus)
# print(zero)

if (len(minus) == N and K%2 == 1) or (plus0 and minus and N == K and (N-len(plus0))%2 == 1):
    # 答えはマイナスなので最小化を目指す
    ans = 1
    cnt = 0
    plus0.sort(reverse=True)
    minus.sort()
    while cnt != K:
        if not plus0:
            ans *= minus.pop()
        elif not minus:
            ans *= plus0.pop()
        else:
            if plus0[-1] < -minus[-1]:
                ans *= plus0.pop()
            else:
                ans *= minus.pop()
        cnt += 1
        ans %= mod
    print(ans)
else:
    # 答えは0以上なので最大化を目指す
    ans = 1
    cnt = 0
    plus0.sort()
    minus.sort(reverse=True)
    # print(plus0)
    # print(minus)
    while cnt != K:
        if cnt == K-1 or len(minus) <= 1:
            ans *= plus0.pop()
            cnt += 1
        else:
            if not plus0:
                ans *= minus.pop()
                ans *= minus.pop()
                cnt += 2
            else:
                if plus0[-1] > minus[-1]*minus[-2]:
                    ans *= plus0.pop()
                    cnt += 1
                else:
                    ans *= minus.pop()
                    ans *= minus.pop()
                    cnt += 2
        ans %= mod
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, -ai)
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    if len(mi) >= k:
        ans = 1
        A = []
        if k & 1:
            k -= 1
            ans *= -heappop(ma)
        for _ in range(k):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        tmp = ans
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            tmp *= pow(h1 * h2, mod - 2, mod)
            tmp %= mod
            tmp *= g1 * g2
            tmp %= mod
            ans = max(ans, tmp)
        print(ans)
    else:
        ans = 1
        L = len(mi)
        A = []
        X = k - L
        if len(mi) & 1:
            L -= 1
            X += 1
        for i in range(L):
            x = heappop(mi)
            ans *= x
            ans %= mod
            heappush(A, -x)
        for i in range(X):
            x = -heappop(ma)
            ans *= x
            ans %= mod
        tmp = ans
        while len(ma) >= 2 and len(A) >= 2:
            g1 = -heappop(ma)
            g2 = -heappop(ma)
            h1 = -heappop(A)
            h2 = -heappop(A)
            tmp *= pow(h1 * h2, mod - 2, mod)
            tmp %= mod
            tmp *= g1 * g2
            tmp %= mod
            ans = max(ans, tmp)
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    cand=[]
    poss=[]
    negs=[]
    replace=[]
    if K%2==1:#奇数個
        K-=1
        cand.append(L[-1])
        for l in L[:-1]:
            if l>0:
                heapq.heappush(poss,l)
                if len(poss)>K:
                    heapq.heappop(poss)#正の数でK番目より小さいやつは捨てる
            else:
                heapq.heappush(negs,l)
        #N-1こ(偶数を選んでから)追加で、正の(一番大きいやつを取っておく?)怪しい
    else:
        for l in L:
            if l>0:
                heapq.heappush(poss,l)
                if len(poss)>K:
                    heapq.heappop(poss)#正の数でK番目より小さいやつは捨てる
            else:
                heapq.heappush(negs,l)
    while len(negs)>=2:
        a = heapq.heappop(negs)
        b = heapq.heappop(negs)
        heapq.heappush(replace,-a*b)

    #print("poss=>",poss)
    #print("negs=>",negs)
    #print("rep=>",replace)
    #print("cand=>",cand)
    added=0

    while len(replace)>0:
        if len(poss)>=2:
            a = heapq.heappop(poss)
            b = heapq.heappop(poss)
            rep= - heapq.heappop(replace)
            if a*b<rep:#possのした二つを置き換える
                added+=2
                cand.append(rep)
        elif len(poss)+added<K:#possの長さが足りないから無条件で負の方から追加する
            rep= - heapq.heappop(replace)
            added+=2
            cand.append(rep)
    
    #print("last.poss=>",poss)
    #print("last can=>",cand)
    for p in poss:
        ans*=p
        ans%=MOD
    for r in cand:
        ans*=r
        ans%=MOD
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
#import numpy as np
Q = int(1e9 + 7)

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

A = sorted(A)

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= Q
    print(ans)
    exit()
elif K == 1:
    ans = A[-1] % Q
    print(ans)
    exit()

A_mi, A_0, A_pl = [], [], []
for a in A:
    if a > 0:
        A_pl.append(a)
    elif a < 0:
        A_mi.append(a)
    else:
        A_0.append(a)

#答えが必ず0
if len(A_mi) + len(A_pl) < K:
    print(0)
    exit()

#全て正
if N == len(A_pl):
    ans, c = 1, 0
    for a in reversed(A_pl):
        ans *= a
        ans %= Q
        c += 1
        if c == K:
            break
    print(ans)
    exit()

#全て負or0
if N == len(A_mi) + len(A_0):
    if K % 2 == 0:
        ans, c = 1, 0
        for a in A_mi:
            ans *= a
            ans %= Q
            c += 1
            if c == K:
                break
        print(ans)
        exit()
    else:
        if len(A_0) > 0:
            print(0)
            exit()
        else:
            ans, c = 1, 0
            for a in reversed(A_mi):
                ans *= a
                ans %= Q
                c += 1
                if c == K:
                    break
            print(ans)
            exit()


cost_2 = []
if len(A_mi) > 1:
    for i in range(0, len(A_mi)-1, 2):
        cost_2.append(A_mi[i] * A_mi[i + 1])

c = 0
ans = 1

while True:
    if K - c > 1:
        if len(cost_2) > 0:
            c2 = cost_2[0]
        else:
            c2 = 0
        if len(A_pl) > 2:
            pl2 = A_pl[-1] * A_pl[-2]
        else:
            pl2 = 0
        if c2 >= pl2:
            ans *= c2
            cost_2.pop(0)
        else:
            ans *= pl2
            A_pl.pop(-1)
            A_pl.pop(-1)
        ans %= Q
        c += 2
    else:
        ans *= A_pl[-1]
        ans %= Q
        c += 1
        A_pl.pop(-1)
    if K == c:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input().strip()
    return(list(s[:len(s)]))
def invr():
    return(map(int,input().split()))

n, k = invr()
a = inlt()
p1 = 1
p2 = 1
for i in range(0, k):
     p1 = (p1 * a[i])

a.reverse()

for i in range(0, k):
     p2 = (p2 * a[i])

print(max(p1, p2) % 1000000007)

Submission status: Wrong Answer

Solution code:
def resolve():
    def addans(i, ans):
        return ans * i % mod
    import sys
    import bisect
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    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)
    if n - k < r - l:
        print(0)
        return
    if r == n:
        ans = 1
        for i in range(k):
            ans = addans(a[-i - 1], ans)
        print(ans)
        return
    ans = 1
    minus = [0] * 3 + a[::-1]
    plus = [0] * 3 + a
    if k % 2 == 1:
        ans = plus.pop()
        k -= 1
    m = minus.pop() * minus.pop()
    p = plus.pop() * plus.pop()
    for _ in range(k // 2):
        if p >= m:
            ans = addans(p, ans)
            p = plus.pop() * plus.pop()
        else:
            ans = addans(m, ans)
            m = minus.pop() * minus.pop()
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
mod=10**9+7
A.sort(reverse=True,key=lambda x:abs(x))

if min(A)>0:
  ans=1
  for i in range(k):
    ans=(ans*A[i])%mod
  print(ans)
elif max(A)<0:
  ans=1
  if k%2==0:
    for i in range(k):
      ans=(ans*A[i])%mod
    print(ans)
  else:
    for i in range(k):
      ans=(ans*A[n-1-i])%mod
    print(ans)
elif n==k:
  ans=1
  for i in range(k):
    ans=(ans*A[i])%mod
  print(ans)
elif k==1:
  print(max(A)%mod)

else:
  L1,L2,R1,R2=[],[],[],[]
  ct=0
  for a in A:
    if a==0:
      continue
    if ct<k:
      if a>0:
        L1.append(a)
      elif a<0:
        L2.append(a)
      ct+=1
    else:
      if a>0:
        R1.append(a)
      elif a<0:
        R2.append(a)
  if ct<k:
    print(0)
  else:
    if not L1:
      if k%2==1:
        if not R1:
          print(0)

        else:
          c=R1[0]
          ans=1
          for i in range(len(L2)-1):
            ans=(ans*L2[i])%mod
          ans=(ans*c)%mod
          print(ans)
      else:
        ans=1
        for i in range(len(L2)):
          ans=(ans*L2[i])%mod
        print(ans)
    elif not L2:
      ans=1
      for i in range(len(L1)):
        ans=(ans*L1[i])%mod
      print(ans)
    else:
      if len(L2)%2==0:
        ans=1
        for a in L1:
          ans=(ans*a)%mod
        for a in L2:
          ans=(ans*a)%mod
        print(ans)
      else:
        if not R1:
          if not R2:
            if 0 in A:
              print(0)
            else:
              ans=1
              ans=1
              for a in L1:
                ans=(ans*a)%mod
              for a in L2:
                ans=(ans*a)%mod
              print(ans)
          else:
            d=-R2[0]
            ans=d
            for i in range(len(L1)-1):
              ans=(ans*L1[i])%mod
            for i in range(len(L2)):
              ans=(ans*L2[i])%mod
            print(ans)
        else:
          c=R1[0]
          a=L1[-1]
          b=L2[-1]
          if R2 and R2[0]*b>a*c:
            ans=R2[0]
            for i in range(len(L1)-1):
              ans=(ans*L1[i])%mod
            for i in range(len(L2)):
              ans=(ans*L2[i])%mod
            print(ans)
          else:
            ans=c
            for i in range(len(L1)):
              ans=(ans*L1[i])%mod
            for i in range(len(L2)-1):
              ans=(ans*L2[i])%mod
            print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, K = input().split()
N, K = int(N), int(K)
li = input().split()
li = list(map(int,li))
n_li = []
for l in li:
    n_li.append(l % (10**9+7))
s_li = sorted(n_li,reverse=True)
num = 1
if K == 1:
    print(max(li))
else:
    for i in range(K):
        num *= s_li[i]
    print(num %  (10**9+7))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)

    def check_positive(k, pos, neg):
        if k % 2 == 0:
            return (len(neg) // 2) * 2 + len(pos) >= k
        else:
            if pos:
                k -= len(pos) if len(pos) % 2 == 1 else len(pos) - 1
                return (len(neg) // 2) * 2 >= k
            return False

    def solve(n, k, L):
        pos = []
        zero_cnt = 0
        neg = []
        for elm in L:
            if elm < 0:
                neg.append(elm)
            elif elm > 0:
                pos.append(elm)
            else:
                zero_cnt += 1
        
        if check_positive(k, pos, neg):
            # 答えは正にできる。できるだけ大きい正の値を作ろう
            abs_neg = []
            tmp = sorted([abs(elm) for elm in neg], reverse=True)
            i = 0
            while i + 1 < len(tmp):
                abs_neg.append(tmp[i] * tmp[i+1])
                i += 2
            abs_neg.reverse()
            neg = abs_neg
            pos.sort()
            mul = 1
            cnt = 0
            # print(pos)
            # print(neg)
            while cnt < k:
                if pos and neg:
                    if cnt == k - 1:
                        mul = (mul * pos.pop()) % mod
                        cnt += 1
                    elif len(pos) == 1:
                        if pos[-1] < neg[-1]:
                            mul = (mul * neg.pop()) % mod
                            cnt += 2
                        else:
                            mul = (mul * pos.pop()) % mod
                            cnt += 1
                    else:
                        if pos[-1] * pos[-2] < neg[-1]:
                            mul = (mul * neg.pop()) % mod
                            cnt += 2
                        else:
                            mul = (mul * pos.pop() * pos.pop()) % mod
                            cnt += 2
                elif pos:
                    mul = (mul * pos.pop()) % mod
                    cnt += 1
                elif neg:
                    mul = (mul * neg.pop()) % mod
                    cnt += 2
                else:
                    raise RuntimeError
            return mul

        elif zero_cnt != 0:
            # 答えは 0 にできる。0 が最善や
            return 0

        else:
            # 答えは負にしかならぬ。できるだけ 0 に近い負の値を作ろう
            tmp = [abs(elm) for elm in L]
            tmp.sort()
            mul = 1
            # print(tmp)
            for i in range(k):
                mul = (mul * tmp[i]) % mod
            return mod - mul
    
    
    n, k = mi()
    L = lmi()

    print(solve(n, k, L))




if __name__ == "__main__":
    main()

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
        f11 = False
        f12 = False
        for i in range(K, N):
            if A[i][1] < 0:
                a1 *= A[i][0]
                f11 = True
                break
        for i in range(K-1, -1, -1):
            if A[i][1] > 0:
                a1 /= A[i][0]
                f12 = True
                break
        a2 = 1
        f21 = False
        f22 = False
        for i in range(K, N):
            if A[i][1] > 0:
                a2 *= A[i][0]
                f21 = True
                break
        for i in range(K-1, -1, -1):
            if A[i][1] < 0:
                a2 /= A[i][0]
                f22 = True
                break

        if a1 > a2 and f11 and f12 and f21 and f22:
            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 f11 and f12 and f21 and f22:
            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 f11 and f12:
            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 f21 and f22:
            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:
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==[]:
    ANS=1
    for i in range(K):
        ANS=ANS*(C[i])%mod

    if Z==[] and K%2==0:
        print(ANS)
    elif Z==[] and K%2==1:
        print(-ANS%mod)
    elif K%2==1:
        print(0)
    else:
        print(ANS)

    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=K-len(B)

    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=K-len(B)+1
        

    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)

Submission status: Wrong Answer

Solution code:
import bisect

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

arr.sort()
o_ind = bisect.bisect_left(arr,0)
# print()

minus = arr[:o_ind]
plus = arr[o_ind:]
plus.reverse()

buf = [-1 for i in range(3)]
pm = [0 for i in range(3)] # 0 plus , 1 minus

mod = 10**9+7

canplus = True
types = -1

if (k == n and len(minus)%2==1):
    canplus = False
    types = 0
elif (k%2 ==1 and len(plus)==0):
    canplus = False

if canplus:
    if k % 2 == 0:
        ans = 1
        phead = 0
        mhead = 0

        for i in range(k // 2):
            tp1 = 1e-20
            tp2 = 1e-20
            if phead + 1 < len(plus):
                tp1 = plus[phead] * plus[phead + 1]

            if mhead + 1 < len(minus):
                tp2 = minus[mhead] * minus[mhead + 1]

            if tp1 < tp2:
                ans *= tp2
                ans %= mod
                mhead += 2
            else:
                ans *= tp1
                ans %= mod
                phead += 2
    else:
        if len(plus) > 0:
            ans = plus[0]
            phead = 1
            mhead = 0

            for i in range(k // 2):
                tp1 = 1e-20
                tp2 = 1e-20

                flag = False
                if phead + 1 < len(plus):
                    tp1 = plus[phead] * plus[phead + 1]

                if mhead + 1 < len(minus):
                    tp2 = minus[mhead] * minus[mhead + 1]


                if tp1 < tp2:
                    ans *= tp2
                    ans %= mod
                    mhead += 2
                else:
                    ans *= tp1
                    ans %= mod
                    phead += 2

    print(ans)
else:
    ans = 1
    if types == 0:
        for i in range(k):
            ans *= arr[i]
            ans %= mod

        print(ans)
    else:
        minus.reverse()
        for i in range(k):
            ans *= minus[i]
            ans %= mod
        print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

n, k = [int(_) for _ in input().split()]

a = [int(_) for _ in input().split()]

m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))

m.sort()
p.sort(reverse=True)


if len(p)+len(m) < k:
    print(0)
    exit()

if len(p) == 0:
    ans = 1
    for i in range(k):
        ans = (ans*m[-i-1]) % MOD
    if 0 in a:
        ans *= 0
    print(ans)
    exit()


i, j = 0, 0

m.append(0)
m.append(0)
p.append(0)
p.append(0)
ans = 1
for c in range(k//2):
    # print(i, j)
    if m[i]*m[i+1] >= p[j]*p[j+1]:
        ans = (ans*m[i]*m[i+1]) % MOD
        i += 2
    else:
        ans = (ans*p[j]*p[j+1]) % MOD
        j += 2
if k % 2 == 1:
    ans = (ans*p[j]) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,k=map(int,input().split())
a=list(map(int,input().split()))
MOD=10**9+7
ans=-10**9
for i in itertools.combinations(a,k):
    b=1
    #print(*i)
    for l in range(k):
        b*=i[l]
    ans=max(ans,b)
    #print(ans)
ans=ans%MOD
print(ans)

Submission status: Wrong Answer

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

n,k = map(int,input().split())
A = list(map(int,input().split()))
B = [0,0,0]
C = [[],[]]
D = [[abs(A[i]), A[i]] for i in range(n)]
D.sort(reverse=True)
ans = 1
mod = 10**9+7
for i in range(n):
    if A[i] > 0:
        B[0] += 1
        C[0].append(A[i])
    elif A[i] < 0:
        B[1] += 1
        C[1].append(-A[i])
    else:
        B[2] += 1
C[0].sort()
C[1].sort()

if k == 1:
    print(max(A))
elif k == 2:
    ans = 1
    if B[0] >= 2:
        ans = max(ans, C[0][0]*C[0][1])
    if B[1] >= 2:
        ans = max(ans, C[1][0]*C[1][1])
    if B[2] > 0:
        ans = max(ans, 0)
    print(ans%mod)

else:

    if (k%2==1 and B[0]==0) or (k%2==0 and k==n and B[1]%2==0):
        if B[2] > 0:
            print(0)
        else:
            D.sort()
            for i in range(k):
                ans = (ans * D[i][1]) % mod
            print(ans)
    elif B[0]+(B[1]//2)*2 < k and B[2] > 0:
        print(0)
    else:
        indd = 0
        for i in range(k-3):
            ans = (ans * D[indd][1]) % mod
            indd += 1
        if ans < 0:
            K = []
            L = ["001","100","010","111"]
            for i in range(len(L)):
                mm = 1
                ind = indd
                for j in range(3):
                    while ind < n and ((D[ind][1]<0 and L[j]=="0") or(D[ind][1]>=0 and L[j]=="1")):
                        ind += 1
                    if ind == n:
                        break
                    else:
                        mm *= D[ind][0]
                        K.append(mm)
                        ind += 1
        else:
            K = []
            L = ["101","110","011","000"]
            for i in range(len(L)):
                mm = 1
                ind = indd
                for j in range(3):
                    while ind < n and ((D[ind][1]<0 and L[j]=="0") or(D[ind][1]>=0 and L[j]=="1")):
                        ind += 1
                    if ind == n:
                        break
                    else:
                        mm *= D[ind][0]
                        K.append(mm)
                        ind += 1
        print((abs(ans) * max(K)) % mod)