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:
#E_Multiplication4
N,K = map(int,input().split())
A = list(map(int,input().split()))
MAX = 200010
MOD = 1000000007
#ソート
arr = []
j = 0
i = 0
seki = 1

#minus_count = len(list(filter(lambda x : (x < 0),A)))

arr = sorted(A,reverse = True)

while (i + j) < K:
    if arr[(N - j -1)] > 0 :
        seki = seki * arr[i] % MOD
        i += 1
    else:
        if arr[i] < 0 :
            if K % 2 == 0:
                seki = seki *  arr[(N - j -1)] % MOD
                j += 1
            else:
                seki = seki * arr[i] % MOD
                i += 1
        else:
            if abs(arr[i]) > abs( arr[(N - j -1)]) :
                seki = seki * arr[i] % MOD
                i += 1
            else:
                seki = seki * abs(arr[(N - j -1)]) % MOD
                j += 1

print(seki)

Submission status: Wrong Answer

Solution code:
from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0:
    if K%2:
        if 0 in A:
            ans = 0
        else:
            ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    else:
        ans = reduce(lambda a, b: a*b%mod, Am[:K], 1)
    print(ans)
    exit()


idx_Am = 0
n = 0
ans = 1
for idx_Ap, ap in enumerate(Ap+[0]):
    while idx_Am < len(Am) and n < K and -Am[idx_Am] > ap:
        ans = ans * Am[idx_Am] % mod
        idx_Am += 1
        n += 1
    if n == K:
        break
    n += 1
    idx_Ap += 1
    ans = ans * ap % mod
    if n == K:
        break
else:
    assert False
if idx_Am % 2 == 0:
    print(ans)
else:
    if idx_Ap == len(Ap) or (idx_Am != len(Am) and Am[idx_Am] * Am[idx_Am-1] > Ap[idx_Ap] * Ap[idx_Ap-1]):
        ans = ans * Am[idx_Am] * pow(Ap[idx_Ap-1], mod-2, mod) % mod
    else:
        ans = ans * Ap[idx_Ap] * pow(Am[idx_Am-1], mod-2, mod) % mod
    print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0 and K%2:
    ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    print(ans)
    exit()
idx_Am = 0
n = 0
ans = 1
for idx_Ap, ap in enumerate(Ap+[0]):
    while idx_Am < len(Am) and n < K and -Am[idx_Am] > ap:
        ans = ans * Am[idx_Am] % mod
        idx_Am += 1
        n += 1
    if n == K:
        break
    n += 1
    idx_Ap += 1
    ans = ans * ap % mod
    if n == K:
        break
else:
    assert False
if idx_Am % 2 == 0:
    print(ans)
else:
    if idx_Ap == len(Ap) or (idx_Am != len(Am) and Am[idx_Am] * Am[idx_Am-1] > Ap[idx_Ap] * Ap[idx_Ap-1]):
        ans = ans * Am[idx_Am] * pow(Ap[idx_Ap-1], mod-2, mod) % mod
    else:
        ans = ans * Ap[idx_Ap] * pow(Am[idx_Am-1], mod-2, mod) % mod
    print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0 and K%2:
    ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    print(ans)
    exit()
idx_Am = 0
n = 0
ans = 1
for idx_Ap, ap in enumerate(Ap+[0]):
    while idx_Am < len(Am) and n < K and -Am[idx_Am] > ap:
        ans = ans * Am[idx_Am] % mod
        idx_Am += 1
        n += 1
    if n == K:
        break
    n += 1
    idx_Ap += 1
    ans = ans * ap % mod
    if n == K:
        break
else:
    assert False
if idx_Am % 2 == 0:
    print(ans)
else:
    if idx_Ap == len(Ap) or (idx_Am != len(Am) and -Am[idx_Am] / Ap[idx_Ap-1] > Ap[idx_Ap] / -Am[idx_Am-1]):
        ans = ans * Am[idx_Am] * pow(Ap[idx_Ap-1], mod-2, mod) % mod
    else:
        ans = ans * Ap[idx_Ap] * pow(Am[idx_Am-1], mod-2, mod) % mod
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import collections
import math

"""
#### 入力例 ####
N, X = map(int, input().split())

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

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
"""

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

def main():
    ans = 1
    A.sort(reverse=True)
    if N == K:
        for n in range(N):
            ans*=A[n]
        print(ans % mod)
        return
    
    M = collections.deque()
    P = collections.deque()
    for n in range(N):
        if A[n] < 0:
            M.append(A[n])
        else:
            P.append(A[n])

    if len(P) == 0:
        if(K%2 != 0):
            for k in range(K):
                ans *= M.popleft()
            print(ans % mod)
            return
        else:
            for k in range(K):
                ans *= M.pop()
            print(ans%mod)
            return
    
    if K % 2 == 1:
        ans *= P.popleft()
    
    p_stock = 0
    m_stock = 0
    M = list(M)
    print(M)
    P = list(P)
    idx_p = 0
    idx_m = 0
    for k in range(0, K//2, 2):
        if  len(M)-1 <= idx_m:
            ans *= P[idx_p] * P[idx_p +1 ]
            idx_p += 2
            
        elif len(P)-1 <= idx_p:
            ans *= M[idx_m] * M[idx_m + 1]  
            idx_m += 2
        elif idx_m < len(M)-1 and idx_p < len(P) -1:
            m_stock = M[idx_m] * M[idx_m + 1] 
            p_stcok = P[idx_p] * P[idx_p + 1]
            if m_stock < p_stcok:
                ans *= p_stock
                idx_p += 2
            else:
                ans *= m_stock
                idx_m += 2
        else:
            break

    print(ans%mod)
    return
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import bisect
import copy
import collections
import heapq
import itertools
import math
import numpy as np
from operator import itemgetter
import scipy.misc
import sys

"""
#### 入力例 ####
N, X = map(int, input().split())

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

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
"""

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

def main():
    ans = 1
    A.sort(reverse=True)
    if N == K:
        for n in range(N):
            ans*=A[n]
        print(ans % mod)
        return
    
    M = collections.deque()
    P = collections.deque()
    for n in range(N):
        if A[n] < 0:
            M.append(A[n])
        else:
            P.append(A[n])

    if len(P) == 0:
        if(K%2 != 0):
            for k in range(K):
                ans *= M.popleft()
            print(ans % mod)
            return
        else:
            for k in range(K):
                ans *= M.pop()
            print(ans%mod)
            return
    
    if K % 2 == 1:
        ans *= P.popleft()
    
    p_stock = 0
    m_stock = 0
    M = list(M)
    M.sort()
    P = list(P)
    idx_p = 0
    idx_m = 0
    for k in range(0, K//2, 2):
        if  len(M)-1 <= idx_m:
            ans *= P[idx_p] * P[idx_p +1 ]
            idx_p += 2
            
        elif len(P)-1 <= idx_p:
            ans *= M[idx_m] * M[idx_m + 1]  
            idx_m += 2
        elif idx_m < len(M)-1 and idx_p < len(P) -1:
            m_stock = M[idx_m] * M[idx_m + 1] 
            p_stcok = P[idx_p] * P[idx_p + 1]
            if m_stock < p_stcok:
                ans *= p_stock
                idx_p += 2
            else:
                ans *= m_stock
                idx_m += 2
        else:
            break

    print(ans%mod)
    return
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
p= 10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
right = list()
left = list()
for x in a:
  if x > 0:
    right.append(x)
  else:
    left.append(x)

right.sort(reverse=True)
if len(right)==0:
  #0以下の数だけ
  left.sort(reverse=k%2)
  left_r = k
  right_r = 0
elif len(left)==0:
  #正の数だけ
  left_r = 0
  right_r = k
else:
  # 両方が1個以上ある場合は必ず0以上にできる
  # 偶数個のときはrightを偶数に、奇数のときは奇数個にする
  left.sort()
  left_r = 0
  right_r = 0
  while left_r + right_r < k:
    if k - left_r - right_r == 1:
      if right_r < len(right):
        right_r += 1
      else:
        left_r += 1
      break
    if left_r < len(left) - 1 and right_r < len(right) - 1:
      if left[left_r]*left[left_r+1] > right[right_r]*right[right_r]:
        left_r += 2
      else:
        right_r += 1
    elif left_r < len(left) - 1:
      left_r += 2
    elif right_r < len(right) - 1:
      right_r += 1
    else:
      left_r += 1
      right_r += 1

ans = 1
for i in range(right_r):
  ans = (ans * right[i]) % p
for i in range(left_r):
  ans = (ans * left[i]) % p
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
p= 10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort(key=lambda x:abs(x))
ans = 1
left_min = 0
right_min = 10**9 
for i in range(k):
  ans = ans * a[i] % p
  if left_min < a[i] < 0:
    left_min = a[i]
  elif 0 < a[i] < right_min:
    right_min = a[i]
if ans >= 0:
  print(ans)
  sys.exit()

left_max = 0
right_max = -1
for i in range(k+1, n):
  if a[i] < left_max:
    left_max = a[i]
  elif right_max < a[i]:
    right_max = a[i]
  if left_max > 0 and right_max > -1:
    break
if left_min==0 or right_max < 0:
  ans = ans // right_min * left_max % p
elif right_min==10**9 or left_max ==0:
  ans = ans // left_min * right_max % p
else:
  ans = max(ans // right_min * left_max, ans // left_min * right_max)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
p= 10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
right = list()
left = list()
for x in a:
  if x > 0:
    right.append(x)
  else:
    left.append(x)

right.sort(reverse=True)
if len(right)==0:
  #0以下の数だけ
  left.sort(reverse=k%2)
  left_r = k
  right_r = 0
elif len(left)==0:
  #正の数だけ
  left_r = 0
  right_r = k
else:
  # 両方が1個以上ある場合は必ず0以上にできる
  # 偶数個のときはrightを偶数に、奇数のときは奇数個にする
  left.sort()
  left_r = 0
  right_r = 0
  while left_r + right_r < k:
    if k - left_r - right_r == 1:
      if right_r < len(right):
        right_r += 1
      else:
        left_r += 1
      break
    if left_r < len(left) - 1 and right_r < len(right) - 1:
      if left[left_r]*left[left_r+1] > right[right_r]*right[right_r]:
        left_r += 2
      else:
        right_r += 2
    elif left_r < len(left) - 1:
      left_r += 2
    elif right_r < len(right) - 1:
      right_r += 2
    else:
      left_r += 1
      right_r += 1

ans = 1
for i in range(right_r):
  ans = (ans * right[i]) % p
for i in range(left_r):
  ans = (ans * left[i]) % p
print(ans)

Submission status: Wrong Answer

Solution code:
# from itertools import accumulate as acc

MOD = 10**9 + 7

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

A.sort()

plus_list = []
minus_list = []

zero_count = 0
for a in A:
    # print(a)
    if a > 0:
        plus_list.append(a)
    elif a < 0:
        minus_list.append(a)
    else:
        zero_count += 1

plus_list.sort()
minus_list.sort()

# def solve():
#     # FIX: 大小を比べる方法 or 比べずに解決できる方法
#     plus_list_reverse_acc = [1]
#     for a in plus_list[::-1]:
#         plus_list_reverse_acc.append(
#             (plus_list_reverse_acc[-1] * a) % MOD
#         )
#     minus_list_acc = [1]
#     for a in minus_list:
#         minus_list_acc.append(
#             (minus_list_acc[-1] * a) % MOD
#         )
#     # print(plus_list_reverse_acc, minus_list_acc)
#     r = -(10**18)
#     for minus_count in range(0, K+1, 2):
#         if not (0 <= minus_count <= len(minus_list)):
#             continue
#         plus_count = K-minus_count
#         if not (0 <= plus_count <= len(plus_list)):
#             continue
#         x = (minus_list_acc[minus_count] * plus_list_reverse_acc[plus_count]) % MOD
#         r = max(r, x)
#     return r

def solve():
    # print("A")
    r = 1
    minus_list_reverse = reversed(minus_list)
    minus_pair_list = []
    for i in range(0, len(minus_list), 2):
        if i+1 < len(minus_list):
            x = minus_list[i] * minus_list[i+1]
            minus_pair_list.append(x)
    minus_pair_list.reverse()
    # print(plus_list, minus_pair_list)
    q_num = 1
    q_len = 0
    while q_len < K:
        if len(minus_pair_list) == 0 or ((len(plus_list) >= 2) and (plus_list[-2]*plus_list[-1] >= minus_pair_list[-1])) or q_len + 1 == K:
            # print("{P")
            q_num = (q_num * plus_list.pop()) % MOD
            q_len += 1
            # print(q_len)
        else:
            # print("P")
            q_num = (q_num * minus_pair_list.pop())
            q_len += 2
    return q_num

if plus_list and (not minus_list):
    # print("plus")
    if len(plus_list) < K:
        r = 0
    else:
        r = 1
        for a in plus_list[-K:]:
            # print(r*a)
            r = (r * a) % MOD
        # print(A[-K:], r)
elif (not plus_list) and minus_list:
    # print("minus")
    if K%2 == 1:
        if zero_count:
            r = 0
        else:
            r = 1
            for a in minus_list[-K:]:
                r = (r * a) % MOD
    else:
        if len(minus_list) < K:
            r = 0
        else:
            r = 1
            for a in minus_list[:K]:
                r = (r * a) % MOD
elif (not plus_list) and (not minus_list):
    # print("zero")
    r = 0
else:
    # print("plus minus zero")
    # 2要素以上
    if K == N:
        r = (zero_count == 0)
        for a in plus_list:
            r = (r * a) % MOD
        for a in minus_list:
            r = (r * a) % MOD
    else:
        # K <= N-1:
        # print(zero_count)
        if zero_count:
            # 3要素以上
            if K > N-zero_count:
                r = 0
            elif K == N-zero_count:
                if len(minus_list)%2 == 1:
                    r = 0
                else:
                    r = 1
                    for a in plus_list:
                        r = (r * a) % MOD
                    for a in minus_list:
                        r = (r * a) % MOD
            else:
                r = solve()
        else:
            # 2要素以上 
            r = solve()

print(r)

Submission status: Wrong Answer

Solution code:
# from itertools import accumulate as acc

MOD = 10**9 + 7

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

A.sort()

plus_list = []
minus_list = []

zero_count = 0
for a in A:
    # print(a)
    if a > 0:
        plus_list.append(a)
    elif a < 0:
        minus_list.append(a)
    else:
        zero_count += 1

plus_list.sort()
minus_list.sort()

def solve():
    plus_list_reverse_acc = [1]
    for a in plus_list[::-1]:
        plus_list_reverse_acc.append(
            (plus_list_reverse_acc[-1] * a) % MOD
        )
    minus_list_acc = [1]
    for a in minus_list:
        minus_list_acc.append(
            (minus_list_acc[-1] * a) % MOD
        )
    # print(plus_list_reverse_acc, minus_list_acc)
    r = -(10**18)
    for minus_count in range(0, K+1, 2):
        if minus_count > len(minus_list):
            continue
        plus_count = K-minus_count
        if plus_count > len(plus_list):
            continue
        x = (minus_list_acc[minus_count] * plus_list_reverse_acc[plus_count]) % MOD
        r = max(r, x)
    return r

if plus_list and (not minus_list):
    # print("plus")
    if len(plus_list) < K:
        r = 0
    else:
        r = 1
        for a in plus_list[-K:]:
            # print(r*a)
            r = (r * a) % MOD
        # print(A[-K:], r)
elif (not plus_list) and minus_list:
    # print("minus")
    if K%2 == 1:
        if zero_count:
            r = 0
        else:
            r = 1
            for a in minus_list[-K:]:
                r = (r * a) % MOD
    else:
        if len(minus_list) < K:
            r = 0
        else:
            r = 1
            for a in minus_list[:K]:
                r = (r * a) % MOD
elif (not plus_list) and (not minus_list):
    # print("zero")
    r = 0
else:
    # print("plus minus zero")
    # 2要素以上
    if K == N:
        r = (zero_count == 0)
        for a in plus_list:
            r = (r * a) % MOD
        for a in minus_list:
            r = (r * a) % MOD
    else:
        # K <= N-1:
        # print(zero_count)
        if zero_count:
            # 3要素以上
            if K > N-zero_count:
                r = 0
            elif K == N-zero_count:
                if len(minus_list)%2 == 1:
                    r = 0
                else:
                    r = 1
                    for a in plus_list:
                        r = (r * a) % MOD
                    for a in minus_list:
                        r = (r * a) % MOD
            else:
                r = solve()
        else:
            # 2要素以上 
            r = solve()

print(r)

Submission status: Wrong Answer

Solution code:
# from itertools import accumulate as acc

MOD = 10**9 + 7

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

A.sort()

plus_list = []
minus_list = []

zero_count = 0
for a in A:
    # print(a)
    if a > 0:
        plus_list.append(a)
    elif a < 0:
        minus_list.append(a)
    else:
        zero_count += 1

plus_list.sort()
minus_list.sort()

def solve():
    plus_list_reverse_acc = [1]
    for a in plus_list[::-1]:
        plus_list_reverse_acc.append(
            (plus_list_reverse_acc[-1] * a) % MOD
        )
    minus_list_acc = [1]
    for a in minus_list:
        minus_list_acc.append(
            (minus_list_acc[-1] * a) % MOD
        )
    # print(plus_list_reverse_acc, minus_list_acc)
    r = -(10**18)
    for minus_count in range(0, K+1, 2):
        if minus_count > len(minus_list):
            continue
        plus_count = K-minus_count
        if plus_count > len(plus_list):
            continue
        x = (minus_list_acc[minus_count] * plus_list_reverse_acc[plus_count]) % MOD
        r = max(r, x)
    return r

if plus_list and (not minus_list):
    # print("plus")
    r = 1
    for a in plus_list[-K:]:
        r = (r * a) % MOD
elif (not plus_list) and minus_list:
    # print("minus")
    if K%2 == 1:
        if zero_count:
            r = 0
        else:
            r = 1
            for a in minus_list[-K:]:
                r = (r * a) % MOD
    else:
        r = 1
        for a in minus_list[:K]:
            r = (r * a) % MOD
elif (not plus_list) and (not minus_list):
    # print("zero")
    r = 0
else:
    # print("plus minus zero")
    # 2要素以上
    if K == N:
        r = (zero_count == 0)
        for a in plus_list:
            r = (r * a) % MOD
        for a in minus_list:
            r = (r * a) % MOD
    else:
        # K <= N-1:
        # print(zero_count)
        if zero_count:
            # 3要素以上
            if K > N-zero_count:
                r = 0
            elif K == N-zero_count:
                if len(minus_list)%2 == 1:
                    r = 0
                else:
                    r = 1
                    for a in plus_list:
                        r = (r * a) % MOD
                    for a in minus_list:
                        r = (r * a) % MOD
            else:
                r = solve()
        else:
            # 2要素以上 
            r = solve()

print(r)

Submission status: Wrong Answer

Solution code:
#E_Multiplication4
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 1000000007
#ソート
arr = []
j = 0
i = 0
seki = 1

minus_count = len(list(filter(lambda x : (x < 0),A)))
arr = sorted(A,reverse = True)
while (i + j) < K:
    if arr[(N - j -1)] > 0 :
        seki = seki * arr[i] % MOD
        i += 1
    else:
        if arr[i] < 0 :
            if K % 2 == 0:
                seki = seki *  arr[(N - j -1)] % MOD
                j += 1
            else:
                seki = seki * arr[i] % MOD
                i += 1
        else:
            if (K - i - j > 2 and minus_count > 2):
                if abs(arr[i]) > abs( arr[(N - j -1)]) :
                    seki = seki * arr[i] % MOD
                    i += 1
                else:
                    seki = seki * abs(arr[(N - j -1)]) % MOD
                    j += 1
                    minus_count -= 1
            else:
                if (j % 2 == 0):
                    if abs(arr[(N - j -1)] * arr[(N - j -2)]) > arr[i] * arr[i + 1]:
                        seki = seki * abs(arr[(N - j -1)] * arr[(N - j -2)]) % MOD
                        j += 2
                    else:
                        seki = seki * arr[i] * arr[i + 1]
                        i += 2
                else:
                    seki = seki * abs(arr[(N - j -1)]) * arr[i] % MOD
                    j += 2
                    i += 1

print(seki)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    A = list(map(int, input().split()))
    B = [(abs(x), x) for x in A]
    B.sort(reverse=True)
    plus = []
    minus = []

    ans = 1

    if N == K:
        for x in A:
            ans *= x
            ans %= mod
        print(ans)
        return
    minus_count = 0
    for i in range(K):
        if B[i][-1] < 0:
            minus_count += 1
            minus.append(B[i][-1])
        else:
            plus.append(B[i][-1])
        ans *= B[i][-1]
        ans %= mod

    if minus_count % 2 == 0:
        print(ans)
        return

    else:
        if len(plus) > 0 and len(minus) > 0:
            S = 1
            for i in range(len(plus)-1):
                S *= plus[i]
                S %= mod
            for i in range(len(minus)-1):
                S *= minus[i]
                S %= mod
            plus_sub = -1
            minus_sub = -1
            for i in range(K, N):
                if B[i][-1] >= 0:
                    plus_sub = B[i][-1]*plus[-1]
                    break
            for i in range(K, N):
                if B[i][-1] < 0:
                    minus_sub = B[i][-1]*minus[-1]
            print(S*max(plus_sub, minus_sub) % mod)
            return

        else:
            for i in range(K, N):
                if B[i][-1] >= 0:
                    minus.append(B[i][-1])
                    break
            if minus[-1] >= 0:
                res = 1
                for i in range(K-1):
                    res *= minus[i]
                    res %= mod
                res *= minus[-1]
                print(res % mod)
                return
            else:
                A.sort(reverse=True)
                res = 1
                for i in range(K):
                    res *= A[i]
                    res %= mod
                print(res)
                return


main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    A = list(map(int, input().split()))
    B = [(abs(x), x) for x in A]
    B.sort(reverse=True)

    ans = 1

    if N == K:
        for x in A:
            ans *= x
            ans %= mod
        print(ans)
        return

    minus_count = 0

    for i in range(K):
        if B[i][-1] <= 0:
            minus_count += 1
        ans *= B[i][0]
        ans %= mod

    if minus_count % 2 == 0:
        print(ans)
        return

    else:
        if minus_count == K:
            # all<0
            sub_data = 1
            for i in range(K-1):
                sub_data *= B[i][-1]
                sub_data %= mod
            V = B[K-1][-1]
            for i in range(K, N):
                if B[i][-1] > 0:
                    print(sub_data*B[i][-1] % mod)
                    return
            ##ok 
            if K % 2 != 0:
                A.sort(reverse=True)
                ans = 1
                for i in range(K):
                    ans *= A[i]
                    ans %= mod
                print(ans)
                return

            elif K % 2 == 0:
                A.sort()
                ans = 1
                for i in range(K):
                    ans *= A[i]
                    ans %= mod
                print(ans)
                return

        else:
            plus_count = K-minus_count
            plus = []
            minus = []
            for i in range(K):
                if B[i][-1] > 0:
                    plus.append(B[i][-1])
                else:
                    minus.append(B[i][-1])
            if B[K][-1] > 0:
                res = 1
                for i in range(plus_count):
                    res *= plus[i]
                    res %= mod
                for i in range(minus_count-1):
                    res *= minus[i]
                    res %= mod
                res *= B[K][-1]
                print(res % mod)
                return

            elif B[K][-1] <= 0:
                res = 1
                for i in range(plus_count-1):
                    res *= plus[i]
                    res %= mod

                for i in range(minus_count):
                    res *= minus[i]
                    res %= mod

                res *= B[K][-1]
                print(res % mod)
                return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    A = list(map(int, input().split()))
    B = [(abs(x), x) for x in A]
    B.sort(reverse=True)

    ans = 1

    if N == K:
        for x in A:
            ans *= x
            ans %= mod
        print(ans)
        return

    minus_count = 0

    for i in range(K):
        if B[i][-1] < 0:
            minus_count += 1
        ans *= B[i][0]
        ans %= mod

    if minus_count % 2 == 0:
        print(ans)
        return

    else:
        if minus_count == K:
            # all<0
            sub_data = 1
            for i in range(K-1):
                sub_data *= B[i][-1]
                sub_data %= mod
            V = B[K-1][-1]
            for i in range(K, N):
                if B[i][-1] >= 0:
                    print(sub_data*B[i][-1] % mod)
                    return
            print(pow(10,100000000000000))
            if K % 2 != 0:
                A.sort(reverse=True)
                ans = 1
                for i in range(K):
                    ans *= A[i]
                    ans %= mod
                print(ans)
                return

            elif K % 2 == 0:
                A.sort()
                ans = 1
                for i in range(K):
                    ans *= A[i]
                    ans %= mod
                print(ans)
                return

        else:
            plus_count = K-minus_count
            plus = []
            minus = []
            for i in range(K):
                if B[i][-1] >= 0:
                    plus.append(B[i][-1])
                else:
                    minus.append(B[i][-1])
            if B[K][-1] >= 0:
                res = 1
                for i in range(plus_count):
                    res *= plus[i]
                    res %= mod
                for i in range(minus_count-1):
                    res *= minus[i]
                    res %= mod
                res *= B[K][-1]
                print(res % mod)
                return

            elif B[K][-1] < 0:
                res = 1
                for i in range(plus_count-1):
                    res *= plus[i]
                    res %= mod

                for i in range(minus_count):
                    res *= minus[i]
                    res %= mod

                res *= B[K][-1]
                print(res % mod)
                return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    A = list(map(int, input().split()))
    B = [(abs(x), x) for x in A]
    B.sort(reverse=True)

    ans = 1

    if N == K:
        for x in A:
            ans *= x
            ans %= mod
        print(ans)
        return

    minus_count = 0

    for i in range(K):
        if B[i][-1] < 0:
            minus_count += 1
        ans *= B[i][0]
        ans %= mod

    if minus_count % 2 == 0:
        print(ans)
        return

    else:
        if minus_count == K:
            # all<0
            sub_data = 1
            for i in range(K-1):
                sub_data *= B[i][-1]
                sub_data %= mod
            V = B[K-1][-1]
            for i in range(K, N):
                if B[i][-1] >= 0:
                    print(sub_data*B[i][-1] % mod)
                    return
            if K % 2 != 0:
                A.sort(reverse=True)
                ans = 1
                for i in range(K):
                    ans *= A[i]
                    ans %= mod
                print(ans)
                return

            elif K % 2 == 0:
                A.sort()
                ans = 1
                for i in range(K):
                    ans *= A[i]
                    ans %= mod
                print(ans)
                return

        else:
            plus_count = K-minus_count
            plus = []
            minus = []
            for i in range(K):
                if B[i][-1] >= 0:
                    plus.append(B[i][-1])
                else:
                    minus.append(B[i][-1])
            if B[K][-1] >= 0:
                res = 1
                for i in range(plus_count):
                    res *= plus[i]
                    res %= mod
                for i in range(minus_count-1):
                    res *= minus[i]
                    res %= mod
                res *= B[K][-1]
                print(res % mod)
                return

            elif B[K][-1] < 0:
                res = 1
                for i in range(plus_count-1):
                    res *= plus[i]
                    res %= mod

                for i in range(minus_count):
                    res *= minus[i]
                    res %= mod

                res *= B[K][-1]
                print(res % mod)
                return


if __name__ == "__main__":
    main()