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:
#!/usr/bin/env python3
import sys
import heapq

MOD = 1000000007  # type: int

def containPositive(arr):
    for a in arr:
        if a >= 0:
            return True
    return False

def solve(N: int, K: int, A: "List[int]"):
    if N == K:
        m = 1
        for a in A:
            m = m*a%MOD
        print(m)
    elif not containPositive(A):
        A = list(reversed(sorted(A))) if K%2 == 1 else list(sorted(A))
        m = 1
        for i in range(K):
            m = m*A[i]%MOD
        print(m)
    else:
        m = 1
        B = [(abs(a),a) for a in A]
        B = list(reversed(sorted(B)))
        lastNegative = 0
        lastPositive = 1
        hadPositive = False
        for i in range(K):
            a = B[i][1]
            if a < 0:
                if lastNegative == 0:
                    lastNegative = a
                else:
                    m = m*lastNegative*a%MOD
                    lastNegative = 0
            else:
                if a > 0 and lastPositive != 1:
                    m = m*lastPositive%MOD
                if a > 0:
                    lastPositive = a
                    hadPositive = True
                else:
                    m=m*a%MOD
        if lastNegative == 0:
            print(m*lastPositive%MOD)
        else:
            nextNegative = 0
            for i in range(K,N):
                b = B[i][1]
                if b < 0:
                    nextNegative = b
                    break
            if nextNegative == 0:
                m = m*B[K][1]
                print(m*lastPositive%MOD)
            else:
                c1 = lastNegative*nextNegative
                nextPositive = 0
                k = K
                while k < N:
                    a = B[k][1]
                    if a >=0:
                        nextPositive = a
                    k+=1
                c2 = nextPositive*lastPositive
                if c1 > c2 and hadPositive:
                    m = m*lastNegative*nextNegative%MOD
                    # print("here")
                    # print(hadPositive)
                    # print(lastNegative,nextNegative)
                    # print(lastPositive,nextPositive)
                    print(m)
                else:
                    m =m*nextPositive*lastPositive%MOD
                    print(m)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
BC = []
for a in A:
    if a >= 0:
        B.append(a)
        BC.append([a,0])
    else:
        C.append(-a)
        BC.append([-a,1])
BC = sorted(BC,reverse = True)
BC = sum(BC[:K],[])

neg_cnt = sum(BC[1::2])
non_neg_cnt = K - neg_cnt
ans = 1
if neg_cnt % 2 == 1 and len(B) == 0:
    C = sorted(C)
    for i in range(K):
        ans *= C[i]
        ans %= MOD
    ans *= -1
    ans %= MOD
    print(ans)
    sys.exit()
    
for i in range(K):
    ans *= BC[2*i]
    ans %= MOD
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)

if neg_cnt % 2 == 1:
    if neg_cnt == len(C) and non_neg_cnt == len(B):
        pass
    elif neg_cnt == len(C):      
        b,c = C[neg_cnt-1],B[non_neg_cnt]
        ans = ans // b * c % MOD
    elif non_neg_cnt == len(B):
        a,d = C[neg_cnt],B[non_neg_cnt-1]
        ans = ans // d * a % MOD
    else:
        a,b,c,d = C[neg_cnt],C[neg_cnt-1],B[non_neg_cnt],B[non_neg_cnt-1]
        if a*b > c*d:
            ans = ans // d * a % MOD
        else:
            ans = ans // b * c % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
n, k = map(int, input().split())
A = [*map(int, input().split())]
B = []
for a in A: B.append((abs(a), ([0,1][a<0])))

B.sort(reverse=True)
val = [1]*(n+1)
sign = [0]*(n+1)
for i in range(n): val[i+1] = B[i][0]
for i in range(n): sign[i+1] = sign[i] + B[i][1]
mx_pr = [-1, -1]
for s in range(n-k+1):
    e = s+k
    if (sign[e]-sign[s])%2 == 0:
        ans = 1
        for v in val[:e+1]: ans *= v; ans %= mod
        print((ans+mod) % mod)
        exit()

c = 0
ans = 1
for i in range(n):
    if B[i][1] == 0:
        ans *= B[i][1]
        c += 1
        if c == k:
            print((ans+mod) % mod)
            exit()

B.sort()
val = [1]*(n+1)
sign = [0]*(n+1)
for i in range(n): val[i+1] = B[i][0]
for i in range(n): sign[i+1] = sign[i] + B[i][1]
mx_pr = [-1, -1]
for s in range(n-k+1):
    e = s+k
    if (sign[e]-sign[s])%2 == 1:
        ans = -1
        for v in val[:e+1]: ans *= v; ans %= mod
        print((ans+mod) % mod)
        exit()

c = 0
ans = -1
for i in range(n):
    if B[i][1] == 1:
        c += 1
        ans *= B[i][1]
        if c == k:
            print((ans+mod) % mod)
            exit()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    mod = 10**9 + 7
    p = 1
    if n == k:
        for ai in a:
            p = p * ai % mod
        print(p)
        return
    if a[0] < 0 and k % 2:
        for ai in a[:k]:
            p = p * ai % mod
        print(p)
        return
    b = sorted([(abs(ai), ai) for ai in a], reverse=True)
    s = 0
    for ba, bb in b[:k]:
        p = p * ba % mod
        if bb < 0:
            s += 1
    if s % 2 == 0:
        print(p)
        return
    pa, na, pb, nb = [-1] * 4
    for ba, bb in b[:k]:
        if bb < 0:
            na = ba
        else:
            pa = ba
    for ba, bb in b[k:]:
        if nb == -1 and bb < 0:
            nb = ba
        elif pb == -1:
            pb = ba
        else:
            break
    if pa == -1 or nb == -1:
        print(p * pb * pow(na, mod - 2, mod) % mod)
    elif pb == -1 or na == -1:
        print(p * nb * pow(pa, mod - 2, mod) % mod)
    elif pa * pb > na * nb:
        print(p * pb * pow(na, mod - 2, mod) % mod)
    else:
        print(p * nb * pow(pa, mod - 2, mod) % mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    mod = 10**9 + 7
    p = 1
    if n == k:
        for ai in a:
            p = p * ai % mod
        print(p)
        return
    if a[0] < 0 and k % 2:
        for ai in a[:k]:
            p = p * ai % mod
        print(p)
        return
    b = sorted([(abs(ai), ai) for ai in a], reverse=True)
    s = 0
    for ba, bb in b[:k]:
        p = p * ba % mod
        if bb < 0:
            s += 1
    if s % 2 == 0:
        print(p)
        return
    pa, na, pb, nb = [-1] * 4
    for ba, bb in b[:k]:
        if bb < 0:
            na = ba
        else:
            pa = ba
    for ba, bb in b[k:]:
        if nb == -1 and bb < 0:
            nb = ba
        elif pb == -1:
            pb = ba
        else:
            break
    if pa == -1 or nb == -1:
        print(p * pb * pow(na, mod - 2, mod) % mod)
    elif pb == -1 or na == -1:
        print(p * nb * pow(pa, mod - 2, mod) % mod)
    elif pb * pb > na * nb:
        print(p * pb * pow(na, mod - 2, mod) % mod)
    else:
        print(p * nb * pow(pa, mod - 2, mod) % mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
n, k = map(int, input().split())
A = [*map(int, input().split())]
B = []
for a in A: B.append((abs(a), ([0,1][a<0])))

B.sort(reverse=True)
val = [1]*(n+1)
sign = [0]*(n+1)
for i in range(n): val[i+1] = B[i][0]
for i in range(n): sign[i+1] = sign[i] + B[i][1]
mx_pr = [-1, -1]
for s in range(n-k+1):
    e = s+k
    if (sign[e]-sign[s])%2 == 0:
        ans = 1
        for v in val[:e+1]: ans *= v; ans %= mod
        print((ans+mod) % mod)
        exit()

c = 0
ans = 1
for i in range(n):
    if B[i][1] == 0:
        c += 1
        ans *= B[i][1]
if c == k:
    print((ans+mod) % mod)
    exit()

B.sort()
val = [1]*(n+1)
sign = [0]*(n+1)
for i in range(n): val[i+1] = B[i][0]
for i in range(n): sign[i+1] = sign[i] + B[i][1]
mx_pr = [-1, -1]
for s in range(n-k+1):
    e = s+k
    if (sign[e]-sign[s])%2 == 1:
        ans = -1
        for v in val[:e+1]: ans *= v; ans %= mod
        print((ans+mod) % mod)
        exit()

c = 0
ans = -1
for i in range(n):
    if B[i][1] == 1:
        c += 1
        ans *= B[i][1]
if c == k:
    print((ans+mod) % mod)
    exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq

MOD = 1000000007  # type: int

def containPositive(arr):
    for a in arr:
        if a >= 0:
            return True
    return False

def solve(N: int, K: int, A: "List[int]"):
    if N == K:
        m = 1
        for a in A:
            m = m*a%MOD
        print(m)
    elif not containPositive(A):
        A = list(reversed(sorted(A))) if K%2 == 1 else list(sorted(A))
        m = 1
        for i in range(K):
            m = m*A[i]%MOD
        print(m)
    else:
        m = 1
        B = [(abs(a),a) for a in A]
        B = list(reversed(sorted(B)))
        lastNegative = 0
        lastPositive = 1
        for i in range(K):
            a = B[i][1]
            if a < 0:
                if lastNegative == 0:
                    lastNegative = a
                else:
                    m = m*lastNegative*a%MOD
                    lastNegative = 0
            else:
                if a > 0 and lastPositive != 1:
                    m = m*lastPositive%MOD
                if a > 0:
                    lastPositive = a
                else:
                    m=m*a%MOD
        if lastNegative == 0:
            print(m*lastPositive%MOD)
        else:
            nextNegative = 0
            for i in range(K,N):
                b = B[i][1]
                if b < 0:
                    nextNegative = b
                    break
            if nextNegative == 0:
                m = m*B[K][1]
                print(m*lastPositive%MOD)
            else:
                c1 = lastNegative*nextNegative
                nextPositive = 0
                k = K
                while k < N:
                    a = B[k][1]
                    if a >=0:
                        nextPositive = a
                    k+=1
                c2 = nextPositive*lastPositive
                if c1 > c2:
                    m = m*lastNegative*nextNegative%MOD
                    print(m)
                else:
                    m =m*nextPositive*lastPositive%MOD
                    print(m)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 1
mod = 10**9 + 7
c = 0
z = 0
for i in a:
    if i < 0:
        c += 1
    elif i == 0:
        z += 1
if c == n and k & 1:
    a.reverse()
    for i in range(k):
        ans *= -a[i]
        ans %= mod
    print(-ans % mod)
elif c == n:
    for i in range(k):
        ans *= -a[i]
        ans %= mod
    print(ans)
elif k == n:
    for i in a:
        ans *= abs(i)
        ans %= mod
    print(((-1)**c * ans) % mod)
else:
    plus = [i for i in a if i > 0]
    minus = [i for i in a if i <= 0]
    plus.sort(reverse=1)
    minus.sort()
    x = len(plus)
    y = len(minus)
    plus += [0] * z
    p, m = 0, 0
    for i in range(k // 2):
        if x - 1 <= p:
            ans *= minus[m] * minus[m + 1]
            m += 2
        elif y - 1 <= m:
            ans *= plus[p] * plus[p + 1]
            p += 2
        else:
            if minus[m] * minus[m + 1] >= plus[p] * plus[p + 1]:
                ans *= minus[m] * minus[m + 1]
                m += 2
            else:
                ans *= plus[p] * plus[p + 1]
                p += 2
        ans %= mod
    if k & 1:
        if p < x:
            ans *= plus[p]
        else:
            ans *= minus[-1]
        ans %= mod

    print(ans % mod)

Submission status: Wrong Answer

Solution code:


"""解説:上のであってる　indexで管理するの危なそう　listで整理するか
コーナーケースをプログラムの頭で処理 早め早めに処理"""

from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

def main():
    N,K = inpl()
    Als = inpl()
    mils = []
    pls = []
    Als.sort(key=lambda x:abs(x), reverse=True)
    ans = 1
    if N==K:
        for a1 in Als:
            ans *= a1
        print((ans+mod)%mod)
        return

    for i in range(K):
        if Als[i] < 0:
            mils.append(Als[i])
        if Als[i] > 0:
            pls.append(Als[i])

    if len(mils)%2==0:
        for k in pls:
            ans = (ans * abs(k))%mod
        for kk in mils:
            ans = (ans * abs(kk))%mod
        print((ans+mod)%mod)
        return
    if len(pls)==0 and (K%2 != 0):
        Als = Als[::-1]
        for kon in Als[:K]:
            ans *= kon
        print((ans + mod)%mod)
        return
    bans = 1
    cans = 1
    for item in Als[K+1:]:
        if item > 0:
            for kb in pls:
                bans  = (bans * abs(kb))%mod
            for kkb in mils[:-1]:
                bans  = (bans * abs(kkb))%mod
            bans = (bans*abs(item))%mod
    for item2 in Als[K+1:]:
        if item2 < 0:
            for kc in pls[:-1]:
                cans  = (cans * abs(kc))%mod
            for kkc in mils:
                cans = (cans * abs(kkc))%mod
            cans = (cans * abs(item2))%mod
    if bans > cans:
        print((bans+mod)%mod)
    else:
        print((cans+mod)%mod)

main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
canZero = A.count(0) > 0
MOD = 10**9 + 7

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        K = 0
        break
    if K == 1:
        if ans < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        K = 0
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
    else:
        if len(N) == 1:
            n = N.pop()
            if ans < 0:
                ans *= n
                K -= 1
            continue
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue
        if len(P) == 1:
            p = P[-1]
            n = N[-1] * N[-2]
            if p > n:
                ans *= P.pop()
                K -= 1
            else:
                ans *= N.pop() * N.pop()
                K -= 2
        else:
            ans *= N.pop() * N.pop()
            K -= 2

print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
BC = []
for a in A:
    if a >= 0:
        B.append(a)
        BC.append([a,0])
    else:
        C.append(-a)
        BC.append([-a,1])
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)
BC = sorted(BC,reverse = True)
BC = sum(BC[:K],[])

neg_cnt = sum(BC[1::2])
non_neg_cnt = K - neg_cnt
ans = 1
for i in range(K):
        ans *= BC[2*i]
        ans %= MOD

if neg_cnt % 2 == 1:
    if non_neg_cnt == 0:
        C = sorted(C)
        tmp = 1
        for i in range(K):
            tmp *= C[i]
            tmp %= MOD
        tmp *= -1
        tmp %= MOD
        ans = tmp
    elif neg_cnt == len(C) and non_neg_cnt == len(B):
        pass
    elif neg_cnt == len(C):       
        b,c = C[neg_cnt-1],B[non_neg_cnt]
        ans = ans // b * c % MOD
    elif non_neg_cnt == len(B):
        a,d = C[neg_cnt],B[non_neg_cnt-1]
        ans = ans // d * a % MOD
    else:
        a,b,c,d = C[neg_cnt],C[neg_cnt-1],B[non_neg_cnt],B[non_neg_cnt-1]
        if a*b > c*d:
            ans = ans // d * a % MOD
        else:
            ans = ans // b * c % MOD
print(ans)

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
        sign = 1
        for (x, neg) in B[-K:]:
            a3 = (a3 * x) % MOD
            if neg:
                sign *= -1
        return (MOD + sign * a3) % MOD

    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 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
BC = []
for a in A:
    if a >= 0:
        B.append(a)
        BC.append([a,0])
    else:
        C.append(-a)
        BC.append([-a,1])
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)
BC = sorted(BC,reverse = True)
BC = sum(BC[:K],[])

neg_cnt = sum(BC[1::2])
non_neg_cnt = K - neg_cnt
ans = 1
for i in range(K):
        ans *= BC[2*i]
        ans %= MOD

if neg_cnt % 2 == 1:
    if non_neg_cnt == 0:
        C = sorted(C)
        tmp = 1
        for i in range(K):
            tmp *= C[i]
            tmp %= MOD
        tmp *= -1
        tmp %= MOD
        ans = tmp
    elif neg_cnt == len(C) and non_neg_cnt == len(B):
        pass
    elif neg_cnt == len(C):       
        b,c = C[neg_cnt-1],B[non_neg_cnt]
        ans = ans // b * c % MOD
    elif non_neg_cnt == len(B):
        a,d = C[neg_cnt],B[non_neg_cnt-1]
        ans = ans // d * a % MOD
    else:
        a,b,c,d = C[neg_cnt],C[neg_cnt-1],B[non_neg_cnt],B[non_neg_cnt-1]
        if a*b > c*d:
            ans = ans // d * a % MOD
        else:
            ans = ans // b * c % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
n, k = map(int, input().split())
A = [*map(int, input().split())]
B = []
for a in A: B.append((abs(a), ([0,1][a<0])))
B.sort(reverse=True)

# print(n,k)
# print(A)
# print(B)
# print('---')

val = [1]*(n+1)
sign = [0]*(n+1)
for i in range(n): val[i+1] = B[i][0]
for i in range(n): sign[i+1] = sign[i] + B[i][1]
# print(val)
# print(sign)
mx_pr = [-1, -1]
for s in range(n-k+1):
    e = s+k
    # print(s,e, sign[s],sign[e], sign[e]-sign[s])
    if (sign[e]-sign[s])%2 == 0:
        ans = 1
        for v in val[:e+1]: ans *= v; ans %= mod
        print((ans+mod) % mod)
        exit()

# print('===')
B.sort()
# print(B)

val = [1]*(n+1)
sign = [0]*(n+1)
for i in range(n): val[i+1] = B[i][0]
for i in range(n): sign[i+1] = sign[i] + B[i][1]
# print(val)
# print(sign)
mx_pr = [-1, -1]
for s in range(n-k+1):
    e = s+k
    # print(s,e, sign[s],sign[e], sign[e]-sign[s])
    if (sign[e]-sign[s])%2 == 1:
        ans = 1
        for v in val[:e+1]: ans *= v; ans %= mod
        ans *= -1; ans %= mod
        print((ans+mod) % mod)
        exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq

MOD = 1000000007  # type: int

def containPositive(arr):
    for a in arr:
        if a >= 0:
            return True
    return False

def solve(N: int, K: int, A: "List[int]"):
    if N == K:
        m = 1
        for a in A:
            m = m*a%MOD
        print(m)
    elif not containPositive(A):
        A = list(reversed(sorted(A))) if K%2 == 1 else list(sorted(A))
        m = 1
        for i in range(K):
            m = m*A[i]%MOD
        print(m)
    else:
        m = 1
        B = [(abs(a),a) for a in A]
        B = list(reversed(sorted(B)))
        lastNegative = 0
        for i in range(K):
            a = B[i][1]
            if a < 0:
                if lastNegative == 0:
                    lastNegative = a
                else:
                    m = m*lastNegative*a%MOD
                    lastNegative = 0
            else:
                m=m*a%MOD
        if lastNegative == 0:
            print(m)
        else:
            nextNegative = 0
            for i in range(K,N):
                b = B[i][1]
                if b < 0:
                    nextNegative = b
                    break
            if nextNegative == 0:
                m = m*B[K][1]
                print(m)
            else:
                c1 = lastNegative*nextNegative
                nextPositive = 0
                nextNextPositive = 0
                k = K
                while k < N:
                    a = B[k][1]
                    if a >=0:
                        nextPositive = a
                    k+=1
                while k < N:
                    a = B[k][1]
                    if a >=0:
                        nextNextPositive = a
                    k+=1
                c2 = nextPositive*nextNextPositive
                if c1 > c2:
                    m = m*lastNegative*nextNegative%MOD
                    print(m)
                else:
                    m =m*nextPositive*nextNextPositive%MOD
                    print(m)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq

MOD = 1000000007  # type: int

def containPositive(arr):
    for a in arr:
        if a >= 0:
            return True
    return False

def solve(N: int, K: int, A: "List[int]"):
    if N == K:
        m = 1
        for a in A:
            m = m*a%MOD
        print(m)
    elif not containPositive(A):
        A = list(reversed(sorted(A))) if K%2 == 1 else list(sorted(A))
        m = 1
        for i in range(K):
            m = m*A[i]%MOD
        print(m)
    else:
        m = 1
        B = [(abs(a),a) for a in A]
        B = list(reversed(sorted(B)))
        lastNegative = 0
        for i in range(K):
            a = B[i][1]
            if a < 0:
                if lastNegative == 0:
                    lastNegative = a
                else:
                    m = m*lastNegative*a%MOD
                    lastNegative = 0
            else:
                m=m*a%MOD
        if lastNegative == 0:
            print(m)
        else:
            nextNegative = 0
            for i in range(K,N):
                b = B[i][1]
                if b < 0:
                    nextNegative = b
                    break
            if nextNegative == 0:
                m = m*B[K][1]
                print(m)
            else:
                c1 = lastNegative*nextNegative
                nextPositive = 0
                nextNextPositive = 0
                k = K
                while k < N:
                    a = B[i][1]
                    if a >=0:
                        nextPositive = a
                    k+=1
                while k < N:
                    a = B[i][1]
                    if a >=0:
                        nextNextPositive = a
                    k+=1
                c2 = nextPositive*nextNextPositive
                if c1 > c2:
                    m = m*lastNegative*nextNegative%MOD
                    print(m)
                else:
                    m =m*nextPositive*nextNextPositive%MOD
                    print(m)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop


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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできるので、絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    # 候補テーブルを作成
    A1 = []  # 非負要素のリスト
    A2 = []  # 負要素を絶対値の大きい順に2つずつ掛けたリスト

    BIGINT = 10**9 + 1  # tmp 用
    tmp = BIGINT
    for a in A:
        if a >= 0:
            heappush(A1, -a)
        else:
            if tmp == BIGINT:
                tmp = a
            else:
                heappush(A2, -tmp*a)
                tmp = BIGINT

    # cost が K を上回らなように大きいものから埋めていく〜
    cost = 0
    ans = 1
    while cost < K:
        if (K - cost) >= 2:
            # このときは A2 からも入れてよし
            if A1 and A2:
                if -A1[0] >= -A2[0]:
                    cost += 1
                    ans *= -heappop(A1)
                else:
                    cost += 2
                    ans *= -heappop(A2)
            elif A1:
                cost += 1
                ans *= -heappop(A1)
            else:
                cost += 2
                ans *= -heappop(A2)
            ans %= MOD
        else:
            cost += 1
            ans *= -heappop(A1)
            ans %= MOD

    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop


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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
elif max(A) < 0 and K % 2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    # case3. それ以外は正にできるので、絶対値の降順にソートする
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    # 候補テーブルを作成
    A1 = []  # 非負要素のリスト
    A2 = []  # 負要素を絶対値の大きい順に2つずつ掛けたリスト

    tmp = 10**9 + 8
    for a in A:
        if a >= 0:
            heappush(A1, -a)
        else:
            if tmp != 10**9 + 8:
                heappush(A2, -tmp*a)
                tmp = 10**9 + 8
            else:
                tmp = a

    # cost が K を上回らなように大きいものから埋めていく〜
    cost = 0
    ans = 1
    while cost < K:
        if (K - cost) >= 2:
            # このときは A2 からも入れてよし
            if A1 and A2:
                if -A1[0] >= -A2[0]:
                    cost += 1
                    ans *= -heappop(A1)
                else:
                    cost += 2
                    ans *= -heappop(A2)
            elif A1:
                cost += 1
                ans *= -heappop(A1)
            else:
                cost += 2
                ans *= -heappop(A2)
            ans %= MOD
        else:
            cost += 1
            ans *= -heappop(A1)
            ans %= MOD

    print(ans)