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())
X = list(map(int, input().split()))
MOD = 10 ** 9 + 7

pos = sorted(v for v in X if v >= 0)
neg = sorted(-v for v in X if v < 0)

ok = False  # True: ans>=0, False: ans<0
if pos:
    if N == K:
        # Select all -> number of negatives must be even
        ok = len(neg) % 2 == 0
    else:
        ok = True
else:
    # All negative and even number is selected
    ok = K % 2 == 0

ans = 1
if ok:
    # ans >= 0
    if K % 2 == 1:
        ans = ans * pos.pop() % MOD

    # 答えは正になる→二つの数の積は必ず正になる．
    cand = []
    while len(pos) >= 2:
        x = pos.pop() * pos.pop()
        cand.append(x)

    while len(neg) >= 2:
        x = neg.pop() * neg.pop()
        cand.append(x)

    cand.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * cand[i] % MOD
else:
    # ans <= 0
    cand = sorted(X, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * cand[i] % MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def modpow(a,n):
    r=1
    while n > 0:
        if n%2==1:
            r = r*a%MOD
        a = a*a % MOD
        n = n//2
    return r

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



As.sort(key=lambda x:abs(x),reverse=True)
As_srt=sorted(As)

if N==K or (As_srt[-1]<0 and K%2==1):
    ans=1
    for i in range(K):
        ans *= As[N-i-1]
        ans %= MOD
    print(ans)
else:
    ans = 1
    sign = 1
    for i in range(K):
        ans *=As[i]
        ans %=MOD
        if As[i]<0:
            sign *= -1
    if sign < 0:
        #print(As,ans) ###
        # ansを正にする
        rm_p=None
        rm_n=None
        for i in range(K):
            if rm_p!=None and rm_n!=None:
                break
            if rm_p==None and As[K-i-1]>0:
                rm_p=As[K-i-1]
            if rm_n==None and As[K-i-1]<0:
                rm_n=As[K-i-1]
        
        apd_zp=None
        apd_n=None
        for i in range(N-K):
            if apd_zp!=None and apd_n!=None:
                break
            if apd_zp==None and As[K+i]>=0:
                apd_zp=As[K+i]
            if apd_n==None and As[K+i]<0:
                apd_n=As[K+i]
        #print(rm_n,rm_p,apd_n,apd_zp) ###

        if rm_n == None or apd_zp == None:
            rm=rm_p
            apd=apd_n
        elif rm_p == None or apd_n == None:
            rm=rm_n
            apd=apd_zp
        else:
            if abs(rm_p * apd_zp) <= abs(rm_n * apd_n):
               rm=rm_p
               apd=apd_n
            else:
                rm=rm_n
                apd=apd_zp
        ans *= apd
        ans %=MOD
        rm_inv = modpow(rm,MOD-2)
        ans *= rm_inv
        ans %= MOD

    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10 ** 9+ 7
    ans = 1

    def answer(a):
        ans =1
        for x in a:
            ans *= x
            ans %= mod
        return ans

    if n == k:
        print(answer(a))
        return
    a.sort(reverse=True, key= lambda x:abs(x))
    if sum(x<0 for x in a[:k])%2 == 0:
        print(answer(a[:k]))
    else:
        if all(x < 0 for x in a):
            print(answer(a[-k:]))
        else:
            try:
                x1, y1= min([x for x in a[:k] if x > 0]), min([x for x in a[k:] if x < 0])
            except ValueError:
                x1, y1 = 1, 0
            try:
                x2, y2= max([x for x in a[:k] if x < 0]),\
                    max([x for x in a[k:] if x >= 0])
            except ValueError:
                x2, y2 = 1, 0
            if abs(x2*y1) > abs(x1*y2):           
                a[a.index(x1)] = y1
            else:
                a[a.index(x2)] = y2
            print(answer(a[:k]))
            


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A_neg = []
A_pos = []
 
for i in range(N):
  if A[i] <= 0:
    A_neg.append(-A[i])
  else:
    A_pos.append(A[i])
 
A_neg.sort(reverse=True)
A_pos.sort(reverse=True)
 
ans = 1
 
if K == N:
  for i in range(N):
    ans *= (A[i]%1000000007)
    ans %= 1000000007
  print(ans)
 
elif K%2==1 and len(A_pos)==0:
  for i in range(1, K+1):
    ans *= ((-A_neg[-i])%1000000007)
    ans %= 1000000007
  print(ans)
 
else:
  if K%2==1:
    ans *= A_pos.pop(0)
    K -= 1
  buf = []
  for i in range(len(A_pos)//2):
    buf.append(A_pos[2*i]*A_pos[2*i+1])
  for i in range(len(A_neg)//2):
    buf.append(A_neg[2*i]*A_neg[2*i+1])
  buf.sort(reverse=True)
  for i in range(K//2):
    ans *= (buf[i]%1000000007)
    ans %= 1000000007
  print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
from functools import reduce


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = sorted(map(int, args[1].split()))
    mod = 10**9+7

    if n == k:
        return str(reduce(lambda a, b: (a*b) % mod, A, 1))

    if k % 2 and A[-1] < 0:
        return str(reduce(lambda a, b: (a*b) % mod, A[n-k:], 1))

    l, r = 0, n-1
    count = 0
    ret = 1

    if k % 2:
        ret *= A[-1]
        r -= 1
        count += 1

    while count < k-1:
        pos = max(0, A[r]*A[r-1])
        neg = max(0, A[l]*A[l+1])
        if pos <= neg:
            ret *= neg
            l += 2
        else:
            ret *= pos
            r -= 2
        ret %= mod
        count += 2

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
#/usr/bin/python

def solve():
    n, k = map(int, input().split())
    a = sorted(map(int, input().split()), reverse=True)

    mod = 10 ** 9 + 7
    l = 0
    r = n - 1
    ans = 1

    if k % 2 == 1:
        ans = a[0]
        l = 1

    # If the maximum number is negative and k is odd, the answer is the product of the first k numbers.
    if ans < 0:
        mul = 1
        for i in range(k):
            mul = mul * a[i] % mod
        return mul

    # otherwise, multiply the leftmost two products and the rightmost two products, whichever is larger.
    for i in range(k//2):
        l_mul = a[l] * a[l+1]
        r_mul = a[r] * a[r-1]
        if l_mul >= r_mul:
            ans = ans * l_mul % mod
            l += 2
        else:
            ans = ans * r_mul % mod
            r -= 2

    return ans

print(solve())

Submission status: Accepted

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

A_neg = []
A_pos = []

for i in range(N):
  if A[i] <= 0:
    A_neg.append(-A[i])
  else:
    A_pos.append(A[i])

A_neg.sort(reverse=True)
A_pos.sort(reverse=True)

ans = 1

if K == N:
  for i in range(N):
    ans *= (A[i]%1000000007)
    ans %= 1000000007
  print(ans)

elif K%2==1 and len(A_pos)==0:
  for i in range(1, K+1):
    ans *= ((-A_neg[-i])%1000000007)
    ans %= 1000000007
  print(ans)

else:
  if K%2==1:
    ans *= A_pos.pop(0)
    K -= 1
  buf = []
  if len(A_pos)>=2:
    for i in range(len(A_pos)//2):
      buf.append(A_pos[2*i]*A_pos[2*i+1])
  if len(A_neg)>=2:
    for i in range(len(A_neg)//2):
      buf.append(A_neg[2*i]*A_neg[2*i+1])
  buf.sort(reverse=True)
  for i in range(K//2):
    ans *= (buf[i]%1000000007)
    ans %= 1000000007
  print(ans)

Submission status: Accepted

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

A_neg = []
A_pos = []

for i in range(N):
  if A[i] <= 0:
    A_neg.append(-A[i])
  else:
    A_pos.append(A[i])

A_neg.sort(reverse=True)
A_pos.sort(reverse=True)

ans = 1

if K == N:
  for i in range(N):
    ans *= (A[i]%1000000007)
    ans %= 1000000007
  print(ans)

elif K%2==1 and len(A_pos)==0:
  for i in range(1, K+1):
    ans *= ((-A_neg[-i])%1000000007)
    ans %= 1000000007
  print(ans)

else:
  if K%2==1:
    ans *= A_pos.pop(0)
    K -= 1
  buf = []
  for i in range(len(A_pos)//2):
    buf.append(A_pos[2*i]*A_pos[2*i+1])
  for i in range(len(A_neg)//2):
    buf.append(A_neg[2*i]*A_neg[2*i+1])
  buf.sort(reverse=True)
  for i in range(K//2):
    ans *= (buf[i]%1000000007)
    ans %= 1000000007
  print(ans)

Submission status: Accepted

Solution code:
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0 and k%2 ==1 :
  if zero >= 1:
    ans = 0
  else:
    minus.sort(reverse=True)
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2 == 1:
    ans *= plus[0]
    q = 1
  judge = []
  for i in range((P-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(M//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0 and k%2 ==1 :
  if zero >= 1:
    ans = 0
  else:
    minus.sort(reverse=True)
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2 == 1:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((P-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(M//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0 and k%2 ==1 :
  if zero >= 1:
    ans = 0
  else:
    minus.sort(reverse=True)
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2 == 1:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0 and k%2 ==1 :
  if zero >= 1:
    ans = 0
  else:
    minus.sort(reverse=True)
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0 and k%2 ==1 :
  if zero >= 1:
    ans = 0
  else:
    minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero >= 1 and k%2 == 1:
    ans = 0
  else:
    if k%2 == 1:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero >= 1 and k%2 == 1:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2 == 1:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
def prod(li, MOD):
    ret = 1
    for a in li:
        ret *= a
        ret %= MOD
    return ret

N, K = map(int, input().split())
MOD = 1_000_000_007
aaa = list(map(int, input().split()))
if N == K:
    print(prod(aaa, MOD))
    exit()
aaa.sort(key=lambda x : abs(x))
if sum(a < 0 for a in aaa[-K:]) % 2 == 0:
    print(prod(aaa[-K:], MOD))
else:
    if all(a <= 0 for a in aaa):
        bbb = aaa[:K]
    else:
        try:
            x1, y1 = min([a for a in aaa[-K:] if a > 0]), min([a for a in aaa[:-K] if a < 0])
        except:
            x1, y1 = 1, 0
        try:
            x2, y2 = max([a for a in aaa[-K:] if a < 0]), max([a for a in aaa[:-K] if a >= 0])
        except:
            x2, y2 = 1, 0
        bbb = aaa[-K:]
        if abs(x2 * y1) > abs(x1 * y2):
            bbb.remove(x1)
            bbb.append(y1)
        else:
            bbb.remove(x2)
            bbb.append(y2)
    print(prod(bbb, MOD))

Submission status: Accepted

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

def solve():
    A.sort(key=lambda x: abs(x), reverse=True)

    ans = 1
    nneg = 0
    a, b, c, d = -1, -1, -1, -1
    for k in range(K):
        ans = (ans * A[k])%MOD
        if A[k] < 0:
            nneg += 1
            b = k
        else:
            a = k
    
    if K == N or nneg%2 == 0:
        return ans
    
    for k in range(N-1, K-1, -1):
        if A[k] < 0:
            d = k
        else:
            c = k

    # b must be >= 0
    if a == -1 and c == -1: # all minus
        ans = 1
        for k in range(K):
            ans = (ans * A[-1-k])%MOD
        return ans
    
    if a == -1 or d == -1:
        outn = A[b]
        inn = A[c]
    elif c == -1:
        outn = A[a]
        inn = A[d]
    else:
        if A[a]*A[c] > A[b]*A[d]:
            outn = A[b]
            inn = A[c]
        else:
            outn = A[a]
            inn = A[d]

    ans = (ans * pow(outn, MOD-2, MOD))%MOD
    ans = (ans * inn)%MOD
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
MOD = (int) (1e9+7)

def power(a,n):
    if a == 0: return 0
    if n == 0: return 1

    res = 1
    while n > 0:
        if n % 2 == 1: res = res * a % MOD
        a = a * a % MOD
        n //= 2

    return res

def inverse(n):
    return power(n, MOD-2)

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

B = []
pos, neg = 0, 0
for a in A:
    if a > 0:
        B.append([a,1])
        pos += 1
    if a < 0:
        B.append([-a,-1])
        neg += 1
    if a == 0:
        B.append([0,0])
B.sort(reverse=True)

ans, sign  = 1, 1
if N == neg and K % 2 == 1:
    for i in range(K):
        ans *= B[N-1-i][0] 
        ans %= MOD
    print(-ans % MOD)
    exit()

for i in range(K):
    ans *= B[i][0]
    ans %= MOD
    sign *= B[i][1]

if N == K:
    if sign >= 0: print(ans)
    else: print(-ans % MOD)
    exit()

if sign < 0:
    out_neg, out_pos = 0, 0
    in_pos, in_neg = 0, 0

    for i in range(K):
        if B[K-1-i][1] < 0:
            out_neg = B[K-1-i][0]
            break
    
    for i in range(K):
        if B[K-1-i][1] > 0:
            out_pos = B[K-1-i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] > 0:
            in_pos = B[K+i][0]
            break
    
    for i in range(N-K):
        if B[K+i][1] < 0:
            in_neg = B[K+i][0]
            break
    

    if in_neg == 0 or out_pos == 0:
        ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
    elif in_pos == 0 or out_neg == 0:
        ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
    else:
        if out_pos * in_pos < out_neg * in_neg:
            ans = (ans * in_neg % MOD) * inverse(out_pos) % MOD
        else:
            ans = (ans * in_pos % MOD) * inverse(out_neg) % MOD
            
print(ans)

Submission status: Accepted

Solution code:
n, k = [int(x) for x in input().strip().split(" ")]
p = 10**9 + 7

num_list = [int(x) for x in input().strip().split(" ")]
num_list = sorted(num_list, reverse = True)

ans = 1
l_idx = 0
r_idx = -1

if num_list[0] < 0 and k % 2 == 1:
  for i in range(k):
    ans = (ans * num_list[i]) % p
else:
  while True:
    if k >= 2:
      l_prod = num_list[l_idx] * num_list[l_idx+1]
      r_prod = num_list[r_idx] * num_list[r_idx-1]
      if l_prod >= r_prod:
        ans = (ans * num_list[l_idx]) % p
        l_idx +=1
        k -= 1
      else:
        ans = (ans * r_prod) % p
        r_idx -=2
        k -= 2
    elif k == 1:
      ans = (ans * num_list[l_idx]) % p
      ans %= p
      break
    else:
      break

print(ans)

Submission status: Accepted

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

if K == N:
    ans = 1
    for x in A:
        ans = (ans * x) % MOD
    print(ans)
    exit()

plus, minus = [], []
for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)

plus.sort(reverse=True)
minus.sort()

if not plus:
    ans = 1
    if K % 2:
        # 答えは負値になるので絶対値小さいのを取る
        for x in minus[-K:]:
            ans = (ans * x) % MOD
    else:
        # 答えは非負値になるので絶対値大きいのを取る
        for x in minus[:K]:
            ans = (ans * x) % MOD
    print(ans)
    exit()

idx = 0
for i in range(2, N, 2):
    if K - i < 0:
        break
    if not len(plus) >= K - i + 2:
        idx += 2
        continue
    if len(minus) >= i:
        if minus[i - 2] * minus[i - 1] < plus[K - i + 1] * plus[K - i]:
            break
        else:
            idx += 2

ans = 1
for x in minus[:idx] + plus[:K - idx]:
    ans = (ans * x) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    res = 1
    if n == k:
        for a in A:
            res = (res * a) % mod
        print(res)
        exit()

    P, M = [], []
    for a in A:
        P.append(a) if a >= 0 else M.append(a)

    if len(P) == n:
        A.sort(reverse=True)
        for i in range(k):
            res = (res * A[i]) % mod
    elif len(M) == n:
        A.sort(reverse=True) if k % 2 else A.sort()
        for i in range(k):
            res = (res * A[i]) % mod
    else:
        P.sort(reverse=True)
        M.sort()
        B = []
        if k % 2:
            k -= 1
            b = P.pop(0)
            B.append(b)
            res = (res * b) % mod
        for i in range(0, len(P), 2):
            if i + 1 < len(P):
                B.append(P[i] * P[i + 1])
        for j in range(0, len(M), 2):
            if j + 1 < len(M):
                B.append(M[j] * M[j + 1])
        B.sort(reverse=True)
        for i in range(k // 2):
            res = (res * B[i]) % mod

    print(res)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

if n==k:
  # n==kなら全部選ぶ必要がある
  ans=1
  for q in a:
    ans*=q
    ans%=mod
  print(ans)
  exit()
  
if all(q>=0 for q in a):
  # 全部正なら大きい方から
  ans=1
  a.sort()
  for _ in range(k):
    ans*=a.pop()
    ans%=mod
  print(ans)
  exit()

if all(q<0 for q in a):
  # 全部負なら
  # kが奇数の時は大きい方(絶対値が小さい方)から
  # kが偶数のときは小さい方(絶対値が大きい方)から
  ans=1
  a.sort()
  if k%2==0:
    for i in range(k):
      ans*=a[i]
      ans%=mod
  else:
    for _ in range(k):
      ans*=a.pop()
      ans%=mod
  print(ans)
  exit()
  
pos=[]
neg=[]
for q in a:
  if q>=0:
    pos.append(q)
  else:
    neg.append(q)

pos.sort()
neg.sort()
neg=neg[::-1]
# arr[-1]の絶対値が最大となるようにソート

kk=k
# kが奇数のときは、posの最大は絶対とって良い
if kk%2==1:
  ans=pos.pop()%mod
  kk=kk-1
else:
  ans=1

# 2個ずつ比較しながら掛け算
# 片方の長さが2に満たない場合は、もうそちらからは取らない
while kk>0:
  if len(pos)<2:
    ans=ans*neg.pop()%mod*neg.pop()%mod
    kk-=2
  elif len(neg)<2:
    ans=ans*pos.pop()%mod*pos.pop()%mod
    kk-=2
  else:
    if pos[-1]*pos[-2]>=neg[-1]*neg[-2]:
      ans=ans*pos.pop()%mod*pos.pop()%mod
      kk-=2
    else:
      ans=ans*neg.pop()%mod*neg.pop()%mod
      kk-=2
      
print(ans)

Submission status: Accepted

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

if n==k:
  ans=1
  for q in a:
    ans*=q
    ans%=mod
  print(ans)
  exit()
  
if all(q>=0 for q in a):
  ans=1
  a.sort()
  for _ in range(k):
    ans*=a.pop()
    ans%=mod
  print(ans)
  exit()

if all(q<0 for q in a):
  ans=1
  a.sort()
  if k%2==0:
    for i in range(k):
      ans*=a[i]
      ans%=mod
  else:
    for _ in range(k):
      ans*=a.pop()
      ans%=mod
  print(ans)
  exit()
  
pos=[]
neg=[]
for q in a:
  if q>=0:
    pos.append(q)
  else:
    neg.append(q)

pos.sort()
neg.sort()
neg=neg[::-1]

kk=k
if kk%2==1:
  ans=pos.pop()%mod
  kk=kk-1
else:
  ans=1

while kk>0:
  if len(pos)<2:
    ans=ans*neg.pop()%mod*neg.pop()%mod
    kk-=2
  elif len(neg)<2:
    ans=ans*pos.pop()%mod*pos.pop()%mod
    kk-=2
  else:
    if pos[-1]*pos[-2]>=neg[-1]*neg[-2]:
      ans=ans*pos.pop()%mod*pos.pop()%mod
      kk-=2
    else:
      ans=ans*neg.pop()%mod*neg.pop()%mod
      kk-=2
      
print(ans)

Submission status: Accepted

Solution code:
import sys

# after これ通る？コピペs


def solve(n, k, aaa):
    MOD = 10 ** 9 + 7

    if n == k:
        ans = 1
        for a in aaa:
            ans = ans * a % MOD
        return ans

    pos = []  # Strictly, Non-neg
    neg = []
    for a in aaa:
        if a >= 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)

    if len(pos) == 0:
        if k % 2 == 1:
            neg.sort(reverse=True)
        else:
            neg.sort()
        ans = 1
        for a in neg[:k]:
            ans = ans * a % MOD
        return ans

    pos.sort()
    neg.sort(reverse=True)
    ans = 1
    r = k

    if r % 2 == 1:
        ans = ans * pos.pop() % MOD
        r -= 1

    while r > 0:
        if len(pos) <= 1:
            ans = ans * neg.pop() * neg.pop() % MOD
        elif len(neg) <= 1:
            ans = ans * pos.pop() * pos.pop() % MOD
        else:
            pm = pos[-1] * pos[-2]
            nm = neg[-1] * neg[-2]
            if pm > nm:
                ans = ans * pos.pop() * pos.pop() % MOD
            else:
                ans = ans * neg.pop() * neg.pop() % MOD
        r -= 2

    return ans


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, aaa))

Submission status: Accepted

Solution code:
MOD=1000000007
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
pos=[]
neg=[]
nzero=0
for i in a:
    if i>0:
        pos.append(i)
    elif i<0:
        neg.append(-i)
    else:
        nzero+=1
if nzero+k>n:
    print(0)
elif nzero+k==n and len(pos)>0 and len(neg)>0:
    if nzero==0:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        if len(neg)%2:
            res*=-1
            res+=MOD
        print(res)
    elif len(neg)%2:
        print(0)
    else:
        res=1
        for i in pos+neg:
            res*=i
            res%=MOD
        print(res)
elif len(pos)==0:
    res=1
    if k%2 and nzero>0:
        print(0)
    elif k%2:
        neg.sort()
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
    else:
        neg.sort(reverse=True)
        for i in range(k):
            res*=MOD-neg[i]
            res%=MOD
        print(res)
elif len(neg)==0:
    res=1
    pos.sort(reverse=True)
    for i in range(k):
        res*=pos[i]
        res%=MOD
    print(res)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    ruip=[1 for i in range(len(pos)+1)]
    ruin=[1 for i in range(len(neg)+1)]
    for i in range(len(pos)):
        ruip[i+1]=ruip[i]*pos[i]
        ruip[i+1]%=MOD
    for i in range(len(neg)):
        ruin[i+1]=ruin[i]*neg[i]
        ruin[i+1]%=MOD
    np=0
    if len(pos)>=k:
        np=k
    elif (k-len(pos))%2:
        np=len(pos)-1
    else:
        np=len(pos)
    while np>=2 and (pos[np-1]*pos[np-2]<neg[k-np+1]*neg[k-np]):
        np-=2
        if len(neg)-1<k-np+1:
            break
    print((ruip[np]*ruin[k-np])%MOD)