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:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 +7

a_plus = []
a_minus = []
cnt_0 = 0

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

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

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

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

if(cnt_p + cnt_m == k)&(cnt_0>0)&(cnt_m%2==1):
    print(0)
    exit()


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

p_ind = 0
m_ind = 0

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

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

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

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


ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:

def inverse(a): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

import sys
N,K = map(int,input().split())
A = list(map(int,input().split()))

B = []
zero = 0
pl = 0
mi = 0
for i in A:
    if i == 0:
        zero += 1
    else:
        B.append( ( abs(i) , i // abs(i) ) )
        if i < 0:
            mi += 1
        else:
            pl += 1

last_pl = None

B.sort()
B.reverse()
mod = 10**9+7

if N - zero < K:
    print (0)
    sys.exit()

if pl == 0:

    if K % 2 == 0:
        now = 1
        for i in range(K):
            now *= B[i][0]
            now %= mod
        print (now % mod)
        sys.exit()
    else:
        now = 1
        if zero > 0:
            print (0)
            sys.exit()
        
        for i in range(K):
            now *= B[N-i-1][0] * B[N-i-1][1]
            now %= mod
        print (now % mod)
        sys.exit()


lasp = None
lasm = None

now = 1
for i in range(K):
    now *= B[i][0] * B[i][1]

    if now >= 0:
        now %= mod
    else:
        now = now % mod - mod

    if B[i][1] > 0:
        lasp = B[i][0]
    else:
        lasm = -1 * B[i][0]

#print (lasp,lasm)
if now > 0:
    print (now % mod)
    sys.exit()

else:

    if lasp == None:
        change2 = float("-inf")
        a2 = 0
    else:
        a2 = now * inverse(lasp)
        change2 = 1 / lasp
        for i in range(K+1,len(B)):
            if B[i][1] < 0:
                a2 *= -1 * B[i][0]
                change2 *= B[i][0]
                break
        else:
            change2 = float("-inf")

    if lasm == None:
        change3 = float("-inf")
        a3 = 0
    else:
    
        a3 = now * inverse(lasm % mod)
        change3 = 1 / lasm
        for i in range(K+1,len(B)):
            if B[i][1] > 0:
                a3 *= B[i][0]
                change3 *= B[i][0]
                break
        else:
            change3 = float("-inf")

    #print (a2,a3)
    if change2 > change3:
        print (a2 % mod)
    else:
        print (a3 % mod)

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
        for i in minus:
            ans *= i
        for i in plus:
            ans *= i
            ans %= mod
        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
for i in range(m+1):
    tmp *= minus[i]
    r = k - i
    if r > p:
        continue
    if r < 0:
        continue
    tmp2 = tmp * plus[r]
    ans = max(ans, tmp2)

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

Submission status: Wrong Answer

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

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

tmp = 1
cnt = 0

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

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

ans = 0

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

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

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

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


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

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

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

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

print(ans % mod)

Submission status: Wrong Answer

Solution code:
#                          JAI SHREE RAM

import math; from collections import *
import sys; from functools import reduce

# sys.setrecursionlimit(10**6)
def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())
def get_string(): return list(input().strip().split())
def printxsp(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")

UGLYMOD = int(1e9)+7; SEXYMOD = 998244353; MAXN = int(1e5)

# sys.stdin=open("input.txt","r");sys.stdout=open("output.txt","w")

# for _testcases_ in range(int(input())):
n, k = get_ints()
li = get_list()
pos = []
neg = []
ans = 1
zeroes = 0
for i in li:
    if i < 0: neg.append(i)
    elif i > 0: pos.append(i)
    else: zeroes += 1
lengthOfPos, lengthOfNeg = len(pos), len(neg)

if lengthOfNeg + lengthOfPos < k :
    print("0")
elif k&1 : #and (k - lengthOfPos) >= 0 and (k - lengthOfPos) & 1:
    if k > lengthOfPos:
        if zeroes:
            print("0")
        else:
            # last pr pakka negative ayega
            pos.sort(); positionOfPos = 0
            neg.sort(reverse = True); positionOfNeg = 0
            while k > 1:
                try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
                except: negpower = float('inf')
                try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
                except: pospower = float('inf')
                if pospower <= negpower:
                    positionOfPos += 2
                    ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
                else:
                    ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
                    positionOfNeg += 2
                k -= 2
            if k == 1:
                try: negpower = neg[positionOfNeg]
                except: negpower = float('inf')
                try: pospower = pos[positionOfPos]
                except: pospower = float('inf')
                ans = (ans * min(pospower, negpower)) % UGLYMOD
            print(ans)
            
    else:
        pos.sort(reverse = True); positionOfPos = 0
        neg.sort(); positionOfNeg = 0
        ans = 1
        while k > 1:
            try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
            except: negpower = -float('inf')
            try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
            except: pospower = -float('inf')
            if pospower >= negpower:
                positionOfPos += 2
                ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
            else:
                ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
                positionOfNeg += 2
            k -= 2
        if k == 1:
            ans = (ans * pos[positionOfPos]) % UGLYMOD
        print(ans)
else:
    pos.sort(reverse = True); positionOfPos = 0
    neg.sort(); positionOfNeg = 0
    ans = 1
    while k > 1:
        try: negpower = neg[positionOfNeg] * neg[positionOfNeg+1]
        except: negpower = -float('inf')
        try: pospower = pos[positionOfPos] * pos[positionOfPos+1]
        except: pospower = -float('inf')
        if pospower >= negpower:
            positionOfPos += 2
            ans = (ans * (pospower % UGLYMOD)) % UGLYMOD
        else:
            ans = (ans * (negpower % UGLYMOD)) % UGLYMOD
            positionOfNeg += 2
        k -= 2
    if k == 1:
        ans = (ans * pos[positionOfPos]) % UGLYMOD
    print(ans)







'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS MINE @luctivud ( UDIT GUPTA )
Link may be copy-pasted here if it's taken from other source.
DO NOT PLAGIARISE.
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Submission status: Wrong Answer

Solution code:
from collections import deque
n, k = map(int, input().split())
dq = deque(sorted(list(map(int, input().split())),reverse=True))
dq_n = len(dq)
res = 1
if k%2 != 0:
    res *= dq.popleft()
    dq_n -= 1
    k -= 1
if k == 0:
    print(int(res % 1000000007))
    exit()
while True:
    if k==0:
       break
    if dq_n >= 4:
        if dq[0] * dq[1] > dq[-1] * dq[-2]:
            res *= dq[0] * dq[1]
            dq.popleft()
            dq.popleft()
            dq_n -= 2
        else:
            res *= dq[-1] * dq[-2]
            dq.pop()
            dq.pop()
            dq_n -= 2
    else:
        res *= dq[0] * dq[1]
        dq.popleft()
        dq.popleft()
        dq_n -= 2
    k -= 2
print(int(res % 1000000007))

Submission status: Wrong Answer

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

ret = 1
mod = 10 ** 9 + 7

a.sort()

left = k

newls = []

for i, item in enumerate(a):
    if item > 0:
        newls.append((item, 1))
    else:
        if i % 2 == 1:
            if a[i] < 0 and a[i-1] < 0:
                newls.append((a[i] * a[i-1], 2))

newls.sort(reverse=True)

for val, cnt in newls:
    if cnt == 1:
        ret *= val % mod
        left -= 1
    else:
        if left == 1 and cnt == 2:
            continue
        else:
            ret *= (val % mod)
            ret %= mod
            left -= cnt
    if left == 0:
        break

if left == 0:
    print(ret % mod)
else:
    a.sort(key=lambda x: abs(x))
    ret = 1
    for i in range(k):
        ret *= a[i] % mod
        if ret == 0:
            break
    print(ret % 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)
        
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:
import sys, math,os
from io import BytesIO, IOBase
#data = BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
from decimal import Decimal
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
#sys.setrecursionlimit(100000 + 1)
INF = 10**9
mod = 10**9 + 7


n,k=mdata()
a=mdata()
n1,p=-1,-1
a1=[(abs(a[i]),a[i]) for i in range(n)]
a1.sort(reverse=True)
ans=1
c=1
for i in range(k):
    if a1[i][1]>0:
        p=i
    elif a1[i][1]<0:
        n1=i
        c*=-1
    else:
        c=0
    ans=(ans*a1[i][1])%mod
if c>=0:
    out(ans%mod)
else:
    m=-INF
    b1=0
    b2=0
    for i in range(k,n):
        if a1[i][1]>=0 and b1==0:
            u1,v1=a1[n1][1],a1[i][1]
            b1=1
            c=1
        if a1[i][1]<0 and p!=-1 and b2==0:
            u2,v2=a1[p][1],a1[i][1]
            b2=1
            c=1
    if c<0:
        ans=1
        for i in range(k):
            ans = (ans*a1[n-i-1][1])%mod
    else:
        if b1==1 and b2==1:
            if Decimal(v1/u1)<Decimal(v2/u2):
                ans=ans*pow(u1,mod-2,mod)*v1
            else:
                ans = ans * pow(u2, mod - 2, mod) * v2
        elif b1==1:
            ans = ans * pow(u1, mod - 2, mod) * v1
        else:
            ans = ans * pow(u2, mod - 2, mod) * v2
    out(ans%mod)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
am = []
ap = []
for ai in a:
    if ai > 0:
        ap.append(ai)
    elif ai < 0:
        am.append(-ai)
am.sort(reverse=True)
ap.sort(reverse=True)

nm = len(am)
np = len(ap)
nz = n - np - nm
# print(am)
# print(ap)

if np + nm < k:
    ans = 0
elif np == 0:
    if k % 2 == 1:
        if nz > 0:
            ans = 0
        else:
            am.sort()
            ans = -1 + MOD
            for i in range(k):
                ans *= am[i]
                ans %= MOD
    else:
        ans = 1
        for i in range(k):
            ans *= am[i]
            ans %= MOD
elif np < k:
    if (k - np) % 2 == 1:
        idx1 = np - 1
        idx2 = k - np + 1
        if k - np + 1 > nm:
            if nz > 0:
                ans = 0
            else:
                if nm % 2 == 1:
                    ans = -1 + MOD
                else:
                    ans = 1
                for i in range(np):
                    ans *= ap[i]
                    ans %= MOD
                for i in range(nm):
                    ans *= am[i]
                    ans %= MOD
        else:
            print(idx1, idx2)
            while idx1 >= 2 and idx2 + 1 < nm and \
                ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
                idx1 -= 2
                idx2 += 2
            print(idx1, idx2)
            ans = 1
            for i in range(idx1):
                ans *= ap[i]
                ans %= MOD
            for i in range(idx2):
                ans *= am[i]
                ans %= MOD
    else:
        idx1 = np
        idx2 = k - np
        while idx1 >= 2 and idx2 + 1 < nm and \
            ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
            idx1 -= 2
            idx2 += 2
        ans = 1
        for i in range(idx1):
            ans *= ap[i]
            ans %= MOD
        for i in range(idx2):
            ans *= am[i]
            ans %= MOD
else:
    idx1 = k
    idx2 = 0
    while idx1 >= 2 and idx2 + 1 < nm and \
        ap[idx1 - 1] * ap[idx1 - 2] < am[idx2] * am[idx2 + 1]:
        idx1 -= 2
        idx2 += 2
    ans = 1
    for i in range(idx1):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx2):
        ans *= am[i]
        ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
from collections import defaultdict, deque
from decimal import *
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

mod=1000000007
n,k=rm()
a=rl()
pos=[]
neg=[]
for i in a:
    if i>0:
        pos.append(i)
    else:
        neg.append(i)
pos.sort(reverse=True)
neg.sort(reverse=True)
for i in range(1,len(pos)):
    pos[i]=(pos[i-1]*pos[i])%mod
for j in range(1,len(neg)):
    neg[j]=(neg[j-1]*neg[j])%mod

if len(pos)==0:
    print(neg[k-1]%mod)
elif len(neg)==0:
    print(pos[k-1]%mod)
else:
    maxi=-math.inf
    for i in range(0,k+1,2):
        if i==0:
            if k-i<=len(pos):
                maxi=max(maxi,pos[k-i-1]%mod)
        elif k-i==0:
            if i<=len(neg):
                maxi=max(maxi,neg[i-1]%mod)
        elif i<=len(neg) and k-i<=len(pos):
            maxi=max(maxi,(neg[i-1]*pos[k-i-1])%mod)
    print(maxi)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    mp = sum([int(a<=0) for a in A])
    pl = True
    if (N == K):
        if mp%2 == 0:     pl = True
        else:     pl = False
    if (mp == N):
        if K%2 == 0: pl = True
        else: pl = False

    absA = sorted(A, key=abs)
    sA = deque(absA)
    ans = 1
    if pl:
        for i in range(K):
            ans*= sA.pop()
            ans%= MOD

        if ans<0:
            pre=absA[i]
            prei = i
            while((i!=N) and (absA[i] * pre)>0 ): i+=1
            if i==N:
                pre = avsA[prei+1]
                i = prei
                while((absA[i]*pre)>0 ): i-=1
            
            ans//= absA[i]
            ans*= pre

        print(ans%MOD)

    else:
        for i in range(K):
            ans*= sA.popleft()
            ans%= MOD
        print(ans%MOD)


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

P = []
N = []
z = 0
for i in A:
  if i > 0:
    P.append(i)
  elif i < 0:
    N.append(i)
  else:
    z += 1
P.sort(reverse = True)
N.sort()

ans = 1
sig = 1
if len(P) + (len(N)// 2) * 2 < K and z > 0:# Conner_1
  ans = 0
elif len(P) == 0 and K % 2 == 1:# Conner_2
  for i in range(K):
    ans *= N[-i-1]
    ans %= base
else:#Not use zeros and (P exists or even K)
  x = 0
  y = 0
  for i in range(K):
    if x == len(P):
      ans *= N[y]
      y += 1
      sig = sig * (-1)
      continue
    if y == len(N):
      ans *= P[x]
      x += 1
      ans %= base
      continue
    if y == len(N) - 1 and sig > 0:# ans must be positive
      ans *= P[x]
      x += 1
      ans %= base
      continue
    if x == len(P) - 1:
      if sig > 0 and (K - i) % 2 == 1 or sig < 0 and (K - i) % 2 == 0:
        ans *= P[x]
        x += 1
      else:
        ans *= N[y]
        y += 1
        sig = sig * (-1)
      ans %= base
      continue
    if P[x] > abs(N[y]):
      ans *= P[x]
      x += 1
    else:
      ans *= N[y]
      y += 1
      sig = sig * (-1)
    ans %= base
print(ans)

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(abs, A))

A = sorted(A)
A = np.array(A)
A = A % (10**9+7)

dp = [0 for i in range(N//4+1)]

for i in range(N//4+1):
  if i == 0:
    a = A[-K:]
    prod = 1
    for j in range(len(a)):
      prod *= a[i]
      prod = prod % (10**9+7)
    dp[0] = prod
  else:
    if -K+i*2 < 0:
      a = np.hstack([A[:i*2], A[-K+i*2:]])
      prod = 1
      for j in range(len(a)):
        prod *= a[i]
        prod = prod % (10**9+7)
      dp[i] = prod
    else:
      a = A[:i*2]
      prod = 1
      for j in range(len(a)):
        prod *= a[i]
        prod = prod % (10**9+7)
      dp[i] = prod

print(max(dp))

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x.append(i)
        if i<0:y.append(i)
    if len(x)+len(y)<k or len(x)<k and (len(y)<k or k%2>len(x)) and (k-len(x))%2 and len(x)+len(y)<n:
        print(0)
        exit()
    if len(x)<k and (len(y)<k or k%2>len(x)) and (k-len(x))%2:
        x=sorted(x+[-i for i in y])[:k]
        x[0]*=-1
        c=1
        for i in x:
            c=c*i%M
        print(c)
        exit()
    x=sorted(x)[::-1][:k]
    y.sort()
    m=len(y)
    i=len(x)
    j=0
    if i<k:
        j=k-i
        x+=y[:j]
        j+=1
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

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 = 1
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:
        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:
    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:
    ans = (ans * sei) % P
print(ans % P)