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: Runtime Error

Solution code:
N,K = map(int,input().split())
la = list(map(int,input().split()))
la = sorted(la)
la = sorted(la,key=abs,reverse=True)
lg = la[:K]
lgp = []
lgm = []
lr = la[K:]
lrp = []
lrm = []
for a in lg:
    if a >= 0:
        lgp.append(a)
    else:
        lgm.append(a)
for a in lr:
    if a >= 0:
        lrp.append(a)
    else:
        lrm.append(a)
if len(lgm) % 2 == 1:
    if len(lrp) > 0 and len(lrm) > 0:
        if len(lgp) > 0 and len(lgm) > 0:
            if lgp[len(lgp) - 1] * lrp[0] > lgm[len(lgm) - 1] * lrm[0]:
                lg.pop(lg.index(lgm[len(lgm) - 1]))
                lg.append(lrp[0])
            else:
                lg.pop(lg.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
        else:
            if len(lgp) > 0:
                lg.pop(lg.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
            else:
                lg.pop(lg.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
    else:
        if len(lrm) > 0:
            if len(lgp) > 0:
                lg.pop(lg.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
            else:
                lg = la[N - K:]
ans = 1
for a in lg:
    ans *= a
    ans %= 10 ** 9 + 7
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus = []
minus = []
zero = -float('inf')
for element in a:
  if element >= 0:
    plus.append(element)
  else:
    minus.append(element)
plus.sort()
plus.reverse()
minus.sort()
answer = -float('inf')
if not plus and minus:
  answer = 1
  if k % 2 == 0:
    for i in range(k):
      answer *= minus[i]
  else:
    for i in range(k):
      answer *= minus[-i-1]
elif len(plus) > 0 and len(minus) == 0:
  answer = 1
  for i in range(k):
    answer *= plus[i]
else:
  for i in range(0, min(len(minus)+1, k+1), 2):
    product = 1
    for j in range(i):
      product *= minus[j]
    for j in range(k-i):
      product *= plus[j]
    answer = max(answer, product)
print(answer%(10**9+7))

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
la = list(map(int,input().split()))
la = sorted(la,key=abs,reverse=True)
lg = la[:K]
lgp = []
lgm = []
lr = la[K:]
lrp = []
lrm = []
for a in lg:
    if a >= 0:
        lgp.append(a)
    else:
        lgm.append(a)
for a in lr:
    if a >= 0:
        lrp.append(a)
    else:
        lrm.append(a)
if len(lgm) % 2 == 1:
    if len(lrp) > 0:
        lg.pop(l.index(lgm[len(lgm) - 1]))
        lg.append(lrp[0])
    else:
        if len(lrm) > 0:
            if len(lgp) > 0:
                lg.pop(lg.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
            else:
                lg = la[N - K:]
ans = 1
for a in lg:
    ans *= a
    ans %= 10 ** 9 + 7
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
la = list(map(int,input().split()))
la = sorted(la,key=abs,reverse=True)
lg = la[:K]
lgp = []
lgm = []
lr = la[K:]
lrp = []
lrm = []
for a in lg:
    if a >= 0:
        lgp.append(a)
    else:
        lgm.append(a)
for a in lr:
    if a >= 0:
        lrp.append(a)
    else:
        lrm.append(a)
if len(lgm) % 2 == 1:
    if len(lrp) > 0:
        lg.pop(l.index(lgm[len(lgm) - 1]))
        lg.append(lrp[0])
    else:
        if len(lrm) > 0:
            if len(lgp) > 0:
                lg.pop(l.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
            else:
                lg = la[N - K:]
ans = 1
for a in lg:
    ans *= a
    ans %= 10 ** 9 + 7
print(ans)

Submission status: Runtime Error

Solution code:
def lpop(ans,l):
    return((ans * l.pop(0)) % (10 ** 9 + 7))
N,K = map(int,input().split())
la = list(map(int,input().split()))
la = sorted(la,key=abs,reverse=True)
lg = la[:K]
lgp = []
lgm = []
lr = la[K:]
lrp = []
lrm = []
for a in lg:
    if a >= 0:
        lgp.append(a)
    else:
        lgm.append(a)
for a in lr:
    if a >= 0:
        lrp.append(a)
    else:
        lrm.append(a)
if len(lgm) % 2 == 1:
    if len(lrp) > 0:
        lg.pop(l.index(lgm[len(lgm) - 1]))
        lg.append(lrp[0])
    else:
        if len(lrm) > 0:
            if len(lgp) > 0:
                lg.pop(l.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
            else:
                lg = la[N - K:]
ans = 1
for a in lg:
    ans *= a
    ans %= 10 ** 9 + 7
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))
import numpy as np
aa = np.array(aa)

def mul(dd):
    mod = 10**9+7
    ret = 1
    for d in dd:
        ret = (ret*d)%mod
    return ret

def sol(aa, n, k):
    mod = 10**9+7
    aap = aa[aa>0]
    aam = aa[aa<0]
    if n == k:
        return mul(aa)
    if len(aap) + 2*(len(aam)//2) < k:
        return 0
    if len(aam) == n and k%2==1:
        aam.sort()
        aam = aam[::-1]
        return mul(aam[:k])

    aap.sort()
    aap = aap[::-1]
    aam.sort()

    ret=1
    if k%2 >0:
        k = k-1
        ret *= aap[0]
        aap = aap[1:]

    aap2 = [aap[2*i]*aap[2*i+1] for i in range(len(aap)//2)]
    aam2 = [aam[2*i]*aam[2*i+1] for i in range(len(aam)//2)]
    ip=0
    im=0
    for i in range(k//2):
        if ip < len(aap2) and aap2[ip] >= aam2[im]:
            ret = (ret * aap2[ip])%mod
            ip += 1
        else:
            ret = (ret * aam2[im])%mod
            im += 1
    return ret%mod

print(sol(aa, n, k))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
T = {"mi":0, "pu":0, "zero":0}
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

for i in range(N):
    if A[i] < 0:
        T["mi"] += 1
    elif A[i] == 0:
        T["zero"] += 1
    else:
        T["pu"] += 1
mod = 10**9+7
for i in range(N):
    if A[i] < 0:
        B.append([A[i]*(-1), 1])
    else:
        B.append([A[i], 0])
A.sort()
B.sort(reverse=True)

ans = 1
c = 0
for i in range(K):
    ans *= B[i][0]
    ans %= mod
    c += B[i][1]
if c % 2 == 0:
    print(ans)
elif K > T["pu"]+T["mi"]:
    print(0)
elif T["mi"] == 1 and K > T["pu"]:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    if T["zero"] != 0:
        ans = 0
    print(ans)
elif T["pu"] == 1 and K > T["mi"]:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    if T["zero"] != 0:
        ans = 0
    print(ans)
elif T["pu"] == 0:
    ans = 1
    A.reverse()
    for i in range(K):
        ans *= A[i]
        ans %= mod
    if T["zero"] != 0:
        ans = 0
    print(ans)
else:
    change1 = B[K-1][1]
    change2 = (change1 + 1)%2
    chindex1 = K-1
    chindex2 = -1
    for i in range(K-1, -1, -1):
        if B[i][1] == change2:
            chindex2 = i
            break
    afterindex1 = -1
    afterindex2 = -1
    for i in range(K, N):
        if B[i][1] == change2:
            afterindex1 = i
    for i in range(K, N):
        if B[i][1] == change1:
            afterindex1 = i
    result1 = 0
    result2 = 0
    if chindex1 > 0 and afterindex1 > 0:
        result1 = ans * modinv(B[chindex1][0]) * B[afterindex1]
    if chindex2 > 0 and afterindex2 > 0:
        result2 = ans * modinv(B[chindex2][0]) * B[afterindex2]
    ans = max(result1, result2)
    print(ans%mod)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
# マイナスの個数
minus_num = len([i for i in A if i < 0])
A.sort(key=lambda x: abs(x), reverse=True)
A_k, k1_A = A[:k], A[k:]
tmp = 1
for num in A_k:
    tmp *= num
if tmp >= 0:
    print(tmp%MOD)
else:
    a = float("-inf")
    b = float("inf")
    c = float("-inf")
    d = float("inf")
    e = float("-inf")
    f = float("inf")
    # k+1以降でabsが最大のマイナスa
    for i in k1_A:
        if i < 0:
            a = max(a, abs(i))
    # k個のうちでabsが最小のプラスb
    for i in A_k:
        if i > 0:
            b = min(b, i)
    # k+1以降でabsが最大のプラスc
    for i in k1_A:
        if i > 0:
            c = max(c, i)
    # k個のうちでabsが最小のマイナスd
    for i in A_k:
        if i < 0:
            d = min(d, abs(i))
    # k個の内でabsが最大のマイナスe
    for i in A_k:
        if i < 0:
            e = max(e, abs(i))
    # k+1以降でabsが最小のマイナスf
    for i in k1_A:
        if i < 0:
            f = min(f, abs(i))

    if a == float("-inf"):
        if c == float("-inf"):
            print(tmp%MOD)
        else:
            tmp = tmp * c // (-d)
            print(tmp%MOD)
    elif c == float("-inf"):
        if b == float("inf"):
            tmp = tmp * (-f) // (-e)
            print(tmp%MOD)
        else:
            tmp = tmp * (-a) // b
            print(tmp%MOD)
    else:
        if (-a) * (-d) > c * b:
            tmp = tmp * c // d
            print(tmp%MOD)
        else:
            tmp = tmp * a // b
            print(tmp%MOD)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    import bisect
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    a.sort()
    que = deque()

    if n == k:
        que.extend(a)
    elif a[-1] < 0 and k % 2 == 1:
        que.extend(a)
        for _ in range(n - k):
            que.popleft()
    else:
        b = [[] for _ in range(n)]
        for i in range(n):
            b[i] = [abs(a[i]), a[i] // abs(a[i])]
        b.sort(reverse=True)
        b = deque(b)
        que1 = deque()
        que2 = deque()
        sign = 1

        for i in range(k):
            val, sg = b.popleft()
            if sg >= 0:
                que1.append(val)
            else:
                que2.append(val)
                sign *= -1

        if sign == -1:
            add1, add2 = 0, 0
            rmv1, rmv2 = 10 ** 19, 10 ** 19
            if que1:
                rmv1 = que1[-1]
                for x, sign in b:
                    if sign == -1:
                        add1 = x
                        break
            if que2:
                rmv2 = que2[-1]
                for x, sign in b:
                    if sign == 1:
                        add2 = x
                        break

            if add1 * rmv2 > add2 * rmv1:
                que2.append(add1)
                que1.pop()
            else:
                que1.append(add2)
                que2.pop()

        que.extend(que1)
        que.extend(que2)

    while len(que) > 1:
        que.append(que.popleft() * que.popleft())

    print(que.popleft() % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus = []
minus = []
zero = float('inf')
for element in a:
  if element > 0:
    plus.append(element)
  elif not element:
    zero = 0
  else:
    minus.append(element)
plus.sort()
minus.sort()
minus_sub = []
for i in range(1, len(minus), 2):
  minus_sub.append(minus[i-1] * minus[i])
minus_sub.sort()
i = k
answer = 1
while i > 0:
  if plus[-1] > minus_sub[-1]:
    answer *= plus.pop()
    i -= 1
  else:
    answer *= minus_sub.pop()
    i -= 2
print(answer//(10**9+7))

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    import bisect
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    a.sort()
    que = deque()

    if n == k:
        que.extend(a)
    elif a[-1] < 0 and k % 2 == 1:
        que.extend(a)
        for _ in range(n - k):
            que.popleft()
    else:
        b = [[] for _ in range(n)]
        for i in range(n):
            b[i] = [abs(a[i]), a[i] // abs(a[i])]
        b.sort(reverse=True)
        que1 = deque()
        que2 = deque()
        sign = 1

        for i in range(k):
            if b[i][0] >= 0:
                que1.append(b[i][0])
            else:
                que2.append(b[i][0])
                sign *= -1

        if sign == -1:
            add1, add2 = 0, 0
            rmv1, rmv2 = 10 ** 19, 10 ** 19
            if que1:
                rmv1 = que1[-1]
                for x, sign in b:
                    if sign == -1:
                        add1 = x
                        break
            if que2:
                rmv2 = que2[-1]
                for x, sign in b:
                    if sign == 1:
                        add2 = x
                        break

            if add1 * rmv2 > add2 * rmv1:
                que2.append(add1)
                que1.pop()
            else:
                que1.append(add2)
                que2.pop()

        que.extend(que1)
        que.extend(que2)

    while len(que) > 1:
        que.append(que.popleft() * que.popleft())

    print(que.popleft() % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def lpop(ans,l):
    return((ans * l.pop(0)) % (10 ** 9 + 7))
N,K = map(int,input().split())
lp = []
lm = []
for a in map(int,input().split()):
    if a >= 0:
        lp.append(a)
    else:
        lm.append(a)
lp.sort
lm = sorted(lm,reverse=(len(lm) - K) % 2 == 1 and len(lp) == 0)
ans = 1
np = len(lp) == 0
nm = len(lm) == 0
fp = len(lp) == 1
fm = len(lm) == 1
f = len(lp) + len(lm) == 1
skp = 0

for k in range(K):
    if skp:
        skp = 0
        continue
    if np:
        ans = lpop(ans,lm)
        continue
    if nm:
        ans = lpop(ans,lp)
        continue
    if fm:
        ans = lpop(ans,lp)
        if len(lp) == 0:
            np = 1
        continue
    if fp:
        if f:
            ans = lpop(ans,lp)
            continue
        ans = lpop(ans,lm)
        ans = lpop(ans,lm)
        if len(lm) == 0:
            nm = 1
        continue
    p0 = lp[0]
    p1 = lp[1]
    m0 = -1 * lm[0]
    m1 = -1 * lm[1]
    if p0 * p1 > m0 * m1:
        ans = lpop(ans,lp)
        ans = lpop(ans,lp)
    else:
        ans = lpop(ans,lm)
        ans = lpop(ans,lm)
    skp = 1
    np = len(lp) == 0
    nm = len(lm) == 0
    fp = len(lp) == 1
    fm = len(lm) == 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    import bisect
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    a.sort()

    if n == k:
        que = deque(a)
    elif a[-1] < 0 and k % 2 == 1:
        que = deque(a)
        for _ in range(n - k):
            que.popleft()
    else:
        idx = bisect.bisect_left(a, 0)
        b = a[:idx] + a[idx + 1:]
        c = list(map(abs, b))
        que = deque(c)
        for _ in range(n - k):
            que.popleft()

    while len(que) > 1:
        que.append(que.popleft() * que.popleft())

    print(que.popleft() % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [i for i in a if i > 0], [j for j in a if j < 0]

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
            ans %= mod
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
            ans %= mod
        p = []
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p.append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p.append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
            ans %= mod
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [i for i in a if i > 0], [j for j in a if j < 0]

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
            ans %= mod
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
            ans %= mod
        p = []
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p.append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p.append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
            ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [i for i in a if i > 0], [j for j in a if j < 0]

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
            ans %= mod
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
            ans %= mod
        p = []
        p_append = p.append
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p_append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p_append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
            ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [i for i in a if i > 0], [j for j in a if j < 0]

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
        p = []
        p_append = p.append
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p_append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p_append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [i for i in a if i > 0], [j for j in a if j < 0]
    
    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
        p = []
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p.append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p.append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
ans=1
if n==k or max(a)<=0 or min(a)>0:
    a.sort(reverse=True)
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
pos,neg=[],[]
for num in a:
    if num<0:
        neg.append(-num)
    else:
        pos.append(num)
neg.sort(reverse=True)
pos.sort(reverse=True)
nn=len(neg)
np=len(pos)
cand=[]
i,j=0,0
while k>0:
    if i<np-1 and j<nn-1:
        if k>=2:
            if pos[i+1]*pos[i]<neg[i+1]*neg[i]:
                cand.append(-neg[j+1])
                cand.append(-neg[j])
                k-=2
                j+=2
            else:
                cand.append(pos[i])
                k-=1
                i+=1
        else:
            cand.append(pos[i])
            k-=1
            i+=1
    elif j>=nn-1:
        cand.append(pos[i])
        k-=1
        i+=1
    elif i==np-1:
        if k==1:
            cand.append(pos[i])
            i+=1
            k-=1
        else:
            cand.append(-neg[j+1])
            cand.append(-neg[j])
            j+=2
            k-=2
    elif i==np:
        cand.append(-neg[j+1])
        cand.append(-neg[j])
        j+=2
        k-=2
for num in cand:
    ans*=num
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus = []
minus = []
zero = float('inf')
for element in a:
  if element > 0:
    plus.append(element)
  elif not element:
    zero = 0
  else:
    minus.append(element)
plus.sort()
minus.sort()
minus_sub = []
for i in range(0, len(minus), 2):
  minus_sub.append(minus[i] * minus[i+1])
minus_sub.sort()
i = k
answer = 1
while i > 0:
  if plus[-1] > minus_sub[-1]:
    answer *= plus.pop()
    i -= 1
  else:
    answer *= minus_sub.pop()
    i -= 2
print(answer % (10**9+7))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus = []
minus = []
zero = float('inf')
for element in a:
  if element > 0:
    plus.append(element)
  elif not element:
    zero = 0
  else:
    minus.append(element)
plus.sort()
minus.sort()
minus_sub = []
for i in range(0, len(minus), 2):
  minus_sub.append(minus[i] * minus[i+1])
minus_sub.sort()
i = k
answer = 1
while i > 0:
  if plus[-1] > minus_sub[-1]:
    answer *= plus.pop()
    i -= 1
  else:
    answer *= minus_sub.pop()
    i -= 2
print(answer//(10**9+7))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
plus = []
minus = []
zero = float('inf')
for element in a:
  if element > 0:
    plus.append(element)
  elif not element:
    zero = 0
  else:
    minus.append(element)
plus.sort()
minus.sort()
minus_sub = []
for i in range(0, len(minus), 2):
  minus_sub.append(minus[i] * minus[i+1])
minus_sub.sort()
i = k
answer = 1
while i > 0:
  if plus[-1] > minus_sub[-1]:
    answer *= plus.pop()
    i -= 1
  else:
    answer *= minus_sub.pop()
    i -= 2
print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque

MOD = 10**9+7
INF = 10**18+10

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

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

# 個別を読んでいく
not_negative = []
negative = []
for a in A:
    if a < 0:
        negative.append(a)
    else:
        not_negative.append(a)


negR = sorted(negative, reverse=True)

# 全部負で奇数個選ぶとき，答えは負なので最小にする
if len(negative) == N and K % 2 == 1:
    ans = 1
    for k in range(K):
        ans *= negR[k]
        ans %= MOD
    print(ans)
    exit()


not_negative.sort(reverse=True)
negative.sort()

# dequeに入れて2つずつ取る
not_negative = deque(not_negative)
negative = deque(negative)
ans = 1
count = 0

while count < K:
    # あと1つしか使えないとき，負を2つ使えない
    flag1 = count == K - 1
    # 残りの負が1つしかない (2つ使えない)
    flag2 = len(negative) < 2
    # |x1 x2| > |y1 y2| (解法2)
    flag3 = len(not_negative) >= 2 and not_negative[0] * not_negative[1] > negative[0] * negative[1]
    if flag1 or flag2 or flag3:
        ans = ans * not_negative.popleft() % MOD
        count += 1
    else:
        ans = ans * negative.popleft() * negative.popleft() % MOD
        count += 2

print(ans)

Submission status: Runtime Error

Solution code:
MOD = int(1e9 + 7)

N, K = map(int, input().split())
A = list(map(int, input().split()))
AA = sorted(A, key=lambda x: abs(x))
AAr = sorted(A, key=lambda x: abs(x), reverse=True)


ans = 1
if N == K:
    for a in A:
        ans *= a
        ans %= MOD
elif all([a < 0 for a in A]) and K % 2 == 1:
    for k in range(K):
        ans *= AA[k]
    ans %= MOD
else:
    AArk = AAr[:K]
    AArem = AAr[K:]
    # print(AAr)
    # print(AArk)
    for k in range(K):
        ans *= AAr[k]
    if ans > 0:
        ans %= MOD
    else:
        # 負を1つとり除き，非負を1つ加える
        neg1 = float("inf")
        for a in AArk:
            if a < 0 and abs(a) < abs(neg1):
                neg1 = a
        # 代わりに入れる
        pos1 = None
        for a in AArem:
            if a > 0:
                pos1 = a
                break
        # print(neg1, pos1)

        # 正を1つとり除き，負を1つ加える
        pos2 = float("inf")
        for a in AArk:
            if a > 0 and abs(a) < abs(pos2):
                pos2 = a
        if pos2 == float("inf"):
            ans = ans // neg1 * pos1
            ans %= MOD
        else:
            # 非負にする
            neg2 = None
            for a in AArem:
                if a < 0:
                    neg2 = a
                    break

            # (pos1, neg1) と (pos2, neg2) を比較
            ans1 = ans // neg1 * pos1
            ans2 = ans // pos2 * neg2
            ans = max(ans1, ans2)
            ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
import sys


def divide_a_by_b_mod(a, b, MOD):
    a, b = int(a), int(b)
    return (a % MOD * pow(b, MOD - 2, MOD)) % MOD


input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x), reverse=True)
MOD = 10**9 + 7

# print(f'{A=}')

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

if K % 2 == 1:
    if max(A) < 0:
        ans = 1
        for a in A[::-1][:K]:
            ans *= a
            ans %= MOD
        print(ans)
        exit()

P = 1
for a in A[:K]:
    if a >= 0:
        P *= 1
    else:
        P *= -1
# print(f'{P=}')

if P > 0:
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# (1) 負の数を 1 つ取り除き、非負の数を 1 つ加える
patern_one = True
plus1, minus1 = 0, 0
for plus1 in A[K:]:
    if plus1 >= 0:
        break
else:
    patern_one = False
for minus1 in A[:K][::-1]:
    if minus1 < 0:
        break
else:
    patern_one = False
# print(f'{plus1=}, {minus1=}, {patern_one=}')

# (2) 正の数を 1 つ取り除き、負の数を 1 つ加える
patern_two = True
plus2, minus2 = 0, 0
for plus2 in A[:K][::-1]:
    if plus2 >= 0:
        break
else:
    patern_two = False
for minus2 in A[K:]:
    if minus2 < 0:
        break
else:
    patern_two = False
# print(f'{plus2=}, {minus2=}, {patern_two=}')


def f1():
    subset = deepcopy(A[:K])
    subset.remove(minus1)
    subset.append(plus1)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


def f2():
    subset = deepcopy(A[:K])
    subset.remove(plus2)
    subset.append(minus2)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


P = 1
for a in A[:K]:
    P = P * a % MOD

if patern_one and patern_two:
    if abs(plus2 * minus1) < abs(plus1 * minus2):
        # (1)
        ans = divide_a_by_b_mod(P, plus2) * minus1 % P
        # ans = f1()
    else:
        # (2)
        ans = divide_a_by_b_mod(P, minus1) * plus1 % P
        # ans = f2()
elif patern_one:
    ans = f1()
else:
    ans = f2()
print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
import sys


def divide_a_by_b_mod(a, b, MOD):
    a, b = int(a), int(b)
    return (a % MOD * pow(b, MOD - 2, MOD)) % MOD


input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x), reverse=True)
MOD = 10**9 + 7

# print(f'{A=}')

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

if K % 2 == 1:
    if max(A) < 0:
        ans = 1
        for a in A[::-1][:K]:
            ans *= a
            ans %= MOD
        print(ans)
        exit()

P = 1
for a in A[:K]:
    if a >= 0:
        P *= 1
    else:
        P *= -1
# print(f'{P=}')

if P > 0:
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# (1) 負の数を 1 つ取り除き、非負の数を 1 つ加える
patern_one = True
plus1, minus1 = 0, 0
for plus1 in A[K:]:
    if plus1 >= 0:
        break
else:
    patern_one = False
for minus1 in A[:K][::-1]:
    if minus1 < 0:
        break
else:
    patern_one = False
# print(f'{plus1=}, {minus1=}, {patern_one=}')

# (2) 正の数を 1 つ取り除き、負の数を 1 つ加える
patern_two = True
plus2, minus2 = 0, 0
for plus2 in A[:K][::-1]:
    if plus2 >= 0:
        break
else:
    patern_two = False
for minus2 in A[K:]:
    if minus2 < 0:
        break
else:
    patern_two = False
# print(f'{plus2=}, {minus2=}, {patern_two=}')


def f1():
    subset = deepcopy(A[:K])
    subset.remove(minus1)
    subset.append(plus1)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


def f2():
    subset = deepcopy(A[:K])
    subset.remove(plus2)
    subset.append(minus2)
    # print(f'{subset=}')
    ans = 1
    for s in subset:
        ans *= s
        ans %= MOD
    return ans


P = 1
for a in A[:K]:
    P = P * a % MOD

if patern_one and patern_two:
    if abs(plus2 * minus1) < abs(plus1 * minus2):
        # (1)
        ans = divide_a_by_b_mod(P, minus1) * plus1 % P
        # ans = f1()
    else:
        # (2)
        ans = divide_a_by_b_mod(P, plus2) * minus1 % P
        # ans = f2()
elif patern_one:
    ans = f1()
else:
    ans = f2()
print(ans)