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 numpy as np

MOD = 10**9 + 7
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
ans = 1
plus = a[a >= 0]
plus = np.sort(plus)[::-1]
plus = np.append(plus, [-np.inf, np.inf])
minus = a[a < 0]
minus = np.sort(minus)
minus = np.append(minus, [np.inf, -np.inf])
if n == k:
    for i in range(len(a)):
        ans *= a[i]
        ans %= MOD
    print(ans)
    exit()
if len(plus) == 2 and k % 2 == 1:
    for i in range(3, k + 3):
        ans *= minus[-i]
        ans %= MOD
else:
    c = 0
    cplus = 0
    cminus = 0
    while c < k - 1:
        if plus[cplus] * plus[cplus + 1] > minus[cminus] * minus[cminus + 1]:
            ans *= plus[cplus]
            ans %= MOD
            cplus += 1
            c += 1
        else:
            ans *= minus[cminus] * minus[cminus + 1]
            ans %= MOD
            cminus += 2
            c += 2
    if c == k - 1:
        ans *= plus[cplus]
print(int(ans))

Submission status: Wrong Answer

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


def solve(N, K, A):
    ans = 1
    # K = N の場合は明らか
    if K == N:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    # Ai の全ての数が負かつ K が奇数のとき、
    elif max(A) < 0 and K % 2 == 1:
        A.sort(reverse=True)
        # 絶対値が小さい方から K 個の積
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    # それ以外の場合、積は必ず非負
    else:
        A_nonneg = [a for a in A if a >= 0]
        A_neg = [a for a in A if a < 0]
        A_nonneg.sort()
        A_neg.sort(reverse=True)
        s = 0
        while s < K:

            if s == K - 2 and len(A_nonneg) == 1:
                neg = True
            elif len(A_neg) < 2:
                neg = False
            elif len(A_nonneg) < 1:
                neg = True
            elif s == K - 1:
                neg = False
            # 「まだ選んでいない非負の要素のうち絶対値が大きい順の 2 つ x1, x2 の積」と「まだ選んでいない負の要素のうち絶対値が大きい順の 2 つ y1, y2 の積」を比較す
            elif A_nonneg[-1] > A_neg[-1] * A_neg[-2]:
                neg = False
            else:
                neg = True

            if neg:
                s += 2
                ans *= A_neg.pop()
                ans *= A_neg.pop()
            else:
                s += 1
                ans *= A_nonneg.pop()

            ans %= MOD
    return ans


print(solve(N, K, A))

Submission status: Wrong Answer

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


def solve(N, K, A):
    ans = 1
    if N == K:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    elif max(A) < 0 and K % 2 == 1:
        A.sort(reverse=True)
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    else:
        A_nonneg = [a for a in A if a >= 0]
        A_neg = [a for a in A if a < 0]
        A_nonneg.sort()
        A_neg.sort(reverse=True)
        s = 0
        while s < K:
            if len(A_neg) < 2:
                neg = False
            elif len(A_nonneg) < 1:
                neg = True
            elif s == K - 1:
                neg = False
            elif s == K - 2 and len(A_neg) == 1:
                neg = True
            # 大小関係
            elif A_nonneg[-1] > A_neg[-1] * A_neg[-2]:
                neg = False
            else:
                neg = True

            if neg:
                s += 2
                ans *= A_neg.pop()
                ans *= A_neg.pop()
            else:
                s += 1
                ans *= A_nonneg.pop()

            ans %= MOD
    return ans


print(solve(N, K, A))

Submission status: Wrong Answer

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


def solve(N, K, A):
    ans = 1
    if N == K:
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    elif max(A) < 0 and K % 2 == 1:
        A.sort(reverse=True)
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    else:
        A_nonneg = [a for a in A if a >= 0]
        A_neg = [a for a in A if a < 0]
        A_nonneg.sort()
        A_neg.sort(reverse=True)
        count = 0
        while count < K:
            if len(A_nonneg) >= 1 and (
                count == K - 1 or len(A_neg) < 2 or A_nonneg[-1] > A_neg[-1] * A_neg[-2]
            ):
                count += 1
                ans *= A_nonneg.pop()
            else:
                count += 2
                ans *= A_neg.pop()
                ans *= A_neg.pop()
            ans %= MOD
    return ans


print(solve(N, K, A))


pass

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    A=list(mi())
    MOD=10**9+7

    if K == 1:
        A.sort(reverse=True)
        print(A[0]%MOD)
        exit()

    B = []
    NEG = []
    for a in A:
        if a == 0: continue
        is_neg = a < 0
        B.append((abs(a),is_neg))
        if is_neg:
            NEG.append(-a)
    
    B.sort(reverse=True)
    if len(B) < K:
        print(0)
        exit()
    
    X = B[:K]
    negs = 0
    neg_min = INF
    neg_max = 0
    neg_min_i = 0
    ans = 1
    for i in range(len(X)):
        x = X[i]
        a,is_neg = x

        ans *= a % MOD
        ans %= MOD
        if is_neg:
            negs += 1

            neg_max = max(neg_max,a)
            if neg_min > a:
                neg_min = a
                neg_min_i = i
    
    if negs % 2 == 1:
        pos_max = -INF
        unseen_neg_min = INF
        
        j = neg_min_i+1
        while 0<= j < len(B):
            x,is_neg = B[j]
            # print(x)
            if not is_neg:
                pos_max = max(pos_max,x)
            else:
                unseen_neg_min = min(x,unseen_neg_min)

            j+=1

        if pos_max != -INF: # 正が見つかったら
            ans *= pow(neg_min,MOD-2,MOD) * pos_max % MOD
            ans %= MOD
        else:
            # print(unseen_neg_min)
            unseen_neg_min = unseen_neg_min if unseen_neg_min != INF else neg_max
            ans *= pow(neg_max,MOD-2,MOD) * unseen_neg_min % MOD
            ans *= MOD-1

    print(ans % MOD)
    # print(MOD-ans%MOD)








if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    A=list(mi())
    MOD=10**9+7

    if K == 1:
        A.sort(reverse=True)
        print(A[0]%MOD)
        exit()

    B = []
    NEG = []
    for a in A:
        if a == 0: continue
        is_neg = a < 0
        B.append((abs(a),is_neg))
        if is_neg:
            NEG.append(-a)
    
    B.sort(reverse=True)
    if len(B) < K:
        print(0)
        exit()
    
    X = B[:K]
    negs = 0
    neg_min = INF
    neg_max = 0
    neg_min_i = 0
    ans = 1
    for i in range(len(X)):
        x = X[i]
        a,is_neg = x

        ans *= a % MOD
        ans %= MOD
        if is_neg:
            negs += 1

            neg_max = max(neg_max,a)
            if neg_min > a:
                neg_min = a
                neg_min_i = i
    
    if negs % 2 == 1:
        pos_max = -INF
        unseen_neg_min = INF
        
        j = N-K+neg_min_i
        while 0<= j < len(B):
            x,is_neg = B[j]
            if not is_neg:
                pos_max = max(pos_max,x)
            else:
                unseen_neg_min = min(x,unseen_neg_min)

            j+=1

        if pos_max != -INF: # 正が見つかったら
            ans *= pow(neg_min,MOD-2,MOD) * pos_max % MOD
            ans %= MOD
        else:
            # print(unseen_neg_min)
            unseen_neg_min = unseen_neg_min if unseen_neg_min != INF else neg_max
            ans *= pow(neg_max,MOD-2,MOD) * unseen_neg_min % MOD
            ans *= MOD-1

    print(ans % MOD)
    # print(MOD-ans%MOD)








if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,K=mi()
    A=list(mi())
    MOD=10**9+7

    if K == 1:
        A.sort(reverse=True)
        print(A[0])
        exit()

    B = []
    NEG = []
    for a in A:
        if a == 0: continue
        is_neg = a < 0
        B.append((abs(a),is_neg))
        if is_neg:
            NEG.append(-a)
    
    B.sort(reverse=True)
    if len(B) < K:
        print(0)
        exit()
    
    X = B[:K]
    negs = 0
    neg_min = INF
    neg_max = 0
    neg_min_i = 0
    ans = 1
    for i in range(len(X)):
        x = X[i]
        a,is_neg = x

        ans *= a % MOD
        ans %= MOD
        if is_neg:
            negs += 1

            neg_max = max(neg_max,a)
            if neg_min > a:
                neg_min = a
                neg_min_i = i
    
    if negs % 2 == 1:
        pos_max = INF
        while neg_min_i < len(X):
            x,is_neg = X[neg_min_i]
            if not is_neg:
                pos_max = x
                break
            neg_min_i+=1

        if pos_max != INF:
            ans *= pow(neg_min,MOD-2,MOD) * pos_max % MOD
            ans %= MOD
        else:
            NEG.sort()
            ans *= pow(neg_max,MOD-2,MOD) * NEG[0] % MOD
            ans *= MOD-1

    print(ans % MOD)








if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    if K == 1:
        print(max(A))
        return
    positive = 0
    zero = 0
    negative = 0
    for a in A:
        if a > 0:
            positive += 1
        elif a == 0:
            zero += 1
        else:
            negative += 1
    if positive+negative < K:
        print(0)
        return
    if positive == 0:
        if K%2 == 1:
            if zero > 0:
                print(0)
                return
            else:
                A.sort(reverse=True)
                ans = 1
                for a in A[:K]:
                    ans *= a
                    ans %= Q
                print(ans)
                return
        else:
            A.sort()
            ans = 1
            for a in A[:K]:
                ans *= a
                ans %= Q
            print(ans)
            return
    # if K == 2:
    #     if negative <= 1:
    #         A.sort(reverse=True)
    #         print(A[0]*A[1]%Q)
    #         return
    if negative <= 1:
        A.sort(reverse=True)
        ans = 1
        for a in A[:K]:
            ans *= a
            ans %= Q
        print(ans)
        return
    if K == negative + positive:
        if negative%2 == 1:
            if zero > 0:
                print(0)
                return
        ans = 1
        for a in A:
            if a != 0:
                ans *= a
                ans %= Q
        print(ans)
        return
    print("Ok")
    B = [(abs(a), a) for a in A]
    B.sort(reverse = True)
    minus = False
    minus_value = 0
    plus_value = 0
    ans = 1
    for b in B[:K]:
        ans *= b[0]
        ans %= Q
        if b[1] < 0:
            minus = not minus
            minus_value = b[0]
        elif b[1] > 0:
            plus_value = b[0]
    if minus:
        ans_plus = ans_minus = ans
        plus_replaced_value = 0
        minus_replaced_value = 0
        if minus_value > 0:
            for b in B[K:]:
                if b[1] > 0:
                    ans_plus = ans*pow(minus_value,Q-2,Q)%Q*b[0]%Q
                    plus_replaced_value = plus_value*b[0]
                    break
        if plus_value > 0:
            for b in B[K:]:
                if b[1] < 0:
                    ans_minus = ans*pow(plus_value,Q-2,Q)%Q*b[0]%Q
                    minus_replaced_value = minus_value*b[0]
                    break
        if plus_replaced_value == 0 and minus_replaced_value == 0:
            pass
        elif plus_replaced_value < minus_replaced_value:
            ans = ans_minus
        else:
            ans = ans_plus
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    if K == 1:
        print(max(A))
        return
    positive = 0
    zero = 0
    negative = 0
    for a in A:
        if a > 0:
            positive += 1
        elif a == 0:
            zero += 1
        else:
            negative += 1
    if positive+negative < K:
        print(0)
        return
    if positive == 0:
        if K%2 == 1:
            if zero > 0:
                print(0)
                return
            else:
                A.sort(reverse=True)
                ans = 1
                for a in A[:K]:
                    ans *= a
                    ans %= Q
                print(ans)
                return
        else:
            A.sort()
            ans = 1
            for a in A[:K]:
                ans *= a
                ans %= Q
            print(ans)
            return
    # if K == 2:
    #     if negative <= 1:
    #         A.sort(reverse=True)
    #         print(A[0]*A[1]%Q)
    #         return
    if negative <= 1:
        A.sort(reverse=True)
        ans = 1
        for a in A[:K]:
            ans *= a
            ans %= Q
        print(ans)
        return
    if K == negative + positive:
        if negative%2 == 1:
            if zero > 0:
                print(0)
                return
        ans = 1
        for a in A:
            if a != 0:
                ans *= a
                ans %= Q
        print(ans)
        return
            
    B = [(abs(a), a) for a in A]
    B.sort(reverse = True)
    minus = False
    minus_value = 0
    plus_value = 0
    ans = 1
    for b in B[:K]:
        ans *= b[0]
        ans %= Q
        if b[1] < 0:
            minus = not minus
            minus_value = b[0]
        elif b[1] > 0:
            plus_value = b[0]
    # if minus:
    #     ans_plus = ans_minus = ans
    #     plus_replaced_value = 0
    #     minus_replaced_value = 0
    #     if minus_value > 0:
    #         for b in B[K:]:
    #             if b[1] > 0:
    #                 ans_plus = ans*pow(minus_value,Q-2,Q)%Q*b[0]%Q
    #                 plus_replaced_value = plus_value*b[0]
    #                 break
    #     if plus_value > 0:
    #         for b in B[K:]:
    #             if b[1] < 0:
    #                 ans_minus = ans*pow(plus_value,Q-2,Q)%Q*b[0]%Q
    #                 minus_replaced_value = minus_value*b[0]
    #                 break
    #     if plus_replaced_value == 0 and minus_replaced_value == 0:
    #         pass
    #     elif plus_replaced_value < minus_replaced_value:
    #         ans = ans_minus
    #     else:
    #         ans = ans_plus
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    if K == 1:
        print(max(A))
        return
    positive = 0
    zero = 0
    negative = 0
    for a in A:
        if a > 0:
            positive += 1
        elif a == 0:
            zero += 1
        else:
            negative += 1
    if positive+negative < K:
        print(0)
        return
    if positive == 0:
        if K%2 == 1:
            if zero > 0:
                print(0)
                return
            else:
                A.sort(reverse=True)
                ans = 1
                for a in A[:K]:
                    ans *= a
                    ans %= Q
                print(ans)
                return
        else:
            A.sort()
            ans = 1
            for a in A[:K]:
                ans *= a
                ans %= Q
            print(ans)
            return
    # if K == 2:
    #     if negative <= 1:
    #         A.sort(reverse=True)
    #         print(A[0]*A[1]%Q)
    #         return
    if negative <= 1:
        A.sort(reverse=True)
        ans = 1
        for a in A[:K]:
            ans *= a
            ans %= Q
        print(ans)
        return
    if K == negative + positive:
        if negative%2 == 1:
            if zero > 0:
                print(0)
                return
        ans = 1
        for a in A:
            if a != 0:
                ans *= a
                ans %= Q
        print(ans)
        return
            
    B = [(abs(a), a) for a in A]
    B.sort(reverse = True)
    minus = False
    minus_value = 0
    plus_value = 0
    ans = 1
    for b in B[:K]:
        ans *= b[0]
        ans %= Q
        if b[1] < 0:
            minus = not minus
            minus_value = b[0]
        elif b[1] > 0:
            plus_value = b[0]
    if minus:
        ans_plus = ans_minus = ans
        plus_replaced_value = 0
        minus_replaced_value = 0
        if minus_value > 0:
            for b in B[K:]:
                if b[1] > 0:
                    ans_plus = ans*pow(minus_value,Q-2,Q)%Q*b[0]%Q
                    plus_replaced_value = plus_value*b[0]
                    break
        if plus_value > 0:
            for b in B[K:]:
                if b[1] < 0:
                    ans_minus = ans*pow(plus_value,Q-2,Q)%Q*b[0]%Q
                    minus_replaced_value = minus_value*b[0]
                    break
        if plus_replaced_value == 0 and minus_replaced_value == 0:
            pass
        elif plus_replaced_value < minus_replaced_value:
            ans = ans_minus
        else:
            ans = ans_plus
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    if K == 1:
        print(max(A))
        return
    positive = 0
    zero = 0
    negative = 0
    for a in A:
        if a > 0:
            positive += 1
        elif a == 0:
            zero += 1
        else:
            negative += 1
    if positive+negative < K:
        print(0)
        return
    if positive == 0:
        if K%2 == 1:
            if zero > 0:
                print(0)
                return
            else:
                A.sort(reverse=True)
                ans = 1
                for a in A[:K]:
                    ans *= a
                    ans %= Q
                print(ans)
                return
        else:
            A.sort()
            ans = 1
            for a in A[:K]:
                ans *= a
                ans %= Q
            print(ans)
            return
    # if K == 2:
    #     if negative <= 1:
    #         A.sort(reverse=True)
    #         print(A[0]*A[1]%Q)
    #         return
    if negative <= 1:
        A.sort(reverse=True)
        ans = 1
        for a in A[:K]:
            ans *= a
            ans %= Q
        print(ans)
        return
    if K == negative + positive:
        if negative%2 == 1:
            if zero > 0:
                print(0)
                return
        ans = 1
        for a in A:
            if a != 0:
                ans *= a
                ans %= Q
        print(ans)
        return
            
    B = [(abs(a), a) for a in A]
    B.sort(reverse = True)
    minus = False
    minus_value = 0
    plus_value = 0
    ans = 1
    for b in B[:K]:
        ans *= b[0]
        ans %= Q
        if b[1] < 0:
            minus = not minus
            minus_value = b[0]
        elif b[1] > 0:
            plus_value = b[0]
    if minus:
        ans_plus = ans_minus = ans
        plus_replaced_value = 0
        minus_replaced_value = 0
        for b in B[K:]:
            if b[1] > 0:
                ans_plus = ans*pow(minus_value,Q-2,Q)%Q*b[0]%Q
                plus_replaced_value = plus_value*b[0]
                break
        for b in B[K:]:
            if b[1] < 0:
                ans_minus = ans*pow(plus_value,Q-2,Q)%Q*b[0]%Q
                minus_replaced_value = minus_value*b[0]
                break
        if plus_replaced_value < minus_replaced_value:
            ans = ans_minus
        else:
            ans = ans_plus
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    if K == 1:
        print(max(A))
        return
    positive = 0
    zero = 0
    negative = 0
    for a in A:
        if a > 0:
            positive += 1
        elif a == 0:
            zero += 1
        else:
            negative += 1
    if positive+negative < K:
        print(0)
        return
    if positive == 0:
        if K%2 == 1:
            if zero > 0:
                print(0)
                return
            else:
                A.sort(reverse=True)
                ans = 1
                for a in A[:K]:
                    ans *= a
                    ans %= Q
                print(ans)
                return
        else:
            A.sort()
            ans = 1
            for a in A[:K]:
                ans *= a
                ans %= Q
            print(ans)
            return
    # if K == 2:
    #     if negative <= 1:
    #         A.sort(reverse=True)
    #         print(A[0]*A[1]%Q)
    #         return
    if negative <= 1:
        A.sort(reverse=True)
        print(A[0]*A[1]%Q)
        return
    if K == negative + positive:
        if negative%2 == 1:
            if zero > 0:
                print(0)
                return
        ans = 1
        for a in A:
            if a != 0:
                ans *= a
                ans %= Q
        print(ans)
        return
            
    B = [(abs(a), a) for a in A]
    B.sort(reverse = True)
    minus = False
    minus_value = 0
    plus_value = 0
    ans = 1
    for b in B[:K]:
        ans *= b[0]
        ans %= Q
        if b[1] < 0:
            minus = not minus
            minus_value = b[0]
        elif b[1] > 0:
            plus_value = b[0]
    if minus:
        ans_plus = ans_minus = ans
        plus_replaced_value = 0
        minus_replaced_value = 0
        for b in B[K:]:
            if b[1] > 0:
                ans_plus = ans*pow(minus_value,Q-2,Q)%Q*b[0]%Q
                plus_replaced_value = plus_value*b[0]
                break
        for b in B[K:]:
            if b[1] < 0:
                ans_minus = ans*pow(plus_value,Q-2,Q)%Q*b[0]%Q
                minus_replaced_value = minus_value*b[0]
                break
        if plus_replaced_value < minus_replaced_value:
            ans = ans_minus
        else:
            ans = ans_plus
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    if K == 1:
        print(max(A))
        return
    positive = 0
    zero = 0
    negative = 0
    for a in A:
        if a > 0:
            positive += 1
        elif a == 0:
            zero += 1
        else:
            negative += 1
    if N - zero < K:
        print(0)
        return
    if positive == 0:
        if K%2 == 1:
            if zero > 0:
                print(0)
                return
            else:
                A.sort(reverse=True)
                ans = 1
                for a in A[:K]:
                    ans *= a
                    ans %= Q
                print(ans)
                return
        else:
            A.sort()
            ans = 1
            for a in A[:K]:
                ans *= a
                ans %= Q
            print(ans)
            return
    if K == 2:
        if negative <= 1:
            A.sort(reverse=True)
            print(A[0]*A[1]%Q)
            return
    if K == negative + positive:
        if negative%2 == 1:
            if zero > 0:
                print(0)
                return
        ans = 1
        for a in A:
            if a != 0:
                ans *= a
                ans %= Q
        print(ans)
        return
            
    B = [(abs(a), a) for a in A]
    B.sort(reverse = True)
    minus = False
    minus_value = 0
    plus_value = 0
    ans = 1
    for b in B[:K]:
        ans *= b[0]
        ans %= Q
        if b[1] < 0:
            minus = not minus
            minus_value = b[0]
        elif b[1] > 0:
            plus_value = b[0]
    if minus:
        ans_plus = ans_minus = ans
        plus_replaced_value = 0
        minus_replaced_value = 0
        for b in B[K:]:
            if b[1] > 0:
                ans_plus = ans*pow(minus_value,Q-2,Q)%Q*b[0]%Q
                plus_replaced_value = plus_value*b[0]
                break
        for b in B[K:]:
            if b[1] < 0:
                ans_minus = ans*pow(plus_value,Q-2,Q)%Q*b[0]%Q
                minus_replaced_value = minus_value*b[0]
                break
        if plus_replaced_value < minus_replaced_value:
            ans = ans_minus
        else:
            ans = ans_plus
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    if K == 1:
        print(max(A))
        return
    exist_plus = False
    zero = 0
    for a in A:
        if a > 0:
            exist_plus = True
        elif a == 0:
            zero += 1
    if N - zero < K:
        print(0)
        return
    if not exist_plus:
        A.sort(reverse=True)
        ans = 1
        for a in A[:K]:
            ans *= a
            ans %= Q
        print(ans)
        return
    B = [(abs(a), a) for a in A]
    B.sort(reverse = True)
    minus = False
    minus_value = 0
    ans = 1
    for b in B[:K]:
        ans *= b[0]
        ans %= Q
        if b[1] < 0:
            minus = not minus
            minus_value = b[0]
    if minus:
        ans *= pow(minus_value, Q-2, Q)
        ans %= Q
        for b in B[K:]:
            if b[1] > 0:
                ans *= b[1]
                ans %= Q
                break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import sys
from functools import reduce
from operator import mul
input = lambda: sys.stdin.readline().strip()
n, k = [int(x) for x in input().split()]
a = sorted((int(x) for x in input().split()), key=abs)
sgn = [0 if x == 0 else x // abs(x) for x in a]
M = 10**9 + 7
def modmul(x, y):
    return x * y % M
if reduce(mul, sgn[-k:]) >= 0:
    print(reduce(modmul, a[-k:], 1))
elif any(x > 0 for x in a[:n-k]):
    rem = next(i for i, x in enumerate(a[-k:]) if x < 0)
    print(next(x for x in reversed(a[:n-k]) if x > 0) * reduce(modmul, (x for i, x in enumerate(a[-k:]) if i != rem), 1) % M)
else:
    print(reduce(modmul, a[:k], 1))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import sys
from functools import reduce
from operator import mul
input = lambda: sys.stdin.readline().strip()
n, k = [int(x) for x in input().split()]
a = sorted((int(x) for x in input().split()), key=abs)
M = 10**9 + 7
if reduce(mul, a[-k:]) >= 0:
    print(reduce(mul, a[-k:]) % M)
elif any(x > 0 for x in a[:n-k]):
    print(next(x for x in a[:n-k] if x > 0) * reduce(mul, a[-k:]) // next(x for x in a[-k:] if x < 0) % M)
else:
    print(reduce(mul, a[:k]) % M)

Submission status: Wrong Answer

Solution code:
mod = (10**9)+7

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


arr=sorted(list(map(int,input().split())))

ans = 1

while k > 1:
    if arr[0]*arr[1] > arr[-1] and arr[-1] > 0:
        ans *= arr[0]*arr[1]
        arr.pop(1)
        arr.pop(0)
        k -= 2
    else:
        ans *= arr[-1]
        arr.pop(-1)
        k -= 1
if k == 0:
    print(ans%mod)
else: 
    print((ans*max(arr))%mod)

Submission status: Wrong Answer

Solution code:
import functools 
mod = (10**9)+7

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

arr=sorted(list(map(int,input().split())))
darr = arr.copy()
ans = 1

while k > 1:
    if arr[0]*arr[1] > arr[-1]:
        ans *= arr[0]*arr[1]
        arr.pop(1)
        arr.pop(0)
        k -= 2
    else:
        ans *= arr[-1]
        arr.pop(-1)
        k -= 1
if k == 0:
    print(ans%mod)
else:
    fin = ans*max(arr)
    if fin > 0:
        print(fin%mod)
    else:
        fina = functools.reduce(lambda a,b : a*b,darr[-s:])
        print(fina%mod)

Submission status: Wrong Answer

Solution code:
MOD = 1e9 + 7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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

plist = []
mlist = []
znum = 0
for a in alist:
    if a < 0:
        mlist.append(-a)
    elif a > 0:
        plist.append(a)
    else:
        znum += 1
plist.sort(reverse=True)
mlist.sort(reverse=True)
rem = 1

# 例外処理1 N=Kのとき
if (n == k):
    for a in alist:
        rem = rem * a % MOD
    print(int(rem))
    exit()

# 例外処理2 正の数が存在しないかつk:奇数のとき
if (len(plist) == 0 and k % 2 == 1):
    for m in mlist[-k:]:
        rem = rem * m % MOD
    if znum == 0:
        rem = (MOD - rem) % MOD
    else:
        rem = 0
    print(int(rem))
    exit()

# 例外処理3 絶対に0が入ってしまうとき
if (len(mlist) + len(plist) < k):
    print(0)
    exit()

i = max(0, ((k - len(plist) + 1) // 2))  # 2*iは使用する負の数の個数
for p in plist[:(k - 2 * i)]:
    rem = rem * p % MOD
for m in mlist[:(2 * i)]:
    rem = rem * m % MOD
while 2 * i + 2 <= len(mlist) and k - (2 * i + 2) >= 0:
    # print(i, rem)
    if mlist[(2 * i)] * mlist[(2 * i) + 1] < plist[k - 2 * i - 1] * plist[k - 2 * i - 2]:
        break
    rem = rem * mlist[(2 * i)] % MOD * mlist[(2 * i) + 1] % MOD * \
        modinv(plist[k - 2 * i - 1], MOD) % MOD * \
        modinv(plist[k - 2 * i - 2], MOD) % MOD
    i += 1

print(int(rem))