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())
A = list(map(int, input().split()))
mod = 10**9 + 7
A.sort(reverse=True)
kk = K % 2
k2 = K // 2
p = 1
if A[-1] > 0:
    for i in range(K):
        p = (p * A[i]) % mod
elif A[0] < 0:
    if kk == 0:
        for i in range(K):
            p = (p * A[-i-1]) % mod
    else:  # kk == 1:
        for i in range(K):
            p = (p * A[i]) % mod
else:
    if kk == 0:
        ip = 0
        im = -1
        for i in range(k2):
            pp = (p * A[ip] * A[ip + 1]) % mod
            pm = (p * A[im] * A[im - 1]) % mod
            if pp > pm:
                p = pp
                ip += 2
            else:
                p = pm
                im -= 2
    else:  # kk == 1:
        # case 1
        p1 = A[0]
        ip = 1
        im = -1
        for i in range(k2):
            pp = (p1 * A[ip] * A[ip + 1]) % mod
            pm = (p1 * A[im] * A[im - 1]) % mod
            if pp > pm:
                p1 = pp
                ip += 2
            else:
                p1 = pm
                im -= 2
        # case 2
        p2 = A[-1]
        ip = 0
        im = -2
        for i in range(k2):
            pp = (p2 * A[ip] * A[ip + 1]) % mod
            pm = (p2 * A[im] * A[im - 1]) % mod
            if pp > pm:
                p2 = pp
                ip += 2
            else:
                p2 = pm
                im -= 2
        p = max(p1, p2)
print(p)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        if minnega == 0:
            pp
        maxposi = 0
        maxnega = 0
        flag = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            elif a[i] < 0:
                if maxnega == 0:
                    maxnega = a[i]


        if abs(minposi*maxposi) <= abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)

        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
div = 10**9+7
a = sorted(A)
ans = 1
l = 0
r = -1
if K == N or (K % 2 != 0 and a[-1] < 0):
    for _ in range(K):
        ans *= a[r]
        r-=1
        ans %= div
    print(ans)
    exit()
for _ in range(K//2):
    if a[0] * a[1] > a[-1] * a[-2]:
        ans *= a[l]
        ans %= div
        ans *= a[l+1]
        ans %= div
        l+=2
    else:
        ans *= a[r]
        ans %= div
        ans *= a[r-1]
        ans %= div
        r-=2
if K % 2 == 1:
    ans *= a[r]
    ans %= div
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]


        maxposi = 0
        maxnega = 0
        flag = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            elif a[i] < 0:
                if maxnega == 0:
                    maxnega = a[i]

        if minposi == 0:
            ans *= pow(a[k-1], mod-2, mod)
            ans *= maxposi

        elif abs(minposi*maxposi) <= abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)

        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)

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 N==K:
  answer=1
  for a in alist:
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
  
pos_possible=True
if num_neg==N and 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
pos_absmin=0
neg_absmin=0
for i in range(K):
  aa,a=aalist[i]
  answer*=a
  answer%=MOD
  if a>0:
    pos_absmin=a  
  elif a<0:
    neg_absmin=a
    sgn*=-1
  else:
    sgn=0

if sgn==0:
  print(0)    
elif sgn>0:
  print(answer)
else:
  pos_absmax=0
  neg_absmax=0
  for i in reversed(range(K,N)):
    aa,a=aalist[i]
    if a>0:
      pos_absmax=a
    else:
      neg_absmax=a
      
  #print(pos_absmin,neg_absmin,pos_absmax,neg_absmax)
  if abs(pos_absmin*neg_absmax)<abs(pos_absmax*neg_absmin):
    answer*=neg_absmax%MOD
    answer*=pow(pos_absmin,MOD-2,MOD)
    answer%=MOD
  else:
    answer*=pos_absmax
    answer*=pow(neg_absmin%MOD,MOD-2,MOD)
    answer%=MOD
  
  print(answer)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from collections import deque
#import operator

#解説見た

def main():
    MOD = int(1e9 + 7)
    N, K = tuple(int(c) for c in input().split())
    A = [int(c) for c in input().split()]
    A_plus = [x for x in A if x >= 0]
    A_plus.sort(reverse=True)
    A_minus = [x for x in A if x < 0]
    A_minus.sort()

    if K == 1:
        return max(A) % MOD
    if K == N:
        #ans = reduce(operator.mul, A)
        ans = 1
        for t in A:
            ans *= t
            ans %= MOD
        return ans % MOD

    if len(A_plus) == 0:
        #minusだけから選ぶ場合
        if K % 2 == 1:
            #答えは負になるので、絶対値が小さい順に積を取る
            ans = 1
            for t in list(reversed(A_minus))[:K]:
                ans *= t
                ans %= MOD
            return ans
        else:
            #答えは正になるので、絶対値が大きい順に積をとる
            ans = 1
            for t in A_minus[:K]:
                ans *= t
                ans %= MOD
            return ans
    
    k = K
    S = []
    A_plus = deque(A_plus)
    A_minus = deque(A_minus)
    if k % 2 == 1:
        t = A_plus.popleft()
        S.append(t)
        k -= 1
    #kは偶数になった
    while k > 0:
        if len(A_minus) < 2:
            t1 = A_plus.popleft()
            S.append(t1)
            t2 = A_plus.popleft()
            S.append(t2)
            k -= 2
        elif len(A_plus) < 2:
            t1 = A_minus.pop()
            S.append(t1)
            t2 = A_minus.pop()
            S.append(t2)
            k -= 2
        else:
            t_p = A_plus[0] * A_plus[1]
            t_m = A_minus[-1] * A_minus[-2]
            if t_p >= t_m:
                t1 = A_plus.popleft()
                S.append(t1)
                t2 = A_plus.popleft()
                S.append(t2)
                k -= 2
            else:
                t1 = A_minus.pop()
                S.append(t1)
                t2 = A_minus.pop()
                S.append(t2)
                k -= 2
    ans = 1
    for t in S:
        ans *= t
        ans %= MOD
    return ans % MOD

if __name__ == "__main__":
    ret = main()
    print(ret)

Submission status: Wrong Answer

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

plus=[]
minus=[]
zero=0

for i in li:
  if i>0:
    plus.append(i)
  elif i==0:
    zero+=1
  else:
    minus.append(abs(i))
plus.sort()
minus.sort()

#print(minus)

res=1

if K>N-zero:
  res=0
elif len(plus)==0:
  if zero>0:
    res==0
  else:
    for i in range(K):

      res=(res*minus[i])
      res=res%(10**9+7)
    res=-res
    
else:
  while K>1:
    if len(plus)>1 and len(minus)>1:
      if plus[-1]*plus[-2] > minus[-1]*minus[-2]:
          res=res*plus[-1]*plus[-2]
          del plus[-2:]
          K-=2
      else:
        res=res*minus[-1]*minus[-2]
        del minus[-2:]
        K-=2

    elif len(plus)<2 and len(minus)>=2:
      res=res*minus[-1]*minus[-2]
      del minus[-2:]
      K-=2
      
    elif len(plus)>=2 and len(minus)<2:
      res=res*plus[-1]*plus[-2]
      del plus[-2:]
      K-=2
    
    res=res%(10**9+7)
    
  if K==0:
    res=res
  elif len(plus)>0:
    res=res*plus[-1]
  else:
    res=res*minus[-1]*(-1)
  
print(res%(10**9+7))

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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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

if N == K:
	ans = 1
	for x in A:
		ans = ans*x%mod
	print(ans)
	exit()

a = []
for x in A:
	flg = 0
	if x < 0:
		flg = 1
	a.append([x, abs(x), flg])

a.sort(key = lambda x: -x[1])

#print(a)

flg_sum = sum([x[2] for x in a[:K]])

if flg_sum%2 == 0:
	ans = 1
	for x in a[:K]:
		ans = ans*x[1]%mod
	print(ans)
	exit()


flg = a[K-1][2]
for i in range(K, N):
	if a[i][2] != flg:
		ans = 1
		for j in range(K-1):
			ans = ans*a[j][1]%mod
		print(ans*a[i][1]%mod)
		exit()

for i in range(K-1, -1, -1):
	if a[i][2] != flg:
		ans = 1
		for j in range(K+1):
			if j != i:
				ans = ans*a[j][1]%mod
		print(ans)
		exit()

ans = 1
for x in a[::-1][:K]:
	ans = ans*x[0]%mod

print(ans)

Submission status: Wrong Answer

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = 0
if len(pos) == 0 or n == k:
    ans = 1
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    from collections import deque
    ans = 1
    neg_new = []
    for i in range(0, len(neg)//2):
        neg_new.append(neg[2*i] * neg[2*i+1])
    neg_new = deque(sorted(neg_new, reverse = True))
    pos = deque(pos)
    if k % 2 == 1:
        k -= 1
        ans = pos.popleft()
    else:
        ans = 1
    while k > 0:
        if len(pos) >= 2 and len(neg_new) >= 1:
            if pos[0] * pos[1] > neg_new[0]:
                ans *= pos.popleft() * pos.popleft()
            else:
                ans *= neg_new.popleft()
        elif len(pos) >= 2:
            ans *= pos.popleft() * pos.popleft()
        else:
            ans *= neg_new.popleft()
        k -= 2
        ans %= mod
    print(ans % mod)

Submission status: Wrong Answer

Solution code:
from functools import reduce
#import operator

#解説見た

def main():
    MOD = int(1e9 + 7)
    N, K = tuple(int(c) for c in input().split())
    A = [int(c) for c in input().split()]
    A_plus = [x for x in A if x >= 0]
    A_plus.sort(reverse=True)
    A_minus = [x for x in A if x < 0]
    A_minus.sort()

    if K == 1:
        return max(A) % MOD
    if K == N:
        #ans = reduce(operator.mul, A)
        ans = 1
        for t in A:
            ans *= t
            ans %= MOD
        return ans % MOD

    if len(A_plus) == 0:
        #minusだけから選ぶ場合
        if K % 2 == 1:
            #答えは負になるので、絶対値が小さい順に積を取る
            ans = 1
            for t in list(reversed(A_minus))[:K]:
                ans *= t
                ans %= MOD
            return ans
        else:
            #答えは正になるので、絶対値が大きい順に積をとる
            ans = 1
            for t in A_minus[:K]:
                ans *= t
                ans %= MOD
            return ans
    
    k = K
    S = []
    if k % 2 == 1:
        t = A_plus.pop(0)
        S.append(t)
        k -= 1
    #kは偶数になった
    while k > 0:
        if len(A_minus) < 2:
            t1 = A_plus.pop(0)
            S.append(t1)
            t2 = A_plus.pop(0)
            S.append(t2)
            k -= 2
        elif len(A_plus) < 2:
            t1 = A_minus.pop()
            S.append(t1)
            t2 = A_minus.pop()
            S.append(t2)
            k -= 2
        else:
            t_p = A_plus[0] * A_plus[1]
            t_m = A_minus[-1] * A_minus[-2]
            if t_p >= t_m:
                t1 = A_plus.pop(0)
                S.append(t1)
                t2 = A_plus.pop(0)
                S.append(t2)
                k -= 2
            else:
                t1 = A_minus.pop()
                S.append(t1)
                t2 = A_minus.pop()
                S.append(t2)
                k -= 2
    ans = 1
    for t in S:
        ans *= t
        ans %= MOD
    return ans % MOD

if __name__ == "__main__":
    ret = main()
    print(ret)

Submission status: Wrong Answer

Solution code:
from functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return x2, y2, n

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
A = sorted(A, key=abs, reverse=True)
cand = []
minus = False
last_plus, last_minus = None, None
for a in A[:K]:
    cand.append(a)
    if a < 0: minus = not minus; last_minus = a
    elif a > 0: last_plus = a
ans = reduce(lambda x, y: x * y % MOD, cand)
if minus:
    ans *= modular_inverse(last_minus, MOD)
    ans %= MOD
    for a in A[K:]:
        if a > 0: ans *= a; ans %= MOD; break
    else:
        if last_plus is not None:
            if A[K:]:
                ans *= last_minus * modular_inverse(last_plus, MOD) * A[K]
                ans %= MOD
            else:
                ans *= last_minus
                ans %= MOD
        else:
            ans = reduce(lambda x, y: x * y % MOD, A[::-1][:K])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
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 S(): return input()
def LS(): return input().split()


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

n, k = LI()
a = LI()
a = sorted(a, key=lambda x: abs(x))[::-1]
# print(a)
neg = [i for i in a if i < 0][::-1]
pos = [i for i in a if i > 0]
ans = 1
if len(pos) == 0:
    if k % 2 == 0:
        for elem in a[:k]:
            ans = ans * elem % MOD
    else:
        for elem in a[::-1][:k]:
            ans = ans * elem % MOD
    print(ans)
else:
    for elem in a[:k]:
        ans = ans * elem % MOD
    if ans < 0:  # 非負にした上でなるべく大きな数になるようにする
        # 取り除く要素の絶対値は小さく、加える要素の絶対値は大きく
        elems = a[:k]
        neg = [i for i in elems if i < 0][::-1]
        pos = [i for i in elems if i > 0]
        # 負の数を取り除いて正の数を加える
        elems = neg[:-1] + pos[:1]
        ans_1 = 1
        for elem in elems:
            ans_1 = ans_1 * elem % MOD
        # 正の数を取り除いて負の数を加える
        ans_2 = 1
        elemes = neg[-2:-1] + pos[:-1]
        for elem in elems:
            ans_2 = ans_2 * elem % MOD
        ans = max(ans_1, ans_2)

    print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort()
minus = []
m = 0
plus = []
p = 0
zero = 0
for i in range(n):
    if a[i] < 0:
        minus.append(a[i])
        m += 1
    elif a[i] >= 0:
        plus.append(a[i])
        p += 1

plus = plus[::-1]
for i in range(1, p):
    plus[i] = plus[i-1] * plus[i]
    plus[i] %= mod

for i in range(m):
    minus[i] = -minus[i]

if p >= k:
    ans = plus[k-1]
else:
    ans = -inf
tmp = 1
for i in range(m):
    tmp *= minus[i]
    tmp %= mod
    if i % 2:
        r = k - (i+1)
        if r == 0:
            ans = max(ans, tmp)
        elif 0 < r <= p:
            ans = max(ans, tmp * plus[r-1] % mod)

minus = minus[::-1]
tmp = 1
for i in range(m):
    tmp *= minus[i]
    tmp %= mod
    if i % 2 == 0:
        r = k - (i+1)
        if r == 0:
            ans = max(ans, -tmp)
        elif 0 < r <= p:
            ans = max(ans, -tmp * plus[p-r])
print(ans % mod)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
import sys

mod = 10**9 + 7

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

# 0も入れておく
pos_list = []
neg_list = []
for a_i in A:
    if a_i >= 0:
        pos_list.append(a_i)
    else:
        neg_list.append(a_i)

pos_list.sort()
neg_list.sort()


lp = len(pos_list)
ln = len(neg_list)

# 前計算
# 大きい順にかけたもの
pos_values = []
tmp = 1
for i, v in enumerate(sorted(pos_list, reverse=True)):
    if i == lp:
        break
    tmp *= v
    tmp %= mod
    pos_values.append(tmp)
pos_rev_values = []
tmp = 1
for i, v in enumerate(pos_list):
    if i == lp:
        break
    tmp *= v
    tmp %= mod
    pos_rev_values.append(tmp)
# print(pos_rev_values)

# 最大値が大きい順にかけたもの
neg_values = []
tmp = 1
for i, v in enumerate(neg_list):
    if i == ln:
        break
    tmp *= v * (-1)
    tmp %= mod
    neg_values.append(tmp)
# print(neg_values)

neg_rev_values = []
tmp = 1
for i, v in enumerate(sorted(neg_list, reverse=True)):
    if i == ln:
        break
    tmp *= v * (-1)
    tmp %= mod
    neg_rev_values.append(tmp)
# print(neg_rev_values)

# print("pos", len(pos_values))
# print("neg", len(neg_values))
# print("neg_rev", len(neg_rev_values))

ans = -float("inf")
# 最大の正の場合
for NK in range(0, K+1, 2):
    tmp = 1
    if NK > ln:
        break
    if K - NK > lp:
        continue

    if NK > 0:
        tmp *= neg_values[NK-1]
    if K-NK > 0:
        tmp *= pos_values[K-NK-1]
    # print(neg_values[NK-1], pos_values[K-NK-1])
    ans = max(ans, tmp % mod)
if ans != -float("inf"):
    print(ans)
    sys.exit()

# 最大がマイナスになる場合
ans = float("inf")
for NK in range(1, K+1, 2):
    tmp = 1
    if NK > ln:
        break
    if K - NK > lp:
        continue
    if NK > 0:
        tmp *= neg_rev_values[NK-1]
    if K-NK > 0:
        tmp *= pos_rev_values[K-NK-1]
    # print(tmp)
    ans = min(ans, tmp)

print(-1 * ans % mod)

Submission status: Wrong Answer

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

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

import sys
input = sys.stdin.readline

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

N,K = IL()
A = IL()
A = sorted(A,key= lambda x:-abs(x))

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

if max(A)<0 and K%2==1:
  ans = 1
  for i in range(K):
    ans *= A[N-1-i]
    ans %= MOD
  print(ans)
  exit()

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if A[i] < 0:
    last_M = i
    count_M += 1
  if A[i] > 0:
    last_P = i

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

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

Submission status: Wrong Answer

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] > 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = 0
if len(pos) == 0 or n == k:
    ans = 1
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    from collections import deque
    ans = 1
    neg_new = []
    for i in range(0, len(neg)//2):
        neg_new.append(neg[2*i] * neg[2*i+1])
    neg_new = deque(sorted(neg_new, reverse = True))
    pos = deque(pos)
    if k % 2 == 1:
        k -= 1
        ans = pos.popleft()
    else:
        ans = 1
    while k > 0:
        if len(pos) >= 2 and len(neg_new) >= 1:
            if pos[0] * pos[1] > neg_new[0]:
                ans *= pos.popleft() * pos.popleft()
            else:
                ans *= neg_new.popleft()
        elif len(pos) >= 2:
            ans *= pos.popleft() * pos.popleft()
        else:
            ans *= neg_new.popleft()
        k -= 2
        ans %= mod
    print(ans % mod)