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: Accepted

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0

#tmp = k-pl
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3#mn
elif zr >= 1 and pl == 0 and k % 2 == 1:
    hugo = 2#zr
else:
    hugo = 1#pl

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        if tmp % 2 == 1:
            tmp -= 1
            pl_num += 1
            tmp_ans = a[n-1]
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = 0
                tmp_m_seki = 0
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                elif tmp_p_seki == 0 and tmp_m_seki == 0:
                    tmp_seki = 0
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            #elif tmp == 1:
            #    tmp_seki = a[n-1-pl_num]
            #    tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Accepted

Solution code:

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

zeros = []
pluss = []
minuss = []

for i in range(N):
    if A[i]>0:
        pluss.append(A[i])
    elif A[i]==0:
        zeros.append(A[i])
    else:
        minuss.append(A[i])

pluss = sorted(pluss, reverse = True)
minuss = sorted(minuss)

if len(pluss) + (min(len(minuss), K)//2)*2 >= K:
    answer_type = 1
elif len(zeros) > 0:
    answer_type = 2
else:
    answer_type = 3


rest = K
if answer_type == 1:
    plus_now = 0
    minus_now = 0
    minus_counter = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = -1000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = -1000000000000
        
        if plus_target >= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
            minus_counter += 1

    if minus_counter%2 == 1:
        #★インデックスの有効範囲をよく考えること、勝手に-1とかなっちゃう★
        if minus_now >= len(minuss) or plus_now == 0:
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        elif plus_now >= len(pluss) or minus_now == 0:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod
        #★割り算の時は有効桁数よく考えること★
        elif pluss[plus_now]*pluss[plus_now-1] > -minuss[minus_now]*(-minuss[minus_now-1]):
            answer = answer * pow(-minuss[minus_now-1],mod-2,mod)
            answer = (answer * pluss[plus_now])%mod
        else:
            answer = answer * pow(pluss[plus_now-1],mod-2,mod)
            answer = (answer * -minuss[minus_now])%mod

elif answer_type == 2:
    answer = 0
elif answer_type == 3:
    minuss = sorted(minuss, reverse = True)
    pluss = sorted(pluss)
    plus_now = 0
    minus_now = 0
    answer = 1
    for i in range(K):
        if plus_now < len(pluss):
            plus_target = pluss[plus_now]
        else:
            plus_target = 10000000000000
        
        if minus_now < len(minuss):
            minus_target = -minuss[minus_now]
        else:
            minus_target = 10000000000000  
        
        if plus_target <= minus_target:
            answer = (answer*plus_target)%mod
            plus_now += 1
        else:
            answer = (answer*minus_target)%mod
            minus_now += 1
    answer = answer * -1
print(answer%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    if N == K:
        ans = 1
        for a in A:
            ans *= a
            ans %= MOD
        print(ans)
        return
    
    if all(a < 0 for a in A) and K%2 == 1:
        A.sort(reverse = True)
        ans = 1
        for i in range(K):
            ans *= A[i]
            ans %= MOD
        print(ans)
        return
    
    A.sort(key = abs,reverse = True)
    cnt_m = 0
    ans = 1
    last_p = -1
    last_m = 1
    for i in range(K):
        if A[i] == 0:
            print(0)
            return
        elif A[i] < 0:
            ans *= A[i]
            ans %= MOD
            cnt_m += 1
            last_m = A[i]
        else:
            ans *= A[i]
            ans %= MOD
            last_p = A[i]
    if cnt_m%2 == 0:
        print(ans)
    else:
        diff1 = last_p
        diff2 = last_m
        inv1 = pow(last_m,MOD - 2,MOD)
        inv2 = pow(last_p,MOD - 2,MOD)
        for i in range(K,N):
            if A[i] >= 0:
                diff1 *= A[i]
                inv1 *= A[i]
                inv1 %= MOD
                break
            if i == N - 1:
                diff1 = -1
        for i in range(K,N):
            if A[i] < 0:
                diff2 *= A[i]
                inv2 *= A[i]
                inv2 %= MOD
                break
            if i == N - 1:
                diff2 = -1
        
        if last_p > 0:
            if diff1 < diff2:
                ans *= inv2
                ans %= MOD
            else:
                ans *= inv1
                ans %= MOD
        else:
            ans *= inv1
            ans %= MOD
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num, cnt = 1, [], 0

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) == 0 or (len(pla) > 0 and abs(mia[-1]) <= pla[-1]):
        tmp = pla.pop()
    elif len(pla) == 0 or (len(mia) > 0 and abs(mia[-1]) > pla[-1]):
        tmp = mia.pop()
        cnt += 1
    num.append(tmp)
    ans = ans * tmp % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def main():
    n, k = map(int, input().split())# 正0でコーナー
    a = list(map(int, input().split()))
    pos = []
    neg = []
    zero = []
    for v in a:
        if v == 0:
            zero.append(v)
        elif 0 < v:
            pos.append(v)
        else:
            neg.append(v)
    if len(pos) + len(neg) < k:
        print(0)
    else:
        if k%2 == 0:
            if len(pos) + len(neg) == k and len(pos) % 2 == 1:#負になる
                if len(zero) > 0:
                    print(0)
                else:
                    ans = 1
                    for v in pos:
                        ans *= v
                        ans %= MOD
                    for v in neg:
                        ans *= v
                        ans %= MOD
                    print(ans % MOD)
            else:
                pos.sort(reverse=True)
                neg.sort()
                ans = 1
                p, q = 0, 0
                while k > 0:
                    if p+1 < len(pos) and q+1 < len(neg):
                        x, y = pos[p]*pos[p+1], neg[q]*neg[q+1]
                        if x > y:
                            ans *= x
                            p += 2
                        else:
                            ans *= y
                            q += 2
                    elif p+1 < len(pos):
                        ans *= pos[p]*pos[p+1]
                        p += 2
                    else:
                        ans *= neg[q]*neg[q+1]
                        q += 2
                    k -= 2
                    ans %= MOD
                print(ans % MOD)
        else:
            if 0 == len(pos):
                if 0 < len(zero):
                    print(0)
                else:
                    neg.sort(reverse=True)
                    ans = 1
                    for i in range(k):
                        ans *= neg[i]
                        ans %= MOD
                    print(ans)
            else:
                pos.sort(reverse=True)
                neg.sort()
                ans = pos[0]
                p, q = 1, 0
                k -= 1
                while k > 0:
                    if p+1 < len(pos) and q+1 < len(neg):
                        x, y = pos[p]*pos[p+1], neg[q]*neg[q+1]
                        if x > y:
                            ans *= x
                            p += 2
                        else:
                            ans *= y
                            q += 2
                    elif p+1 < len(pos):
                        ans *= pos[p]*pos[p+1]
                        p += 2
                    else:
                        ans *= neg[q]*neg[q+1]
                        q += 2
                    k -= 2
                    ans %= MOD
                print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
mod=10**9+7
def solve(n,k,a):
  if min(a)>0:
    ans=1
    a.sort(reverse=1)
    for i in a[:k]:
      ans*=i
      ans%=mod
    return ans
  if max(a)<0:
    if k%2==0:
      a.sort()
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
    else:
      a.sort(reverse=1)
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
  if n==k:
    ans=1
    for i in a:
      ans*=i
      ans%=mod
    return ans
  if k==1:
    return max(a)
  if n-k==1:
    ans=1
    if a.count(0)>1:return 0
    p=[]
    m=[]
    for i in a:
      if i>0:p.append(i)
      elif i<0:m.append(i)
    if 0 in a:
      if len(m)%2==0:
        for i in a:
          if i==0:continue
          ans=(ans*i)%mod
      else:ans=0
    else:
      if len(m)%2==0:
        for i in sorted(p)[1:]+m:ans=(ans*i)%mod
      else:
        for i in p+sorted(m)[:-1]:ans=(ans*i)%mod
    return ans


  ans=1
  p=[]
  m=[]
  for i in a:
    if i<0:m.append(i)
    elif i>=0:p.append(i)
  p.sort()
  m.sort(reverse=1)

  while k>1:
    if k<=5:
      if len(p)>=10:p=p[-10:]
      if len(m)>=10:m=m[-10:]
      ans*=solve2(len(p)+len(m),k,m+p)
      ans%=mod
      k=0
      break
    if len(p)<2:
      ans*=m.pop()*m.pop()
      k-=2
    elif len(m)<2:
      ans*=p.pop()*p.pop()
      k-=2
    elif m[-1]*m[-2]>p[-1]*p[-2]:
      ans*=m.pop()*m.pop()
      k-=2
    else:
      ans*=p.pop()*p.pop()
      k-=2
    ans%=mod
  if k:
    ans*=p.pop()
  return ans

def solve2(n,k,a):
  ans=-10**20
  for c in combinations(range(n),k):
    anss=1
    for i in c:anss*=a[i]
    ans=max(ans,anss)
  return ans%mod

n,k=map(int,input().split())
a=list(map(int,input().split()))
print(solve(n,k,a))

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
if max(a)<0:
  if k%2:a.sort(reverse=1)
  else:a.sort()
  ans=1
  for i in a[:k]:ans=(ans*i)%mod
  exit(print(ans))
if n==k:
  ans=1
  for i in a:ans=(ans*i)%mod
  exit(print(ans))
p=[(0,0)]
m=[(0,0)]
for i in a:
  if i<0:m.append((-i,1))
  else:p.append((i,0))
pp=mm=None
p.sort()
m.sort()
oe=0
ans=1
for i in range(k):
  if p[-1][0]>m[-1][0]:
    t,f=p.pop()
    pp=t
  else:
    t,f=m.pop()
    mm=t
  ans=(ans*t)%mod
  if ans==0:exit(print(0))
  oe^=f
if oe:
  if mm==None:
    ans=(ans*pow(pp,mod-2,mod)*m[-1][0])%mod
  elif pp==None:
    ans=(ans*pow(mm,mod-2,mod)*p[-1][0])%mod
  elif pp*p[-1][0]>mm*m[-1][0]:
    ans=(ans*pow(mm,mod-2,mod)*p[-1][0])%mod
  else:
    ans=(ans*pow(pp,mod-2,mod)*m[-1][0])%mod
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10**9+7
if k==n:
    ans = 1
    for i in a:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
if k%2==1 and len(pa)==0:
    ans = 1
    for i in a[::-1][:k]:
        ans *= i
        ans %= mod
    print(ans)
    exit(0)
if k==1:
    print(a[-1])
    exit(0)
if k%2==1:
    rem = pa[-1]
    pa = pa[:-1]
na += [0]*n
pa += [0]*n
nn = 0
pn = 0
ans = 1
for i in range(k//2):
    if i==k//2-1 and k%2==1:
        break
    if pa[pn]*pa[pn+1]>=na[nn]*na[nn+1]:
        ans *= pa[pn]*pa[pn+1]
        pn += 2
    else:
        ans *= na[nn]*na[nn+1]
        nn += 2
    ans %= mod
if k%2==1:
    ans *= max(pa[pn]*pa[pn+1]*max(pa[pn+2], rem), na[nn]*na[nn+1]*max(pa[pn], rem))
print(ans%mod)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    plus = []
    minus = []
    for a in A:
        if a >= 0:
            plus.append(a)
        else:
            minus.append(a)
    # 答えが負になる場合をFalse
    flag = False
    if len(plus) > 0:
        if N == K:
            flag = (len(minus) % 2) == 0
        if N > K:
            flag = True
    elif len(plus) == 0:
        flag = (K % 2) == 0
    
    MOD = 10 ** 9 + 7
    ans = 1
    if flag:
        plus.sort(reverse=True)
        minus.sort()
        if K % 2 == 1:
            ans = plus.pop(0)
        B = []
        for i in range(0,len(plus),2):
            if i + 1 < len(plus):
                B.append(plus[i]*plus[i+1])
        for i in range(0,len(minus),2):
            if i + 1 < len(minus):
                B.append(minus[i]*minus[i+1])
        B.sort(reverse=True)
        for j in range(K//2):
            ans *= B[j]
            ans %= MOD
    else:
        A.sort(reverse=True)
        for i in range(K):
            ans *= A[i]
            ans %= MOD

    print(ans)
        


if __name__ == "__main__":
    main()

Submission status: Accepted

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) == 0 or (len(pla) > 0 and abs(mia[-1]) <= pla[-1]):
        tmp = pla.pop()
    elif len(pla) == 0 or (len(mia) > 0 and abs(mia[-1]) > pla[-1]):
        tmp = mia.pop()
    num.append(tmp)
    ans = ans * tmp % mod

cnt = sum(i < 0 for i in num)
if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) == 0 or(len(pla) > 0 and abs(mia[-1]) <= pla[-1]):
        tmp = pla.pop()
    elif len(pla) == 0 or (len(mia) > 0 and abs(mia[-1]) > pla[-1]):
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if (len(mia) * len(pla) > 0 and abs(mia[-1]) <= pla[-1]) or len(mia) == 0:
        tmp = pla.pop()
    elif (len(mia) * len(pla) > 0 and abs(mia[-1]) > pla[-1]) or len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p,q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                r, s = i, pla[-1]
                break
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans); exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        for i in num[::-1]:
            if i >= 0:
                p, q = i, mia[-1]; break
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                r, s = i, pla[-1]; break
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        for i in num[::-1]:
            if i >= 0:
                p, q = i, mia[-1]
                break
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                r, s = i, pla[-1]
                break
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N or len(A) == K:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
sign = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if sign < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop()
            K -= 1
        else:
            ans *= N.pop() * N.pop()
            K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            sign *= -1
            continue

        if len(N) == 1:
            n = N.pop()
            if sign < 0:
                ans *= n
                K -= 1
                sign *= -1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1 and sign > 0 or K % 2 == 0 and sign < 0:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N or len(A) == K:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
sign = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if sign < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop()
            K -= 1
        else:
            ans *= N.pop() * N.pop()
            K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            sign *= -1
            continue

        if len(P) == len(N) == 1:
            ans *= P.pop() * N.pop()
            K -= 2
            sign *= -1
            continue

        if len(N) == 1:
            n = N.pop()
            if sign < 0:
                ans *= n
                K -= 1
                sign *= -1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1 and sign > 0 or K % 2 == 0 and sign < 0:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

Submission status: Accepted

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

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if len(mia) > 0 and len(pla) > 0:
        if abs(mia[-1]) <= pla[-1]:
            tmp = pla.pop()
        elif abs(mia[-1]) > pla[-1]:
            tmp = mia.pop()
    elif len(mia) == 0:
        tmp = pla.pop()
    elif len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    if len(mia) > 0 and cnt != k:
        for i in num[::-1]:
            if i >= 0:
                p, q = i, mia[-1]
                break
        if len(pla) == 0:
            ans *= q * pow(p, mod - 2, mod)
    if len(pla) > 0:
        for i in num[::-1]:
            if i < 0:
                r, s = i, pla[-1]
                break
        if len(mia) == 0 or cnt == k:
            ans *= s * pow(r, mod - 2, mod)
    if len(mia) > 0 and len(pla) > 0 and cnt != k:
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)