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:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    pos = []
    neg = []
    for a in aa:
        if a < 0: neg.append(a)
        else: pos.append(a)
    pn = len(pos)
    nn = len(neg)
    if min(k,nn) // 2 * 2 + pn < k:
        aa.sort(key=lambda x: abs(x))
        print(cal(aa[:k]))
    else:
        pos.sort()
        neg.sort(reverse=True)
        ans = pos.pop() if k & 1 else 1
        mul = []
        while len(pos) > 1: mul.append(pos.pop() * pos.pop())
        while len(neg) > 1: mul.append(neg.pop() * neg.pop())
        mul.sort(reverse=True)
        print(ans * cal(mul[:k // 2]) % md)

def cal(xx):
    res=1
    for x in xx:
        res=res*x%md
    return res

md=10**9+7
n,k=MI()
aa=LI()
main()

Submission status: Accepted

Solution code:
from heapq import *
from collections import deque

N,K,*A = map(int, open(0).read().split())
pos = []
zero = 0
neg = []
count = K
m = 1000000007
for x in A:
    if x > 0:
        pos.append(x)
    elif x == 0:
        zero += 1
    else:
        neg.append(x)
if K == N:
    ans = A[0] % m
    for x in A[1:]:
        ans = (ans*x) % m
    print(ans)
elif K % 2 == 1 and len(pos) == 0:
    if zero > 0:
        print(0)
    else:
        ai = [x * (-1) for x in A]
        heapify(ai)
        ans = (heappop(ai)*(-1)) % m
        for i in range(K-1):
            ans = (ans*heappop(ai)*(-1)) % m
        print(ans)
elif K > N - zero:
    print(0)
else:
    heapify(neg)
    ans = 1
    negpos = []
    for i in range(len(neg)//2):
        temp = heappop(neg)
        negpos.append(temp*heappop(neg))
    dnp = deque(negpos)
    posi = [x * (-1) for x in pos]
    heapify(posi)
    if len(posi) > 0:
        t1 = heappop(posi) * (-1)
    else:
        t1 = 1
    if len(posi) > 0:
        t2 = heappop(posi) * (-1)
    else:
        t2 = 1
    for i in range(K):
        if count > 1:
            if len(dnp) > 0:
                if t1 > dnp[0]:
                    if count > 2:
                        ans = (ans*t1) % m
                        t1 = t2
                        if len(posi) > 0:
                            t2 = heappop(posi) * (-1)
                        else:
                            t2 = 1
                        count -= 1
                    else:
                        if t2 == 1 and len(posi) == 0:
                            ans = (ans*dnp.popleft()) % m
                            count -= 2
                        else:
                            ans = (ans*t1) % m
                            t1 = t2
                            if len(posi) > 0:
                                t2 = heappop(posi) * (-1)
                            else:
                                t2 = 1
                            count -= 1
                else:
                    if t1 * t2 > dnp[0]:
                        if count != 3:
                            ans = (ans*t1*t2) % m
                            if len(posi) > 0:
                                t1 = heappop(posi) * (-1)
                            else:
                                t1 = 1
                            if len(posi) > 0:
                                t2 = heappop(posi) * (-1)
                            else:
                                t2 = 1
                            count -= 2
                        else:
                            if len(posi) > 0:
                                t3 = heappop(posi) * (-1)
                                M = max(t1*t2*t3,dnp[0]*t1)
                                ans = (ans*M) % m
                                break
                            else:
                                ans = (ans*dnp.popleft()*t1) % m
                                break
                    else:
                        ans = (ans*dnp.popleft()) % m
                        count -= 2
            else:
                ans = (ans*t1) % m
                if len(posi) > 0:
                    t1 = t2
                    t2 = heappop(posi) * (-1)
                else:
                    t1 = t2
                count -= 1
        elif count == 1:
            ans = (ans*t1) % m
            break
        else:
            break
    print(ans)

Submission status: Accepted

Solution code:

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

    P = []
    M = []
    for a in A:
        if a < 0:
            M.append(a)
        else:
            P.append(a)
    p_n = len(P)
    m_n = len(M)
    # 正の値にできるかを判定する
    ok = False
    if p_n > 0:
        if N == K:
            ok = (m_n%2==0) # 負の値が偶数あるとTrue
        else:
            ok = True
    # 負の値しか無い場合
    else:
        ok = (K % 2 == 0) # Kが偶数なら負の値を偶数個選べる

    ans = 1
    # 正の値にできない
    if not ok:
        # 絶対値が小さい順にソート
        A.sort(key=lambda x:abs(x))
        for i in range(K):
            ans *= A[i]
            ans %= MOD
    else:
        P.sort()
        M.sort(reverse=True)
        if K%2== 1:
            ans *= P.pop()
            ans %= MOD
        pair = []
        # 2個ずつ処理する
        while len(P) >= 2:
            x = P.pop()
            x *= P.pop()
            pair.append(x)
        while len(M) >= 2:
            x = M.pop()
            x *= M.pop()
            pair.append(x)
        pair.sort(reverse=True)
        for i in range(K//2):
            ans *= pair[i]
            ans %= MOD
    ans %= MOD
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())

MOD = 10 ** 9 + 7
s = []  # v >= 0
t = []  # v < 0
for i in range(N):
    if A[i] < 0:
        t.append(A[i])
    else:
        s.append(A[i])
        
ok = False  # ans > 0
if len(s) > 0:
    if N == K:
        ok = len(t) % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    x = sorted(A, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * x[i] % MOD
else:
    s.sort()
    t.sort(key=lambda x: abs(x))
    if K % 2 == 1:
        ans = ans * s.pop() % MOD
        
    p = []
    while len(s) >= 2:
        x = s.pop() * s.pop()
        p.append(x)
    
    while len(t) >= 2:
        x = t.pop() * t.pop()
        p.append(x)

    p.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * p[i] % MOD
    
print(ans)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
MOD = 10**9 + 7
def main(N, K, A):
    neg = pos = zer = 0
    for a in A:
        if a < 0: neg += 1
        elif a > 0: pos += 1
        else: zer += 1
    # print(neg, pos, zer, N - K)

    if N - K < zer:
        # ゼロになっちゃう
        return 0
    N -= zer
    A = sorted([a for a in A if a != 0], key=lambda x: abs(x))

    if (pos == 0 and K & 1) or (neg & 1 and N == K):
        # マイナスになっちゃう
        if zer:
            # ゼロにもできるじゃん
            return 0
        else:
            ans = Mint(1)
            for i in range(K):
                ans *= abs(A[i])
            return -ans

    # プラスにできる
    A.reverse()
    positives = []
    negatives = []
    # 絶対値の大きい方からK個取る
    for i in range(K):
        if A[i] > 0: positives.append(A[i])
        else: negatives.append(A[i])

    if len(negatives) & 1:
        # マイナスになっちゃった
        # マイナスを1手戻す
        nn = [negatives.pop()]
        pp = []
        rem = 1
        if positives:
            # プラスも1手戻す
            pp.append(positives.pop())
            rem = 2

        # 残りの人たちを探索
        for i in range(K, N):
            if A[i] < 0: nn.append(A[i])
            else: pp.append(A[i])
        # print(pp[:5])
        # print(nn[:5])

        if rem == 2:
            # マイナスのペアかプラスのペアを作る
            if len(nn) >= 2 and len(pp) < 2:
                # マイナスのペアだけ作れる
                negatives.append(nn[0])
                negatives.append(nn[1])
            elif len(pp) >= 2 and len(nn) < 2:
                # プラスのペアだけ作れる
                positives.append(pp[0])
                positives.append(pp[1])
            elif len(pp) >= 2 and len(nn) >= 2:
                # どっちも作れるなら掛けて大きい方
                if pp[0] * pp[1] > nn[0] * nn[1]:
                    positives.append(pp[0])
                    positives.append(pp[1])
                else:
                    negatives.append(nn[0])
                    negatives.append(nn[1])
            else:
                # どっちも作れないなんてことはない
                assert False
        else:
            # プラスをもう一つ選ぶ
            positives.append(pp[0])

    # 答えを計算
    ans = Mint(1)
    for p in positives:
        ans *= p
    for n in negatives:
        ans *= abs(n)
    return ans

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    print(main(N, K, A))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
from copy import deepcopy
mod = 10**9 + 7

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a = sorted(a, key=lambda x: abs(x))[::-1]
a_plus = [int(x) for x in a if x > 0]
a_minus = [int(x) for x in a if x < 0]
a_abs = [abs(x) for x in a]

def calc(x):
    res = 1
    for i in x:
        res*=abs(i)
        res %= mod 
    return res

max_a = a[:k]
max_a_minus = []
max_a_plus = []
minus_cnt = 0

for i in max_a:
    if i == 0:
        print(0)
        sys.exit()
    if i < 0:
        minus_cnt += 1
        max_a_minus.append(i)
    else:
        max_a_plus.append(i)

if minus_cnt % 2 == 0:
    print(calc(max_a))
    sys.exit()

plus_cnt = k - minus_cnt

if len(a_minus) <= minus_cnt and len(a_plus) <= plus_cnt:
    ans = -float('inf')
elif len(a_minus) <= minus_cnt:
    if len(max_a_minus) == 0:
        ans = -float("inf")
    else:
        max_a_minus.pop()
        max_a_plus.append(a_plus[plus_cnt])
        ans = calc(max_a_plus + max_a_minus)
elif len(a_plus) <= plus_cnt:
    if len(max_a_plus) == 0:
        ans = -float("inf")
    else:
        max_a_plus.pop()
        max_a_minus.append(a_minus[minus_cnt])
        ans = calc(max_a_minus + max_a_plus)
else:
    flag1 = 1
    flag2 = 1
    if len(max_a_minus) == 0:
        ans1 = -float("inf")
        flag1 = 0
    if len(max_a_plus) == 0:
        ans2 = -float("inf")
        flag2 = 0
    if flag1:
        c1 = deepcopy(max_a_minus)
        c2 = deepcopy(max_a_plus)
        d1 = abs(c1.pop()); d2 = abs(a_plus[plus_cnt])
        c2.append(a_plus[plus_cnt])
        ans1 = calc(c1 + c2)
    if flag2:
        c3 = deepcopy(max_a_minus)
        c4 = deepcopy(max_a_plus)
        d3 = abs(c4.pop()); d4 = abs(a_minus[minus_cnt])
        c3.append(a_minus[minus_cnt])
        ans2 = calc(c3 + c4)
    if flag1 and flag2:
        ans = ans1 if d2*d3 > d1*d4 else ans2
    else:
        ans = max(ans1, ans2)

a_abs = a_abs[::-1]
ans2 = -calc(a_abs[:k])
if ans != -float("inf"):
    print(ans%mod)
else:
    print(ans2%mod)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
i=0
for _ in k//2*'_':
 x=a[i]*a[i+1]
 if x*b>a[-1]*a[-2]*b:s*=x;i+=2
 else:s*=p()*p()
 s%=10**9+7
print(s)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
s=b=~k%2or a.pop()
j=1
for _ in k//2*'_':
 if(x:=a[i]*a[i+1])*b>(y:=a[-j]*a[~j])*b:s*=x;i+=2
 else:s*=y;j+=2
 s%=10**9+7
print(s)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
j=1
for _ in k//2*'_':
 if(x:=a[i]*a[i+1])*b>(y:=a[-j]*a[~j])*b:s*=x;i+=2
 else:s*=y;j+=2
 s%=10**9+7
print(s)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
for _ in k//2*'_':
 if(x:=a[i]*a[i+1])*b>a[-1]*a[-2]*b:s*=x;i+=2
 else:s*=p()*p()
 s%=10**9+7
print(s)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(i:=0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
for _ in k//2*'_':
 x=a[i]*a[i+1]
 if x*b>a[-1]*a[-2]*b:s*=x;i+=2
 else:s*=p()*p()
 s%=10**9+7
print(s)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

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

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        vec = []
        if K & 1:
            vec.append(pos.pop())

        tmp = []
        while len(neg) >= 2:
            tmp.append(neg.pop() * neg.pop())
        while len(pos) >= 2:
            tmp.append(pos.pop() * pos.pop())

        tmp.sort(reverse=True)
        vec.extend(tmp[: K // 2])

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a.sort()
s=1
a=a[-k*(a[-1]<0<k%2):]
while k-y>1:
 if(t:=a[y]*a[y+1])>a[-1]*a[-2]:s=s*t%M;y+=2
 else:s=s*a.pop()%M;k-=1
if k-y:s*=a[-1]
print(s%M)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    pos = [a for a in A if a >= 0]
    neg = [a for a in A if a < 0]

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

    if N == K:
        vec = A
    elif N == len(neg):
        if K & 1:
            vec = neg[:K]
        else:
            vec = neg[-K:]
    else:
        ans_pos = []
        ans_neg = []
        for _ in range(K):
            if not pos:
                ans_neg.append(neg.pop())
            elif not neg:
                ans_pos.append(pos.pop())
            elif pos[-1] > -neg[-1]:
                ans_pos.append(pos.pop())
            else:
                ans_neg.append(neg.pop())

        if (len(ans_neg) & 1) and ((not ans_pos) or (ans_pos[-1] != 0)):
            if not pos or not ans_neg:
                drop_pos = True
            elif not neg or not ans_pos:
                drop_pos = False
            else:
                drop_pos = pos[-1] * ans_pos[-1] < neg[-1] * ans_neg[-1]

            if drop_pos:
                ans_neg.append(neg.pop())
                ans_pos.pop()
            else:
                ans_pos.append(pos.pop())
                ans_neg.pop()

        vec = ans_pos + ans_neg

    ans = 1
    for a in vec:
        ans = ans * a % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a.sort()
x=s=1
a=a[-k*(a[-1]<0<k%2):]
while x+y<k:
 if(t:=a[y]*a[y+1])>a[-x]*a[~x]:s=s*t%M;y+=2
 else:s=s*a[-x]%M;x+=1
print(s*(x+y-k or a[-x])%M)

Submission status: Accepted

Solution code:
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a.sort()
x=s=1
while x+y<k:
 if(t:=a[y]*a[y+1])>a[-x]*a[~x]:s=s*t%M;y+=2
 else:s=s*a[-x]%M;x+=1
s*=x+y-k or a[-x]
if a[-1]<0<k%2:
 s=1
 for i in a[-k:]:s=s*i%M
print(s%M)

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
MOD=10**9+7
plus=[]
minus=[]
zero=[]
for i in range(n):
  if a[i]>0:
    plus.append(a[i])
  if a[i]<0:
    minus.append(a[i])
  if a[i]==0:
    zero.append(a[i])
if k==n:
  ans=1
  for i in range(k):
    ans=(ans*a[i])%MOD
  print(ans)
  sys.exit()
if len(plus)==0:
  if k%2!=0:
    a.reverse()
  ans=1
  for i in range(k):
    ans=(ans*a[i])%MOD
  print(ans)
  sys.exit()
if len(plus)+len(minus)<k:
  print(0)
  sys.exit()
m=len(minus)
minus.sort()
plus.reverse()
plpointer=k
if k>len(plus):
  plpointer=2*(len(plus)//2)
  if k%2==1:
    if plpointer+1<=len(plus):
      plpointer+=1
    else:
      plpointer-=1
mnpointer=k-plpointer
while mnpointer<m-1 and plpointer>=2 and minus[mnpointer]*minus[mnpointer+1]>plus[plpointer-1]*plus[plpointer-2]:
  mnpointer+=2
  plpointer-=2
ans=1
for i in range(mnpointer):
  ans=(ans*minus[i])%MOD
for i in range(plpointer):
  ans=(ans*plus[i])%MOD
print(ans)

Submission status: Accepted

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        return
    if n==k or k%2 and not x:
        c=1
        for i in sorted(x+y)[-k:]:
            c=c*i%M
        print(c)
        return
    x=sorted(x)[::-1][:k]
    i=len(x)
    y.sort()
    m=len(y)
    j=k-i
    if j%2:
        x=x[:-1]
        i-=1
        j+=1
    x+=y[:j]
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

Submission status: Accepted

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*Mini > plus*Plus:
            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: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod  = int(1e9+7)

n,k = map(int,input().split())
L = list(map(int,input().split()))
ans = 1 
if k==n:
    for i in L:
        ans*=i
        ans%=mod
    print(ans%mod)
    sys.exit()

pos = []
neg = []
for i in L:
    if i>=0:
        pos.append(i)
    else:
        neg.append(i)

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

if len(pos) == 0 and k%2!=0:
    for i in range(1,k+1):
        ans *= neg[-i]
        ans %= mod
    print(ans%mod)
    sys.exit()

if k%2!=0:
    ans*=pos.pop(0)
    k-=1

l=[]
for i in range(1,len(pos),2):
    l.append(pos[i]*pos[i-1])
    
for i in range(1,len(neg),2):
    l.append(neg[i]*neg[i-1])

l.sort(reverse = True)
for i in range(k//2):
    ans *= l[i]
    ans %= mod
print(ans%mod)

Submission status: Accepted

Solution code:
import copy

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

mod = 10**9 + 7

Am, Ap = [], []
pm = [0, 0]
B = []

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

if N == K:
  print(ans(A))
  exit()

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

Am.sort()

if pm[0] == N:
  if K%2 == 0:
    print(ans(Am[N-K:]))
  else:
    print((-1 * ans(Am[:K]))%mod)
  exit()

P = []
B.sort(reverse = True)

cnt = 0

p_min = (-1, -1)
m_min = (-1, -1)

for i in range(K):
  P.append(B[i][0])
  cnt ^= B[i][1]
  if B[i][1] == 0:
    p_min = (B[i][0], i)
  else:
    m_min = (B[i][0], i)

if cnt == 0:
  print(ans(P))
  exit()

P1 = copy.deepcopy(P)
P2 = copy.deepcopy(P)

p_max = (-1, -1)
m_max = (-1, -1)

for i in range(K, N):
  if B[i][1] == 0:
    p_max = (B[i][0], i)
    break

for i in range(K, N):
  if B[i][1] == 1:
    m_max = (B[i][0], i)
    break

Flag1 = False
Flag2 = False

if p_min[1] != -1 and m_max[1] != -1:
  Flag1 = True
  P1[p_min[1]] = 1
  P1.append(m_max[0])
  ans1 = ans(P1)

if m_min[1] != -1 and p_max[1] != -1:
  Flag2 = True
  P2[m_min[1]] = 1
  P2.append(p_max[0])
  ans2 = ans(P2)

if Flag1 and Flag2:
  if m_min[0]*m_max[0] > p_min[0]*p_max[0]:
    print(ans1)
  else:
    print(ans2)
elif Flag1:
  print(ans1)
else:
  print(ans2)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

pos = []
neg = []
MOD = 10**9+7

for i in a:
    if i >= 0: pos.append(i)
    else: neg.append(i)

if n==k:
    ans = 1
    for i in a:
        ans *= i
        ans %= MOD
    print(ans)

elif pos == []: # 全部負
    if k%2==0:
        neg.sort()
        ans = 1
        for i in range(k):
            ans *= neg[i]
            ans %= MOD
        print(ans)
    else:
        neg.sort(reverse=True)
        ans = 1
        for i in range(k):
            ans *= neg[i]
            ans %= MOD
        print(ans%MOD)
            
else: #正もいる
    pos.sort()
    neg.sort(reverse=True)
    if k&1:
        ans = pos.pop()%MOD
    else:
        ans = 1
    
    res = []
    while len(pos)>1:
        x,y=pos.pop(),pos.pop()
        res.append(x*y)
    while len(neg)>1:
        x,y=neg.pop(),neg.pop()
        res.append(x*y)

    res.sort(reverse=True)
    for i in range(k//2):
        ans *= res[i]
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
a,b,i=0,1,0
mod=10**9+7
ans=1
while i<K-1:
  if A[a]*A[a+1]>A[-b]*A[-b-1]:
    ans*=A[a]*A[a+1]
    ans%=mod
    a+=2
    i+=2
  else:
    ans*=A[-b]
    ans%=mod
    b+=1
    i+=1
if i==K-1:
  ans*=A[-b]
  ans%=mod
if A[-1]<0 and K%2==1:
  ans=1
  for i in A[N-K:]:
    ans*=i
    ans%=mod
print(ans%mod)

Submission status: Accepted

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

# パターン1: K == N のとき
if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# 非負整数Pと負整数Mに分ける
P = []
M = []
for a in A:
    if a >= 0:
        P.append(a)
    elif a < 0:
        M.append(a)

# パターン2: すべて負の数 かつ Kが奇数のとき
if len(P) == 0 and K % 2 == 1:
    ans = 1
    M.sort(reverse=True)
    for k in range(K):
        ans *= M[k]
        ans %= MOD
    print(ans)
    exit()

# パターン3: それ以外
P.sort(reverse=True)
M.sort()
LP = len(P)  # LP: リストPの長さ
LM = len(M)  # LM: リストMの長さ
cur_p = 0    # cur_p: リストP内での位置
cur_m = 0    # cur_m: リストM内での位置
cnt = 0      # cnt: 選んだ要素の数
ans = 1      # ans: 答え mod(10**9 + 7)
while cnt < K:  # 要素をK個選ぶまで続ける
    if K - cnt == 1 or LM - cur_m <= 1:  # 既にK-1個選んだ or Mが残り1個以下 のとき必ずPから選ぶ
        flag = 'p'
    elif LP - cur_p == 1:  # Pが残り1個のとき
        if (K - cnt) % 2 == 1:  # 残り奇数個選ぶとき、Pの最後の要素は必ず選ばれる.
            flag = 'p'
        else:                   # 残り偶数個選ぶとき、Pの最後の要素は選んではいけない.
            flag = 'm'
    elif LP - cur_p == 0:  # Pが残り0個のとき
        flag = 'm'
    else:  # Pが残り2個以上 かつ Mが残り2個以上 のとき
        p1 = P[cur_p]
        p2 = P[cur_p + 1]
        m1 = M[cur_m]
        m2 = M[cur_m + 1]
        if p1 * p2 >= m1 * m2:
            flag = 'p'
        else:
            flag = 'm'
    
    if flag == 'p':  # Pから選ぶときは1個選ぶ
        ans *= P[cur_p]
        ans %= MOD
        cur_p += 1
        cnt += 1
    else:  # Mから選ぶときは2個同時に選ぶ
        ans *= M[cur_m] * M[cur_m + 1]
        ans %= MOD
        cur_m += 2
        cnt += 2

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse = True)
ans = 1
p = 0
m = 0
plus = []
minus = []
use = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            use.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            use.append(a[i])
            ans *= -a[i]
            ans %= mod
if f:
    ans = -ans
if ans < 0:
    if k == n:
        print(ans % mod)
    elif p == 0:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in range(k):
            ans *= -a[i]
            ans %= mod
        if k % 2:
            ans = -ans
        print(ans % mod)
    else:
        for i in range(k, n):
            if a[i] < 0:
                break
        else:
            ans = -ans
            ans *= pow(-minus[-1], mod-2, mod)
            ans *= max(a[k:])
            print(ans % mod)
            quit()
        if plus:
            ans = -ans
            ans *= pow(plus[-1], mod-2, mod)
            ans %= mod
            ans *= pow(-minus[-1], mod-2, mod)
            ans %= mod
            ans1 = plus[-1] * max(a[k:])
            ans2 = minus[-1] * min(a[k:])
            print(max(ans1, ans2) * ans % mod)
        else:
            ans = -ans
            ans *= pow(-minus[-1], mod-2, mod)
            ans %= mod
            ans *= max(a[k:])
            print(ans % mod)
else:
    print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
c = []
d = 1
m = 10**9+7
for i in range(n):
    if a[i] < 0:
        c.append(a[i])
    else:
        b.append(a[i])
b.sort()
c.sort(reverse=True)
if len(b) == 0 and k%2 == 1:
    for i in range(k):
        d = d*c[i]%m
else:
    while k > 0:
        if len(b) > 1 and len(c) > 1:
            if b[-1]*b[-2] < c[-1]*c[-2] and k > 1:
                d = d*c.pop()%m
                d = d*c.pop()%m
                k -= 2
            else:
                d = d*b.pop()%m
                k -= 1
        elif len(b) == 1 and len(c) > 1:
            if k > 1:
                d = d*c.pop()%m
                d = d*c.pop()%m
                k -= 2
            else:
                d = d*b.pop()%m
                k -= 1
        elif len(b) >= 1 and len(c) <= 1:
            d = d*b.pop()%m
            k -= 1
        else:
            d = d*c.pop()%m
            k -= 1
print(d)