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
readline=sys.stdin.readline

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

# 正に出来る場合：
# ・すべて正の数を選べる
# ・選べる数が奇数個で、負の数が偶数個と正の数が1個以上存在する
# ・選べる数が偶数個で、負の数が偶数個存在する
# 負になる場合：
# ・すべて負の数で且つ、選べる数が奇数個
# ・0が存在していれば、0のほうがマシ

# 開始時点で、絶対値が少ないほうを目指すか大きいほうを目指すか決まる
# 負の数を目指す場合、大きいほうからK個掛ければOK

# 大きいほうを目指す場合、
# 正の数の大きい順リスト [2,1]
# 負の数の絶対値大きい順リスト [-4,-3]
# の先頭から、2個のペアが大きくなるほうを貪欲に取っていく。
# 取れる数が奇数の場合は、まず正のほうの一番大きいのを取っちゃえばOK

pluslist = []
minuslist = []
zerocnt = 0
for i in range(len(A)):
  if A[i] > 0:
    pluslist.append(A[i])
  elif A[i] < 0:
    minuslist.append(A[i])
  else:
    zerocnt += 1
    
# 必ずゼロを選んでしまう場合
if N - zerocnt < K:
  print(0)
  exit(0)
  
if K % 2 == 1 and len(pluslist) == 0:
  # 負になる場合
  if zerocnt > 0:
    print(0)
    exit(0)
  # 絶対値が小さい状態を目指す
  minuslist = sorted(minuslist, reverse = True)
  ans = 1
  for i in range(K):
    ans *= minuslist[i]
    ans %= DIV
  print(ans)
  exit(0)
  
if K + zerocnt == N:
  if len(minuslist) % 2 == 1 and zerocnt > 0:
    print(0)
    exit(0)
  else:
    ans = 1
    for p in pluslist:
      ans *= p
      ans %= DIV
    for m in minuslist:
      ans *= m
      ans %= DIV
    print(ans)
    exit(0)

# 正の数を目指す
pluslist = sorted(pluslist, reverse = True)
minuslist = sorted(minuslist)
from collections import deque

plusq = deque(pluslist)
minusq = deque(minuslist)

ans = 1
# この時点で、正にすることが出来る。
# Kが奇数の場合、最低でも1回正の数を使う必要がある
if K % 2 == 1 and len(plusq) > 0:
  ans *= plusq.popleft() # 一番大きいものを取っておく
  K -= 1

for i in range(K // 2):
  p = None
  m = None
  if len(plusq) >= 2:
    p1 = plusq.popleft()
    p2 = plusq.popleft()
    p = p1 * p2
  if len(minusq) >= 2:
    m1 = minusq.popleft()
    m2 = minusq.popleft()
    m = m1 * m2
  if p is None and m is None:
    ans *= (minusq.popleft() * plusq.popleft()) % DIV
    continue
  if m is None:
    ans *= p % DIV
    ans %= DIV
    continue
  if p is None:
    ans *= m % DIV
    ans %= DIV
    continue
  if p > m:
    ans *= p % DIV
    ans %= DIV
    minusq.appendleft(m2)
    minusq.appendleft(m1)
  else:
    ans *= m % DIV
    ans %= DIV
    plusq.appendleft(p2)
    plusq.appendleft(p1)

print(ans)

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
MOD = 10**9 + 7
def calc(X):
  ans = 1
  for x in X:
    ans *= x
    ans %= MOD
  return ans

def solve(A):
  if N == K:
    return calc(A)
  if max(A) < 0 and K % 2:
    return calc(sorted(A, reverse=True)[:K])
  
  sA = sorted(((abs(a), -1 if a < 0 else 1) for a in A), reverse=True)
  #print(sA)
  cn = 0
  for i in range(K):
    if sA[i][1] < 0:
      cn += 1
  if cn % 2 == 0:
    return calc([s[0] for s in sA[:K]])
  pA = sorted([abs(a) for a in A if a >= 0], reverse=True)
  nA = sorted([abs(a) for a in A if a < 0], reverse=True)
  #print(pA, nA)
  if (len(nA) >= cn + 1 and len(pA) >= K - cn - 1 and K - cn - 1 >= 0 and
      len(nA) >= cn - 1 and len(pA) >= K - cn + 1):
    candidates = []
    candidates.append((nA[cn-1] * nA[cn], calc(pA[:K-cn-1] + nA[:cn+1])))
    candidates.append((pA[K-cn-1] * pA[K-cn], calc(pA[:K-cn+1] + nA[:cn-1])))
    #print(candidates)
    return(max(candidates)[1])
    
  if len(nA) >= cn + 1 and len(pA) >= K - cn - 1 and K - cn - 1 >= 0:
    #print(cn, cn+1)
    return(calc(pA[:K-cn-1] + nA[:cn+1]))
  if len(nA) >= cn - 1 and len(pA) >= K - cn + 1:
    #print(cn, cn-1)
    return(calc(pA[:K-cn+1] + nA[:cn-1]))
  

print(solve(A))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def solve():
    N, K = mapint()
    As = list(mapint())
    mod = 10**9+7
    pos = []
    neg = []
    for a in As:
        if a>=0:
            pos.append(a)
        else:
            neg.append(a)

    pos.sort(reverse=True)
    neg.sort()
    lenp = len(pos)
    lenn = len(neg)
    if not pos and K%2==1:
        ans = 1
        for i, n in enumerate(neg[::-1]):
            ans *= n
            ans %= mod
            if i==K-1:
                break
        return ans
    if lenp+lenn==K and (K-lenp)%2==1:
        ans = 1
        pos.extend(neg)
        pos.sort(reverse=True)
        for i, p in enumerate(pos):
            ans *= p
            ans %= mod
            if i==K-1:
                break
        return ans
    ans = 1
    pcnt = 0
    ncnt = 0
    for i in range(K//2):
        if pcnt*2+1>=lenp:
            ans *= neg[ncnt*2]*neg[ncnt*2+1]
            ans %= mod
            ncnt += 1
        elif ncnt*2+1>=lenn:
            ans *= pos[pcnt*2]*pos[pcnt*2+1]
            ans %= mod
            pcnt += 1
        elif pos[pcnt*2]*pos[pcnt*2+1]>neg[ncnt*2]*neg[ncnt*2+1]:
            ans *= pos[pcnt*2]*pos[pcnt*2+1]
            ans %= mod
            pcnt += 1
        else:
            ans *= neg[ncnt*2]*neg[ncnt*2+1]
            ans %= mod
            ncnt += 1
    if K%2==1:
        ans *= pos[pcnt*2]
        ans %= mod
    return ans

print(solve())

Submission status: Accepted

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

pos, neg = [], []
zero_count = 0

for x in a:
	if x > 0:
		pos.append(x)
	elif x < 0:
		neg.append(x)
	else:
		zero_count += 1

# max_v = pos[0]
# min_v = neg[0]

# max_p_idx = 1
# max_n_idx = 0
# min_p_idx = 0
# min_n_idx = 1

# for kk in range(1, min(k, len(pos) + len(neg))):
# 	if max_p_idx < len(pos):
# 		max_v 


MOD = 10**9 + 7

neg = list(sorted(neg))
pos = list(reversed(sorted(pos)))

if len(pos) >= k:
	#print('case 1')
	pos_res = pos[:k]
	idx = 0
	while idx + 1 < len(neg) and pos_res[k - idx - 1] * pos_res[k - idx - 2] < neg[idx] * neg[idx + 1]:
		idx += 2

	result = 1
	for i in range(idx):
		result = result * neg[i] % MOD

	for i in range(k - idx):
		result = result * pos[i] % MOD

	print(result)

else:
	#print('case 2')
	left = k - len(pos)	
	if left % 2 == 1:
		if len(pos) > 0:
			left += 1
		else:
			left = 1000000000
	if left > len(neg):
		#print('case 3')
		b = list(sorted(map(abs, a)))
		result = 1
		for i in range(k):
			result = result * b[i] % MOD
		print(-result % MOD)
	else:
		#print("left = ", left)
		idx = left
		pos_shift = 0
		while idx + 1 < len(neg) and pos_shift + 1 < len(pos) and pos[len(pos) - pos_shift - 1] * pos[len(pos) - pos_shift - 2] < neg[idx] * neg[idx + 1]:
			idx += 2
			pos_shift += 2

		result = 1
		for i in range(idx):
			result = result * neg[i] % MOD

		for i in range(k - idx):
			result = result * pos[i] % MOD

		print(result)

Submission status: Accepted

Solution code:
def main():

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

    mod = pow(10, 9) + 7

    pos = []
    neg = []
    zero = 0
    for v in A:
        if v > 0: pos.append(v)
        elif v < 0: neg.append(v)
        else: zero += 1

    # zero is needed
    if len(pos) + len(neg) < K:
        return 0

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

    cnt_p, cnt_n = 0, 0
    h = []
    for v in pos:
        h.append([v, 1])
    for v in neg:
        h.append([-v, -1])

    h.sort(reverse = True)
    v = 1
    for k in range(K):
        if h[k][1] > 0:
            cnt_p += 1
        else:
            cnt_n += 1

    if cnt_n % 2 == 0: # when positive
        v = 1
        for i in range(cnt_p):
            v *= pos[i]
            v %= mod
        for j in range(cnt_n):
            v *= neg[j]
            v %= mod
        return v
    else: # when negative
        if cnt_p < len(pos) and cnt_n < len(neg) and cnt_p > 0: # both are not full
            # if abs(neg[cnt_n]) / pos[cnt_p-1] < pos[cnt_p] / abs(neg[cnt_n-1]):
            if pos[cnt_p] * pos[cnt_p-1] > abs(neg[cnt_n]) * abs(neg[cnt_n-1]):
                cnt_p += 1
                cnt_n -= 1
            else:
                cnt_p -= 1
                cnt_n += 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        elif cnt_p < len(pos) and cnt_n > 0:
            cnt_p += 1
            cnt_n -= 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        elif cnt_n < len(neg) and cnt_p > 0:
            cnt_p -= 1
            cnt_n += 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        else:
            if zero > 0:
                return 0
            else:
                h.sort()
                v = 1
                for i in range(K):
                    v *= h[i][0] * h[i][1]
                    v %= mod
                return v



if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7
A1 = []  
A2 = []
for i in range(N):
    if A[i] > 0:
        A1.append(A[i])
    if A[i] < 0:
        A2.append(-A[i])
A1.sort(reverse=True)
A2.sort(reverse=True)
ans = 1
if max(A)< 0:
    if K%2 == 0:
        for i in range(K):
            ans = (ans * A2[i])%mod
    else:
        A2.sort()
        for i in range(K):
            ans = (ans * A2[i])%mod
            ans = (mod - ans)%mod
elif max(A) == 0:
    if K%2 == 1:
        ans = 0
    else:
        if len(A2) >= K:
            for i in range(K):
                ans = (ans * A2[i])%mod
        else:
            ans = 0
else:
    A3 = []
    for i in range(len(A2)//2):
        A3.append(A2[2 * i] * A2[2 * i + 1])
    A4 = []
    A5 = []
    for i in range(len(A1)//2):
        A4.append(A1[2 * i] * A1[2 * i + 1])
    for i in range((len(A1) - 1)//2):
        A5.append(A1[2 * i + 1] * A1[2 * i + 2])
    if len(A1) + 2 * len(A3) < K:
        if N == K:
            for i in range(N):
                ans = (ans * A[i])%mod
        else:
            ans = 0
    else:
        if K%2 == 0:
            A6 = A3 + A4
            A6.sort(reverse=True)
            for i in range(K//2):
                ans = (ans * A6[i])%mod
        else:
            A6 = A3 + A5
            A6.sort(reverse=True)
            ans = A1[0]
            for i in range((K - 1)//2):
                ans = (ans * A6[i])% mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:33:15 2020

"""

N, K = map(int,input().split())
A = list(map(int, input().split())) 
A = sorted(A, key=abs, reverse=True)
mod = 10**9+7
ans = 1
lp = 10**6
lm = 10**6
lpflag = 0
lmflag = 0
rp = 10**6
rm = 10**6
rpflag = 0
rmflag = 0
ans1 = 0
ans2 = 0
minus = 0
flag0 = 0
for i in range(K):
    if A[i] < 0:
        minus = (minus+1)%2
    ans = ans * A[i] % mod
if not minus:
    print(ans)
else:
    for i in range(K-1,-1,-1):
        if lp < 10**6 and lm < 10**6:
            break
        if A[i] > 0 and lpflag == 0:
            lpflag = 1
            lp = i
        elif A[i] < 0 and lmflag == 0:
            lmflag = 1
            lm = i
    for i in range(K,N):
        if rp < 10**6 and rm < 10**6:
            break
        if A[i] > 0 and rpflag == 0:
            rpflag = 1
            rp = i
        elif A[i] < 0 and rmflag == 0:
            rmflag = 1
            rm = i
        elif A[i] == 0:
            flag0 = 1
    if lpflag*rmflag == 1:
        ans = 1
        for i in range(K):
            if not i == lp:
                ans = ans * A[i] % mod
        ans = ans * A[rm] % mod
        ans1 = ans
    if lmflag*rpflag == 1:
        ans = 1
        for i in range(K):
            if not i == lm:
                ans = ans * A[i] % mod
        ans = ans * A[rp] % mod    
        ans2 = ans
    if lpflag*rmflag == 0 and lmflag*rpflag == 0:
        ans = 1
        for i in range(N-1,N-1-K,-1):
            ans = ans * A[i] % mod
        if flag0:
            print(0)
        else:
            print(ans)

    else:
        if ans1 > 0 and ans2 > 0:
            if A[rm]*A[lm] > A[rp]*A[lp]:
                print(ans1)
            else:
                print(ans2)
        else:
            print(max(ans1,ans2))

Submission status: Accepted

Solution code:
from collections import deque
MOD = pow(10,9)+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
P = []; M = []; Z = []
for i in range(N):
  if A[i] >0:
    P.append(A[i])
  elif A[i] <0:
    M.append(A[i])
  else:
    Z.append(0)
P.sort(reverse=True)
M.sort(reverse=True)
ans = 1
if K == 1:
  print(P[0]%MOD)
  exit()
if len(Z) > N-K:
  print(0)
  exit()
if len(M) == 0: #全て正の場合。0があれば0
  for i in range(K):
    ans = ans*P[i]%MOD
  print(ans)
  exit()
if len(P) == 0: #全て負の場合
  if K%2 == 1 and len(Z) > 0:
    print(0)
    exit()
  if K%2 == 1:
    for i in range(K):
      ans = ans*M[i]%MOD
  else:
    M.sort()
    for i in range(K):
      ans = ans*M[i]%MOD
  print(ans)
  exit()

L = [[],[]]
M.sort()
P = deque(P); M = deque(M)
pm = [0,0] #正負の数を保存
pnow = 0; mnow = 0
#print(P,M)

for i in range(K):
  if not P:
    temp = M.popleft()
    pm[1] +=1
    L[1].append(temp)
  elif not M:
    temp = P.popleft()
    pm[0] +=1
    L[0].append(temp)
  elif P and M:
    if P[0] >= abs(M[0]):
      temp = P.popleft()
      pm[0] += 1
      L[0].append(temp)
    else:
      temp = M.popleft()
      pm[1] += 1
      L[1].append(temp)
#一個ずらす
#print(L)
#print(M,P,L)
if pm[1]%2 == 1:
  if not P and not M:
    pass
  elif not M: #もう負の数が残っていない
    L[1].pop()
    L[0].append(P[0])
  elif not P: #もう正の数が残っていない
    L[0].pop()
    L[1].append(M[0])
  elif M and P:
    if L[0] and L[1]:
      if L[0][-1]*P[0] >= L[1][-1]*M[0]:
        L[1].pop()
        L[0].append(P[0])
      else:
        L[0].pop()
        L[1].append(M[0])
    elif not L[0]:
      L[1].pop()
      L[0].append(P[0])
    elif not L[1]:
      L[0].pop()
      L[1].append(M[0])
#print(L)    
for num in range(2):
  for s in L[num]:
    ans = ans*s%MOD
print(ans)

Submission status: Accepted

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

def solve(N,K,A):
    prod = lambda x,y : ((x*y) % MOD)
    if N == K:
        return reduce(prod,A,1) % MOD
    A.sort()
    minus = [a for a in A if a < 0][::-1]
    plus = [a for a in A if a > 0][::-1]


    if K % 2 == 1 and len(plus) == 0:
        if 0 in A:
            return 0
        else:
            ans = reduce(prod,minus[:K],1)
            return ans % MOD

    ans = 1
    if K % 2 == 1:
        ans *= plus[0]
        plus2 = [p*q for p,q in zip(plus[1::2],plus[2::2])]
        minus2 = [p*q for p,q in zip(minus[::-1][::2],minus[::-1][1::2])]
        cand = sorted((plus2 + minus2),reverse=True)
        if len(cand) < K//2:
            return 0
        ans *= reduce(prod,cand[:K//2],1)
        ans %= MOD
    else:
        plus2 = [p*q for p,q in zip(plus[::2],plus[1::2])]
        minus2 = [p*q for p,q in zip(minus[::-1][::2],minus[::-1][1::2])]
        cand = sorted((plus2 + minus2),reverse=True)
        if len(cand) < K//2:
            return 0
        ans *= reduce(prod,cand[:K//2],1)
        ans %= MOD
    return ans

print(solve(N,K,A))

exit()

import random
from itertools import combinations
def ans(N,K,A):
    ans = -10**10
    for itr in combinations(range(N),K):
        t = 1
        for i in itr:
            t *= A[i]
        ans = max(ans,t)
    return ans % MOD

for i in range(100):
    N = 5 
    K = random.randint(1,N)
    A = [random.randint(-10,10) for i in range(N)]
    if solve(N,K,A) != ans(N,K,A):
        print(N,K,A)
        print(solve(N,K,A),ans(N,K,A))
        exit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


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


def main():
    from bisect import bisect_left, bisect_right
    N, K = MAP()
    A = LIST()
    A.sort()
    neg = bisect_left(A, 0)
    pos = bisect_right(A, 0)
    negative = A[:neg]
    zeros = A[neg:pos]
    positive = list(reversed(A[pos:]))
    if len(negative) + len(positive) < K:
        # 必ず0を選ぶ必要がある
        print(0)
        return
    if len(positive) == 0:
        if K % 2 == 1:
            if len(zeros) > 0:
                # 0を選びさえすれば良い
                print(0)
                return
            else:
                # 負の数から、0に近い数を選ぶ
                ans = 1
                for n in negative[-K:]:
                    ans *= (-n)
                    ans %= MOD
                ans *= -1
                print(ans % MOD)
                return
        else:
            # 答えは正となる。絶対値が大きい数を選ぶ
            ans = 1
            for n in negative[:K]:
                ans *= (-n)
                ans %= MOD
            print(ans % MOD)
            return

    if len(negative) + len(positive) == K:
        if len(negative) % 2 == 1:
            if len(zeros) > 0:
                print(0)
                return
            else:
                ans = 1
                for a in A:
                    ans *= a
                    ans %= MOD
                print(ans % MOD)
                return
    # print(negative)
    # print(zeros)
    # print(positive)
    # 負の数は二個一で採用する
    new_neg = []
    for i in range(0, len(negative)-1, 2):
        new_neg.append(negative[i]*negative[i+1])

    phead = 0
    nhead = 0

    k = K
    ans = 1
    while k > 1 and phead+2 < len(positive) and nhead < len(new_neg):
        if k >= 3:
            # 負のやつと、正の２番め３番目の積を比較する
            if new_neg[nhead] < positive[phead+1]*positive[phead+2]:
                ans *= positive[phead]
                ans %= MOD
                phead += 1
                k -= 1
                continue
            else:
                ans *= new_neg[nhead]
                ans %= MOD
                nhead += 1
                k -= 2
                continue
        if k == 2:
            if new_neg[nhead] < positive[phead+1]*positive[phead]:
                ans *= positive[phead+1]*positive[phead]
                ans %= MOD
                print(ans)
                return
            else:
                ans *= new_neg[nhead]
                ans %= MOD
                print(ans)
                return
    if nhead >= len(new_neg):
        # 残りは正から採用する
        # ここではpositiveは尽きない
        while k > 0:
            ans *= positive[phead]
            ans %= MOD
            phead += 1
            k -= 1
        print(ans)
        return
    if phead + 2 >= len(positive):
        # positiveが残り1個か2個
        if k % 2 == 0:
            # 負からとるんだが、残りのpositiveが2つなら、それを一回だけ代わりに使える
            pcand = -INF
            if phead + 1 < len(positive):
                pcand = positive[phead]*positive[phead+1]

            while k > 1 and nhead < len(new_neg):
                ncand = new_neg[nhead]
                if ncand < pcand:
                    ans *= pcand
                    ans %= MOD
                    pcand = -INF
                    k -= 2
                else:
                    ans *= ncand
                    ans %= MOD
                    nhead += 1
                    k -= 2
            if k != 0:
                ans *= pcand
                ans %= MOD

            print(ans % MOD)
            return
        else:
            # print(k)
            # print(positive[phead:])
            # print(new_neg[nhead:])
            ans *= positive[phead]
            ans %= MOD
            while k > 1:
                ncand = new_neg[nhead]
                ans *= ncand
                ans %= MOD
                k -= 2
                nhead += 1
            print(ans)
            return
    if k == 1:
        ans *= positive[phead]
        ans %= MOD
        print(ans)
        return
    #
    # 負の個数、0の個数,正の個数
    # 負の個数+正の個数 < Kの場合、0
    # 正の個数 == 0の場合、
    #   Kが奇数なら、0か0に近いものをK個
    #   Kが偶数なら、大きい物をK個
    # 0 < 正の個数 <= K の場合、
    #   いくつ負を選ぶかという話 二個一で貪欲 最後は最大の正
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
from fractions import Fraction

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k,*A = get_all_int()
    A = list(A)

    # 答えが負である条件
    # ・Aが全て負で、Kが奇数
    # ・Aの負数が奇数個かつ0が存在せず、K=N

    # 答えが0である条件
    # ・N-(Aの0の個数) < K

    positives = 0
    zeros = 0
    negatives = 0

    for a in A:
        if a > 0:
            positives += 1
        elif a == 0:
            zeros += 1
        else:
            negatives += 1
    

    if k == 1:
        # 1個だけの場合はたんに最大値を出力する
        A.sort(reverse=True)
        print(A[0])
        exit()

    if (n-zeros) < k:
        # 答えが0
        print(0)
        exit()
    
    elif (k==n and negatives%2==1  or  n==negatives+zeros and k%2==1):
        # 答えが負
        # 絶対値小さい順にK個掛ける
        A.sort(key=lambda a: abs(a))
        # log(A)
        ans = 1
        for i in range(k):
            ans =  (ans * A[i]) % MOD
        print(ans%MOD)
        exit()

    else:
        # 答えが正
        # 絶対値大きい順にK個掛ける
        A.sort(reverse=True, key=lambda a: abs(a))
        # log(A)
        ans = 1
        n_count = 0
        last_n = 0
        last_p = 0
        for i in range(k):
            a = A[i]
            ans =  (ans * a) % MOD
            if a < 0:
                n_count += 1
                last_n = a
            elif a > 0:
                last_p = a
                # log(i, last_n)

        # log(ans, n_count, last_n)
        
        # 負数を奇数個選んでいる場合は調整する
        if n_count%2 == 1:
            first_p = None
            first_n = None
            for i in range(k,n):
                a = A[i]
                if a > 0 :
                    ans_a = ans*inv(last_n, MOD) * a
                    first_p = a
                    break
            if last_p != 0:
                for i in range(k,n):
                    a = A[i]
                    if a < 0:
                        ans_b = ans*inv(last_p, MOD) * a
                        first_n = a
                        break
                if first_n is not None:
                    if first_p is not None:
                        xx = Fraction(abs(first_p), abs(last_n))
                        yy = Fraction(abs(first_n), abs(last_p))
                        # xx = abs(first_p) / abs(last_n)
                        # yy = abs(first_n) / abs(last_p)
                        if yy > xx:
                            ans_a = ans_b
                    else:
                        ans_a = ans_b
            if first_n is None and first_p is None:
                ans_a = 0
            ans = ans_a
        
        print(ans%MOD)
        exit()

main()

Submission status: Accepted

Solution code:
#import numpy as np
Q = int(1e9 + 7)

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

A = sorted(A)

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= Q
    print(ans)
    exit()
elif K == 1:
    ans = A[-1] % Q
    print(ans)
    exit()

A_mi, A_0, A_pl = [], [], []
for a in A:
    if a > 0:
        A_pl.append(a)
    elif a < 0:
        A_mi.append(a)
    else:
        A_0.append(a)

#答えが必ず0
if len(A_mi) + len(A_pl) < K:
    print(0)
    exit()

#全て正
if N == len(A_pl):
    ans, c = 1, 0
    for a in reversed(A_pl):
        ans *= a
        ans %= Q
        c += 1
        if c == K:
            break
    print(ans)
    exit()

#全て負or0
if N == len(A_mi) + len(A_0):
    if K % 2 == 0:
        ans, c = 1, 0
        for a in A_mi:
            ans *= a
            ans %= Q
            c += 1
            if c == K:
                break
        print(ans)
        exit()
    else:
        if len(A_0) > 0:
            print(0)
            exit()
        else:
            ans, c = 1, 0
            for a in reversed(A_mi):
                ans *= a
                ans %= Q
                c += 1
                if c == K:
                    break
            print(ans)
            exit()


cost_2 = []
if len(A_mi) > 1:
    for i in range(0, len(A_mi)-1, 2):
        cost_2.append(A_mi[i] * A_mi[i + 1])

c = 0
ans = 1

if K % 2 == 0:
    while True:
        if len(cost_2) > 0:
            c2 = cost_2[0]
        else:
            c2 = 0
        if len(A_pl) > 1:
            pl2 = A_pl[-1] * A_pl[-2]
        else:
            pl2 = 0
        if c2 > pl2:
            ans *= c2
            cost_2.pop(0)
        else:
            ans *= pl2
            A_pl.pop(-1)
            A_pl.pop(-1)
        ans %= Q
        c += 2
        if c == K:
            break
    print(ans)
else:
    while True:
        if (K - c > 1) and (len(cost_2) > 0):
            c2 = cost_2[0]
            if len(A_pl) > 2:
                pl2 = A_pl[-1] * A_pl[-2]
            else:
                pl2 = 0
            if c2 >= pl2:
                ans *= c2
                cost_2.pop(0)
            else:
                ans *= pl2
                A_pl.pop(-1)
                A_pl.pop(-1)
            ans %= Q
            c += 2
        else:
            ans *= A_pl[-1]
            ans %= Q
            c += 1
            A_pl.pop(-1)
        if K == c:
            break

    print(ans)

Submission status: Accepted

Solution code:
import sys

N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))[::-1]
mod=10**9+7
score=1

if K%2==1:  #これでKは偶数として扱えるようになった
    score*=A[0]
    A.pop(0)
    K-=1

#print(A)

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

M=M[::-1]
t=0
p,m=0,0
while t<=K:
    if score<0:  #負であることが確定しているなら小さくなるようにする
        P=P[::-1]
        M=M[::-1]
        if 0 in M:
            print(0)
            sys.exit()
    if t+2<=K:
        if 2*p+1<len(P) and 2*m+1<len(M):
            if P[2*p]*P[2*p+1] >= M[2*m]*M[2*m+1]:
                score*=P[2*p]*P[2*p+1]
                p+=1
                t+=2
            else:
                score*=M[2*m]*M[2*m+1]
                m+=1
                t+=2
        elif 2*p+1<len(P):
            score*=P[2*p]*P[2*p+1]
            p+=1
            t+=2
        elif 2*m+1<len(M):
            score*=M[2*m]*M[2*m+1]
            m+=1
            t+=2
        else:  #?
            score*=P[-1]*M[-1]
            break
    elif t+1<=K:
        if 2*p<len(P):
            score*=P[2*p]
        else:
            score*=M[2*m]
        break
    else:
        break
    score%=mod

print(score%mod)

Submission status: Accepted

Solution code:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
s=1
c=0
l=0
r=-1
c1=0
while True:
    if k-c>=2:
        if a[r]*a[r-1]>a[l]*a[l+1]:
            s*=a[r]*a[r-1]
            r-=2
            c+=2
        else:
            s*=a[l]*a[l+1]
            l+=2
            c+=2
    else:
        if a[r]<0:
            s=1
            a=np.absolute(a)
            a=list(a)
            a.sort()
            while True:
                s*=a[c1]
                c1+=1
                s%=10**9+7
                if c1==k:
                    s=-s
                    print(s%10**9+7)
                    exit()
        else:s*=a[r]
        c+=1
    s%=10**9+7
    if k==c:break
print(s)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
n, k, *A = map(int, open(0).read().split())
if k == n:
    s = 1
    for a in A[:k]:
        s *= a
        s %= mod
    print(s)
elif k % 2 == 1 and all(a <= 0 for a in A):
    A.sort(key=abs, reverse=1)
    s = A.pop() % mod
    c = 1
    while c < k:
        t = A.pop() * A.pop() % mod
        s *= t
        s %= mod
        c += 2
    print(s)
else:
    A.sort(key=abs)
    pos_A = [a for a in A if a >= 0]
    neg_A = [a for a in A if a <= 0]

    if k % 2 == 1:
        s = pos_A.pop()
        c = 1
    else:
        s = 1
        c = 0
    while c < k:
        if len(pos_A) >= 2 and len(neg_A) >= 2:
            if pos_A[-1] * pos_A[-2] > neg_A[-1] * neg_A[-2]:
                t = pos_A.pop() * pos_A.pop() % mod
            else:
                t = neg_A.pop() * neg_A.pop() % mod
        elif len(pos_A) < 2:
            t = neg_A.pop() * neg_A.pop() % mod
        else:
            t = pos_A.pop() * pos_A.pop() % mod
        s *= t
        s %= mod
        c += 2
    print(s)