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:
		if cp == 0:
			cp += 1
			cm += 1

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

	#data.sort()
	co = 0

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


		
	print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
ans = 1
if N == K:
    for i in range(K):
        ans *= A[i]
        if abs(ans) > mod:
            ans %= mod
elif len([v for v in A if v <= 0]) == N:
    for i in range(K):
        ans *= A[-(i + 1)]
        if abs(ans) > mod:
            ans %= mod
else:
    num_hu = len([v for v in A[:K] if v < 0])
    if num_hu % 2 == 0:
        for i in range(K):
            ans *= A[i]
            if abs(ans) > mod:
                ans %= mod
    else:
        if len([v for v in A[K:] if v >= 0]) == N - K:
            idx = K - 1
            while True:
                if A[idx] < 0:
                    break
                idx -= 1
            for i in range(idx):
                ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
            ans *= A[K]
            ans %= mod
            for i in range(idx + 1, K):
                ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
        elif len([v for v in A[K:] if v <= 0]) == N - K:
            idx = K - 1
            while True:
                if A[idx] > 0:
                    break
                idx -= 1
            for i in range(idx):
                ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
            ans *= A[K]
            ans %= mod
            for i in range(idx + 1, K):
                ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
        else:
            ans_1 = 1
            ans_2 = 1
            # ans_1
            min_hu_idx = K - 1
            while True:
                if A[min_hu_idx] < 0:
                    break
                min_hu_idx -= 1
            max_sei_idx = K
            while True:
                if A[max_sei_idx] > 0:
                    break
                max_sei_idx += 1
            for i in range(K):
                if i == min_hu_idx:
                    ans_1 *= A[max_sei_idx]
                else:
                    ans_1 *= A[i]
                if abs(ans_1) > mod:
                    ans_1 %= mod
            # ans_2
            min_sei_idx = K - 1
            while True:
                if A[min_sei_idx] > 0:
                    break
                min_sei_idx -= 1
            max_hu_idx = K
            while True:
                if A[max_hu_idx] < 0:
                    break
                max_hu_idx += 1
            for i in range(K):
                if i == min_sei_idx:
                    ans_2 *= A[max_hu_idx]
                else:
                    ans_2 *= A[i]
                if abs(ans_2) > mod:
                    ans_2 %= mod
            ans = max(ans_1, ans_2)
print(ans % mod)

Submission status: Wrong Answer

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

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

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

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

n,k = m()

a = l()

a.sort()

mina = []

pra = []

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

lp = len(pra)

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

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


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

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

		else:
			
			
			if cp != -1 and cm != lm:
				if pra[cp-1] != 0 and -mina[cm]/pra[cp-1] <= pra[cp]/-mina[cm+1]:
					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):
		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:
def mult(lis):
  ret=1
  for i in lis:
    ret*=i
    ret%=1000000007
  return ret
n,k=map(int,input().split())
a=list(map(int,input().split()))
minus=[]
plus=[]
ch=[]
for i in a:
  if i<0:
    minus.append(i)
  else:
    plus.append(i)
if len(a)==k:
  ch.extend(a)
elif len(plus)==0 and k%2:
  minus.sort(reverse=True)
  ch.extend(minus[:k])
else:
  pls=True
  a.sort(key=lambda x: abs(x), reverse=True)
  while k>0:
    inp=a.pop(0)
    if inp<0:
      if k==1 and pls==False:
        continue
      pls^=1
    ch.append(inp)
    k-=1
print(mult(ch))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            else:
                if maxnega == 0:
                    maxnega = a[i]


        if abs(minposi*maxposi) < abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)
        elif abs(minposi*maxposi) > abs(minnega*maxnega):
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)
        else:
            pp


print(ans % mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
a.sort()
mi = []
pl = []
zero = 0
for i in a:
    if i < 0:
        mi.append(i)
    elif i == 0:
        zero += 1
    else:
        pl.append(i)
pl = sorted(pl,reverse=True)
if n-zero < k:
    print(0)
    exit()
if mi == []:
    ans = 1
    count = 0
    while count < k:
        ans *= a[-1-count]
        ans %= mod
        count += 1
    print(ans)
    
    exit()
if pl == []:
    if k%2:
        if zero:
            print(0)
        else:
            ans = 1
            count = 0
            while count < k:
                ans *= a[-1-count]
                ans %= mod
                count += 1
            print(ans)
            
    else:
        ans = 1
        count = 0
        while count < k:
            ans *= a[count]
            ans %= mod
            count += 1
        print(ans)
        
    exit()

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

Submission status: Wrong Answer

Solution code:
import numpy as np

MOD = 10**9 + 7
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
ans = 1
plus = a[a >= 0]
plus = np.sort(plus)[::-1]
plus = np.append(plus, [-np.inf, np.inf])#index errorにならないように
minus = a[a < 0]
minus = np.sort(minus)
minus = np.append(minus, [np.inf, -np.inf])
if n == k:
    for i in range(len(a)):
        ans *= a[i]
        ans %= MOD
    print(ans)
    exit()
if len(plus) == 2 and k % 2 == 1:#plusがない時
    for i in range(3, k + 3):#inf を入れてるせいでminus[-3]からとる
        ans *= minus[-i]
        ans %= MOD
else:
    if k % 2 == 1:#plus,minusからそれぞれ奇数、偶数個とる.plusから一つとって始める
        p = k // 2
        ans *= plus[0]
        cplus = 1
        cminus = 0
    else:#plus,minusからそれぞれ偶数個とる
        p = k // 2
        cplus = 0
        cminus = 0
    for l in range(p):
        if plus[cplus] * plus[cplus + 1] > minus[cminus] * minus[cminus + 1]:#plusとminusの絶対値の大きい二つを比べて大きい方を採用
            ans *= plus[cplus] * plus[cplus + 1]
            ans %= MOD
            cplus += 2
        else:
            ans *= minus[cminus] * minus[cminus + 1]
            ans %= MOD
            cminus += 2
print(int(ans))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
plus = []
minus = []
for i in map(int, input().split()):
    if i >= 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
plen = len(plus)
mlen = len(minus)
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)
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
div = 10**9+7
a = sorted(A)
ans = 1
if K == N or (K % 2 != 0 and a[-1] < 0):
    while K > 0:
        ans *= a.pop(-1)
        ans %= div
        K -= 1
    print(ans)
    exit()
while K > 0:
    if K >= 2 and a[0] * a[1] > a[-1] * a[-2]:
        ans *= a.pop(0)
        ans %= div
        ans *= a.pop(0)
        ans %= div
        K -= 2
    elif K >= 2 and a[0] * a[1] <= a[-1] * a[-2]:
        ans *= a.pop(-1)
        ans %= div
        ans *= a.pop(-1)
        ans %= div
        K -= 2
    else:
        ans *= a.pop(-1)
        ans %= div
        K -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
A = IL()
IS_P = False

for a in A:
  if a>0:
    IS_P = True

A = sorted(A,key= lambda x:-abs(x))
S = [a//abs(a) if abs(a)!=0 else 0 for a in A]

if not IS_P:
  ans = 1
  for i in range(K):
    ans *= A[N-1-i]
    ans %= MOD
  print(ans)
  exit()

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if S[i] == -1:
    last_M = i
    count_M += 1
  if S[i] == 1:
    last_P = i

if count_M%2 == 0:
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans %= MOD
  print(ans)
  exit()

else:
  ANS1 = -INF
  ANS2 = -INF
  if last_M!=None:
    for i in range(K,N):
      if S[i] == 1:
        ans = 1
        for ii in range(K):
          if ii != last_M:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        ANS1 = ans
        break
  if last_P!=None:
    for i in range(K,N):
      if S[i] == -1:
        ans = 1
        for ii in range(K):
          if ii != last_P:
            ans *= A[ii]
            ans %= MOD
        ans *= A[i]
        ans %= MOD
        ANS2 = ans
        break
  print(max(ANS1,ANS2))

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

def solve():
    n, k = NextInts()
    da = NextIntList()
    ans = 1
    MOD = 10**9+7
    
    if n == k:
        for i in range(n):
            ans = ans*da[i]%MOD
        return ans
    
    neg = []
    pos = []
    for i in range(n):
        if da[i] < 0:
            neg.append(da[i])
        else:
            pos.append(da[i])
    neg.sort()
    pos.sort()
    
    if len(pos) == 0 and k%2 == 1:
        neg.reverse()
        for i in range(k):
            ans = ans * da[i] % MOD
        return ans
    
    li = []
    pos.reverse()
    po, ne = 0, 0
    if k%2 == 1:
        po = 1
        ans = pos[0]
    while po+1 < len(pos):
        li.append(pos[po]*pos[po+1])
        po += 2
    while ne+1 < len(neg):
        li.append(neg[ne]*neg[ne+1])
        ne += 2
    li.sort()
    li.reverse()
    for i in range(k//2):
        ans = li[i] * ans % MOD
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
num = list(map(int, input().split()))
max = -((10 ** 9) +7)
for i in range(2 ** n):
    wk = []
    cnt = 0
    numWk = 1
    for j in range(n):
        if ((i>>j) & 1):
            cnt +=1
            wk.append(num[j])
        if cnt > k:
            break
    if cnt == k:
        for j in range(k):
            numWk = wk[j] * numWk % ((10 ** 9) +7)
        if max < numWk:
            max = numWk
print(max)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

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

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

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

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def solve():
    positive = sorted([a for a in A if 0 < a], reverse=True)
    negative = sorted([a for a in A if a <= 0])

    if not positive:
        ret = 1
        negative.reverse()
        for n in negative[: K]:
            ret *= n
        print(ret % MOD)
        return

    if K % 2 == 1:
        ret = positive[0]
        p_idx, n_idx = 1, 0
        k = 1
    else:
        ret = 1
        p_idx, n_idx = 0, 0
        k = 0

    ret = ModInt(ret)
    while k < K:
        if len(positive) - 2 <= p_idx or (1 <= len(negative) and positive[p_idx] * positive[p_idx + 1] < negative[n_idx] * negative[n_idx + 1]):
            ret *= negative[n_idx] * negative[n_idx + 1]
            n_idx += 2
        else:
            ret *= positive[p_idx] * positive[p_idx + 1]
        k += 2
    print(ret)

if __name__ == "__main__":
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    solve()

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:
    if K%2==1:
        for i in range(1, K+1):
            ans = (ans * A[-i]) % P
    else:
        for i in range(K):
            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:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	B = []
	for i in range(N):
		val = abs(A[i])
		if A[i] > 0:
			B.append([val , 1])
		elif A[i] < 0:
			B.append([val, -1])
		else:
			B.append([val, 0])
	B = sorted(B)

	M = 0; p = 0; m = 0; Aplus = []; Aminus = []; zerocnt = 0
	for i in A:
		if i == 0:
			zerocnt += 1
		elif i > 0:
			Aplus.append(i)
			M += 1; p += 1
		else:
			Aminus.append(i)
			M += 1; m += 1
	Aplus.sort()
	Aminus.sort()

	# 0が絶対に入る場合
	if K > M:
		print(0)
		return
	# マイナスになるから絶対ゼロを入れる場合
	if zerocnt > 0 and M == m and K % 2 == 1:
		print(0)
		return
	# マイナスのみの時の処理
	if m == N:
		if K % 2 == 0:
			ans = 1
			for i in range(K):
				ans *= Aminus[i]
				ans %= con
			print(ans)
			return
		else:
			ans = 1
			for i in range(K):
				ans *= Aminus[-1 - i]
				ans %= con
			print(ans)
			return

	# マイナスと0のとき
	if m == M:
		if K % 2 == 0:
			ans = 1
			for i in range(K):
				ans *= Aminus[i]
				ans %= con
			print(ans)
			return
		else:
			print(0)
			return

	pindPre = -100; pindAfter = INF
	mindPre = -100;	mindAfter = INF
	# print(B)

	for i in range(N - K):
		if B[i][1] == 1:
			pindPre = i
		elif B[i][1] == -1:
			mindPre = i

	for i in range(N - 1, N - K - 1, -1):
		if B[i][1] == 1:
			pindAfter = i
		elif B[i][1] == -1:
			mindAfter = i

	cnt = 0
	ans = 1
	for i in range(K):
		ans *= B[-1 - i][0]
		ans %= con
		if B[-1 - i][1] == -1:
			cnt += 1

	if cnt % 2 == 0:
		print(ans)
		return
	else:
		# ans *= -1
		ans %= con
		if mindPre >= 0 and pindPre >= 0 and pindAfter <= N and mindAfter <= N:		
			if B[mindPre][0] * B[mindAfter][0] <= B[pindPre][0] * B[pindAfter][0]:
				ans *= B[pindPre][0] * pow(B[mindAfter][0], con - 2, con)
				ans %= con
			else:
				ans *= B[mindPre][0] * pow(B[pindAfter][0], con - 2, con)
				ans %= con
			print(ans)
			return

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


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

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

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

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