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())
*a,=map(int, input().split())

ans=1
mod=10**9+7

a.sort()
if a[0]>=0:
    for i in range(n-1,n-k,-1):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
if a[-1]<=0:
    if k%2:
        for i in range(n-1,n-k-1,-1):
            ans*=a[i]
            ans%=mod
    else:
        for i in range(k):
            ans*=a[i]
            ans%=mod
    print(ans)
    exit()
l=0;r=n-1
if k%2:
    ans=a[-1]
    r-=1
    k-=1
while k:
    if k>=2:
        if a[l]*a[l+1]>a[r]*a[r-1]:
            ans*=a[l]*a[l+1]
            l+=2
        else:
            ans*=a[r]*a[r-1]
            r-=2
        k-=2
        ans%=mod
    else:
        if a[l]>a[r]:
            ans*=a[l]
        else:
            ans*=a[r]
        k-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from decimal import Decimal


read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N, K = in_nn()
    A = in_nl()

    #import random
    #N, K = 1, 1
    #A = [random.randint(-10**9, 10**9) for _ in range(N)]
    mod = 10 ** 9 + 7

    Am = []
    Ap = []

    for i in range(N):
        if A[i] < 0:
            Am.append(A[i])
        elif A[i] >= 0:
            Ap.append(A[i])

    Ap = list(sorted(Ap, reverse=True))
    Am = list(sorted(Am))

    Nm = len(Am)
    Np = len(Ap)

    if Nm == 0:
        ans = 1
        for i in range(K):
            ans *= Ap[i]
            ans %= mod
    elif Nm == 1:
        if Nm + Np == K:
            ans = Am[0]
            for i in range(K - 1):
                ans *= Ap[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Ap[i]
                ans %= mod
    elif Np == 0:
        if K % 2 == 0:
            ans = 1
            for i in range(K):
                ans *= Am[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Am[Nm - 1 - i]
                ans %= mod
    else:
        if K % 2 == 0:
            if Np % 2 == 0:
                pi = Np
                mi = 0
            else:
                pi = Np - 1
                mi = 2
        else:
            if Np % 2 == 0:
                pi = Np - 1
                mi = 2
            else:
                pi = Np
                mi = 0
        rate = Decimal(1)
        max_rate = Decimal(1)
        max_i = (pi, mi)
        while True:
            pi -= 2
            mi += 2
            if pi >= 0 and mi <= Nm:
                tm = Decimal(Am[mi - 2] * Am[mi - 1])
                tp = Decimal(Ap[pi - 1] * Ap[pi])
                if tp == 0:
                    break
                rate *= tm / tp
                if max_rate < rate:
                    max_rate = rate
                    max_i = (pi, mi)
            else:
                break
        pi, mi = max_i
        ans = 1
        for i in range(pi):
            ans *= Ap[i]
            ans %= mod
        for i in range(mi):
            ans *= Am[i]
            ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
*a,=map(int, input().split())

ans=1
mod=10**9+7

a.sort()
if a[0]>=0:
    for i in range(n-1,n-k,-1):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
if a[-1]<=0:
    if k%2:
        for i in range(n-1,n-k-1,-1):
            ans*=a[i]
            ans%=mod
    else:
        for i in range(k):
            ans*=a[i]
            ans%=mod
    print(ans)
    exit()
l=0;r=n-1
if k%2:
    ans=a[0]
    l=1
    k-=1
while k:
    if k>=2:
        if a[l]*a[l+1]>a[r]*a[r-1]:
            ans*=a[l]*a[l+1]
            l+=2
        else:
            ans*=a[r]*a[r-1]
            r-=2
        k-=2
        ans%=mod
    else:
        if a[l]>a[r]:
            ans*=a[l]
        else:
            ans*=a[r]
        k-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from decimal import Decimal

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N, K = in_nn()
    A = in_nl()
    mod = 10 ** 9 + 7

    Am = []
    Ap = []

    for i in range(N):
        if A[i] < 0:
            Am.append(A[i])
        elif A[i] >= 0:
            Ap.append(A[i])

    Ap = list(sorted(Ap, reverse=True))
    Am = list(sorted(Am))

    Nm = len(Am)
    Np = len(Ap)

    if Nm == 0:
        ans = 1
        for i in range(K):
            ans *= Ap[i]
            ans %= mod
    elif Nm == 1:
        if Nm + Np == K:
            ans = Am[0]
            for i in range(K - 1):
                ans *= Ap[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Ap[i]
                ans %= mod
    elif Np == 0:
        if K % 2 == 0:
            ans = 1
            for i in range(K):
                ans *= Am[i]
                ans %= mod
        else:
            ans = 1
            for i in range(K):
                ans *= Am[Nm - 1 - i]
                ans %= mod
    else:
        print(0)
        exit()
        if K % 2 == 0:
            if Np % 2 == 0:
                pi = Np
                mi = 0
            else:
                pi = Np - 1
                mi = 2
        else:
            if Np % 2 == 0:
                pi = Np - 1
                mi = 2
            else:
                pi = Np
                mi = 0
        rate = Decimal(1)
        max_rate = Decimal(1)
        max_i = (pi, mi)
        while True:
            pi -= 2
            mi += 2
            if pi >= 0 and mi <= Nm:
                tm = Decimal(Am[mi - 2] * Am[mi - 1])
                tp = Decimal(Ap[pi - 1] * Ap[pi])
                rate *= tm / tp
                if max_rate < rate:
                    max_rate = rate
                    max_i = (pi, mi)
            else:
                break
        pi, mi = max_i
        ans = 1
        for i in range(pi):
            ans *= Ap[i]
            ans %= mod
        for i in range(mi):
            ans *= Am[i]
            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
negs = [-x for x in A if x < 0]
non_negs = [x for x in A if x >= 0]


def inv(a):
    return pow(a, mod - 2, mod)


# 負の数を選ばざるを得ない数を考える
# 選べる負の数の個数の最小
n_min = k - (max(n - len(negs), 0))
# 　選べる負の数の個数の最大
n_max = min(n, k)

# この2数が一致していて、更に奇数のときにのみ負になる。(はず)
if n_max == n_min and n_max % 2 == 1:
    negs.sort()
    non_negs.sort()
    cnt = 0
    ans = 1
    n_idx, nn_idx = 0, 0
    while cnt < k:
        if n_idx == len(negs):
            ans *= non_negs[nn_idx]
            nn_idx += 1
        elif nn_idx == len(non_negs):
            ans *= -negs[n_idx]
            n_idx += 1
        else:
            if non_negs[nn_idx] < negs[n_idx]:
                ans *= non_negs[nn_idx]
                nn_idx += 1
            else:
                ans *= -negs[n_idx]
                n_idx += 1
        ans %= mod
        cnt += 1

    print(ans % mod)
    exit()

negs.sort(reverse=True)
non_negs.sort(reverse=True)

cnt = 0
ans = 1
neg_cnt = 0
n_idx, nn_idx = 0, 0
# idx番号と配列の長さを比較して、その配列から取得可能かをみる
while cnt < k:
    if n_idx == len(negs):
        ans *= non_negs[nn_idx]
        nn_idx += 1
    elif nn_idx == len(non_negs):
        ans *= -negs[n_idx]
        n_idx == 1
        neg_cnt += 1
    else:
        if non_negs[nn_idx] > negs[n_idx]:
            ans *= non_negs[nn_idx]
            nn_idx += 1
        else:
            ans *= -negs[n_idx]
            n_idx += 1
            neg_cnt += 1
    ans %= mod
    cnt += 1

# 動かす余地がない場合→negが偶数個or動かす余裕がない
if neg_cnt % 2 == 0 or n == k:
    # REからここがおかしそう…
    print(ans % mod)
    exit()
else:
    # 次にかけるのはnegs[n_idx] or non_negs[nn_idx]
    # 一つ戻すならnegs[n_idx-1] or non_negs[nn_idx-1]

    # negsが右にずらせるかどうか
    if n_idx == len(negs) or nn_idx == 0:
        ans *= inv(-negs[n_idx - 1])
        ans *= non_negs[nn_idx]
        ans %= mod
    # non_negsが右にずらせるか
    elif nn_idx == len(non_negs) or n_idx == 0:
        ans *= inv(non_negs[nn_idx - 1])
        ans *= -negs[n_idx]
        ans %= mod
    else:
        # 両方ともずらせないのはすでに除外済み(のはず)
        if non_negs[nn_idx] * non_negs[nn_idx - 1] > negs[n_idx] * negs[n_idx - 1]:
            ans *= non_negs[nn_idx]
            ans *= inv(-negs[n_idx - 1])
            ans %= mod
        else:
            ans *= -negs[n_idx]
            ans *= inv(non_negs[nn_idx - 1])
            ans %= mod

    print(ans % mod)
    exit()

Submission status: Wrong Answer

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

    if N == K:
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD

        print(ans)
        return 

    if K % 2 != 0 and len(list(filter(lambda a: a<0, A))) == N:
        A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD

        print(ans)
        return 

    A.sort(key=abs, reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    
    if ans >= 0:
        print(ans)
        return

    x1 = 1
    y1 = 1
    for i in range(K-1,-1,-1):
        if A[i] < 0:
            x1 = A[i]
            break
    
    for i in range(K,N):
        if A[i] >= 0:
            y1 = A[i]
            break
    
    x2 = 1
    y2 = 1
    for i in range(K-1,-1,-1):
        if A[i] >= 0:
            x2 = A[i]
            break
    
    for i in range(K,N):
        if A[i] < 0:
            y2 = A[i]
            break
    
    prod = max(x1*y1, x2*y2) % MOD
    
    print(ans // prod % MOD)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

    if N == K:
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD

        print(ans)
        return 

    if K % 2 != 0 and len(list(filter(lambda a: a<0, A))) == N:
        A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD

        print(ans)
        return 

    A.sort(key=abs, reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    
    if ans >= 0:
        print(ans)
        return

    x1 = 1
    y1 = 1
    for i in range(K-1,-1,-1):
        if A[i] < 0:
            x1 = A[i]
            break
    
    for i in range(K,N):
        if A[i] >= 0:
            y1 = A[i]
            break
    
    x2 = 1
    y2 = 1
    for i in range(K-1,-1,-1):
        if A[i] >= 0:
            x2 = A[i]
            break
    
    for i in range(K,N):
        if A[i] < 0:
            y2 = A[i]
            break
    
    prod = max(x1*y1, x2*y2) % MOD
    
    print(ans * prod % MOD)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        return
    
    if all(a < 0 for a in A) and K%2 == 1:
        A.sort(reverse = True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return
    
    A.sort(key = abs,reverse = True)
    cnt_m = 0
    ans = 1
    last_p = -1
    last_m = 1
    for i in range(K):
        if A[i] == 0:
            print(0)
            return
        elif A[i] < 0:
            ans *= A[i]
            ans %= MOD
            cnt_m += 1
            last_m = A[i]
        else:
            ans *= A[i]
            ans %= MOD
            last_p = A[i]
    if cnt_m%2 == 0:
        print(ans)
    else:
        diff1 = last_p
        diff2 = last_m
        inv1 = pow(last_m,MOD - 2,MOD)
        inv2 = pow(last_p,MOD - 2,MOD)
        for i in range(K,N):
            if A[i] >= 0:
                diff1 *= A[i]
                inv1 *= A[i]
                inv1 %= MOD
                break
            if i == N - 1:
                diff1 = -1
        for i in range(K,N):
            if A[i] < 0:
                diff2 *= A[i]
                inv2 *= A[i]
                inv2 %= MOD
                break
            if i == N - 1:
                diff2 = -1
        
        if diff1 < diff2:
            ans *= inv2
            ans %= MOD
        else:
            ans *= inv1
            ans %= MOD
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0

#tmp = k-pl
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3#mn
elif zr >= 1 and pl == 0 and k % 2 == 1:
    hugo = 2#zr
else:
    hugo = 1#pl

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 1
                tmp_m_seki = 1
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                #elif tmp_p_seki == 0 and tmp_m_seki == 0:
                #    tmp_seki = 0
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            elif tmp == 1:
                tmp_seki = a[n-1-pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0

#tmp = k-pl
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3#mn
elif zr >= 1 and pl == 0 and k % 2 == 1:
    hugo = 2#zr
else:
    hugo = 1#pl

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 0
                tmp_m_seki = 0
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                #elif tmp_p_seki == 0 and tmp_m_seki == 0:
                #    tmp_seki = 0
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            elif tmp == 1:
                tmp_seki = a[n-1-pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0

#tmp = k-pl
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3#mn
elif zr >= 1 and pl == 0 and k % 2 == 1:
    hugo = 2#zr
else:
    hugo = 1#pl

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 0
                tmp_m_seki = 0
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                elif tmp_p_seki == 0 and tmp_m_seki == 0:
                    tmp_seki = 0
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            elif tmp == 1:
                tmp_seki = a[n-1-pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Wrong Answer

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

    if K % 2 != 0 and len(list(filter(lambda a: a<0, A))) == N:
        A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD

        print(ans)
        return 

    A.sort(key=abs, reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    
    if ans >= 0:
        print(ans)
        return

    ans2 = ans
    for i in range(K-1,-1,-1):
        if A[i] < 0:
            ans2 //= A[i]
            break
    
    for i in range(K,N):
        if A[i] >= 0:
            ans2 *= A[i]
            break
    
    ans3 = ans
    for i in range(K-1,-1,-1):
        if A[i] >= 0:
            ans3 //= A[i]
            break
    
    for i in range(K,N):
        if A[i] < 0:
            ans3 *= A[i]
            break
    
    print(max(ans2, ans3) % MOD)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0

#tmp = k-pl
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3#mn
elif zr >= 1 and pl == 0 and k % 2 == 1:
    hugo = 2#zr
else:
    hugo = 1#pl

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 1
                tmp_m_seki = 1
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                elif tmp_p_seki == 0 and tmp_m_seki == 0:
                    tmp_seki = 0
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            elif tmp == 1:
                tmp_seki = a[n-1-pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Wrong Answer

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

    if K % 2 != 0 and len(list(filter(lambda a: a<0, A))) == N:
        A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]

        print(ans%MOD)
        return 

    A.sort(key=abs, reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
    
    if ans >= 0:
        print(ans%MOD)
        return

    ans2 = ans
    for i in range(K-1,-1,-1):
        if A[i] < 0:
            ans2 //= A[i]
            break
    
    for i in range(K,N):
        if A[i] >= 0:
            ans2 *= A[i]
            break
    
    ans3 = ans
    for i in range(K-1,-1,-1):
        if A[i] >= 0:
            ans3 //= A[i]
            break
    
    for i in range(K,N):
        if A[i] < 0:
            ans3 *= A[i]
            break
    
    print(max(ans2, ans3) % MOD)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys

mod = 10 ** 9 + 7

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

if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

plus = []
minus = []

for i in range(N):
    if A[i] < 0:
        minus.append(A[i])
    else:
        plus.append(A[i])

if len(minus) == N:
    minus.sort(reverse = True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

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

ans = 1
flag = 0
if K % 2 == 1:
    flag = 1
    K -= 1
    ans *= plus[0]

n_plus = [(plus[i+flag] * plus[i+flag+1]) % mod for i in range((len(plus)-flag)//2)]
n_minus = [(minus[i] * minus[i+1]) % mod for i in range(len(minus)//2)]

p = 0
m = 0
for i in range(K//2):
    if p == len(n_plus):
        ans *= n_minus[m]
        ans %= mod
        m += 1
    elif m == len(n_minus):
        ans *= n_plus[p]
        ans %= mod
        p += 1
    elif n_plus[p] > n_minus[m]:
        ans *= n_plus[p]
        ans %= mod
        p += 1
    else:
        ans *= n_minus[m]
        ans %= mod
        m += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        return
    
    if all(a < 0 for a in A) and K%2 == 1:
        A.sort(reverse = True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return
    
    A.sort(key = abs,reverse = True)
    cnt_m = 0
    ans = 1
    last_p = -1
    last_m = 1
    for i in range(K):
        if A[i] == 0:
            print(0)
            return
        elif A[i] < 0:
            ans *= A[i]
            cnt_m += 1
            last_m = A[i]
        else:
            ans *= A[i]
            last_p = A[i]
    if cnt_m%2 == 0:
        print(ans)
    else:
        diff1 = last_p
        diff2 = last_m
        inv1 = pow(last_m,MOD - 2,MOD)
        inv2 = pow(last_p,MOD - 2,MOD)
        for i in range(K,N):
            if A[i] >= 0:
                diff1 *= A[i]
                inv1 *= A[i]
                inv1 %= MOD
                break
        for i in range(K,N):
            if A[i] < 0:
                diff2 *= A[i]
                inv2 *= A[i]
                inv2 %= MOD
                break
            if i == N - 1:
                diff2 = -1
        
        if diff1 < diff2:
            ans *= inv2
            ans %= MOD
        else:
            ans *= inv1
            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
negs = [-x for x in A if x < 0]
non_negs = [x for x in A if x >= 0]


def inv(a):
    return pow(a, mod - 2, mod)


# 負の数を選ばざるを得ない数を考える
# 選べる負の数の個数の最小
n_min = k - (max(n - len(negs), 0))
# 　選べる負の数の個数の最大
n_max = min(n, k)

# この2数が一致していて、更に奇数のときにのみ負になる。(はず)
if n_max == n_min and n_max % 2 == 1:
    negs.sort()
    non_negs.sort()
    cnt = 0
    ans = 1
    n_idx, nn_idx = 0, 0
    while cnt < k:
        if n_idx == len(negs):
            ans *= non_negs[nn_idx]
            nn_idx += 1
        elif nn_idx == len(non_negs):
            ans *= -negs[n_idx]
            n_idx += 1
        else:
            if non_negs[nn_idx] < negs[n_idx]:
                ans *= non_negs[nn_idx]
                nn_idx += 1
            else:
                ans *= -negs[n_idx]
                n_idx += 1
        ans %= mod
        cnt += 1

    print(ans % mod)
    exit()

negs.sort(reverse=True)
non_negs.sort(reverse=True)

cnt = 0
ans = 1
neg_cnt = 0
n_idx, nn_idx = 0, 0
# idx番号と配列の長さを比較して、その配列から取得可能かをみる
while cnt < k:
    if n_idx == len(negs):
        ans *= non_negs[nn_idx]
        nn_idx += 1
    elif nn_idx == len(non_negs):
        ans *= -negs[n_idx]
        n_idx == 1
        neg_cnt += 1
    else:
        if non_negs[nn_idx] > negs[n_idx]:
            ans *= non_negs[nn_idx]
            nn_idx += 1
        else:
            ans *= -negs[n_idx]
            n_idx += 1
            neg_cnt += 1
    ans %= mod
    cnt += 1

if neg_cnt % 2 == 0 or n == k:
    # REからここがおかしそう…
    print(ans % mod)
else:

    # 次にかけるのはnegs[n_idx] or non_negs[nn_idx]
    # 一つ戻すならnegs[n_idx-1] or non_negs[nn_idx-1]

    # negsが右にずらせるかどうか
    if n_idx == len(negs) or nn_idx == 0:
        ans *= inv(-negs[n_idx - 1])
        ans *= non_negs[nn_idx]
        ans %= mod
    # non_negsが右にずらせるか
    elif nn_idx == len(non_negs) or n_idx == 0:
        ans *= inv(non_negs[nn_idx - 1])
        ans *= -negs[n_idx]
        ans %= mod
    else:
        # 両方ともずらせないのはすでに除外済み(のはず)
        if non_negs[nn_idx] * non_negs[nn_idx - 1] > negs[n_idx] * negs[n_idx - 1]:
            ans *= non_negs[nn_idx]
            ans *= inv(-negs[n_idx - 1])
            ans %= mod
        else:
            ans *= -negs[n_idx]
            ans *= inv(non_negs[nn_idx - 1])
            ans %= mod

    print(ans % mod)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
negs = [-x for x in A if x < 0]
non_negs = [x for x in A if x >= 0]


def inv(a):
    return pow(a, mod - 2, mod)


# 負の数を選ばざるを得ない数を考える
# 選べる負の数の個数の最小
n_min = k - (max(n - len(negs), 0))
# 　選べる負の数の個数の最大
n_max = min(n, k)

# この2数が一致していて、更に奇数のときにのみ負になる。(はず)
if n_max == n_min and n_max % 2 == 1:
    negs.sort()
    non_negs.sort()
    cnt = 0
    ans = 1
    n_idx, nn_idx = 0, 0
    while cnt < k:
        if n_idx == len(negs):
            ans *= non_negs[nn_idx]
            nn_idx += 1
        elif nn_idx == len(non_negs):
            ans *= -negs[n_idx]
            n_idx += 1
        else:
            if non_negs[nn_idx] < negs[n_idx]:
                ans *= non_negs[nn_idx]
                nn_idx += 1
            else:
                ans *= -negs[n_idx]
                n_idx += 1
        ans %= mod
        cnt += 1

    print(ans % mod)
    exit()

negs.sort(reverse=True)
non_negs.sort(reverse=True)

cnt = 0
ans = 1
neg_cnt = 0
n_idx, nn_idx = 0, 0
# idx番号と配列の長さを比較して、その配列から取得可能かをみる
while cnt < k:
    if n_idx == len(negs):
        ans *= non_negs[nn_idx]
        nn_idx += 1
    elif nn_idx == len(non_negs):
        ans *= -negs[n_idx]
        n_idx == 1
        neg_cnt += 1
    else:
        if non_negs[nn_idx] > negs[n_idx]:
            ans *= non_negs[nn_idx]
            nn_idx += 1
        else:
            ans *= -negs[n_idx]
            n_idx += 1
            neg_cnt += 1
    ans %= mod
    cnt += 1

if neg_cnt % 2 == 0 or n == k:
    # REからここがおかしそう…
    print(ans % mod)
else:

    # 次にかけるのはnegs[n_idx] or non_negs[nn_idx]
    # 一つ戻すならnegs[n_idx-1] or non_negs[nn_idx-1]

    # negsが右にずらせるかどうか
    if n_idx == len(negs) or nn_idx == 0:
        ans *= inv(negs[n_idx - 1])
        ans *= non_negs[nn_idx]
        ans %= mod
    # non_negsが右にずらせるか
    elif nn_idx == len(non_negs) or n_idx == 0:
        ans *= inv(non_negs[nn_idx - 1])
        ans *= negs[n_idx]
        ans %= mod
    else:
        # 両方ともずらせないのはすでに除外済み(のはず)
        if non_negs[nn_idx] * non_negs[nn_idx - 1] > negs[n_idx] * negs[n_idx - 1]:
            ans *= non_negs[nn_idx]
            ans *= inv(negs[n_idx - 1])
            ans %= mod
        else:
            ans *= negs[n_idx]
            ans *= inv(non_negs[nn_idx - 1])
            ans %= mod

    print(ans % mod)

Submission status: Wrong Answer

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

    if K % 2 != 0 and len(list(filter(lambda a: a<0, A))) == N:
        A.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD

        print(ans)
        return 

    A.sort(key=abs, reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    
    if ans >= 0:
        print(ans)
        return

    ans2 = ans
    for i in range(K-1,-1,-1):
        if A[i] < 0:
            ans2 //= A[i]
            break
    
    for i in range(K,N):
        if A[i] >= 0:
            ans2 *= A[i]
            break
    
    ans3 = ans
    for i in range(K-1,-1,-1):
        if A[i] >= 0:
            ans3 //= A[i]
            break
    
    for i in range(K,N):
        if A[i] < 0:
            ans3 *= A[i]
            break
    
    print(max(ans2%MOD, ans3%MOD))

if __name__ == '__main__':
    solve()