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:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

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

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

file=1


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] 
            product%=mod
        return product 
  
    i = 0
    j = n - 1
    if (k & 1): 
        product *= A[j] 
        product%=mod
        j-= 1
        k-=1
    k >>= 1
    for itr in range( k) : 
        left_product = A[i] * A[i + 1] 
        left_product%=mod
        right_product = A[j] * A[j - 1] 
        right_product%=mod
        if (left_product > right_product) : 
            product *= left_product 
            product%=mod
            i += 2
          
        else : 
            product *= right_product 
            product%=mod
            j -= 2 
    return product
def solve():
    
    # for _ in range(ii()):
    n,k=mi()
    a=li()
    print(maxProductSubarrayOfSizeK(a,n,k))

        
        




 









if __name__ =="__main__":

    if(file):

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

Submission status: Wrong Answer

Solution code:
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()]
    A.sort()
    mod = 7 + 10 ** 9

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= mod
        print(ans)
        return 0
    else:
        isPlus = False
        P, M = [], []
        for a in A:
            if a >= 0: 
                P.append(a)
                isPlus = True
            else: M.append(a)
        if not isPlus:
            ans = 1
            if K % 2 == 0:
                for i in range(K):
                    ans *= A[i]
                    ans %= mod
            else:
                for i in range(K):
                    ans *= A[N-i-1]
                    ans %= mod
            print(ans)
            return 0
        else:
            P.sort(reverse = True)
            M.sort()
            pp, mp = 0, 0
            q = []
            for i in range(len(P) // 2):
                heappush(q, (-P[i] * P[i+1], 1))
            for i in range(len(M) // 2):
                heappush(q, (-M[i] * M[i+1], -1))
            ans = 1
            for i in range(K // 2):
                a, pm = heappop(q)
                ans *= -a
                ans %= mod
                if pm == 1: pp += 1
            if K % 2 == 1:
                ans *= P[2 * pp]
                ans %= mod
            print(ans)
            return 0

   
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

a_plus = []
a_minus = []
cnt_0 = 0

for ai in a:
    if(ai==0):
        cnt_0 += 1
    elif(ai > 0):
        a_plus.append(ai)
    else:
        a_minus.append(ai)

a_plus.sort(reverse = True)
a_minus.sort()

cnt_p = len(a_plus)
cnt_m = len(a_minus)

if(cnt_p + cnt_m < k):
    print(0)
    exit()


if(cnt_m == n)&(k%2==1):
    ans = 1
    for i in range(k):
        ans *= a_minus[cnt_m - 1 - i]
        ans %= mod
    print(ans)
    exit()
elif(cnt_p == 0)&(k%2==1)&(cnt_0>0):
    print(0)
    exit()

p_ind = 0
m_ind = 0

ans = 1
if(k%2==1):
    ans = a_plus[0]
    p_ind = 1

for i in range(k//2):
    tmp_p = 0
    tmp_m = 0
    if(p_ind + 2 <= cnt_p ):
        tmp_p = a_plus[p_ind] * a_plus[p_ind+1]

    if(m_ind + 2 <= cnt_m ):
        tmp_m = a_minus[m_ind] * a_minus[m_ind+1]

    if(tmp_p > tmp_m):
        ans *= tmp_p
        p_ind += 2
    else:
        ans *= tmp_m
        m_ind += 2
    ans %= mod


ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0

tmp = k-pl
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3#mn
elif zr == 1 and pl == 0 and k % 2 == 1:
    hugo = 2#zr
else:
    hugo = 1#pl

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 1
                tmp_m_seki = 1
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            elif tmp == 1:
                tmp_seki = a[n-1-pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np

MOD = 10**9 + 7
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
ans = 1
plus = a[a >= 0]
plus = np.sort(plus)[::-1]
plus = np.append(plus, [-np.inf, np.inf])
minus = a[a < 0]
minus = np.sort(minus)
minus = np.append(minus, [np.inf, -np.inf])
if n == k:
    for i in range(len(a)):
        ans *= a[i]
        ans %= MOD
    print(ans)
    exit()
if len(plus) == 2 and k % 2 == 1:
    for i in range(3, k + 3):
        ans *= minus[-i]
        ans %= MOD
else:
    if k % 2 == 1:
        p = k // 2
        ans *= plus[0]
        cplus = 1
        cminus = 0
    else:
        p = k // 2
        cplus = 0
        cminus = 0
    for l in range(p):
        if plus[cplus] * plus[cplus + 1] > minus[cminus] * minus[cminus + 1]:
            ans *= plus[cplus] * plus[cplus + 1]
            ans %= MOD
            cplus += 2
        else:
            ans *= minus[cminus] * minus[cminus + 1]
            ans %= MOD
            cminus += 2
print(int(ans))

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = sorted(A, key=lambda x: abs(x), reverse=True)
    Bp = [x for x in B if x > 0]
    Bm = [x for x in B if x < 0]
    Bpm = [x for x in B if x != 0]
    Bmm = []
    for i in range(0, len(Bm)-1, 2):
        Bmm.append(Bm[i]*Bm[i+1])

    q = 10**9 + 7

    n_plus, n_zero, n_minus = 0, 0, 0
    for a in A:
        if a > 0:
            n_plus += 1
        elif a < 0:
            n_minus += 1
        else:
            n_zero += 1

    # if K > n_plus + n_minus:
    #     return 0

    # ans != 0
    rest = K
    ans = 1

    if K <= n_plus + n_minus and not (n_plus == 0 or (K == n_plus + n_minus and n_minus % 2 == 1)):
        # ans > 0
        i, j = 0, 0
        while rest > 0:
            if rest >= 2 and j < len(Bmm):
                if i+1 < len(Bp):
                    if Bmm[j] >= Bp[i] * Bp[i+1]:
                        ans = (ans * (Bmm[j] % q)) % q
                        j += 1
                        rest -= 2
                    else:
                        ans = (ans * Bp[i]) % q
                        i += 1
                        rest -= 1
                elif i < len(Bp):
                    if Bmm[j] >= Bp[i]:
                        ans = (ans * (Bmm[j] % q)) % q
                        j += 1
                        rest -= 2
                    else:
                        ans = (ans * Bp[i]) % q
                        i += 1
                        rest -= 1
                else:
                    ans = (ans * (Bmm[j] % q)) % q
                    j += 1
                    rest -= 2
            else:
                ans = (ans * Bp[i]) % q
                i += 1
                rest -= 1
        return ans
    elif n_zero > 0:
        return 0
    else:
        # ans < 0
        for i in range(K):
            ans = (ans * Bpm[len(Bpm)-1-i]) % q
        return ans

        # i = 0
        # ip = 0
        # im = 0
        # while rest > 0:
        #     if B[i] > 0:
        #         ans = (ans * B[i]) % q
        #         i += 1
        #         ip += 1
        #         rest -= 1
        #     else:  # B[i] < 0
        #         if rest == 1:
        #             i += 1
        #         elif B[i+1] < 0:  # rest >= 2
        #             ans = (ans * (B[i]*B[i+1] % q)) % q
        #             i += 2
        #             im += 2
        #             rest -= 2
        #         else:  # rest >= 2 and B[i+1] > 0
        #             if Bp[ip] * Bp[ip+1] > Bm[im] * Bm[im+1]:
        #                 ans = (ans * (Bp[ip]*Bp[ip+1] % q)) % q


print(main())

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lp,2):
			if i == lp-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	#data = []
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1
					else:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1

				else:
					count += 1
					#ans *= pra[cp]
					#data.append(pra[cp])
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1
					else:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1


				else:
					count += 1
					#ans *= mina[cm]
					#data.append(mina[cm])
					cm += 1
		elif cp != lp:
			#ans *= pra[cp]
			#data.append(pra[cp])
			cp -= 1
			count += 1
		elif cm != lm:
			#ans *= mina[cm]
			#data.append(mina[cm])
			cm += 1
			count += 1

		else:
			break
	if cm % 2 != 0:
		if cp == 0:
			cp += 1
			cm += 1

		else:
			cp -= 1
			cm += 1
			if cp-1 != -1 and cm + 1 != lm:
				if pra[cp] != 0 and pra[cp-1]/-mina[cm] <= -mina[cm+1]/pra[cp]:
					cp -= 1
					cm -= 1
				else:
					cp += 1
					cm += 1
			elif cp-1 != -1:
				cp -= 1
				cm -= 1
			else:
				cp += 1
				cm += 1
			cp += 1
			cm -= 1
		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod


		
	print(ans)

Submission status: Wrong Answer

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


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

    neg = 0

    cnt = 0
    ret = 1

    n_neg = bisect_left(A, 0)

    if n_neg == n and k % 2:
        for a in sorted(A, key=lambda x: abs(x)):
            if a != 0:
                ret = (a*ret) % mod
                cnt += 1

            if k <= cnt:
                break
    else:
        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

    if cnt < k:
        ret = 0

    return str(ret)


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

Submission status: Wrong Answer

Solution code:
import sys

def L(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())

def anser(prod):
    print(prod%(10**9+7))
    exit()

def solver(N,K,A):
    #print(A)
    all_minus = False
    minus_count = sum( [1 if i<=0 else 0 for i in A] )
    if minus_count == len(A):
        _sort = sorted(A,reverse=True)
        all_minus = True
    else:
        _sort = sorted(A, key=lambda x: abs(x),reverse=True)

    print(_sort)

    prod = 1
    last_idx = -1
    stack = []
    for i in range(K):
        #stack.append(_sort[i])
        prod *= _sort[i]
        last_idx = i

    if prod >= 0 or all_minus:
        anser(prod)

    else:
        print("last_idx=",last_idx)
        #print(stack, prod)
        bef_prod = prod

        mod_idx = -1
        for i in range(last_idx, -1, -1):
            print(i)
            if _sort[i] < 0:
                mod_idx = i
                break

        if mod_idx==-1:
            anser(prod)

        #zprint("mod_idx=",mod_idx)
        for i in range(mod_idx+1, N):
            #print("_sort[i]=",_sort[i])
            if _sort[i] > 0:
                #print("prod=",prod,"mod_idx=",mod_idx,"_sort[i]=",_sort[i])
                prod = prod // _sort[mod_idx] * _sort[i]

                if prod >= 0:
                    anser(prod)

        anser(bef_prod)


def main():

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

    solver(N,K,A)

if __name__ == '__main__':
    main()

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, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_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

N, K = MAP()

A = LIST()

plus0 = []
minus = []
zero = []

for a in A:
    if a >= 0:
        plus0.append(a)
    if a == 0:
        zero.append(a)
    if a < 0:
        minus.append(a)

# print(plus0)
# print(minus)
# print(zero)

if (len(minus) == N and K%2 == 1) or (plus0 and minus and N == K and len(minus)%2 == 1):
    # 答えはマイナスなので最小化を目指す
    if (len(minus) == N and K%2 == 1):
        minus.sort(reverse=True)  # 小さい方からKこ
        ans = 1
        for i in range(K):
            ans *= minus[i]
            ans %= mod
    else:
        ans = 1
        for x in minus+plus0:
            ans *= x
            ans %= mod
    print(ans)
else:
    if len(plus0) == N:
        ans = 1
        plus0.sort(reverse=True)
        for i in range(K):
            ans *= plus0[i]
            ans %= mod
        print(ans)
        exit()

    # 答えは0以上なので最大化を目指す
    ans = 0
    cnt = 0
    plus0.sort(reverse=True)
    minus.sort()
    minus = [-x for x in minus]
    modmul = lambda x, y:x*y%mod
    plus0 = [1]+list(accumulate(plus0, modmul))
    minus = [1]+list(accumulate(minus, modmul))
    # print(plus0)
    # print(minus)
    s_m = 2*((len(minus)-1)//2)
    s_p = K-s_m
    while 1:
        if s_m < 0:
            break
        # print(s_m, s_p)
        try:
            ans = max(ans, (plus0[s_p]*minus[s_m])%mod)
            s_m -= 2
            s_p += 2
        except:
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
# N = int(input())
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
A_p = []
A_n = []
for a in A:
  if a >= 0:
    A_p.append(a)
  else:
    A_n.append(-a)

A_p.sort(reverse=True)
A_n.sort(reverse=True)
A_p = deque(A_p)
A_n = deque(A_n)

p_top = 0
n_top = 0
ans_p = deque([])
ans_n = deque([])
for i in range(K):
  if len(A_p) == 0:
    ans_n.append(A_n.popleft())
  elif len(A_n) == 0:
    ans_p.append(A_p.popleft())
  elif A_p[0] >= A_n[0]:
    ans_p.append(A_p.popleft())
  else:
    ans_n.append(A_n.popleft())
if len(ans_n) % 2 == 1:
  if len(ans_p) == 0 and len(A_p) > 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_n) == 0 and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
  elif len(ans_p) > 0 and len(ans_n) > 0 and ans_p[-1] >= ans_n[-1] and len(A_p) > 0 and A_p[0] != 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_p) > 0 and len(ans_n) > 0 and ans_p[-1] < ans_n[-1] and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
ans = 1
for a in ans_p:
  ans = (a * ans) % MOD
for a in ans_n:
  ans = (a * ans) % MOD
if ans != 0 and len(ans_n) % 2 == 1:
  ans = 1
  A_abs = [abs(a) for a in A]
  A_abs.sort()
  for i in range(K):
    ans = (ans * A_abs[i]) % MOD
  ans = (-ans) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

import math
import itertools
import random
n, k = map(int, input().split())
a = list(map(int, input().split()))
maximum=-9999999999999999999999999
for i in list(itertools.combinations(a, k)):
    tmp=1
    for e in list(i):
        tmp *= e
    maximum = max(maximum, tmp)
print(maximum%(10**9+7))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lp,2):
			if i == lp-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	#data = []
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1
					else:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1

				else:
					count += 1
					#ans *= pra[cp]
					#data.append(pra[cp])
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1
					else:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1


				else:
					count += 1
					#ans *= mina[cm]
					#data.append(mina[cm])
					cm += 1
		elif cp != lp:
			#ans *= pra[cp]
			#data.append(pra[cp])
			cp -= 1
			count += 1
		elif cm != lm:
			#ans *= mina[cm]
			#data.append(mina[cm])
			cm += 1
			count += 1

		else:
			break
	if cm % 2 != 0:
		if cp == 0:
			cp += 1
			cm += 1

		else:
			if cp-1 != -1 and cm + 1 != lm:
				if pra[cp] != 0 and pra[cp-1]/-mina[cm] <= -mina[cm+1]/pra[cp]:
					cp -= 1
					cm -= 1
				else:
					cp += 1
					cm += 1
			elif cp-1 != -1:
				cp -= 1
				cm -= 1
			else:
				cp += 1
				cm += 1
		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		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
a.sort()
mi = []
pl = []
zero = 0
for i in a:
    if i < 0:
        mi.append(i)
    elif i == 0:
        zero += 1
    else:
        pl.append(i)
pl = pl[::-1]
if n-zero < k:
    print(0)
    exit()
if mi == []:
    ans = 1
    count = 0
    while count < k:
        ans *= a[-1-count]
        ans %= mod
        count += 1
    print(ans)
    
    exit()
if pl == []:
    if k%2:
        if zero:
            print(0)
        else:
            ans = 1
            count = 0
            while count < k:
                ans *= a[-1-count]
                ans %= mod
                count += 1
            print(ans)
            
    else:
        ans = 1
        count = 0
        while count < k:
            ans *= a[count]
            ans %= mod
            count += 1
        print(ans)
        
    exit()

ans = 0
ip = 0
im = 0
if k%2:
    count = pl[0]
    k -= 1
    ip += 1
else:
    count = 1
while k > 0:
    check1 = True
    check2 = True
    if ip+2 <= len(pl):
        x = pl[ip]*pl[ip+1]
        
    else:
        x = 1
        check1 = False
    if im+2 <= len(mi):
        y = mi[im]*mi[im+1]
    else:
        y = 1
        check2 = False
    if x >= y:
        if check1:
            ip += 2
        count = (x*count)%mod
    else:
        if check2:
            im += 2
        count = (y*count)%mod
    if check1 == False and check2 == False:
        break
    k -= 2
if k:
    if zero:
        print(0)
    else:
        count *= (pl[ip]*mi[ip])%mod
        print(count%mod)
else:
    print(count%mod)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

pl = []
mn = []
zr = []

tmp = 1
cnt = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)

ans = 0

if len(mn) >= k and k % 2:
    tmp = 1
    for i in range(1, k+1):
        tmp *= mn[-i]
        tmp %= mod
    ans = -tmp

if len(pl) == 0 and len(mn) >= k:
    tmp = 1
    if k % 2:
        for i in range(1, k+1):
            tmp *= mn[-i]
            tmp %= mod
        tmp = -tmp
    else:
        for i in range(k):
            tmp *= mn[i]
            tmp %= mod
    ans = tmp
    if len(zr) > 0:
        print(0)
    else:
        print(ans % mod)
    exit()

if len(zr) > 0:
    ans = max(0, ans)

pl_cum = [1]
for i, x in enumerate(pl):
    pl_cum.append(pl_cum[-1]*x % mod)

mn_cum = [1]
for i, x in enumerate(mn):
    mn_cum.append(mn_cum[-1]*x % mod)


for p in range(0, k+1, 2):
    if len(mn) < p:
        break
    first = False
    if len(pl) >= k-p:
        first = True
        pl_ind = k-p
        mn_ind = p
        break

if not first:
    print(ans % mod)
    exit()

while pl_ind-2 > -1 and mn_ind+1 < len(mn):
    if pl[pl_ind-1]*pl[pl_ind-2] <= mn[mn_ind]*mn[mn_ind+1]:
        pl_ind -= 2
        mn_ind += 2
    else:
        break

if pl_ind < 0:
    ans = mn_cum[mn_ind]
else:
    ans = pl_cum[pl_ind]*mn_cum[mn_ind]

print(ans % mod)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
N = [0]*n
for i in range(len(a)):
    if a[i] >= 0:
        N[i] = [a[i], 1]
    else:
        N[i] = [a[i], -1]

A = []
B = []
C = []

for i in N:
    if i[0] >= 0:
        B.append(i)
    else:
        C.append(i)
    A.append([abs(i[0]), i[1]])
    
A = sorted(A, reverse=True, key=lambda x: x[0])
B = sorted(B, reverse=True, key=lambda x: x[0])
C = sorted(C, key=lambda x: x[0])

ans = 1
s = 1
for i in range(k):
    s *= A[i][1]
if s == 1:
    for i in range(k):
        if ans*A[i][0] > 1000000007:
            ans = (ans*A[i][0])%1000000007
        else:
            ans *= A[i][0]
    print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2000)

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

mod = 10**9 + 7

als = []
test = True
for i in an:
    if i > 0:
        test = False
    als.append([abs(i), i])

#全部負かつkが奇数の時
if test and k % 2 == 1:
    an.sort(reverse=True)
    ans = 1
    for i in range(k):
        ans = ans * an[i] % mod
    print(ans)
    exit()

#絶対値の最大値を計算
als.sort(reverse=True)

ans = 1
min_p = 10**9 + 1
min_m = - 10**9 + 1
cnt = 0
for i in range(k):
    x, y = als[i]
    ans = ans * x % mod
    if y > 0:
        min_p = x
    if y < 0:
        min_m = x
        cnt += 1

#もし答えが正なら、そのまま出力
if cnt % 2 == 0:
    print(ans)
    exit()

#もし答えが負なら、k以降のalsから絶対値が最も大きい正の要素と負の要素を取り出してくる
max_p = 0
max_m = 0
for j in range(k, n):
    if als[j][1] > 0:
        max_p = max(max_p, als[j][0])
    if als[j][1] < 0:
        max_m = max(max_m, als[j][0])
    if max_p != 0 and max_m != 0:
        break

#逆元用
def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y/2)**2 * x % mod

#ansをプラスで割ってマイナスをかけるか、マイナスで割ってプラスをかけるかどちらか大きいかで場合わけ
if max_m == 0 or max_p / min_m >= max_m / min_p:
    print(ans * max_p * power(min_m, mod-2) % mod)
else:
    print(ans * max_m * power(min_p, mod-2) % mod)