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

Submission status: Wrong Answer

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

allm = True
for a in A:
    if a > 0:
        allm = False
        break

if N == K:
    ans = 1
    for a in A:
        ans = (ans*a) % MOD
    print(ans)
elif allm and K % 2 == 1:
    A.sort()
    A.reverse()
    ans = 1
    for a in A[:K]:
        ans = (ans*a) % MOD
    print(ans)
else:
    p, m = [], []
    for a in A:
        if a > 0:
            p.append(a)
        if a < 0:
            m.append(-a)
    p.sort(key=lambda k: -k)
    m.sort(key=lambda k: -k)

    pi, mi = 0, 0
    ans = 1
    while K > 0:
        if K == 1:
            ans = (ans*p[pi]) % MOD
            break
        elif pi < len(p) or mi < len(m)-1:
            pv, mv = 0, 0
            if pi < len(p):
                pv = p[pi]
            if mi < len(m)-1:
                mv = m[mi]*m[mi+1]

            if pv > mv:
                ans = (ans*p[pi]) % MOD
                pi += 1
                K -= 1
            else:
                ans = (ans*mv) % MOD
                mi += 2
                K -= 2
        else:
            ans = 0
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    from collections import Counter
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    ans = modint(1)
    if N == K:
        for a in A:
            ans *= a
        return print(ans)
    elif all(a < 0 for a in A) and K % 2 == 1:
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
        return print(ans)
    # 以降，非負の答えにできる
    if sum(a < 0 for a in A[:K]) % 2 == 0:
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
    else:
        ans1 = modint(1)  # 正を取り除く
        ans2 = modint(1)  # 負を取り除く
        p_remove = False
        p_re = -1
        for a in A[:K][::-1]:
            if a > 0 and not p_remove:
                p_remove = True
                p_re = a
                continue
            ans1 *= a
        n_remove = False
        n_re = -1
        for a in A[:K][::-1]:
            if a < 0 and not n_remove:
                n_remove = True
                n_re = a
                continue
            ans2 *= a
        mul1 = 0  # 一番大きい正
        mul2 = 0  # 一番大きい負
        for a in A[K:]:
            if mul1 == 0 and a > 0:
                mul1 = a
            if mul2 == 0 and a < 0:
                mul2 = a
            if mul1 != 0 and mul2 != 0:
                break
        ans1 *= mul2
        ans2 *= mul1
        if abs(mul2*n_re) > abs(mul1*p_re):
            ans = ans1
        else:
            ans = ans2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

mod = 10**9 + 7

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

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

Bm = list(zip(Am, [1]*pm[0]))
Bp = list(zip(Ap, [0]*pm[1]))
B = Bm + Bp
ans = 1
cnt = 0

if pm[0] == N and K%2 == 1:
  for i in range(K):
    ans *= B[i][0]
    ans %= mod
  print(ans)
  exit()

B.sort(reverse = True)  

for i in range(K):
  ans *= B[i][0]
  ans %= mod
  cnt ^= B[i][1]

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

amcnt, apcnt, rmcnt, rpcnt = 0, 0, 0, 0  

ans1, ans2 = ans, ans

for i in range(K+1, N):
  if B[i][1] == 1:
    amcnt += 1
    ans1 *= B[i][0]
    ans1 %= mod
    break

for i in range(K+1, N):
  if B[i][1] == 0:
    apcnt += 1
    ans2 *= B[i][0]
    ans2 %= mod
    break

for i in range(K-1, -1, -1):
  if B[i][1] == 1:
    rmcnt += 1
    r = pow(B[i][0], mod-2, mod)
    ans2 *= r
    ans2 %= mod
    break

for i in range(K-1, -1, -1):
  if B[i][1] == 0:
    rpcnt += 1
    r = pow(B[i][0], mod-2, mod)
    ans1 *= r
    ans1 %= mod
    break

Flag1 = (amcnt + rpcnt) % 2
Flag2 = (apcnt + rmcnt) % 2

if Flag1 == 0 and Flag2 == 0:
  print(max(ans1, ans2))
elif Flag1 == 0:
  print(ans1)
else:
  print(ans2)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
res = 1
if N == K:
    for a in A:
        res *= a
        res %= MOD
    print(res)
    exit()
cnt = sum(1 if a < 0 else 0 for a in A)
if cnt == N and K % 2 == 1:
    for a in A[N-1:N-K-1:-1]:
        res *= a
        res %= MOD
    print(res)
    exit()
minus = -1
plus = 1
for a in A[:K]:
    res *= a
    res %= MOD
    if a > 0:
        plus = a
    else:
        minus = a
if res < 0:
    tmp1 = 0
    tmp2 = 0
    f1 = False
    f2 = False
    for a in A[K:]:
        if f1 and f2:
            break
        if a > 0 and not f1:
            tmp1 = a
            f1 = True
        elif a < 0 and not f2:
            tmp2 = a
            f2 = True
    if abs(minus * tmp1) > abs(plus * tmp2):
        res //= minus
        res *= tmp1
        res %= MOD
    else:
        res //= plus
        res *= tmp2
        res %= MOD
print(res)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
plus = [] # 非負数
minus = [] # 負数
c = 0
for i in list(map(int, input().split())):
    c += 1
    if i >= 0:
        plus.append(i)
    else:
        minus.append(i)
plen = len(plus)
mlen = len(minus)
plus.sort(reverse=True)
minus.sort()

# 累積積
pp = [1]
mp = [1]
for p in plus:
    pp.append((pp[-1]*p)%mod)
for m in minus:
    mp.append((mp[-1]*m)%mod)

# 累積積(逆順)
ppm = [1]
mpm = [1]
for p in plus[::-1]:
    ppm.append((ppm[-1]*p)%mod)
for m in minus[::-1]:
    mpm.append((mpm[-1]*m)%mod)

ans = -float("inf")
# k個マイナスから選ぶ
for k in range(K+1):
    if mlen < k:
        continue
    if plen < K-k:
        continue
    if k % 2 == 0: # 絶対値最大を目指す
        tmp = mp[k] * pp[K-k]
        tmp %= mod
        ans = max(ans, tmp)
    else: # 絶対値最小を目指す
        if ans == -float("inf"):
            tmp = mpm[k] * ppm[K-k]
            ans = max(ans, tmp)
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())), key = lambda x:-abs(x))
ans = 1
mod = 10 ** 9 + 7
sign = 1
flag = False
for i in range(k):
    if a[i] < 0:
        sign *= -1
    else:
        flag = True
if not flag or n == k:
    a = a[::-1]
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
else:
    if sign > 0:
        for i in range(k):
            ans *= a[i]
            ans %= mod
        print(ans)
    else:
        tmp_plus1, tmp_plus2, tmp_minus1, tmp_minus2 = (0, 0), (0, 0), (0, 0), (0, 0)
        for i in range(k)[::-1]:
            if a[i] >= 0:
                tmp_plus1 = (a[i], i)
                break
        for j in range(k, n):
            if a[j] < 0:
                tmp_plus2 = (a[j], j)
                break
        for i in range(k)[::-1]:
            if a[i] < 0:
                tmp_minus1 = (a[i], i)
                break
        for j in range(k, n):
            if a[i] >= 0:
                tmp_minus2 = (a[j], j)
                break
        if abs(tmp_plus1[0] * tmp_minus2[0]) < abs(tmp_plus2[0] * tmp_minus1[0]):
            a[tmp_plus2[1]], a[tmp_minus1[1]] = a[tmp_minus1[1]], a[tmp_plus2[1]]
        
        for i in range(k):
            ans *= a[i]
            ans %= mod
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heapify, heappush
mod = 10**9 + 7
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
plus = []
minus = []
zero = []
ans = []
for a in A:
    if a > 0:
        plus.append(-a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(a)
heapify(plus)
heapify(minus)
cnt = 0
last_minus = 0
last_plus = 0
if len(plus) + len(minus) < K:
    print(0)
    sys.exit()

if len(plus) == 0:
    if K%2 == 1:
        print(0)
        sys.exit()
    else:
        A.sort()
        num = 1
        for x in A[:K]:
            num *= x%mod
        print(num%mod)
        sys.exit()

if len(minus) == 0:
    num = 1
    plus.sort(reverse=True)
    for x in plus[:K]:
        if x < 0:
            x = -x
        num *= x
        num %= mod
    print(num%mod)
    sys.exit()

if len(plus) + len(minus) == K:
    if len(minus)%2 == 0:
        num = 1
        for x in plus:
            num *= x%mod
        for x in minus:
            num *= x%mod
        print(num%mod)
        sys.exit()
    else:
        print(0)
        sys.exit()

flag = 0

for i in range(K):
    if len(plus) > 0 and len(minus) > 0:
        a = heappop(plus)
        b = heappop(minus)
    elif len(plus) == 0:
        flag = 1
        break
    else:
        flag = 2
        break
    if a >= b:
        ans.append(b)
        heappush(plus, a)
        cnt += 1
        last_minus = b
    else:
        ans.append(a)
        heappush(minus, b)
        last_plus = a

if flag == 1:
    for i in range(K - len(ans)):
        a = heappop(minus)
        last_minus = a
        cnt += 1
        ans.append(a)

if flag == 2:
    for i in range(K - len(ans)):
        a = heappop(plus)
        last_plus = a
        ans.append(a)

if cnt%2 == 0:
    num = 1
    for a in ans:
        if a < 0:
            a = -a
        num = (num * a%mod)%mod
    print(num%mod)
    sys.exit()
else:
    num = 1
    ls = []
    for a in ans:
        if a < 0:
            ls.append(-a)
        else:
            ls.append(a)

    if len(plus) != 0 and len(minus) != 0:
        a = heappop(plus)
        b = heappop(minus)
        if a < 0:
            a = -a
        if b < 0:
            b = -b
        if last_minus < 0:
            last_minus = -last_minus
        if last_plus < 0:
            last_plus = -last_plus
        
        if last_plus == 0:
            for c in ls[:-1]:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
            sys.exit()
        if last_minus == 0:
            for c in ls[:-1]:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)
            sys.exit()

        if a *last_plus >= b*last_minus:
            ls.remove(last_minus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
        else:
            ls.remove(last_plus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)
    elif len(plus) == 0:
        c = heappop(minus)
        if c < 0:
            c = -c
        if last_plus < 0:
            last_plus = -last_plus
        ls.remove(last_plus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)
    elif len(minus) == 0:
        c = heappop(plus)
        if c < 0:
            c = -c
        if last_minus < 0:
            last_minus = -last_minus
        ls.remove(last_minus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heapify, heappush
mod = 10**9 + 7
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
plus = []
minus = []
zero = []
ans = []
for a in A:
    if a > 0:
        plus.append(-a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(a)
heapify(plus)
heapify(minus)
cnt = 0
last_minus = 0
last_plus = 0
if len(plus) + len(minus) < K:
    print(0)
    sys.exit()

if len(plus) == 0:
    if K%2 == 1:
        num = 1
        minus.sort()
        for x in minus[::-1][:K]:
            num *= x%mod
        print(num%mod)
        sys.exit()
    else:
        A.sort()
        num = 1
        for x in A[:K]:
            num *= x%mod
        print(num%mod)
        sys.exit()

if len(minus) == 0:
    num = 1
    plus.sort(reverse=True)
    for x in plus[:K]:
        if x < 0:
            x = -x
        num *= x
        num %= mod
    print(num%mod)
    sys.exit()

if len(plus) + len(minus) == K:
    if len(minus)%2 == 0:
        num = 1
        for x in plus:
            num *= x%mod
        for x in minus:
            num *= x%mod
        print(num%mod)
        sys.exit()
    else:
        print(0)
        sys.exit()

flag = 0

for i in range(K):
    if len(plus) > 0 and len(minus) > 0:
        a = heappop(plus)
        b = heappop(minus)
    elif len(plus) == 0:
        flag = 1
        break
    else:
        flag = 2
        break
    if a >= b:
        ans.append(b)
        heappush(plus, a)
        cnt += 1
        last_minus = b
    else:
        ans.append(a)
        heappush(minus, b)
        last_plus = a

if flag == 1:
    for i in range(K - len(ans)):
        a = heappop(minus)
        last_minus = a
        cnt += 1
        ans.append(a)

if flag == 2:
    for i in range(K - len(ans)):
        a = heappop(plus)
        last_plus = a
        ans.append(a)

if cnt%2 == 0:
    num = 1
    for a in ans:
        if a < 0:
            a = -a
        num = (num * a%mod)%mod
    print(num%mod)
    sys.exit()
else:
    num = 1
    ls = []
    for a in ans:
        if a < 0:
            ls.append(-a)
        else:
            ls.append(a)

    if len(plus) != 0 and len(minus) != 0:
        a = heappop(plus)
        b = heappop(minus)
        if a < 0:
            a = -a
        if b < 0:
            b = -b
        if last_minus < 0:
            last_minus = -last_minus
        if last_plus < 0:
            last_plus = -last_plus
        
        if last_plus == 0:
            for c in ls[:-1]:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
            sys.exit()
        if last_minus == 0:
            for c in ls[:-1]:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)
            sys.exit()

        if a *last_plus >= b*last_minus:
            ls.remove(last_minus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
        else:
            ls.remove(last_plus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)
    elif len(plus) == 0:
        c = heappop(minus)
        if c < 0:
            c = -c
        if last_plus < 0:
            last_plus = -last_plus
        ls.remove(last_plus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)
    elif len(minus) == 0:
        c = heappop(plus)
        if c < 0:
            c = -c
        if last_minus < 0:
            last_minus = -last_minus
        ls.remove(last_minus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)

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

p = []
P = 0
z = False
t = 0
for i in a:
  if i > 0:
    p.append((i,1))
    P += 1
  elif i == 0:
    p.append((0,0))
    z = True
  else:
    p.append((-i,-1))

if P == 0 and k%2 == 1:
  if z:
    print(0)
  else:
    ans = 1
    p.sort()
    for i in range(k):
      ans *= -p[i][0]
      ans %= mod
    print(ans)
  exit()

p.sort(reverse=True)
mi_p = 0
ma_m = 0
c = 0

for i in range(k):
  if p[i][1] > 0:
    mi_p = i
  elif p[i][1] == 0:
    print(0)
    exit()
  else:
    ma_m = i
    c += 1
    
if c%2 == 0:
  ans = 1
  for i in range(k):
    ans *= p[i][0]
    ans %= mod
  print(ans)
elif n == k:
  ans = 1
  for i in a:
    ans *= i
    ans %= mod
  print(ans)
else:
  ma_p = 0
  mi_m = 0
  for i in range(n-k):
    L = p[k+i]
    if L[1] > 0 and ma_p == 0:
      ma_p = p[k+i][0]
    if L[1] < 0 and mi_m == 0:
      mi_m = p[k+i][0]
    if ma_p*mi_m != 0:
      break
  ans_p = 1
  ans_m = 1
  for i in range(k):
    if i == ma_m:
      ans_p *= p[i][0]
    elif i == mi_p:
      ans_m *= p[i][0]
    else:
      ans_p *= p[i][0]
      ans_m *= p[i][0]
    ans_p %= mod
    ans_m %= mod
  if mi_m*p[ma_m][0] > ma_p*p[mi_p][0]:
    print(ans_p*mi_m%mod)
  else:
    print(ans_m*ma_p%mod)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    elif i == 0:
        li.append((0, 0))
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    if k %2 ==1:
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans *= li[n-1-i][0]
            ans %= mod
        print(ans)
        exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    if n-k-1 >= 0:
        for i in range(n-k-1, -1, -1):
            if li[i][1] >= 0:
                plus = li[i][0]
                p = i
                p1 = False
                break
        for i in range(n-k-1, -1, -1):
            if li[i][1] <= 0:
                mini = li[i][0]
                m = i
                m1 = False
                break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans2 *= li[i][0]
            ans2 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if (not p1) and (not P1) and (not M1) and (not m1):
        if mini/Plus > plus/Mini:
            print(ans1)
        else:
            print(ans2)
    elif (not p1) and (not M1):
        print(ans2)
    elif (not m1) and (not P1):
        print(ans1)
    else:
        ans = 1
        for i in range(k):
            ans *= li[i][0]
            ans %= mod
        ans *= -1
        ans %= mod
        print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
# N = int(input())
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
A_p = []
A_n = []
for a in A:
  if a >= 0:
    A_p.append(a)
  else:
    A_n.append(-a)

A_p.sort(reverse=True)
A_n.sort(reverse=True)
A_p = deque(A_p)
A_n = deque(A_n)

p_top = 0
n_top = 0
ans_p = deque([])
ans_n = deque([])
for i in range(K):
  if len(A_p) == 0:
    ans_n.append(A_n.popleft())
  elif len(A_n) == 0:
    ans_p.append(A_p.popleft())
  elif A_p[0] >= A_n[0]:
    ans_p.append(A_p.popleft())
  else:
    ans_n.append(A_n.popleft())
if len(ans_n) % 2 == 1:
  if len(ans_p) == 0 and len(A_p) > 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_n) == 0 and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
  elif len(ans_p) > 0 and len(ans_n) > 0 and ans_p[-1] >= ans_n[-1] and len(A_p) > 0 and A_p[0] != 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_p) > 0 and len(ans_n) > 0 and ans_p[-1] < ans_n[-1] and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
ans = 1
for a in ans_p:
  ans = (a * ans) % MOD
for a in ans_n:
  ans = (-a * ans) % MOD
if ans != 0 and len(ans_n) % 2 == 1:
  ans = 1
  A_abs = [abs(a) for a in A]
  A_abs.sort()
  for i in range(K):
    ans = (ans * A_abs[i]) % MOD
  ans = (-ans) % MOD
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
plus = [] # 非負数
minus = [] # 負数
c = 0
for i in list(map(int, input().split())):
    c += 1
    if i >= 0:
        plus.append(i)
    else:
        minus.append(i)
plen = len(plus)
mlen = len(minus)
plus.sort(reverse=True)
minus.sort()

# 累積積
pp = [1]
mp = [1]
for p in plus:
    pp.append((pp[-1]*p)%mod)
for m in minus:
    mp.append((mp[-1]*m)%mod)

# 累積積(逆順)
ppm = [1]
mpm = [1]
for p in plus[::-1]:
    ppm.append((ppm[-1]*p)%mod)
for m in minus[::-1]:
    mpm.append((mpm[-1]*m)%mod)

ans = -float("inf")
ans_m = float("inf")
# k個マイナスから選ぶ
for k in range(K+1):
    if mlen < k:
        continue
    if plen < K-k:
        continue
    if k % 2 == 0: # 絶対値最大を目指す
        tmp = mp[k] * pp[K-k]
        tmp %= mod
        ans = max(ans, tmp)
    else: # 絶対値最小を目指す
        tmp = mpm[k] * ppm[K-k]
        tmp %= mod
        ans_m = min(ans_m, tmp)
if ans == -float("inf"):
    ans = ans_m
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ans=set()
ls=sorted(ls, key=lambda x: -abs(x))
mul=1
sign=0
zeroflag=0
flag=[0 for _ in range(N)]
for i in range(K):
  flag[i]=1
  if ls[i]<0:
    sign=(sign+1)%2
if sign==1:
  if 0 in ls:
    zeroflag=1
  else:
    a=[0,0,0,0]
    b=[0,0,0,0]
    for j in range(K,N):
      if ls[j]>0:
        for k in range(K):
          if ls[K-1-k]<0:
            a[0]=ls[j]
            b[0]=j
            a[1]=ls[K-1-k]
            b[1]=K-1-k
            break
        break
    for j in range(K,N):
      if ls[j]<0:
        for k in range(K):
          if ls[K-1-k]>0:
            a[2]=ls[j]
            b[2]=j
            a[3]=ls[K-1-k]
            b[3]=K-1-k
            break
        break
    if a==[0,0,0,0]:
      flag.reverse()
    elif b[0]==0 and b[1]==0:
      flag[b[2]]=1
      flag[b[3]]=0
    elif b[2]==0 and b[3]==0:
      flag[b[0]]=1
      flag[b[1]]=0
    elif abs(a[0]*a[3])>abs(a[1]*a[2]):
      flag[b[0]]=1
      flag[b[1]]=0
    else:
      flag[b[2]]=1
      flag[b[3]]=0
if sign==1 and zeroflag==1:
  print(0)
else:
  mul=1
  for i in range(N):
    if flag[i]==1:
      mul=mul*ls[i]%MOD
  print(mul)

Submission status: Wrong Answer

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

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

A_minus = []
A_plus = []
A_zero_count = 0

for a in A:
    if a > 0:
        A_plus.append(a)
    elif a == 0:
        A_zero_count += 1
    else:
        A_minus.append(a)

A_plus.sort(reverse=True)
A_minus.sort()

MOD = 10 ** 9 + 7


# aの-1乗をmで割ったときの商を求める
def mod_inv(mod_a, m=10 ** 9 + 7):
    b = m
    u = 1
    v = 0
    while b > 0:
        t = mod_a // b
        mod_a -= t * b
        c = mod_a
        mod_a = b
        b = c

        u -= t * v
        c = u
        u = v
        v = c
    u %= m
    return u


def get_all_mul(area):
    ans = 1
    for a_check in area:
        ans = mul(ans, a_check)
    return ans


def mul(mul_a, mul_b):
    return (mul_a * mul_b) % MOD


def solve():
    ans = 1
    if N == K:
        return get_all_mul(A)

    if K + A_zero_count > N:
        return 0

    if len(A_plus) == 0:
        if A_zero_count == 0:
            if K & 1:
                return get_all_mul(A_minus[-K:])
            else:
                return get_all_mul(A_minus[:K])
        else:
            if K & 1:
                return 0
            else:
                return get_all_mul(A_minus[:K])
    elif len(A_minus) == 0:
        return get_all_mul(A_plus[:K])
    else:
        if K + A_zero_count == N:
            if len(A_minus) & 1:
                return 0
            else:
                return mul(get_all_mul(A_minus), get_all_mul(A_plus))

        A_plus.append(0)
        A_minus.append(0)
        plus_choice_num = 0
        minus_choice_num = 0
        last_plus_choice = 0
        last_minus_choice = 0
        for _ in range(K):
            if A_plus[plus_choice_num] > -A_minus[minus_choice_num]:
                ans = mul(ans, A_plus[plus_choice_num])
                last_plus_choice = A_plus[plus_choice_num]
                plus_choice_num += 1
            else:
                ans = mul(ans, A_minus[minus_choice_num])
                last_minus_choice = A_minus[minus_choice_num]
                minus_choice_num += 1
        if minus_choice_num & 1 == 0:
            return ans
        else:
            if last_plus_choice * A_plus[plus_choice_num] >= last_minus_choice * A_minus[minus_choice_num]:
                change = mul(mod_inv(last_minus_choice), A_plus[plus_choice_num])
            else:
                change = mul(mod_inv(last_plus_choice), A_minus[minus_choice_num])
            return mul(ans, change)

print(solve())

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
plus = [] # 非負数
minus = [] # 負数
c = 0
for i in list(map(int, input().split())):
    c += 1
    if i >= 0:
        plus.append(i)
    else:
        minus.append(i)
plen = len(plus)
mlen = len(minus)
plus.sort(reverse=True)
minus.sort()

# 累積積
pp = [1]
mp = [1]
for p in plus:
    pp.append((pp[-1]*p)%mod)
for m in minus:
    mp.append((mp[-1]*m)%mod)

# 累積積(逆順)
ppm = [1]
mpm = [1]
for p in plus[::-1]:
    ppm.append((ppm[-1]*p)%mod)
for m in minus[::-1]:
    mpm.append((mpm[-1]*m)%mod)

ans = -float("inf")
ans_m = -float("inf")
# k個マイナスから選ぶ
for k in range(K+1):
    if mlen < k:
        continue
    if plen < K-k:
        continue
    if k % 2 == 0: # 絶対値最大を目指す
        tmp = mp[k] * pp[K-k]
        tmp %= mod
        ans = max(ans, tmp)
    else: # 絶対値最小を目指す
        tmp = mpm[k] * ppm[K-k]
        tmp %= mod
        ans_m = max(ans_m, tmp)
if ans == -float("inf"):
    ans = ans_m
ans %= mod
print(ans)