Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

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

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

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

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

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

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

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

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

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

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

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

Sample Input 4

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

Sample Output 4

999983200

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



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
T = {"mi":0, "pu":0, "zero":0}

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
            break
    for i in range(K, N):
        if B[i][1] == change1:
            afterindex2 = i
            break
    result1 = 0
    result2 = 0
    if chindex1 >= 0 and afterindex1 >= 0:
        ans = 1
        for i in range(N):
            if i <= K-1 or i == afterindex1:
                if i != chindex1:
                    ans *= B[i][0]
                    ans %= mod
        result1 = ans
    if chindex2 >= 0 and afterindex2 >= 0:
        ans = 1
        for i in range(N):
            if i <= K-1 or i == afterindex2:
                if i != chindex2:
                    ans *= B[i][0]
                    ans %= mod
        result2 = ans
    ans = max(result1, result2)
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
# 色々参考にしつつ

n,k,*a=map(int,open(0).read().split())
MOD=10**9+7
a.sort()
if a[0]<0:
  if k%2==1:
    ans=1
    a=a[::-1]
    for i in range(k):
      ans=ans*a[i]%MOD
    print(ans%MOD)
    exit()

a=a[::-1]
ans=1
l=0
r=n-1
if k%2==1:
  ans=ans*a[l]%MOD
  l+=1
for i in range(k//2):
  if a[l]*a[l+1]>=a[r-1]*a[r]:
    ans=ans*(a[l]*a[l+1])%MOD
    l+=2
  else:
    ans=ans*(a[r-1]*a[r])%MOD
    r-=2

print(ans%MOD)

Submission status: Wrong Answer

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:
        aam.sort()
        if k%2==1:
            return mul(aam[-k:])
        else:
            return mul(aam[:k])

    aap = aa[aa>=0]
    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)]
    aap2.extend(aam2)
    aap2.sort(reverse=True)
    return (ret*mul(aap2[:k//2]))%mod
print(sol(aa, n, k))

Submission status: Wrong Answer

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:
        aam.sort()
        if k%2==1:
            return mul(aam[:k])
        else:
            return mul(aam[-k:])

    aap = aa[aa>=0]
    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)]
    aap2.extend(aam2)
    aap2.sort(reverse=True)
    return (ret*mul(aap2[:k//2]))%mod
print(sol(aa, n, k))

Submission status: Wrong Answer

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(max(0, k-len(plus)), min(len(minus)+1, k+1), 2):
    if i % 2 == 1:
      continue
    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: Wrong Answer

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)
debug('program begins.')

mod = 10**9 + 7
n, k = map(int, input().split())
A = [*map(int, input().split())]
A.sort(reverse=True, key=lambda x: abs(x))
m_max = p_max = 0
for a in A:
    if a<0: m_max += 1
    else: p_max += 1

debug('k {} <= n {}'.format(k,n))
debug('m_max {} p_max {}'.format(m_max,p_max))
debug('A {}'.format(A))
debug('A[:k-1] {}'.format(A[:k-1]))
debug('A[k-1:n] {}'.format(A[k-1:n]))
debug('---')

m_sign = p_sign = 0
ans = 1
for a in A[:k-1]:
    ans *= a; ans %= mod
    if a < 0: m_sign += 1
    else: p_sign += 1

debug('m_sign {} p_sign {} ans {}'.format(m_sign,p_sign,ans))

if m_sign%2: # odd -> ans < 0 -> ans * a (a<0)
    if m_max - m_sign > 0:
        for a in A[k-1:n]:
            if a < 0:
                ans *= a; ans %= mod
                m_sign += 1
                break
    else:
        A.sort(key=lambda x: abs(x))
        debug('A {}'.format(A))
        debug('A[:k-1] {}'.format(A[:k-1]))
        debug('A[k-1:n] {}'.format(A[k-1:n]))
        m_sign = p_sign = 0
        ans = 1
        for a in A[:k-1]:
            ans *= a; ans %= mod
            if a < 0: m_sign += 1
            else: p_sign += 1
        debug('m_sign {} p_sign {} ans {}'.format(m_sign,p_sign,ans))

        if m_sign%2: # odd -> ans < 0 -> ans * a (a>=0)
            for a in A[k-1:n]:
                if a >= 0:
                    ans *= a; ans %= mod
                    p_sign += 1
                    break
        else: # even -> ans >= 0 -> ans * a (a<0)
            for a in A[k-1:n]:
                if a < 0:
                    ans *= a; ans %= mod
                    m_sign += 1
                    break

else: # even -> ans >= 0 -> ans * a (a>=0)
    if p_max - p_sign > 0:
        for a in A[k-1:n]:
            if a >= 0:
                ans *= a; ans %= mod
                p_sign += 1
                break
    else:
        A.sort(key=lambda x: abs(x))
        debug('A {}'.format(A))
        debug('A[:k-1] {}'.format(A[:k-1]))
        debug('A[k-1:n] {}'.format(A[k-1:n]))
        m_sign = p_sign = 0
        ans = 1
        for a in A[:k-1]:
            ans *= a; ans %= mod
            if a < 0: m_sign += 1
            else: p_sign += 1
        debug('m_sign {} p_sign {} ans {}'.format(m_sign,p_sign,ans))

        if m_sign%2: # odd -> ans < 0 -> ans * a (a>=0)
            for a in A[k-1:n]:
                if a >= 0:
                    ans *= a; ans %= mod
                    p_sign += 1
                    break
        else: # even -> ans >= 0 -> ans * a (a<0)
            for a in A[k-1:n]:
                if a < 0:
                    ans *= a; ans %= mod
                    m_sign += 1
                    break

debug('m_sign {} p_sign {} ans {}'.format(m_sign,p_sign,ans))

ans += mod; ans %= mod
debug('ans {}'.format(ans))
print(ans)

Submission status: Wrong Answer

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:
        lg.pop(lg.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: Wrong Answer

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(lg.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: Wrong Answer

Solution code:
from logging import *
basicConfig(level=DEBUG, format='%(levelname)s: %(message)s')
disable(CRITICAL)
debug('program begins.')

mod = 10**9 + 7
n, k = map(int, input().split())
A = [*map(int, input().split())]
A.sort(reverse=True, key=lambda x: abs(x))
m_max = p_max = 0
for a in A:
    if a<0: m_max += 1
    else: p_max += 1

debug('k {} <= n {}'.format(k,n))
debug('m_max {} p_max {}'.format(m_max,p_max))
debug('A {}'.format(A))
debug('A[:k-1] {}'.format(A[:k-1]))
debug('A[k-1:n] {}'.format(A[k-1:n]))
debug('---')

m_sign = p_sign = 0
ans = 1
for a in A[:k-1]:
    ans *= a; ans %= mod
    if a < 0: m_sign += 1
    else: p_sign += 1

debug('m_sign {} p_sign {} ans {}'.format(m_sign,p_sign,ans))

if m_sign%2: # odd -> ans < 0 -> ans * a (a<0)
    for a in A[k-1:n]:
        if a < 0:
            ans *= a; ans %= mod
            m_sign += 1
            break
else: # even -> ans >= 0 -> ans * a (a>=0)
    if p_max - p_sign> 0:
        for a in A[k-1:n]:
            if a >= 0:
                ans *= a; ans %= mod
                p_sign += 1
                break
    else:
        A.sort(key=lambda x: abs(x))
        debug('A {}'.format(A))
        debug('A[:k-1] {}'.format(A[:k-1]))
        debug('A[k-1:n] {}'.format(A[k-1:n]))
        m_sign = p_sign = 0
        ans = 1
        for a in A[:k-1]:
            ans *= a; ans %= mod
            if a < 0: m_sign += 1
            else: p_sign += 1
        debug('m_sign {} p_sign {} ans {}'.format(m_sign,p_sign,ans))

        if m_sign%2: # odd -> ans < 0 -> ans * a (a>=0)
            for a in A[k-1:n]:
                if a >= 0:
                    ans *= a; ans %= mod
                    p_sign += 1
                    break
        else: # even -> ans >= 0 -> ans * a (a<0)
            for a in A[k-1:n]:
                if a < 0:
                    ans *= a; ans %= mod
                    m_sign += 1
                    break

debug('m_sign {} p_sign {} ans {}'.format(m_sign,p_sign,ans))

ans += mod; ans %= mod
debug('ans {}'.format(ans))
print(ans)

Submission status: Wrong Answer

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
            break
    for i in range(K, N):
        if B[i][1] == change1:
            afterindex2 = i
            break
    result1 = 0
    result2 = 0
    if chindex1 > 0 and afterindex1 > 0:
        ans = 1
        for i in range(N):
            if i <= K-1 or i == afterindex1:
                if i != chindex1:
                    ans *= B[i][0]
                    ans %= mod
        result1 = ans
    if chindex2 > 0 and afterindex2 > 0:
        ans = 1
        for i in range(N):
            if i <= K-1 or i == afterindex2:
                if i != chindex2:
                    ans *= B[i][0]
                    ans %= mod
        result2 = ans
    ans = max(result1, result2)
    print(ans%mod)

Submission status: Wrong Answer

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]))%mod * B[afterindex1][0]
    if chindex2 > 0 and afterindex2 > 0:
        result2 = (ans * modinv(B[chindex2][0]))%mod * B[afterindex2][0]
    ans = max(result1, result2)
    print(ans%mod)

Submission status: Wrong Answer

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]]
        b.sort(reverse=True)
        b = deque(b)
        que1 = deque()
        que2 = deque()
        sign = 1

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

        if sign == -1:
            add1, add2 = 0, 0
            rmv1, rmv2 = 10 ** 19, 10 ** 19
            if que1:
                rmv1 = que1[-1]
                for x_abs, x in b:
                    if x < 0:
                        add1 = x
                        break
            if que2:
                rmv2 = que2[-1]
                for x_abs, x in b:
                    if x > 0:
                        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: Wrong Answer

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]]
        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)
            elif sg < 0:
                que2.append(val)
                sign *= -1
            else:
                print(0)
                return

        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: Wrong Answer

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]]
        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: Wrong Answer

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
    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:
        a = list(map(abs, a))
        a.sort()
        que = deque(a)
        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: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, key= lambda x: abs(x), reverse=True)
mod = int(1e9) + 7
inf = float("inf")

# すべて負の数であった場合
ans = 1
if all(a < 0 for a in A):
    # Kが偶数の場合
    if K % 2 == 0:
        for el in range(K):
            ans *= A[el] % mod
            ans = ans % mod
    
    # Kが奇数であった場合
    else:
        A = list(reversed(A))
        for el in range(K):
            ans *= A[el] % mod
            ans = ans % mod

# それ以外
else:
    box = []
    for el in range(K):
        if el >= 0:
            box.append("+")
        else:
            box.append("-")
        ans *= A[el] % mod
        ans = ans % mod
    # ans >= 0の場合OK、それ以外の場合、場合にわける
    if ans >= 0:
        pass
    # NがKに同値であった場合はこの値で確定となる
    elif N == K:
        pass
    else:
        # K個中にある負の数のうち絶対値が最小のものを外し、K個外にある正の数のうち絶対値が最大のものを入れる
        ind, pind = -1, -1
        for i in reversed(range(K)):
            if box[i] == "-":
                ind = i
                break
        for i in range(K, N):
            if A[i] > 0:
                pind = i
                break
        if pind == -1:
            temp1 = -inf
        else:
            temp1 = 1
            for i in range(K):
                if i != ind:
                    temp1 *= A[i] % mod
                    temp1 = temp1 % mod
            temp1 *= A[pind] % mod
            temp1 %= mod

        # K個中にある正の数のうち絶対値が最小のものを外し、K個外にある負の数のうち絶対値が最大のものを入れる
        ind, mind = -1, -1
        for i in reversed(range(K)):
            if box[i] == "+":
                ind = i
                break
        for i in range(K, N):
            if A[i] < 0:
                mind = i
                break
        if mind == -1:
            temp2 = -inf
        else:
            temp2 = 1
            for i in range(K):
                if i != ind:
                    temp2 *= A[i] % mod
                    temp2 %= mod
            temp2 *= A[mind] % mod
            temp2 %= mod
        ans = max(temp1, temp2)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

mod = 10 ** 9 + 7

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

A.sort(reverse = True)

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

l = 0
r = N-1

ans = 1
if K % 2 == 1:
    ans *= A[0]
    l += 1

for _ in range(K // 2):
    if A[l] * A[l+1] > A[r] * A[r-1]:
        ans *= A[l] * A[l+1]
        ans %= mod
        l += 2
    else:
        ans *= A[r] * A[r-1]
        ans %= mod
        r -= 2

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
 
mod = 10 ** 9 + 7
 
N, K = map(int,input().split())
A = list(map(int,input().split()))
 
if N == K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

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

plus.sort(reverse = True)
minus.sort()
 
ans = 1
flag = 0
if K % 2 == 1:
    flag = 1
    K -= 1
    ans *= plus[0]

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

Submission status: Wrong Answer

Solution code:
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[j+1]*neg[j]:
                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: Wrong Answer

Solution code:
mod = 1000000007
N, K = map(int, input().split())

pos = []
neg = []
A = list(map(int, input().split()))
for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    else:
        neg.append(A[i])

ans = 1
if len(pos) == 0:
    neg.sort()
    for i in range(K):
        ans = (ans * neg.pop()) % mod
elif N == K:
    for i in pos:
        ans = (ans * i) % mod
    for i in neg:
        ans = (ans * i) % mod
else:
    pos.sort()
    neg.sort(reverse=True)
    if K % 2 == 1:
        ans = pos.pop()
    for i in range(K//2):
        if len(pos) > 1 and len(neg) > 1:
            if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
                for _ in range(2):
                    ans = ans * pos.pop() % mod
            else:
                for _ in range(2):
                    ans = ans * neg.pop()
        elif len(pos) > 1:
            for _ in range(2):
                ans = ans * pos.pop() % mod
        else:
            for _ in range(2):
                ans = ans * neg.pop() % mod

print(ans)

Submission status: Wrong Answer

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
        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)