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:
from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    MOD=10**9+7
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    Q=[]
    q=[]
    flag=True
    minus=0
    plus=0
    for i in range(n):
        if A[i]<0:
            minus+=1
        elif A[i]>0:
            plus+=1

    if plus>=k:
        pass
    else:
        num=k-plus
        if num%2==0 and minus//2>=num:
            pass
        else:
            flag=False

    if flag:
        for i in A:
            if i>0:
                heappush(Q,-i)
            else:
                heappush(q,i)
        

        while len(q)>=1:
            pv=heappop(q)
            heappush(Q,pv)
        ans=1
        for i in range(k):
            pv=-heappop(Q)
            ans=(ans*pv)%MOD

    else:
        for i in A:
            if i>0:
                heappush(Q,i)
            else:
                heappush(q,i)
        

        while len(q)>=1:
            pv=heappop(q)
            heappush(Q,-pv)
        ans=1
        for i in range(k):
            pv=heappop(Q)
            ans=(ans*pv)%MOD
        ans=-ans
        


    
    print(ans%MOD)
    
resolve()

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort(key=lambda x: abs(x),reverse=True)
mod = 10**9+7
sign = 1
last_nega = -1
last_posi = -1

if N == 1:
    print(A[0]%mod)
else:
    if K == 1:
        print(max(A)%mod)
        exit()

    if all([a<0 for a in A]) and K%2:
        ans = 1
        for i in range(1,K+1):
            ans *= abs(A[-i])
            ans %= mod
        print(-ans%mod)
    else:
        for i in range(K):
            if A[i] < 0:
                last_nega = i
            elif 0 < A[i]:
                last_posi = i
            sign *= (1 if 0 < A[i] else (-1 if A[i] < 0 else 0))
        if sign == 0:
            print(0)
            exit()

        if 0 < sign:
            ans = 1
            for i in range(K):
                ans *= abs(A[i])
                ans %= mod
            print(ans)
        else:
            ans = 1
            for i in range(K):
                ans *= abs(A[i])
                ans %= mod
            if N == K:
                print(-ans%mod)
                exit()

            ans1 = -float('inf')
            ans2 = -float('inf')

            #Aが正負を一つずつもつならどっかに引っかかる(と思う)
            if last_nega != -1:
                ans1 = -ans*pow(abs(A[last_nega]),mod-2,mod)
                ans1 %= mod
                for i in range(K,N):
                    if 0 <= A[i]:
                        ans1 *= A[i]
                        ans1 %= mod
                        break
                else:
                    ans1 = -float('inf')
            if last_posi != -1:
                ans2 = -ans*pow(abs(A[last_posi]),mod-2,mod)
                ans2 %= mod
                for i in range(K,N):
                    if A[i] <= 0:
                        ans2 *= abs(A[i])
                        ans2 %= mod
                        break
                else:
                    ans2 = -float('inf')
            ans = max(ans1,ans2)
            print(ans%mod)

Submission status: Wrong Answer

Solution code:
def maxProductSubarrayOfSizeK(A, n, k):
    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%(10**9+7)

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

    k >>= 1
    for itr in range(k):
        left_product = A[i] * A[i + 1]
        right_product = A[j] * A[j - 1]
        if (left_product > right_product):
            product *= left_product
            i += 2

        else:
            product *= right_product
            j -= 2
    return product%(10**9+7)
if __name__ == "__main__":
    n,k=map(int,input().split())
    A = [int(x) for x in input().split()]
    print(maxProductSubarrayOfSizeK(A, n, k)%(10**9+7))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

mod=(10**9+7)
p=1
t=0
if k<n:
    for i in range(k//2):
        if A[k-2*i]*A[k-2*i-1]<A[-2*i-1]*A[-2*i-2]:
            t+=1


for i in range(k-2*t):
    p=p*A[i]%mod
for i in range(2*t):
    p=p*A[-i-1]%mod


print(p)

Submission status: Wrong Answer

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


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

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, K = mulinputs()
    datas = list(mulinputs())
    mc = len(list(filter(lambda x: x < 0, datas)))
    pc = len(list(filter(lambda x: x > 0, datas)))
    zc = len(list(filter(lambda x: x == 0, datas)))

    if N - zc < K:
        print(0)
        exit()

    ans = ModInt(1)
    if pc == N:
        datas.sort(reverse=True)
        for n in datas[0:K]:
            ans *= ModInt(n)
    elif mc == N:
        datas = list(filter(lambda x: x != 0, datas))
        datas.sort(reverse=True)
        for n in datas[0:K]:
            ans *= ModInt(n)
    else:
        parr = list(filter(lambda x: x > 0, datas))
        marr = list(filter(lambda x: x < 0, datas))
        parr.sort(reverse=True)
        marr.sort(reverse=True)
        marr2 = []
        for i in range(int(len(marr)//2)):
            l, r = marr[i*2], marr[i*2+1]
            marr2.append((l*r, l, r))
        idx, pidx, midx = 0, 0, 0
        while idx < K:
            if pidx < len(parr) and midx < len(marr2):
                if parr[pidx] >= marr2[midx][0]:
                    ans *= ModInt(parr[pidx])
                    pidx += 1
                    idx += 1
                # else parr[pidx] < marr2[midx][0]:
                else:
                    ans *= marr2[midx][0]
                    midx += 1
                    idx += 2
            else:
                if pidx < len(parr):
                    ans *= ModInt(parr[pidx])
                    pidx += 1
                    idx += 1
                else:
                    ans *= marr2[midx][0]
                    midx += 1
                    idx += 2

    # 出力
    print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

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

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

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

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


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

if len(p) == 0 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:
    d = p.pop(-1)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
print(p, m)
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], d)) % MOD


if ans > MOD:
    ans -= MOD
if ans < 0:
    1/0
print(ans)

Submission status: Wrong Answer

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

#solve
def solve():
    n, k = LI()
    a = LI()
    if n == k:
        ans = a[0]
        for i in a[1:]:
            ans *= i
            ans %= mod
        print(ans)
        return
    mi = []
    ma = []
    a.sort()
    for ai in a:
        if ai <= 0:
            heappush(mi, ai)
        else:
            heappush(ma, (-ai,1))
    X = []
    if not ma:
        ans = 1
        if k & 1:
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
        else:
            for i in range(k):
                ans *= a[i]
                ans %= mod
        print(ans)
        return
    ans = 1
    while len(mi) >= 2:
        xx1 = heappop(mi)
        xy1 = heappop(mi)
        heappush(ma, (-xx1 * xy1, 2))
    t = 0
    LL = 0
    while t < k and ma:
        tmp, xx = heappop(ma)
        if xx == 1:
            LL = tmp
        if t + xx > k:
            while t < k and ma:
                tmp1, xx = heappop(ma)
                if xx == 1:
                    if tmp1 * LL >= tmp:
                        ans *= tmp1
                        ans %= mod
                        print(ans)
                        return
                    else:
                        ans *= pow(LL, mod - 2, mod)
                        ans *= tmp
                        ans %= mod
                        print(ans)
                        return
        ans *= -tmp
        t += xx
        ans %= mod

    print(ans)
    return


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

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a = sorted(a)
mod = 1000000007

if n == k:
    prod = 1
    for b in a:
        prod *= b
        prod %= mod
    print(prod)
    exit()

# negative prod
if k & 1 and a[-1] < 0:
    prod = 1
    for i in range(k):
        prod *= a[-1 - i]
        prod %= mod
    print(prod)
    exit()

A = []
for b in a:
    if b < 0:
        A.append((-b, True))
    else:
        A.append((b, False))
A = sorted(A)[::-1]

ans = 1
is_neg = False
last_neg = 1
last_nneg = -1

for i in range(k + 1):
    (b, neg) = A[i]
    if neg:
        ans *= -b
    else:
        ans *= b
    ans %= mod
    is_neg ^= neg
    if b == 0:
        is_neg = False
    if i == k - 1:
        if not is_neg:
            print(ans)
            exit()
    if i <= k - 1:
        if neg:
            last_neg = -b
        else:
            last_nneg = b
    if i == k:
        if is_neg:
            assert last_neg != 1
            ans *= pow(last_neg, mod - 2, mod)
        else:
            if last_nneg != -1:
                ans *= pow(last_nneg, mod - 2, mod)
            else:
                ans *= pow(last_neg, mod - 2, mod)
                ans *= pow(-b, mod - 2, mod)
                for j in range(k + 1, n):
                    if not A[j][1]:
                        ans *= A[j][0]
                        break
        ans %= mod
        print(ans)
        exit()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	B = []
	for i in range(N):
		val = abs(A[i])
		if A[i] > 0:
			B.append([val , 1])
		elif A[i] < 0:
			B.append([val, -1])
		else:
			B.append([val, 0])
	B = sorted(B)

	M = 0; p = 0; m = 0; Aplus = []; Aminus = []; zerocnt = 0
	for i in A:
		if i == 0:
			zerocnt += 1
		elif i > 0:
			Aplus.append(i)
			M += 1; p += 1
		else:
			Aminus.append(i)
			M += 1; m += 1
	Aplus.sort()
	Aminus.sort()

	# 0が絶対に入る場合
	if K > M:
		print(0)
		return
	# マイナスになるから絶対ゼロを入れる場合
	if zerocnt > 0 and M == m and K % 2 == 1:
		print(0)
		return
	# マイナスのみの時の処理
	if m == N:
		if K % 2 == 0:
			ans = 1
			for i in range(K):
				ans *= Aminus[i]
				ans %= con
			print(ans)
			return
		else:
			ans = 1
			for i in range(K):
				ans *= Aminus[-1 - i]
				ans %= con
			print(ans)
			return

	# マイナスと0のとき
	if m == M:
		if K % 2 == 0:
			ans = 1
			for i in range(K):
				ans *= Aminus[i]
				ans %= con
			print(ans)
			return
		else:
			print(0)
			return

	pindPre = -100; pindAfter = INF
	mindPre = -100;	mindAfter = INF
	# print(B)

	for i in range(N - K):
		if B[i][1] == 1:
			pindPre = i
		elif B[i][1] == -1:
			mindPre = i

	for i in range(N - 1, N - K - 1, -1):
		if B[i][1] == 1:
			pindAfter = i
		elif B[i][1] == -1:
			mindAfter = i

	cnt = 0
	ans = 1
	for i in range(K):
		ans *= B[-1 - i][0]
		ans %= con
		if B[-1 - i][1] == -1:
			cnt += 1

	if cnt % 2 == 0:
		print(ans)
		return
	else:
		ans *= -1
		ans % con
		if mindPre >= 0 and pindPre >= 0 and pindAfter <= N and mindAfter <= N:		
			if B[mindPre][0] * B[mindAfter][0] <= B[pindPre][0] * B[pindAfter][0]:
				ans *= B[pindPre][0] * pow(B[pindAfter][0], con - 2, con)
				ans %= con
			else:
				ans *= B[mindPre][0] * pow(B[mindAfter][0], con - 2, con)
				ans %= con

			print(ans)
			return

		elif pindPre >= 0 and pindAfter <= N:
			ans *= B[pindPre][0] * pow(B[pindAfter][0], con - 2, con)
			ans %= con
			print(ans)
			return
		else:
			ans *= B[mindPre][0] * pow(B[mindAfter][0], con - 2, con)
			ans %= con
			print(ans)
			return


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	A.sort()
	A = A[::-1]

	ans = 1
	for i in range(K):
		ans = (ans * A[i]) % mod

	if ans < 0:
		ans = A[-1] * A[-2]
		for i in range(K-2):
			ans = (ans * A[i]) % mod

	if abs(A[K-1]) < abs(A[-1]) and abs(A[K-2]) < abs(A[-2]):
		ans = A[-1] * A[-2]
		for i in range(K-2):
			ans = (ans * A[i]) % mod

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
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)
minus = sum(a <= 0 for a in A)
if N - K < A.count(0):
    print(0)
    exit()
if N == minus:
    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:
#!python3

import numpy as np

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
A = np.array(LI())

MOD = 10 ** 9 + 7


def main():
    if np.count_nonzero(A == 0) > N - K:
        print(0)
        return
    ans = 1
    m = A[A < 0] * -1
    p = A[A > 0]
    m = np.sort(m)[::-1]
    p = np.sort(p)[::-1]
    mn = len(m)
    pn = len(p)
    i, j = 0, 0
    for _ in range(K):
        if i >= mn:
            j += 1
            continue
        if j >= pn:
            i += 1
            continue
        if m[i] < p[j]:
            j += 1
        else:
            i += 1
    if i % 2 == 1:
        if i < mn - 1 and j > 0:
            if j < pn - 1:
                x = m[i] * m[i + 1]
                y = p[j] * p[j + 1]
                if x < y:
                    i -= 1
                    j += 1
                else:
                    i += 1
                    j -= 1
            else:
                i += 1
                j -= 1
        elif j < pn - 1:
            i -= 1
            j += 1
    if i % 2 == 0:
        ans = 1
        for x in m[:i]:
            ans = ans * x % MOD
        for x in p[:j]:
            ans = ans * x % MOD
    else:
        ans = -1
        for x in m[mn - i:]:
            ans = ans * x % MOD
        for x in p[pn - j:]:
            ans = ans * x % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

mod = 10 ** 9 + 7
n, k = map(int, input().split())
A = list(map(int, input().split()))
# dp = [[[0] * (2) for _ in range(k+1)]for _ in range(n+1)]
# # dp[桁][数][負数の数=1,0]

A.sort()
n_minus = bisect_left(A, 0)
n_zero = bisect_right(A, 0) - n_minus
n_plus = n - n_minus - n_zero

possible_max = min(k, n_minus)
possible_min = max(k - (n_plus + n_zero), 0)
ans = 1
if possible_max == possible_min and possible_min % 2 == 1:
    if k - (possible_min) > 0 and n_zero > 0:
        print(0)
        exit()
    A_plus = A[n - (n_plus) :]
    A_minus = A[:n_minus]
    A_minus.sort(reverse=True)
    # 負の数は奇数個小さい方から選ぶ
    for i in range(possible_min):
        ans *= A_minus[i]
        ans %= mod
    for i in range(k - possible_min):
        ans *= A_plus[i]
        ans %= mod
else:
    # 正の数に成る→大きいものがほしい
    # 負の数は偶数個、これの数を決め打つ
    # 計算すると大変だから大小を考える

    A_plus = A[n - (n_plus) :]
    A_plus.sort(reverse=True)
    A_minus = A[:n_minus]

    # 負の数を使う数を決め打つ
    # 最終的に正にできるパターン
    minus_num_max = min(n_minus // 2, k // 2)
    select = k - 2 * minus_num_max
    if n_plus < select:
        print(0)
        exit()
    # 負の数にしかできないパターン
    # 遊びがない時に奇数個の負の数を選ばざるを得ない
    # その時に0があるかどうかパターン
    kouho = []
    for i in range(minus_num_max):
        if 2 * i + 1 >= n_minus:
            break
        temp = A_minus[2 * i] * A_minus[2 * i + 1]
        kouho.append((temp, -1))
    for i in range(n_plus // 2):
        temp = A_plus[2 * i] * A_plus[2 * i + 1]
        kouho.append((temp, +1))
    kouho.sort(reverse=True)
    if k % 2 == 0:
        for i in range(k // 2):
            ans *= kouho[i][0]
            ans %= mod
    # else:
    #     cnt = 0
    #     i = 0
    #     for i in range(k // 2):
    #         num, f = kouho[i]
    #         if f == 1:
    #             cnt += 1
    #         ans *= num
    #         ans %= mod
    #     ans *= A_plus[2 * cnt]
    #     ans %= mod


print(ans % mod)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True,key=abs)
    dif= 10**9+7
    ans = 1
    count = 0
    mcount = 0
    for i in a:
        if i < 0:
            if  count < n-1:
                temp = i% dif
                if i < temp:
                    ans = ans*i
                else:
                    ans =ans*temp
                count+=1
                mcount+=1
            elif count == n-1 and mcount %2 ==1:
                temp = i% dif
                if i < temp:
                    ans = ans*i
                else:
                    ans =ans*temp
                count+=1
                mcount+=1

        else:
            temp = i% dif
            if i < temp:
                ans = ans * i
            else:
                ans = ans * temp
            count+=1
        if count ==k:
            break
    if ans < dif and ans >-1:
        print(ans)
    else:
        print(ans %dif)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
ans = 1
if len([v for v in A if v <= 0]) == N:
    for i in range(K):
        ans *= A[-(i + 1)]
        if abs(ans) > mod:
            ans %= mod
else:
    num_hu = len([v for v in A[:K] if v < 0])
    if num_hu % 2 == 0:
        for i in range(K):
            ans *= A[i]
            if abs(ans) > mod:
                ans %= mod
    else:
        if A[K - 1] < 0:
            if len([v for v in A[K:] if v > 0]):
                idx = K
                while True:
                    if A[idx] > 0:
                        break
                    idx += 1
                for i in range(K - 1):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[idx]
            elif len([v for v in A[K:] if v < 0]):
                idx = K - 2
                while True:
                    if A[idx] > 0:
                        break
                    idx -= 1
                for i in range(idx):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[K]
                for i in range(idx + 1, K):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
            else:
                for i in range(K):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
        else:
            if len([v for v in A[K:] if v < 0]):
                idx = K
                while True:
                    if A[idx] < 0:
                        break
                    idx += 1
                for i in range(K - 1):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[idx]
            elif len([v for v in A[K:] if v > 0]):
                idx = K - 2
                while True:
                    if A[idx] < 0:
                        break
                    idx -= 1
                for i in range(idx):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[K]
                for i in range(idx + 1, K):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
            else:
                for i in range(K):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
print(ans % mod)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = sorted(map(int,input().split()))
mod = 10**9 + 7
H = K % 2
if N != K:
    if H == 0:
        S = []
        for i in range (N//2):
            S.append(A[i*2]*A[i*2+1])
        T = sorted(S,reverse = True)
        Ans = 1
        for j in range (K//2):
            Ans *= T[j]
        print(Ans % mod)
    else:
        if A[-1]>=0:
            S = []
            for i in range (N//2):
                S.append(A[i*2]*A[i*2+1])
            T = sorted(S,reverse = True)
            Ans = A[-1]
            for j in range (K//2):
                Ans *= T[j]
            print(Ans % mod)
        else:
            Ans = 1
            for j in range (K):
                Ans *= A[-(j+1)]
            print(Ans % mod)