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:
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:
		cm -= 1
		cp -= 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:
import sys
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sorted(A, key=abs, reverse=True)
X = 1
pm = 0
for i in range(K - 1):
    if S[i] < 0:
        pm = 1 - pm
    X = X * abs(S[i]) % MOD
    X = X % MOD
for i in range(K - 1, N):
    if pm == 0:
        if S[i] > 0:
            Y = X * S[i] % MOD
            print(Y % MOD)
            sys.exit()
    else:
        if S[i] < 0:
            Y = X * abs(S[i]) % MOD
            print(Y % MOD)
            sys.exit()

for i in range(K - 2, 0, -1):
    if pm == 0:
        if S[i] > 0:
            X = 1
            for j in range(K):
                if j == i:
                    continue
                X = X * abs(S[j]) % MOD
                X = X % MOD
            print(X % MOD)
            sys.exit()
    if pm == 1:
        if S[i] < 0:
            X = 1
            for j in range(K):
                if j == i:
                    continue
                X = X * abs(S[j]) % MOD
                X = X % MOD
            print(X % MOD)
            sys.exit()

X = 1
S = S[::-1]
for i in range(K):
    X = X * abs(S[i]) % MOD
X *= -1
print(X % MOD)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

MOD = 10**9+7


def main(input, print):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    nc = 0
    for i in range(n):
        if a[i] < 0:
            nc += 1
    negative = 0
    cnt = 0
    ans = 1
    a = sorted(a, key=abs, reverse=True)
    y = 0
    for i in range(n):
        if k == cnt:
            break
        if a[i] < 0:
            if k-cnt > 1:
                if negative % 2 == 1:
                    ans = ans * y * a[i] % MOD
                    cnt += 2
                else:
                    y = a[i]
                negative += 1
        else:
            ans = ans * a[i] % MOD
            cnt += 1
    if cnt == k:
        print(ans)
        return
    ans = 1
    a = sorted(a, key=abs)
    y = 0
    for i in range(k):
        ans = ans * a[i] % MOD

    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
mod = 10**9 + 7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a_plus = [int(x) for x in a if x > 0]
a_minus = [int(x) for x in a if x < 0]
a_abs = [abs(x) for x in a]
a_abs = sorted(a_abs, key=lambda x: abs(x))[::-1]
a = sorted(a, key=lambda x: abs(x))[::-1]
a_plus = sorted(a_plus, key=lambda x: abs(x))[::-1]
a_minus = sorted(a_minus, key=lambda x: abs(x))[::-1]

def calc(x):
    res = 1
    for i in x:
        res*=i
        res %= mod 
    return res
max_a = a[:k]
max_a_minus = []
max_a_plus = []
cnt = 0
for i in max_a:
    if i == 0:
        print(0)
        sys.exit()
    if i < 0:
        cnt += 1
        max_a_minus.append(i)
    else:
        max_a_plus.append(i)

if cnt % 2 ==0:
    print(calc(max_a))
    sys.exit()

minus_cnt = cnt
plus_cnt = k - cnt
from copy import deepcopy
if len(a_minus) <= cnt and len(a_plus) <= plus_cnt:
    ans = -float('inf')
elif len(a_minus) <= cnt:
    if len(max_a_minus) == 0:
        ans = -float("inf")
    else:
        max_a_minus.pop()
        max_a_plus.append(a_plus[plus_cnt])
        ans = calc(max_a_plus + max_a_minus)
elif len(a_plus) <= plus_cnt:
    if len(max_a_plus) == 0:
        ans = -float("inf")
    else:
        max_a_plus.pop()
        max_a_minus.append(a_minus[cnt])
        ans = calc(max_a_minus + max_a_plus)
else:
    if len(max_a_minus) == 0 or len(max_a_plus) == 0:
        ans = -float("inf")
    else:
        c1 = deepcopy(max_a_minus)
        c2 = deepcopy(max_a_plus)
        c3 = deepcopy(max_a_minus)
        c4 = deepcopy(max_a_plus)
        c1.pop()
        c4.pop()
        c2.append(a_plus[plus_cnt])
        c3.append(a_minus[cnt])
        ans = max(calc(c1 + c3), calc(c2 + c4))
a_abs = a_abs[::-1]
ans2 = -calc(a_abs[:k])
if ans > ans2:
    print(ans%mod)
else:
    print(ans2%mod)

Submission status: Wrong Answer

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



flg = 0
plus_num = 0
for i in a:
    if i>0:
        plus_num+=1
minus_num = n-plus_num


if minus_num ==1 and k==n:
    flg = 1
if minus_num >=2 and plus_num>=1 and n-plus_num%2==1 and k==n:
    flg = 1
if  minus_num >=2  and plus_num==0 and k%2==1:
    flg = 2



if flg == 1:
    ans = 1
    for i in a:
        ans*=i
        ans %= (10**9+7)
        ans = 1
        
if flg ==2:
    abs_a = sorted(a, key=abs)
    ans = 1
    for i in range(k):
        ans*=abs_a[i]
        ans %= (10**9+7)
else:
    abs_a = sorted(a, key=abs)
    abs_a.reverse()
    min_minus = 0
    ans = 1
    for i in range(k):
        if abs_a[i]>=0:
            ans*=abs_a[i]
            ans %= (10**9+7)
        else:
            ans *= abs_a[i]
            ans %= (10**9+7)
            min_minus = abs_a[i]
    if ans <0:
        ans /=min_minus
        while True:
            for i in range(k,n):
                if abs_a[i]>=0:
                    ans*=abs_a[i]
                    ans %= (10**9+7)
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
As = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def multiReduce(array):
    ret = 1
    for a, s in array:
        if s == 0:
            ret = ret * a % MOD
        else:
            ret = ret * (-a) % MOD
    return ret

arr = []
for a in As:
    if a >= 0:
        arr.append((a, 0))
    else:
        arr.append((-a, 1))

arr.sort(reverse=True)

if arr[K-1][0] == 0:
    print(0)
    exit()

lastPlus = None
lastPlusIdx = None
lastMinus = None
lastMinusIdx = None
numMinus = 0
for i in range(K):
    a = arr[i]
    if a[1] == 0:
        lastPlus = a[0]
        lastPlusIdx = i
    else:
        lastMinus = a[0]
        lastMinusIdx = i
        numMinus += 1

if numMinus % 2 == 0:
    print(multiReduce(arr[:K]))
    exit()

nextPlus = None
nextMinus = None
for i in range(K, N):
    a = arr[i]
    if a[1] == 0 and nextPlus is None:
        nextPlus = a[0]
    elif a[1] == 1 and nextMinus is None:
        nextMinus = a[0]

BD = None
if lastMinus and nextPlus is not None:
    BD = lastMinus * nextPlus
AC = None
if lastPlus is not None and nextMinus:
    AC = lastPlus * nextMinus

if BD is not None and (AC is None or BD >= AC):
    arr[lastMinusIdx] = (nextPlus, 0)
    print(multiReduce(arr[:K]))
    exit()
elif AC is not None and (BD is None or BD < AC):
    arr[lastPlusIdx] = (nextMinus, 1)
    print(multiReduce(arr[:K]))
    exit()

print(multiReduce(arr[N-K:]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

def resolve():
    mod = 10**9 + 7
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a= sorted(a)
    if k == 1:
        print(a[-1])
        exit()
    b = []
    for i in range(n):
        b.append(a[i]%mod)
    b = sorted(b, reverse = True)
    ans = 1
    for i in range(k):
        ans *= b[i]
        ans %= mod
    print(ans)

resolve()

Submission status: Wrong Answer

Solution code:
from math import ceil
from collections import defaultdict as dd
import sys
input=sys.stdin.readline
#t=int(input())
#while t:
n,k=map(int,input().split())
positive=[]
negative=[]
zero=[]
mod=10**9+7
l=list(map(int,input().split()))
l.sort(reverse=True)
for i in range(n):
    if(l[i]>0):
        positive.append(l[i])
    elif(l[i]==0):
        zero.append(0)
    else:
        negative.append(l[i])
positive.sort()
negative.sort(reverse=True)
com=[]
for i in range(len(negative)-1,-1,-2):
    com.append(abs(negative[i]))
    com.append(abs(negative[i-1]))
#print(com)
lp=len(positive)
ln=len(negative)
lc=len(com)
lz=len(zero)
mul=1
if(k%2==0):
    i=lp-1
    j=lc-1
    while(k and j>0 and i>0):
        if(com[j]*com[j-1]>positive[i]*positive[i-1]):
            mul=(mul*com[j]*com[j-1])%mod
            j-=2
        else:
            mul=(mul*positive[i]*positive[i-1])%mod
            i-=2
        k-=2
    while (k and i>0):
        mul=(mul*positive[i]*positive[i-1])%mod
        i-=2
        k-=2
    while(k and j>0):
        mul=(mul*com[j]*com[j-1])%mod
        j-=2
        k-=2
    if(k):
        mul=0
else:
    i=lp-1
    j=lc-1
    if(positive):
        mul=positive.pop()
        i-=1
        k-=1
        while(k and j>0 and i>0):
            if(com[j]*com[j-1]>positive[i]*positive[i-1]):
                mul=(mul*com[j]*com[j-1])%mod
                j-=2
            else:
                mul=(mul*positive[i]*positive[i-1])%mod
                i-=2
            k-=2
        while (k and i>0):
            mul=(mul*positive[i]*positive[i-1])%mod
            i-=2
            k-=2
        while(k and j>0):
            mul=(mul*com[j]*com[j-1])%mod
            j-=2
            k-=2
        if(k):
            mul=0
    else:
        mul=1
        kk=k
        if(lz):
            mul=0
        else:
            for i in range(min(k,ln)):
                #print(negative[i])
                mul=((mul%mod)*((negative[i]+mod)%mod))%mod
                kk-=1
            if(kk):
                mul=0
print(mul)

Submission status: Wrong Answer

Solution code:
N , K = map(int, input().split())
A =list(map(int, input().split()))
mod = 10**9 + 7
count =0
for k in range(len(A)):
    if A[k] == 0:
        count +=1
        A[k] = float("inf")
if N-count < K:
    print(0)
    exit()
A.sort()
A = A[:N-count]
A.sort(reverse=True)
#print(A)
ans = 1
plus = 0
minus = -1
countp = 0
countm = 0
if A[0] >0:
    for k in range(K):
        if abs(A[plus]) >= abs(A[minus]):
            ans = ans*A[plus]%mod
            plus+=1
        else:
            ans = ans*A[minus]%mod
            minus-=1
    if minus%2 == 1:
        print(ans%mod)
    else:
        print(ans//A[minus+1]*A[plus]%mod)
else:
    for k in range(K):
        ans = ans*A[k]%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
zeros = 0
for i in a:
  if i < 0:
    neg.append(i)
  elif i==0:
    zeros+=1
  else:
    pos.append(i)
neg.sort(reverse=True)
if pos == []:
  if zeros != 0:
    print(0)
  else:
    p = 1
    if k&1:
      for i in neg[:k]:
        p *= i
    else:
      for i in neg[::-1][:k]:
        p *= i
    print(p%mod)
else:
  pos.sort()
  a = neg+pos
  p = 1
  for i in a[:k]:
    p *= i
  m = p
  j = 0
  for i in a[k:]:
    p *= i
    p = p//a[j]
    m = max(m,p)
    j+=1
  print(m%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(p+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 = [(1,[n,n])]
    a.sort()
    s = 1
    s2 = 1
    k1 = 0
    k2 = 0
    ind = [None]*2
    ind2 = [None]*2
    for j in range(n):
        i = a[j]
        if i != 0:
            if i < 0:
                ind[k1] = j
                k1 ^= 1
                s *= -i
                if not k1:
                    minus.append((s,ind))
                    s = 1
            else:
                ind[k2] = j
                k2 ^= 1
                s2 *= i
                if not k2:
                    minus.append((s2,ind))
                    s2 = 1
    ans = 1
    x = k>>1
    minus.sort(reverse = True)
    f = [1]*(n+1)
    for i in range(x):
        m,indi = minus[i]
        for j in indi:
            f[j] = 0
        ans *= m
        ans %= mod
    if (k-2*x)&1:
        b = [a[i] for i in range(n) if f[i]]
        p = max(b)
        ans *= p
    print(ans%mod)
    return

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

Submission status: Wrong Answer

Solution code:
def resolve():
    from bisect import bisect_left
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    m=bisect_left(a,0)
    MOD=10**9+7
    if m==0:
        ans=1
        for i in a[-k:]:
            ans=(ans*i)%MOD
    elif m==n:
        ans=1
        if k%2==0:
            for i in a[:k]:
                ans=(ans*i)%MOD
        else:
            for i in a[-k:]:
                ans=(ans*i)%MOD
    else:
        cal=1
        i=(m//2)*2
        for j in a[:i]:
            cal=(cal*j)%MOD
        if k-i>0:
            for j in a[-(k-i):]:
                cal=(cal*j)%MOD
        ans=cal
        for i in range((m//2)*2-2,-2,-2):
            if k-i>n-m:
                break
            for j in a[i-2:i]:
                cal=(cal*pow(j,MOD-2,MOD))%MOD
            if k-i>=0:
                for j in a[-(k-i):-(k-i)+2]:
                    cal=(cal*j)%MOD
            ans=max(ans,cal)
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = (int(i) for i in input().split())
A = np.array([int(i) for i in input().split()])
Ax = A[np.argsort(np.abs(A))[::-1]]
res = 1
cnt = 0
bak = 0
for i in range(N):
    if Ax[i] < 0:
        if bak != 0:
            res = res * Ax[i] * bak % (10**9+7)
            cnt = cnt + 2
            bak = 0
        else:
            bak = Ax[i]
    else:
        res = res * Ax[i] % (10**9+7)
        cnt = cnt + 1
    if cnt >= K:
        break
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    A_neg = [a for a in A if a < 0]
    A_zero = [a for a in A if a == 0]
    A_pos = [a for a in A if a > 0]

    A_neg.sort(reverse=True)
    A_pos.sort()

    if K > len(A_neg) + len(A_pos):
        print(0)
        return
    elif len(A_pos) == 0:
        if len(A_zero) > 0:
            print(0)
            return
        elif K % 2:
            ans = 1
            for a in A_neg[:K]:
                ans = (ans * a) % MOD
            print(ans)
            return
        else:
            ans = 1
            for a in A_neg[-K:]:
                ans = (ans * a) % MOD
            print(ans)
            return

    tmp_pos = []
    tmp_neg = []

    ans = 1
    neg = 0
    for i in range(K):
        if not A_neg:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop() % MOD
        elif not A_pos:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop() % MOD
            neg = 1 - neg
        elif -A_neg[-1] > A_pos[-1]:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop() % MOD
            neg = 1 - neg
        else:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop() % MOD

    if neg:
        if A_pos:
            ans = ans * pow(tmp_neg[-1], MOD - 2, MOD) * A_pos.pop() % MOD
        elif A_neg and tmp_pos:
            ans = ans * pow(tmp_pos[-1], MOD - 2, MOD) * A_neg.pop() % MOD
        else:
            ans = 0

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


MOD = 10**9 + 7


def solve(n, k, a):
    a = sorted(a, reverse=True, key=lambda x: (abs(x), 1 if x >= 0 else -1))
    sign = 1
    for i in range(k):
        if a[i] < 0:
            sign = -sign
        if a[i] == 0:
            sign = 0

    if sign == 0:
        return 0

    if sign == 1:
        ans = 1
        for i in range(k):
            ans = (ans * abs(a[i])) % MOD
        return ans

    if sign == -1:
        cc = []

        more_neg = -1
        for i in range(k, n):
            if a[i] < 0:
                more_neg = i
                break

        more_pos = -1
        for i in range(k, n):
            if a[i] > 0:
                more_pos = i
                break

        taken_neg = -1
        for i in range(k-1, -1, -1):
            if a[i] < 0:
                taken_neg = i
                break

        taken_pos = -1
        for i in range(k - 1, -1, -1):
            if a[i] > 0:
                taken_pos = i
                break

        if more_neg >= 0 and taken_pos >= 0:
            cc.append((taken_pos, more_neg))
        if more_pos >= 0 and taken_neg >= 0:
            cc.append((taken_neg, more_pos))
        cc = sorted(cc, key=lambda x: abs(a[x[1]] / a[x[0]]), reverse=True)

        if len(cc) > 0:
            ans = 1
            for i in range(k):
                if i != cc[0][0]:
                    ans = (ans * a[i]) % MOD
            ans = (ans * a[cc[0][1]]) % MOD
            return ans
        else:
            # product is negative, taking smallest
            ans = 1
            for i in range(k):
                ans = (ans * a[n-i-1]) % MOD
            return ans


import random


def gen():
    for n in range(2, 100):
        for k in range(2, n):
            for t in range(100):
                a = [random.randrange(100) - 100 for _ in range(n)]
                solve(n, k, a)
        wi(n)


def main():
    # gen()
    # return
    n, k = ria()
    a = ria()
    wi(solve(n, k, a))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)

A_array=np.array(A)
n_min=np.sum(A_array<0)
n_zero=np.sum(A_array==0)


if N-K<n_zero or (n_min+n_zero==N and (K%2==1 or K>n_min)):
    print(0)
else:
    cand=[]
    for i in range(0,n_min//2+1):
        p_min=np.prod(A_array[-2*i:])
        p_pla=np.prod(A_array[0:K-2*i])
        if 2*i==0:
            cand.append(p_pla)
        elif K-2*i==0:
            cand.append(p_min)
        else:
            cand.append(p_pla*p_min)
    print(max(cand))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
p, n = [], []
flag = False

for Ai in A:
    if Ai==0:
        flag = True
    elif Ai>0:
        p.append(Ai)
    else:
        n.append(Ai)

if len(p)==0 and K%2==1:
    if 0 in A:
        print(0)
    else:
        n.sort(reverse=True)
        ans = 1
        
        for ni in n[:K]:
            ans *= ni
            ans %= MOD
        
        print(ans)
    exit()
    
if K==N:
    ans = 1
    
    for Ai in A:
        ans *= Ai
        ans %= MOD
    
    print(ans)
    exit()

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

if K%2==0:
    l = []
    
    for i in range(len(p)//2):
        l.append(p[2*i]*p[2*i+1])
    
    for i in range(len(n)//2):
        l.append(n[2*i]*n[2*i+1])

    l.sort(key=lambda x: abs(x), reverse=True)
    ans = 1
    
else:
    ans = p[0]
    l = []
    
    for i in range(len(p)//2):
        l.append(p[2*i]*p[2*i+1])
    
    for i in range(len(n)//2):
        l.append(n[2*i]*n[2*i+1])
    
    l.sort(key=lambda x: abs(x), reverse=True)
    

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = -9999999999
for x in itertools.combinations(A, K):
    seki = 1
    for i in range(len(x)):
        seki *= x[i]
    ans = max(ans, seki)

print(ans%(7 + (10**9)))

Submission status: Wrong Answer

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

l_pos=[]
l_neg=[]
for i in range(n):
  if l[i]<0:
    l_neg.append(l[i])
  else:
    l_pos.append(l[i])

l_neg.sort()
l_pos.sort()
a=len(l_neg)
b=len(l_pos)
a=a-1
b=b-1

if len(l_neg)==0:
  ans=1
  for i in range(k):
    ans*=l_pos[-1-i]
    ans=ans%mod

elif len(l_pos)==0:
  ans=1
  for j in range(k):
    ans*=l_neg[i]
    ans=ans%mod

elif k==n:
  ans=1
  for i in range(n):
    ans*=l[i]
    ans=ans%mod

else:
  ans=1
  cntodd=0
  while a>0 and b>0:
    if l_pos[b]>=abs(l_neg[a]):
      ans*=l_pos[b]
      ans=ans%mod
      b-=1
    
    elif l_pos[b]<abs(l_neg[a]):
      ans*=l_pos[b]
      ans=ans%mod
      a-=1
      cntodd+=1
    k-=1
    if k==1:
      break

  if cntodd%2==0 and k==1:
    ans*=l_pos[b]
    k-=1
  elif cntodd%2!=0 and k==1:
    if b+1<len(l_neg):
      b+=1
    ans=ans//l_neg[b]
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[]
m=[]
z=0
a.sort(reverse=True)
for i in range(n):
    if a[i]>0:
        p.append(a[i])
    elif a[i]==0:
        z+=1
    else:
        m.append(a[i])
nump=len(p)
numm=len(m)
ans=1
if nump+numm<k:
    print(0)
elif numm<2 and nump>=k:
    for i in range(k):
        ans*=p[i]
        ans%=10**9+7
    print(ans)
elif 2*(numm//2)+nump<k: #2
    if z!=0:
        print(0)
    else:
        for i in range(n):
            a[i]=abs(a[i])
        a.sort()
        ans=-1
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0: #8?
    if z!=0 and k%2==1:
        print(0)
    elif z!=0 and numm<k:
        print(0)
    else:
        if k%2==0:
            m.sort()
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        else:
            m.sort(reverse=True)
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
    m.sort()
    nump=(nump-1)//2
    numm=numm//2
    nump1=0
    nump2=0
    numm1=0
    numm2=0
    for i in range(k//2):
        if nump2==nump:
            nump1=-1
        else:
            nump1=p[nump2*2]*p[nump2*2+1]
        if numm2==numm:
            numm1=-1
        else:
            numm1=m[numm2*2]*m[numm2*2+1]
        if numm1>=nump1:
            num=numm1
            numm2+=1
        else:
            num=nump1
            nump2+=1
        ans*=num
        ans%=10**9+7
    print(ans)

Submission status: Wrong Answer

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

input = sys.stdin.readline

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

inf = float('inf')
mod = 1000000007

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

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

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

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

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

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()