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 deque
import sys
input=sys.stdin.readline

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

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>=0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    num=0
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if B[0]>negative:
                ans *=B.popleft()
                num=1
            elif plus>negative:ans *=B.popleft()*B.popleft()
            else:ans *=C.popleft()*C.popleft()
        elif length_C>=2:ans *=C.popleft()*C.popleft()
        elif length_B>=2:ans *=B.popleft()*B.popleft()
        else:
            ans *=B.popleft()*C.popleft()
            flag=0
        k -=2-num
    else:
        if 0<length_B:
            ans *=B.popleft()
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
        k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    ans %=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

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

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>=0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if B[0]>negative:
                ans *=B.popleft()
                k -=1
                break
            elif plus>negative:ans *=B.popleft()*B.popleft()
            else:ans *=C.popleft()*C.popleft()
        elif length_C>=2:ans *=C.popleft()*C.popleft()
        elif length_B>=2:ans *=B.popleft()*B.popleft()
        else:
            ans *=B.popleft()*C.popleft()
            flag=0
        k -=2
    else:
        if 0<length_B:
            ans *=B.popleft()
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
        k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    ans %=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

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

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>=0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if plus>negative:ans *=B.popleft()*B.popleft()
            else:ans *=C.popleft()*C.popleft()
        elif length_C>=2:ans *=C.popleft()*C.popleft()
        elif length_B>=2:ans *=B.popleft()*B.popleft()
        else:
            ans *=B.popleft()*C.popleft()
            flag=0
        k -=2
    else:
        if 0<length_B:
            ans *=B.popleft()
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
        k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    ans %=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

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

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>=0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if length_C==2:ans *=C.popleft()*C.popleft()
            elif plus>negative:ans *=B.popleft()*B.popleft()
            else:ans *=C.popleft()*C.popleft()
        elif length_C>=2:ans *=C.popleft()*C.popleft()
        elif length_B>=2:ans *=B.popleft()*B.popleft()
        k -=2
    else:
        if 0<length_B:
            ans *=B.popleft()
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
        k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    ans %=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

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

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>=0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if plus>negative:ans *=B.popleft()*B.popleft()
            else:ans *=C.popleft()*C.popleft()
        elif length_C>=2:ans *=C.popleft()*C.popleft()
        elif length_B>=2:ans *=B.popleft()*B.popleft()
        k -=2
    else:
        if 0<length_B:
            ans *=B.popleft()
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
        k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    ans %=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

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

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if plus>negative:ans *=B.popleft()*B.popleft()
            else:ans *=C.popleft()*C.popleft()
        elif length_C>=2:ans *=C.popleft()*C.popleft()
        elif length_B>=2:ans *=B.popleft()*B.popleft()
        k -=2
    else:
        if 0<length_B:
            ans *=B.popleft()
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
        k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
index=0
while cnt!=0:
    num=A[index]
    if num==0:continue
    ans *=num
    ans %=mod
    index +=1
    cnt -=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

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

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if plus>negative:ans *=B.popleft()*B.popleft()
            else:ans *=C.popleft()*C.popleft()
        elif length_C>=2:ans *=C.popleft()*C.popleft()
        elif length_B>=2:ans *=B.popleft()*B.popleft()
        k -=2
    else:
        if 0<length_B:
            ans *=B.popleft()
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
        k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    ans %=mod
print(ans)

Submission status: Wrong Answer

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

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if plus>negative:ans *=B.popleft()*B.popleft()
            else:ans *=C.popleft()*C.popleft()
            k -=2
        elif length_C>=2:
            ans *=C.popleft()*C.popleft()
            k -=2
        elif length_B>=2:
            ans *=B.popleft()*B.popleft()
            k -=2
    else:
        if 0<length_B:
            ans *=B.popleft()
            k -=1
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
            k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    ans %=mod
print(ans)

Submission status: Wrong Answer

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

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    if k>=2:
        if len(B)>=2 and len(C)>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if plus>negative:ans *=B.popleft()*B.popleft()
            else:ans *=C.popleft()*C.popleft()
            k -=2
        elif len(C)>=2:
            ans *=C.popleft()*C.popleft()
            k -=2
        elif len(B)>=2:
            ans *=B.popleft()*B.popleft()
            k -=2
    else:
        if 0<len(B):
            ans *=B.popleft()
            k -=1
        elif 0<len(C):
            ans *=C.popleft()
            flag=0
            k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    ans %=mod
print(ans)

Submission status: Wrong Answer

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

plus = []
minus = []
zero = 0
ans = 1

for i in a:
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(-i)
    else:
        zero += 1

plus.sort()
minus.sort()
p_l = len(plus)
m_l = len(minus)
cnt = 0
if k == 1:
    print(max(a))
elif zero > n - k:
    print(0)
elif zero == n - k:
    for i in plus:
        ans = (i * ans) % num
    for j in minus:
        ans = (ans * j) % num
    if m_l % 2 == 0:
        print(ans)
    else:
        print(-ans % num)
elif len(plus) == 0:
    if k % 2 == 0:
        for j in range(k):
            ans = ans * (minus[-(j + 1)]) % num
        print(ans % num)
    else:
        for j in range(k):
            ans = ans * (minus[j]) % num
        print(-ans % num)
else:
    for i in range(k - 1):

        if p_l > 1 and m_l > 1:
            if plus[-1] >= minus[-1]:
                ans = ans * plus.pop() % num
                p_l -= 1
            else:
                ans = ans * minus.pop() % num
                cnt += 1
                m_l -= 1
        elif p_l == 1:
            ans = ans * minus.pop() % num
            cnt += 1
            m_l -= 1
        elif m_l == 1:
            ans = ans * plus.pop() % num
            p_l -= 1
    if cnt % 2 == 0:
        ans = ans * plus.pop() % num
        p_l -= 1
    else:
        ans = ans * minus.pop() % num
        m_l -= 1
    print(ans % num)

Submission status: Wrong Answer

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

plus = []
minus = []
zero = 0
ans = 1

for i in a:
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1

plus.sort()
minus.sort(reverse=True)
p_l = len(plus)
m_l = len(minus)

if k == 1:
    print(max(a))
elif zero > n - k:
    print(0)
elif zero == n - k:
    for i in plus:
        ans = (i * ans) % num
    for j in minus:
        ans = (ans * j) % num
    print(ans)
elif len(plus) == 0:
    if k % 2 == 0:
        for j in range(k):
            ans = ans * (minus[-(j + 1)]) % num
        print(ans % num)
    else:
        for j in range(k):
            ans = ans * (minus[j]) % num
        print(ans % num)
else:
    for i in range(k - 1):

        if p_l > 1 and m_l > 1:
            if plus[-1] >= -minus[-1]:
                ans = ans * plus.pop() % num
                p_l -= 1
            else:
                ans = -(ans * minus.pop() % num)
                m_l -= 1
        elif p_l == 1:
            ans = -(ans * minus.pop() % num)
            m_l -= 1
        elif m_l == 1:
            ans = ans * plus.pop() % num
            p_l -= 1
    if ans > 0:
        ans = ans * plus.pop() % num
        p_l -= 1
    else:
        ans = -(ans * minus.pop() % num)
        m_l -= 1
    print(ans % num)

Submission status: Wrong Answer

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

plus = []
minus = []
zero = 0
ans = 1

for i in a:
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1

plus.sort()
minus.sort(reverse=True)
p_l = len(plus)
m_l = len(minus)

if n == 1:
    print(a[0])
elif zero > n - k:
    print(0)
elif zero == n - k:
    for i in plus:
        ans = (i * ans) % num
    for j in minus:
        ans = (ans * j) % num
    print(ans)
elif len(plus) == 0:
    if k % 2 == 0:
        for j in range(k):
            ans = ans * (minus[-(j + 1)]) % num
        print(ans % num)
    else:
        for j in range(k):
            ans = ans * (minus[j]) % num
        print(ans % num)
else:
    for i in range(k - 1):

        if p_l > 1 and m_l > 1:
            if plus[-1] >= -minus[-1]:
                ans = ans * plus.pop() % num
                p_l -= 1
            else:
                ans = -(ans * minus.pop() % num)
                m_l -= 1
        elif p_l == 1:
            ans = -(ans * minus.pop() % num)
            m_l -= 1
        elif p_l > 1:
            ans = ans * plus.pop() % num
            p_l -= 1
    if ans > 0:
        ans = ans * plus.pop() % num
        p_l -= 1
    else:
        ans = -(ans * minus.pop() % num)
        m_l -= 1
    print(ans % num)

Submission status: Wrong Answer

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

plus = []
minus = []
zero = 0
ans = 1

for i in a:
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1

plus.sort()
minus.sort(reverse=True)
p_l = len(plus)
m_l = len(minus)

if n == 1:
    print(a[0])
elif zero > n - k:
    print(0)
elif zero == n - k:
    for i in plus:
        ans = (i * ans) % num
    for j in minus:
        ans = (ans * j) % num
    print(ans)
elif len(plus) == 0:
    if k % 2 == 0:
        for j in range(k):
            ans = ans * (minus[-(j + 1)]) % num
        print(ans % num)
    else:
        for j in range(k):
            ans = ans * (minus[j]) % num
        print(ans % num)
else:
    for i in range(k - 1):

        if p_l > 1 and m_l > 1:
            if plus[-1] >= -minus[-1]:
                ans = ans * plus.pop() % num
                p_l -= 1
            else:
                ans = -(ans * minus.pop() % num)
                m_l -= 1
        elif p_l == 1:
            ans = -(ans * minus.pop() % num)
            m_l -= 1
        elif p_l > 1:
            ans = ans * plus.pop() % num
            p_l -= 1
        print(ans)
    if ans > 0:
        ans = ans * plus.pop() % num
        p_l -= 1
    else:
        ans = -(ans * minus.pop() % num)
        m_l -= 1
    print(ans % num)

Submission status: Wrong Answer

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

plus = []
minus = []
zero = 0
ans = 1

for i in a:
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1

plus.sort()
minus.sort(reverse=True)
p_l = len(plus)
m_l = len(minus)

if n == 1:
    print(a[0])
elif zero > n - k:
    print(0)
elif zero == n - k:
    for i in plus:
        ans = (i * ans) % num
    for j in minus:
        ans = (ans * j) % num
    print(ans)
elif len(plus) == 0:
    if k % 2 == 0:
        for j in range(k):
            ans = ans * (minus[-(j + 1)]) % num
        print(ans % num)
    else:
        for j in range(k):
            ans = ans * (minus[j]) % num
        print(ans % num)
else:
    for i in range(k - 1):

        if p_l > 1 and m_l > 1:
            if plus[-1] >= minus[-1]:
                ans = ans * plus.pop() % num
                p_l -= 1
            else:
                ans = ans * minus.pop() % num
                m_l -= 1
        elif p_l == 1:
            ans = ans * minus.pop() % num
            m_l -= 1
        elif p_l > 1:
            ans = ans * plus.pop() % num
            p_l -= 1

    if ans > 0:
        ans = ans * plus.pop() % num
        p_l -= 1
    else:
        ans = ans * minus.pop() % num
        m_l -= 1
    print(ans % num)

Submission status: Wrong Answer

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

plus = []
minus = []
zero = 0
ans = 1

for i in a:
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(-i)
    else:
        zero += 1
        
plus.sort()
minus.sort()
p_l = len(plus)
m_l = len(minus)

if n == 1:
    print(a[0])
elif zero > n - k:
    print(0)
elif zero == n - k:
    for i in plus:
        ans = (i * ans) % num
    for j in minus:
        ans = (ans * j) % num
    if k % 2 == 0:
        print(ans)
    else:
        print(-ans % num)
elif len(plus) == 0:
    if k % 2 == 0:
        for j in range(k):
            ans = ans * (minus[-(j + 1)]) % num
        print(ans % num)
    else:
        for j in range(k):
            ans = ans * (minus[j]) % num
        print(-ans % num)
else:
    for i in range(k - 1):

        if p_l > 1 and m_l > 1:
            if plus[-1] >= minus[-1]:
                ans = ans * plus.pop() % num
                p_l -= 1
            else:
                ans = -(ans * -minus.pop() % num)
                m_l -= 1
        elif p_l == 1:
            ans = -(ans * -minus.pop() % num)
            m_l -= 1
        elif p_l > 1:
            ans = ans * plus.pop() % num
            p_l -= 1

    if ans > 0:
        ans = ans * plus.pop() % num
        p_l -= 1
    else:
        ans = -(ans * -minus.pop() % num)
        m_l -= 1
    print(ans % num)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import sys


def divide_a_by_b_mod(a, b, MOD):
    a, b = int(a), int(b)
    return (a % MOD * pow(b, MOD - 2, MOD)) % MOD


input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x), reverse=True)
MOD = 10**9 + 7

# print(f'{A=}')

if N == K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if K % 2 == 1:
    if max(A) < 0:
        ans = 1
        for a in A[::-1][:K]:
            ans *= a
            ans %= MOD
        print(ans)
        exit()

P = 1
for a in A[:K]:
    if a >= 0:
        P *= 1
    else:
        P *= -1
# print(f'{P=}')

if P > 0:
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# (1) 負の数を 1 つ取り除き、非負の数を 1 つ加える
patern_one = True
plus1, minus1 = 0, 0
for plus1 in A[K:]:
    if plus1 >= 0:
        break
else:
    patern_one = False
for minus1 in A[:K][::-1]:
    if minus1 < 0:
        break
else:
    patern_one = False
# print(f'{plus1=}, {minus1=}, {patern_one=}')

# (2) 正の数を 1 つ取り除き、負の数を 1 つ加える
patern_two = True
plus2, minus2 = 0, 0
for plus2 in A[:K][::-1]:
    if plus2 >= 0:
        break
else:
    patern_two = False
for minus2 in A[K:]:
    if minus2 < 0:
        break
else:
    patern_two = False
# print(f'{plus2=}, {minus2=}, {patern_two=}')


def f1():
    subset = deepcopy(A[:K])
    subset.remove(minus1)
    subset.append(plus1)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


def f2():
    subset = deepcopy(A[:K])
    subset.remove(plus2)
    subset.append(minus2)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


P = 1
for a in A[:K]:
    P = P * a % MOD

if patern_one and patern_two:
    if abs(plus2 * minus1) < abs(plus1 * minus2):
        # (1)
        ans = divide_a_by_b_mod(P, minus1, MOD) * plus1 % P
        # ans = f1()
    else:
        # (2)
        ans = divide_a_by_b_mod(P, plus2, MOD) * minus1 % P
        # ans = f2()
elif patern_one:
    ans = f1()
else:
    ans = f2()
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import sys


def divide_a_by_b_mod(a, b, MOD):
    a, b = int(a), int(b)
    return (a % MOD * pow(b, MOD - 2, MOD)) % MOD


input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x), reverse=True)
MOD = 10**9 + 7

# print(f'{A=}')

if N == K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if K % 2 == 1:
    if max(A) < 0:
        ans = 1
        for a in A[::-1][:K]:
            ans *= a
            ans %= MOD
        print(ans)
        exit()

P = 1
for a in A[:K]:
    if a >= 0:
        P *= 1
    else:
        P *= -1
# print(f'{P=}')

if P > 0:
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# (1) 負の数を 1 つ取り除き、非負の数を 1 つ加える
patern_one = True
plus1, minus1 = 0, 0
for plus1 in A[K:]:
    if plus1 >= 0:
        break
else:
    patern_one = False
for minus1 in A[:K][::-1]:
    if minus1 < 0:
        break
else:
    patern_one = False
# print(f'{plus1=}, {minus1=}, {patern_one=}')

# (2) 正の数を 1 つ取り除き、負の数を 1 つ加える
patern_two = True
plus2, minus2 = 0, 0
for plus2 in A[:K][::-1]:
    if plus2 >= 0:
        break
else:
    patern_two = False
for minus2 in A[K:]:
    if minus2 < 0:
        break
else:
    patern_two = False
# print(f'{plus2=}, {minus2=}, {patern_two=}')


def f1():
    subset = deepcopy(A[:K])
    subset.remove(minus1)
    subset.append(plus1)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


def f2():
    subset = deepcopy(A[:K])
    subset.remove(plus2)
    subset.append(minus2)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


P = 1
for a in A[:K]:
    P = P * a % MOD

if patern_one and patern_two:
    if abs(plus2 * minus1) < abs(plus1 * minus2):
        # (1)
        ans = divide_a_by_b_mod(P, plus2, MOD) * minus1 % P
        # ans = f1()
    else:
        # (2)
        ans = divide_a_by_b_mod(P, minus1, MOD) * plus1 % P
        # ans = f2()
elif patern_one:
    ans = f1()
else:
    ans = f2()
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import sys

input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x), reverse=True)
MOD = 10**9 + 7

# print(f'{A=}')

if N == K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if K % 2 == 1:
    if max(A) < 0:
        ans = 1
        for a in A[::-1][:K]:
            ans *= a
            ans %= MOD
        print(ans)
        exit()

P = 1
for a in A[:K]:
    if a >= 0:
        P *= 1
    else:
        P *= -1
# print(f'{P=}')

if P > 0:
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# print(f'{A[K:]=}')

# (1) 負の数を 1 つ取り除き、非負の数を 1 つ加える
patern_one = True
plus1, minus1 = 0, 0
for plus1 in A[K:]:
    if plus1 >= 0:
        break
else:
    patern_one = False
for minus1 in A[:K][::-1]:
    if minus1 < 0:
        break
else:
    patern_one = False
# print(f'{plus1=}, {minus1=}, {patern_one=}')

# (2) 正の数を 1 つ取り除き、負の数を 1 つ加える
patern_two = True
plus2, minus2 = 0, 0
for plus2 in A[:K][::-1]:
    if plus2 >= 0:
        break
else:
    patern_two = False
for minus2 in A[K:]:
    if minus2 < 0:
        break
else:
    patern_two = False
# print(f'{plus2=}, {minus2=}, {patern_two=}')


def f1():
    subset = deepcopy(A[:K])
    subset.remove(minus1)
    subset.append(plus1)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


def f2():
    subset = deepcopy(A[:K])
    subset.remove(plus2)
    subset.append(minus2)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


if patern_one and patern_two:
    # print(f'plus2 * minus1={plus2 * minus1}')
    # print(f'plus1 * minus2={plus1 * minus2}')
    ans = max(f1(), f2())
    # if abs(plus2 * minus1) <= abs(plus1 * minus2):
    #     # (1)
    #     ans = f1()
    #     ans2 = f2()
    # else:
    #     # (2)
    #     ans2 = f1()
    #     ans = f2()
elif patern_one:
    ans = f1()
else:
    ans = f2()
# print(ans, ans2)
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import sys

input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x), reverse=True)
MOD = 10**9 + 7

# print(f'{A=}')

if N == K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if K % 2 == 1:
    if max(A) < 0:
        ans = 1
        for a in A[::-1][:K]:
            ans *= a
            ans %= MOD
        print(ans)
        exit()

P = 1
for a in A[:K]:
    if a >= 0:
        P *= 1
    else:
        P *= -1
# print(f'{P=}')

if P > 0:
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# print(f'{A[K:]=}')

# (1) 負の数を 1 つ取り除き、非負の数を 1 つ加える
patern_one = True
plus1, minus1 = 0, 0
for plus1 in A[K:]:
    if plus1 >= 0:
        break
else:
    patern_one = False
for minus1 in A[:K][::-1]:
    if minus1 < 0:
        break
else:
    patern_one = False
# print(f'{plus1=}, {minus1=}, {patern_one=}')

# (2) 正の数を 1 つ取り除き、負の数を 1 つ加える
patern_two = True
plus2, minus2 = 0, 0
for plus2 in A[:K][::-1]:
    if plus2 >= 0:
        break
else:
    patern_two = False
for minus2 in A[K:]:
    if minus2 < 0:
        break
else:
    patern_two = False
# print(f'{plus2=}, {minus2=}, {patern_two=}')


def f1():
    subset = deepcopy(A[:K])
    subset.remove(minus1)
    subset.append(plus1)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


def f2():
    subset = deepcopy(A[:K])
    subset.remove(plus2)
    subset.append(minus2)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


if patern_one and patern_two:
    if abs(plus2 * minus1) <= abs(plus1 * minus2):
        # (1)
        # ans = f1()
        ans = f2()
    else:
        # (2)
        ans = f1()
        # ans = f2()
elif patern_one:
    ans = f1()
else:
    ans = f2()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
for a in A:
    if a >= 0:
        B.append(a)
    else:
        C.append(-a)

ans = 1
if len(B) == 0 and K % 2 == 1:
    C = sorted(C)
    for i in range(K):
        ans *= -C[i]
        ans %= MOD
    print(ans)
    sys.exit()
      
negs_p = 0
non_negs_p = 0
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)

for i in range(K):
    if negs_p == len(C):
        non_negs_p += 1
    elif non_negs_p == len(B):
        negs_p += 1
    elif C[negs_p] > B[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
        
if N == K or negs_p % 2 == 0:
    for i in range(non_negs_p):
        ans = ans * B[i] % MOD
    for i in range(negs_p):
        ans = ans * -C[i] % MOD
    print(ans)
    sys.exit()

for i in range(non_negs_p):
    ans = ans * B[i] % MOD
for i in range(negs_p):
    ans = ans * C[i] % MOD

if negs_p == len(C) or non_negs_p == 0:
    b,c = C[negs_p-1],B[non_negs_p]
    ans = (ans*MOD // b) * c % MOD
elif non_negs_p == len(B) or negs_p == 0:
    a,d = C[negs_p],B[non_negs_p-1]
    ans = (ans*MOD // d) * a % MOD 
else:
    a,b,c,d = C[negs_p],C[negs_p-1],B[non_negs_p],B[non_negs_p-1]
    if a*b > c*d:
        ans = (ans*MOD // d) * a % MOD  
    else:   
        ans = (ans*MOD // b) * c % MOD    
print(ans)

Submission status: Wrong Answer

Solution code:
N = 0
K = 0
A = []

try:
    line = input().split(' ')
    N = int(line[0])
    K = int(line[1])
    A = [int(i) for i in input().split(' ')]
    A = sorted(A, key = lambda x: abs(x))
    A.reverse()
except:
  pass

cDivBy = 10 ** 9 + 7
selected = [i for i in range(K)]

isZeroAvailable = False
isMaxNeg = False
while not isMaxNeg:
    sig = 1
    for i in selected:
        sig *= 1 if A[i] > 0 else -1 if A[i] < 0 else 0
    if sig == 1:
        break
    if sig == 0:
        isZeroAvailable = True
    for i in range(len(selected)):
        j = len(selected) - 1 - i
        selected[j] += 1
        if selected[j] == N - i:
            selected[j] = selected[j - 1] + 2
            if selected[j] >= N:
                isMaxNeg = True
                break
        else:
            break

if isMaxNeg and isZeroAvailable:
    print(0)
else:
    if isMaxNeg:
        selected = [N - K + i for i in range(K)]
    #print(A, selected)
    a = 1
    for i in selected:
        a = (a * (A[i] % cDivBy)) % cDivBy
    print(a)