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:
#!/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
    else:
        zero += 1

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


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

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

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    from collections import Counter
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    posi = [a for a in A if a > 0]
    nega = [a for a in A if a < 0]
    posi.sort(reverse=True)
    nega.sort(reverse=True)
    A.sort(reverse=True, key=abs)
    if len(posi) + len(nega) < K:
        # 0を含まなければいけないとき
        return print(0)

    ans = modint(1)
    ans1 = []  # 正を取り除く
    ans2 = []  # 負を取り除く
    posi = [a for a in A[:K] if a > 0]
    nega = [a for a in A[:K] if a < 0]
    p_remove = False
    for a in A[:K][::-1]:
        if a > 0 and not p_remove:
            p_remove = True
            continue
        ans1.append(a)
    n_remove = False
    for a in A[:K][::-1]:
        if a < 0 and not n_remove:
            n_remove = True
            continue
        ans2.append(a)
    mul1 = 0  # 一番大きい正
    mul2 = 0  # 　一番大きい負
    for a in A[K:]:
        if mul1 == 0 and a > 0:
            mul1 = a
        if mul2 == 0 and a < 0:
            mul2 = a
        if mul1 != 0 and mul2 != 0:
            break
    ans1.append(mul2)
    ans2.append(mul1)
    s1 = sum(abs(a) for a in ans1)
    s2 = sum(abs(a) for a in ans2)
    if mul2 == 0:
        for a in ans2:
            ans *= a
    elif mul1 == 0:
        for a in ans1:
            ans *= a
    else:
        if s1 < s2:
            for a in ans2:
                ans *= a
        elif s1 > s2:
            for a in ans1:
                ans *= a
        else:
            from random import randint
            if randint(0, 1) == 0:
                for a in ans2:
                    ans *= a
            else:
                for a in ans1:
                    ans *= a
    print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

N,K = map(int,input().split())
L = list(map(int,input().split()))
L = sorted(L)

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    cand=[]
    poss=[]
    negs=[]
    replace=[]
    if K%2==1:#奇数個
        K-=1
        cand.append(L[-1])
        for l in L[:-1]:
            if l>0:
                heapq.heappush(poss,-l)
            else:
                heapq.heappush(negs,l)
    else:
        for l in L:
            if l>0:
                heapq.heappush(poss,-l)
            else:
                heapq.heappush(negs,l)

    added = len(cand) if cand else 0
    while added<K:
        if len(poss)>=2 and len(negs)>=2:
            pa = -heapq.heappop(poss)
            pb = -heapq.heappop(poss)

            na = heapq.heappop(negs)
            nb = heapq.heappop(negs)
            if pa*pb>na*nb:
                cand.append(pa*pb)
                added+=2
            else:
                cand.append(na*nb)
                added+=2
        elif len(poss)>=2:
            pa = -heapq.heappop(poss)
            pb = -heapq.heappop(poss)
            cand.append(pa*pb)
            added+=2
        if len(negs)>=2:
            na = heapq.heappop(negs)
            nb = heapq.heappop(negs)
            cand.append(na*nb)
            added+=2
        else:
            break
    for c in cand:
        ans*=c
        ans%=MOD
print(ans%MOD)

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 = -1
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:
    #最大化するとき
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = 0
        if i - 1 >= 0:
            m = abs(neg[i-1])
        if k-i-1 >= 0:
            m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    #print(good_num)
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans *= pos[i]
        ans %= mod
    print(ans % mod)

Submission status: Wrong Answer

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

def linked_merge_sort(l): #マージソート
    if len(l) == 1:
        return
    q, r = divmod(len(l), 2)
    left = [l.pop() for _ in range(q)]
    right = [l.pop() for _ in range(q + r)]
    
    linked_merge_sort(left)
    linked_merge_sort(right)
    
    left.reverse()
    right.reverse()
    while left and right:
        if left[-1] <= right[-1]:
            l.append(left.pop())
        else:
            l.append(right.pop())
    while left:
        l.append(left.pop())
    while right:
        l.append(right.pop())
    return

linked_merge_sort(a)
s=0
while s<n and a[s]<0:
    s+=1
b=[0]*s
for i in range(s):
    b[s-1-i]=a[s-1-i]
    i+=1

a2=[0]*(n-s)
i=0
while i<n-s:
    a2[i]=a[n-1-i]
    i+=1

ans=1
if n==s and k%2==1:
    for i in range(k):
        ans*=b[s-1-i]
else:
    j=0
    l=0
    for i in range(k):
        if l==s:
            ans*=a2[j]
            j+=1
        elif j==n-s:
            ans*=b[l]
            l+=1
        elif a2[j]>=abs(b[l]):
            ans*=a2[j]
            j+=1
        else:
            ans*=b[l]
            l+=1

    if ans<0:
        if j==n-s and l<s and n-s!=0:
            ans*=b[l]
            ans//=a2[j-1]
        elif j!=n-s:
            ans//=b[l-1]
            ans*=a2[j]
        
ans%=(10**9 +7)
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))
ans=1
plus1=-1
minus1=-1
for i in range(k):
    ans*=a[i]
    if a[i]>=0:
        plus1=i
    else:
        minus1=i
plus2=-1
for i in range(k,n):
    if a[i]>=0:
        plus2=i
        break
minus2=-1
for i in range(k,n):
    if a[i]<0:
        minus2=i
        break
if ans>=0:
    print(ans)
else:
    if (plus2>0 and minus1>0) or (minus2>0 and plus1>0):
        ans1=-1
        ans2=-1
        if plus2>0 and minus1>0:
            ans1=ans*a[plus2]//a[minus1]
        if minus2>0 and plus1>0:
            ans2=ans*a[minus2]//a[plus1]
        print(max(ans1,ans2))
    else:
        ans=1
        for i in range(0,k):
            ans*=a[-1-i]
        print(ans)

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[mindAfter][0], con - 2, con)
				ans %= con
			else:
				ans *= B[mindPre][0] * pow(B[pindAfter][0], con - 2, con)
				ans %= con
			print(ans)
			return

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


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))[::-1]
mod=10**9+7
score=1

P,M=[],[]
for i in A:
    if i>0:
        P.append(i)
    else:
        M.append(i)

M=M[::-1]
t=0
p,m=0,0
if score<0:  #負であることが確定しているなら小さくなるようにする
    P=P[::-1]
    M=M[::-1]
while t<K:  
    if t+2<=K:
        if 2*p+1<len(P) and 2*m+1<len(M):
            if P[2*p]*P[2*p+1] >= M[2*m]*M[2*m+1]:
                score*=P[2*p]*P[2*p+1]
                p+=1
                t+=2
            else:
                score*=M[2*m]*M[2*m+1]
                m+=1
                t+=2
        elif 2*p+1<len(P):
            score*=P[2*p]*P[2*p+1]
            p+=1
            t+=2
        elif 2*m+1<len(M):
            score*=M[2*m]*M[2*m+1]
            m+=1
            t+=2
        else:
            score*=P[-1]*M[-1]
            break
    elif t+1<=K:
        if 2*p<len(P):
            score*=P[2*p]
        else:
            score*=M[2*m]
        break
    score%=mod

print(score%mod)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans%mod)
    exit()
    
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    ans=ans*((-1)%mod)
    print(ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def fact(arr):
  ans = 1
  for s in arr:
    ans *= s
    ans = ans % (10e9+7)
  return ans

def main():
  N, K = map(int, input().split(' '))
  A = list(map(int, input().split(' ')))
  Aplus = []
  Aminus = []
  for a in A:
    if(a >= 0):
      Aplus.append(a)
    else:
      Aminus.append(a)
  Aplus= sorted(Aplus, reverse=True)
  Aminus= sorted(Aminus)
  Aabs = sorted(A, key=lambda x:abs(x), reverse=True)
  plusnum=0
  minusnum=0
  for i in range(K):
    if(Aabs[i] >= 0):
      plusnum+=1
    else:
      minusnum += 1
  if(minusnum % 2 == 1):
    if(minusnum > 0 and plusnum > 0):
      if minusnum < len(Aminus):
        if (plusnum < len(Aplus)):
          if(abs(Aplus[plusnum] * Aminus[minusnum - 2]) > abs(Aplus[plusnum - 2] * Aminus[minusnum])):
            plusnum+=1
            minusnum-=1
          else:
            plusnum-=1
            minusnum+=1
        else:
          plusnum-=1
          minusnum+=1
      else:
        plusnum+=1
        minusnum-=1
  print(plusnum, minusnum)
  if(plusnum == 0):
    print(int(fact(Aminus[::-1][:minusnum])))
  else:    
    print(int(fact(Aplus[:plusnum]+Aminus[:minusnum])))

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
# WA
from itertools import accumulate
from collections import deque
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort(reverse = True, key = lambda x : abs(x))
Aneg = [1 if A[i] < 0 else 0 for i in range(len(A))]
cum = list(accumulate(Aneg)) + [0]
p = 10 ** 9 + 7

que = deque(A)
ans = 1
if cum[N - 1] == N or K == N:  # 絶対マイナス使わなくちゃいけない
    for i in range(N - 1, N - K - 1, -1):
        ans = ans * A[i] % p
    print(ans)
    sys.exit()

k = 0
neg = False
avoid = 1
for i in range(N):
    # if i == 0 and A[i] == 0:
    if A[i] == 0:
        ans = 0
        break
    if k >= K: break
    if A[i] > 0:
        ans = ans * abs(A[i]) % p
        k += 1
    elif neg:
        ans = ans * abs(A[i]) % p
        k += 1
        neg = not neg
    else:
        if cum[N - 1] - cum[i - 1] < 2:
            continue
        ans = ans * abs(A[i]) % p
        k += 1
        neg = not neg
if neg:
    ans = (-ans) % p
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, k = map(int, input().split())
a = list( map(int, input().split()))
p = 10**9+7

a.sort()

from bisect import bisect_left, bisect_right
zerostart = bisect_left(a, 0)
posstart = bisect_right(a, 0)

aneg = a[:zerostart]
cntzero = posstart - zerostart
apos = a[posstart:]

cntneg = len(aneg)
cntpos = len(apos)

# 答えが0になる時
if k > n-cntzero:
    print(0)
    exit()

# 答えが正になる時
if k <= cntpos or (k%2==0 and  k <= (cntneg//2)*2 + cntpos) or (k%2==1 and cntpos%2==1 and k <= (cntneg//2)*2 + cntpos-1):
    pos_pair_mix=[]
    apos.sort(reverse=True)
    for i in range(cntpos//2):
        pos_pair_mix.append((apos[2*i]*apos[2*i+1],+1,i))

    for i in range(cntneg//2):
        pos_pair_mix.append((aneg[2*i]*aneg[2*i+1],-1,i))

    pos_pair_mix.sort(key=lambda x:x[0],reverse=True)

    ans = 1
    last_apos=0

    for i in range(k//2):
        ans*=pos_pair_mix[i][0]%p
        ans%=p
        if pos_pair_mix[i][1]==1:
            last_apos = pos_pair_mix[i][2]+1
    if k%2==0:
        print(ans%p)
        exit()
    else:
        print((ans*apos[last_apos])%p)
        exit()

# 答えが負になる時
a.sort(key=lambda x:abs(x) )

ans = 1
for i in range(k):
    ans*=a[i]
    ans%=p

print(ans%p)

Submission status: Wrong Answer

Solution code:
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
cnt_plus=0
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
  if flag==-1:
    if cnt==0:
      prev=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if (k%2==1 and cnt_plus==0) or (cand_plus==0 and cand_minus==0):
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if pick[-1]*cand_plus>=prev*cand_minus:
      pick.append(cand_plus)
    else:
      pick=pick[:-1]
      pick.append(prev)
      pick.append(cand_minus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)

Submission status: Wrong Answer

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

sys.setrecursionlimit(1000000)
mod = 1000000007

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

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

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
a = lr()
a.sort()
mnum = 0
znum = 0
mlist = []
plist = []
judge = []
for num in a:
    if num < 0:
        mnum += 1
        mlist.append(abs(num))
    elif num == 0:
        znum += 1
    else:
        plist.append(num)
    judge.append(abs(num))
mflag = False
if (a[-1] <= 0 and k%2 == 1) or (k == n and mnum%2 == 1):
    mflag = True
if ((0 in a) and ((mflag) or (n-znum-k < 0))):
    print(0)
    sys.exit()
mmlist = []
for i in range(1,len(mlist),2):
    mmlist.append(mlist[i-1]*mlist[i]%mod)
plist.reverse()
mind = 0
pind = 0
pmax = len(plist)
mmax = len(mlist)
if k%2 == 0:
    if pmax%2 == 1:
        pmax-=1
else:
    if pmax%2 == 0:
        pmax = max(pmax-1,0)
tmp = 0
ans = 1
if not mflag:
    while tmp < k:
        if k-tmp == 1:
            ans *= plist[pind]
            ans %= mod
            tmp+=1
            pind+=1
        else:
            if pind+1 < pmax:
                if mind < mmax and mmlist[mind] > plist[pind]*plist[pind+1]:
                    ans *= mmlist[mind]
                    ans %= mod
                    tmp += 2
                    mind+=1
                else:
                    ans *= plist[pind]
                    ans %= mod
                    tmp += 1
                    pind+=1
            elif pind < pmax:
                if mind < mmax and mmlist[mind] > plist[pind]:
                    ans *= mmlist[mind]
                    ans %= mod
                    tmp += 2
                    mind+=1
                else:
                    ans *= plist[pind]
                    ans %= mod
                    tmp += 1
                    pind+=1
            else:
                ans *= mmlist[mind]
                ans %= mod
                tmp += 2
                mind += 1
    print(ans)
else:
    judge.sort(reverse=True)
    for i in range(k):
        ans *= judge[i]
        ans %= mod
    print((-ans)%mod)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))[::-1]
mod=10**9+7
score=1

P,M=[],[]
for i in A:
    if i>0:
        P.append(i)
    else:
        M.append(i)

M=M[::-1]
t=0
p,m=0,0
while t<K:
    if max(A)<0:
        P=P[::-1]
        M=M[::-1]
    if t+2<=K:
        if 2*p+1<len(P) and 2*m+1<len(M):
            if P[2*p]*P[2*p+1] >= M[2*m]*M[2*m+1]:
                score*=P[2*p]*P[2*p+1]
                p+=1
                t+=2
            else:
                score*=M[2*m]*M[2*m+1]
                m+=1
                t+=2
        elif 2*p+1<len(P):
            score*=P[2*p]*P[2*p+1]
            p+=1
            t+=2
        elif 2*m+1<len(M):
            score*=M[2*m]*M[2*m+1]
            m+=1
            t+=2
        else:
            score*=P[-1]*M[-1]
            break
    elif t+1<=K:
        if 2*p<len(P):
            score*=P[2*p]
        else:
            score*=M[2*m]
        break
    score%=mod

print(score%mod)

Submission status: Wrong Answer

Solution code:
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(reverse=True)
neg_list_reverse = sorted(neg_list, reverse=True)
neg_list.sort()


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

# 前計算
pos_values = []
tmp = 1
for i in range(N):
    if i >= lp:
        break
    tmp *= pos_list[i]
    tmp %= mod
    pos_values.append(tmp)

neg_values = []
tmp = 1
for i in range(N):
    if i >= ln:
        break
    tmp *= neg_list[i] * (-1)
    tmp %= mod
    neg_values.append(tmp)

neg_rev_values = []
tmp = 1
for i in range(N):
    if i >= ln:
        break
    tmp *= neg_list_reverse[i] * (-1)
    tmp %= mod
    neg_rev_values.append(tmp)

# 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):
    c = 0
    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()

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

print(ans)