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:

def maxProductSubarrayOfSizeK(A, n, k): 

	# sorting given input array 
	A.sort() 

	product = 1

	if (A[n - 1] == 0 and (k & 1)): 
		return 0

	if (A[n - 1] <= 0 and (k & 1)) : 
		for i in range(n - 1, n - k + 1, -1): 
			product *= A[i] 
		return product 

	# else 
	# i is current left pointer index 
	i = 0

	# j is current right pointer index 
	j = n - 1


	if (k & 1): 
		product *= A[j] 
		j-= 1
		k-=1

	k >>= 1

	for itr in range( k) : 

		# product from left pointers 
		left_product = A[i] * A[i + 1] 

		# product from right pointers 
		right_product = A[j] * A[j - 1] 

		if (left_product > right_product) : 
			product *= left_product 
			i += 2
		
		else : 
			product *= right_product 
			j -= 2

	# Finally return product 
	return product 

# Driver Code 
if __name__ == "__main__": 
	
	n,k = map(int,input().split())
	l = list(map(int,input().split()))
	ans=1
	if n==k:
	    for i in l:
	        ans = ans*i
	    print(ans%1000000007)
	    exit()
	ans = maxProductSubarrayOfSizeK(l, n, k)
	ans = ans%1000000007
	print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()

plus = list(filter(lambda x:x>0, A))[::-1]
plus = np.log(plus,dtype="float128")/np.log(100000000,dtype="float128")

from itertools import accumulate
acc_plu = [0] +  list(accumulate(plus))
minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:-x,minu))
minu = np.log(minu,dtype="float128")/np.log(10000000,dtype="float128")
acc_min = [0] +  list(accumulate(minu))


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2

ans = 1
if cand == []:
    if flag:
        print(0)
        exit()
    cnt = 0
    #マイナス確定
    abss = sorted(list(map(lambda x :abs(x),A)))
    for x in abss:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    ans *= -1
    ans %= MOD
    print(ans)
else:
    cand = sorted(cand)[::-1]
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    ans = 1
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()

plus = list(filter(lambda x:x>0, A))[::-1]
plus = np.log10(plus,dtype="float128")
plus = np.log(plus,dtype="float128")/np.log10(1000,dtype="float128")

from itertools import accumulate
acc_plu = [0] +  list(accumulate(plus))
minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:-x,minu))
minu = np.log(minu,dtype="float128")/np.log10(1000,dtype="float128")
acc_min = [0] +  list(accumulate(minu))


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2

ans = 1
if cand == []:
    if flag:
        print(0)
        exit()
    cnt = 0
    #マイナス確定
    abss = sorted(list(map(lambda x :abs(x),A)))
    for x in abss:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    ans *= -1
    ans %= MOD
    print(ans)
else:
    cand = sorted(cand)[::-1]
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    ans = 1
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7
# s=正の数、t=負の数
s,t = [], []
for a in A:
  if a<0:
    t.append(a)
  else:
    s.append(a)

S = len(s)
T = len(t)
ok = False
if (S>0):
  if n==k:
    # すべての負の数をペアにできる
    ok = T%2==0
  else:
    # 負の数は考慮しない
    ok = True
else:
  # kが偶数個
  ok = (k%2==0)

ans = 1
if not ok:
  A.sort(key=lambda x: abs(x))
  for i in range(k):
    ans *= A[i]
else:
  s.sort()
  t.sort(reverse=True)
  if k%2==1:
    ans *= s.pop()

  p = []
  while len(s) >= 2:
    x = s.pop()
    x *= s.pop()
    p.append(x)

  while len(t) >= 2:
    x = t.pop()
    x *= t.pop()
    p.append(x)

  p.sort(reverse=True)
  for i in range(k//2):
    print(p[i])
    ans *= p[i]

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()

plus = list(filter(lambda x:x>0, A))[::-1]
plus = np.log10(plus,dtype="float128")

from itertools import accumulate
acc_plu = [0] +  list(accumulate(plus))
minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:-x,minu))
minu = np.log10(minu,dtype="float128")
acc_min = [0] +  list(accumulate(minu))


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2

ans = 1
if cand == []:
    if flag:
        print(0)
        exit()
    cnt = 0
    #マイナス確定
    abss = sorted(list(map(lambda x :abs(x),A)))
    for x in abss:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    ans *= -1
    ans %= MOD
    print(ans)
else:
    cand = sorted(cand)[::-1]
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    ans = 1
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

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

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if k == n:
    for x in a[:k]:
        ans = (ans * x) % mod
elif k > len(plus) + len(minus):
    ans = 0
elif n == len(plus):
    for x in plus[:k]:
        ans = (ans * x) % mod
elif n == len(minus):
    for x in minus[:k]:
        ans = (ans * x) % mod
    if n % 2 == 1:
        ans = (ans * -1) % mod
else:
    i, j = 0, 0
    while i + j < k:
        x_p = (plus[i] * plus[i + 1]) % mod if i < len(plus) - 1 else 1
        x_m = (minus[j] * minus[j + 1]) % mod if j < len(minus) - 1 else 1
        if x_p > x_m:
            ans = (ans * x_p) % mod
            i += 2
        else:
            ans = (ans * x_m) % mod
            j += 2
print(ans)

Submission status: Wrong Answer

Solution code:
M = int(1e9+7)
N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [i for i in A if i >= 0]
Am = [i for i in A if i < 0]
if K == N:
    ans = 1
    for i in A:
        ans = (ans * i) % M
    print(ans)
elif len(Ap)==0 and K%2==1:
    sA = sorted(A, reverse=True)
    ans = 1
    for i in range(K):
        ans = (ans * sA[i]) % M
    print(ans)
else:
    sAp = sorted(Ap, reverse=True)
    sAm = sorted(Am, reverse=False)
    if K%2==0:
        ans = 1
    else:
        ans = sAp[0]
        sAp = sAp[1:]

    sA2 = [(sAp[2*i]*sAp[2*i+1])%M for i in range(len(sAp)//2)]
    sA2.extend([(sAm[2*i]*sAm[2*i+1])%M for i in range(len(sAm)//2)])
    ssA2 = sorted(sA2, reverse=True)
    for i in range(K//2):
        ans = (ans * ssA2[i]) % M
    print(ans)

Submission status: Wrong Answer

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


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

n, k = LI()
A = LI()
flg = 1 if max(A) < 0 and k % 2 else 0
z_flg = 1 if 0 in A else 0
X = sorted(A, key=lambda x:abs(x), reverse=False if flg else True)
ans = 1
fflg = 0
t1 = INF
t2 = 0
t_minus = 0
t_plus = 0
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
        t2 = min(t2, X[i])
        t_minus = 1
    elif X[i] > 0:
        t1 = min(t1, X[i])
        t_plus = 1

if t1 == INF:
    t1 = 1

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

f_ans = -INF
if fflg:
    if rem_minus and t_plus:
        fflg = 0
        f_ans = max(f_ans, -ans * pow(t1, mod - 2, mod) * r2)
    if rem_plus and t_minus:
        fflg = 0
        f_ans = max(f_ans, -ans * pow(t2, mod - 2, mod) * r1)
else:
    f_ans = ans

if fflg:
    f_ans = 0 if z_flg else -ans
print(f_ans % mod)

Submission status: Wrong Answer

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

plus = []
minus = []
for i in a:
    if i > 0: plus.append(i)
    if i < 0: minus.append(i)

ans = 1
if k > len(plus) + len(minus):
    ans = 0
elif len(minus) == 0:
    plus.sort(reverse=True)
    for i in range(k):
        ans = (ans * plus[i]) % mod
elif len(plus) == 0:
    if k % 2 == 0:
        minus.sort()
        for i in range(k):
            ans = (ans * minus[i]) % mod
    else:
        minus.sort(reverse=True)
        for i in range(k):
            ans = (ans * minus[i]) % mod
elif k == len(plus) + len(minus) and (len(minus) % 2) == 1:
    if n != k:
        ans = 0
    else:
        for x in plus:
            ans = (ans * x) % mod
        for y in minus:
            ans = (ans * y) % mod
else:
    plus.sort(reverse=True)
    minus.sort()
    i, j = 0, 0
    if k % 2 == 1:
        ans = plus[0]
        i = 1
    while i + j < k:
        tmp_p = plus[i] * plus[i + 1] if i <= len(plus) - 2 else 1
        tmp_m = minus[j] * minus[j + 1] if j <= len(minus) - 2 else 1
        if tmp_p >= tmp_m:
            ans = (ans * (tmp_p % mod)) % mod
            i += 2
        else:
            ans = (ans * (tmp_m % mod)) % mod
            j += 2
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
all_minus = True
for i in range(n):
  if a[i] >= 0:
    all_minus = False
    break
if all_minus:
  a.sort(key = lambda x: abs(x))
  ans = 1
  for i in range(k):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()
if k == n:
  ans = 1
  for i in range(k):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()

a.sort(key = lambda x: abs(x))
a.reverse()
ans = 1
mcnt = 0
zcnt = 0
for i in range(n):
  if a[i] == 0:
    zcnt += 1
if zcnt > n - k:
  print(0)
  exit()
b = []
for i in range(n):
  if a[i] == 0:
    continue
  b.append(a[i])
m = len(b)
for i in range(k):
  ans *= b[i]
  ans %= mod
  if b[i] < 0:
    mcnt += 1
if mcnt % 2 == 0:
  print(ans)
  exit()
lp = 0
lpi = -1
lm = 0
lmi = -1
for i in reversed(range(k)):
  if b[i] > 0:
    lp = b[i]
    lpi = i
    break
for i in reversed(range(k)):
  if b[i] < 0:
    lm = b[i]
    lmi = i
    break
rm = 0
rmi = -1
rp = 0
rpi = -1
for i in range(k, m):
  if b[i] < 0:
    rm = b[i]
    rmi = i
    break
for i in range(k, m):
  if b[i] > 0:
    rp = b[i]
    rpi = i
    break
    
ex = False
if lpi < 0:
  temp = 1
  for i in range(k):
    if i == lmi:
      continue
    temp *= b[i]
    temp %= mod
  if rpi >= 0:
    temp *= rp
    temp %= mod
    ans = temp
    ex = True
  
  if not ex:
    if mcnt > 0:
      ans = 0
    else:
      b.sort(key = lambda x: abs(x))
      ans = 1
      for i in range(k):
        ans *= b[i]
        ans %= mod
else:
  exA = False
  exB = False
  
  tempA = 1
  for i in range(k):
    if i == lmi:
      continue
    tempA *= b[i]
    tempA %= mod
  if rpi >= 0:
    tempA *= rp
    tempA %= mod
    exA = True
  
  tempB = 1
  for i in range(k):
    if i == lpi:
      continue
    tempB *= b[i]
    tempB %= mod
  if rmi >= 0:
    tempB *= rm
    tempB %= mod
    exB = True
  
  ex = exA or exB
  if lp * rp > lm * rm and exA and exB:
    ans = tempA
  elif lp * rp <= lm * rm and exA and exB:
    ans = tempB
  elif exA:
    ans = tempA
  elif exB:
    ans = tempB
  else:
    if mcnt > 0:
      ans = 0
    else:
      b.sort(key = lambda x: abs(x))
      ans = 1
      for i in range(k):
        ans *= b[i]
        ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()

plus = list(filter(lambda x:x>0, A))[::-1]
plus = list(map(lambda x:np.longdouble(math.log(x,10000000)),plus))
from itertools import accumulate
acc_plu = [0] +  list(accumulate(plus))
minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:np.longdouble(math.log(-x,10000000)),minu))
acc_min = [0] +  list(accumulate(minu))


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2

ans = 1
print(cand)
if cand == []:
    if flag:
        print(0)
        exit()
    cnt = 0
    #マイナス確定
    abss = sorted(list(map(lambda x :abs(x),A)))
    for x in abss:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    ans *= -1
    ans %= MOD
    print(ans)
else:
    cand = sorted(cand)[::-1]
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    ans = 1
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()

plus = list(filter(lambda x:x>0, A))[::-1]
plus = list(map(lambda x:np.longdouble(math.log(x,10000000)),plus))
from itertools import accumulate
acc_plu = [0] +  list(accumulate(plus))
minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:np.longdouble(math.log(-x,10000000)),minu))
acc_min = [0] +  list(accumulate(minu))


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2

ans = 1
if cand == []:
    if flag:
        print(0)
        exit()
    cnt = 0
    #マイナス確定
    abss = list(map(lambda x :abs(x),A))
    for x in abss:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    ans *= -1
    ans %= MOD
    print(ans)
else:
    cand = sorted(cand)[::-1]
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    ans = 1
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int,input().split())
import math
A = list(map(int,input().split()))
flag = 0
if 0 in A:
    flag = 1
A.sort()

plus = list(filter(lambda x:x>0, A))[::-1]
plus = list(map(lambda x:np.longdouble(math.log(x,10000000)),plus))
from itertools import accumulate
acc_plu = [0] +  list(accumulate(plus))
minu = filter(lambda x:x<0, A)
minu = list(map(lambda x:np.longdouble(math.log(-x,10000000)),minu))
acc_min = [0] +  list(accumulate(minu))


if K % 2 == 0 : num = K // 2 + 1
else: num = (K + 1) // 2 
cand = []
x = K
y = 0
MOD = 10**9 +7
for i in range(num):
    try:
        cand.append((acc_plu[x] +  acc_min[y],x ,y ))
    except: pass
    x -= 2 
    y += 2

ans = 1
if cand == []:
    if flag:
        print(0)
        exit()
    cnt = 0
    minu = list(filter(lambda x:x<0, A))
    for x in minu[::-1]:
        if cnt == K:break
        ans *= x
        ans %= MOD
        cnt += 1
    print(ans)
else:
    cand = sorted(cand)[::-1]
    plus = list(filter(lambda x:x>0, A))[::-1]
    minu = list(filter(lambda x:x<0, A))
    c = cand[0]
    ans = 1
    for i in range(c[1]):
        ans *= plus[i]
        ans %= MOD
    for i in range(c[2]):
        ans *= minu[i]
        ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9 + 7

def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)

def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]

def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

def prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= abs(A[i])
        prod %= MOD
    if add != None:
        prod *= abs(A[add])
        prod %= MOD
    return prod

N, K = read_int_list()
A = read_int_list()

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

last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove_plus = None
add_plus = None
remove_minus = None
add_minus = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None and remove_minus == None:
            remove_minus = last_minus
            add_minus = i
            sig = 1
        elif A[i] < 0 and last_plus != None and remove_plus == None:
            remove_plus = last_plus
            add_plus = i
            sig = 1
        elif A[i] == 0:
            if sig < 0:
                sig = 0
            break

if sig == 0:
    print(0)
elif sig > 0:
    if remove_plus != None and remove_minus != None:
        if abs(A[remove_plus]/A[add_plus]) > abs(A[remove_minus]/A[add_minus]):
            ap = prod(A, K, add_minus, remove_minus)
        else:
            ap = prod(A, K, add_plus, remove_plus)
    elif remove_plus != None:
        ap = prod(A, K, add_plus, remove_plus)
    else:
        ap = prod(A, K, add_minus, remove_minus)
    print(ap)
else:
    ap = prod(A[::-1], K, None, None)
    print((MOD-ap) % MOD)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
all_minus = True
for i in range(n):
  if a[i] >= 0:
    all_minus = False
    break
if all_minus:
  a.sort(key = lambda x: abs(x))
  ans = 1
  for i in range(k):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()
if k == n:
  ans = 1
  for i in range(k):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()

a.sort(key = lambda x: abs(x))
a.reverse()
ans = 1
mcnt = 0
zcnt = 0
for i in range(n):
  if a[i] == 0:
    zcnt += 1
if zcnt > n - k:
  print(0)
  exit()
b = []
for i in range(n):
  if a[i] == 0:
    continue
  b.append(a[i])
m = len(b)
for i in range(k):
  ans *= b[i]
  ans %= mod
  if b[i] < 0:
    mcnt += 1
if mcnt % 2 == 0:
  print(ans)
  exit()
lp = 0
lpi = -1
lm = 0
lmi = -1
for i in reversed(range(k)):
  if b[i] > 0:
    lp = b[i]
    lpi = i
    break
for i in reversed(range(k)):
  if b[i] < 0:
    lm = b[i]
    lmi = i
    break
rm = 0
rp = 0
for i in range(k, m):
  if b[i] < 0:
    rm = b[i]
    rmi = i
    break
for i in range(k, m):
  if b[i] > 0:
    rp = b[i]
    rpi = i
    break
if lpi < 0:
  temp = 1
  for i in range(k):
    if i == lmi:
      continue
    temp *= b[i]
    temp %= mod
  temp *= rp
  temp %= mod
  ans = temp
else:
  tempA = 1
  for i in range(k):
    if i == lmi:
      continue
    tempA *= b[i]
    tempA %= mod
  tempA *= rp
  tempA %= mod
  
  tempB = 1
  for i in range(k):
    if i == lpi:
      continue
    tempB *= b[i]
    tempB %= mod
  tempB *= rm
  tempB %= mod
  
  if lp * rp > lm * rm:
    ans = tempA
  else:
    ans = tempB

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7


def mul_mod(x, y, mod):
    return x * y % mod


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: abs(x), reverse=True)

    res = 1

    if k == 1:
        res = max(a) % MOD
    elif k == n:
        res = 1
        for e in a:
            res *= e
            res %= MOD
    elif max(a) < 0:
        if k % 2 == 1:
            for i in range(n - k, n):
                res *= a[i]
                res %= MOD
        else:
            for i in range(k):
                res *= a[i]
                res %= MOD
    else:
        plus_a = [e for e in a if e >= 0]
        minus_a = [e for e in a if e < 0]

        minus_cnt = min(k, len(minus_a))
        minus_cnt -= minus_cnt % 2
        plus_cnt = k - minus_cnt

        minus_a = minus_a[:minus_cnt]
        minus_a.reverse()

        max_change_cnt = min(minus_cnt, len(plus_a) - plus_cnt)
        max_change_cnt -= max_change_cnt % 2
        change_cnt = 0
        while change_cnt < max_change_cnt:
            if plus_a[plus_cnt + change_cnt] * plus_a[plus_cnt + change_cnt + 1]\
                    <= minus_a[change_cnt] * minus_a[change_cnt + 1]:
                break
            change_cnt += 2

        for i in range(minus_cnt - change_cnt):
            res *= minus_a[i]
            res %= MOD

        for i in range(plus_cnt + change_cnt):
            res *= plus_a[i]
            res %= MOD

    print(res)


main()

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7


def mul_mod(x, y, mod):
    return x * y % mod


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: abs(x), reverse=True)

    res = 1

    if k == 1:
        res = max(a) % MOD
    elif k == n:
        res = 1
        for e in a:
            res *= e
            res %= MOD
    elif max(a) < 0:
        if k % 2 == 1:
            for i in range(n - k, n):
                res *= a[i]
                res %= MOD
        else:
            for i in range(k):
                res *= a[i]
                res %= MOD
    else:
        plus_a = [e for e in a if e >= 0]
        minus_a = [e for e in a if e < 0]

        minus_cnt = min(k, len(minus_a))
        minus_cnt -= minus_cnt % 2
        plus_cnt = k - minus_cnt

        minus_a = minus_a[:minus_cnt]
        minus_a.reverse()

        max_change_cnt = min(minus_cnt, len(plus_a) - plus_cnt)
        max_change_cnt -= max_change_cnt % 2
        change_cnt = 0
        while change_cnt < max_change_cnt:
            if plus_a[plus_cnt + change_cnt] * plus_a[plus_cnt + change_cnt + 1]\
                    <= minus_a[change_cnt] * minus_a[change_cnt + 1]:
                break
            change_cnt += 2

        for i in range(minus_cnt):
            res *= minus_a[i]
            res %= MOD

        for i in range(plus_cnt):
            res *= plus_a[i]
            res %= MOD

    print(res)


main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    A = LI()

    ans = 1
    ma = max(A)
    if ma <= 0 and K % 2:
        # 最大値が0以下でKが奇数の場合
        x = sorted(A,reverse=True)
        # 大きいほうからK個の積
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return

    # 絶対値でソート
    x = sorted(A, key=lambda x: abs(x), reverse=True)
    m = 0
    # 絶対値が大きいほうからK個の積
    for i in range(K):
        ans = (ans * x[i]) % MOD
        if x[i] < 0 :m += 1

    # K==Nか、マイナスが偶数ならそのままリターン
    if K == N or m % 2 == 0 or ans == 0:
        print(ans)
        return
    # K+1個目が0なら、0でリターン
    if x[K] == 0:
        print(0)
        return

    # K個目まですべてマイナスなら
    if m == K:
        # K番目とK+1以降の最大値とを入れ替え
        ans = (ans * pow(x[K-1],MOD-2,MOD) * max(x[K:])) % MOD

    else:
        K1 = -1
        # K+1番目と符号が反対で絶対値が最大の数をK+2番目以降で探す
        for i in range(K+1,N):
            if x[K] * x[i] < 0:
                K1 = i
                break

        f0 = 0.0
        f1 = 0.0
        i0 = -1
        i1 = -1
        # K番目以内でK+1番目と符号が反対で最小の数を探す
        for i in range(K-1,-1,-1):
            if x[i] * x[K] < 0:
                i0 = i
                # 入れ替えた時の減少率
                f0 = x[K] / x[i]
                break

        if K1 >= 0:
            # K1が存在するとき、K番目以内でK1番目と符号が反対で最小の数を探す
            for i in range(K-1,-1,-1):
                if x[i] * x[K1] < 0:
                    i1 = i
                    f1 = x[K1] / x[i]
                    break

        if abs(f0) >= abs(f1):
            ans = (ans * pow(x[i0],MOD-2,MOD) * x[K]) % MOD
        else:
            ans = (ans * pow(x[i1],MOD-2,MOD) * x[K1]) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
all_minus = True
for i in range(n):
  if a[i] >= 0:
    all_minus = False
    break
if all_minus:
  a.sort(key = lambda x: abs(x))
  ans = 1
  for i in range(k):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()
a.sort(key = lambda x: abs(x))
a.reverse()
ans = 1
mcnt = 0
zcnt = 0
for i in range(n):
  if a[i] == 0:
    zcnt += 1
if zcnt > n - k:
  print(0)
  exit()
b = []
for i in range(n):
  if a[i] == 0:
    continue
  b.append(a[i])
m = len(b)
for i in range(k):
  ans *= b[i]
  ans %= mod
  if b[i] < 0:
    mcnt += 1
if mcnt % 2 == 0:
  print(ans)
  exit()
lp = 0
lpi = -1
lm = 0
lmi = -1
for i in reversed(range(k)):
  if b[i] > 0:
    lp = b[i]
    lpi = i
    break
for i in reversed(range(k)):
  if b[i] < 0:
    lm = b[i]
    lmi = i
    break
rm = 0
rp = 0
for i in range(k, m):
  if b[i] < 0:
    rm = b[i]
    rmi = i
    break
for i in range(k, m):
  if b[i] > 0:
    rp = b[i]
    rpi = i
    break
if lpi < 0:
  temp = 1
  for i in range(k):
    if i == lmi:
      continue
    temp *= b[i]
    temp %= mod
  temp *= rp
  temp %= mod
  ans = temp
else:
  tempA = 1
  for i in range(k):
    if i == lmi:
      continue
    tempA *= b[i]
    tempA %= mod
  tempA *= rp
  tempA %= mod
  
  tempB = 1
  for i in range(k):
    if i == lpi:
      continue
    tempB *= b[i]
    tempB %= mod
  tempB *= rm
  tempB %= mod
  
  if lp * rp > lm * rm:
    ans = tempA
  else:
    ans = tempB

print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
all_minus = True
for i in range(n):
  if a[i] >= 0:
    all_minus = False
    break
if all_minus:
  a.sort(key = lambda x: abs(x))
  ans = 1
  for i in range(k):
    ans *= a[i]
    ans %= mod
  print(ans)
  exit()
a.sort(key = lambda x: abs(x))
a.reverse()
ans = 1
mcnt = 0
zcnt = 0
for i in range(n):
  if a[i] == 0:
    zcnt += 1
if zcnt > n - k:
  print(0)
  exit()
b = []
for i in range(n):
  if a[i] == 0:
    continue
  b.append(a[i])
m = len(b)
for i in range(k):
  ans *= b[i]
  ans %= mod
  if b[i] < 0:
    mcnt += 1
if mcnt % 2 == 0:
  print(ans)
  exit()
lp = 0
lpi = -1
lm = 0
lmi = -1
for i in reversed(range(k)):
  if b[i] > 0:
    lp = b[i]
    lpi = i
    break
for i in reversed(range(k)):
  if b[i] < 0:
    lm = b[i]
    lmi = i
    break
rm = 0
rp = 0
for i in range(k, m):
  if b[i] < 0:
    rm = b[i]
    rmi = i
    break
for i in range(k, m):
  if b[i] > 0:
    rp = b[i]
    rpi = i
    break
if lpi < 0:
  temp = 1
  for i in range(k):
    if i == lmi:
      continue
    temp *= b[i]
    temp %= mod
  temp *= rp
  temp %= mod
  ans = temp
else:
  tempA = 1
  for i in range(k):
    if i == lmi:
      continue
    tempA *= b[i]
    tempA %= mod
  tempA *= rp
  tempA %= mod
  
  tempB = 1
  for i in range(k):
    if i == lpi:
      continue
    tempB *= b[i]
    tempB %= mod
  tempB *= rm
  tempB %= mod
  
  if lp * rp > lm * rm:
    ans = tempA
  else:
    ans = tempB
if zcnt > 0:
  ans = max(0, ans) % mod
print(ans)