Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

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

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

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

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

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

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

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

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

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

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

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

Sample Input 4

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

Sample Output 4

999983200

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



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and sum([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max/negative_big_max < negative_small_min/positive_big_min:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9+7
a1 = []
a2 = []
cnt = 0
for i in a:
    if (i >= 0):
        a1.append(i)
    else:
        a2.append(-i)
a1.sort()
a2.sort()
#print(a1,a2)
if (k==1):
    print(max(a)%mod)
    exit()
if (n==k):
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if (len(a1)==0):
    if (k%2==0):
        ans = 1
        for i in range(k):
            ans *= a2.pop()
            ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= -a2[i]
            ans %= mod
        print(ans)
        exit()
elif (len(a2)==0):
    ans = 1
    for i in range(k):
        ans *= a1.pop()
        ans %= mod
    print(ans)
    exit()

bef1 = 10**10
bef2 = 10**10
index1 = 0
index2 = 0
ans = 1
for i in range(k):
    if (len(a1)==0):
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        bef2 = x
        continue
    if (len(a2)==0 or a1[-1]>=a2[-1]):
        x = a1.pop()
        ans *= x
        ans %= mod
        index1 += 1
        bef1 = x
    else:
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        bef2 = x
if (cnt%2==1):
    if len(a1)>0 and len(a2)>0:
        if (index1==0):
            ans *= a1[-1]
            ans *= pow(bef2,mod-2,mod)
            ans %= mod
        elif (index2==0):
            ans *= a2[-1]
            ans *= pow(bef1,mod-2,mod)
            ans %= mod
        else:
            A = a1[-1]/bef2
            B = a2[-1]/bef1
            if (A>=B):
                ans *= a1[-1]
                ans *= pow(bef2,mod-2,mod)
                ans %= mod
            else:
                ans *= a2[-1]
                ans *= pow(bef1,mod-2,mod)
                ans %= mod
    elif (len(a1)==0):
        ans *= a2[-1]
        ans *= pow(bef1,mod-2,mod)
        ans %= mod
    else:
        ans *= a1[-1]
        ans *= pow(bef2,mod-2,mod)
        ans %= mod
if 0 in a:
    print(max(0,ans%mod))
else:
    print(ans%mod)

Submission status: Wrong Answer

Solution code:
from math import ceil
from collections import defaultdict as dd
import sys
input=sys.stdin.readline
#t=int(input())
#while t:
n,k=map(int,input().split())
positive=[]
negative=[]
zero=[]
mod=10**9+7
l=list(map(int,input().split()))
l.sort(reverse=True)
for i in range(n):
    if(l[i]>0):
        positive.append(l[i])
    elif(l[i]==0):
        zero.append(0)
    else:
        negative.append(l[i])
positive.sort()
negative.sort(reverse=True)
com=[]
for i in range(len(negative)-1,0,-2):
    com.append(abs(negative[i]))
    com.append(abs(negative[i-1]))
com.reverse()
#print(com)
lp=len(positive)
ln=len(negative)
lc=len(com)
lz=len(zero)
mul=1
if(k%2==0):
    i=lp-1
    j=lc-1
    while(k and j>0 and i>0):
        if(com[j]*com[j-1]>positive[i]*positive[i-1]):
            mul=(mul*com[j]*com[j-1])%mod
            j-=2
        else:
            mul=(mul*positive[i]*positive[i-1])%mod
            i-=2
        k-=2
    
    while (k and i>0):
        mul=(mul*positive[i]*positive[i-1])%mod
        i-=2
        k-=2
    #print(k,j)
    while(k and j>0):
        mul=(mul*com[j]*com[j-1])%mod
        j-=2
        k-=2
        #print(j,"lol")
    #print(k)
    #print(k)
    while k and i>=0:
        mul=(mul*positive[i])%mod
        i-=1
        k-=1
    #print(k)
    if(k):
        mul=0
else:
    i=lp-1
    j=lc-1
    if(positive):
        mul=positive.pop()
        i-=1
        k-=1
        while(k and j>0 and i>0):
            if(com[j]*com[j-1]>positive[i]*positive[i-1]):
                mul=(mul*com[j]*com[j-1])%mod
                j-=2
            else:
                mul=(mul*positive[i]*positive[i-1])%mod
                i-=2
            k-=2
        while (k and i>0):
            mul=(mul*positive[i]*positive[i-1])%mod
            i-=2
            k-=2
        while(k and j>0):
            mul=(mul*com[j]*com[j-1])%mod
            j-=2
            k-=2
        while k and i>=0:
            mul=(mul*positive[i])%mod
            i-=1
            k-=1
        #print(k)
        if(k):
            mul=0
    else:
        mul=1
        kk=k
        if(lz):
            mul=0
        else:
            for i in range(min(k,ln)):
                #print(negative[i])
                mul=((mul%mod)*((negative[i]+mod)%mod))%mod
                kk-=1
            if(kk):
                mul=0
print(mul)

Submission status: Wrong Answer

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

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

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

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

flag = 0

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = -1
ip = -1
cp = 0
mod = 10 ** 9 + 7

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans) # ok
    else:
        ans = 1
        cnt = 0
        f = 0
        for i, ai in enumerate(a):
            if cnt == k:
                f = 2
                break
            if i == im:
                f = 1
                continue
            if f == 1 and ai <= 0:
                continue
            ans *= abs(ai)
            ans %= mod
            # print(i, ai)
            cnt += 1
        if f == 2:
            print(ans)
        else:
            ans = 1
            cnt = 0
            f = 0
            for i, ai in enumerate(a):
                if cnt == k:
                    f = 2
                    break
                if i == ip:
                    f = 1
                    continue
                if f == 1 and ai >= 0:
                    continue
                ans *= abs(ai)
                ans %= mod
                # print(i, ai)
                cnt += 1
            if f == 2:
                print(ans) # ok
            else:
                ans = 1
                a.sort(reverse=True)
                for i, ai in enumerate(a):
                    if i == k:
                        break
                    ans *= ai
                    ans %= mod
                print(ans) # ok

else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= abs(ai)
        ans %= mod
    print(ans) # ok

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
a = list(map(int,readline().split()))
mod = 10**9+7

p = []
P = 0
z = False
t = 0
for i in a:
  if i > 0:
    p.append((i,1))
    P += 1
  elif i == 0:
    p.append((0,0))
    z = True
  else:
    p.append((-i,-1))
    
if P == 0 and k%2 == 1:
  if z:
    print(0)
  else:
    ans = 1
    p.sort()
    for i in range(k):
      ans *= -p[i][0]
      ans %= mod
    print(ans)
  exit()

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

mod = 10**9 + 7

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

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

Am.sort()
Ap.sort()
ans = 1

if N-K < pm[1]:
  print(0)
  exit()

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

if K == 1:
  print(Ap[-1])
  exit()

Bm = sorted(zip(Am, [1]*pm[0]))
Bp = sorted(zip(Ap, [0]*pm[2]))

B = Bm + Bp
B.sort(reverse = True)
cnt = 0

for i in range(K):
  if i == K-1:
    cnt %= 2
    if cnt != B[i][1]:
      break
    else:
      ans *= B[i][0]
      ans %= mod
      print(ans)
      exit()
  else:
    ans *= B[i][0]
    ans %= mod
    cnt += B[i][1]

ans1 = ans
ans2 = ans * B[K-1][0] % mod

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

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

if mcnt1 == 1 and mcnt2 == 1:
  print(max(ans1, ans2))
elif mcnt1 == 1:
  print(ans1)
elif mcnt2 == 1:
  print(ans2)
else:
  ans *= B[K][0]
  ans %= mod
  print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and sum([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True, key=lambda x:abs(x))
cnt = 0
im = 0
ip = 0
cp = 0
mod = 10 ** 9 + 7

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans) # ok
    else:
        ans = 1
        cnt = 0
        f = 0
        for i, ai in enumerate(a):
            if cnt == k:
                f = 2
                break
            if i == im and ai < 0:
                f = 1
                continue
            if f == 1 and ai <= 0:
                continue
            ans *= abs(ai)
            ans %= mod
            # print(i, ai)
            cnt += 1
        if f == 2:
            print(ans)
        else:
            ans = 1
            cnt = 0
            f = 0
            for i, ai in enumerate(a):
                if cnt == k:
                    f = 2
                    break
                if i == ip:
                    f = 1
                    continue
                if f == 1 and ai >= 0:
                    continue
                ans *= abs(ai)
                ans %= mod
                # print(i, ai)
                cnt += 1
            if f == 2:
                print(ans) # ok
            else:
                ans = 1
                a.sort(reverse=True)
                for i, ai in enumerate(a):
                    if i == k:
                        break
                    ans *= ai
                    ans %= mod
                print(ans) # ok

else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= abs(ai)
        ans %= mod
    print(ans) # ok

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(len(a)):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lm,2):
			if i == lm-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						cp -= 1
					else:
						cm += 1
				else:
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						cm += 1
					else:
						cp -= 1
				else:
					
					cm += 1
		elif cp != -1:
			cp -= 1
		elif cm != lm:
			cm += 1
			
		else:
			break
	if cm % 2 != 0:
		if cp == lp-1:
			cp -= 1
			cm -= 1

		else:
			if cp != -1 and cm != lm:
				if pra[cp+1] == 0: 
					cp += 1
					cm += 1
				elif pra[cp]/-mina[cm-1] <= -mina[cm]/pra[cp+1]:
					cp += 1
					cm += 1
				else:
					cp -= 1
					cm -= 1
			elif cp != -1:
				cp -= 1
				cm -= 1
			elif cm != lm:
				cp += 1
				cm += 1

	ii = -2
	for i in range(0,cm,2):
		if i == cm-1:
			ii = i
			continue
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod
	if ii == cm-1:
		ans *= mina[ii]
		ans %= mod

		
	print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=sorted(list(map(int,input().split())))
t=1
def maxProductSubarrayOfSizeK(A, n, k): 
  
    # sorting given input array 
    A.sort() 
  
    # variable to store final product of  
    # all element of sub-sequence of size k 
    product = 1
  
    # CASE I 
    # If max element is 0 and 
    # k is odd then max product will be 0 
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    # CASE II 
    # If all elements are negative and 
    # k is odd then max product will be 
    # product of rightmost-subarray of size k 
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product=(product* A[i])%1000000007 
        return product 
  
    # else 
    # i is current left pointer index 
    i = 0
  
    # j is current right pointer index 
    j = n - 1
  
    # CASE III 
    # if k is odd and rightmost element in 
    # sorted array is positive then it 
    # must come in subsequence 
    # Multiplying A[j] with product and 
    # correspondingly changing j 
    if (k & 1): 
        product = (product*A[j])%1000000007 
        j-= 1
        k-=1
  
    # CASE IV 
    # Now k is even. So, Now we deal with pairs 
    # Each time a pair is multiplied to product 
    # ie.. two elements are added to subsequence  
    # each time. Effectively k becomes half 
    # Hence, k >>= 1 means k /= 2 
    k >>= 1
  
    # Now finding k corresponding pairs to get 
    # maximum possible value of product 
    for itr in range( k) : 
  
        # product from left pointers 
        left_product = (A[i] * A[i + 1])%1000000007 
  
        # product from right pointers 
        right_product = A[j] * A[j - 1]%1000000007
  
        # Taking the max product from two  
        # choices. Correspondingly changing 
        # the pointer's position 
        if (left_product > right_product) : 
            product =(product* left_product)%1000000007 
            i += 2
          
        else : 
            product =(product* right_product)%1000000007 
            j -= 2
  
    # Finally return product 
    return product 
k=maxProductSubarrayOfSizeK(l,n,k)
print(k%1000000007)

Submission status: Wrong Answer

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

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

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

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