Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

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

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

Constraints

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

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

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

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

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

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

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

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

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

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

Sample Input 4

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

Sample Output 4

999983200

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



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Wrong Answer

Solution code:
def main():

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

    mod = pow(10, 9) + 7

    pos = []
    neg = []
    zero = 0
    for v in A:
        if v > 0: pos.append(v)
        elif v < 0: neg.append(v)
        else: zero += 1

    # zero is needed
    if len(pos) + len(neg) < K:
        return 0

    pos.sort(reverse = True)
    neg.sort()

    cnt_p, cnt_n = 0, 0
    h = []
    for v in pos:
        h.append([v, 1])
    for v in neg:
        h.append([-v, -1])

    h.sort(reverse = True)
    v = 1
    for k in range(K):
        if h[k][1] > 0:
            cnt_p += 1
        else:
            cnt_n += 1

    if cnt_n % 2 == 0: # when positive
        v = 1
        for i in range(cnt_p):
            v *= pos[i]
            v %= mod
        for j in range(cnt_n):
            v *= abs(neg[j])
            v %= mod
        return v
    else: # when negative
        if cnt_p < len(pos) and cnt_n < len(neg): # both are not full
            if pos[cnt_p] * pos[cnt_p-1] > neg[cnt_n] * neg[cnt_n-1]:
                cnt_p += 1
                cnt_n -= 1
            else:
                cnt_p -= 1
                cnt_n += 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= abs(neg[j])
                v %= mod
            return v
        elif cnt_p < len(pos) and cnt_n > 0:
            cnt_p += 1
            cnt_n -= 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= abs(neg[j])
                v %= mod
            return v
        elif cnt_n < len(neg) and cnt_p > 0:
            cnt_p -= 1
            cnt_n += 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= abs(neg[j])
                v %= mod
            return v
        else:
            if zero > 0:
                return 0
            else:
                pos.sort()
                neg.sort(reverse = True)
                h = []
                for v in pos:
                    h.append([v, 1])
                for v in neg:
                    h.append([-v, -1])
                v = 1
                for i in range(K):
                    v *= h[i][0] * h[i][1]
                    v %= mod
                return v



if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a, key = abs, reverse=True)

ans = 1
for i in range(k):
    ans *= a[i]

ans = ans % (10**9 +7)
print(ans)

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
    for i in range(k):
        ans *= -li[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-1):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n-1):
        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
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化

def main():
    INF = 10**9 + 7
    n, k = list(map(int,input().split()))
    A = list(map(int,input().split()))
    A.sort(reverse=True)
    A = deque(A)
    ans = 1
    if A[0] >= 0:
        while(k != 0):
            #print(A, k)
            if k == 1:
                ans *= A.popleft()
                k -= 1
            else:
                if A[0] * A[1] > A[-1] * A[-2]:
                    ans *= A.popleft()
                    ans *= A.popleft()
                else:
                    ans *= A.pop()
                    ans *= A.pop()
                k -= 2
        ans = ans % INF
    else:
        for i in range(k):
            ans *= A[i]
        ans += INF 
    print(ans)
    return 0

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    N, K = list(map(int, input().split()))
    A = list(map(int, sysread().split()))
    mod = 10 ** 9 + 7
    INF = mod

    plus = [a for a in A if a >= 0]
    minus = [-a for a in A if a < 0]

    plus = sorted(plus, reverse=True)
    minus = sorted(minus, reverse=True)

    P, M  = [1], [1]
    for p in plus:
        P.append((P[-1] * p) % mod)
    for m in minus:
        M.append((M[-1] * m) % mod)
    #print(P, M)


    max_ans = -mod
    for i in range(0, K+1, 2):
        if i >= len(M) or K - i >= len(P):continue
        ans = M[i] * P[K-i] % mod
        if max_ans < ans:
            max_ans = ans
        #else:
        #    break

    if max_ans == -mod:
        P, M = [1], [1]
        for p in plus[::-1]:
            P.append((P[-1] * p) % mod)
        for m in minus[::-1]:
            M.append((M[-1] * m) % mod)
        #print(P, M)

        for i in range(1, K + 1, 2):
            #print(i)
            if i >= len(M) or K - i >= len(P): continue
            ans = (-M[i] * P[K - i]) % mod
            #print(ans)
            if max_ans < ans:
                max_ans = ans


    print(max_ans)






if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
def pf(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) %p
        if bi[i] == "1":
            res = (res*a) %p
    return res

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

pos=[]
neg=[]
for a in A:
    if a<0:
        neg.append(abs(a))
    elif a>0:
        pos.append(a)
pos=pos[::-1]

p=0
n=0
ans=[1]
mod=10**9+7
for k in range(K):
    if p<len(pos) and n<len(neg):
        if pos[p]>=neg[n]:
            ans.append(ans[-1]*pos[p]%mod)
            p+=1
        else:
            ans.append(ans[-1]*neg[n]%mod)
            n+=1
    elif p==len(pos) and n<len(neg):
        ans.append(ans[-1]*neg[n]%mod)
        n+=1
    elif n==len(neg) and p<len(pos):
        ans.append(ans[-1]*pos[p]%mod)
        p+=1
    else:
        ans.append(0)
        break

if n%2==1:
    if p<len(pos):
        ans.append(ans[-1]*pos[p]*pf(neg[n-1],mod-2,mod))
    else:
        ABS=[]
        for a in A:
            ABS.append(abs(a))
        ABS.sort()
        ans=[1]
        for j in range(K):
            ans.append(ans[-1]*ABS[j]%mod)
        ans.append(-1*ans[-1])
print(ans[-1]%mod)

Submission status: Wrong Answer

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

P = []
N = []
z = 0
for i in A:
  if i > 0:
    P.append(i)
  elif i < 0:
    N.append(i)
  else:
    z += 1
P.sort(reverse = True)
N.sort()

ans = 1
sig = 1
if len(P) < K and z > 0:# Conner_1
  ans = 0
elif len(P) == 0 and K % 2 == 1:# Conner_2
  for i in range(K):
    ans *= N[-i-1]
    ans %= base
else:#Not use zeros and (P exists or even K)
  x = 0
  y = 0
  for i in range(K):
    if x == len(P):
      ans *= N[y]
      y += 1
      sig = sig * (-1)
      continue
    if y == len(N):
      ans *= P[x]
      x += 1
      ans %= base
      continue
    if y == len(N) - 1 and sig > 0:# ans must be positive
      ans *= P[x]
      x += 1
      ans %= base
      continue
    if x == len(P) - 1:
      if sig > 0 and (K - i) % 2 == 1 or sig < 0 and (K - i) % 2 == 0:
        ans *= P[x]
        x += 1
      else:
        ans *= N[y]
        y += 1
        sig = sig * (-1)
      ans %= base
      continue
    if P[x] > abs(N[y]):
      ans *= P[x]
      x += 1
    else:
      ans *= N[y]
      y += 1
      sig = sig * (-1)
    ans %= base
print(ans)

Submission status: Wrong Answer

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

if K == 1:
    ans = max(A)
elif N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
elif max(A) <= 0 and K % 2 == 1:
    A.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    A.sort(key=abs)
    sign = 1
    ans = 1
    for _ in range(K - 2):
        a = A.pop()
        ans *= a
        ans %= MOD
        if a < 0:
            sign = -sign

    if sign < 0:
        A.sort()
        ans = ans * A[0] * A[-1]
    else:
        A.sort()
        ans = ans * max(A[0] * A[1], A[-2] * A[-1])

ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    mp = sum([int(a<=0) for a in A])
    pl = True
    if (N == K):
        if mp%2 == 0:     pl = True
        else:     pl = False
    if (mp == N):
        if K%2 == 0: pl = True
        else: pl = False

    absA = sorted(A, key=abs)
    sA = deque(absA)
    ans = 1
    if pl:
        for i in range(K):
            ans*= sA.pop()
            ans%= MOD

            # print(ans)
        if ans<0:
            pre=absA[i]
            prei = i
            while((i!=N) or (absA[i] * pre)>0 ): i+=1
            if i==N:
                pre = avsA[prei+1]
                i = prei-1
                while( (i!=-1) or (absA[i]*pre)>0 ): i-=1
                if i == -1: raise
            ans//= absA[i]
            ans*= pre

        print(ans%MOD)



    else:
        for i in range(K):
            ans*= sA.popleft()
            ans%= MOD
        print(ans%MOD)


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    pls = [i for i in A if i > 0]
    ms = [i for i in A if i <0]
    pls.sort(reverse=True)
    ms.sort(reverse=False)
    A.sort(key = lambda x : abs(x),reverse=True)
    if len(pls)+len(ms) < K:
        print(0)
        return
    if len(pls) == 0 and K %2 == 1:
        x=1
        for i in list(reversed(ms))[:K]:
            x*= abs(i)
            x%= 10**9+7

        print((-x)%10**9+7)
        return
    if len(pls)+len(ms) == K and K %2==1:
        print(0)
        return

    pc = 0
    mc = 0
    for i in range(K):
        if pc >= len(pls):
            mc+=1
        elif mc >= len(ms):
            pc+=1
        elif pls[pc] > abs(ms[mc]):
            pc +=1
        else:
            mc +=1

    if mc%2  !=0:
        aplan=0
        bplan=0
        if mc < len(ms)-1:
            aplan = abs(ms[mc] *ms[mc-1])
        if pc < len(pls)-1:
            bplan = abs(pls[pc]*pls[pc-1])
        
        if aplan>bplan:
            pc -=1
            mc +=1
        else:
            pc +=1
            mc -=1
    result=1
    for i in pls[:pc]:
        result*=i
        result%=10**9+7
    for i in ms[:mc]:
        result*=abs(i)
        result%=10**9+7
    print(result)


resolve()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    A = LI()

    ans = 1
    ma = max(A)
    if ma <= 0 and K % 2:
        x = sorted(A,reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return

    x = sorted(A, key=lambda x: abs(x), reverse=True)
    m = 0
    for i in range(K):
        ans = (ans * x[i]) % MOD
        if x[i] < 0 :m += 1

    if K == N or m % 2 == 0:
        print(ans)
        return
    if x[K] == 0:
        print(0)
        return
    else:
        if m == K:
            ans = (ans * pow(x[K-1],MOD-2,MOD) * max(x[K:])) % MOD

        else:
            K1 = -1
            for i in range(K+1,N):
                if x[K] * x[i] < 0:
                    K1 = i
                    break

            f1 = 0.0
            f2 = 0.0
            i0 = -1
            i1 = -1
            for i in range(K-1,-1,-1):
                if x[i] * x[K] < 0:
                    i0 = i
                    f1 = x[K] / x[i]
                    break

            if K1 >= 0:
                for i in range(K-1,-1,-1):
                    if x[i] * x[K1] < 0:
                        i1 = i
                        f2 = x[K1] / x[i]
                        break

            if abs(f1) >= abs(f2):
                ans = (ans * pow(x[i0],MOD-2,MOD) * x[K]) % MOD
            elif i1 >= 0:
                ans = (ans * pow(x[i1],MOD-2,MOD) * x[K1]) % MOD

        print(ans)
        return



if __name__ == '__main__':
    main()

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 c%2 == 1 and n == k:
  ans = 1
  for i in range(k):
    ans *= p[i][0]
    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
  print(max(ans_p*mi_m%mod,ans_m*ma_p%mod))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort(reverse = True, key = lambda x : abs(x))
Aneg = [1 if A[i] < 0 else 0 for i in range(len(A))]
cum = list(accumulate(Aneg)) + [0]
p = 10 ** 9 + 7

ans = 1
if cum[N - 1] == N or K == N:  # 絶対マイナス使わなくちゃいけない
    for i in range(N - 1, N - K - 1, -1):
        ans = ans * A[i] % p
    print(ans)
    sys.exit()

k = 0
neg = False
avoid = 1
for i in range(N):
    if i == 0 and A[i] == 0:
        ans = 0
        break
    # if A[i] == 0 or k >= K: break
    if k >= K: break
    if A[i] > 0:
        ans = ans * abs(A[i]) % p
        k += 1
    elif neg:
        ans = ans * abs(A[i]) % p
        k += 1
        neg = not neg
    else:
        if cum[N - 1] - cum[i - 1] < 2:
            continue
        ans = ans * abs(A[i]) % p
        k += 1
        neg = not neg
# else:
#     ans = ans *
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort(key=lambda x:abs(x),reverse=True)

mod=10**9+7

p=[]
m=[]
cntm=0
cntp=0

for aa in a:
    if aa>=0:
        p.append(aa)
        if cntp+cntm<K:
            cntp+=1
    else:
        m.append(-aa)
        if cntp+cntm<K:
            cntm+=1

ans=1

if cntm%2==1:
    cntm-=1
    cntp+=1

    if cntp>len(p):
        for i in range(K):
            ans*=a[N-i-1]
            ans=(ans+mod*mod)%mod
        
        print(ans)
        exit(0)

for i in range(cntm):
    ans*=m[i]
    ans%=mod
for i in range(cntp):
    ans*=p[i]
    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
b_p = []
b_n = []
ab = []
for i in range(n):
    ab.append(abs(a[i]))
    if a[i] >= 0:
        b_p.append(a[i])
    else:
        b_n.append(a[i])
b_p = sorted(b_p,reverse=True)
b_n = sorted(b_n)
ab = sorted(ab)
ans = 1
i = 0
x = 0
y = 0
if k%2 == 1:
    if len(b_p) >= 1:
        ans *= b_p[0]
        x += 1
        i += 1
while i < k-1:
    i += 2
    if x < len(b_p)-1 and y < len(b_n)-1:
        if b_p[x]*b_p[x+1] > b_n[y]*b_n[y+1]:
            ans *= b_p[x]*b_p[x+1]
            ans %= mod
            x += 2
        else:
            ans *= b_n[y]*b_n[y+1]
            ans %= mod
            y += 2
    
    elif x < len(b_p)-1:
        ans *= b_p[x]*b_p[x+1]
        ans %= mod
        x += 2
    elif y < len(b_n)-1:
        ans *= b_n[y]*b_n[y+1]
        ans %= mod
        y += 2
    
if i != k:
    if 0 in b_p:
        ans = 0
    else:
        ans = 1
        for i in range(k):
            ans *= ab[i]
            ans %= mod
        ans *= -1
print(ans%mod)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


def main():
    from collections import Counter
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    posi = [a for a in A if a > 0]
    nega = [a for a in A if a < 0]
    posi.sort(reverse=True)
    nega.sort(reverse=True)
    A.sort(reverse=True, key=abs)
    if len(posi) + len(nega) < K:
        # 0を含まなければいけないとき
        return print(0)

    ans = modint(1)
    if K % 2 == 1 and len(posi) < K:
        # 結果が負数
        # 絶対値が小さいやつをK個取ってくる
        A.sort(key=abs)
        for a in A[:K]:
            ans *= a
    else:
        # 結果が正になるように注意しなければいけない
        # skipしてかけるものがなくなったらこわい
        # 負数がK以下の奇数個しかないとハマる
        if sum(a < 0 for a in A[:K]) % 2 == 0:
            for a in A[:K]:
                ans *= a
        else:
            ans1 = []  # 正を取り除く
            ans2 = []  # 負を取り除く
            posi = [a for a in A[:K] if a > 0]
            nega = [a for a in A[:K] if a < 0]
            p_remove = False
            for a in A[:K][::-1]:
                if a > 0 and not p_remove:
                    p_remove = True
                    continue
                ans1.append(a)
            n_remove = False
            for a in A[:K][::-1]:
                if a < 0 and not n_remove:
                    n_remove = True
                    continue
                ans2.append(a)
            mul1 = 0  # 一番大きい正
            mul2 = 0  # 　一番大きい負
            for a in A[K:]:
                if mul1 == 0 and a > 0:
                    mul1 = a
                if mul2 == 0 and a < 0:
                    mul2 = a
                if mul1 != 0 and mul2 != 0:
                    break
            ans1.append(mul2)
            ans2.append(mul1)
            s1 = sum(abs(a) for a in ans1)
            s2 = sum(abs(a) for a in ans2)

            if len(posi) == 0 or mul2 == 0:
                for a in ans2:
                    ans *= a
            elif len(nega) == 0 or mul1 == 0:
                for a in ans1:
                    ans *= a
            else:
                if s1 < s2:
                    for a in ans2:
                        ans *= a
                elif s1 > s2:
                    for a in ans1:
                        ans *= a
                else:
                    s1_3 = sum(abs(a) == 3 for a in ans1)
                    s2_3 = sum(abs(a) == 3 for a in ans2)
                    if s1_3 < s2_3:
                        for a in ans2:
                            ans *= a
                    elif s1_3 > s2_3:
                        for a in ans1:
                            ans *= a
    print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    from bisect import bisect_left, bisect_right
    N, K = MAP()
    A = LIST()
    A.sort()
    neg = bisect_left(A, 0)
    pos = bisect_right(A, 0)
    negative = A[:neg]
    zeros = A[neg:pos]
    positive = list(reversed(A[pos:]))
    if len(negative) + len(positive) < K:
        # 必ず0を選ぶ必要がある
        print(0)
        return
    if len(positive) == 0:
        if K % 2 == 1:
            if len(zeros) > 0:
                # 0を選びさえすれば良い
                print(0)
                return
            else:
                # 負の数から、0に近い数を選ぶ
                ans = 1
                for n in negative[-K:]:
                    ans *= (-n)
                    ans %= MOD
                ans *= -1
                print(ans % MOD)
                return
        else:
            # 答えは正となる。絶対値が大きい数を選ぶ
            ans = 1
            for n in negative[:K]:
                ans *= (-n)
                ans %= MOD
            print(ans % MOD)
            return

    if len(negative) + len(positive) == K:
        if len(negative) % 2 == 1:
            if len(zeros) > 0:
                print(0)
                return
            else:
                ans = 1
                for a in A:
                    ans *= a
                    ans %= MOD
                print(ans % MOD)
                return
    # print(negative)
    # print(zeros)
    # print(positive)
    # 負の数は二個一で採用する
    new_neg = []
    for i in range(0, len(negative)-1, 2):
        new_neg.append(negative[i]*negative[i+1])

    phead = 0
    nhead = 0

    k = K
    ans = 1
    while k > 1 and phead+2 < len(positive) and nhead < len(new_neg):
        if k >= 3:
            # 負のやつと、正の２番め３番目の積を比較する
            if new_neg[nhead] < positive[phead+1]*positive[phead+2]:
                ans *= positive[phead]
                ans %= MOD
                phead += 1
                k -= 1
                continue
            else:
                ans *= new_neg[nhead]
                ans %= MOD
                nhead += 1
                k -= 2
                continue
        if k == 2:
            if new_neg[nhead] < positive[phead+1]*positive[phead]:
                ans *= positive[phead+1]*positive[phead]
                ans %= MOD
                print(ans)
                return
            else:
                ans *= new_neg[nhead]
                ans %= MOD
                print(ans)
                return
    # print(k)
    # print(positive[phead:])
    # print(new_neg[nhead:])
    if nhead >= len(new_neg):
        # 残りは正から採用する
        # ここではpositiveは尽きない
        while k > 0:
            ans *= positive[phead]
            ans %= MOD
            phead += 1
            k -= 1
        print(ans)
        return
    if phead + 2 >= len(positive):
        # positiveが残り1個か2個
        if k % 2 == 0:
            # 負からとるんだが、残りのpositiveが2つなら、それを一回だけ代わりに使える
            pcand = -INF
            if phead + 1 < len(positive):
                pcand = positive[phead]*positive[phead+1]

            while k > 1 and nhead < len(new_neg):
                ncand = new_neg[nhead]
                if ncand < pcand:
                    ans *= pcand
                    ans %= MOD
                    pcand = -INF
                    k -= 2
                else:
                    ans *= ncand
                    ans %= MOD
                    nhead += 1
                    k -= 2
            if k != 0:
                ans *= pcand
                ans %= MOD

            print(ans % MOD)
            return
        else:
            ans *= positive[phead]
            ans %= MOD
            while k > 1:
                ncand = negative[nhead]*negative[nhead+1]
                ans *= ncand
                ans %= MOD
                k -= 2
                nhead += 2
            print(ans)
            return
    if k == 1:
        ans *= positive[phead]
        ans %= MOD
        print(ans)
        return
    #
    # 負の個数、0の個数,正の個数
    # 負の個数+正の個数 < Kの場合、0
    # 正の個数 == 0の場合、
    #   Kが奇数なら、0か0に近いものをK個
    #   Kが偶数なら、大きい物をK個
    # 0 < 正の個数 <= K の場合、
    #   いくつ負を選ぶかという話 二個一で貪欲 最後は最大の正
    return


if __name__ == '__main__':
    main()