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:
# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

    # もしN = K なら全部選択しないといけないので、
    # 全部掛け算して返す
    if N == K:
        ans = 1
        for a in A:
            ans = (ans * a) % MOD
        print(ans)
        return

    Ap = [] # 正の数だけ入っている
    Am = [] # 負の数だけ入っている.値は絶対値で入れる
    has0 = False # 0がAの中にあるか
    for a in A:
        if a == 0:
            has0 = True
        elif a > 0:
            Ap.append(a)
        else:
            Am.append(-a)

    # それぞれを絶対値の大きい順に並べる
    Ap.sort(reverse=True)
    Am.sort(reverse=True)

    ip = 0
    im = 0
    lp = len(Ap)
    lm = len(Am)

    # もし0でない数がK個未満しかない場合、0を必ず選ばないといけないので
    # 答えは0になる
    if lp + lm < K:
        print(0)
        return

    # # 正の数+負の数=K かつ負の数が奇数のとき、0を選んだほうがマシなので、
    # # 答えは0になる
    # if lp + lm == K and lm % 2 == 1:
    #     print(0)
    #     return
    # もしKが奇数のときで、かつ正の数が1個もない時
    if K % 2 == 1 and lp == 0:
        # 0があるなら0にする
        if has0:
            print(0)
            return
        # 0がない場合は、負の数の中から絶対値の小さいものを選ぶ
        else:
            ans = 1
            for a in Am[-K:]:
                ans = (ans * a) % MOD
            print(MOD - ans)
            return

    # 戦略: Aの中から絶対値の大きい順に選んでいく
    ans = 1
    for i in range(K):
        x = None
        if ip == lp: # 正の数をこれ以上選べないのであれば負の数を選ぶ
            x = Am[im]
            im += 1
        elif im == lm: # 負の数をこれ以上選べないのであれば正の数を選ぶ
            x = Ap[ip]
            ip += 1
        # 正の数、負の数どちらも選べるのであれば、絶対値の大きいほうを選ぶ
        elif Am[im] < Ap[ip]:
            x = Ap[ip]
            ip += 1
        else:
            x = Am[im]
            im += 1
        # print(x)
        ans = ans * x % MOD

    # もし絶対値の大きい順で選んで、負の数を奇数個選んでいたとき
    if im % 2 == 1:
        # 選んだ中で一番小さい負の数を外して、まだ選んでない中で最も大きい正の数を入れるか、
        # 選んだ中で一番小さい正の数を外して、まだ選んでない中で最も（絶対値が）大きい負の数を入れるか選ぶ

        # これ以上0でない数がない場合は、0を選択して答えを0にするのが最大値になる
        if ip == lp and im == lm:
            print(0)
            return
        # 正の数をこれ以上選べない場合は負の数から選ぶ
        elif ip == lp:
            ans = ans * modinv(Ap[ip-1]) % MOD
            ans = ans * Am[im] % MOD
        # 負の数をこれ以上選べない場合は正の数から選ぶ
        # 正の数を1つも選んでないときも正の数から選ぶ
        elif im == lm or ip == 0:
            ans = ans * modinv(Am[im-1]) % MOD
            ans = ans * Ap[ip] % MOD
        # 正、負ともまだ選ぶ余裕がある場合
        else:
            # 一旦、選んだ中で一番小さい負の数と、選んだ中で一番小さい正の数を戻す（再度選べるようにする）
            ip -= 1
            ans = ans * modinv(Ap[ip]) % MOD
            im -= 1
            ans = ans * modinv(Am[im]) % MOD
            
            # 正、負のリストから、まだ選んでない中で絶対値が大きいもの2つを選び、その積の大きいほうを選ぶ
            a = Ap[ip] * Ap[ip+1]
            b = Am[im] * Am[im+1]
            # print(a, b)

            ans = ans * max(a, b) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

plus = []
minus = []

for i in a:
	if i >= 0:
		plus.append(i)
	else:
		minus.append(i)

plus.sort(key = lambda x:-x)
minus.sort()

#print(plus, minus)

"""
貪欲チックに求める
numplus … 前からnumplus番目まで掛け合わせる
numminus … 前からnumminus番目まで掛け合わせる

入力例2に合わせるのは場合分けが必要だが, minusは2個単位で管理する.
"""

numplus = k
numminus = 0

"""
kがplusを超える場合, うまく処理ができないのでリスト参照できる範囲まで下げる.
"""
while numplus > len(plus):
	numplus -= 2
	numminus += 2

#print(numplus, numminus)

while numplus-2 >= 0 and numminus+1 < len(minus):
	if plus[numplus-1] * plus[numplus-2] <= minus[numminus] * minus[numminus+1]:
		numplus -= 2
		numminus += 2
	else:
		break

#print(numplus, numminus)

ans = 1

if numplus >= 0 and numminus >= 0 and numminus <= len(minus) and numplus <= len(plus):
	for i in range(numplus):
		ans = ans * plus[i] % mod
	for i in range(numminus):
		ans = ans * minus[i] % mod
else:
	"""
	これは, ansが負になる場合や, minusが1個だけの場合, minusしかない場合, plusしかない場合に使える.
	"""
	#print("ここに来ました！")
	tmp = sorted(a, key=lambda x:-x)
	for i in range(k):
		ans = ans * tmp[i]%mod

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

if N==K:
    T=1
    for a in A:
        T=(T*a)%M
    print(T)
    sys.exit()
elif max(A)<0 and K%2==1:
    A.sort(reverse=True)
    T=1
    for i in range(K):
         T=(T*A[i])%M
    print(T)
    sys.exit()
    
U=list(map(lambda x:max(x,0),A))
U.sort(reverse=True)
U=deque(U)

V=list(map(lambda x:min(x,0),A))
V.sort()
V=deque(V)

T=1
Y=0
while Y<K:
    x1,x2=U[0],U[1]
    y1,y2=V[0],V[1]

    if Y==K-1 or x1*x2>=y1*y2:
        Y+=1
        T=(T*x1)%M
        _=U.popleft()
        U.append(0)
    else:
        Y+=2
        T=(T*y1*y2)%M
        _=V.popleft()
        _=V.popleft()
        V.append(0)
        V.append(0)
print(T)

Submission status: Accepted

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

a_p =[]
a_m =[]
for i in a:
    if i >= 0:
        a_p.append(i)
    else :
        a_m.append(i)

a_p.sort()
a_m.sort(reverse=True)


a_select =[]

if n == k:
    a_select = a
elif len(a_p) == 0 and k%2 == 1:
    for i in range(k):
        a_select.append(a_m[i])


while len(a_select) < k:
    if len(a_select) == k - 1:
        a_select.append(a_p[-1])
        break
    if len(a_p) == 1 and (k-len(a_select))%2 == 1:
        a_select.append(a_p.pop(-1))
    elif len(a_p) == 1 and (k-len(a_select))%2 == 0:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))
    elif len(a_p) == 0:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))
    elif len(a_m) <= 1:
        a_select.append(a_p.pop(-1))
    elif a_p[-1]*a_p[-2] > a_m[-1]*a_m[-2] :
        a_select.append(a_p.pop(-1))
    else:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))

#print(a_select)
ans = 1
for i in a_select:
    ans = ans*i % (10**9 + 7)

print(ans)

Submission status: Accepted

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

allm = True
for a in A:
    if a > 0:
        allm = False
        break

if N == K:
    ans = 1
    for a in A:
        ans = (ans*a) % MOD
    print(ans)
elif allm and K % 2 == 1:
    A.sort()
    A.reverse()
    ans = 1
    for a in A[:K]:
        ans = (ans*a) % MOD
    print(ans)
else:
    p, m = [], []
    for a in A:
        if a > 0:
            p.append(a)
        if a < 0:
            m.append(-a)
    p.sort(key=lambda k: -k)
    m.sort(key=lambda k: -k)

    pi, mi = 0, 0
    ans = 1

    # Kが奇数の場合はplusから最初に一つとっておく
    if K % 2 == 1:
        pi = 1
        ans = p[0]
        K -= 1

    while K > 0:
        if K == 1:
            ans = (ans*p[pi]) % MOD
            break
        elif pi < len(p)-1 or mi < len(m)-1:
            pv, mv = 0, 0
            if pi < len(p)-1:
                pv = p[pi]*p[pi+1]
            if mi < len(m)-1:
                mv = m[mi]*m[mi+1]

            if pv > mv:
                ans = (ans*pv) % MOD
                pi += 2
            else:
                ans = (ans*mv) % MOD
                mi += 2
            K -= 2
        else:
            ans = 0
            break
    print(ans)

Submission status: Accepted

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

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

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

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

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

    for i in range(K, -1, -2):
        if len(plus) < i:continue
        if len(minus) < K - i:continue
        if max_ans == -1:
            max_ans = P[i] * M[K-i] % mod
        else:
            if not plus[i] or not plus[i + 1]:
                max_ans = P[i] * M[K-i] % mod
                continue
            if plus[i+1] * plus[i] <  minus[K-i-2] * minus[K-i-1]:
                max_ans = P[i] * M[K-i] % mod

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

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

    print(max_ans)

if __name__ == "__main__":
    run()

Submission status: Accepted

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

As.sort()
dic = {-1:0, 1:0}
for a in As:
  if a < 0:
    dic[-1] += 1
  else:
    dic[1] += 1

rlt = 1
j = 0
if N == K:
  for a in As:
    rlt *= a
    rlt %= P
  while rlt < 0:
    rlt += P
elif As[N-1] < 0 and K%2 == 1:
  for i in range(1,K+1):
    rlt *= As[-i]
    rlt %= P
  while rlt < 0:
    rlt += P
else:
  s = 0
  i = 0
  j = 1
  while s < K:
    if i+1 >= dic[-1] or s+1 == K:
      rlt *= As[-j]
      rlt %= P
      j += 1
      s += 1
    elif j+1 > dic[1]:
      rlt *= As[i]*As[i+1]
      rlt %= P
      i += 2
      s += 2
    else:
      if As[i]*As[i+1] > As[-j]*As[-(j+1)]:
        rlt *= As[i]*As[i+1]
        rlt %= P
        i += 2
        s += 2
      else:
        rlt *= As[-j]
        rlt %= P
        j += 1
        s += 1
        
print(rlt)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9+7
a1 = []
a2 = []
cnt = 0
for i in a:
    if (i >= 0):
        a1.append(i)
    else:
        a2.append(-i)
a1.sort()
a2.sort()
#print(a1,a2)
if (k==1):
    print(max(a)%mod)
    exit()
if (n==k):
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if (len(a1)==0):
    if (k%2==0):
        ans = 1
        for i in range(k):
            ans *= a2.pop()
            ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= -a2[i]
            ans %= mod
        print(ans)
        exit()
elif (len(a2)==0):
    ans = 1
    for i in range(k):
        ans *= a1.pop()
        ans %= mod
    print(ans)
    exit()

bef1 = 10**10
bef2 = 10**10
index1 = 0
index2 = 0
ans = 1
for i in range(k):
    if (len(a1)==0):
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        bef2 = x
        continue
    if (len(a2)==0 or a1[-1]>=a2[-1]):
        x = a1.pop()
        ans *= x
        ans %= mod
        index1 += 1
        bef1 = x
    else:
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        bef2 = x
if (cnt%2==1):
    if len(a1)>0 and len(a2)>0:
        if (index1==0):
            ans *= a1[-1]
            ans *= pow(bef2,mod-2,mod)
            ans %= mod
        elif (index2==0):
            ans *= a2[-1]
            ans *= pow(bef1,mod-2,mod)
            ans %= mod
        else:
            A = a1[-1]/bef2
            B = a2[-1]/bef1
            if (a1[-1]*bef1>=a2[-1]*bef2):
                ans *= a1[-1]
                ans *= pow(bef2,mod-2,mod)
                ans %= mod
            else:
                ans *= a2[-1]
                ans *= pow(bef1,mod-2,mod)
                ans %= mod
    elif (len(a1)==0):
        ans *= a2[-1]
        ans *= pow(bef1,mod-2,mod)
        ans %= mod
    else:
        ans *= a1[-1]
        ans *= pow(bef2,mod-2,mod)
        ans %= mod
if 0 in a:
    print(max(0,ans%mod))
else:
    print(ans%mod)

Submission status: Accepted

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

plst=sorted([x for x in lst if x>=0],reverse=True)
nlst=sorted([abs(x) for x in lst if x<0],reverse=True)
out=[None for _ in range(k)]
lenn=len(nlst)
lenp=len(plst)



if lenp==0 and k%2==1:
    sm=1
    for i in range(lenn-1,lenn-k-1,-1):
        sm*=-nlst[i]
        sm%=mod
    print(sm)
    exit()

if n==k:
    sm=1
    for x in lst:
        sm*=x
        sm%=mod
    print(sm)
    exit()



ptoken=0
ntoken=0
token=0
pm=0



while token<k:
    if ptoken==lenp:
        out[token]=nlst[ntoken]
        pm=(pm+1)%2
        ntoken+=1
    elif ntoken==lenn:
        out[token]=plst[ptoken]
        ptoken+=1
    elif plst[ptoken]>nlst[ntoken]:
        out[token]=plst[ptoken]
        ptoken+=1
    else :
        out[token]=nlst[ntoken]
        pm=(pm+1)%2
        ntoken+=1
    token+=1

if pm==1:
    if ptoken==lenp:          
        out.remove(plst[ptoken-1])
        out.append(nlst[ntoken])
    elif ntoken==lenn:
        out.remove(nlst[ntoken-1])
        out.append(plst[ptoken])
    elif ptoken==0 : 
        out.remove(nlst[ntoken-1])
        out.append(plst[ptoken])
    else : 
        if nlst[ntoken-1]*nlst[ntoken]>=plst[ptoken-1]*plst[ptoken]:
            out.remove(plst[ptoken-1])
            out.append(nlst[ntoken])
        else :
            out.remove(nlst[ntoken-1])
            out.append(plst[ptoken])               

sm=1
for x in out:
    sm*=x
    sm%=mod

print(sm)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

plus_zero = []
minus = []

for i in a:
    if i >= 0:
        plus_zero.append(i)
    if i < 0:
        minus.append(-i)

from collections import deque

plus_zero = deque(sorted(plus_zero, reverse=True))
minus = deque(sorted(minus, reverse=True))
ans_lst = []
# 境界条件: k == n
if k == n:
    ans_lst.extend(a)
# 負
elif len(plus_zero) == 0 and (k % 2) != 0:
    for _ in range(k):
        ans_lst.append(-minus.pop())
# 正 or 0
else:
    while len(ans_lst) != k:
        if len(ans_lst) == k-1:
            ans_lst.append(plus_zero.popleft())
        else:
            if len(plus_zero) == 0:
                ans_lst.append(minus.popleft())
                ans_lst.append(minus.popleft())
                continue
            if len(plus_zero) == 1:
                if (k - len(ans_lst)) % 2 == 0:
                    ans_lst.append(minus.popleft())
                    ans_lst.append(minus.popleft())
                else:
                    ans_lst.append(plus_zero.popleft())
                continue
            if len(minus) < 2:
                ans_lst.append(plus_zero.popleft())
                continue
            if len(plus_zero) >= 2 and len(minus) >= 2:
                if (plus_zero[0] * plus_zero[1]) >= (minus[0] * minus[1]):
                    ans_lst.append(plus_zero.popleft())
                else:
                    ans_lst.append(minus.popleft())
                    ans_lst.append(minus.popleft())
                continue
# functools.reduceはTLEをくらう場合があるので気をつける
ans = 1
for i in ans_lst:
    ans = (ans * i) % 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

p = []
P = 0
z = False
t = 0
for i in a:
  if i > 0:
    p.append((i,1))
    P += 1
  elif i == 0:
    p.append((0,0))
    z = True
  else:
    p.append((-i,-1))

if P == 0 and k%2 == 1:
  if z:
    print(0)
  else:
    ans = 1
    p.sort()
    for i in range(k):
      ans *= -p[i][0]
      ans %= mod
    print(ans)
  exit()

p.sort(reverse=True)
mi_p = 0
ma_m = 0
c = 0

for i in range(k):
  if p[i][1] > 0:
    mi_p = i
  elif p[i][1] == 0:
    print(0)
    exit()
  else:
    ma_m = i
    c += 1
    
if c%2 == 0:
  ans = 1
  for i in range(k):
    ans *= p[i][0]
    ans %= mod
  print(ans)
elif n == k:
  ans = 1
  for i in a:
    ans *= i
    ans %= mod
  print(ans)
else:
  ma_p = 0
  mi_m = 0
  for i in range(n-k):
    L = p[k+i]
    if L[1] > 0 and ma_p == 0:
      ma_p = p[k+i][0]
    if L[1] < 0 and mi_m == 0:
      mi_m = p[k+i][0]
    if ma_p*mi_m != 0:
      break
  ans_p = 1
  ans_m = 1
  for i in range(k):
    if i == ma_m:
      ans_p *= p[i][0]
    elif i == mi_p:
      ans_m *= p[i][0]
    else:
      ans_p *= p[i][0]
      ans_m *= p[i][0]
    ans_p %= mod
    ans_m %= mod
  if k-c > 1 and mi_m*p[ma_m][0] > ma_p*p[mi_p][0]:
    print(ans_p*mi_m%mod)
  else:
    print(ans_m*ma_p%mod)

Submission status: Accepted

Solution code:
import math
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
plist=[]
mlist=[]
ans=1
p=10**9+7
for i in range(N):
    if A[i]>=0:
        plist.append(A[i])
    else:
        mlist.append(A[i])
if len(plist)==0:
    if K%2==1:
        A.sort(reverse=True)
    else:
        A.sort()
    for i in range(K):
        ans=(ans*A[i])%p
    print(ans%p)
else:
    ans=1
    plist.sort(reverse=True)
    mlist.sort()
    pmap=deque()
    mmap=deque()
    if K%2==1:
        ans=plist[0]%p
        plist.pop(0)
        K=K-1
    #print(plist,mlist)
    for i in range(0,len(plist)-1,2):
        pmap.append(plist[i]*plist[i+1])
    for i in range(0,len(mlist)-1,2):
        mmap.append(mlist[i]*mlist[i+1])
    if len(plist)>0:
        pres=plist[len(plist)-1]
    if len(mlist)>0:
        mres=mlist[len(mlist)-1]
    #print(K)
    mapnum=K//2
    #print(mapnum)
    #print(pmap,mmap,ans)
    for i in range(mapnum):
        if (len(pmap)>0)and(len(mmap)>0):
            pl=pmap.popleft()
            mi=mmap.popleft()
            if pl>mi:
                ans=(ans*pl)%p
                mmap.appendleft(mi)
            else:
                ans=(ans*mi)%p
                pmap.appendleft(pl)
        elif (len(pmap)==0)and(len(mmap)>0):
            mi=mmap.popleft()
            ans = (ans *mi) % p
        elif (len(mmap)==0)and(len(pmap)>0):
            pl=pmap.popleft()
            ans = (ans *pl) % p
        else:
            ans=(ans*pres*mres)%p
    print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
plist=[]
mlist=[]
ans=1
p=10**9+7
for i in range(N):
    if A[i]>=0:
        plist.append(A[i])
    else:
        mlist.append(A[i])
if len(plist)==0:
    if K%2==1:
        A.sort(reverse=True)
    else:
        A.sort()
    for i in range(K):
        ans=(ans*A[i])%p
    print(ans%p)

else:
    ans=1
    plist.sort(reverse=True)
    mlist.sort()
    pmap=deque()
    mmap=deque()
    if K%2==1:
        ans=plist[0]%p
        plist.pop(0)
        K=K-1
    #print(plist,mlist)
    for i in range(0,len(plist)-1,2):
        pmap.append(plist[i]*plist[i+1])
    if len(plist)>0:
        pres=plist[len(plist)-1]
    if len(mlist)>0:
        mres=mlist[len(mlist)-1]
    for i in range(0,len(mlist)-1,2):
        mmap.append(mlist[i]*mlist[i+1])
    #print(K)
    mapnum=K//2
    #print(mapnum)
    #print(pmap,mmap,ans)
    for i in range(mapnum):
        if (len(pmap)>0)and(len(mmap)>0):
            pl=pmap.popleft()
            mi=mmap.popleft()
            if pl>mi:
                ans=(ans*pl)%p
                mmap.appendleft(mi)
            else:
                ans=(ans*mi)%p
                pmap.appendleft(pl)
        elif (len(pmap)==0)and(len(mmap)>0):
            mi=mmap.popleft()
            ans = (ans *mi) % p
        elif (len(mmap)==0)and(len(pmap)>0):
            pl=pmap.popleft()
            ans = (ans *pl) % p
        else:
            ans=(ans*pres*mres)%p
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
A = IL()
A = sorted(A,key= lambda x:-abs(x))

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

if max(A)<0 and K%2==1:
  ans = 1
  for i in range(K):
    ans *= A[N-1-i]
    ans %= MOD
  print(ans)
  exit()

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if A[i] < 0:
    last_M = i
    count_M += 1
  else:
    last_P = i

if count_M%2 == 0:
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans %= MOD
  print(ans)
  exit()

else:
  ANS1 = -INF
  ANS2 = -INF
  if last_M!=None:
    for i in range(K,N):
      if A[i] >= 0:
        CHANGE1 = A[i]
        ans = A[i]%MOD
        for ii in range(K):
          if ii != last_M:
            ans *= A[ii]
            ans %= MOD
        ANS1 = ans
        break
  if last_P!=None:
    for i in range(K,N):
      if A[i] <= 0:
        CHANGE2 = A[i]
        ans = A[i]%MOD
        for ii in range(K):
          if ii != last_P:
            ans *= A[ii]
            ans %= MOD
        ANS2 = ans
        break
  if ANS1 == -INF:
    print(ANS2)
    exit()
  elif ANS2 == -INF:
    print(ANS1)
    exit()
  else:
    if abs(A[last_M]*CHANGE2)<abs(A[last_P]*CHANGE1):
      print(ANS1)
    else:
      print(ANS2)

Submission status: Accepted

Solution code:
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ans=set()
ls=sorted(ls, key=lambda x: -abs(x))
mul=1
sign=0
zeroflag=0
flag=[0 for _ in range(N)]
for i in range(K):
  flag[i]=1
  if ls[i]<0:
    sign=(sign+1)%2
if sign==1:
  if 0 in ls:
    zeroflag=1
  a=[0,0,0,0]
  b=[0,0,0,0]
  for j in range(K,N):
    if ls[j]>0:
      for k in range(K):
        if ls[K-1-k]<0:
          a[0]=ls[j]
          b[0]=j
          a[1]=ls[K-1-k]
          b[1]=K-1-k
          break
      break
  for j in range(K,N):
    if ls[j]<0:
      for k in range(K):
        if ls[K-1-k]>0:
          a[2]=ls[j]
          b[2]=j
          a[3]=ls[K-1-k]
          b[3]=K-1-k
          break
      break
  if a==[0,0,0,0]:
    flag.reverse()
  elif b[0]==0 and b[1]==0:
    flag[b[2]]=1
    flag[b[3]]=0
  elif b[2]==0 and b[3]==0:
    flag[b[0]]=1
    flag[b[1]]=0
  elif abs(a[0]*a[3])>abs(a[1]*a[2]):
    flag[b[0]]=1
    flag[b[1]]=0
  else:
    flag[b[2]]=1
    flag[b[3]]=0
if sign==1 and a==[0,0,0,0] and zeroflag==1:
  print(0)
else:
  mul=1
  for i in range(N):
    if flag[i]==1:
      mul=mul*ls[i]%MOD
  print(mul)

Submission status: Accepted

Solution code:
import sys

if(__name__ == "__main__"):

    N, K = map( int, input().strip().split() )
    divisor = 10**9+7
    list_a = list( map( int, input().strip().split() ) )
    multiplies = 1
    if(N==K):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
    else:
        list_a.sort()
        """
        解が負になるのはN>Kの時には
        正の項が1つもなく、Kが奇数の時
        """
        if(list_a[-1] < 0 and K % 2 != 0):
            """
            全て負の項
            list_a = [-5, -3, -1]のようにソートされている
            末尾の項から選んでいく
            """
            for i in range(K):
                multiplies = multiplies * list_a[N-1-i] % divisor
        elif(K==1):
            multiplies = list_a[N-1]
        else:
            left = 0
            right = N-1
            if(K%2!=0):
                multiplies = multiplies * list_a[right] % divisor
                right -= 1
            multiply_left = list_a[left] * list_a[left+1]
            multiply_right = list_a[right] * list_a[right-1]
            """
            注意:
                for文を単にK//2回ループ回すと問題が起こりうる。
                multiply_left > multiply_rightがK//2回続いた場合を考える。この時最後のループでleft = K

                Nが奇数かつN = K+1のケースではK//2回目の
                multiply_left = list_a[left] * list_a[left+1]の計算で、
                left+1 = Nとなりリストの領域範囲を超えているためREとなる。

                Nが偶数でかつN=K+1ならばleft+1が領域範囲を超えることがない。

            """

            """
            for s in range(K//2-1):
                if(multiply_left < multiply_right):
                    multiply_right %= divisor
                    multiplies = multiplies * multiply_right % divisor
                    right -= 2
                    multiply_right = list_a[right] * list_a[right-1]

                else:
                    multiply_left%=divisor
                    multiplies = multiplies * multiply_left % divisor
                    left += 2
                    multiply_left = list_a[left] * list_a[left+1]

            if(multiply_left < multiply_right):
                multiply_right %= divisor
                multiplies = multiplies * multiply_right % divisor

            else:
                multiply_left%=divisor
                multiplies = multiplies * multiply_left % divisor
            """

            flag_left = True
            for s in range(K//2):
                if(flag_left==True):
                    multiply_left = list_a[left] * list_a[left+1]
                else:
                    multiply_right = list_a[right] * list_a[right-1]
                if(multiply_left < multiply_right):
                    multiply_right %= divisor
                    multiplies = multiplies * multiply_right % divisor
                    right -= 2
                    flag_left=False


                else:
                    multiply_left%=divisor
                    multiplies = multiplies * multiply_left % divisor
                    left += 2
                    flag_left=True



    print(multiplies)