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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, k = LI()
A = LI()
flg = 1 if max(A) < 0 and k % 2 else 0
X = sorted(A, key=lambda x:abs(x), reverse=False if flg else True)
ans = 1
fflg = 0
t1 = INF
t2 = 1
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
        t2 = min(t2, X[i])
    elif X[i] > 0:
        t1 = min(t2, X[i])

if t1 == INF:
    t1 = 1

rem = []
r1 = 1
r2 = 1
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    if X[ii] > 0:
        rem_plus = 1
        r1 = max(X[ii], r1)
    elif X[ii] < 0:
        rem_minus = 1
        r2 = min(X[ii], r2)


if r1 / t2 > r2 / t1:
    ans = ans * pow(t1, mod - 2, mod) * r2
else:
    ans = ans * pow(t2, mod - 2, mod) * r1




if fflg:
    ans = -ans
print(ans % mod)

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC173
# Problem No.: E
# Solver:      JEMINI
# Date:        20200705

import sys
import heapq

def main():
    modVal = 10 ** 9 + 7
    n, k = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    
    if n == k:
        ans = 1
        for i in nums:
            ans *= i % modVal
            ans %= modVal
        print(ans)
        return

    if max(nums) < 0:
        nums.sort()
        ans = 1
        for i in range(k):
            ans *= nums[-i - 1] % modVal
            ans %= modVal
        print(ans)
        return
    
    absNums = []
    zeroCnt = 0
    for i in nums:
        if i == 0:
            zeroCnt += 1
        else:
            absNums.append([abs(i), i])
    absNums.sort()
    
    if len(absNums) < k:
        print(0)
        return

    posOverK = []
    posLessK = []
    negOverK = []
    negLessK = []
    for i in range(k):
        temp = absNums.pop()
        if temp[1] > 0:
            posOverK.append(temp[0])
        else:
            negOverK.append(temp[0])
    while absNums:
        temp = absNums.pop()
        if temp[1] > 0:
            posLessK.append(temp[0])
        else:
            negLessK.append(temp[0])
    
    # all values are abs val
    posOverK.sort()
    posLessK.sort()
    negOverK.sort()
    negLessK.sort()
    ans = 1

    # odd negative numbers
    if len(negOverK) % 2:
        minNeg = None
        minPos = None
        if posOverK:
            minPos = posOverK[0]
        if negOverK:
            minNeg = negOverK[0]

        maxNeg = None
        maxPos = None
        if posLessK:
            maxPos = posLessK[-1]
        if negLessK:
            maxNeg = negLessK[-1]
        
        if (minNeg and maxPos) and (minPos and maxNeg):
            if maxPos / minNeg > maxNeg / minPos:
                negOverK[0] = maxPos
            else:
                posOverK[0] = maxNeg
        elif (not minNeg or not maxPos) and (minPos and maxNeg):
            posOverK[0] = maxNeg
        elif (minNeg and maxPos) and (not minPos or not maxNeg):
            negOverK[0] = maxPos
        elif zeroCnt:
            print(0)
            return
    
    for i in posOverK:
        ans *= i % modVal
        ans = ans % modVal
    for i in negOverK:
        ans *= i % modVal
        ans = ans % modVal
    
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = int(1e9+7)

A = np.array(sorted(A, reverse=True, key=lambda x: abs(x)))
if sum(np.sign(A)) == -N and K%2 == 1:
    A = sorted(A, reverse=True)
last_p = 0
last_m = 0
eliminate_m = 0
eliminate_p = 0
add_m = 0
add_p = 0
ans = 1
for i in range(N):
    if i < K:
        # ans = (ans * A[i])%mod
        if A[i] > 0:
            ans = (ans*last_p)%mod
            last_p = A[i]
        else:
            ans = (ans*last_m)%mod
            last_m = A[i]
    else:
        if A[i] > 0 and eliminate_m == 0:
            eliminate_m = last_p * A[i]
            add_p = A[i]
        elif A[i] < 0 and eliminate_p == 0:
            eliminate_p = last_m * A[i]
            add_m = A[i]
    if i == K-1:
        if ans < 0 or K == N:
            ans = (ans*last_p)%mod
            ans = (ans*last_m)%mod
            break
if eliminate_p > 0 or eliminate_m > 0:
    if eliminate_m > eliminate_p:
        ans = (ans*eliminate_m%mod)%mod
        # ans = (ans*pow(last_m, mod-2))%mod
        # ans = (ans*add_p)%mod
    else:
        # ans = (ans*pow(last_p, mod-2))%mod
        # ans = (ans*add_m)%mod
        ans = (ans*eliminate_p%mod)%mod

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = int(1e9+7)

A = np.array(sorted(A, reverse=True, key=lambda x: abs(x)))
if sum(np.sign(A)) == -N and K%2 == 1:
    A = sorted(A, reverse=True)
last_p = 0
last_m = 0
eliminate_m = 0
eliminate_p = 0
add_m = 0
add_p = 0
ans = 1
for i in range(N):
    if i < K:
        # ans = (ans * A[i])%mod
        if A[i] > 0:
            ans = (ans*last_p)*mod
            last_p = A[i]
        else:
            ans = (ans*last_m)*mod
            last_m = A[i]
    else:
        if A[i] > 0 and eliminate_m == 0:
            eliminate_m = last_p * A[i]
            add_p = A[i]
        elif A[i] < 0 and eliminate_p == 0:
            eliminate_p = last_m * A[i]
            add_m = A[i]
    if i == K-1:
        if ans < 0 or K == N:
            ans = (ans*last_p)%mod
            ans = (ans*last_m)%mod
            break
if eliminate_p > 0 or eliminate_m > 0:
    if eliminate_m > eliminate_p:
        ans = (ans*eliminate_m%mod)%mod
        # ans = (ans*pow(last_m, mod-2))%mod
        # ans = (ans*add_p)%mod
    else:
        # ans = (ans*pow(last_p, mod-2))%mod
        # ans = (ans*add_m)%mod
        ans = (ans*eliminate_p%mod)%mod


print(ans)

Submission status: Wrong Answer

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

mod = 10**9+7

mi = []
pl = []
for a in A:
    if a < 0:
        mi.append(a)
    else:
        pl.append(a)

if pl == []:
    if K%2:
        ans = 1
        for k in range(K):
            ans *= mi[-1-k]
            ans %= mod
    else:
        ans = 1
        for k in range(K):
            ans *= mi[k]
            ans %= mod
    print(ans)
    exit()

pl = pl[::-1]

ip = 0
im = 0
ans = 1
if K % 2:
    ans = pl[0]
    ip += 1
    K -= 1

while K > 0:
    check = True
    if ip + 2 <= len(pl):
        x = pl[ip]*pl[ip+1]
    else:
        x = 1
    if im + 2 <= len(mi):
        y = mi[im]*mi[im+1]
    else:
        check = False
        y = 1

    if x >= y or check == False:
        ans *= x
        ans %= mod
        ip += 2
    else:
        ans *= y
        ans %= mod
        im += 2
    K -= 2
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)

res = 1
if k == 1:
    res = max(a)
elif k == n:
    res = 1
    for e in a:
        res *= e
        res %= MOD
elif max(a) < 0:
    if k % 2 == 1:
        for i in range(n - k, n):
            res *= a[i]
            res %= MOD
    else:
        for i in range(k):
            res *= a[i]
            res %= MOD
else:
    prev_minus_value = 0
    prev_plus_value = -1
    mul_cnt = 0
    idx = 0
    while mul_cnt < k:
        if a[idx] < 0:
            if prev_minus_value == 0:
                prev_minus_value = a[idx]
            else:
                if mul_cnt == k - 1:
                    mul_minus_value = prev_plus_value * a[idx]

                    if prev_plus_value != -1:
                        next_plus_value = -1
                        for i in range(idx + 1, n):
                            if a[i] >= 0:
                                next_plus_value = a[i]
                                break

                        if next_plus_value != -1:
                            if prev_plus_value * next_plus_value > mul_minus_value:
                                res *= next_plus_value
                                res %= MOD
                                break

                    res *= pow(prev_plus_value, MOD - 2, MOD)
                    res *= mul_minus_value
                    res %= MOD
                    break

                res *= prev_minus_value * a[idx]
                res %= MOD
                prev_minus_value = 0
                mul_cnt += 2
        else:
            res *= prev_minus_value * a[idx]
            res %= MOD
            prev_plus_value = a[idx]
            mul_cnt += 1

        idx += 1

print(res)

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC173
# Problem No.: E
# Solver:      JEMINI
# Date:        20200705

import sys
import heapq

def main():
    modVal = 10 ** 9 + 7
    n, k = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    
    if n == k:
        ans = 1
        for i in nums:
            ans *= i % modVal
            ans %= modVal
        print(ans)
        return

    if max(nums) == 0:
        print(0)
        return
    elif max(nums) < 0:
        nums.sort()
        ans = 1
        for i in range(k):
            ans *= nums[-i - 1] % modVal
            ans %= modVal
        print(ans)
        return
    
    absNums = []
    zeroCnt = 0
    for i in nums:
        if i == 0:
            zeroCnt += 1
        else:
            absNums.append([abs(i), i])
    absNums.sort()
    
    if len(absNums) < k:
        print(0)
        return

    posOverK = []
    posLessK = []
    negOverK = []
    negLessK = []
    for i in range(k):
        temp = absNums.pop()
        if temp[1] > 0:
            posOverK.append(temp[0])
        else:
            negOverK.append(temp[0])
    while absNums:
        temp = absNums.pop()
        if temp[1] > 0:
            posLessK.append(temp[0])
        else:
            negLessK.append(temp[0])
    
    # all values are abs val
    posOverK.sort()
    posLessK.sort()
    negOverK.sort()
    negLessK.sort()
    ans = 1

    # odd negative numbers
    if len(negOverK) % 2:
        minNeg = None
        minPos = None
        if posOverK:
            minPos = posOverK[0]
        if negOverK:
            minNeg = negOverK[0]

        maxNeg = None
        maxPos = None
        if posLessK:
            maxPos = posLessK[-1]
        if negLessK:
            maxNeg = negLessK[-1]
        
        if (minNeg and maxPos) and (minPos and maxNeg):
            if maxPos / minNeg > maxNeg / minPos:
                negOverK[0] = maxPos
            else:
                posOverK[0] = maxNeg
        elif (not minNeg or not maxPos) and (minPos and maxNeg):
            posOverK[0] = maxNeg
        elif (minNeg and maxPos) and (not minPos or not maxNeg):
            negOverK[0] = maxPos
        elif zeroCnt:
            print(0)
            return
    
    for i in posOverK:
        ans *= i % modVal
        ans = ans % modVal
    for i in negOverK:
        ans *= i % modVal
        ans = ans % modVal
    
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

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


arr = [ int(i) for i in input().split() ]

arr = sorted(arr)

mod = (10**9)+7

pre = [ 0 for i in range(n) ]
suff = [ 0 for i in range(n+1) ]

pre[0] = arr[0]

for i in range(1, n):
	pre[i] = pre[i-1] * arr[i]
	pre[i] %= mod 

suff[n] = 1
suff[n-1] = arr[n-1]

for i in range(n-2,-1,-1):
	suff[i] = suff[i+1] * arr[i]
	suff[i] %= mod

max_ans = suff[n-k]

# print(pre)
# print(suff)

for i in range(k):
	fromLeft = k - i 
	ans = pre[i] * suff[n-fromLeft + 1]
	max_ans = max(max_ans, ans)
max_ans %= mod
print(max_ans)

Submission status: Wrong Answer

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

B=[]
for i in range(n):
    num=A[i]
    B.append([abs(num),num])
B.sort(reverse=True)

C=[]
ans,flag=1,1
for i in range(k):
    num=B[i][1]
    if num<0:flag *=-1
    ans *=num
    ans %=mod
    C.append(num)

if flag==1:print(ans);exit()

plus,negative=0,0
for i in range(k,n):
    if plus!=0 and negative!=0:break
    num=B[i][1]
    if num>0 and plus==0:plus=num
    elif num<0 and negative==0:negative=num

if plus==0 and negative!=0:
    ans=1
    for i in range(k):
        ans *=B[-(i+1)][1]
        ans %=mod
    print(ans)
elif plus!=0 and negative==0:
    ans=1
    index=0
    for i in range(k):
        num=C[i]
        if num<0:index=i
    C[index]=plus
    for i in range(k):
        ans *=C[i]
        ans %=mod
    print(ans)
elif plus!=0 and negative!=0:
    x,y=0,0
    for i in range(k):
        num=C[i]
        if num>0:x=i
        else:y=i
    test1,test2=1,1
    for i in range(k):
        if i==x:
            test1 *=negative
            test2 *=C[i]
        elif i==y:
            test1 *=C[i]
            test2 *=plus
        else:
            test1 *=C[i]
            test2 *=C[i]
        test1 %=mod
        test2 %=mod
    print(max(test1,test2))
else:print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = int(1e9+7)

A = np.array(sorted(A, reverse=True, key=lambda x: abs(x)))
if sum(np.sign(A)) == -N and K%2 == 1:
    A = sorted(A, reverse=True)
last_p = 0
last_m = 0
eliminate_m = 0
eliminate_p = 0
add_m = 0
add_p = 0
ans = 1
for i in range(N):
    if i < K:
        # ans = (ans * A[i])%mod
        if A[i] > 0:
            ans = (ans*last_p)%mod
            last_p = A[i]
            # last_p = i
        else:
            ans = (ans*last_m)%mod
            last_m = A[i]
            # last_m = i
    else:
        if A[i] > 0 and eliminate_m == 0:
            eliminate_m = last_p * A[i]
            add_p = A[i]
        elif A[i] < 0 and eliminate_p == 0:
            eliminate_p = last_m * A[i]
            add_m = A[i]
    if i == K-1:
        if ans < 0:
            break
if ans < 0 :
    ans = (ans*last_p)%mod
    ans = (ans*last_m)%mod
if eliminate_p > 0 or eliminate_m > 0:
    if eliminate_m > eliminate_p:
        # ans = (ans*pow(A[last_m], mod-2))%mod
        # ans = (ans*add_p)%mod
        ans = (ans*eliminate_m%mod)%mod
    else:
        # ans = (ans*pow(A[last_p], mod-2))%mod
        # ans = (ans*add_m)%mod
        ans = (ans*eliminate_p%mod)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC173
# Problem No.: E
# Solver:      JEMINI
# Date:        20200705

import sys
import heapq

def main():
    modVal = 10 ** 9 + 7
    n, k = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    
    if n == k:
        ans = 1
        for i in nums:
            ans *= i % modVal
            ans %= modVal
        print(ans)
        return

    if max(nums) == 0:
        print(0)
        return
    elif max(nums) < 0:
        nums.sort()
        ans = 1
        for i in range(k):
            ans *= nums[-i - 1] % modVal
            ans %= modVal
        print(ans)
        return
    
    absNums = []
    zeroCnt = 0
    for i in nums:
        if i == 0:
            zeroCnt += 1
        else:
            absNums.append([abs(i), i])
    absNums.sort()
    
    if len(absNums) < k:
        print(0)
        return

    posOverK = []
    posLessK = []
    negOverK = []
    negLessK = []
    for i in range(k):
        temp = absNums.pop()
        if temp[1] > 0:
            posOverK.append(temp[0])
        else:
            negOverK.append(temp[0])
    while absNums:
        temp = absNums.pop()
        if temp[1] > 0:
            posLessK.append(temp[0])
        else:
            negLessK.append(temp[0])
    
    # all values are abs val
    posOverK.sort()
    posLessK.sort()
    negOverK.sort()
    negLessK.sort()
    # print(posOverK)    
    # print(posLessK)
    # print(negOverK)
    # print(negLessK)    
    ans = 1

    # odd negative numbers
    if len(negOverK) % 2:
        minNeg = None
        minPos = None
        if posOverK:
            minPos = posOverK[0]
        if negOverK:
            minNeg = negOverK[0]

        maxNeg = None
        maxPos = None
        if posLessK:
            maxPos = posLessK[-1]
        if negLessK:
            maxNeg = negLessK[-1]
        
        if (minNeg and maxPos) and (minPos and maxNeg):
            if maxPos / minNeg > maxNeg / minPos:
                negOverK[0] = maxPos
            else:
                posOverK[0] = maxNeg
        elif (not minNeg or not maxPos) and (minPos and maxNeg):
            posOverK[0] = maxNeg
        elif (minNeg and maxPos) and (not minPos or not maxNeg):
            negOverK[0] = maxPos
        elif zeroCnt:
            ans = 0
        # print(posOverK)    
        # print(posLessK)
        # print(negOverK)
        # print(negLessK)    
    
    for i in posOverK:
        ans *= i % modVal
        ans = ans % modVal
    for i in negOverK:
        ans *= i % modVal
        ans = ans % modVal
    
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, k = LI()
A = LI()
flg = 1 if max(A) < 0 and k % 2 else 0
X = sorted(A, key=lambda x:abs(x), reverse=False if flg else True)
ans = 1
L = []
fflg = 0
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
    L += [X[i]]

rem = []
r1 = 0
r2 = 0
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    if X[ii] > 0:
        rem_plus = 1
        r1 = max(X[ii], 0)
    elif X[ii] < 0:
        rem_minus = 1
        r2 = max(abs(X[ii]), 0)

if fflg:
    for jj in range(len(L)-1, -1, -1):
        if L[jj] < 0 and rem_plus:
            ans = -ans * pow(L[jj], mod - 2, mod) % mod
            ans *= r1
            fflg ^= 1
            break
        elif L[jj] > 0 and rem_minus:
            -ans * pow(L[jj], mod - 2, mod) % mod
            ans *= r2
            fflg ^= 1
            break

if fflg:
    ans = -ans
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import unittest
from io import StringIO
#import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    MOD = 10**9+7

    def prod(iter):
        ret = 1
        for i in range(len(iter)):
            ret *= iter[i]
            ret %= MOD
        return ret % MOD

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

    if k == n:
        print(prod(A))
    else:
        minus = 0
        plus = 0
        for i in A:
            if i < 0:
                minus += 1
            else:
                plus += 1
        if minus == n and k % 2 == 1:
            A.sort(reverse=True)
            print(prod(A[:k]))
        else:
            A.sort(key=abs, reverse=True)
            p = prod(A[:k])
            if p >= 0:
                print(p)
            else:
                ans=p
                Mplus = -1
                mminus = 1
                for i in range(k):
                    if A[i]<0:
                        mminus = min(mminus, A[i])
                for i in range(k, n):
                    if A[i]>=0:
                        Mplus = max(Mplus, A[i])
                if mminus<0 and Mplus>=0:
                    ans = p//mminus*Mplus

                INF = 10**10

                mplus = INF
                Mminus = -INF
                for i in range(k):
                    if A[i]>=0:
                        mplus = min(mplus, A[i])
                for i in range(k, n):
                    if A[i]<0:
                        Mminus = max(Mminus, A[i])
                
                ans = max(ans, p//mplus*Mminus)

                print(ans%MOD)


resolve()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
phold = -1
nhold = 1
cnt = 0
pv = -10**10
nv = -10**10

if max(a) <= 0:
    a = sorted(a)[::-1]
    for i in range(k):
        ans = ans*a[i]%(10**9 + 7)
    print(ans)
    exit()

a = sorted(a, key = abs)[::-1]

for i in range(n):
    if cnt >= k - 2:
        break
    if a[i] >= 0:
        if phold == -1:
            phold = a[i]
        else:
            ans = ans*phold%(10**9 + 7)
            phold = a[i]
            cnt += 1
    else:
        if nhold == 1:
            nhold = a[i]
        else:
            ans = ans*nhold*a[i]%(10**9 + 7)
            nhold = 1
            cnt += 2

for j in range(i, n):
    if cnt == k - 1: #残り1つなら
        if phold != -1: #正の値を持っていれば確定
            ans = ans*phold%(10**9 + 7)
            print(ans)
            exit()
        else: #正の値を探してくる。（全てマイナスバターンは除去済）
            if a[j] >= 0:
                ans = ans*a[j]%(10**9 + 7)
                print(ans)
                exit()
    else: #残り2つなら、正2つと負2つの積を比較
        if pv != -10**10 and nv != -10**10:
            ans = ans*max(pv, nv)%(10**9 + 7)
            print(ans)
            exit()
        else:
            if j == n - 1:
                if pv == -10**10:
                    if a[j] >= 0:
                        pv = a[j]
                    ans = ans*max(pv, nv)%(10**9 + 7)
                    print(ans)
                    exit()
                else:
                    if a[j] < 0:
                        nv = a[j]
                    ans = ans*max(pv, nv)%(10**9 + 7)
                    print(ans)
                    exit()
            if a[j] >= 0:
                if phold == -1:
                    phold = a[j]
                elif phold != -1 and pv == -10**10:
                    pv = phold*a[j]
            else:
                if nhold == 1:
                    nhold = a[j]
                elif nhold != 1 and nv == -10**10:
                    nv = nhold*a[j]

Submission status: Wrong Answer

Solution code:

def main():
  n, k = map(int, input().split())

  plus = [0] * n
  minus = [0] * n
  pn = mn = 0

  for num in input().split():
    num = int(num)
    if num >= 0:
      plus[pn] = num
      pn += 1
    else:
      minus[mn] = num
      mn += 1

  mod = 10 ** 9 + 7

  if pn == 0 and k % 2 == 1:
    minus.sort(reverse = True)
    ans = 1
    for i in range(k):
      ans = (-ans * minus[i]) % mod

    print((-ans) % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pi = 0
  mi = 0

  while k > 0:
    if pi + 1 == pn:
      if k % 2 == 0:
        mi += k
      else:
        pi += 1
        mi += k - 1

      break

    if pi == pn:
      mi += k
      break

    if mi + 1 >= mn:
      pi += k
      break

    if mi == mn:
      pi += k
      break

    if plus[pi] * plus[pi + 1] >= minus[mi] * minus[mi + 1]:
      pi += 1
      k -= 1
    else:
      mi += 2
      k -= 2

  ans = 1
  for i in range(pi):
    ans = (ans * plus[i]) % mod

  for i in range(mi):
    ans = (-ans * minus[i]) % mod

  print(ans % mod)


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, k = LI()
A = LI()
flg = 1 if max(A) < 0 and k % 2 else 0
X = sorted(A, key=lambda x:abs(x), reverse=False if flg else True)
ans = 1
L = []
fflg = 0
for i in range(k):
    ans = ans * abs(X[i]) % mod
    if X[i] < 0:
        fflg ^= 1
    L += [X[i]]

rem = []
r1 = 0
r2 = 0
rem_minus = 0
rem_plus = 0
for ii in range(k, n):
    rem += [A[ii]]
    if A[ii] > 0:
        rem_plus = 1
        r1 = max(A[ii], 0)
    elif A[ii] < 0:
        rem_minus = 1
        r2 = max(abs(A[ii]), 0)

if fflg:
    for jj in range(len(L)-1, -1, -1):
        if L[jj] < 0 and rem_plus:
            ans = -ans * pow(L[jj], mod - 2, mod) % mod
            ans *= r1
            fflg ^= 1
            break
        elif L[jj] > 0 and rem_minus:
            -ans * pow(L[jj], mod - 2, mod) % mod
            ans *= r2
            fflg ^= 1
            break

if fflg:
    ans = -ans
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    MOD = 10**9+7

    def prod(iter):
        ret = 1
        for i in range(len(iter)):
            ret *= iter[i]
            ret %= MOD
        return ret % MOD

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

    if k == n:
        print(prod(A))
    else:
        minus = 0
        plus = 0
        for i in A:
            if i < 0:
                minus += 1
            else:
                plus += 1
        if minus == n and k % 2 == 1:
            A.sort(reverse=True)
            print(prod(A[:k]))
        else:
            A.sort(key=abs, reverse=True)
            p = prod(A[:k])
            if p >= 0:
                print(p)
            else:
                ans=p
                Mplus = 0
                mminus = 0
                for i in range(k):
                    mminus = min(mminus, A[i])
                for i in range(k, n):
                    Mplus = max(Mplus, A[i])
                if mminus<0 and Mplus>0:
                    ans = p//mminus*Mplus

                INF = 10**10

                mplus = INF
                Mminus = -INF
                for i in range(k):
                    if A[i]>0:
                        mplus = min(mplus, A[i])
                for i in range(k, n):
                    if A[i]<0:
                        Mminus = max(Mminus, A[i])
                
                ans = max(ans, p//mplus*Mminus)

                print(ans%MOD)


resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = int(1e9+7)

A = np.array(sorted(A, reverse=True, key=lambda x: abs(x)))
if sum(np.sign(A)) == -N and K%2 == 1:
    A = sorted(A, reverse=True)
last_p = 0
last_m = 0
eliminate_m = 0
eliminate_p = 0
add_m = 0
add_p = 0
ans = 1
for i in range(N):
    if i < K:
        ans = (ans * A[i])%mod
        if A[i] > 0:
            last_p = i
        else:
            last_m = i
    else:
        if A[i] > 0 and eliminate_m == 0:
            eliminate_m = A[last_p] * A[i]
            add_p = A[i]
        elif A[i] < 0 and eliminate_p == 0:
            eliminate_p = A[last_m] * A[i]
            add_m = A[i]
    if i == K-1:
        if ans > 0:
            break
if eliminate_p > 0 or eliminate_m > 0:
    if eliminate_m > eliminate_p:
        ans = (ans*pow(A[last_m], mod-2))%mod
        ans = (ans*add_p)%mod
    else:
        ans = (ans*pow(A[last_p], mod-2))%mod
        ans = (ans*add_m)%mod

print(ans)