Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

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

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

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

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

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

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

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

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

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

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

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

Sample Input 4

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

Sample Output 4

999983200

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



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
N,K = 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:
import sys
import heapq

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7

    q = []
    pluscnt = 0
    minuscnt = 0
    for a in A:
        if a >= 0:
            pluscnt += 1
            heapq.heappush(q, (-abs(a), 1))
        else:
            minuscnt += 1
            heapq.heappush(q, (-abs(a), -1))

    ans = 1
    # 絶対マイナスになる場合
    if pluscnt < K - min((K - K % 2), (minuscnt - minuscnt % 2)):
        q = []
        for a in A:
            heapq.heappush(q, abs(a))

        for _ in range(K):
            ans *= -heapq.heappop(q)
            ans %= MOD
    else:
        lastplus = 0
        lastminus = 0
        minuscnt = 0
        for _ in range(K):
            x = heapq.heappop(q)
            ans *= -x[0]
            ans %= MOD
            if x[1] == 1:
                lastplus = -x[0]
            else:
                minuscnt += 1
                lastminus = -x[0]

        # 積がminus
        # minusを1個減らして plusに変えるか
        # plusを1個減らして minusに変える必要がある
        if minuscnt % 2 == 1:
            nextplus = 0
            nextminus = 0
            while q:
                x = heapq.heappop(q)
                if x[1] == 1 and nextplus == 0:
                    nextplus = -x[0]
                if x[1] == -1 and nextminus == 0:
                    nextminus = -x[0]
            tmp1 = 0
            tmp2 = 0
            if lastplus != 0 and nextminus != 0:
                tmp1 = ans * nextminus / lastplus
            if lastminus != 0 and nextplus != 0:
                tmp2 = ans * nextplus / lastminus

            ans = max(tmp1, tmp2)
            ans %= MOD


    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
P = []
N = []
for i in range(n):
    if a[i] >= 0:
        P.append(a[i])
    else:
        N.append(a[i])
P  = sorted(P, reverse=True) 
N  = sorted(N)
x = 0
y = 0
i = 0
ans = 1
if k%2 == 1 and len(P) >= 1:
    ans *= P[0]
    x += 1
    i += 1
while i < k-1:
    if x < len(P)-1 and y < len(N)-1:
        if P[x]*P[x+1] > N[y]*N[y+1]:
            ans *= P[x]*P[x+1]
            ans %= mod
            x += 2
            i += 2
        else:
            ans *= N[y]*N[y+1]
            ans %= mod
            y += 2
            i += 2
    elif x < len(P)-1:
        ans *= P[x]*P[x+1]
        ans %= mod
        x += 2
        i += 2
    elif y < len(N)-1:
        ans *= N[y]*N[y+1]
        ans %= mod
        y += 2
        i += 2
    else:
        break
if k%2 == 1 and len(P) == 0:
    ans = 1
    N = sorted(N, reverse=True)
    for i in range(k):
        ans *= N[i]
        ans %= mod
print(ans%mod)

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))
    #print("absL=>",absL)

    ans_cand=[v for v in absL[:K]]
    remain=[v for v in absL[K:]]
    #print("ans_cand=>",ans_cand)
    #print("remain=>",remain)

    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
        else:
            assert 1==2

        #print("ans_cand->",ans_cand)
        #print("NG=>",NG)

        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()))
mod = 10**9 + 7
P = []
N = []
for i in range(n):
    if a[i] >= 0:
        P.append(a[i])
    else:
        N.append(a[i])
P  = sorted(P, reverse=True) 
N  = sorted(N)
x = 0
y = 0
ans = 1
if k%2 == 1 and len(P) >= 1:
    ans *= P[0]
    x += 1
while 1:
    if x < len(P)-1 and y < len(N)-1:
        if P[x]*P[x+1] > N[y]*N[y+1]:
            ans *= P[x]*P[x+1]
            ans %= mod
            x += 2
        else:
            ans *= N[y]*N[y+1]
            ans %= mod
            y += 2
    elif x < len(P)-1:
        ans *= P[x]*P[x+1]
        ans %= mod
        x += 2
    elif y < len(N)-1:
        ans *= N[y]*N[y+1]
        ans %= mod
        y += 2
    else:
        break
if k%2 == 1 and len(P) == 0:
    ans = 1
    N = sorted(N, reverse=True)
    for i in range(k):
        ans *= N[i]
        ans %= mod
print(ans%mod)

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 L[-1]<=0:#全部負
    if 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:]]

    #print("ans_cand=>",ans_cand)

    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
                break

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

        #正の数を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
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a

        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
        else:
            assert 1==2

        #print("ans_cand->",ans_cand)
        #print("NG=>",NG)

        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 L[-1]<=0:#全部負
    if 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 sum([a<0 for a in L])%2==0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        #ans_candはabsの大きさでsortされている
        #できるだけ絶対ちが小さいやつ
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a
                break

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

        #正の数を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
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a

        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
        else:
            assert 1==2


        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 L[-1]<=0:#全部負
    if 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:]]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        #ans_candはabsの大きさでsortされている
        #できるだけ絶対ちが小さいやつ
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a
                break

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

        #正の数を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
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a

        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
        else:
            assert 1==2


        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()))
mod = 10**9 + 7
b_p = []
b_n = []
ab = []
for i in range(n):
    ab.append(abs(a[i]))
    if a[i] >= 0:
        b_p.append(a[i])
    else:
        b_n.append(a[i])
b_p = sorted(b_p,reverse=True)
b_n = sorted(b_n)
ab = sorted(ab)
ans = 1
i = 0
x = 0
y = 0
if k%2 == 1:
    if len(b_p) >= 1:
        ans *= b_p[0]
        x += 1
        i += 1
while i < k-1:
    i += 2
    if x < len(b_p)-1 and y < len(b_n)-1:
        if b_p[x]*b_p[x+1] >= b_n[y]*b_n[y+1]:
            ans *= b_p[x]*b_p[x+1]
            ans %= mod
            x += 2
        else:
            ans *= b_n[y]*b_n[y+1]
            ans %= mod
            y += 2
    
    elif x < len(b_p)-1:
        ans *= b_p[x]*b_p[x+1]
        ans %= mod
        x += 2
    elif y < len(b_n)-1:
        ans *= b_n[y]*b_n[y+1]
        ans %= mod
        y += 2
    else:
        break
if i != k:
    if x < len(b_p):
        ans *= b_p[x]
        ans %= mod
    else:
        if 0 in b_p:
            ans = 0
        else:
            ans = 1
            for i in range(k):
                ans *= ab[i]
                ans %= mod
            ans *= -1
print(ans%mod)

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 L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    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:]]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        #ans_candはabsの大きさでsortされている
        #できるだけ絶対ちが小さいやつ
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a
                break

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

        #正の数を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
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a

        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
        else:
            #N==Kの特殊な場合?
            pass


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

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 %= MOD
    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 %= MOD
        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)
        #print(l)

        ans = 1
        fu = 0
        for i in range(K):
            if l[i][1] < 0:
                fu += 1
            ans *= l[i][0]
            ans %= MOD

        if fu%2 == 0:
            print(ans)
        elif ans == 0:
            print(0)
        else:
            sei_suteru = -1
            fu_suteru = -1
            for i in range(K)[::-1]:
                if sei_suteru == -1:
                    if l[i][1] > 0:
                        sei_suteru = l[i][0]
                if fu_suteru == -1:
                    if l[i][1] < 0:
                        fu_suteru = l[i][0]
                
            sei_ireru = -1
            fu_ireru = -1
            for i in range(K,N):
                if sei_ireru == -1:
                    if l[i][1] > 0:
                        sei_ireru = l[i][0]
                if fu_ireru == -1:
                    if l[i][1] < 0:
                        fu_ireru = l[i][0]

            #print(ans)
            #print(sei_suteru,fu_suteru,sei_ireru,fu_ireru)
            if sei_suteru >= 0 and fu_suteru >= 0 and sei_ireru >= 0 and fu_ireru >= 0:
                if sei_ireru/fu_suteru <= fu_ireru/sei_suteru: # 正を捨てて負を入れる方がいいとき
                    ans = -ans * -fu_ireru * pow(sei_suteru,MOD-2,MOD)
                    ans %= MOD
                else: # 負を捨てて正を入れる方がいいとき
                    ans = -ans * sei_ireru * pow(-fu_suteru,MOD-2,MOD)
                    ans %= MOD
            elif sei_ireru == -1 or fu_suteru == -1:
                ans = -ans * -fu_ireru * pow(sei_suteru,MOD-2,MOD)
                ans %= MOD
            else:
                ans = -ans * sei_ireru * pow(-fu_suteru,MOD-2,MOD)
                ans %= MOD

            print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    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:]]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        #ans_candはabsの大きさでsortされている
        #できるだけ絶対ちが小さいやつ
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a
                break

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

        #正の数を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
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a

        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
        else:
            #N==Kの特殊な場合?
            pass

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

Submission status: Wrong Answer

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

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 %= MOD
    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 %= MOD
        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)
        #print(l)

        ans = 1
        fu = 0
        for i in range(K):
            if l[i][1] < 0:
                fu += 1
            ans *= l[i][0]
            ans %= MOD

        if fu%2 == 0:
            print(ans)
        elif ans == 0:
            print(0)
        else:
            sei_suteru = -1
            fu_suteru = -1
            for i in range(K)[::-1]:
                if sei_suteru == -1:
                    if l[i][1] > 0:
                        sei_suteru = l[i][0]
                if fu_suteru == -1:
                    if l[i][1] < 0:
                        fu_suteru = l[i][0]
                
            sei_ireru = -1
            fu_ireru = -1
            for i in range(K,N):
                if sei_ireru == -1:
                    if l[i][1] > 0:
                        sei_ireru = l[i][0]
                if fu_ireru == -1:
                    if l[i][1] < 0:
                        fu_ireru = l[i][0]

            #print(ans)
            #print(sei_suteru,fu_suteru,sei_ireru,fu_ireru)
            if sei_suteru >= 0 and fu_suteru >= 0 and sei_ireru >= 0 and fu_ireru >= 0:
                if sei_ireru/fu_suteru <= fu_ireru/sei_suteru: # 正を捨てて負を入れる方がいいとき
                    ans = -ans * -fu_ireru * pow(sei_suteru,MOD-2,MOD)
                    ans %= MOD
                else: # 負を捨てて正を入れる方がいいとき
                    ans = -ans * sei_ireru * pow(-fu_suteru,MOD-2,MOD)
                    ans %= MOD
            elif sei_ireru == -1 or fu_suteru == -1:
                    ans = -ans * sei_ireru * pow(-fu_suteru,MOD-2,MOD)
                    ans %= MOD
            else:
                ans = -ans * -fu_ireru * pow(sei_suteru,MOD-2,MOD)
                ans %= MOD

            print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))
    cand=[v for v in absL[:K]]
    
    ans_cand=cand[-K:]
    remain=cand[:-K]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        #ans_candはabsの大きさでsortされている
        #できるだけ絶対ちが小さいやつ
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a
                break

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

        #正の数を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
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a

        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
        else:
            #N==Kの特殊な場合?
            pass

        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
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/ss>=ts/sh:
                    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)