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:
MOD=10**9+7
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))

num_neg=0
num_pos=0
num_zero=0
aalist=[]
for a in alist:
  if a>0:
    num_pos+=1
  elif a<0:
    num_neg+=1
  else:
    num_zero+=1
  aalist.append((abs(a),a))
aalist.sort(reverse=True)
    
if num_zero>N-K:
  print(0)
  sys.exit(0)
  
if N==K:
  answer=1
  for a in alist:
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
  
pos_possible=True
if num_pos==0:
  if K%2==1:
    pos_possible=False
    
if not pos_possible:
  aalist.sort()
  answer=1
  for i in range(K):
    aa,a=aalist[i]
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
    
aalist.sort(reverse=True)
#print(aalist)
answer=1
sgn=1
for i in range(K-2):
  aa,a=aalist[i]
  answer*=a
  answer%=MOD
  if a<0:
    sgn*=-1

if sgn>0:
  if aalist[K-2][1]*aalist[K-1][1]>0:
    answer*=aalist[K-2][1]*aalist[K-1][1]
    answer%=MOD
  else:
    if aalist[K-2][1]*aalist[K][1]>0:
      answer*=aalist[K-2][1]*aalist[K][1]
      answer%=MOD
    else:
      answer*=aalist[K-1][1]*aalist[K][1]
      answer%=MOD
else:
  if aalist[K-2][1]*aalist[K-1][1]<0:
    answer*=aalist[K-2][1]*aalist[K-1][1]
    answer%=MOD
  else:
    if aalist[K-2][1]*aalist[K][1]<0:
      answer*=aalist[K-2][1]*aalist[K][1]
      answer%=MOD
    else:
      answer*=aalist[K-1][1]*aalist[K][1]
      answer%=MOD
    
print(answer)

Submission status: Wrong Answer

Solution code:
def maxProductSubarrayOfSizeK(A, n, k): 
  
    MOD = 10**9+7
    A.sort()   
    product = 1
    
    ALL = []
    Po = []
    Ne = []
    for i in A:
        ALL.append(abs(i))
        if i > 0:
            Po.append(i)
        else:
            Ne.append(i)

    ALL.sort(reverse=True)
    Po.sort(reverse=True)
    Ne.sort()
    
    if A[n-1] < 0 and k%2 ==1:
        for i in range(k):
            product *= -Ne[i]
            product %= MOD
        
  
    

        
  
    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] 
        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 
            product %= MOD
            i += 2
          
        else : 
            product *= right_product 
            product %= MOD
            j -= 2
  
    return product

MOD = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
print((maxProductSubarrayOfSizeK(A, N, K))% MOD)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import os
from sys import stdin, stdout

MOD = int(1e9+7)

def solve(tc):
    n, k = map(int, stdin.readline().split())
    seq = list(map(int, stdin.readline().split()))

    seq = sorted(seq, key=lambda x: abs(x), reverse=True)

    contain_zero = False
    last_plus = -1
    last_minus = -1
    mul_minus = False

    arr = []
    p = 0
    while p < n and len(arr) < k:
        if seq[p] == 0:
            contain_zero = True
            p += 1
            continue

        if seq[p] < 0:
            last_minus = len(arr)
            mul_minus ^= True
        elif seq[p] > 0:
            last_plus = len(arr)

        arr.append(seq[p])
        p += 1

    # should contain zeros
    if p == n and len(arr)<k:
        print(0)
        return

    # found maximal
    if not mul_minus:
        ans = 1
        for num in arr:
            ans *= num
            ans %= MOD
        print(ans)
        return

    first_plus = -1
    first_minus = -1
    while p < n:
        if seq[p]==0:
            contain_zero = True
            p += 1
            continue

        if seq[p] < 0:
            if first_minus < 0:
                first_minus = p
        elif seq[p] > 0:
            if first_plus < 0:
                first_plus = p
        p += 1
    
    if first_plus < 0:
        if first_minus < 0:
            print(0)
            return
        elif last_plus < 0:
            if contain_zero:
                print(0)
            else:
                ans = 1
                for i in range(n-1, n-k-1, -1):
                    ans *= seq[i]
                    ans %= MOD
                print(ans)
            return
        else:
            arr[last_plus] = seq[first_minus]
    elif first_minus < 0:
        arr[last_minus] = seq[first_plus]
    else:
        if seq[first_plus]*arr[last_plus] < seq[first_minus]*arr[last_minus]:
            arr[last_plus] = seq[first_minus]
        else:
            arr[last_minus] = seq[first_plus]

    ans = 1
    for num in arr:
        ans *= num
        ans %= MOD
    print(ans)


tcs = 1
tc = 1
while tc <= tcs:
    solve(tc)
    tc += 1

Submission status: Wrong Answer

Solution code:
import sys, math
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x))[::-1]
P = int(1e9+7)

ans = 1
hu = None
sei = None
flg = False
for a in A:
    flg = a > 0
    if flg:
        break
if not flg:
    for i in range(1, K+1):
        ans = (ans * A[-i]) % P
    print(ans)
    sys.exit()
if K == N:
    for a in A:
        ans = (ans * a) % P
    print(ans)
    sys.exit()

for i, a in zip(range(K), A):
    if a > 0:
        if sei:
            ans = (ans * sei) % P
        sei = a
    else:
        if not hu:
            hu = a
        else:
            ans = (ans * a * hu) % P
            hu = None

ptn1, ptn2 = -math.inf, -math.inf
if hu:
    if sei:
        for i in range(K, N):
            if A[i] > 0:
                ptn1 = sei * A[i]
                break
        for i in range(K, N):
            if A[i] <= 0:
                ptn2 = hu * A[i]
                break
        ans = (ans * max(ptn1, ptn2)) % P
    else:
        for i in range(K, N):
            if A[i] > 0:
                ans = (ans*A[i])%P
                break
else:
    if sei:
        ans = (ans * sei) % P
print(ans % P)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

ans = 1
if N == K:
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit(0)

if N - A.count(0) < K:
    print(0)
    exit(0)

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

if K % 2 == 1 and len(plus) == 0:
    minus.sort(reverse=True)
    for i in range(K):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit(0)

plus.sort(reverse=True)
minus.sort()

if len(minus) == 0:
    for k in range(K):
        ans *= plus[k]
        ans %= MOD
    print(ans)
    exit(0)

i = 0
j = 0

if K % 2 == 1:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

print(ans)

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:
		anss = 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
		elif cm + 1 != lm:
			cp += 1
			cm += 1
		

		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		if i == cm-1:
			continue
		else:	
			ans *= (mina[i] * mina[i+1]) % mod
			ans %= mod
	ii = i
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod
	if ii == cm-1:
		ans *= mina[ii]
		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

abs_a =sorted(a,key=lambda x:abs(x))
abs_ak = abs_a[-k:]

if 0 in abs_ak:
    ans=0
    
elif all( aa<0 for aa in a ) or n==k:
    ans=1
    for aa in a[:k]:
        ans= ans*aa%mod
    
else:
    n_nega = sum(aa<0 for aa in abs_ak )   
    if n_nega%2==0:
        ans=1
        for c in abs_ak:
            ans = ans*c%mod
    else:    
        nokori = abs_a[:-k]
        
        maxposi=0
        maxnega=0
        found_posi=False
        found_nega=False
        for i in nokori[::-1]:
            if i<0 and not found_nega:
                    maxnega=i
                    found_nega=True
            if i>0 and not found_posi:
                    maxposi=i
                    found_posi=True
            if found_posi and found_nega:
                break

        minposi=float("inf")
        minnega=-float("inf")
        found_posi_inabsak=False
        found_nega_inabsak=False
        for i in abs_ak:
            if i<0 and not found_nega_inabsak:
                    minnega=i
                    found_nega_inabsak = True
            if i>0 and not found_posi_inabsak:
                    minposi=i
                    found_posi_inabsak = True
            if found_posi_inabsak and found_nega_inabsak:
                break
        
#         (found_nega and found_posi and found_posi_inabsak and found_nega_inabsak
        
        if abs(maxnega/minposi) <= abs(maxposi/minnega
                                      ) or not found_nega or not found_posi_inabsak:
            ans=1
            swap=False
            for c in abs_ak:
                if c==minnega and not swap:
                    ans = ans*maxposi%mod
                    swap=True
                else:
                    ans = ans*c%mod
        else:
            ans=1
            swap=False
            for c in abs_ak:
                if c==minposi and not swap:
                    ans = ans*maxnega%mod
                    swap=True
                else:
                    ans = ans*c%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]
    for j in range(len(a)):
        i = a[j]
        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 i in range(x):
        m = minus[i]
        ans *= m
        ans %= mod
    print(ans%mod)
    return

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

Submission status: Wrong Answer

Solution code:
N, K, *A = map(int, open(0).read().split())
MOD = 10 ** 9 + 7

z_num = sum(v == 0 for v in A)
p_num = sum(v > 0 for v in A)
m_num = sum(v < 0 for v in A)

if p_num + m_num < K:
    print(0)
    exit()
    
if m_num % 2 == 1 and p_num + m_num == K and z_num > 0:
    print(0)
    exit()
    
if p_num == 0 and m_num >= K:
    if K % 2 == 1 and z_num > 0:
        print(0)
    else:
        x = sorted([v for v in A if v < 0])
        ans = 1
        if K % 2 == 0:
            for i in range(K):
                ans = ans * x[i] % MOD
        else:
            n = len(x)
            for i in range(n - K, n):
                ans = ans * x[i] % MOD

        print(ans)
    exit()


x = sorted([(abs(v), v // abs(v)) for v in A if v != 0])
plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s == 1:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s == 1 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v

    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_org = plus.pop()
        m_org = minus.pop()
        if p_org * p_cand > m_org * m_cand:
            plus.append(p_org)
            plus.append(p_cand)
        else:
            minus.append(m_org)
            minus.append(m_cand)


ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * (-v) % MOD
print(ans)

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]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n and all_minus%2!=0:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    ans=ans*((-1)%mod)
    print(ans % mod)
    exit()
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()
if n==k:
    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:
MOD = 10 ** 9 + 7


def mod_mul(arr, mod):
    res = 1
    for elem in arr:
        res *= elem
        res %= mod
    return res


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

    if all([e <= 0 for e in a]):
        if k % 2 == 0:
            print(mod_mul(a[:k], MOD))
        else:
            print(mod_mul(a[n - k:], MOD))
        return

    if k == 1:
        print(max(a))
        return

    if k == n:
        print(mod_mul(a, MOD))
        return

    res = 1
    if sum(a[i] < 0 for i in range(k)) % 2 == 1:
        minus_flag = False
        for i in range(k - 1, -1, -1):
            if a[i] < 0:
                if not minus_flag:
                    minus_flag = True
                else:
                    res *= a[i]
                    res %= MOD
            else:
                res *= a[i]
                res %= MOD
        for i in range(k, n):
            if a[i] >= 0:
                res *= a[i]
                res %= MOD
                break
    else:
        for i in range(k):
            res *= a[i]
            res %= MOD

    print(res)


main()

Submission status: Wrong Answer

Solution code:
import math
import collections
import bisect
from copy import copy, deepcopy

MOD = 1000000007


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    sortedA = sorted(A)
    n_neg = bisect.bisect_left(sortedA, 1)
    n_0 = n_neg - bisect.bisect_left(sortedA, 0)
    n_pos = N - n_neg - n_0

    ans = 1
    if (n_pos + n_neg <= K or n_pos == 0) and (K - n_pos) % 2 == 1:
        if n_0 != 0:
            ans = 0
        else:
            absA = sorted(map(abs, sortedA))
            for i in range(K):
                ans *= absA[i]
                ans %= MOD
            ans *= -1
            ans %= MOD
    else:
        l = 0
        r = 0
        while(l + r < K):
            if sortedA[l] >= 0 or sortedA[l + 1] >= 0:
                ans *= sortedA[N - 1 - r]
                ans %= MOD
                r += 1
            elif sortedA[N - 1 - r] <= 0 or sortedA[N - 1 - r - 1] <= 0:
                ans *= sortedA[l]
                ans %= MOD
                ans *= sortedA[l + 1]
                ans %= MOD
                l += 2
            elif abs((sortedA[l] * sortedA[l + 1])) >= abs(sortedA[N - 1 - r] * sortedA[N - 1 - r - 1]):
                ans *= sortedA[l]
                ans %= MOD
                ans *= sortedA[l + 1]
                ans %= MOD
                l += 2
            else:
                ans *= sortedA[N - 1 - r]
                ans %= MOD
                r += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
plus = []
minus = []
zlen = 0
for i in map(int, input().split()):
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zlen += 1
plen = len(plus)
mlen = len(minus)
if K > plen + mlen:
    print(0)
    import sys
    sys.exit()
plus.sort(reverse=True)
minus.sort()
pp = [1]
mp = [1]
for p in plus:
    pp.append((pp[-1]*p)%mod)
for m in minus:
    mp.append((mp[-1]*(-m))%mod)
ppm = [1]
mpm = [1]
for p in plus[::-1]:
    ppm.append((ppm[-1]*p)%mod)
for m in minus[::-1]:
    mpm.append((mpm[-1]*(-m))%mod)
ans = -float("inf")
# kこマイナスから選ぶ
for k in range(K+1):
    if mlen < k:
        continue
    if plen < K-k:
        continue
    # 最大を目指す
    if k % 2 == 0:
        tmp = mp[k] * pp[K-k]
        ans = max(ans, tmp)
    # 絶対値最小を目指す
    else:
        tmp = -(mpm[k] * ppm[K-k])
        ans = max(ans, tmp)
if ans < 0 and zlen > 0:
    print(0)
    import sys
    sys.exit()
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N,K = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype='int64')
    plus = A[np.where(A > 0)]
    minus = A[np.where(A < 0)] * -1
    
    count_p = np.count_nonzero(A > 0)
    count_m = np.count_nonzero(A < 0)
    count_zero = np.count_nonzero(A == 0)

    def p(plus, minus, K):
        plus = np.sort(plus)[::-1]
        minus = np.sort(minus)[::-1]

        if K % 2 == 0:
            r = 1
        else:
            r = plus[0]
            plus = plus[1:]
            K -= 1
        
        p = 0
        m = 0
        while K > 0:
            if len(plus) <= p+1:
                r *= int(minus[m]*minus[m+1])
                m+=2
            elif len(minus) <= m+1:
                r *= int(plus[p]*plus[p+1])
                p+=2
            elif plus[p]*plus[p+1] > minus[m]*minus[m+1]:
                r *= int(plus[p]*plus[p+1])
                p+=2
            else:
                r *= int(minus[m]*minus[m+1])
                m+=2
            K -= 2
        return (r+(10**9+7))%(10**9+7)
            
    def m(plus, minus, K):
        plus = np.sort(plus)
        minus = np.sort(minus)

        if K % 2 == 0:
            r = 1
        else:
            r = minus[0]
            minus = minus[1:]
            K -= 1

        p = 0
        m = 0
        while K > 0:
            if len(plus) <= p+1:
                r *= int(minus[m]*minus[m+1])
                m+=2
            elif len(minus) <= m+1:
                r *= int(plus[p]*plus[p+1])
                p+=2
            elif plus[p]*plus[p+1] < minus[m]*minus[m+1]:
                r *= int(plus[p]*plus[p+1])
                p+=2
            else:
                r *= int(minus[m]*minus[m+1])
                m+=2
            K -= 2
        return (-r+(10**9+7))%(10**9+7)
            
    
    if N-K == 0:
        if count_zero > 0:
            print(0)
            return
        else:
            if count_m % 2 == 1:
                #minus
                print(m(plus, minus, K))
                return
            else:
                #plus
                print(p(plus,minus,K))
                return
    else:
        if count_p > 0:
            if count_zero <= N-K:
                #plus
                print(p(plus,minus,K))
                return
            else:
                print(0)
                return
        else:
            if count_zero > 0:
                print(0)
                return
            else:
                #minus
                print(m(plus, minus, K))
                return

main()

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()

# 答えが負になる時
mix = [(neg,-neg,-1) for neg in aneg] + [(pos,pos,1) for pos in apos]
mix.sort(key=lambda x:x[1])

ans = 1
for i in range(k-cntzero):
    ans*=mix[i][0]
    ans%=p

if ans <0 and cntzero>0:
    ans = 0

print(ans%p)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
MOD = 10**9 + 7
def main(N, K, A):
    negative = sorted([a for a in A if a < 0])
    neg = len(negative)
    zero = [a for a in A if a == 0]
    positive = sorted([a for a in A if a > 0])
    pos = len(positive)

    if N - K < len(zero):
        return 0
    N -= len(zero)
    A = sorted([a for a in A if a != 0], key=lambda x: abs(x))

    ans = Mint(1)
    if pos == 0 and K & 1:
        # マイナスになっちゃう
        for i in range(K):
            ans *= abs(A[i])
        ans = -ans
    else:
        # プラスにできる
        A.reverse()
        neg_cnt = 0
        last_pos = 0
        last_cnt = 0
        for i in range(K):
            ans *= abs(A[i])
            if A[i] < 0: neg_cnt += 1
            if neg_cnt & 1 == 0:
                last_pos = ans.value
                last_cnt = i + 1
        remain = K - last_cnt
        if remain == 1:
            for i in range(last_cnt, N):
                if A[i] > 0:
                    ans = Mint(last_pos * A[i])
                    break
        elif remain != 0:
            pospos = 1
            negneg = 1
            pos_rem = remain
            neg_rem = remain
            for i in range(last_cnt, N):
                if A[i] > 0 and pos_rem > 0:
                    pospos *= A[i]
                    pos_rem -= 1
                if A[i] < 0 and neg_rem > 0:
                    negneg *= abs(A[i])
                    neg_rem -= 1
                if pos_rem == neg_rem == 0:
                    break
            pospos = pospos if pos_rem == 0 else 1
            negneg = negneg if neg_rem == 0 else 1
            ans = Mint(last_pos * max(pospos, negneg))

    return ans

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    print(main(N, K, A))