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:
N, K, *A = map(int, open(0).read().split())
MOD = 10 ** 9 + 7

if sum(v == 0 for v in A) > N - K:
    print(0)
    exit()


if all(v <= 0 for v in A):
    x = sorted([v for v in A if v < 0])
    ans = 1
    if K % 2 == 0:
        for i in range(K):
            ans = ans * x[i] % MOD
    else:
        n = len(x)
        for i in range(n - K, n):
            ans = ans * x[i] % MOD

    print(ans)
    exit()


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


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

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

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
A = li()

d = defaultdict(int)
mod = 10**9+7
K_ = K

for i in range(N):
    d[A[i]] += 1
    if A[i] < 0:
        A[i] *= -1

A = sorted(A, reverse=True)
l = []

for num in A:
    if d[-num] > 0:
        l.append(1)
        d[-num] -= 1
    else:
        l.append(0)
        d[num] -= 1

#print(l)
#print(sum(l[:K]))

if not sum(l[:K])%2:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)

else:
    flag = False
    ans = 1
    for i in range(K, N):
        if not l[i]:
            flag = True
            ans *= A[i]
            break
    
    if flag:
        for i in reversed(range(K)):
            if flag and l[i]:
                flag = 0
                continue
            ans *= A[i]
            ans %= mod
        print(ans)
    
    else:
        if K%2:
            for i in range(N-K, N):
                ans *= -A[i]
                ans %= mod
            print(ans)
        else:
            for i in range(N):
                if l[i] == 1:
                    K -= 1
                    ans *= -A[i]
                    ans %= mod
                if K == 0:
                    break
            else:
                if N == K_:
                    ans = -1
                    for num in A:
                        ans *= num
                        ans %= mod
                    print(ans)
                    exit()
                ans = 1
                flag = True
                for i in reversed(range(K_)):
                    if flag and not l[i]:
                        flag = 0
                        continue
                    ans *= A[i]
                    ans %= mod
                ans *= A[K_]
                ans %= mod
                print(ans)
                exit()

            print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline

N,K=map(int,readline().split())
A=list(map(int,readline().split()))
DIV = 10 ** 9 + 7

# 正に出来る場合：
# ・すべて正の数を選べる
# ・選べる数が奇数個で、負の数が偶数個と正の数が1個以上存在する
# ・選べる数が偶数個で、負の数が偶数個存在する
# 負になる場合：
# ・すべて負の数で且つ、選べる数が奇数個
# ・0が存在していれば、0のほうがマシ

# 開始時点で、絶対値が少ないほうを目指すか大きいほうを目指すか決まる
# 負の数を目指す場合、大きいほうからK個掛ければOK

# 大きいほうを目指す場合、
# 正の数の大きい順リスト [2,1]
# 負の数の絶対値大きい順リスト [-4,-3]
# の先頭から、2個のペアが大きくなるほうを貪欲に取っていく。
# 取れる数が奇数の場合は、まず正のほうの一番大きいのを取っちゃえばOK

pluslist = []
minuslist = []
zerocnt = 0
for i in range(len(A)):
  if A[i] > 0:
    pluslist.append(A[i])
  elif A[i] < 0:
    minuslist.append(A[i])
  else:
    zerocnt += 1
    
# 必ずゼロを選んでしまう場合
if N - zerocnt < K:
  print(0)
  exit(0)

if K % 2 == 1 and len(pluslist) == 0:
  # 負になる場合
  if zerocnt > 0:
    print(0)
    exit(0)
  # 絶対値が小さい状態を目指す
  minuslist = sorted(minuslist, reverse = True)
  ans = 1
  for i in range(K):
    ans *= minuslist[i]
    ans %= DIV
  print(ans)
  exit(0)
  
# 正の数を目指す
pluslist = sorted(pluslist, reverse = True)
minuslist = sorted(minuslist)
from collections import deque

plusq = deque(pluslist)
minusq = deque(minuslist)

ans = 1
# この時点で、正にすることが出来る。
# Kが奇数の場合、最低でも1回正の数を使う必要がある
if K % 2 == 1 and len(plusq) > 0:
  ans *= plusq.popleft() # 一番大きいものを取っておく
  K -= 1
  
for i in range(K // 2):
  p = 0
  m = 0
  if len(plusq) >= 2:
    p1 = plusq.popleft()
    p2 = plusq.popleft()
    p = p1 * p2
  if len(minusq) >= 2:
    m1 = minusq.popleft()
    m2 = minusq.popleft()
    m = m1 * m2
  if p == 0 and m == 0:
    ans *= (minusq.popleft() * plusq.popleft()) % DIV
    continue
  if m == 0:
    ans *= p % DIV
    ans %= DIV
    continue
  if p == 0:
    ans *= m % DIV
    ans %= DIV
    continue
  if p > m:
    ans *= (p1 * p2) % DIV
    ans %= DIV
    minusq.appendleft(m2)
    minusq.appendleft(m1)
  else:
    ans *= (m1 * m2) % DIV
    ans %= DIV
    plusq.appendleft(p2)
    plusq.appendleft(p1)

print(ans)

Submission status: Wrong Answer

Solution code:

MOD = 10**9 + 7
def maxProductSubarrayOfSizeK(A, n, k): 
  
    # sorting given input array 
    A.sort() 
    product = 1
    # print(A)
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k - 1, -1): 
            product = (product%MOD * A[i]%MOD)%MOD
        return product%MOD
    i = 0
    j = n - 1
  
    if (k & 1): 
        product = (product%MOD * A[j]%MOD)%MOD
        j-= 1
        k-=1
    k >>= 1
    for itr in range( k) :
        left_product = (A[i]%MOD * A[i + 1]%MOD )%MOD
        right_product = (A[j]%MOD * A[j - 1]%MOD )%MOD
  
    
        if (left_product > right_product) : 
            product = (product%MOD * left_product%MOD)%MOD
            i += 2
          
        else : 
            product = (product%MOD * right_product%MOD)%MOD
            j -= 2
  
   
    return product%MOD

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

ans = maxProductSubarrayOfSizeK(a,n,k)
print(ans%MOD)

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
	for j in range(K):
		ans = (ans * B[j][0]) % MOD
	print(ans)
else:
	n = M[i]
	p = K - M[i]
	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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
sA = sorted(A, reverse=True)

f = 0
b = -1
k = 0
if K == 1:
    print(max(sA))
    exit()

res = 1
m = max(sA)
while k < K:
    if m > 0 | (K % 2 == 0):
        if K - k >= 2:
            if A[f]*A[f+1] < A[b]*A[b-1]:
                res *= A[b]*A[b-1]
                b = b - 2
                k += 2
            else:
                res *= A[f]
                f = f + 1
                k += 1
        else:
            res *= A[f]
            f = f + 1
            k += 1
    else:
        k = K
        for a in range(K):
            res *= sA[a]

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:33:15 2020

"""

N, K = map(int,input().split())
A = list(map(int, input().split())) 
A = sorted(A, key=abs, reverse=True)
mod = 10**9+7
ans = 1
lp = 10**6
lm = 10**6
lpflag = 0
lmflag = 0
rp = 10**6
rm = 10**6
rpflag = 0
rmflag = 0
ans1 = 0
ans2 = 0
minus = 0
for i in range(K):
    if A[i] < 0:
        minus = (minus+1)%2
    ans = ans * A[i] % mod
if not minus:
    print(ans)
else:
    for i in range(K-1,-1,-1):
        if lp < 10**6 and lm < 10**6:
            break
        if A[i] > 0 and lpflag == 0:
            lpflag = 1
            lp = i
        elif A[i] < 0 and lmflag == 0:
            lmflag = 1
            lm = i
    for i in range(K,N):
        if rp < 10**6 and rm < 10**6:
            break
        if A[i] > 0 and rpflag == 0:
            rpflag = 1
            rp = i
        elif A[i] < 0 and rmflag == 0:
            rmflag = 1
            rm = i
    if lpflag*rmflag == 1:
        ans = 1
        for i in range(K):
            if not i == lp:
                ans = ans * A[i] % mod
        ans = ans * A[rm] % mod
        ans1 = ans
    if lmflag*rpflag == 1:
        ans = 1
        for i in range(K):
            if not i == lm:
                ans = ans * A[i] % mod
        ans = ans * A[rp] % mod    
        ans2 = ans
    if lpflag*rmflag == 0 and lmflag*rpflag == 0:
        ans = 1
        for i in range(N-1,N-1-K,-1):
            ans = ans * A[i] % mod
        print("")
    else:
        print(max(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import heapq
import sys

MOD = 10**9+7

n,k = map(int,input().split())
a = map(int,input().split())

a_plus=[]
a_minus=[]
a_zero = 0

for ai in a:
    if ai>0:
        heapq.heappush(a_plus, -ai)
    elif ai<0:
        heapq.heappush(a_minus, ai)
    else:
        a_zero += 1
        
if a_zero > n-k:
    print(0)
    sys.exit()
elif (len(a_minus)+a_zero == n and k%2 == 1) or (n==k and len(a_minus)%2 == 1):
    if a_zero>0:
        print(0)
        sys.exit()
    for _ in range(n-k):
        heapq.heappop(a_minus)
    ans = 1
    for _ in range(len(a_minus)):
        ans *= - heapq.heappop(a_minus)
        ans %= MOD
    for _ in range(len(a_plus)):
        ans *= - heapq.heappop(a_plus)
        ans %= MOD
    print(-ans % MOD)
    sys.exit()


ans = 1
last_plus = MOD
last_minus = MOD
sign = 1

for _ in range(k):
    if len(a_minus)==0 or (len(a_plus)>0 and a_plus[0] < a_minus[0]):
        last_plus = -heapq.heappop(a_plus)
        ans *= last_plus
    else:
        last_minus = -heapq.heappop(a_minus)
        ans *= last_minus
        sign *= -1
    
    ans %= MOD
if sign>0:
    print(ans)
else:
    heapq.heappush(a_plus,0)
    heapq.heappush(a_minus,0)
    
    if -a_plus[0] / last_minus > -a_minus[0] / last_plus:
        ans = ans * (-a_plus[0]) % MOD * pow(last_minus,MOD-2,MOD) % MOD
    else:
        ans = ans * (-a_minus[0]) % MOD * pow(last_plus,MOD-2,MOD) % MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n, k = map(int, input().split())
a = [int(item) for item in input().split()]
# Use all
if n == k:
    ans = 1
    for item in a:
        ans *= item
        ans %= MOD
    print(ans)
    exit()
plus = 0; minus = 0; zero = 0
p = []; m = []
for item in a:
    if item > 0:
        plus += 1
        p.append(item)
    elif item == 0:
        zero += 1
    else:
        minus += 1
        m.append(-item)
p.sort()
m.sort()
# plus only, minus only
if plus == 0:
    if zero:
        print(0)
        exit()
    ans = 1
    for item in m[:k]:
        ans *= -item
        ans %= MOD
    print(ans)
    exit()
if minus == 0:
    if plus >= k:
        ans = 1
        for i in range(k):
            ans *= p.pop()
            ans %= MOD
        print(ans)
        exit()
    else:
        print(0)
        exit()

# Can make it positive
if k <= (minus // 2) * 2 + plus:
    if k % 2 == 0:
        ans = 1
    else:
        ans = p.pop()
        k -= 1
    for i in range(k // 2):
        pval = 0; mval = 0
        if len(p) > 1:
            pval = p[-1] * p[-2]
        if len(m) > 1:
            mval = m[-1] * m[-2]
        if pval > mval:
            p.pop(); p.pop()
            ans *= pval
            ans %= MOD
        else:
            m.pop(); m.pop()
            ans *= mval
            ans %= MOD
    print(ans)
    exit()
# Cannot make positive
else:
    if zero > 0:
        print(0)
        exit()
    else:
        # Not occur
        exit()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
A.sort()
B = []
flag = False
F = False
tmp = 0
num = -1
ans = 1
tmp_ = -1
for i, a in enumerate(A):
    if a < 0:
        if flag:
            B.append(tmp * a)
            flag = False
        else:
            tmp = a
            flag = True
    elif a == 0:
        F = True
    else:
        tmp_ = tmp
        num = i
        break

if num == -1:
    if K % 2 == 1:
        for i, a in enumerate(A[::-1]):
            ans *= a
            ans %= mod
            if i == K-1:
                print(ans)
                exit()
    else:
        B.sort(reverse=True)
        K //= 2
        for i, b in enumerate(B):
            ans *= b
            ans %= mod
            if i == K-1:
                print(ans)
                exit()
A = A[num:]
A.sort(reverse=True)
if K % 2 == 1:
    ans = A[0]
    A = A[1:]
    K -= 1
ans %= mod
flag = False
for a in A:
    if flag:
        B.append(tmp * a)
        flag = False
    else:
        tmp = a
        flag = True
K //= 2
if len(B) < K:
    if F:
        print(0)
        exit()
    else:
        ans *= tmp_

B.sort(reverse=True)
for i, b in enumerate(B):
    if K == i:
        break
    ans *= b
    ans %= mod

print(ans % mod)

Submission status: Wrong Answer

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

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k=list(map(int,input().split()))
a=np.array(list(map(int,input().split())))

if len(a[a!=0])<k:
    print(0)
    
else:
    a_m = a[a<0]
    a_p = a[a>0]
    
    if len(a_m)%2==1:
        tmp = np.sort(a_m)[:-1]
        if len(a_m)+len(a_p)<k:
            a_m =np.sort(a_m)
        else:
            a_m =tmp

    a_n=np.append(a_p, a_m)

    ans_sum=np.sort(a_n)[::-1][:k]
    
    ans=1
    for i in ans_sum:
        ans = int(ans)*int(i)
    print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int, input().split())
A = list(map(int, input().split()))

num_plus, num_zero, num_minus = 0, 0, 0
for i in range(N):
  if A[i] < 0:
    num_minus += 1
  elif A[i] == 0:
    num_zero += 1
  else:
    num_plus += 1

if num_plus == N:	# すべてプラスの場合
  A.sort(reverse=True)
  ans = 1
  for i in range(K):
    ans *= (A[i]%(10**9+7))
  print(ans%(10**9+7))
elif num_minus == N:	# すべてマイナスの場合
  A.sort(reverse=True)
  ans = 1
  for i in range(K):
    ans *= (A[i]%(10**9+7))
  print(ans%(10**9+7))
elif K > num_plus+num_minus:	# 0が含まれる場合
  print(0)
else:
  B = abs(np.array(A))
  B_idx = np.argsort(B)
  ans = 1
  for i in range(K):
    idx = B_idx[N-1-i]
    ans *= (A[idx]%(10**9+7))
  print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
import itertools

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

A = sorted(A)

print(-1 / (10 ** 9 + 7))


if N <= K * 2:
    cand = A
else:
    cand = A[:K] + A[-K:]

max_num = -float('inf')
for comb in itertools.combinations(cand, K):
    r = 1
    for i in comb:
        r *= i
    if max_num < r:
        max_num = r

if 0 <= max_num:
    print(max_num % (10 ** 9 + 7))
else:
    print(10 ** 9 + 7 + max_num)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from functools import total_ordering

MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    B = [Num(A[i]) for i in range(N)]
    B.sort(reverse=True)
    sign = 1
    ret = 1
    if N == 1:
        print(B[0].getNum() % MOD)
        return
    for i in range(K):
        sign *= B[i].getSign()
        ret *= B[i].getNum() % MOD
        ret %= MOD
    if sign > 0:
        print(ret)
        return
    elif sign < 0:
        minP = -1
        minP_i = 0
        minM = 1
        minM_i = 0
        for i in range(K - 1, -1, -1):
            if B[i].getSign() > 0:
                minP = B[i].getNum()
                minP_i = i
                break
        else:
            minP = 10 ** 10
        for i in range(K - 1, -1, -1):
            if B[i].getSign() < 0:
                minM = B[i].getNum()
                minM_i = i
                break
        else:
            minM = 10 ** 10
        maxP = -1
        maxP_i = 0
        maxM = 1
        maxM_i = 0
        for i in range(K, N):
            if B[i].getSign() > 0:
                maxP = B[i].getNum()
                maxP_i = i
                break
        else:
            maxP = 0
        for i in range(K, N):
            if B[i].getSign() < 0:
                maxM = B[i].getNum()
                maxM_i = i
                break
        else:
            maxM = 0
        x = abs(maxM) / abs(minP)   
        y = abs(maxP) / abs(minM)
        ret_new = 1
        if x > y:
            for i in range(K):
                if i != minP_i:
                    ret_new *= B[i].getNum() % MOD
                    ret_new %= MOD
            ret_new *= B[maxM_i].getNum() % MOD
            ret_new %= MOD
        else:
            for i in range(K):
                if i != minM_i:
                    ret_new *= B[i].getNum() % MOD
                    ret_new %= MOD
            ret_new *= B[maxP_i].getNum() % MOD
            ret_new %= MOD
        print(ret_new)
    else:
        print(0)
        return


@total_ordering
class Num:
    def __init__(self, num):
        self.num = num
        self.sign = (num > 0) - (num < 0)
    
    def __eq__(self, value):
        return abs(self.num) == abs(value.num)
    
    def __lt__(self, value):
        return abs(self.num) < abs(value.num)

    def getNum(self):
        return self.num

    def getSign(self):
        return self.sign

# 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()))
MOD = 10 ** 9 + 7

if K == 1:
    ans = max(A)
elif N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
elif max(A) <= 0 and K % 2 == 1:
    A.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    A.sort(key=abs)

    ans = 1
    for _ in range(K - 2):
        ans *= A.pop()
        ans %= MOD

    A.sort()

    ans = max(ans * A[0] * A[1], ans * A[0] * A[-1], ans * A[-2] * A[-1])
    ans %= MOD


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
d=deque(A)

l=[]
if K%2==0 or (K%2==1 and A[0]>=0):
  for i in range(K//2):
    if d[0]*d[1]>d[-1]*d[-2] and len(d)>2 and d[2]>0:
      l.append(d.popleft())
      l.append(d.popleft())
    else:
      l.append(d.pop())
      l.append(d.pop())
  if K%2==1:
    l.append(d[0])
else:
  for i in range(K):
    l.append(d.popleft())
      
ans=1
for i in l:
  ans*=i
  ans%=10**9+7
print(ans%(10**9+7))

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:
    ans1=ans
    for i in range(k,n):
        if a1[i][1]>=0:
            ans1=max(ans*(pow(a1[n1][1],mod-2,mod))*a1[i][1],ans1)
            c=1
        if a1[i][1]<0 and p!=-1:
            ans1=max(ans*pow(a1[p][1],mod-2,mod)*a1[i][1],ans1)
            c=1
    ans=ans1
    if c<0:
        ans=1
        for i in range(k):
            ans = (ans*a1[n-i-1][1])%mod
    out(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
from math import log2
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N, K = MAP()
A = LIST()

A1 = []
A2 = []
B1 = []
B2 = []
zero = 0
for a in A:
    if a > 0:
        A1.append(a)
        B1.append(log2(a))
    elif a < 0:
        A2.append(-a)
        B2.append(log2(-a))
    else:
        zero += 1

A1.sort()
A2.sort()
B1.sort()
B2.sort()
acc1 = [0] + list(accumulate(B1))
accrev1 = [0] + list(accumulate(B1[::-1]))
acc2 = [0] + list(accumulate(B2))
accrev2 = [0] + list(accumulate(B2[::-1]))
mx = -INF
mn = INF
idx1 = (-1, -1)
idx2 = (-1, -1)
for i in range(K+1):
    j = K - i
    if len(B1) < i or len(B2) < j:
        continue
    if j % 2 == 0:
        sm = accrev1[i] + accrev2[j]
        if sm > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn:
            mn = sm
            idx2 = (i, j)

if mx != -INF:
    ans = 1
    n, m = idx1
    A1.reverse()
    A2.reverse()
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)
elif zero:
    print(0)
else:
    ans = 1
    n, m = idx2
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        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
m=[]
p=[]
for i in range(n):
    if a[i]<0:
        m.append(a[i])
    else:
        p.append(a[i])
m.sort(reverse=True)
p.sort()
ans=1

if len(m)==n and k%2==1:
    for i in range(k):
        ans*=m[i]
elif k==1:
    ans=p[-1]

else:
    for i in range(k-2):
        if len(m)==0:
            ans*=p.pop()
        elif len(p)==0:
            ans*=m.pop()
        else:
            if abs(m[-1])<p[-1]:
                ans*=p.pop()
            else:
                ans*=m.pop()

    if len(p)>1 and len(m)>1:
        ans*=max(p[-1]*m[-1],p[-1]*p[-2],m[-1]*m[-2])
    if len(p)==1 and len(m)>1:
        ans*=max(p[-1]*m[-1],m[-1]*m[-2])
    if len(p)>1 and len(m)==1:
        ans*=max(p[-1]*m[-1],p[-1]*p[-2])
    if len(p)==1 and len(m)==1:
        ans*=p[-1]*m[-1]
    if len(p)==0:
        ans*=m[-1]*m[-2]
    if len(m)==0:
        ans*=p[-1]*p[-2]

print(ans%mod)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort()
large = 10**9 + 7
num_minus = 0
for k in range(N):
    if a[k] < 0:
        num_minus += 1
if num_minus == N and K%2 == 1:
    ans = 1
    for i in range(K):
        #print(a[K-1-i],K-1-i)
        ans *= a[N-1-i]
        ans = ans % large
    print(ans)
    exit()

large = 10**9 + 7

i_left = 0
i_right = N-1

if K == 1:
    print(a[i_right])
    exit()
ans = 1



while K > 1:
    #print(i_right,i_left)
    if a[i_right]*a[i_right-1] >= a[i_left]*a[i_left+1]:
        ans = ans * a[i_right]
        ans = ans % large
        ans = ans * a[i_right-1]
        ans = ans % large
        i_right -= 2
    else:
        ans = ans * a[i_left]
        ans = ans % large
        ans = ans * a[i_left+1]
        ans = ans % large
        i_left += 2
    K -= 2

if K == 0:
    print(ans)
else:
    ans = ans * a[i_right]
    ans = ans % large
    print(ans)