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
from io import StringIO
import unittest
import heapq

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    mod=10**9+7
    readline=sys.stdin.readline

    arrP=[]
    arrM=[]
    arrMMM=[]
    heapq.heapify(arrP)
    heapq.heapify(arrM)
    heapq.heapify(arrMMM)
    n,k=map(int, readline().rstrip().split())
    arr=list(map(int, readline().rstrip().split()))
    cp=0
    cm=0
    cz=0
    for a in arr:
        if a < 0:
            cm+=1
            heapq.heappush(arrM,a)
            heapq.heappush(arrMMM,a*(-1))
        elif a > 0:
            cp+=1
            heapq.heappush(arrP,a*(-1))
            heapq.heappush(arrMMM,a)
        else: #0
            cz+=1
    cm4p=cp
    if cp%2==1:
        cm4p-=1
    
    ans=1

    if (cm4p+cp) >= k:
        #ans plus
        popP=-1
        popM=-1
        mc=0
        for i in range(k-1):
            if len(arrM)>0 and popM==-1:
                popM=heapq.heappop(arrM)*(-1)
            if len(arrP)>0 and popP==-1:
                popP=heapq.heappop(arrP)*(-1)
            if popM > popP:
                ans=(ans*popM)%mod
                popM=-1
                mc+=1
            else:
                ans=(ans*popP)%mod
                popP=-1
                
        if len(arrM)>0 and popM==-1:
            popM=heapq.heappop(arrM)*(-1)
        if len(arrP)>0 and popP==-1:
            popP=heapq.heappop(arrP)*(-1)
        if mc%2==0:
            ans=(ans*popP)%mod
        else:
            ans=(ans*popM)%mod
        print(ans)
        return
    elif cz>0:
        #ans zero
        print(0)
        return
    else:
        for i in range(k):
            pop=heapq.heappop(arrMMM)
            ans=(ans*pop)%mod
        ans=ans*(-1)
        ans+=3*mod
        ans=ans%mod
        print(ans)
        return
        #ans minus

    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    N, K = list(map(int, input().split()))
    A = list(map(int, sysread().split()))
    mod = 10 ** 9 + 7
    INF = mod

    plus = [a for a in A if a >= 0]
    minus = [-a for a in A if a < 0]

    plus = sorted(plus, reverse=True)
    minus = sorted(minus, reverse=True)

    P, M  = [1], [1]
    for p in plus:
        P.append((P[-1] * p) % mod)
    for m in minus:
        M.append((M[-1] * m) % mod)
    #print(P, M)


    max_ans = -mod
    for i in range(0, K+1, 2):
        if i >= len(M) or K - i >= len(P):continue
        ans = M[i] * P[K-i] % mod
        if max_ans < ans:
            max_ans = ans
        else:
            break

    if max_ans == -mod:
        P, M = [1], [1]
        for p in plus[::-1]:
            P.append((P[-1] * p) % mod)
        for m in minus[::-1]:
            M.append((M[-1] * m) % mod)
        #print(P, M)

        for i in range(1, K + 1, 2):
            #print(i)
            if i >= len(M) or K - i >= len(P): continue
            ans = (-M[i] * P[K - i]) % mod
            #print(ans)
            if max_ans < ans:
                max_ans = ans
            else:
                break


    print(max_ans)






if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort(key = lambda x:-abs(x))
    c = 0
    p = 0
    m = 0
    for i in a:
        if i != 0:
            c += 1
        if i > 0:
            p += 1
        if i < 0:
            m += 1
    if c < k:
        print(0)
        return
    f = 1
    for x in range(p+1):
        y = k-x
        if y < 0 or y > m:
            continue
        if not y&1:
            f = 0
            break
    if f:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in a[:k]:
            ans *= i
            ans %= mod
        print(ans)
        return
    plus = 0
    minus = [1]
    a.sort()
    s = 1
    s2 = 1
    k1 = 0
    k2 = 0
    for i in a:
        if i != 0:
            if i < 0:
                k1 ^= 1
                s *= -i
                if not k1:
                    minus.append(s)
                    s = 1
            else:
                k2 ^= 1
                s2 *= i
                if not k2:
                    minus.append(s2)
                    s2 = 1
    if k2:
        plus = s2
    ans = 1
    x = k>>1
    for i in range(x+1):
        ans *= minus[i]
        ans %= mod
    if (k-2*x)&1:
        ans *= plus
    print(ans%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))

num_neg=0
num_pos=0
num_zero=0
aalist=[]
for a in alist:
  if a>0:
    num_pos+=1
  elif a<0:
    num_neg+=1
  else:
    num_zero+=1
  aalist.append((abs(a),a))
aalist.sort(reverse=True)
    
if num_zero>N-K:
  print(0)
  sys.exit(0)
  
if N==K:
  answer=1
  for a in alist:
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
  
pos_possible=True
if num_pos==0:
  if K%2==1:
    pos_possible=False
    
if not pos_possible:
  aalist.sort()
  answer=1
  for i in range(K):
    aa,a=aalist[i]
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
    
aalist.sort(reverse=True)
#print(aalist)
answer=1
sgn=1
for i in range(K-1):
  aa,a=aalist[i]
  answer*=a
  answer%=MOD
  if a<0:
    sgn*=-1
for i in range(K-1,N):
  aa,a=aalist[i]
  if sgn>0 and a>=0:
    answer*=a
    answer%=MOD
    break
  elif sgn<0 and a<=0:
    answer*=a
    answer%=MOD
    break
    
print(answer)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
ls=list(map(int,input().split()))
ls.sort()
ans=1
if ls[0]>=0:
  #全部非負整数
  for i in range(k):
    ans*=ls[n-1-i]
elif ls[-1]<=0:
  #全部ひ正整数
  if k%2==1:
    for i in range(k):
      ans*=ls[n-1-i]
  else:
    for i in range(k):
      ans*=ls[i]
else:
  #不も正もある
  if k<2:
    for i in range(k):
      ans*=ls[n-1-i]
  else:
    lcnt=0
    rcnt=0
    tmp=0
    tmp2=0
    lk=k
    em=False
    while True:
      tmp=ls[lcnt]*ls[lcnt+1]
      if tmp<0:
        break
      tmp2=ls[-1-rcnt]*ls[-2-rcnt]
      if tmp>=tmp2:
        ans*=tmp
        lcnt+=2
        lk-=2
      else:
        ans*=tmp2
        rcnt+=2
        lk-=2
      if lk<2:
        break
    if em:
      pass
    else:
      for i in range(lk):
        ans*=ls[-1-rcnt-i]

Submission status: Wrong Answer

Solution code:
from collections import Counter, deque

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

MOD = 10 ** 9 + 7

c = Counter()
for a in A:
    if a == 0:
        c['0'] += 1
    elif a < 0:
        c['-'] += 1
    else:
        c['+'] += 1

if c['-'] + c['+'] < K:
    print(0)
elif (c['-'] == N and K % 2 == 1) or (N == K and c['-'] % 2 == 1):
    def f(x):
        if x == 0:
            return 10 ** 9
        else:
            return abs(x)


    A = sorted(A, key=f)
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD

    print(ans)
else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    plus = deque()
    minus = deque()

    for i in range(K):
        if A[i] >= 0:
            plus.append(A[i])
        else:
            minus.append(A[i])

    if len(minus) % 2 == 1:
        p = None
        m = None
        for a in A[K:]:
            if a >= 0 and p is None:
                p = a
            if a < 0 and m is None:
                m = a
            if p is not None and m is not None:
                break
        if m is None and p is None:
            pass
        elif len(minus) == 0 or len(plus) == 0:
            pass
        elif m is None and p is not None:
            minus.pop()
            plus.append(p)
        elif m is not None and p is None:
            plus.pop()
            minus.append(m)
        elif minus[-1] * m > plus[-1] * p:
            plus.pop()
            minus.append(m)
        else:
            minus.pop()
            plus.append(p)

    ans = 1
    while plus:
        ans *= plus.popleft()
        ans %= MOD
    while minus:
        ans *= minus.popleft()
        ans %= MOD

    print(ans)

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 & m != 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:
import sys
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sorted(A, key=abs, reverse=True)
X = 1
pm = 0
for i in range(K - 1):
    if S[i] < 0:
        pm = 1 - pm
    X = X * abs(S[i]) % MOD
    X = X % MOD
for i in range(K - 1, N):
    if pm == 0:
        if S[i] > 0:
            Y = X * S[i] % MOD
            print(Y % MOD)
            sys.exit()
    else:
        if S[i] < 0:
            Y = X * abs(S[i]) % MOD
            print(Y % MOD)
            sys.exit()

if S[0] > 0:
    pm = 0
else:
    pm = 1
for i in range(K - 2, -1, -1):
    if pm == 0:
        if S[i] < 0:
            X = 1
            for j in range(K):
                if j == i:
                    continue
                X = X * abs(S[j]) % MOD
                X = X % MOD
            print(X % MOD)
            sys.exit()
    if pm == 1:
        if S[i] > 0:
            X = 1
            for j in range(K):
                if j == i:
                    continue
                X = X * abs(S[j]) % MOD
                X = X % MOD
            print(X % MOD)
            sys.exit()

X = 1
S = S[::-1]
for i in range(K):
    X = X * abs(S[i]) % MOD
X *= -1
print(X % MOD)

Submission status: Wrong Answer

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

mia, pla, zero = [], [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai > 0:
        pla.append(ai)
    elif ai == 0:
        zero.append(ai)

cnt = 1
while k > 0:
    if len(pla) == 0 and len(mia) == 0:
        print(0)
        break
    elif len(pla) == 0:
        cnt = cnt * mia.pop() % mod
        k -= 1
    elif len(mia) <= 1 or k==1:
        cnt = cnt * pla.pop() % mod
        k -= 1
    elif len(pla) == 1:
        if k % 2 == 1:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif k % 2 == 0 and len(mia) >= 2:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
        elif k % 2 == 0 and len(mia) <= 1:
            print(0)
            break
    elif len(pla) >= 2 and len(mia) >= 2:
        if pla[-1] * pla[-2] >= mia[-1] * mia[-2]:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif pla[-1] * pla[-2] < mia[-1] * mia[-2]:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        return

    B = []
    n_plus = 0
    for a in A:
        if a >= 0:
            B.append((a, True))
            n_plus += 1
        else:
            B.append((-a, False))

    if n_plus == 0:
        A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return

    B.sort(key=lambda x: x[0], reverse=True)
    cnt = 0
    prev_minus = None
    prev_plus = None
    for i in range(K):
        b, flag = B[i]

        if flag:
            prev_plus = b
        else:
            cnt += 1
            prev_minus = b

    if prev_plus == 0:
        print(0)
        return

    if cnt % 2 == 0:
        ans = 1
        for i in range(K):
            b, flag = B[i]
            ans *= b
            ans %= MOD
        print(ans)
        return

    next_minus = None
    next_plus = None
    for i in range(K, N):
        b, flag = B[i]
        if flag:
            if next_plus is None:
                next_plus = b
        else:
            if next_minus is None:
                next_minus = b

    if next_plus is not None and prev_minus is not None:
        ans1 = 1
        ignored = False
        for i in range(K):
            b, flag = B[i]

            if ignored or prev_minus != b:
                ans1 *= b
                ans1 %= MOD
                continue

            if prev_minus == b:
                ignored = True

        ans1 *= next_plus
        ans1 %= MOD
    else:
        ans1 = -INF

    if next_minus is not None and prev_plus is not None:
        ans2 = 1
        ignored = False
        for i in range(K):
            b, flag = B[i]

            if ignored or prev_plus != b:
                ans2 *= b
                ans2 %= MOD
                continue

            if prev_plus == b:
                ignored = True

        ans2 *= next_minus
        ans2 %= MOD
    else:
        ans2 = -INF

    if ans1 == -INF:
        print(ans2)
    elif ans2 == -INF:
        print(ans1)
    else:
        if prev_minus * next_minus > prev_plus * next_plus:
            print(ans2)
        else:
            print(ans1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from typing import Reversible


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

A.sort(key=lambda x: abs(x),reverse=True)
if N - K < A.count(0):
    print(0)
    exit()
if all(a <= 0 for a in A):
    if 0 in A:
        print(0)
    else:
        ans = 1
        A.sort(reverse=True)
        for a in A[:K]:
            ans = ans * a % mod
        print(ans)
    exit()
minus1 = 0
minus2 = 0
ans1 = 1
ans2 = 0
last_minus = 1
last_plus = -1
n = 0
for a in A:
    if a == 0:
        continue
    n += 1
    ans1 = ans1 * a % mod
    if a < 0:
        minus1 += 1
        last_minus = a
    if n == K:
        if minus1 % 2 != 0:
            ans1 = ans1 * pow(last_minus, mod-2, mod) % mod
            n -= 1
            minus1 -= 1
        else:
            break
if n != K:
    ans1 = -1
n = 0
for a in A:
    if a == 0:
        continue
    n += 1
    ans2 = ans2 * a % mod
    if a < 0:
        minus2 += 1
    else:
        last_plus = a
    if n == K:
        if minus2 % 2 != 0:
            ans2 = ans2 // last_plus % mod
            n -= 1
        else:
            break
if n != K:
    ans2 = -1
print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
def hugo(k):
  h=0
  for i in k:
    if i>=0:
      h+=1
  if h==0:
    return True
  else:
    return False
n,k=map(int,input().split())
mod=10**9+7
a=list(map(int,input().split()))
s=sorted(a,key=abs)
s.reverse()
a=list(map(abs,a))
a.sort()
a.reverse()
x=1
o=0
m=1
if k%2==1 and hugo(s):
  s.reverse()
  if k>1:
    for i in s[0:k]:
      m*=i
      o+=1
      if o%2==0:
        x=(x*m)%mod
        m=1
    x*=m
    x%=mod
    print(x) 
  else:
    print(s[0]%mod)
else:
  if k>1:
    for i in s[0:k-1]:
      if i>=0:
        x=(x*i)%mod
      else:
        m*=i
        o+=1
        if o%2==0:
          x=(x*m)%mod
          m=1
    if m<0:
      y=0
      z=1
      l=0
      for i in s[k-1:]:
        if i<0:
          y=i
          break
      for i in s[k-1:]:
        if i>=0:
          z*=i
          l+=1
          if l==2:
            break
      m*=y
      if z>=m:
        x=(x*z)%mod
      else:
        x=(x*m)%mod
    print(x)
  else:
    for i in s:
      if i>=0:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_right


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    mod = 10**9+7

    neg = 0

    cnt = 0
    ret = 1

    n_pos = n-bisect_right(sorted(A), 0)
    if k <= n_pos or 1 != (k-n_pos) % 2:
        for a in sorted(A, key=lambda x: abs(x), reverse=True):
            if a < 0:
                if neg < 0 and 2 <= k-cnt:
                    neg = (a*neg) % mod
                    ret = (ret*neg) % mod
                    cnt += 2
                    neg = 0
                elif neg == 0:
                    neg = a
            elif 0 < a:
                ret = (ret*a) % mod
                cnt += 1

            if k <= cnt:
                break
    else:
        for a in sorted(A, key=lambda x: abs(x)):
            if a != 0:
                ret = (a*ret) % mod
                cnt += 1
            if k <= cnt:
                break

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from collections import deque

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    q = []
    for a in A:
        if a < 0: heappush(q, (a, -1))
        else: heappush(q, (-a, 1))

    qu = deque()
    minus = -1
    plus = 1
    plusFound = False
    mc = 0
    ans = 1
    for i in range(K):
        a, pm = heappop(q)
        if pm == 1:
            plusFound = True
            ans *= plus
            ans %= mod
            plus = -a
        else:
            if mc == 1:
                ans *= (minus * a) % mod
                ans %= mod
            else:
                minus = a
            mc ^= 1
        qu.append((a, pm))
    if mc == 1:
        stock = 1
        for i in range(K, N):
            a, pm = heappop(q)
            if pm == 1:
                if stock == 1:
                    ans *= (-a * plus) % mod
                    ans %= mod
                else:
                    if a > stock:
                        ans *= (minus * stock) % mod
                    else:
                        if plus * -1 <= minus: ans *= (-a * plus) % mod
                        else: ans *= (minus * stock) % mod
                    ans %= mod
                print(ans)
                break
            elif plusFound and stock == 1:
                stock = a
            qu.append((a, pm))
        else: #ここまで来るのは0以上の数が一つもない場合
            ans = 1
            for i in range(K):
                a, pm = qu.pop()
                ans *= a
                ans %= mod
            print(ans)
    else: 
        print((ans * plus) % mod)

    return 0

if __name__ == "__main__":
    solve()

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):
    ans = 1
    for i in range(K):
        ans *= A[-1 - i]
        ans %= mod
    print(ans)
    exit()
minus = A[:p]
plus = sorted(A[p:],reverse=True)
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:
import itertools

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


max = -10 ** 99
ans = 1

for i in itertools.combinations(a,k):
    for a in i:
        ans = ans * a
    if ans > max:
        max = ans
    ans = 1

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

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
pm = 1
ans = 1
a.sort()
cnt = 0
if n > k:
    for x in a:
        if x < 0: cnt += 1
    if cnt%2 == 1:
        a.pop(cnt - 1)
        n -= 1

if k%2 == 1 and a[n - 1] < 0:
    if 0 in a:
        print(0)
        sys.exit()
    for i in range(k):
        ans = (ans * a[n - 1 - i])%mod
    print(ans%mod)
    sys.exit()
for i in range(k//2):
    p = a[n-1] * a[n-2]
    m = a[0] * a[1]
    if p > m:
        #print(a)
        ans = (ans * p)%mod
        a.pop(n - 1)
        a.pop(n - 2)
        #print(ans)
    else:
        ans = (ans * m)%mod
        a.pop(1)
        a.pop(0)
    n -= 2
if k%2 == 1:
    ans = (ans * a[n - 1])%mod
print(ans%mod)

Submission status: Wrong Answer

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

def solve():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    P = 10**9 + 7
    def mod_prod(a,b):
        return (a % P) * (b % P) % P

    def mod_fact(a):
        ret = 1
        for i in range(a):
            ret = ret * (i + 1) % P
        return ret

    def mod_pow(a, n):
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * a % P
            a = a * a % P
            n = n >> 1
        return ret

    def mod_div(a, b):
        b_inv = mod_pow(b, P - 2)
        return a * b_inv % P

    def mod_comb(a,b):
        ret = 1
        b = min(b, a - b)
        for i in range(b):
            ret *= a - i
            ret %= P
        ret = mod_div(ret, mod_fact(b))
        return ret

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

    topK = A[:K]
    rest = A[K:]

    if sum(1 if a < 0 else 0 for a in topK) % 2 == 0:
        ans = 1
        for a in topK:
            ans *= a
            ans %= P
        print(ans)
    else:
        ans1 = 0
        rest_negs = [a for a in rest if a < 0]
        topk_poss = [a for a in topK if a >= 0]
        if len(rest_negs) > 0 and len(topk_poss) > 0:
            ans1 = 1
            mult, div = min(rest_negs), min(topk_poss)
            for a in topK:
                ans1 *= a
                ans1 %= P
            ans1 = mod_div(ans1, min(topk_poss))
            ans1 = ans1 * min(rest_negs) % P
        else:
            mult, div = 0, 1000000

        ans2 = 0
        rest_poss = [a for a in rest if a >= 0]
        topk_negs = [a for a in topK if a < 0]
        if len(rest_poss) > 0 and len(topk_negs) > 0:
            ans2 = 1
            for a in topK:
                ans2 = ans2 * a % P
            ans2 = mod_div(ans2, max(topk_negs))
            ans2 = ans2 * max(rest_poss) % P

            mult2, div2 = max(rest_poss), max(topk_negs)
        else:
            mult2, div2 = 0, 1000000
        
        if mult == 0 and mult2 == 0:
            ans3 = 1
            for i in range(K):
                ans3 = ans3 * A[N - 1 - i] % P
            print(ans3)
        elif mult * div2 > mult2 * div:
            print(ans1)
        else:
            print(ans2)

solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


n, k = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for i in range(n):
    if A[i] < 0:
        neg.append(A[i])
    elif A[i] > 0:
        pos.append(-A[i])

if len(pos) + len(neg) < k:
    print(0)
    exit()

pos.sort()
neg.sort()
# print(pos, neg)

if len(pos) == 0:
    if k%2 == 1:
        if n - (len(pos) + len(neg)) > 0:
            print(0)
            exit()
        ans = 1
        for i in range(1, k+1):
            ans = (ans * neg[-i]) % MOD
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans = (ans * neg[i]) % MOD
        print(ans)
        exit()

elif len(neg) == 0:
    ans = 1
    for i in range(k):
        ans = (ans * -pos[i]) % MOD
    print(ans)
    exit()

else:
    mix = pos + neg
    mix.sort()
    val = mix[k-1]
    pos_idx = bisect.bisect(pos, val) - 1
    neg_idx = bisect.bisect(neg, val) - 1
    pos_idx2 = bisect.bisect_left(pos, val) - 1
    neg_idx2 = bisect.bisect_left(neg, val) - 1
    # print(pos_idx, neg_idx, pos_idx2, neg_idx2)
    if pos_idx + neg_idx + 2 > k:
        rem = k-2-pos_idx2-neg_idx2
        if neg_idx2%2 == 0 and neg_idx2 < neg_idx:
            neg_idx2 += 1
            rem -= 1
        while neg_idx2+1 < neg_idx and rem >= 2:
            neg_idx2 += 2
            rem -= 2
        while rem >= 1:
            pos_idx2 += 1
            rem -= 1
        pos_idx = pos_idx2
        neg_idx = neg_idx2

    # print(pos_idx, neg_idx)

    if neg_idx % 2 == 0:
        if neg_idx == len(neg)-1 and pos_idx == len(pos)-1:
            print(0)
            exit()
        elif neg_idx == len(neg)-1:
            neg_idx -= 1
            pos_idx += 1
        elif pos_idx == len(pos)-1:
            neg_idx += 1
            pos_idx -= 1
        else:
            if neg[neg_idx+1] >= pos[pos_idx+1]:
                neg_idx -= 1
                pos_idx += 1
            else:
                neg_idx += 1
                pos_idx -= 1

    # print(pos_idx, neg_idx)
    ans = 1
    for i in range(pos_idx+1):
        ans = (ans * -pos[i]) % MOD
    for i in range(neg_idx + 1):
        ans = (ans * neg[i]) % MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x.append(i)
        if i<0:y.append(i)
    if len(x)+len(y)<k or len(x)<k and (len(y)<k or len(y)%2 and not x) and (k-len(x))%2 and len(x)+len(y)<n:
        print(0)
        exit()
    if len(x)<k and (len(y)<k or len(y)%2 and not x) and (k-len(x))%2:
        x=sorted(x+[-i for i in y])[:k]
        x[0]*=-1
        c=1
        for i in x:
            c=c*i%M
        print(c)
        exit()
    x=sorted(x)[::-1][:k]
    y.sort()
    m=len(y)
    i=len(x)
    j=0
    if i<k:
        j=k-i
        x+=y[:j]
        j+=1
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

Submission status: Wrong Answer

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

a = sorted(a, reverse=True)

if a[0] < 0 and k%2 == 1:
    for i in range(k):
        ans *= a.pop(0)
else:
    tobashi = False
    for i in range(k):
        if tobashi:
            tobashi = False
            continue

        if abs(a[0]) >= abs(a[-1]):
            ans *= a.pop(0)
        else:
            if a[-1]*a[-2] > a[0]*a[1]:
                if i < k-1:
                    ans *= (a.pop())
                    ans *= (a.pop())
                    tobashi = True
                else:
                    ans *= a.pop(0)

ans = ans%wari
print(ans)