Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys 
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
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
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)

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()

if negs_p % 2 == 1:
    if negs_p == len(C) or non_negs_p == 0:
        negs_p -= 1
        non_negs_p += 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
    elif non_negs_p == len(B) or negs_p == 0:
        negs_p += 1
        non_negs_p -= 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % 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:
            negs_p += 1
            non_negs_p -= 1
        else:   
            negs_p -= 1
            non_negs_p += 1
        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)

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:
    C = sorted(C)
    for i in range(K):
        ans *= -C[i]
        ans %= MOD
    print(ans)
    sys.exit()
      
negs_p = 0
non_negs_p = 0
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
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)

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()

if negs_p % 2 == 1:
    if negs_p == len(C) or non_negs_p == 0:
        negs_p -= 1
        non_negs_p += 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
    elif non_negs_p == len(B) or negs_p == 0:
        negs_p += 1
        non_negs_p -= 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % 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:
            negs_p += 1
            non_negs_p -= 1
        else:   
            negs_p -= 1
            non_negs_p += 1
        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)

Submission status: Wrong Answer

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(k==n or k>len(pos)+len(neg)):
    for el in a:
        ans = (ans%mod*el%mod)%mod
elif(len(pos)+len(neg)==k):
    if(len(neg)%2!=0):
        ans = 0
    else:
        for el in pos:
            ans = (ans%mod*el%mod)%mod
        for el in neg:
            ans = (ans%mod*el%mod)%mod

else:

    if(len(pos)==0):
        if(k%2==0):
            temp = 0
            for i in range(len(neg)-1, -1, -1):
                if(temp==k):
                    break
                ans = (ans%mod*neg[i]%mod)%mod
                temp+=1
            if(temp<k):
                ans = 0
        else:
            temp = 0
            for i in range(len(neg) - 1):
                if (temp == k):
                    break
                ans = (ans%mod * neg[i]%mod) % mod
                temp += 1
            if (temp < k):
                ans = 0
    else:

        left = k

        i,j = 0, len(neg)-1

        while(left>1):
            temp, temp1 = 0, 0
            if(i<len(pos)-1):
                temp = pos[i]*pos[i+1]
                # i+=2
            if(j>=1):
                temp1 = neg[j]*neg[j-1]
                # j-=2
            if(temp==0 and temp1==0):
                break
            if(temp1>temp):
                ans = (ans*(temp1%mod))%mod
                j-=2
            else:
                ans = (ans*(temp%mod))%mod
                i+=2
            left -= 2
        # print(ans,i,j)
        if(left>1):
            ans = 0
        elif(left==1):
            if(i<len(pos)):
                ans = ((ans%mod)*pos[i])%mod
            else:
                ans1 = 1
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
                ans = max(ans, ans1)
        if(k%2!=0):
            ans1 = 1
            if(i-2>=0 and j-2>=-1 and i-2<=len(pos)-1 and j-2<=len(neg)-1):
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
            # print(ans, ans1)
            ans = max(ans, ans1)
print(ans)

Submission status: Wrong Answer

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(k==n):
    for el in a:
        ans = (ans%mod*el%mod)%mod
elif(len(pos)+len(neg)==k):
    if(len(neg)%2!=0):
        ans = 0
    else:
        for el in pos:
            ans = (ans%mod*el%mod)%mod
        for el in neg:
            ans = (ans%mod*el%mod)%mod

else:

    if(len(pos)==0):
        if(k%2==0):
            temp = 0
            for i in range(len(neg)-1, -1, -1):
                if(temp==k):
                    break
                ans = (ans%mod*neg[i]%mod)%mod
                temp+=1
            if(temp<k):
                ans = 0
        else:
            temp = 0
            for i in range(len(neg) - 1):
                if (temp == k):
                    break
                ans = (ans%mod * neg[i]%mod) % mod
                temp += 1
            if (temp < k):
                ans = 0
    else:

        left = k

        i,j = 0, len(neg)-1

        while(left>1):
            temp, temp1 = 0, 0
            if(i<len(pos)-1):
                temp = pos[i]*pos[i+1]
                # i+=2
            if(j>=1):
                temp1 = neg[j]*neg[j-1]
                # j-=2
            if(temp==0 and temp1==0):
                break
            if(temp1>temp):
                ans = (ans*(temp1%mod))%mod
                j-=2
            else:
                ans = (ans*(temp%mod))%mod
                i+=2
            left -= 2
        # print(ans,i,j)
        if(left>1):
            ans = 0
        elif(left==1):
            if(i<len(pos)):
                ans = ((ans%mod)*pos[i])%mod
            else:
                ans1 = 1
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
                ans = max(ans, ans1)
        if(k%2!=0):
            ans1 = 1
            if(i-2>=0 and j-2>=-1 and i-2<=len(pos)-1 and j-2<=len(neg)-1):
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
            # print(ans, ans1)
            ans = max(ans, ans1)
print(ans)

Submission status: Wrong Answer

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(k==n):
    for el in a:
        ans = (ans%mod*el%mod)%mod
elif(len(pos)+len(neg)==k):
    if(len(neg)%2!=0):
        ans = 0
    else:
        for el in pos:
            ans = (ans%mod*el%mod)%mod
        for el in neg:
            ans = (ans%mod*el%mod)%mod

else:

    if(len(pos)==0):
        if(k%2==0):
            temp = 0
            for i in range(len(neg)-1, -1, -1):
                if(temp==k):
                    break
                ans = (ans%mod*neg[i]%mod)%mod
                temp+=1
            if(temp<k):
                ans = 0
        else:
            temp = 0
            for i in range(len(neg) - 1):
                if (temp == k):
                    break
                ans = (ans%mod * neg[i]%mod) % mod
                temp += 1
            if (temp < k):
                ans = 0
    else:

        left = k

        i,j = 0, len(neg)-1

        while(left>1):
            temp, temp1 = 0, 0
            if(i<len(pos)-1):
                temp = pos[i]*pos[i+1]
                # i+=2
            if(j>=1):
                temp1 = neg[j]*neg[j-1]
                # j-=2
            if(temp==0 and temp1==0):
                break
            if(temp1>temp):
                ans = (ans*(temp1%mod))%mod
                j-=2
            else:
                ans = (ans*(temp%mod))%mod
                i+=2
            left -= 2
        # print(ans,i,j)
        if(left>1):
            ans = 0
        elif(left==1):
            if(i<len(pos)):
                ans = ((ans%mod)*pos[i])%mod
            else:
                ans1 = 1
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
                ans = max(ans, ans1)
        if(k%2!=0):
            ans1 = 1
            if(i-2>=0 and j-2>=0 and i-2<=len(pos)-1 and j-2<=len(neg)-1):
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
            # print(ans, ans1)
            ans = max(ans, ans1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
pos = []
neg = []
zero = []
for i in A:
    if i == 0:
        zero.append(i)
    elif i > 0:
        pos.append(i)
    else:
        neg.append(i)
pos.sort(reverse=True)
neg.sort(reverse=True)
ans = 1
pos_cnt = 0
neg_cnt = 0
for i in range(K):
    if pos_cnt > len(pos) - 1 and neg_cnt > len(neg) - 1:
        print(0)
        sys.exit()
    elif pos_cnt > len(pos) - 1:
        ans *= neg[neg_cnt]
        neg_cnt += 1
    elif neg_cnt > len(neg) - 1:
        ans *= pos[pos_cnt]
        pos_cnt += 1
    elif pos[pos_cnt] >= abs(neg[neg_cnt]):
        ans *= pos[pos_cnt]
        pos_cnt += 1
    else:
        ans *= neg[neg_cnt]
        neg_cnt += 1
    ans %= mod
if ans >= 0:
    print(ans)
    sys.exit()
ans = 1
if pos_cnt > len(pos) - 1 and neg_cnt > len(neg) - 1:
    print(0)
    sys.exit()
elif pos_cnt > len(pos) - 1:
    for i in pos[0:neg_cnt + 1]:
        ans *= i
        ans %= mod
    for i in neg[0:pos_cnt - 1]:
        ans *= i
        ans %= mod
elif neg_cnt > len(neg) - 1:
    for i in pos[0:neg_cnt - 1]:
        ans *= i
        ans %= mod
    for i in neg[0:pos_cnt + 1]:
        ans *= i
        ans %= mod
elif pos[pos_cnt - 1] >= abs(neg[neg_cnt - 1]):
    for i in pos[0:neg_cnt - 1]:
        ans *= i
        ans %= mod
    for i in neg[0:pos_cnt + 1]:
        ans *= i
        ans %= mod
else:
    for i in pos[0:neg_cnt + 1]:
        ans *= i
        ans %= mod
    for i in neg[0:pos_cnt - 1]:
        ans *= 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()))
ans = 1
r = 0
r_f = 0
l = n - 1
l_f = 1

a.sort()
if n == 1:
    ans = a[0]
elif a[0] * a[-1] > 0:
    if a[0] < 0:
        if k % 2 == 0:
            for i in range(k):
                ans *= (abs(a[i]) % num)
        else:
            for i in range(k):
                ans *= (abs(a[-(i + 1)]) % num)
            ans = -ans
    else:
        for i in range(k):
            ans *= (a[-i - 1] % num)
else:
    while k != 1:
        if r_f == 0 and l_f == 0:
            if abs(a[r]) >= abs(a[l]):
                ans *= (-(abs(a[r]) % num))
                r += 1
                if a[r + 1] >= 0:
                    r_f = 1
            else:
                ans *= (a[l] % num)
                l -= 1
                if a[l - 1] <= 0:
                    l_f = 1
        elif r_f == 1 and l_f == 0:
            ans *= (a[l] % num)
            l -= 1
            if a[l - 1] <= 0:
                l_f = 1
        elif r_f == 0 and l_f == 1:
            ans *= (-(abs(a[r]) % num))
            r += 1
            if a[r + 1] >= 0:
                r_f = 1
        else:
            if abs(a[r]) >= abs(a[l]):
                ans *= (-(abs(a[r]) % num))
                r += 1
            else:
                ans *= (a[l] % num)
                l -= 1
        k -= 1
    if ans < 0:
        ans *= a[r]
    else:
        ans *= a[l]

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()))
ans = 1
r = 0
r_f = 0
l = n - 1
l_f = 1

a.sort()
if n == 1:
    ans = a[0]
elif a[0] * a[-1] > 0:
    if a[0] < 0:
        if k % 2 == 0:
            for i in range(k):
                ans *= (abs(a[i]) % num)
        else:
            for i in range(k):
                ans *= (abs(a[-(i + 1)]) % num)
            ans = -ans
    else:
        for i in range(k):
            ans *= (a[-i - 1] % num)
else:
    while k != 1:
        if r_f == 0 and l_f == 0:
            if abs(a[r]) >= abs(a[l]):
                ans *= (-(abs(a[r]) % num))
                r += 1
                if a[r] >= 0:
                    r_f = 1
            else:
                ans *= (a[l] % num)
                l -= 1
                if a[l] <= 0:
                    l_f = 1
        elif r_f == 1 and l_f == 0:
            ans *= (a[l] % num)
            l -= 1
            if a[l] <= 0:
                l_f = 1
        elif r_f == 0 and l_f == 1:
            ans *= (-(abs(a[r]) % num))
            r += 1
            if a[r] >= 0:
                r_f = 1
        else:
            if abs(a[r]) >= abs(a[l]):
                ans *= (-(abs(a[r]) % num))
                r += 1
            else:
                ans *= (a[l] % num)
                l -= 1
        k -= 1
    if ans < 0:
        ans *= a[r]
    else:
        ans *= a[l]

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()))
ans = 1
r = 0
r_f = 0
l = n - 1
l_f = 1

a.sort()
if n == 1:
    ans = a[0]
elif a[0] * a[-1] > 0:
    if a[0] < 0:
        if k % 2 == 0:
            for i in range(k):
                ans *= (a[i] % num)
        else:
            for i in range(k):
                ans *= (a[-(i + 1)] % num)
    else:
        for i in range(k):
            ans *= (a[-i - 1] % num)
else:
    while k != 1:
        if r_f == 0 and l_f == 0:
            if abs(a[r]) >= abs(a[l]):
                ans *= (a[r] % num)
                r += 1
                if a[r] >= 0:
                    r_f = 1
            else:
                ans *= (a[l] % num)
                l -= 1
                if a[l] <= 0:
                    l_f = 1
        elif r_f == 1 and l_f == 0:
            ans *= (a[l] % num)
            l -= 1
            if a[l] <= 0:
                l_f = 1
        elif r_f == 0 and l_f == 1:
            ans *= (a[r] % num)
            r += 1
            if a[r] >= 0:
                r_f = 1
        else:
            if abs(a[r]) >= abs(a[l]):
                ans *= (a[r] % num)
                r += 1
            else:
                ans *= (a[l] % num)
                l -= 1
        k -= 1
    if ans < 0:
        ans *= a[r]
    else:
        ans *= a[l]

print(ans % num)

Submission status: Wrong Answer

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

MOD=10**9+7

ans=1
if N==K:
    for a in L:
        ans*=a
        ans%=MOD

#全部ふで奇数個
elif all(l<0 for l in L) and K%2==1:
    #小さい方からKこ
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))

    ans_cand=[v for v in absL[:K]]
    remain=[v for v in absL[K:]]

    if len(list(filter(lambda x:x<0,ans_cand)))%2==0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        ans_cand_min_neg = None
        ans_cand_min_pos=None
        remain_cand_max_neg=None
        remain_cand_max_pos=None

        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a

        #できるだけ絶対値が大きいやつ
        for a in remain:
            if a>0:
                remain_cand_max_pos=a
                break

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
        for a in remain:
            if a<0:
                remain_cand_max_neg=a
                break

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_pos*remain_cand_max_pos)
            B = abs(ans_cand_min_neg*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg


        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
            else:
                NG=None
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
plus,minus,zero = 0,0,0
for i in range(n):
    if a[i] > 0:
        plus += 1
    elif a[i] < 0:
        minus += 1
    else:
        zero += 1
if n==k:
    ans=1
    for i in range(n):
        ans*=a[i]
        ans=ans%(10**9+7)
    print(ans)
else:
    if k%2==1 and minus==n:
        a.sort(reverse=True)
        ans=1
        for i in range(k):
            ans*=a[i]
            ans=ans%(10**9+7)
        print(ans)
    else:
        l=[]
        for i in range(n):
            if a[i]>=0:
                fugou=1
            else:
                fugou=-1
            l.append((abs(a[i]),fugou))
        l.sort(reverse=True)
        ans=1
        hu=1
        for i in range(k):
            ans*=l[i][0]
            ans=ans%(10**9+7)
            hu*=l[i][1]
        if hu==1:
            print(ans)
        elif ans==0:
            print(0)
        else:
            ss,sh,ts,th=-1,-1,-1,-1
            for i in range(k)[::-1]:
                if l[i][1]>0:
                    ss=l[i][0]
                    break
            for i in range(k)[::-1]:
                if l[i][1]<0:
                    sh=l[i][0]
                    break
            for i in range(k,n):
                if l[i][1]>0:
                    ts=l[i][0]
                    break
            for i in range(k,n):
                if l[i][1]<0:
                    th=l[i][0]
                    break
            if ss>0 and sh>0 and ts>0 and th>0:
                if th*sh==ts*ss:
                    ans=(ans*pow(ss,10**9+5,10**9+7)*th)%(10**9+7)
                else:
                    ans=(ans*pow(sh,10**9+5,10**9+7)*ts)%(10**9+7)
                print(ans)
            else:
                if th>0 and ss>0:
                    ans=(ans*pow(ss,10**9+5,10**9+7)*th)%(10**9+7)
                else:
                    ans=(ans*pow(sh,10**9+5,10**9+7)*ts)%(10**9+7)
                print(ans)

Submission status: Wrong Answer

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

MOD=10**9+7

ans=1
if N==K:
    for a in L:
        ans*=a
        ans%=MOD

#全部ふで奇数個
elif all(l<0 for l in L) and K%2==1:
    #小さい方からKこ
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))

    ans_cand=[v for v in absL[:K]]
    remain=[v for v in absL[K:]]

    if len(list(filter(lambda x:x<0,ans_cand)))%2==0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<=0:
                ans_cand_min_neg=a

        #できるだけ絶対値が大きいやつ
        remain_cand_max_pos=None
        for a in remain:
            if a>=0:
                remain_cand_max_pos=a
                break

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる
        ans_cand_min_pos=None
        remain_cand_max_neg=None

        for a in ans_cand:
            if a>=0:
                ans_cand_min_pos=a
        for a in remain:
            if a<=0:
                remain_cand_max_neg=a
                break

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_neg*remain_cand_max_pos)
            B = abs(ans_cand_min_pos*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg


        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
            else:
                NG=None
print(ans)

Submission status: Wrong Answer

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

MOD=10**9+7

ans=1
if N==K:
    for a in L:
        ans*=a
        ans%=MOD

#全部ふで奇数個
elif all(l<0 for l in L) and K%2==1:
    #小さい方からKこ
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))

    ans_cand=[v for v in absL[:K]]
    remain=[v for v in absL[K:]]

    if len(list(filter(lambda x:x<0,ans_cand)))%2==0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a

        #できるだけ絶対値が大きいやつ
        remain_cand_max_pos=None
        for a in remain:
            if a>=0:
                remain_cand_max_pos=a
                break

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる
        ans_cand_min_pos=None
        remain_cand_max_neg=None

        for a in ans_cand:
            if a>=0:
                ans_cand_min_pos=a
        for a in remain:
            if a<0:
                remain_cand_max_neg=a
                break

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_neg*remain_cand_max_pos)
            B = abs(ans_cand_min_pos*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg


        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
            else:
                NG=None
print(ans)

Submission status: Wrong Answer

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

MOD=10**9+7

ans=1
if N==K:
    for a in L:
        ans*=a
        ans%=MOD

#全部ふで奇数個
elif all(l<0 for l in L) and K%2==1:
    #小さい方からKこ
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))

    ans_cand=[v for v in absL[:K]]
    remain=[v for v in absL[K:]]

    if len(list(filter(lambda x:x<0,ans_cand)))%2==0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a

        #できるだけ絶対値が大きいやつ
        remain_cand_max_pos=None
        for a in remain:
            if a>=0:
                remain_cand_max_pos=a
                break

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる
        ans_cand_min_pos=None
        remain_cand_max_neg=None

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
        for a in remain:
            if a<=0:
                remain_cand_max_neg=a
                break

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_neg*remain_cand_max_pos)
            B = abs(ans_cand_min_pos*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg


        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
            else:
                NG=None
print(ans)