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 heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

if len(M)%2 ==1:
    M.pop(-1)

else:
    while i < K-1:
        if(len(P)>=2 and len(M)>=2):
            i +=2
            if(P[0]*P[1]<=M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] <= M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
                i += 1
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
            i += 1
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*heapq.heappop(M)%mod

print(ans2)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

if len(P)%2 ==1:
    P.pop(-1)

else:
    while i < K-1:
        if(len(P)>=2 and len(M)>=2):
            i +=2
            if(P[0]*P[1]<=M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] <= M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
                i += 1
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
            i += 1
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*heapq.heappop(M)%mod

print(ans2)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        if(len(P)>=2 and len(M)>=2):
            i +=2
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] < M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
                i += 1
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
            i += 1
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*heapq.heappop(M)%mod

print(ans2)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        if(len(P)>=2 and len(M)>=2):
            i +=2
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] < M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
                i += 1
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 2
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
            i += 1
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*M[0]%mod



print(ans2)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        i += 1
        if(len(P)>=2 and len(M)>=2):
            i +=1
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] < M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
    while i < K:
        i += 1
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod


print(ans2)

Submission status: Wrong Answer

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if len(zero) + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    for k in range(K):
      ans = ans * minus[- k - 1] % mod
    ans = -1 * ans % mod  
    print(ans)
    exit()
  else:
    for k in range(K):
      ans = ans * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  ans = 1
  for k in range(mp):
    ans = ans * plus[k] % mod
  for k in range(mm):
    ans = ans * minus[k] % mod
  print(ans)
  exit()

if m%2 == 0:
  main(p, m, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(p-1, m, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(p, m, plus, minus, mod, K)
  elif m == lm:
    main(p, m-1, plus, minus, mod, K)
  elif p == 0:
    main(p, m-1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      main(p, m-1, plus, minus, mod, K)
    else:
      main(p-1, m, plus, minus, mod, K)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        i += 1
        if(len(P)>=2 and len(M)>=2):
            i +=1
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] < M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
    if i < K:
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod


print(ans2)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        i += 1
        if(len(P)>=2 and len(M)>=2):
            i +=1
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==1:
            if len(M)>=2 and -P[0] < M[0]*M[1]:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
    if i < K:
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*M[0]%mod


print(ans2)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        i += 1
        if(len(P)>=2 and len(M)>=2):
            i +=1
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
        elif len(M)<=1:
            ans2 = -ans2*heapq.heappop(P)%mod
    if i < K:
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*M[0]%mod


print(ans2)

Submission status: Wrong Answer

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

mod = 10 ** 9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)
lp = len(plus)
lm = len(minus)

if len(zero) + K > N:
  print(0)
  exit()
elif lp == 0: 
  if K % 2 == 1:
    for k in range(K):
      ans = ans * minus[- k - 1] % mod
    ans = -1 * ans % mod  
    print(ans)
    exit()
  else:
    for k in range(K):
      ans = ans * minus[k] % mod
    print(ans)
    exit()
elif lm == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == lp:
      m = K - p  
      break
  else:
    m += 1
    if m == lm:
      p = K - m
      break

def main(mp, mm, plus, minus, mod, K):
  p = 0
  m = 0
  ans = 1
  if mp == 0:
    for _ in range(K):
      ans = ans * minus[_] % mod
  elif mm == 0:
    for _ in range(K):
      ans = ans * plus[_] % mod
  else:
    for _ in range(K):
      if plus[p] >= minus[m]:
        ans = ans * plus[p] % mod
        p += 1
        if p == mp:
          for j in range(K - p - m):
            ans = ans * minus[m + j] % mod
          break
      else:
        ans = ans * minus[m] % mod
        m += 1
        if m == mm:
          for j in range(K - p - m):
            ans = ans * plus[p + j] % mod
          break  
  print(ans)
  exit()

if m%2 == 0:
  main(lp, lm, plus, minus, mod, K)
else:
  if p == lp:
    if m != lm:
      main(lp-1, lm, plus, minus, mod, K)
    else:
      if len(zero) > 0:
        print(0)
        exit()
      else:
        main(lp, lm, plus, minus, mod, K)
  elif m == lm:
    main(lp, lm-1, plus, minus, mod, K)
  elif p == 0:
    main(lp, lm-1, plus, minus, mod, K)
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      main(lp, lm-1, plus, minus, mod, K)
    else:
      main(lp-1, lm, plus, minus, mod, K)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K:
        i += 1
        if(len(P)>=2 and len(M)>=2):
            i +=1
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
            else:
                ans2 =  ans2*heapq.heappop(M)%mod
        elif len(M)==0:
            ans2 = -ans2*heapq.heappop(P)%mod
        elif len(M)==1 and len(P)==1:
            ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==1:
            if(P[0]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i +=1
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(M)==1:
            ans2 = -ans2*heapq.heappop(P)%mod
    if i < K:
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*M[0]%mod


print(ans2)

Submission status: Wrong Answer

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0

if len(P)==0 and K%2 == 1:
    for i in range(len(M)-K,len(M)):
        ans2 = ans2 * M[i] % mod 

else:
    while i < K-1:
        i += 1
        if(len(P)>=2 and len(M)>=2):
            i +=1
            if(P[0]*P[1]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            else:
                ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
        elif len(P)==0:
            if len(M)>=2:
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i += 1
            else:
                ans2 =  ans2*heapq.heappop(M)%mod
        elif len(M)==0:
            ans2 = -ans2*heapq.heappop(P)%mod
        elif len(M)==1 and len(P)==1:
            ans2 = -ans2*heapq.heappop(P)%mod
        elif len(P)==1:
            if(P[0]<M[0]*M[1]):
                ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
                i +=1
            else:
                ans2 = -ans2*heapq.heappop(P)%mod
        elif len(M)==1:
            ans2 = -ans2*heapq.heappop(P)%mod
    if i < K:
        if len(P)>=1:
            ans2 = -ans2*heapq.heappop(P)%mod
        else:
            ans2 = ans2*M[0]%mod


print(ans2)

Submission status: Wrong Answer

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

mod = 10**9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)


if len(zero) + K > N:
  print(0)
  #print('l23')
  exit()

if len(plus) == 0 and K % 2 == 1:
  for k in range(K):
    ans = ans * minus[-k-1] % mod
  ans = -1 * ans % mod  
  print(ans)
  #print('l31')
  exit()

if len(plus) == 0 and K % 2 == 0:
  for k in range(K):
    ans = ans * minus[k] % mod
  print(ans)
  #print('l38')
  exit()

if len(minus) == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  #print('l45')
  exit()


p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    p += 1
    if p == len(plus):
      m = K - p  
      break
  else:
    m += 1
    if m == len(minus):
      p = K - m
      break  




def main(mp, mm, A, mod, K):
  p = 0
  m = 0
  ans = 1
  for k in range(K):
    if plus[p] >= minus[m]:
      ans = ans * plus[p] % mod
      p += 1
      if p == mp:
        for j in range(K - p - m):
          ans = ans * minus[m + j] % mod
        m = K - p  
        break
    else:
      ans = ans * minus[m] % mod
      m += 1
      if m == mm:
        for j in range(K - p - m):
          ans = ans * plus[p + j] % mod
        p = K - m
        break  
  print(ans)



if m%2 == 0:
  main(len(plus), len(minus), A, mod, K)
  #print('l93')
else:
  if p == len(plus) and m != len(minus):
    main(len(plus)-1, len(minus), A, mod, K)
    #print('l97')
    exit()
  elif p == len(plus) and m == len(minus):
    if len(zero) > 0:
      print(0)
      #print('l102')
    else:
      main(len(plus), len(minus), A, mod, K)
      #print('l105')
    exit()
  elif p != len(plus) and m == len(minus):
    main(len(plus), len(minus)-1, A, mod, K)
    #print('l109')
    exit()
  elif p == 0:
    main(len(plus), len(minus)-1, A, mod, K)
    #print('l113')
    exit()
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      main(len(plus), len(minus)-1, A, mod, K)
      #print('l118')
      exit()
    else:
      main(len(plus)-1, len(minus), A, mod, K)
      #print('l122')
      exit()

Submission status: Wrong Answer

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

mod = 10**9 + 7
plus = []
zero = []
minus = []
ans = 1

for k in range(N):
  if A[k] > 0:
    plus.append(A[k])
  elif A[k] < 0:
    minus.append(-1 * A[k])
  else:
    zero.append(A[k])
plus.sort(reverse = True)
minus.sort(reverse = True)


if len(zero) + K > N:
  print(0)
  exit()

if len(plus) == 0 and K % 2 == 1:
  for k in range(K):
    ans = ans * minus[-k-1] % mod
  ans = -1 * ans % mod  
  print(ans)
  exit()

if len(plus) == 0 and K % 2 == 0:
  for k in range(K):
    ans = ans * minus[k] % mod
  print(ans)
  exit()

if len(minus) == 0:
  for k in range(K):
    ans = ans * plus[k] % mod
  print(ans)
  exit()

p = 0
m = 0
for k in range(K):
  if plus[p] >= minus[m]:
    ans = ans * plus[p] % mod
    p += 1
    if p == len(plus):
      for j in range(K - p - m):
        ans = ans * minus[m + j] % mod
      m = K - p  
      break
  else:
    ans = ans * minus[m] % mod
    m += 1
    if m == len(minus):
      for j in range(K - p - m):
        ans = ans * plus[p + j] % mod
      p = K - m
      break  

if m%2 == 0:
  print(ans)
else:
  if p == len(plus) and m != len(minus):
    ans = ans / plus[p-1] % mod
    ans = ans * minus[m] % mod
    print(ans)
    exit()
  elif p == len(plus) and m == len(minus):
    if len(zero) > 0:
      print(0)
    else:
      print(ans)
    exit()
  elif p != len(plus) and m == len(minus):
    ans = ans / minus[m - 1] % mod
    ans = ans * plus[p] % mod
    print(ans)
    exit()
  elif p == 0:
    ans = ans / minus[m-1] % mod
    ans = ans * plus[p] % mod
    print(ans)
    exit()
  else:
    if plus[p] * plus[p-1] > minus[m-1] * minus[m]:
      ans = ans / minus[m-1] % mod
      ans = ans * plus[p] % mod
      print(ans)
      exit()
    else:
      ans = ans / plus[p-1] % mod
      ans = ans * minus[m] % mod
      print(ans)
      exit()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    A = LI()
    MOD = 1000000007
    
    B = []
    plus = 0
    minus = 0
    zero = 0
    for a in A:
        if a > 0:
            plus += 1
        elif a < 0:
            minus += 1
        else:
            zero += 1
        B.append((abs(a), a))

    # 正にできるかどうか
    def can_plus():
        if plus > 0:
            if N == K:
                if minus % 2 == 0:
                    return True
                else:
                    return False
            else:
                return True
        else:
            if K % 2 == 0:
                return True
            else:
                return False

    if can_plus():
        B = sorted(B, key=lambda x: x[0], reverse=True)
        ans = 1
        min_plus = INF
        min_minus = INF
        j = 0
        for i in range(K):
            b = B[i][1]
            if b >= 0:
                min_plus = min(min_plus, b)
            else:
                min_minus = min(min_minus, b)
            ans = ans * b
            j = i

        if ans >= 0:
            print(ans % MOD)
        else:
            for i in range(j+1, N):
                b = B[i][1]
                if b >= 0:
                    # minus -> plus
                    ans = ans // min_minus * b
                    print(ans % MOD)
                    return
                else:
                    # plus -> minus
                    if min_plus == INF:
                        continue
                    else:
                        ans = ans // min_plus * b
                        print(ans % MOD)
                        return

    else:
        # 絶対値が小さい順に選ぶ
        B = sorted(B, key=lambda x: x[0])
        ans = 1
        for i in range(K):
            ans = ans * B[i][1]
        print(ans % MOD)
        return





if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

A_p = []
A_m = []
for a in A:
  if a > 0:
    A_p.append(a)
  else:
    break
for a in A[::-1]:
  if a > 0:
    break
  A_m.append(a)

MOD = 10 ** 9 + 7
def modmul(a, b):
  return a % MOD * (b % MOD) % MOD

cnt = 0
i_m = 0
i_p = 0

a = 1
if k == n:
  for b in A:
    a = modmul(a, b)
  k = 0
if k > len(A_p) and (k - len(A_p)) % 2 != 0:
  A_m = A_m[::-1]
  A_p = A_p[::-1]
  while k != 0:
    if len(A_p) - i_p > 0 and len(A_m) - i_m > 0:
      if abs(A_p[i_p]) < abs(A_m[i_m]):
        a = modmul(A_m[i_m], a)
        i_m += 1
      else:
        a = modmul(A_p[i_p], a)
        i_p += 1
    elif len(A_p) - i_p == 0:
      a = modmul(A_m[i_m], a)
      i_m += 1
    else:
      a = modmul(A_p[i_p], a)
      i_p += 1
    k -= 1
while k != 0:
  if k > 1:
    m = -1
    if len(A_m) - i_m > 1:
      m = A_m[i_m] * A_m[i_m+1]
    p = -1
    if len(A_p) - i_p > 1:
      p = A_p[i_p] * A_p[i_p+1]
  
    if len(A_p) - i_p > 1 and len(A_m) - i_m > 1:
      if m >= p:
        a = modmul(modmul(a, A_m[i_m]), A_m[i_m+1])
        i_m += 2
        k -= 2
      else:
        a = modmul(a, A_p[i_p])
        i_p += 1
        k -= 1
      
    elif len(A_p) - i_p < 2 and len(A_m) - i_m > 1:
      a = modmul(modmul(a, A_m[i_m]), A_m[i_m+1])
      i_m += 2
      k -= 2
  
    elif len(A_p) -i_p > 0 and len(A_m) - i_m < 2:
      a = modmul(a, A_p[i_p])
      i_p += 1
      k -= 1
  
  else:
    if len(A_p) - i_p > 0:
      a = modmul(a, A_p[i_p])
      k = 0

print(a)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

A_p = []
A_m = []
for a in A:
  if a > 0:
    A_p.append(a)
  else:
    break
for a in A[::-1]:
  if a > 0:
    break
  A_m.append(a)

MOD = 10 ** 9 + 7
def modmul(a, b):
  return a % MOD * (b % MOD) % MOD

cnt = 0
i_m = 0
i_p = 0

a = 1
if k > len(A_p) and (k - len(A_p)) % 2 != 0:
  A_m = A_m[::-1]
  A_p = A_p[::-1]
  while k != 0:
    if len(A_p) - i_p > 0 and len(A_m) - i_m > 0:
      if abs(A_p[i_p]) < abs(A_m[i_m]):
        a = modmul(A_m[i_m], a)
        i_m += 1
      else:
        a = modmul(A_p[i_p], a)
        i_p += 1
    elif len(A_p) - i_p == 0:
      a = modmul(A_m[i_m], a)
      i_m += 1
    else:
      a = modmul(A_p[i_p], a)
      i_p += 1
    k -= 1
while k != 0:
  if k > 1:
    m = -1
    if len(A_m) - i_m > 1:
      m = A_m[i_m] * A_m[i_m+1]
    p = -1
    if len(A_p) - i_p > 1:
      p = A_p[i_p] * A_p[i_p+1]
  
    if len(A_p) - i_p > 1 and len(A_m) - i_m > 1:
      if m >= p:
        a = modmul(modmul(a, A_m[i_m]), A_m[i_m+1])
        i_m += 2
        k -= 2
      else:
        a = modmul(a, A_p[i_p])
        i_p += 1
        k -= 1
      
    elif len(A_p) - i_p < 2 and len(A_m) - i_m > 1:
      a = modmul(modmul(a, A_m[i_m]), A_m[i_m+1])
      i_m += 2
      k -= 2
  
    elif len(A_p) -i_p > 0 and len(A_m) - i_m < 2:
      a = modmul(a, A_p[i_p])
      i_p += 1
      k -= 1
  
  else:
    if len(A_p) - i_p > 0:
      a = modmul(a, A_p[i_p])
      k = 0

print(a)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

A_p = []
A_m = []
for a in A:
  if a > 0:
    A_p.append(a)
  else:
    break
for a in A[::-1]:
  if a > 0:
    break
  A_m.append(a)

MOD = 10 ** 9 + 7
def modmul(a, b):
  return a % MOD * (b % MOD) % MOD

cnt = 0
i_m = 0
i_p = 0

a = 1
if k > len(A_p) and (k - len(A_p)) % 2 != 0:
  A_m = A_m[::-1]
  A_p = A_p[::-1]
  while k != 0:
    if len(A_p) - i_p > 0 and len(A_m) - i_m > 0:
      if abs(A_p[i_p]) < abs(A_m[i_m]):
        a = modmul(A_m[i_m], a)
        i_m += 1
      else:
        a = modmul(A_p[i_p], a)
        i_p += 1
    elif len(A_p) - i_p == 0:
      a = modmul(A_m[i_m], a)
      i_m += 1
    else:
      a = modmul(A_p[i_p], a)
      i_p += 1
    k -= 1
while k != 0:
  if k > 1:
    m = -1
    if len(A_m) - i_m > 1:
      m = A_m[i_m] * A_m[i_m+1]
    p = -1
    if len(A_p) - i_p > 1:
      p = A_p[i_p] * A_p[i_p+1]
  
    if len(A_p) - i_p > 1 and len(A_m) - i_m > 1:
      if m >= p:
        a = modmul(modmul(a, A_m[i_m]), A_m[i_m+1])
        i_m += 2
        k -= 2
      else:
        a = modmul(a, A_p[i_p])
        i_p += 1
        k -= 1
      
    elif len(A_p) - i_p < 2 and len(A_m) - i_m > 1:
      a = modmul(modmul(a, A_m[i_m]), A_m[i_m+1])
      i_m += 2
      k -= 2
  
    elif len(A_p) -i_p > 0 and len(A_m) - i_m < 2:
      a = modmul(a, A_p[i_p])
      i_p += 1
      k -= 1
    
    else:
      a = modmul(a, A_m[i_m])
      i_m += 1
      k -= 1
  
  else:
    if len(A_p) - i_p > 0:
      a = modmul(a, A_p[i_p])
      k = 0
    else:
      a = modmul(a,A_m[i_m])
      k = 0

print(a)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

A_p = []
A_m = []
for a in A:
  if a > 0:
    A_p.append(a)
  else:
    break
for a in A[::-1]:
  if a > 0:
    break
  A_m.append(a)

MOD = 10 ** 9 + 7
def modmul(a, b):
  return a % MOD * (b % MOD) % MOD

cnt = 0
i_m = 0
i_p = 0

a = 1
if k > len(A_p) and (k - len(A_p)) % 2 != 0:
  A_m = A_m[::-1]
  A_p = A_p[::-1]
  while k != 0:
    if len(A_p) - i_p > 0 and len(A_m) - i_m > 0:
      if abs(A_p[i_p]) < abs(A_m[i_m]):
        a = modmul(A_m[i_m], a)
        i_m += 1
      else:
        a = modmul(A_p[i_p], a)
        i_p += 1
    elif len(A_p) - i_p == 0:
      a = modmul(A_m[i_m], a)
      i_m += 1
    else:
      a = modmul(A_p[i_p], a)
      i_p += 1
    k -= 1
while k != 0:
  if k > 1:
    m = -1
    if len(A_m) - i_m > 1:
      m = A_m[i_m] * A_m[i_m+1]
    p = -1
    if len(A_p) - i_p > 1:
      p = A_p[i_p] * A_p[i_p+1]
  
    if len(A_p) - i_p > 1 and len(A_m) - i_m > 1:
      if m >= p:
        a = modmul(a, m%MOD)
        i_m += 2
        k -= 2
      else:
        a = modmul(a, A_p[i_p])
        i_p += 1
        k -= 1
      
    elif len(A_p) - i_p < 2 and len(A_m) - i_m > 1:
      a = modmul(modmul(a, A_m[i_m]), A_m[i_m+1])
      i_m += 2
      k -= 2
  
    elif len(A_p) -i_p > 0 and len(A_m) - i_m < 2:
      a = modmul(a, A_p[i_p])
      i_p += 1
      k -= 1
    
    else:
      a = modmul(a, A_m[i_m])
      i_m += 1
      k -= 1
  
  else:
    if len(A_p) - i_p > 0:
      a = modmul(a, A_p[i_p])
      k -= 1
    else:
      a = modmul(a,A_m[i_m])
      k -= 1

print(a)