Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

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

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

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

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

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

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

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

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

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

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

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

Sample Input 4

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

Sample Output 4

999983200

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



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1


for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2


if pn == 0:
    if K == N and 0 in A:
        print(0)
        sys.exit()
    for i in range(K):
        prod = prod * A[i][0] % MOD
    print(prod)
    sys.exit()

elif pn == 1:
    if K == N:
        if 0 in A:
            print(0)
            sys.exit(0)
        for i in range(N):
            prod = prod * A[i][0] % MOD
            prod = prod * (-1) % MOD
        print(prod)
        sys.exit()
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp == N:
        if K % 2 == 0:
            for i in range(K):
                prod = prod * A[i][0] % MOD
        elif K % 2 == 1:
            for i in range(K):
                B = list(reversed(A))
                prod = prod * B[i][0] % MOD
                prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[indn][0] % MOD
            else:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
        prod = max(prod1,prod2)
    print(prod)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())

        if (len(ans_neg) & 1) and ((not ans_pos) or (ans_pos[-1] != 0)):
            s1 = s2 = -1
            if pos and ans_neg:
                s1 = -pos[-1] / ans_neg[-1]
            if neg and ans_pos:
                s2 = -neg[-1] / ans_pos[-1]

            if s1 > s2:
                ans_pos.append(pos.pop())
                ans_neg.pop()
            else:
                ans_neg.append(neg.pop())
                ans_pos.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1


for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2


if pn == 0:
    for i in range(K):
        prod = prod * A[i][0] % MOD
    print(prod)
    sys.exit()

elif pn == 1:
    if K == N:
        for i in range(N):
            prod = prod * A[i][0] % MOD
            prod = prod * (-1) % MOD
        print(prod)
        sys.exit()
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp == N:
        if K % 2 == 0:
            for i in range(K):
                prod = prod * A[i][0] % MOD
        elif K % 2 == 1:
            if 0 in A:
                print(0)
                sys.exit()
            for i in range(K):
                B = list(reversed(A))
                prod = prod * B[i][0] % MOD
                prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[indn][0] % MOD
            else:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
        prod = max(prod1,prod2)
    print(prod)

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1


for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2


if pn == 0:
    for i in range(K):
        prod = prod * A[i][0] % MOD
    print(prod)
    sys.exit()

elif pn == 1:
    if K == N:
        for i in range(N):
            prod = prod * A[i][0] % MOD
            prod = prod * (-1) % MOD
        print(prod)
        sys.exit()
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp >= N:
        if K % 2 == 0:
            for i in range(K):
                prod = prod * A[i][0] % MOD
        elif K % 2 == 1:
            for i in range(K):
                B = list(reversed(A))
                prod = prod * B[i][0] % MOD
                prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[indn][0] % MOD
            else:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
        prod = max(prod1,prod2)
    print(prod)

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1


for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2


if pn == 0:
    for i in range(K):
        prod = prod * A[i][0] % MOD
        print(prod)
        sys.exit()

elif pn == 1:
    if K == N:
        for i in range(N):
            prod = prod * A[i][0] % MOD
            prod = prod * (-1) % MOD
            print(prod)
            sys.exit()
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp >= N:
        if K % 2 == 0:
            for i in range(K):
                prod = prod * A[i][0] % MOD
        elif K % 2 == 1:
            for i in range(K):
                B = list(reversed(A))
                prod = prod * B[i][0] % MOD
                prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[indn][0] % MOD
            else:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
        prod = max(prod1,prod2)
print(prod)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

    pos.sort()
    neg.sort(reverse=True)

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())
                
        if len(ans_neg) & 1 and (ans_pos and ans_pos[-1] != 0):
            s1 = s2 = 0
            if pos and ans_neg:
                s1 = -pos[-1] / ans_neg[-1]
            if neg and ans_pos:
                s2 = -neg[-1] / ans_pos[-1]

            if s1 > s2:
                ans_pos.append(pos.pop())
                ans_neg.pop()
            else:
                ans_neg.append(neg.pop())
                ans_pos.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1
if K == N:
    for i in range(N):
        prod = prod * A[i][0] % MOD
        print(prod)
        sys.exit()

for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2

if pn == 0:
    for i in range(K):
        prod = prod * A[i][0] % MOD
        print(prod)
        sys.exit()

elif pn == 1:
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp >= N:
        if K % 2 == 0:
            for i in range(K):
                prod = prod * A[i][0] % MOD
        elif K % 2 == 1:
            for i in range(K):
                B = list(reversed(A))
                prod = prod * B[i][0] % MOD
                prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        prod1 = 1
        prod2 = 1
        for i in range(K):
            if i == lastn:
                prod1 = prod1 * A[indp][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
            elif i == lastp:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[indn][0] % MOD
            else:
                prod1 = prod1 * A[i][0] % MOD
                prod2 = prod2 * A[i][0] % MOD
        prod = max(prod1,prod2)
print(prod)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, K = inm()
A = inl()
B = [(abs(a), a < 0) for a in A]
B.sort(reverse=True)

MOD = 10 ** 9 + 7


def solve():
    fs = []
    negmin = posrep = None
    posmin = negrep = None
    negcnt = 0
    for i in range(N):
        v, neg = B[i]
        if len(fs) < K:
            fs.append(v)
            if neg:
                negcnt += 1
                negmin = v
            else:
                posmin = v
        elif neg and negrep is None:
            negrep = v
        elif not neg and posrep is None:
            posrep = v
    if negcnt % 2 == 0:
        a0 = 1
        for x in fs:
            a0 = (a0 * x) % MOD
        return a0

    a1 = a2 = None
    if negmin is not None and posrep is not None:
        a1 = 1
        for x in fs:
            if x == negmin:
                a1 = (a1 * posrep) % MOD
            else:
                a1 = (a1 * x) % MOD
    if posmin is not None and negrep is not None:
        a2 = 1
        for x in fs:
            if x == posmin:
                a2 = (a2 * negrep) % MOD
            else:
                a2 = (a2 * x) % MOD

    if a1 is None and a2 is None:
        a3 = 1
        for (x, neg) in list(reversed(B))[:K]:
            if neg:
                a3 *= -x
            else:
                a3 *= x
            a3 %= MOD
        return a3

    assert a1 is not None or a2 is not None
    if a1 is None:
        return a2
    if a2 is None:
        return a1

    if posrep * posmin < negrep * negmin:
        return a2
    else:
        return a1


print(solve())

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, K = inm()
A = inl()
B = [(abs(a), a < 0) for a in A]
B.sort(reverse=True)

MOD = 10 ** 9 + 7


def solve():
    fs = []
    negmin = posrep = None
    posmin = negrep = None
    negcnt = 0
    for i in range(N):
        v, neg = B[i]
        if len(fs) < K:
            fs.append(v)
            if neg:
                negcnt += 1
                negmin = v
            else:
                posmin = v
        elif neg and negrep is None:
            negrep = v
        elif not neg and posrep is None:
            posrep = v
    if negcnt % 2 == 0:
        a0 = 1
        for x in fs:
            a0 = (a0 * x) % MOD
        return a0

    a1 = a2 = None
    if negmin is not None and posrep is not None:
        a1 = 1
        for x in fs:
            if x == negmin:
                a1 = (a1 * posrep) % MOD
            else:
                a1 = (a1 * x) % MOD
    if posmin is not None and negrep is not None:
        a2 = 1
        for x in fs:
            if x == posmin:
                a2 = (a2 * negrep) % MOD
            else:
                a2 = (a2 * x) % MOD

    if a1 is None and a2 is None:
        a3 = -1
        for (x, _) in list(reversed(B))[:K]:
            a3 = (a3 * x) % MOD
        return a3

    assert a1 is not None or a2 is not None
    if a1 is None:
        return a2
    if a2 is None:
        return a1

    if posrep * posmin < negrep * negmin:
        return a2
    else:
        return a1


print(solve())

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
MOD = 10**9 + 7
def resolve():
    c = sys.stdin.readlines()
    c = list(map(lambda x: x.strip(), c))
    N, K = tuple(map(int, c[0].split(' ')))
    p = list(map(int, c[1].split(' ')))
    p = sorted(p, key=lambda x: abs(x), reverse=True)
    prod = 1
    sign = 1
    for i in range(K-1):
        prod *= p[i]
        prod %= MOD
        sign *= np.sign(p[i])
    for i in range(N-K+1):
        if sign == np.sign(p[K+i-1]):
            prod *= p[K+i-1]
            sign *= -1
            break
        p = sorted(p, key=lambda x: abs(x))
        prod = 1
        for i in range(K):
            prod *= p[i]
            prod %= MOD

    prod %= MOD

    print(prod)
    
resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    A_neg = [a for a in A if a < 0]
    A_zero = [a for a in A if a == 0]
    A_pos = [a for a in A if a > 0]

    A_neg.sort(reverse=True)
    A_pos.sort()

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

    if K > len(A_neg) + len(A_pos):
        print(0)
        return
    elif len(A_pos) == 0:
        if len(A_zero) > 0:
            print(0)
            return
        elif K % 2:
            ans = 1
            for a in A_neg[:K]:
                ans = (ans * a) % MOD
            print(ans)
            return
        else:
            ans = 1
            for a in A_neg[-K:]:
                ans = (ans * a) % MOD
            print(ans)
            return

    tmp_pos = []
    tmp_neg = []

    ans = 1
    neg = 0
    for i in range(K):
        if not A_neg:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop() % MOD
        elif not A_pos:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop() % MOD
            neg = 1 - neg
        elif -A_neg[-1] > A_pos[-1]:
            tmp_neg.append(A_neg[-1])
            ans = ans * A_neg.pop() % MOD
            neg = 1 - neg
        else:
            tmp_pos.append(A_pos[-1])
            ans = ans * A_pos.pop() % MOD

    if neg:
        tmp1 = tmp2 = 0
        if A_pos and tmp_neg[-1]:
            tmp1 = A_pos[-1] / (-tmp_neg[-1])
            ans1 = ans * pow(tmp_neg[-1], MOD - 2, MOD) * A_pos.pop() % MOD
        if A_neg and tmp_pos:
            tmp2= A_neg[-1] / (-tmp_pos[-1])
            ans2 = ans * pow(tmp_pos[-1], MOD - 2, MOD) * A_neg.pop() % MOD
        
        if tmp1 > tmp2:
            ans = ans1
        else:
            ans = ans2

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

MOD = 10**9 + 7

def resolve():
    c = sys.stdin.readlines()
    c = list(map(lambda x: x.strip(), c))
    N, K = tuple(map(int, c[0].split(' ')))
    p = list(map(int, c[1].split(' ')))
    p = sorted(p, key=lambda x: abs(x), reverse=True)
    prod = 1
    sign = 1
    for i in range(K):
        prod *= p[i]
        prod %= MOD
        sign *= np.sign(p[i])
    for i in range(N-K):
        if sign != 1:
            if np.sign(p[K]) != np.sign(p[K+i]):
                prod = (prod // p[K]) * p[K+i]
                sign *= -1

    if sign != 1:
        p = sorted(p, key=lambda x: abs(x))
        prod = 1
        for i in range(K):
            prod *= p[i]
            prod %= MOD

    prod %= MOD

    print(prod)

resolve()

Submission status: Wrong Answer

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        return
    if n==k or k%2 and not x:
        c=1
        for i in sorted(y)[-k:]:
            c=c*i%M
        print(c)
        return
    x=sorted(x)[::-1][:k]
    i=len(x)
    y.sort()
    m=len(y)
    j=k-i
    if j%2:
        x=x[:-1]
        i-=1
        j+=1
    x+=y[:j]
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b=[]
for i in a:
    if i>0:
        m=1
    elif i==0:
        m=0
    else:
        m=-1
    b.append([abs(i),m])

b.sort(key=lambda x: x[0], reverse=True)

mod=10**9+7
ans=1
judge=1
seisaisyou=0
seisaidai=0
husaisyou=0
husaidai=0

for i in range(k):
    ans*=b[i][0]%mod
    judge*=b[i][1]
if judge>0:
    print(ans)
if judge<=0:
    
    for j in range(k-1,-1,-1):
        if b[i][1]==1:
            ss=b[i][0]#正の最小
            seisaisyou=1
            break
            
    for j in range(k-1,-1,-1):
        if b[i][1]==-1:
            hs=b[i][0]#負の最小
            husaisyou=1
            break
        
    
    #正の最小と　範囲外の負の最大を交換する
    for j in range(k,n):
        if b[i][1]==-1:
            h=b[i][0]#負の最大
            husaidai=1
            break
    
    #負の最小と　範囲外の正の最大を交換する
    for j in range(k,n):
        if b[i][1]==1:
            s=b[i][0]#正の最大
            seisaidai=1
            break
    
    if husaidai==1and seisaisyou==1:
        pre1=ans*h/ss
    if seisaidai==1and husaisyou==1:
        pre2=ans*s/hs
    if (husaidai==1and seisaisyou==1)or (seisaidai==1and husaisyou==1):
        ans=max(pre1,pre2)
        print(ans%mod)
    else:
        ans=1
        for i in range(n-1,n-k-1,-1):
            ans*=b[i][0]%mod
        print(mod-1*ans)

Submission status: Wrong Answer

Solution code:
import copy

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

mod = 10**9 + 7

Am, Ap = [], []
pm = [0, 0]
B = []

def ans(A):
  ans = 1
  for x in A:
    ans *= x
    ans %= mod
  return ans

if N == K:
  print(ans(A))
  exit()

for x in A:
  if x < 0:
    Am.append(-x)
    B.append((-x, 1))
    pm[0] += 1
  else:
    Ap.append(x)
    B.append((x, 0))
    pm[1] += 1

Am.sort()

if pm[0] == N:
  if K%2 == 0:
    print(ans(Am[N-K:]))
  else:
    print((-1 * ans(Am[:K]))%mod)
  exit()

P = []
B.sort(reverse = True)

cnt = 0

p_min = (-1, -1)
m_min = (-1, -1)

for i in range(K):
  P.append(B[i][0])
  cnt ^= B[i][1]
  if B[i][1] == 0:
    p_min = (B[i][0], i)
  else:
    m_min = (B[i][0], i)

if cnt == 0:
  print(ans(P))
  exit()

P1 = copy.deepcopy(P)
P2 = copy.deepcopy(P)

p_max = (-1, -1)
m_max = (-1, -1)

for i in range(K, N):
  if B[i][1] == 0:
    p_max = (B[i][0], i)
    break

for i in range(K, N):
  if B[i][1] == 1:
    m_max = (B[i][0], i)
    break

Flag1 = False
Flag2 = False

if p_min != -1 and m_max[1] != -1:
  Flag1 = True
  P1[p_min[1]] = 1
  P1.append(m_max[0])
  ans1 = ans(P1)

if m_min != -1 and p_max[1] != -1:
  Flag2 = True
  P2[m_min[1]] = 1
  P2.append(p_max[0])
  ans2 = ans(P2)

if Flag1 and Flag2:
  if m_min[0]*m_max[0] > p_min[0]*p_max[0]:
    print(ans1)
  else:
    print(ans2)
elif Flag1:
  print(ans1)
else:
  print(ans2)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=sorted(list(map(int,input().split())))
MOD=1000000007

def maxProductSubarrayOfSizeK(A, n, k):
    t=1
    #case 1: when the max.element is 0 and k is odd
    if(max(l)==0 and k%2!=0):
        return 0
    #case 2:when the max.element is less than 0 and k is again odd
    if(l[n-1]<=0 and k%2!=0):
        for i in range(n-1,n-k+1,-1):
            t=t*l[i]
            t=t%MOD
        return t%MOD
    s=k//2
    i=0
    j=n-1
    #case3: when the max.element is greater than 0 and k is odd
    if(l[n-1]>0 and k%2!=0):
          y=l[n-1]
          j=j-1
          s=s-1
    
    #case 4 when k is even
    for i in range(s):
        lp=l[i]*l[i+1]
        rp=l[j]*l[j-1]
        if(lp>rp):
            t=t*lp
            i=i+2   
            t%=MOD
        else:
            t=t*lp
            j=j-2
            t%=MOD
    return t%MOD
print(maxProductSubarrayOfSizeK(l,n,k))

Submission status: Wrong Answer

Solution code:
from sys import exit
# import copy
# import numpy as np
# from collections import deque
import random


def mymod(n):
    if abs(n) > 1e9+7:
        if n > 0:
            return n % (1e9+7)
        else:
            return n % (1e9+7) - (1e9+7)
    else:
        return n


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

#A = [random.randrange(1, 100)*1e4*(-1)**random.randrange(0, 2) for _ in range(N)]

A = sorted(A, key=abs)

#print(A)

A.extend([float("inf"), 0])

ans = 1
if N == K:
    for n in A[:-2]:
        ans *= n
        ans = mymod(ans)
    ans %= 1e9+7
    print(int(ans))
    exit()
elif K % 2 == 1 and max(A[:-2]) < 0:
    for i in range(K):
        ans *= A[i]
        ans = mymod(ans)
    ans %= 1e9+7
    print(int(ans))
    exit()
else:
    min_minu = -2
    min_plus = -2
    for i in range(N-K, N):
        ans *= A[i]
        ans = mymod(ans)
        if min_minu == -2 and A[i] < 0:
            min_minu = i
        if min_plus == -2 and A[i] > 0:
            min_plus = i

    if ans >= 0:
        print(int(ans))
        exit()
    else:
        max_minu = -1
        max_plus = -1
        for i in range(N-K-1, -1, -1):
            if max_minu == -1 and A[i] < 0:
                max_minu = i
            if max_plus == -1 and A[i] > 0:
                max_plus = i
            if max_minu != -1 and max_plus != -1:
                break

        if abs(A[max_minu] / A[min_plus]) >= abs(A[max_plus] / A[min_minu]):
            ans = 1
            A[min_plus] = A[max_minu]
            for i in range(N-K, N):
                ans *= A[i]
                ans = mymod(ans)
            ans %= 1e9+7
            print(int(ans))
            exit()
        else:
            ans = 1
            A[min_minu] = A[max_plus]
            for i in range(N-K, N):
                ans *= A[i]
                ans = mymod(ans)
            ans %= 1e9+7
            print(int(ans))
            exit()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = list(sorted([i for i in a if i < 0]))
    ap = list(sorted([i for i in a if i > 0], reverse = True))
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    old_p = 0
    if k == 1:
        print(max(a)%mod)
        return
    if k == n:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        if old_p*next_p > old_n*next_n or next_n == 0:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()