Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    for i in range(k):
        ans *= -li[i][0]
        ans %= mod
    print(ans)
    exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n-1):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n-1):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    if n-k-1 >= 0:
        for i in range(n-k-1, -1, -1):
            if li[i][1] > 0:
                plus = li[i][0]
                p = i
                p1 = False
                break
        for i in range(n-k-1, -1, -1):
            if li[i][1] < 0:
                mini = li[i][0]
                m = i
                m1 = False
                break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans2 *= li[i][0]
            ans2 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if not p1 and not P1 and not M1 and not m1:
        if mini/Plus > plus/Mini:
            print(ans1)
        else:
            print(ans2)
    elif not p1 and not M1:
        print(ans2)
    elif not m1 and not P1:
        print(ans1)
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    print(-ans % mod)
    exit()
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
minus=[]
plus=[]
zero=0
for i in range(n):
    if lis[i]<0:
        minus.append(lis[i])
    elif lis[i]>0:
        plus.append(lis[i])
    else:
        zero+=1
#print(plus)
#print(minus)
#print(zero)
p=len(plus)
m=len(minus)

if n-zero<k:
    ans=0
    print(ans%mod)
    sys.exit()
if p>=k:
    state="plus"
elif (k-p)%2==0:
    state="plus"
elif m>=k-p+1:
    if k%2==1:
        if p>0:
            state="plus"
        else:
            if zero>0:
                ans=0
                sys.exit()
            else:
                state="minus"
    else:    
        state="plus"
else:
    if zero>0:
        ans=0
        print(ans%mod)
        sys.exit()
    else:
        state="minus"
#print(state)
if state=="plus":
    ans=1
    plus.sort(reverse=True)
    minus.sort()
    pros=[]
    if k%2==1:
        ans*=plus[0]
        k-=1
        for i in range((p-1)//2):
            pros.append(plus[2*i+1]*plus[2*i+2])
    else:
        ans*=1
        for i in range(p//2):
            pros.append(plus[2*i]*plus[2*i+1])
    for i in range(m//2):
        pros.append(minus[2*i]*minus[2*i+1])
    pros.sort(reverse=True)
    for i in range(k//2):
        ans=(ans*pros[i])%mod
    print(ans%mod)
    sys.exit()
elif state=="minus":
    ans=1
    plus.sort()
    minus.sort(reverse=True)
    pros=[]
    ans*=minus[0]
    k-=1
    if k%2==1:
        ans*=plus[0]
        k-=1
        for i in range((p-1)//2):
            pros.append(plus[2*i+1]*plus[2*i+2])
    else:
        for i in range(p//2):
            pros.append(plus[2*i]*plus[2*i+1])
    for i in range((m-1)//2):
        pros.append(minus[2*i+1]*minus[2*i+2])
    pros.sort()
    for i in range(k//2):
        ans=(ans*pros[i])%mod
    print(ans%mod)
    sys.exit()

Submission status: Wrong Answer

Solution code:
from queue import PriorityQueue
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


mod = 10**9+7


def prod(l):
    ret = 1
    for e in l:
        ret = (ret*e) % mod

    return ret


def main():
    n, k = geta(int)
    a = list(geta(int))

    p, n, z = [], [], 0
    for ai in a:
        if ai > 0:
            p.append(ai)
        elif ai < 0:
            n.append(-ai)
        else:
            z += 1

    ans = 1
    p.sort()
    n.sort()
    if k & 1 == 1:
        if len(p) == 0:
            if z > 0:
                print(0)
                exit()
            else:
                print(-prod(n[0:k]) % mod)
                exit()
        else:
            k -= 1
            ans *= p.pop()

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

    q = []

    n = n[::-1]
    for i in range(len(n)//2):
        q.append(n[2*i]*n[2*i+1])

    p = p[::-1]
    for i in range(len(p)//2):
        q.append(p[2*i]*p[2*i+1])

    q.sort(reverse=True)

    ans = ans * (prod(q[:k//2])) % mod

    print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split(' '))
A = sorted(list(map(int, input().split(' '))))
mod = 10 ** 9 + 7
p = 0
for i in range(N):
    if A[i] >= 0:
        break
p = i
if (p==N-1 and K%2 != 0) or (N==K and p%2 == 0):
    ans = 1
    for i in range(K):
        ans *= A[-1-i]
        ans %= mod
    print(ans)
    exit()
minus = A[:p]
plus = A[p:]
len_m = len(minus)
len_p = len(plus)
m = 0
p = 0
ans = 1
while K > 0:
    if K >= 2 and m <= len_m - 2 and p <= len_p - 2:
        if minus[m] * minus[m] >= plus[p] * plus[p + 1]:
            ans *= minus[m] * minus[m+1]
            ans %= mod
            m += 2
        else:
            ans *= plus[p] * plus[p + 1]
            ans %= mod
            p += 2
        K -= 2
    elif K >= 2 and m <= len_m-2:
        ans *= minus[m] * minus[m+1]
        ans %= mod
        m += 2
        K -= 2
    elif K >= 2 and p <= len_p-2:
        ans *= plus[p] * plus[p + 1]
        ans %= mod
        p += 2
        K -= 2
    elif p <= len_p -1:
        ans *= plus[p]
        ans %= mod
        p += 1
        K -= 1
    else:
        ans *= minus[m]
        ans %= mod
        m += 1
        K -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7

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

A.sort(reverse=True)

ans = 1
left = 0
right = len(A)-1

# 全部負のとき
if A[0] < 0:
    for i in range(K):
        ans = (ans * A[i]) % mod
elif K % 2 == 0:
    while K > 0:
        r = A[right] * A[right-1]
        l = A[left] * A[left + 1]
        if l > r:
            ans = (ans * l) % mod
            left += 2
        else:
            ans = (ans * r) % mod
            right -= 2
        K -= 2
else:
    p = A.pop(0)
    K -= 1
    right -= 1
    while K > 0:
        r = A[right] * A[right-1]
        l = A[left] * A[left + 1]
        if l > r:
            ans = (ans * l) % mod
            left += 2
        else:
            ans = (ans * r) % mod
            right -= 2
        K -= 2
    ans = (ans * p) % mod
while ans < 0:
    ans = ans + 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
combi = list(itertools.combinations(A, K))

max_combi = (10 ** 9) * -1

for x in combi:
    temp_sum = 1
    for y in x:
        temp_sum = (temp_sum * y)

    # max_combi = max(max_combi, temp_sum)
    max_combi = max(max_combi, temp_sum)
print(max_combi % mod)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
Alist = list(map(int, input().split()))

plus = []
minus = []

for a in Alist:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)

mflg = False

if K%2!=0:
    tmp1 = K-1
else:
    tmp1 = K

if len(minus)%2!=0:
    tmp2 = len(minus)-1
else:
    tmp2 = len(minus)

tmp = min(tmp1, tmp2)
if K - tmp > len(plus):
    mflg = True


if mflg:
    minus = [-m for m in minus]
    nums = minus + plus
    nums.sort()
    ans = 1
    for k in range(K):
        ans = ans * nums[k]
        ans %= (1000000007)
    
    ans = (-ans % 1000000007)
    print(ans)

else:
    plus.sort()
    minus.sort()
    plus = plus[::-1]
    minus = [-m for m in minus]

    ans = -1
    for k in range(0, len(minus)+1, 2):
        if K - k > len(plus):
            continue
        m = minus[:k]
        p = plus[:K-k]

        tmp = 1
        for i in p + m:
            tmp *= i
            ans = max(ans, tmp)
    
    ans %= 1000000007
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
d=deque(A)

l=[]
if K%2==0 or (K%2==1 and A[0]>=0):
  for i in range(K//2):
    if d[0]*d[1]>d[-1]*d[-2] and len(d)>2 and d[2]>0:
      l.append(d.popleft())
      l.append(d.popleft())
    else:
      l.append(d.pop())
      l.append(d.pop())
  if K%2==1:
    if d[0]<0:exit(1)
    l.append(d[0])
else:
  for i in range(K):
    l.append(d.popleft())
      
ans=1
for i in l:
  ans*=i
  ans%=10**9+7
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k,*A = get_all_int()
    A = list(A)

    # 答えが負である条件
    # ・Aが全て負で、Kが奇数
    # ・Aの負数が奇数個かつ0が存在せず、K=N

    # 答えが0である条件
    # ・N-(Aの0の個数) < K

    positives = 0
    zeros = 0
    negatives = 0

    for a in A:
        if a > 0:
            positives += 1
        elif a == 0:
            zeros += 1
        else:
            negatives += 1
    

    if k == 1:
        # 1個だけの場合はたんに最大値を出力する
        A.sort(reverse=True)
        print(A[0])
        exit()

    if (n-zeros) < k:
        # 答えが0
        print(0)
        exit()
    
    elif (k==n and negatives%2==1  or  n==negatives+zeros and k%2==1):
        # 答えが負
        # 絶対値小さい順にK個掛ける
        A.sort(key=lambda a: abs(a))
        # log(A)
        ans = 1
        for i in range(k):
            ans =  (ans * A[i]) % MOD
        print(ans%MOD)
        exit()

    else:
        # 答えが正
        # 絶対値大きい順にK個掛ける
        A.sort(reverse=True, key=lambda a: abs(a))
        # log(A)
        ans = 1
        n_count = 0
        last_n = 0
        last_p = 0
        for i in range(k):
            a = A[i]
            ans =  (ans * a) % MOD
            if a < 0:
                n_count += 1
                last_n = a
            elif a > 0:
                last_p = a
                # log(i, last_n)

        # log(ans, n_count, last_n)
        
        # 負数を奇数個選んでいる場合は調整する
        if n_count%2 == 1:
            first_p = None
            first_n = None
            for i in range(k,n):
                a = A[i]
                if a > 0 :
                    ans_a = ans*inv(last_n, MOD) * a
                    first_p = a
                    break
            if last_p != 0:
                for i in range(k,n):
                    a = A[i]
                    if a < 0:
                        ans_b = ans*inv(last_p, MOD) * a
                        first_n = a
                        break
                if first_n is not None:
                    if first_p is not None:
                        xx = abs(first_p) / abs(last_n)
                        yy = abs(first_n) / abs(last_p)
                        if yy > xx:
                            ans_a = ans_b
                    else:
                        ans_a = ans_b
            ans = ans_a
        
        print(ans%MOD)
        exit()

main()

Submission status: Wrong Answer

Solution code:
import heapq

mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
cnt_plus=0
cnt_zero=0
cnt_minus=0
arr_plus=[]
arr_minus=[]
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    arr_plus.append(arr[i])
  elif arr[i]<0:
    cnt_minus+=1
    arr_minus.append(-arr[i])
  else:
    cnt_zero+=1
if cnt_plus+cnt_minus<k:
  print(0)
else:
  if (k%2==1 and cnt_plus==0) or (cnt_plus+2*(cnt_minus//2)<k):
    if cnt_zero==0:
      q=[]
      for i in range(n):
        if arr[i]>0:
          heapq.heappush(q,(arr[i],1))
        if arr[i]<0:
          heapq.heappush(q,(-arr[i],-1))
      pick=[]
      for i in range(k):
        tmp,flag=heapq.heappop(q)
        pick.append(tmp)
      ans=1
      for i in range(k):
        ans*=pick[i]
        ans%=mod
      print((-ans)%mod)
    else:
      print(0)
  else:
    q=[]
    for i in range(n):
      if arr[i]>0:
        heapq.heappush(q,(-arr[i],1))
      if arr[i]<0:
        heapq.heappush(q,(arr[i],-1))
    pick=[]
    prev=0
    cnt=0
    for _ in range(k):
      tmp,flag=heapq.heappop(q)
      tmp*=-1
      if flag==1:
        pick.append(tmp)
      else:
        if cnt==0:
          prev=tmp
          cnt+=1
        else:
          cnt=0
          pick.append(prev)
          pick.append(tmp)
          prev=0
    if cnt==0:
      ans=1
      for i in range(k):
        ans*=pick[i]
        ans%=mod
      print(ans)
    else:
      cand_plus=0
      cand_minus=0
      while len(q)!=0:
        tmp,flag=heapq.heappop(q)
        tmp*=-1
        if flag==1 and cand_plus==0:
          cand_plus=tmp
        if flag==-1 and cand_minus==0:
          cand_minus=tmp
        if cand_plus!=0 and cand_minus!=0:
          break
      if pick[-1]*cand_plus>=prev*cand_minus:
        pick.append(cand_plus)
      else:
        pick=pick[:-1]
        pick.append(prev)
        pick.append(cand_minus)      
      ans=1
      for i in range(k):
        ans*=pick[i]
        ans%=mod
      print(ans)

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 = []  # 正を取り除く
            ans2 = []  # 負を取り除く
            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.append(a)
            n_remove = False
            for a in A[:K][::-1]:
                if a < 0 and not n_remove:
                    n_remove = True
                    continue
                ans2.append(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
            ans1.append(mul2)
            ans2.append(mul1)
            s1 = sum(abs(a) for a in ans1)
            s2 = sum(abs(a) for a in ans2)

            if len(posi) == 0 or mul2 == 0:
                for a in ans2:
                    ans *= a
            elif len(nega) == 0 or mul1 == 0:
                for a in ans1:
                    ans *= a
            else:
                if s1 > s2:
                    for a in ans1:
                        ans *= a
                else:
                    for a in ans2:
                        ans *= a
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    mod = 10**9+7
    n,k = map(int,raw_input().split())
    arr = list(map(int,raw_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:
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 and k % 2 == 1:
    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
if k % 2 == 1:
    c = p.pop(-1)
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*max(p[j], c)) % MOD


if ans == MOD:
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

file = 0

def solve():
    



    # for _ in range(ii()):

    n,k=mi()
    a=li()
    pos,neg=[],[]
    zero=0
    for i in a:
        if i<0:
            neg.append(i)
        if i>0:
            pos.append(i)
        if i==0:
            zero+=1
    if n==k:
        ans1=1
        for i in a:
            ans1*=i
            ans1%=mod
        print(ans1)
        exit(0)

    if k>(len(pos)+len(neg)):
        print(0)
        exit(0)
    
    if len(pos)==0:
        if k%2:
            if zero:
                print(0)
            else:
                neg.sort(reverse=True)
                ans1=1
                for i in range(k):
                    ans1*=neg[i]
                    ans1%=mod
                print(ans1)
        else:
            neg.sort()
            ans1=1
            for i in neg:
                ans1*=abs(i)
                ans1%=mod
            print(ans1)
        exit(0)
    if len(neg)==0:
        ans1=1
        for i in pos:
            ans1*=i
            ans1%=mod
        print(ans1)
        exit(0)


    ans=[]

    for i in pos:
        ans.append([i,0])
    for i in neg:
        ans.append([abs(i),1])
    ans.sort(reverse=True)
    f=-1
    f1=-1
    c=0
    for i in range(k):
        if ans[i][1]:
            c+=1
            f=i
        else:
            f1=i
    if c%2:
        if len(ans)==k:
            print(0)


        else:
            ans1=1
            for i in range(k):
                if i==f or i==f1:
                    continue
                ans1*=ans[i][0]
                ans1%=mod

            if(f1!=-1):
                f1=ans[f1][0]
            f=ans[f][0]
            f3,f4=-1,-1
            for i in range(k,len(ans)):
                if ans[i][1] and f3==-1:
                    f*=ans[i][0]
                    f3=1
                if ans[i][1]==0 and f4==-1:
                    if f1==-1:
                        f1=ans[i][0]
                    else:
                        f1*=ans[i][0]
                        f4=1
                if f3!=-1 and f4!=-1:
                    break
            if f3==-1:
                ans1*=f1
                ans1%=mod
            elif(f4==-1):
                ans1*=f
                ans1%=mod
            elif(f>f1):
                ans1*=f
                ans1%=mod
            else:
                ans1*=f1
                ans1%=mod
            print(ans1)

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

























  
















if __name__ =="__main__":

    if(file):

        if path.exists('input1.txt'):
            sys.stdin=open('input1.txt', 'r')
            sys.stdout=open('output1.txt','w')
        else:
            input=sys.stdin.readline
    solve()

Submission status: Wrong Answer

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

mod = pow(10,9)+7

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

A_plus = []
A_minus = []
A_zero = []
for i in range(N):
    if A[i] > 0:
        A_plus.append(A[i])
    elif A[i] < 0:
        A_minus.append(A[i])
    else:
        A_zero.append(A[i])
A_plus.sort()
A_minus.sort()

# 基本は絶対値の大きい順に
# マイナスは偶数個になるように取り出さないといけない
# どう選んでもマイナスを奇数個にしかできない場合はマイナスを少ない順に選ぶ
# ...全部マイナスのとき
# どう選んでも0を含んでしまう時は0を出力

# 同じ場合
if N==K:
    ans_list = A
# 0以外からぴったし選べる場合
elif len(A_plus)+len(A_minus) == K:
    if len(A_minus)%2==1:
        print(0)
        exit(0)
    else:
        ans_list = A_plus
        ans_list.extend(A_minus)
# 個数が足りない場合
elif len(A_plus)+len(A_minus) < K:
    print(0)
    exit(0)
# プラスが0個の場合
elif len(A_plus) == 0:
    # 絶対値の小さい方から
    if K%2 == 1:
        A_minus = A_minus[::-1]
        ans_list = A_minus[:K]
    else:
        ans_list = A_minus[:K]
else:
    A_plus = A_plus[::-1]
    plus_pos = 0
    minus_pos = 0
    for k in range(K):
        if minus_pos >= len(A_minus):
            plus_pos += 1
        elif plus_pos >= len(A_plus):
            minus_pos += 1
        elif abs(A_plus[plus_pos]) < abs(A_minus[minus_pos]):
            minus_pos += 1
        else:
            plus_pos += 1

    if minus_pos%2==1:
        if minus_pos >= len(A_minus) or plus_pos == 0:
            minus_pos -= 1
            plus_pos += 1
        elif plus_pos >= len(A_plus):
            plus_pos -= 1
            minus_pos += 1
        else:
            add_plus = abs(A_plus[plus_pos]/A_minus[minus_pos-1])
            add_minus = abs(A_minus[minus_pos]/A_plus[plus_pos-1])
            if add_plus > add_minus:
                plus_pos += 1
                minus_pos -= 1
            else:
                plus_pos -= 1
                minus_pos += 1
    
    if plus_pos == 0:
        ans_list = A_minus[:K]
    elif minus_pos == 0:
        ans_list = A_plus[:K]
    else:
        ans_list = A_plus[:plus_pos]
        ans_list.extend(A_minus[:minus_pos])

ans = 1
for ans_i in ans_list:
    ans = ans*ans_i%mod

print(ans)