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:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort(key = lambda x:-abs(x))
    p = 0
    m = 0
    for i in a:
        if i >= 0:
            p += 1
        else:
            m += 1
    f = 1
    for x in range(min(p,k)+1):
        y = k-x
        if y < 0 or y > m:
            continue
        if not y&1:
            f = 0
            break
    if f:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in a[:k]:
            ans *= i
            ans %= mod
        print(ans)
        return
    minus = []
    s = 1
    s2 = 1
    k1 = 0
    k2 = 0
    ans = 1
    if k&1:
        m = max(a)
        for i in range(n):
            if a[i] == m:
                break
        a = a[:i]+a[i+1:]
        ans *= m
        k -= 1
    for i in a:
        if i < 0:
            k1 ^= 1
            s *= -i
            if not k1:
                minus.append(s)
                s = 1
        else:
            k2 ^= 1
            s2 *= i
            if not k2:
                minus.append(s2)
                s2 = 1
    x = k>>1
    minus.sort(reverse = True)
    for m in minus[:x]:
        ans *= m
        ans %= mod
    print(ans%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if t:
        if max(a) <= 0:
            ans = 1
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
            print(ans)
        else:
            A = min(a[k:])
            B = max(a[k:])
            if A >= 0:
                ans *= pow(L, mod - 2, mod)
                ans *= B
            else:
                if A * L > B * R:
                    ans *= pow(R, mod - 2, mod)
                    ans *= A
                else:
                    ans *= pow(L, mod - 2, mod)
                    ans *= B
            print(ans % mod)
    else:
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
aa = list(map(np.int64, input().split()))
aa = np.array(aa)

def mul(dd):
    mod = 10**9+7
    ret = 1
    for d in dd:
        ret = (ret*d)%mod
    return ret

def sol(aa, n, k):
    mod = 10**9+7
    aap = aa[aa>0]
    aam = aa[aa<0]
    if n == k:
        return mul(aa)
    if len(aap) + 2*(len(aam)//2) < k:
        return 0

    # マイナスのみ
    if len(aam) == n:
        aam.sort()
        if k%2==1:
            return mul(aam[-k:])
        else:
            return mul(aam[:k])

    aap = aa[aa>=0]
    aap.sort()
    aap = aap[::-1]
    aam.sort()

    ret=1
    if k%2 >0:
        k = k-1
        ret *= aap[0]
        aap = aap[1:]

    aap2 = [aap[2*i]*aap[2*i+1] for i in range(len(aap)//2)]
    aam2 = [aam[2*i]*aam[2*i+1] for i in range(len(aam)//2)]
    aap2.extend(aam2)
    aap2.sort(reverse=True)
    aap2 = [i%mod for i in aap2]
    return (ret*mul(aap2[:k//2]))%mod
print(sol(aa, n, k))

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
la = list(map(int,input().split()))
la = sorted(la)
la = sorted(la,key=abs,reverse=True)
lg = la[:K]
lgp = []
lgm = []
lr = la[K:]
lrp = []
lrm = []
for a in lg:
    if a >= 0:
        lgp.append(a)
    else:
        lgm.append(a)
for a in lr:
    if a >= 0:
        lrp.append(a)
    else:
        lrm.append(a)
if len(lgm) % 2 == 1:
    if len(lrp) > 0 and len(lrm) > 0:
        if len(lgp) > 0 and len(lgm) > 0:
            if lgp[len(lgp) - 1] * lrp[0] > lgm[len(lgm) - 1] * lrm[0]:
                lg.pop(lg.index(lgm[len(lgm) - 1]))
                lg.append(lrp[0])
            else:
                lg.pop(lg.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
        else:
            if len(lgp) > 0:
                lg.pop(lg.index(lgp[len(lgp) - 1]))
                lg.append(lrm[0])
            else:
                lg.pop(lg.index(lgm[len(lgm) - 1]))
                lg.append(lrp[0])
    elif len(lrp) > 0:
        if len(lgm) > 0:
            lg.pop(lg.index(lgm[len(lgm) - 1]))
            lg.append(lrp[0])
        else:
            lg = la[N - K:]
    elif len(lrm) > 0:
        if len(lgp) > 0:
            lg.pop(lg.index(lgp[len(lgp) - 1]))
            lg.append(lrm[0])
        else:
            lg = la[N - K:]
ans = 1
for a in lg:
    ans *= a
    ans %= 10 ** 9 + 7
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

# https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#3-1-mod-p-%E3%81%AE%E4%B8%96%E7%95%8C%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E5%89%B2%E3%82%8A%E7%AE%97%E3%81%A8%E3%81%AF


def modinv(a):
  b = MOD
  u = 1
  v = 0
  while b != 0:
    t = a // b
    a -= t * b
    a, b = b, a
    u -= t * v
    u, v = v, u
  u %= MOD
  if u < 0:
    u += MOD
  return u


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

# a = [e for e in a if e != 0]

# if len(a) < k:
#   print(0)
#   exit()

a.sort(key=lambda x: abs(x), reverse=True)

b = a[:k]
c = a[k:]

n = 0
pro_abs_b = 1
for e in b:
  if e < 0:
    n += 1
  pro_abs_b *= abs(e)
  pro_abs_b %= MOD
pro_b = (-1)**n * pro_abs_b % MOD

n_ = 0
pro_abs_ = 1
for e in a[len(a) - k:]:
  if e < 0:
    n_ += 1
  pro_abs_ *= abs(e)
  pro_abs_ %= MOD
pro_ = (-1) ** n_ * pro_abs_ % MOD

if n % 2 == 0:
  print(pro_b)
  exit()

anses = []
last_posinb = None
last_neginb = None
for e in b:
  if e > 0:
    last_posinb = e
  if e < 0:
    last_neginb = e
first_posinc = None
first_neginc = None
for e in reversed(c):
  if e > 0:
    first_posinc = e
  if e < 0:
    first_neginc = e

# print(last_posinb, last_neginb)
# print(first_posinc, first_neginc)
if last_posinb is not None and first_neginc is not None:
  anses.append((-first_neginc / last_posinb, pro_b *
                modinv(last_posinb) * first_neginc % MOD))
if last_neginb is not None and first_posinc is not None:
  anses.append((-first_posinc / last_neginb, pro_b *
                modinv(last_neginb) * first_posinc % MOD))

if len(anses) != 0:
  print(max(anses)[1])
else:
  print(pro_)

Submission status: Accepted

Solution code:
from math import log10
n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9+7
a.sort()

cnt_neg = 0
cnt_pos = 0
for i in a:
   if i <= 0:
      cnt_neg += 1
   else:
      cnt_pos += 1
is_minus = False
k_tmp = k
while k_tmp > 0:
   if k_tmp >= 2:
      if cnt_neg >= 2:
         cnt_neg -= 2
      elif cnt_pos >= 2:
         cnt_pos -= 2
      else:
         is_minus = True
         break
      k_tmp -= 2
   else:
      if cnt_pos > 0:
         cnt_pos -= 1
         k_tmp -= 1
      else:
         is_minus = True
         break

k_1 = k
ans1 = 1
l = 0
r = n - 1
if k_1 % 2:
   ans1 *= a[-1]
   r -= 1
   k_1 -= 1
while k_1 >= 2:
   if a[l] * a[l+1] > a[r-1] * a[r]:
      ans1 *= a[l] * a[l+1]
      l += 2
   else:
      ans1 *= a[r-1] * a[r]
      r -= 2
   k_1 -= 2
   ans1 %= MOD

a.sort(key=abs)
# print(a)
ans2 = 1
for i in a[:k]:
   ans2 *= i
   ans2 %= MOD

if is_minus:
   print(ans2)
else:
   print(ans1)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    import bisect
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    a.sort()
    que = deque()

    if n == k:
        que.extend(a)
    elif a[-1] < 0 and k % 2 == 1:
        que.extend(a)
        for _ in range(n - k):
            que.popleft()
    else:
        pos_ = []
        neg_ = []
        for x in a:
            if x >= 0:
                pos_.append(x)
            else:
                neg_.append(x)
        pos = deque(sorted(pos_, reverse=True))
        neg = deque((sorted(neg_)))
        while len(que) < k:
            if len(pos) >= 2:
                pp = pos[0] * pos[1]
            else:
                pp = -1
            if len(neg) >= 2:
                np = neg[0] * neg[1]
            else:
                np = -1
            if (pp > np) or len(que) == (k-1):
                que.append(pos.popleft())
            else:
                que.append(neg.popleft())
                que.append(neg.popleft())

    while len(que) > 1:
        que.append(que.popleft() * que.popleft())

    print(que.popleft() % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    import bisect
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    a.sort()
    que = deque()

    if n == k:
        que.extend(a)
    elif a[-1] < 0 and k % 2 == 1:
        que.extend(a)
        for _ in range(n - k):
            que.popleft()
    else:
        b = [[] for _ in range(n)]
        for i in range(n):
            b[i] = [abs(a[i]), a[i]]
        b.sort(reverse=True)
        b = deque(b)
        que1 = deque()
        que2 = deque()
        sign = 1

        for i in range(k):
            val_abs, val = b.popleft()
            if val > 0:
                que1.append(val_abs)
            elif val < 0:
                que2.append(val_abs)
                sign *= -1
            else:
                print(0)
                return

        if sign == -1:
            add1, add2 = 0, 0
            rmv1, rmv2 = 10 ** 19, 10 ** 19
            if que1:
                rmv1 = que1[-1]
                for x_abs, x in b:
                    if x < 0:
                        add1 = x_abs
                        break
            if que2:
                rmv2 = que2[-1]
                for x_abs, x in b:
                    if x > 0:
                        add2 = x_abs
                        break

            if add1 == add2:
                print(0)
                return

            if add1 * rmv2 > add2 * rmv1:
                que2.append(add1)
                que1.pop()
            else:
                que1.append(add2)
                que2.pop()

        que.extend(que1)
        que.extend(que2)

    while len(que) > 1:
        que.append(que.popleft() * que.popleft())

    print(que.popleft() % MOD)


if __name__ == '__main__':
    main()

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
        
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
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [], []
    for i in range(n):
        if a[i] < 0:
            t.append(a[i])
        else:
            s.append(a[i])

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
            ans %= mod
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
            ans %= mod
        p = []
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p.append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p.append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
            ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 1
    s, t = [], []
    for i in range(n):
        if a[i] < 0:
            t.append(a[i])
        else:
            s.append(a[i])
    # s, t = [i for i in a if i > 0], [j for j in a if j < 0]

    S, T = len(s), len(t)
    ok = False

    if S > 0:
        if n == k:
            ok = (T % 2 == 0)
        else:
            ok = True
    else:
        ok = (k % 2 == 0)

    if not ok:
        a.sort(key=abs)
        for i in range(k):
            ans *= a[i]
            ans %= mod
    else:
        s.sort()
        t.sort(reverse=True)
        if k % 2 == 1:
            ans *= s.pop()
            ans %= mod
        p = []
        while len(s) >= 2:
            x = s.pop()
            x *= s.pop()
            p.append(x)
        while len(t) >= 2:
            x = t.pop()
            x *= t.pop()
            p.append(x)
        p.sort(reverse=True)
        for i in range(k//2):
            ans *= p[i]
            ans %= mod
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

mod = 10 ** 9 + 7

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

A.sort(reverse = True)

if A[0] < 0 and K % 2 == 1:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)
    sys.exit()

l = 0
r = N-1

ans = 1
if K % 2 == 1:
    ans *= A[0]
    l += 1

for _ in range(K // 2):
    if A[l] * A[l+1] > A[r] * A[r-1]:
        ans *= A[l] * A[l+1]
        ans %= mod
        l += 2
    else:
        ans *= A[r] * A[r-1]
        ans %= mod
        r -= 2

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
ans=1
if n==k or max(a)<0 or min(a)>=0:
    if max(a)<0 and k%2==0:
        a.sort()
    else:
        a.sort(reverse=True)
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
pos,neg=[],[]
for num in a:
    if num<0:
        neg.append(-num)
    else:
        pos.append(num)
neg.sort(reverse=True)
pos.sort(reverse=True)
nn=len(neg)
np=len(pos)
cand=[]
i,j=0,0
while k>0:
    if i<np-1 and j<nn-1:
        if k>=2:
            if pos[i+1]*pos[i]<neg[j+1]*neg[j]:
                cand.append(-neg[j+1])
                cand.append(-neg[j])
                k-=2
                j+=2
            else:
                cand.append(pos[i])
                k-=1
                i+=1
        else:
            cand.append(pos[i])
            k-=1
            i+=1
    elif j>=nn-1:
        cand.append(pos[i])
        k-=1
        i+=1
    elif i==np-1:
        if k==1:
            cand.append(pos[i])
            i+=1
            k-=1
        else:
            cand.append(-neg[j+1])
            cand.append(-neg[j])
            j+=2
            k-=2
    elif i==np:
        cand.append(-neg[j+1])
        cand.append(-neg[j])
        j+=2
        k-=2
for num in cand:
    ans*=num
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

mod=10**9+7
n,k=map(int,input().split())
A=list(map(int,input().split()))
cnt=k

B,C=[],[]
for i in range(n):
    num=A[i]
    if num>=0:B.append(num)
    else:C.append(num)

B.sort(reverse=True)
C.sort()
B,C=deque(B),deque(C)

ans,flag=1,1
while k!=0:
    num=0
    length_B,length_C=len(B),len(C)
    if k>=2:
        if length_B>=2 and length_C>=2:
            plus=B[0]*B[1]
            negative=C[0]*C[1]
            if plus>negative:
                ans *=B.popleft()
                num=1
            else:ans *=C.popleft()*C.popleft()
        elif length_C>=2:ans *=C.popleft()*C.popleft()
        elif length_B>=2:ans *=B.popleft()*B.popleft()
        else:
            ans *=B.popleft()*C.popleft()
            flag=0
        k -=2-num
    else:
        if 0<length_B:ans *=B.popleft()
        elif 0<length_C:
            ans *=C.popleft()
            flag=0
        k -=1
    ans %=mod

if flag:print(ans);exit()

ans=1
A=sorted(A,key=lambda x:abs(x))
for i in range(cnt):
    ans *=A[i]
    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

neg_a = sorted([a for a in A if a < 0], reverse=True)
pos_a = sorted([a for a in A if a >= 0])
ans = 1

if len(pos_a) == 0 and K % 2 == 1:
    for a in neg_a[:K]:
        ans = ans * a % MOD
    print(ans)
    exit()

while K > 0:
    if K == 1 or len(neg_a) <= 1:
        if len(pos_a) == 0:
            ans *= neg_a.pop()
        elif len(pos_a) > 0:
            ans *= pos_a.pop()
        K -= 1
    elif len(pos_a) <= 1:
        ans *= neg_a.pop() * neg_a.pop()
        K -= 2
    elif pos_a[-1] * pos_a[-2] > neg_a[-1] * neg_a[-2]:
        ans *= pos_a.pop()
        K -= 1
    else:
        ans *= neg_a.pop() * neg_a.pop()
        K -= 2
    ans %= MOD

print(ans)

Submission status: Accepted

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
B = []
C = []
for a in A:
    if a >= 0:
        B.append(a)
    else:
        C.append(-a)

ans = 1
if len(B) == 0 and K % 2 == 1:
    C = sorted(C)
    for i in range(K):
        ans *= -C[i]
        ans %= MOD
    print(ans)
    sys.exit()
      
negs_p = 0
non_negs_p = 0
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)

for i in range(K):
    if negs_p == len(C):
        non_negs_p += 1
    elif non_negs_p == len(B):
        negs_p += 1
    elif C[negs_p] > B[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
        
if N == K or negs_p % 2 == 0:
    for i in range(non_negs_p):
        ans = ans * B[i] % MOD
    for i in range(negs_p):
        ans = ans * -C[i] % MOD
    print(ans)
    sys.exit()

if negs_p % 2 == 1:
    if negs_p == len(C) or non_negs_p == 0:
        negs_p -= 1
        non_negs_p += 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
    elif non_negs_p == len(B) or negs_p == 0:
        negs_p += 1
        non_negs_p -= 1 
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
    else:
        a,b,c,d = C[negs_p],C[negs_p-1],B[non_negs_p],B[non_negs_p-1]
        if a*b > c*d:
            negs_p += 1
            non_negs_p -= 1
        else:   
            negs_p -= 1
            non_negs_p += 1
        for i in range(non_negs_p):
            ans = ans * B[i] % MOD
        for i in range(negs_p):
            ans = ans * -C[i] % MOD
print(ans)

Submission status: Accepted

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

X = 1

if N == K:
    for a in A:
        X = X * a % MOD
        X %= MOD
    print(X)
    sys.exit()

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

if len(P) == 0:
    if K % 2 != 0:
        M.sort(reverse=True)
        for i in range(K):
            X = X * M[i] % MOD
            X %= MOD
        print(X)
        sys.exit()

P.sort()
M.sort(reverse=True)

if K % 2 != 0:
    X = X * P[-1] % MOD
    X %= MOD
    K -= 1
    P.pop()

PP = []
if len(P) % 2 == 0:
    for i in range(0, len(P), 2):
        PP.append(P[i] * P[i + 1])
else:
    PP.append(P[0])
    for i in range(1, len(P), 2):
        PP.append(P[i] * P[i + 1])
if len(M) % 2 == 0:
    for i in range(0, len(M), 2):
        PP.append(M[i] * M[i + 1])
else:
    for i in range(1, len(M), 2):
        PP.append(M[i] * M[i + 1])
PP.sort(reverse=True)

i = 0
while K > 0:
    X = X * PP[i] % MOD
    X %= MOD
    K -= 2
    i += 1

print(X)

Submission status: Accepted

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = LIST()

pos = []
neg = []
zero = []

for el in a:
    if(el<0):
        neg.append(el)
    elif(el>0):
        pos.append(el)
    else:
        zero.append(el)

pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]

ans = 1

if(k==n or k>len(pos)+len(neg)):
    for el in a:
        ans = (ans%mod*el%mod)%mod
elif(len(pos)+len(neg)==k):
    if(len(neg)%2!=0):
        ans = 0
    else:
        for el in pos:
            ans = (ans%mod*el%mod)%mod
        for el in neg:
            ans = (ans%mod*el%mod)%mod

else:

    if(len(pos)==0):
        if(k%2==0):
            temp = 0
            for i in range(len(neg)-1, -1, -1):
                if(temp==k):
                    break
                ans = (ans%mod*neg[i]%mod)%mod
                temp+=1
            if(temp<k):
                ans = 0
        else:
            temp = 0
            if(0 in a):
                ans = 0
            else:
                for i in range(len(neg) - 1):
                    if (temp == k):
                        break
                    ans = (ans%mod * neg[i]%mod) % mod
                    temp += 1
                if (temp < k):
                    ans = 0
    else:

        left = k

        i,j = 0, len(neg)-1

        while(left>1):
            temp, temp1 = 0, 0
            if(i<len(pos)-1):
                temp = pos[i]*pos[i+1]
                # i+=2
            if(j>=1):
                temp1 = neg[j]*neg[j-1]
                # j-=2
            if(temp==0 and temp1==0):
                break
            if(temp1>temp):
                ans = (ans*(temp1%mod))%mod
                j-=2
            else:
                ans = (ans*(temp%mod))%mod
                i+=2
            left -= 2
        # print(ans,i,j)
        if(left>1):
            ans = 0
        elif(left==1):
            if(i<len(pos)):
                ans = ((ans%mod)*pos[i])%mod
            else:
                ans1 = 1
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
                ans = max(ans, ans1)
        if(k%2!=0):
            ans1 = 1
            if(i-2>=0 and j-2>=-1 and i-2<=len(pos)-1 and j-2<=len(neg)-1):
                for b in range(i-1):
                    ans1 = (ans1%mod*(pos[b]))%mod
                for c in range(len(neg)-1, j-2,-1):
                    ans1 = (ans1%mod*neg[c])%mod
            # print(ans, ans1)
            ans = max(ans, ans1)
print(ans)

Submission status: Accepted

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

m = 1000000007

a = [e for e in A if e > 0]
b = [e for e in A if e < 0]
c = [e for e in A if e == 0]
# プラスルート
if len(a) >= K - (min(K, len(b)) // 2) * 2:
    a.sort(reverse=True)
    b.sort()
    result = 1
    i = 0
    j = 0
    k = 0
    while k < K:
        if k < K - 1 and i < len(a) - 1 and j < len(b) - 1:
            x = a[i] * a[i + 1]
            y = b[j] * b[j + 1]
            if y >= x:
                result *= y
                result %= m
                j += 2
                k += 2
            else:
                result *= a[i]
                result %= m
                i += 1
                k += 1
        elif k < K - 1 and j < len(b) - 1:
            y = b[j] * b[j + 1]
            result *= y
            result %= m
            j += 2
            k += 2
        elif i < len(a):
            result *= a[i]
            result %= m
            i += 1
            k += 1
        elif j < len(b):
            result *= b[j]
            result %= m
            j += 1
            k += 1
    print(result)
# 0 ルート
elif len(c) != 0:
    print(0)
# マイナスルート
else:
    a.sort()
    b.sort(reverse=True)
    result = 1
    i = 0
    j = 0
    k = 0
    while k < K:
        if i < len(a) and j < len(b):
            if a[i] <= -b[i]:
                result *= a[i]
                result %= m
                i += 1
                k += 1
            else:
                result *= b[j]
                result %= m
                j += 1
                k += 1
        elif i < len(a):
            result *= a[i]
            result %= m
            i += 1
            k += 1
        elif j < len(b):
            result *= b[j]
            result %= m
            j += 1
            k += 1
    print(result)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
MOD = 10 ** 9 + 7
s, t = [], []  # 正、負の配列
for i in a:
  if i < 0:
    t.append(i)
  else:
    s.append(i)
S, T = len(s), len(t)
is_positive = False  # 積が正である
if S > 0:
  # 正の数が0より大きい
  if n == k:
    # nとkが同じ
    is_positive = (T % 2 == 0) # 負の数が偶数個のとき、積は正
  else:
    is_positive = True
else:
  is_positive = (k % 2 == 0)

ans = 1
if not is_positive:
  a.sort(key=abs)
  for i in range(k):
    ans = ans * a[i] % MOD
else:
  s.sort()
  t.sort(reverse=True)
  if k % 2 == 1:
    ans = ans * s.pop(-1) % MOD
  p = []
  while(len(s) >= 2):
    x = s.pop(-1)
    x *= s.pop(-1)
    p.append(x)
  while(len(t) >= 2):
    x = t.pop(-1)
    x *= t.pop(-1)
    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:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    plus = [A[i] for i in range(N) if A[i] >= 0]
    minus = [A[i] for i in range(N) if A[i] < 0]

    ans = 1

    P = len(plus)
    M = len(minus)
    plus.sort(reverse=True)
    minus.sort()
    mod = 10**9 + 7

    if N == K:
        for x in A:
            ans *= x
            ans %= mod
    elif P == 0:
        if K % 2 == 1:
            minus.sort(reverse=True)
        for i in range(K):
            ans *= minus[i]
            ans %= mod
    else:  # 必ず正の値が作れる？ 1つ以上余るので、偶奇は選べるはず
        id = 0
        if K % 2 == 1:
            ans = plus[0]
            id = 1
            P -= 1
            K -= 1
        pp = [plus[i] * plus[i+1] for i in range(id, P-1+id, 2)]
        mm = [minus[i] * minus[i+1] for i in range(0, M-1, 2)]

        id = 0
        id2 = 0

        for i in range(K // 2):
            if id < P // 2 and (id2 >= M // 2 or pp[id] >= mm[id2]):
                ans *= pp[id]
                id += 1
            else:
                ans *= mm[id2]
                id2 += 1
            ans %= mod

    print(ans % mod)


main()