Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

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

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

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

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

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

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

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

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

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

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

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

Sample Input 4

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

Sample Output 4

999983200

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



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
import bisect
N ,K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
mod = 10 ** 9 + 7
  
# ans = minus
plus = bisect.bisect_right(A, 0)
minus = bisect.bisect_left(A, 0) 
if N == K:
  ans = 1
  for i in range(N):
    ans *= A[i]
    ans %= mod
  print(ans % mod)
  quit()
  
if (minus == N) and (K % 2 == 1):
  ans = 1
  for i in range(1, K + 1):
    ans *= A[-i]
    ans %= mod
  print(ans % mod)
  quit()
  
ans = 1

count = 0
i = 0
j = -1
while count < K:
  if K - count >= 2:
    fo = A[i] * A[i + 1]
    re = A[j] * A[j - 1]
    #print(fo, re)
    if fo >= re:
      ans *= (fo % mod) 
      ans %= mod
      i += 2
    elif (A[j - 1] <= 0) or (A[j - 2] <= 0):
      if (K % 2 == 0):
        ans *= (re % mod)
        ans %= mod
        j -= 2
      else:  
        ans *= (fo % mod) 
        ans %= mod
        i += 2      
    else:
      ans *= (re % mod)
      ans %= mod
      j -= 2
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

Submission status: Wrong Answer

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
    print(cnt)
else:
    while k > 0:
        if k == 1:
            if len(pla) > 0:
                cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) <= 1:
            cnt = cnt * mia.pop() % mod
            k -= 1
        elif len(mia) <= 1:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
    else:
        print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int, input().split())
A = list(map(int, input().split()))
APlus = []
AMinus = []

#プラスの要素のリストとマイナスの要素のリストに振り分ける
for i in A:
    if 0 < i:
        #[要素,カウントする数]
        APlus.append([i,1])
    else:
        AMinus.append([i,1])

#バックアップを取る
APlusBackup = APlus[:]
AMinusBackup = AMinus[:]
undoValue = []
undoValue1 = []
undoValue2 = []
answerList = []

#2つのマイナスの要素の積をプラスのリスト移行する
while 1 <= len(AMinus) / 2:
    temp1 = AMinus.pop(0)[0]
    temp2 = AMinus.pop(0)[0]
    temp3 = temp1 * temp2
    #[要素,カウントする数]
    APlus.append([temp3,2])
    undoValue.append(temp3)
    undoValue1.append(temp1)
    undoValue2.append(temp2)

#降順に並び替える
APlus = sorted(APlus, reverse = True)
AMinus = sorted(AMinus, reverse = True)

APlusLen = 0
#要素の数ではなくカウント数の合計を求める
for i in APlus:
    APlusLen += i[1]

AMinusLen = 0
for i in AMinus:
    AMinusLen += i[1]

if K <= APlusLen:
    answer = 1
    count = 0
    while count < K:
        temp = APlus.pop(0)
        value = temp[0]
        point = temp[1]
        #2回カウント可能か判定
        if count + point <= K:
            answer *= value
            count += point
        else:
            index = undoValue.index(value)
            temp1 = undoValue1[index]
            temp2 = undoValue2[index]
            if temp2 <= temp1:
                answer *= temp1
                count += 1
            else:
                answer *= temp2
                count += 1
    answerList.append(answer)

answer = 1
count = 0
APlus = sorted(APlusBackup[:])
AMinus = sorted(AMinusBackup[:])
while count < K:
    if 0 < len(APlus):
        temp = APlus.pop(0)
        value = temp[0]
        point = temp[1]
        answer *= value
        count += point
    elif 0 < len(AMinus):
        temp = AMinus.pop(0)
        value = temp[0]
        point = temp[1]
        answer *= value
        count += point
answerList.append(answer)

if 0 < K - len(APlus) and (K - len(APlus)) % 2 == 1:
    AAbsolute = sorted(np.abs(A))
    answer = 1
    count = 0
    while count < K:
        answer *= AAbsolute.pop(0)
        count += 1
    answerList.append(-answer)

print(max(answerList) % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int, input().split())
A = list(map(int, input().split()))
APlus = []
AMinus = []

#プラスの要素のリストとマイナスの要素のリストに振り分ける
for i in A:
    if 0 < i:
        #[要素,カウントする数]
        APlus.append([i,1])
    else:
        AMinus.append([i,1])

#バックアップを取る
APlusBackup = APlus[:]
AMinusBackup = AMinus[:]
undoValue = []
undoValue1 = []
undoValue2 = []
answerList = []

#2つのマイナスの要素の積をプラスのリスト移行する
while 1 <= len(AMinus) / 2:
    temp1 = AMinus.pop(0)[0]
    temp2 = AMinus.pop(0)[0]
    temp3 = temp1 * temp2
    #[要素,カウントする数]
    APlus.append([temp3,2])
    undoValue.append(temp3)
    undoValue1.append(temp1)
    undoValue2.append(temp2)

#降順に並び替える
APlus = sorted(APlus, reverse = True)
AMinus = sorted(AMinus, reverse = True)

APlusLen = 0
#要素の数ではなくカウント数の合計を求める
for i in APlus:
    APlusLen += i[1]

AMinusLen = 0
for i in AMinus:
    AMinusLen += i[1]

if K <= APlusLen:
    answer = 1
    count = 0
    while count < K:
        temp = APlus.pop(0)
        value = temp[0]
        point = temp[1]
        #2回カウント可能か判定
        if count + point <= K:
            answer *= value
            count += point
        else:
            index = undoValue.index(value)
            temp1 = undoValue1[index]
            temp2 = undoValue2[index]
            if temp2 <= temp1:
                answer *= temp1
                count += 1
            else:
                answer *= temp2
                count += 1
    answerList.append(answer)

answer = 1
count = 0
APlus = sorted(APlusBackup[:])
AMinus = sorted(AMinusBackup[:])
while count < K:
    if 0 < len(APlus):
        temp = APlus.pop(0)
        value = temp[0]
        point = temp[1]
        answer *= value
        count += point
    elif 0 < len(AMinus):
        temp = AMinus.pop(0)
        value = temp[0]
        point = temp[1]
        answer *= value
        count += point
answerList.append(answer)

if 0 < K - len(APlus) and (K - len(APlus) % 2 == 1):
    AAbsolute = sorted(np.abs(A))
    answer = 1
    count = 0
    while count < K:
        answer *= AAbsolute.pop(0)
        count += 1
    answerList.append(-answer)
    
print(max(answerList) % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
n,k,*a=map(int,open(0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
i=0
while k>1:
 x=a[i]*a[i+1]
 if x*b>a[-1]*a[-2]*b:s*=x;i+=2
 else:x=p()*p()
 s=s*x%(10**9+7);k-=2
print(s)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def main():
  N, K = map(int , input().split())
  A = list(map(int, input().split()))
  
  if max(A) < 0 and K % 2 == 1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
      ans = ans*A[i]%MOD
    print(ans%MOD)
  elif K == N:
    ans = 1
    for i in A:
      ans = ans*i%MOD
    print(ans%MOD)
  else:
    A_p = []
    A_m = []
    for i in A:
      if i >= 0:A_p.append(i)
      else:A_m.append(abs(i))
    A_p.sort(reverse =  True)
    A_m.sort(reverse = True)
    num = 0
    ans = 1
    posi_p = 0
    posi_m = 0
    sign = 0
    while (num < K):
      if posi_m == len(A_m) and posi_p < len(A_p):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1
      elif posi_p == len(A_p) and posi_m < len(A_m):
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1        
      elif  A_p[posi_p] >= abs(A_m[posi_m]):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1        
      else:
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1
      if num == K and sign % 2 == 1:
        if K == 1:
          ans = A_p[0]
        elif posi_m == len(A_m):
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD) % MOD
          ans = ans*A_p[posi_p] % MOD
        elif posi_p == len(A_p):
          ans = ans*pow(A_p[posi_p-1],  MOD-2, MOD)
          ans =  ans*A_m[posi_m] % MOD
        elif A_p[posi_p]*A_p[posi_p-1] >= A_m[posi_m]*A_m[posi_m-1]:
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
          ans = ans*A_p[posi_p] % MOD
        else:
          ans = ans*pow(A_p[posi_p-1], MOD-2, MOD)%MOD
          ans = ans*A_m[posi_m]%MOD
    print(ans%MOD)
          
    
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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
    print(cnt)
else:
    while k > 0:
        if k == 1:
            if len(pla) == 0:
                cnt = cnt * mia[0] % mod
            elif len(pla) > 0:
                cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) <= 1:
            cnt = cnt * mia.pop() % mod
            k -= 1
        elif len(mia) <= 1:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
    else:
        print(cnt)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def main():
  N, K = map(int , input().split())
  A = list(map(int, input().split()))
  
  if max(A) < 0 and K % 2 == 1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
      ans = ans*A[i]%MOD
    print(ans%MOD)
  elif K == N:
    ans = 1
    for i in A:
      ans = ans*i%MOD
    print(ans%MOD)
  else:
    A_p = []
    A_m = []
    for i in A:
      if i >= 0:A_p.append(i)
      else:A_m.append(abs(i))
    A_p.sort(reverse =  True)
    A_m.sort(reverse = True)
    num = 0
    ans = 1
    posi_p = 0
    posi_m = 0
    sign = 0
    while (num < K):
      if posi_m == len(A_m) and posi_p < len(A_p):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1
      elif posi_p == len(A_p) and posi_m < len(A_m):
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1        
      elif  A_p[posi_p] >= abs(A_m[posi_m]):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1        
      else:
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1
      if num == K and sign % 2 == 1:
        if K == 1:
          ans = A_p[0]
        elif posi_m == len(A_m):
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD) % MOD
          ans = ans*A_p[posi_p] % MOD
        elif posi_p == len(A_p):
          ans = ans*pow(A_p[posi_p-1],  MOD-2, MOD)
          ans =  ans*A_m[posi_m] % MOD
        elif A_p[posi_p]*A_p[posi_p-1] >= A_m[posi_m]*A_m[posi_m-1]:
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
          ans = ans*A_p[posi_p] % MOD
        else:
          ans = ans*pow(A_p[posi_p-1], MOD-2, MOD)%MOD
          ans = ans*A_m[posi_m]%MOD
    if ans < 0:
      ans += MOD
    print(ans%MOD)
          
    
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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
    print(cnt)
else:
    while k > 0:
        if k == 1:
            if len(pla) == 0:
                cnt = cnt * mia[0] % mod
            elif len(pla) > 0:
                cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) <= 1:
            cnt = cnt * mia.pop() % mod
            k -= 1
        elif len(mia) <= 1:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif len(pla) >= 2 and len(mia) >= 2:
            if pla[-1] * pla[-2] >= mia[-1] * mia[-2]:
                cnt = cnt * pla.pop() % mod
                k -= 1
            elif pla[-1] * pla[-2] < mia[-1] * mia[-2]:
                cnt = cnt * mia.pop() * mia.pop() % mod
                k -= 2
    else:
        print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int, input().split())
A = list(map(int, input().split()))
APlus = []
AMinus = []

#プラスの要素のリストとマイナスの要素のリストに振り分ける
for i in A:
    if 0 < i:
        #[要素,カウントする数]
        APlus.append([i,1])
    else:
        AMinus.append([i,1])

#バックアップを取る
APlusBackup = APlus[:]
AMinusBackup = AMinus[:]
undoValue = []
undoValue1 = []
undoValue2 = []
answerList = []

#2つのマイナスの要素の積をプラスのリスト移行する
while 1 <= len(AMinus) / 2:
    temp1 = AMinus.pop(0)[0]
    temp2 = AMinus.pop(0)[0]
    temp3 = temp1 * temp2
    #[要素,カウントする数]
    APlus.append([temp3,2])
    undoValue.append(temp3)
    undoValue1.append(temp1)
    undoValue2.append(temp2)

#降順に並び替える
APlus = sorted(APlus, reverse = True)
AMinus = sorted(AMinus, reverse = True)

APlusLen = 0
#要素の数ではなくカウント数の合計を求める
for i in APlus:
    APlusLen += i[1]

AMinusLen = 0
for i in AMinus:
    AMinusLen += i[1]

if K <= APlusLen:
    answer = 1
    count = 0
    while count < K:
        temp = APlus.pop(0)
        value = temp[0]
        point = temp[1]
        #2回カウント可能か判定
        if count + point <= K:
            answer *= value
            count += point
        else:
            index = undoValue.index(value)
            temp1 = undoValue1[index]
            temp2 = undoValue2[index]
            if temp2 <= temp1:
                answer *= temp1
                count += 1
            else:
                answer *= temp2
                count += 1
    answerList.append(answer)

answer = 1
count = 0
APlus = sorted(APlusBackup[:])
AMinus = sorted(AMinusBackup[:])
while count < K:
    if 0 < len(APlus):
        temp = APlus.pop(0)
        value = temp[0]
        point = temp[1]
        answer *= value
        count += point
    elif 0 < len(AMinus):
        temp = AMinus.pop(0)
        value = temp[0]
        point = temp[1]
        answer *= value
        count += point
answerList.append(answer)

AAbsolute = sorted(np.abs(A))
answer = 1
count = 0
while count < K:
    answer *= AAbsolute.pop(0)
    count += 1
answerList.append(-answer)
    
print(max(answerList) % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def main():
  N, K = map(int , input().split())
  A = list(map(int, input().split()))
  
  if max(A) < 0 and K % 2 == 1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
      ans = ans*A[i]%MOD
    print(ans%MOD)
  elif K == N:
    ans = 1
    for i in A:
      ans = ans*i%MOD
    print(ans%MOD)
  else:
    A_p = []
    A_m = []
    for i in A:
      if i >= 0:A_p.append(i)
      else:A_m.append(abs(i))
    A_p.sort(reverse =  True)
    A_m.sort(reverse = True)
    num = 0
    ans = 1
    posi_p = 0
    posi_m = 0
    sign = 0
    while (num < K):
      if posi_m == len(A_m) and posi_p < len(A_p):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1
      elif posi_p == len(A_p) and posi_m < len(A_m):
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1        
      elif  A_p[posi_p] >= abs(A_m[posi_m]):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1        
      else:
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1
      if num == K and sign % 2 == 1:
        if posi_m == len(A_m):
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD) % MOD
          ans = ans*A_p[posi_p] % MOD
        elif posi_p == len(A_p):
          ans = ans*pow(A_p[posi_p-1],  MOD-2, MOD)
          ans =  ans*A_m[posi_m] % MOD
        elif A_p[posi_p]*A_p[posi_p-1] >= A_m[posi_m]*A_m[posi_m-1]:
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
          ans = ans*A_p[posi_p] % MOD
        else:
          ans = ans*pow(A_p[posi_p-1], MOD-2, MOD)%MOD
          ans = ans*A_m[posi_m]%MOD
    if ans < 0:
      ans += MOD
    print(ans%MOD)
          
    
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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
while k > 0:
    if k == 1:
        if len(pla) == 0:
            cnt = cnt * mia[0] % mod
        elif len(pla) > 0:
            cnt = cnt * pla.pop() % mod
        k -= 1
    elif len(pla) == 0:
        cnt = cnt * mia.pop() % mod
        k -= 1
    elif len(mia) <= 1:
        cnt = cnt * pla.pop() % mod
        k -= 1
    elif len(pla) == 1:
        if (k % 2 == 1) or (k % 2 == 0 and len(mia) == 1):
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif k % 2 == 0 and len(mia) >= 2:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
    elif len(pla) >= 2 and len(mia) >= 2:
        if pla[-1] * pla[-2] >= mia[-1] * mia[-2]:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif pla[-1] * pla[-2] < mia[-1] * mia[-2]:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()
print(mia)

cnt = 1
while k > 0:
    if k == 1:
        if len(pla) == 0:
            cnt = cnt * mia[0] % mod
        elif len(pla) > 0:
            cnt = cnt * pla.pop() % mod
        k -= 1
    elif len(pla) == 0:
        cnt = cnt * mia.pop() % mod
        k -= 1
    elif len(mia) <= 1:
        cnt = cnt * pla.pop() % mod
        k -= 1
    elif len(pla) == 1:
        if (k % 2 == 1) or (k % 2 == 0 and len(mia) == 1):
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif k % 2 == 0 and len(mia) >= 2:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
    elif len(pla) >= 2 and len(mia) >= 2:
        if pla[-1] * pla[-2] >= mia[-1] * mia[-2]:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif pla[-1] * pla[-2] < mia[-1] * mia[-2]:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def main():
  N, K = map(int , input().split())
  A = list(map(int, input().split()))
  
  if max(A) < 0 and K % 2 == 1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
      ans = ans*A[i]%MOD
    print(ans%MOD)
  elif K == N:
    ans = 1
    for i in A:
      ans = ans*i%MOD
    print(ans%MOD)
  else:
    A_p = []
    A_m = []
    for i in A:
      if i >= 0:A_p.append(i)
      else:A_m.append(abs(i))
    A_p.sort(reverse =  True)
    A_m.sort()
    num = 0
    ans = 1
    posi_p = 0
    posi_m = 0
    sign = 0
    while (num < K):
      if posi_m == len(A_m) and posi_p < len(A_p):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1
      elif posi_p == len(A_p) and posi_m < len(A_m):
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1        
      elif  A_p[posi_p] >= abs(A_m[posi_m]):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1        
      else:
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1
      if num == K and sign % 2 == 1:
        if posi_m == len(A_m):
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD) % MOD
          ans = ans*A_p[posi_p] % MOD
        elif posi_p == len(A_p):
          ans = ans*pow(A_p[posi_p-1],  MOD-2, MOD)
          ans =  ans*A_m[posi_m] % MOD
        elif A_p[posi_p]*A_p[posi_p-1] >= A_m[posi_m]*A_m[posi_m-1]:
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
          ans = ans*A_p[posi_p] % MOD
        else:
          ans = ans*pow(A_p[posi_p-1], MOD-2, MOD)%MOD
          ans = ans*A_m[posi_m]%MOD
    if ans < 0:
      ans += MOD
    print(ans%MOD)
          
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def main():
  N, K = map(int , input().split())
  A = list(map(int, input().split()))
  
  if max(A) < 0 and K % 2 == 1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
      ans = ans*A[i]%MOD
    print(ans%MOD)
  elif K == N:
    ans = 1
    for i in A:
      ans = ans*i%MOD
    print(ans%MOD)
  else:
    A_p = []
    A_m = []
    for i in A:
      if i >= 0:A_p.append(i)
      else:A_m.append(i)
    A_p.sort(reverse =  True)
    A_m.sort()
    num = 0
    ans = 1
    posi_p = 0
    posi_m = 0
    sign = 0
    while (num < K):
      if posi_m == len(A_m) and posi_p < len(A_p):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1
      elif posi_p == len(A_p) and posi_m < len(A_m):
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1        
      elif  A_p[posi_p] >= abs(A_m[posi_m]):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1        
      else:
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1
      if num == K and sign % 2 == 1:
        if posi_m == len(A_m):
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD) % MOD
          ans = ans*A_p[posi_p] % MOD
        elif posi_p == len(A_p):
          ans = ans*pow(A_p[posi_p-1],  MOD-2, MOD)
          ans =  ans*A_m[posi_m] % MOD
        elif A_p[posi_p]*A_p[posi_p-1] >= A_m[posi_m]*A_m[posi_m-1]:
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
          ans = ans*A_p[posi_p] % MOD
        else:
          ans = ans*pow(A_p[posi_p-1], MOD-2, MOD)%MOD
          ans = ans*A_m[posi_m]%MOD
    if ans <0:
      ans += MOD
    print(ans%MOD)
          
    
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

mia, pla = [], []
for ai in a:
    if ai < 0:
        mia.append(ai)
    elif ai >= 0:
        pla.append(ai)
mia.sort(reverse=True)
pla.sort()

cnt = 1
while k > 0:
    if len(pla) == 0:
        cnt = cnt * mia.pop() % mod
        k -= 1
    elif len(mia) <= 1 or k == 1:
        cnt = cnt * pla.pop() % mod
        k -= 1
    elif len(pla) == 1:
        if k % 2 == 1:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif k % 2 == 0 and len(mia) >= 2:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
        elif k % 2 == 0 and len(mia) == 1:
            cnt = cnt * pla.pop() % mod
            k -= 1
    elif len(pla) >= 2 and len(mia) >= 2:
        if pla[-1] * pla[-2] >= mia[-1] * mia[-2]:
            cnt = cnt * pla.pop() % mod
            k -= 1
        elif pla[-1] * pla[-2] < mia[-1] * mia[-2]:
            cnt = cnt * mia.pop() * mia.pop() % mod
            k -= 2
else:
    print(cnt)

Submission status: Wrong Answer

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

# case1. N == K のときは答えは確定
if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
    exit()

# case2. A が全部負の数のとき、 Kが奇数ならば残念ながら答えは負になるのでなるべく絶対値を小さくする
if max(A) < 0 and K%2 == 1:
    ans = 1
    A = sorted(A, reverse=True)
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
    exit()

# case3. それ以外は、負の数は基本的に2つセットで選ばれることに注意
# まずは候補テーブルを作成
A = sorted(A, reverse=True)
A_cost1 = []  # positive 要素
A_cost2 = []  # negative 要素を大きい順に 2 つセットにしたもの
tmp = 1
for a in A:
    if a >= 0:
        A_cost1.append(a)
    else:
        if tmp != 1:
            A_cost2.append(tmp*a)
            tmp = 1
        else:
            tmp *= a
A_cost1 = sorted(A_cost1, reverse=True)
A_cost2 = sorted(A_cost2, reverse=True)

cost = 0
ans = 1
while (cost < K):
    if K - cost >= 2:
        # まだ cost2 から入れる余地がある
        if A_cost2 and A_cost1 and A_cost2[0] >= A_cost1[0]:
            res = A_cost2.pop(0)
            ans *= res
            ans %= MOD
            cost += 2
        elif A_cost2:
            res = A_cost2.pop(0)
            ans *= res
            ans %= MOD
            cost += 2
        else:
            res = A_cost1.pop(0)
            ans *= res
            ans %= MOD
            cost += 1
    else:
        res = A_cost1.pop(0)
        ans *= res
        ans %= MOD
        cost += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
    for i in range(k):
        ans *= a_list[n - 1 - i]
        ans %= mod
else:
    l = 0
    r = -1
    mlt1 = a_list[0] * a_list[1]
    mlt2 = a_list[-2] * a_list[-1]
    for _ in range(0, k // 2):
        if mlt1 >= mlt2:
            ans *= mlt1 % mod
            l += 2
            if l <= n - 2:
                mlt1 = a_list[l + 1] * a_list[l]
        else:
            ans *= mlt2 % mod
            r -= 2
            if r >= - n + 1:
                mlt2 = a_list[r - 1] * a_list[r]
        ans %= mod

    if k % 2 == 1:
        ans *= a_list[r]
        ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def main():
  N, K = map(int , input().split())
  A = list(map(int, input().split()))
  
  if max(A) < 0 and K % 2 == 1:
    A.sort(reverse = True)
    ans = 1
    for i in range(K):
      ans = ans*A[i]%MOD
    print(ans)
  elif K == N:
    ans = 1
    for i in A:
      ans = ans*i%MOD
    print(ans)
  else:
    A_p = []
    A_m = []
    for i in A:
      if i >= 0:A_p.append(i)
      else:A_m.append(i)
    A_p.sort(reverse =  True)
    A_m.sort()
    num = 0
    ans = 1
    posi_p = 0
    posi_m = 0
    sign = 0
    while (num < K):
      if posi_m == len(A_m) and posi_p < len(A_p):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1
      elif posi_p == len(A_p) and posi_m < len(A_m):
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1        
      elif  A_p[posi_p] >= abs(A_m[posi_m]):
        ans = ans*A_p[posi_p]%MOD
        posi_p += 1
        num += 1        
      else:
        ans = ans*A_m[posi_m]%MOD
        sign += 1
        posi_m += 1
        num += 1
      if num == K and sign % 2 == 1:
        if posi_m == len(A_m):
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD) % MOD
          ans = ans*A_p[posi_p] % MOD
        elif posi_p == len(A_p):
          ans = ans*pow(A_p[posi_p-1],  MOD-2, MOD)
          ans =  ans*A_m[posi_m] % MOD
        elif A_p[posi_p]*A_p[posi_p-1] >= A_m[posi_m]*A[posi_m-1]:
          ans = ans*pow(A_m[posi_m-1], MOD-2, MOD)%MOD
          ans = ans*A_p[posi_p] % MOD
        else:
          ans = ans*pow(A_p[posi_p-1], MOD-2, MOD)%MOD
          ans = ans*A_m[posi_m]%MOD
    if ans <0:
      ans += MOD
    print(ans%MOD)
          
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
from collections import deque

a = list(map(int, input().split()))
a.sort()
minus, zero, plus = 0, 0, 0
for i in range(n):
    if a[i] < 0:
        minus += 1
    elif a[i] == 0:
        zero += 1
    else:
        plus += 1

que = deque(a)

#ここを軽量化した
plus_flg = False
tmp = plus - k
if tmp >= 0:
    plus_flg = True
elif (-tmp <= minus and -tmp%2 == 0) or (-tmp < minus and plus >= 1):
    plus_flg = True

# plus可能
if plus_flg:
    ans = 1
    cnt = 0

    while cnt < k:
        if k - cnt >= 2:
            cnt += 2
            if que[0] * que[1] >= que[-1] * que[-2]:
                ans *= que.popleft()
                ans *= que.popleft()
                ans %= mod
                cnt += 2
            else:
                ans *= que.pop()
                ans %= mod
                cnt += 1
        else:
            ans *= que.pop()
            ans %= mod
            cnt += 1

    print(ans)



# zero
elif zero > 0:
    print(0)

# minus
else:
    a = [abs(a[i]) for i in range(n)]
    a.sort()
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    ans = -ans % mod
    print(ans)