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:
def main():
    def solve():
        ret = 1
        for i in range(n):
            if L[i][2]:
                ret *= L[i][0]
                ret %= MOD
        return ret % MOD

    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    INF = float('inf')
    L = []
    p, m = 0, 0
    for a in A:
        if a < 0:
            m += 1
            L.append([abs(a), -1, False])
        else:
            L.append([a, 1, False])
    L = sorted(L, key= lambda x: x[0], reverse=True)
    pm = 1
    lp, lm = None, None
    for i in range(k):
        L[i][2] = True
        pm *= L[i][1]
        if L[i][1] >= 0:
            lp = i
        else:
            lm = i
    if pm >= 0:
        ans = solve()
    else:
        ans1, ans2 = -INF, -INF
        if lp:
            j = k
            while j < n:
                if L[j][1] < 0:
                    L[lp][2] = False
                    L[j][2] = True
                    ans1 = solve()
                    L[lp][2] = True
                    L[j][2] = False
                    break
                j += 1
        if lm:
            j = k
            while j < n:
                if L[j][1] >= 0:
                    L[lm][2] = False
                    L[j][2] = True
                    ans2 = solve()
                    L[lm][2] = True
                    L[j][2] = False
                    break
                j += 1
        ans = max(ans1, ans2)
        if ans1 == ans2 == -INF:
            L = sorted(L, key=lambda x: x[0])
            ans = 1
            for i in range(k):
                ans *= L[i][0]
            ans = -1 * ans % MOD
    print(ans % MOD)
main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

mod = 10 ** 9 + 7
n, k = map(int, input().split())
A = list(map(int, input().split()))
# dp = [[[0] * (2) for _ in range(k+1)]for _ in range(n+1)]
# # dp[桁][数][負数の数=1,0]

A.sort()
n_minus = bisect_left(A, 0)
n_zero = bisect_right(A, 0) - n_minus
n_plus = n - n_minus - n_zero

possible_max = min(k, n_minus)
possible_min = max(k - (n_plus + n_zero), 0)
ans = 1
if possible_max == possible_min and possible_min % 2 == 1:
    if k - (possible_min) > 0 and n_zero > 0:
        print(0)
        exit()
    A_plus = A[n - (n_plus) :]
    A_minus = A[:n_minus]
    A_minus.sort(reverse=True)
    # 負の数は奇数個小さい方から選ぶ
    for i in range(possible_min):
        ans *= A_minus[i]
        ans %= mod
    for i in range(k - possible_min):
        ans *= A_plus[i]
        ans %= mod
else:
    # 正の数に成る→大きいものがほしい
    # 負の数は偶数個、これの数を決め打つ
    # 計算すると大変だから大小を考える

    A_plus = A[n - (n_plus) :]
    A_plus.sort(reverse=True)
    A_minus = A[:n_minus]

    # 負の数を使う数を決め打つ
    # 最終的に正にできるパターン
    minus_num_max = min(n_minus // 2, k // 2)
    select = k - 2 * minus_num_max
    if n_plus < select:
        print(0)
        exit()
    # 負の数にしかできないパターン
    # 遊びがない時に奇数個の負の数を選ばざるを得ない
    # その時に0があるかどうかパターン
    plus_shortage = 0
    minus_shortage = 0
    for i in range(minus_num_max + 1):
        # 各々使う個数
        p = k - 2 * i
        m = 2 * i
        if p - 2 < 0:
            plus_shortage = 1
            break
        if p > n_plus:
            continue
        plus_kouho = A_plus[p - 1] * A_plus[p - 2]
        if m + 1 >= n_minus:
            minus_shortage = 1
            break
        minus_kouho = A_minus[2 * i] * A_minus[2 * i + 1]
        if minus_kouho > plus_kouho:
            ans *= minus_kouho
            ans %= mod
        else:
            break

    for j in range(k - 2 * i):
        ans *= A_plus[j]
        ans %= mod

print(ans)

Submission status: Wrong Answer

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

p_list = []
n_list = []
z_count = 0

for A in map(int, input().split()):
	if A < 0:
		n_list.append(A)
	elif A > 0:
		p_list.append(A)
	else:
		z_count += 1

p_list.sort()
n_list.sort()

#print(p_list)
#print(n_list)

if len(p_list) + len(n_list) < K:
	print(0)
else:
	values = []
	
#	print(len(p_list) >= K ,  (K - len(p_list)) % 2 == 0 ,  ((K - len(p_list)) % 2 == 1 and len(p_list) >= 1 and K - len(p_list) + 1 <= len(n_list)))
	if len(p_list) >= K or (K - len(p_list)) % 2 == 0 or ((K - len(p_list)) % 2 == 1 and len(p_list) >= 1 and K - len(p_list) + 1 <= len(n_list)):
		p_list.reverse()
		i_p = 0
		i_n = 0
		if len(p_list) >= K:
			for i in range(K):
				values.append(p_list[i_p])
				i_p += 1
		elif (K - len(p_list)) % 2 == 0:
			for i in range(len(p_list)):
				values.append(p_list[i_p])
				i_p += 1
			while len(values) < K:
				values.append(-n_list[i_n])
				i_n += 1
			values.sort()
		elif K - len(p_list) + 1 <= len(n_list):
			for i in range(len(p_list) - 1):
				values.append(p_list[i_p])
				i_p += 1
			while len(values) < K:
				values.append(-n_list[i_n])
				i_n += 1
			values.sort()
		i = K - 1
		while i >= 1 and i_n < len(n_list) - 1:
			if values[i] * values[i - 1] < n_list[i_n] * n_list[i_n + 1]:
				values[i] = n_list[i_n]
				values[i - 1] = n_list[i_n + 1]
				i -= 2
				i_n += 2
			else:
				break
	else:
		n_list.reverse()
		i_p = 0
		i_n = 0
		for i in range(min(len(n_list), K)):
			values.append(n_list[i_n])
			i_n += 1
		while len(values) < K:
			values.append(p_list[i_p])
			i_p += 1
	
#	print(values)
	total = 1
	for v in values:
		total = (total * v) % M
	print(total)

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
MOD = 10**9 + 7
def calc(X):
  ans = 1
  for x in X:
    ans *= x
    ans %= MOD
  return ans

def solve(A):
  if N == K:
    return calc(A)
  if max(A) < 0 and K % 2:
    return calc(sorted(A, reverse=True)[:K])
  
  sA = sorted(((abs(a), -1 if a < 0 else 1) for a in A), reverse=True)
  #print(sA)
  cn = 0
  for i in range(K):
    if sA[i][1] < 0:
      cn += 1
  if cn % 2 == 0:
    return calc([s[0] for s in sA[:K]])
  pA = sorted([abs(a) for a in A if a >= 0], reverse=True)
  nA = sorted([abs(a) for a in A if a < 0], reverse=True)
  #print(pA, nA)
  if (len(nA) >= cn + 1 and len(pA) >= K - cn - 1 and
      len(nA) >= cn - 1 and len(pA) >= K - cn + 1):
    candidates = []
    candidates.append((nA[cn-1] * nA[cn], calc(pA[:K-cn-1] + nA[:cn+1])))
    candidates.append((pA[K-cn-1] * pA[K-cn], calc(pA[:K-cn+1] + nA[:cn-1])))
    #print(candidates)
    return(max(candidates)[1])
    
  if len(nA) >= cn + 1 and len(pA) >= K - cn - 1:
    #print(cn, cn+1)
    return(calc(pA[:K-cn-1] + nA[:cn+1]))
  if len(nA) >= cn - 1 and len(pA) >= K - cn + 1:
    #print(cn, cn-1)
    return(calc(pA[:K-cn+1] + nA[:cn-1]))
  

print(solve(A))

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k,*A = get_all_int()
    A = list(A)

    # 答えが負である条件
    # ・Aが全て負で、Kが奇数
    # ・Aの負数が奇数個かつ0が存在せず、K=N

    # 答えが0である条件
    # ・N-(Aの0の個数) < K

    positives = 0
    zeros = 0
    negatives = 0

    for a in A:
        if a > 0:
            positives += 1
        elif a == 0:
            zeros += 1
        else:
            negatives += 1
    

    if k == 1:
        # 1個だけの場合はたんに最大値を出力する
        A.sort(reverse=True)
        print(A[0])
        exit()

    if (n-zeros) < k:
        # 答えが0
        print(0)
        exit()
    
    elif (k==n and negatives%2==1  or  n==negatives+zeros and k%2==1):
        # 答えが負
        # 絶対値小さい順にK個掛ける
        A.sort(key=lambda a: abs(a))
        # log(A)
        ans = 1
        for i in range(k):
            ans =  (ans * A[i]) % MOD
        print(ans%MOD)
        exit()

    else:
        # 答えが正
        # 絶対値大きい順にK個掛ける
        A.sort(reverse=True, key=lambda a: abs(a))
        # log(A)
        ans = 1
        n_count = 0
        last_n = 0
        last_p = 0
        for i in range(k):
            a = A[i]
            ans =  (ans * a) % MOD
            if a < 0:
                n_count += 1
                last_n = a
            elif a > 0:
                last_p = a
                # log(i, last_n)

        # log(ans, n_count, last_n)
        
        # 負数を奇数個選んでいる場合は調整する
        if n_count%2 == 1:
            first_p = None
            first_n = None
            for i in range(k,n):
                a = A[i]
                if a > 0 :
                    ans_a = ans*inv(last_n, MOD) * a
                    first_p = a
                    break
            if last_p != 0:
                for i in range(k,n):
                    a = A[i]
                    if a < 0:
                        ans_b = ans*inv(last_p, MOD) * a
                        first_n = a
                        break
                if first_n is not None:
                    if first_p is not None:
                        xx = abs(first_p) / abs(last_n)
                        yy = abs(first_n) / abs(last_p)
                        if yy > xx:
                            ans_a = ans_b
                    else:
                        ans_a = ans_b
            if first_n is None and first_p is None:
                ans_a = 0
            ans = ans_a
        
        print(ans%MOD)
        exit()

main()

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 and not 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 and not 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:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = []
p = N 
for i in range(N):
    if A[i] > 0:
        p = i
        break
D = A[:p]
B = []
for i in D:
    B.append(-i)
B.sort()
b = len(B)
C = A[p:]
for i in range(p):
    S.append(-A[i])
for i in range(p,N):
    S.append(A[i])
S.sort()
i = 0
while B:
    if S[i] == B[0]:
        S[i] = -S[i]
        B.pop(0)
    i += 1
def pow(a,b,mod):
    if b == 0:
        return 1
    else:
        if b % 2 == 0:
            return (pow(a,b//2,mod))**2%mod
        else:
            return (a*(pow(a,(b-1)//2,mod))**2)%mod
f = 0
p = 0
q = 0
mod = 10**9+7
ans = 1
for i in range(K):
    j = N - i - 1
    if S[j] < 0:
        q = S[j]
        f += 1
    else:
        p = S[j]
    ans *= S[j]
    ans = ans % mod
r = 0
s = 0
for i in range(K,N):
    j = N - i - 1
    if S[j] < 0:
        r = min(S[j],r)
    else:
        s = max(S[j],s)
if N == K:
    print(ans)
    quit()
if b == N:
    ans = 1
    for i in range(K):
        ans *= S[i]
        ans %= mod
    print(ans)
    quit()
if f % 2 == 0:
    print(ans)
    quit()
if r*q > s*q:
    ans *= r
    ans %= mod
    d = pow(p,mod-2,mod)
    ans *= d
    ans %= mod
else:
    ans *= s
    ans %= mod
    d = -pow(-q,mod-2,mod)
    ans *= d
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = int(1e9+7)
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
flag = 0
for a in A:
    if a>0:
        flag = 1
        break
#すべてマイナスか0
if flag == 0 and K%2==1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
    print(ans)
#それ以外
else:
    A = sorted(A, key=abs, reverse = True)
    last_pos = -1
    last_neg = -1
    count_neg = 0
    is_zero = 0
    ans = 1
    for i in range(K):
        ans = (ans*A[i]) % MOD
        if A[i]>0:
            last_pos = i
        elif A[i]<0:
            last_neg = i
            count_neg += 1
        else:
            is_zero = 1
            break
    if is_zero == 1:
        print(0)
    elif count_neg%2 == 0:
        print(ans)
    else:
        flag_pos = 0
        flag_neg = 0
        new_pos = -1
        new_neg = -1
        for i in range(K,N):
            if A[i]>0 and flag_pos==0:
                flag_pos = 1
                new_pos = i
            elif A[i]<0 and flag_neg==0:
                flag_neg = 1
                new_neg = i
            if flag_pos == 1 and flag_neg == 1:
                break

        if last_pos > -1 and last_neg > -1 and new_pos > -1 and new_neg > -1:
            f1 = A[new_pos] * A[last_pos]
            f2 = A[new_neg] * A[last_neg]
            if f1>f2:
                ans = 1
                for i in range(K):
                    if i != last_neg:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_pos]) % MOD
            else:
                ans = 1
                for i in range(K):
                    if i != last_pos:
                        ans = (ans*A[i]) % MOD
                ans = (ans*A[new_neg]) % MOD
        elif last_pos > -1 and new_neg > -1:
            ans = 1
            for i in range(K):
                if i != last_pos:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_neg]) % MOD
        elif last_neg > -1 and new_pos > -1:
            ans = 1
            for i in range(K):
                if i != last_neg:
                    ans = (ans*A[i]) % MOD
            ans = (ans*A[new_pos]) % MOD
        else:
            ans = 0
            
        print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

A = sorted(A, reverse=True)

B = sorted(A, key=abs, reverse=True)

a = 1
b = 1

for num in A[:K]:
    a *= num

for num in B[:K]:
    b *= num

if a > b:
    print(a % (10**9 + 7))
else:
    print(b % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
P=[]
Z=[]
N=[]
for i in range(n):
  if a[i]>0:
    P.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    N.append(-a[i])
P.sort()
P3=[1]
for i in range(len(P)):
  P3.append(P3[-1]*P[i]%mod)
P.reverse()
P2=[1]
for i in range(len(P)):
  P2.append(P2[-1]*P[i]%mod)
N.sort()
N3=[1]
for i in range(len(N)):
  N3.append(N3[-1]*N[i]%mod)
N.reverse()
N2=[1]
for i in range(len(N)):
  N2.append(N2[-1]*N[i]%mod)

if n==k:
  ans=1
  for i in range(n):
    ans*=a[i]
    ans%=mod
  print(ans%mod)
  exit()

if k==1:
  print(max(a)%mod)
  exit()

if len(P)+len(N)<k:
  print(0)
  exit()

if len(N)==0:
  print(P2[k]%mod)
  exit()

if len(P)+len(N)==k:
  if len(N)%2==0:
    print(P2[-1]*N2[-1]%mod)
    exit()
  else:
    if len(Z)!=0:
      print(0)
    else:
      print(-P2[-1]*N2[-1]%mod)
    exit()

if k%2==0:
  ans=1
  xp=0
  xn=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=0
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=0
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
    else:
      xp+=2
      ans*=xa
      ans%=mod
  print(ans%mod)

else:
  ans=1
  xp=0
  xn=0
  ctP=0
  ctN=0
  for i in range(k//2):
    if xp+1<len(P):
      xa=P[xp]*P[xp+1]
    else:
      xa=0
    if xn+1<len(N):
      xb=N[xn]*N[xn+1]
    else:
      xb=0
    if xa<xb:
      xn+=2
      ans*=xb
      ans%=mod
      ctN+=1
    else:
      xp+=2
      ans*=xa
      ans%=mod
      ctP+=1
  if ctP*2+1<=len(P):
    ans*=P[ctP*2]
    ans%=mod
    print(ans%mod)
  else:
    N.reverse()
    P.reverse()
    ans=1
    xp=0
    xn=0
    ctP=0
    ctN=0
    for i in range(k//2):
      if xp+1<len(P):
        xa=P[xp]*P[xp+1]
      else:
        xa=0
      if xn+1<len(N):
        xb=N[xn]*N[xn+1]
      else:
        xb=0
      if xa<xb:
        xn+=2
        ans*=xb
        ans%=mod
        ctN+=1
      else:
        xp+=2
        ans*=xa
        ans%=mod
        ctP+=1
    ans*=N[ctN*2]
    ans%=mod
    if len(Z)!=0:
      print(0)
    else:
      print(-ans%mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict, deque

MOD = 10 ** 9 + 7
N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]


def getBestNonNeg(K):
    neg = [-x for x in A if x < 0]
    nonneg = [x for x in A if x >= 0]
    neg.sort()
    nonneg.sort()
    ans = 1
    while K >= 2 and len(nonneg) >= 2 and len(neg) >= 2:
        if nonneg[-1] * nonneg[-2] < neg[-1] * neg[-2]:  # Take larger
            ans = (ans * neg.pop() * neg.pop()) % MOD
        else:
            ans = (ans * nonneg.pop() * nonneg.pop()) % MOD
        K -= 2
    while K >= 2 and len(neg) >= 2:
        ans = (ans * neg.pop() * neg.pop()) % MOD
        K -= 2
    while K and nonneg:
        ans = (ans * nonneg.pop()) % MOD
        K -= 1
    if K == 0:
        return ans % MOD
    return None


def getBestNeg(K):
    neg = [-x for x in A if x < 0]
    nonneg = [x for x in A if x >= 0]
    neg.sort(reverse=True)
    nonneg.sort(reverse=True)
    ans = neg.pop()
    K -= 1
    while K >= 2 and len(nonneg) >= 2 and len(neg) >= 2:
        if nonneg[-1] * nonneg[-2] > neg[-1] * neg[-2]:  # Take smaller
            ans = (ans * neg.pop() * neg.pop()) % MOD
        else:
            ans = (ans * nonneg.pop() * nonneg.pop()) % MOD
        K -= 2
    while K >= 2 and len(neg) >= 2:
        ans = (ans * neg.pop() * neg.pop()) % MOD
        K -= 2
    while K and nonneg:
        ans = (ans * nonneg.pop()) % MOD
        K -= 1

    assert K == 0
    return (-ans) % MOD


# Make largest nonnegative
ans = getBestNonNeg(K)
if ans is not None:
    print(ans)
else:
    # Failed, retry making smallest absolute value negative
    print(getBestNeg(K))

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-1,2):
			i = -(1+i)
			ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		ans *= mina[-(3+i)]
		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:
		mina.append(pra[0])
		mina.sort()
		for i in range(k):
			i = -(1+i)
			ans *= mina[i]
		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

	#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

	"""
	while co <= k:
		if k - co >= 2:
			if data[co] * data[co+1] >= 0:
				ans *= (data[co] * data[co+1]) % mod
				ans %= mod
				co += 2
			else:
				ans *= data[co]
				ans %= mod
				ans *= data[co+1]
				ans %= mod
				co += 2
		elif k - co == 1:
			ans *= data[co]
			ans %= mod
			co += 1
		else:
			break
	"""

		
	print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import heapq
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, K = NMI()
    A = NLI()
    M = [a for a in A if a < 0]
    P = [-a for a in A if a > 0]
    Z = [a for a in A if a == 0]
    M.sort(reverse=True)
    P.sort(reverse=True)
    heapq.heapify(M)
    heapq.heapify(P)

    ans = []
    if len(P) == 0 and K % 2:
        if len(Z):
            print(0)
            exit()
        else:
            M = [-a for a in A if a < 0]
            heapq.heapify(M)
            for k in range(K):
                ans.append(-heapq.heappop(M))

    elif K == len(M) + len(P) and len(M) % 2:
        if len(Z):
            print(0)
            exit()
        else:
            M = [-a for a in A if a < 0]
            heapq.heapify(M)
            for k in range(len(M)):
                ans.append(-heapq.heappop(M))
            P = [a for a in A if a > 0]
            heapq.heapify(P)
            for k in range(len(P)):
                ans.append(-heapq.heappop(P))

    else:

        while K > 0:
            if K == 1:
                if len(P) >= 1:
                    ans.append(-heapq.heappop(P))
                elif len(M) >= 1:
                    ans.append(heapq.heappop(M))
                else:
                    ans.append(0)
                break


            if len(P) >= 2 and len(M) >= 2:
                m1 = heapq.heappop(M)
                m2 = heapq.heappop(M)
                p1 = heapq.heappop(P)
                p2 = heapq.heappop(P)
                if m1 * m2 > p1 * p2:
                    ans.append(m1)
                    ans.append(m2)
                    heapq.heappush(P, p1)
                    heapq.heappush(P, p2)
                else:
                    ans.append(-p1)
                    ans.append(-p2)
                    heapq.heappush(M, m1)
                    heapq.heappush(M, m2)
                K -= 2

            elif len(P) >= 2:
                p1 = heapq.heappop(P)
                p2 = heapq.heappop(P)
                ans.append(-p1)
                ans.append(-p2)
                K -= 2

            elif len(M) >= 2:
                m1 = heapq.heappop(M)
                m2 = heapq.heappop(M)
                ans.append(m1)
                ans.append(m2)
                K -= 2

            elif len(P) == 1:
                ans.append(-heapq.heappop(P))
                break

            else:
                break
    res = 1
    for a in ans:
        res *= a % MOD
    print(res % MOD)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

b=[]
c=[]
for i in range(n):
    b.append(abs(a[i]))
    if a[i]>0:
        c.append(1)
    else:
        c.append(-1)
d=zip(b,c)
e=sorted(d)

ans=1
for i in range(n-1,n-k-1,-1):
    ans*=b[i]*c[i]
    if i==n-k-1 and ans*a[i-1]<0:
        ans*=a[i-1]

temp=1
for i in range(k):
    temp*=b[i]*c[i]
ans=max(ans,temp)

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

Submission status: Wrong Answer

Solution code:
import itertools
a, b = map(int, input().split())
A = sorted(map(int, input().split()))
long= list(itertools.combinations(A, b))
han=-99999999999999999
for a in long:
    goukei=1
    for b in a:
        goukei*=int(b)
    if goukei>han:
        han=goukei
print(han)
han%1000000007
print(han)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
def Ii():return int(sys.stdin.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n,k = Mi()
mod = 10**9+7
a = np.array(sorted(Li(),reverse=True))
isflag = 0
#b = sorted(np.abs(a),reverse=True)
ans = 1
if n == k:
  for i in range(k): ans = ans*a[i]%mod
  print(ans)
  exit(0)
plus = sum(a>0)
if plus == 0:
  if k%2 == 1:
    for i in range(k): ans = ans*a[i]%mod
  else:
    for i in range(k): ans = ans*a[n-i-1]%mod
  print(ans)
  exit(0)
i = 0
for i in range(k-1):
  idma = np.argmax(np.abs(a))
  ans = ans*np.max(np.abs(a))%mod
  #a.pop(idma)
  isflag = (isflag+(a[idma]>0))
  if plus == isflag+1:
    break
  a = np.delete(a,idma)
  
if k%2 == isflag%2:
  for j in range(k-i-1):
    ans = ans*abs(a[-j-1])%mod
else :
  ans = ans*a[0]%mod
  for j in range(k-i-1):
    ans = ans*abs(a[-j-1])%mod
    
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int , input().split()))
a.sort()
cm = 0
c0 = 0
cp = 0
for ai in a:
    if ai == 0:
        c0 += 1
    elif ai > 0:
        cp += 1
    else:
        cm += 1

ans = []
tmp = 1
#print(a[-k:], a[:k])
for ai in a[-k:]:
    tmp *= ai
ans.append(tmp)
tmp = 1
for ai in a[:k]:
    tmp *= ai
ans.append(tmp)
if c0 > 0:
    ans.append(0)
MOD = 10 ** 9 + 7
#print(ans)
print(max(ans) % MOD)

Submission status: Wrong Answer

Solution code:

def resolve():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    pls = [i for i in A if i > 0]
    ms = [i for i in A if i <0]
    pls.sort(reverse=True)
    ms.sort(reverse=False)
    A.sort(key = lambda x : abs(x),reverse=True)
    if len(pls)+len(ms) < K:
        print(0)
        return
    if len(pls)+len(ms) == K and K %2==1:
        print(0)
        return
    if len(pls) == 0 and K %2 == 1:
        x=1
        for i in list(reversed(ms))[:K]:
            x*= abs(i)
            x%= 10**9+7

        print((-x)%10**9+7)
        return
    pc = 0
    mc = 0
    for i in range(K):
        if pc >= len(pls):
            mc+=1
        elif mc >= len(ms):
            pc+=1
        elif pls[pc] > abs(ms[mc]):
            pc +=1
        else:
            mc +=1

    if mc%2  !=0:
        aplan=0
        bplan=0
        if mc < len(ms)-1:
            aplan = abs(ms[mc] / pls[pc-1])
        if pc < len(pls)-1:
            bplan = abs(pls[pc]/ms[mc-1])
        
        if aplan>bplan:
            pc -=1
            mc +=1
        else:
            pc +=1
            mc -=1
    result=1
    for i in pls[:pc]:
        result*=i
        result%=10**9+7
    for i in ms[:mc]:
        result*=abs(i)
        result%=10**9+7
    print(result)



resolve()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
MOD = 10**9 + 7
A = list(map(int,input().split()))
Ap = [a for a in A if a >= 0]
An = [-a for a in A if a < 0]
Ap.sort()
Ap.reverse()
An.sort()
An.reverse()

if len(Ap) == 0 and K % 2 == 1:
	ans = 1
	An.reverse()
	for i in range(K):
		ans = (ans * -An[i]) % MOD
	print(ans)
	exit()

B = [(a, 1) if a >= 0 else (-a, -1) for a in A]
B.sort()
B.reverse()
M = [0 if B[0][1] > 0 else 1]
for i in range(1, N):
	M.append(M[i-1] + (0 if B[i][1] > 0 else 1))

i = K-1
if M[i] % 2 == 0 or K == N:
	ans = 1
	v = 1 if (M[i] % 2 == 0) else -1
	for j in range(K):
		ans = (ans * B[j][0] * v) % MOD
	print(ans)
else:
	n = M[i]
	p = K - n
	if len(An) == n or p == 0:
		n -= 1
		p += 1
	elif len(Ap) == p:
		n += 1
		p -= 1
	elif Ap[p-1] * Ap[p] >= An[n-1] * An[n]:
		n -= 1
		p += 1
	else:
		n += 1
		p -= 1
	ans = 1
	for i in range(p):
		ans = (ans * Ap[i]) % MOD
	for i in range(n):
		ans = (ans * An[i]) % MOD
	print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
minus = deque(a[:bisect.bisect_left(a, 0)])
plus = deque(a[bisect.bisect_left(a, 0):])
#plus.sort(reverse=True)
nm = len(minus)
np = len(plus)
mod = 10**9+7
ans = -float("inf")
repeat = min(nm//2, k//2)

if k == n:
  ans = 1
  for i in range(n):
    ans *= a[i]
    ans %= mod
  print(ans)
  quit()

flg=False
must1 = k-np
must2 = min(k, nm)
start = must1//2
start += must1%2

if must1 % 2 == 1 and must2 - must1 ==0:
  flg = True

if flg:
  ans = 1
  for i in range(k):
    ans *= minus.pop()
    ans %= mod
  print(ans)
  quit()
    
for i in range(start, repeat+1):
  temp = 1
  kuri = 0
  mcount=0
  pcount=1
  #print("i " + str(i))
  for j in range(i*2):
    #temp*=minus.popleft()  
    temp*=minus[mcount]
    mcount+=1
    temp%=mod
  for j in range(k-i*2):
    #temp*=plus.pop()
    temp*=plus[-pcount]
    pcount+=1
    temp%=mod
  #print(i)
  #print(temp)
  ans=max(ans, temp)

print(ans)