Problem:


Score : 500 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Constraints

1 \leq K \leq N \leq 2\times 10^5

|A_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.

We print this value modulo (10^9+7), that is, 1000000001.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.

Sample Input 4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

Sample Output 4

999983200

Be sure to print the product modulo (10^9+7).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Accepted

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

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

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


ans = 1
if len(P) == 0 and K % 2 == 1:
    M.sort(reverse=True)
    for k in range(K):
        ans *= M[k]
        ans %= MOD
    print(ans)
    exit()

P.sort(reverse=True)
M.sort()
S = 1
LP = len(P)
LM = len(M)
cur_p = 0
cur_m = 0
cnt = 0
ans = 1
while cnt < K:
    if K - cnt == 1 or LM - cur_m <= 1:
        flag = 'p'
    elif LP - cur_p == 1:
        if (K - cnt) % 2 == 1:
            flag = 'p'
        else:
            flag = 'm'
    elif LP - cur_p == 0:
        flag = 'm'
    else:
        p1 = P[cur_p]
        p2 = P[cur_p + 1]
        m1 = M[cur_m]
        m2 = M[cur_m + 1]
        if p1 * p2 >= m1 * m2:
            flag = 'p'
        else:
            flag = 'm'
    
    if flag == 'p':
        ans *= P[cur_p]
        ans %= MOD
        cur_p += 1
        cnt += 1
    else:
        ans *= M[cur_m] * M[cur_m + 1]
        ans %= MOD
        cur_m += 2
        cnt += 2

print(ans)

Submission status: Accepted

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


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

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

ans = 1
if len(P) == 0 and K % 2 == 1:
    M.sort(reverse=True)
    for k in range(K):
        ans *= M[k]
        ans %= MOD
    print(ans)
    exit()

P.sort(reverse=True)
M.sort()
S = 1
LP = len(P)
LM = len(M)
cur_p = 0
cur_m = 0
cnt = 0
ans = 1
while cnt < K:
    if K - cnt == 1 or LM - cur_m <= 1:
        flag = 'p'
    elif LP - cur_p == 1:
        if (K - cnt) % 2 == 1:
            flag = 'p'
        else:
            flag = 'm'
    elif LP - cur_p == 0:
        flag = 'm'
    else:
        p1 = P[cur_p]
        p2 = P[cur_p + 1]
        m1 = M[cur_m]
        m2 = M[cur_m + 1]
        if p1 * p2 >= m1 * m2:
            flag = 'p'
        else:
            flag = 'm'
    
    if flag == 'p':
        ans *= P[cur_p]
        ans %= MOD
        cur_p += 1
        cnt += 1
    else:
        ans *= M[cur_m] * M[cur_m + 1]
        ans %= MOD
        cur_m += 2
        cnt += 2

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
ans = 1

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

if n == k:
    for x in a:
        ans *= x
        ans %= MOD
    print(ans % MOD)
    exit()

pos = []
neg = []

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

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

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

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


l = []

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

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

l.sort(reverse=True)

for i in range(k // 2):
    ans *= l[i]
    ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
ans = 1

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

if n == k:
    for x in a:
        ans *= x
        ans %= MOD
    print(ans % MOD)
    exit()

pos = []
neg = []

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

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

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

pi = 0
ni = 0
if k % 2:
    ans *= pos[pi]
    pi += 1
    k -= 1

while k > 0:
    if pi < len(pos) - 1:
        sp = pos[pi] * pos[pi + 1]
    else:
        sp = 0
    
    if ni < len(neg) - 1:
        sn = neg[ni] * neg[ni + 1]
    else:
        sn = 0
    
    if sp > sn:
        ans *= sp
        pi += 2
    else:
        ans *= sn
        ni += 2
    
    ans %= MOD
    k -= 2

print(ans % MOD)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,K = LI()
AS=LI()
AS.sort(reverse=True)
res = 1
if AS[0] >= 0 and AS[N-1] >= 0:
    for i in range(K):
        res *= AS[i]
        res %= DVSR
elif AS[0] > 0:
    if N != K:
        PS = []
        NS = []
        for i in AS:
            if i >= 0:
                PS.append(i)
            else:
                NS.append(-i)
        PS.sort(reverse=True)
        NS.sort(reverse=True)
        i = 0
        j = 0

        for k in range(K):
            if i < len(PS) and j < len(NS):
                if PS[i] > NS[j]:
                    res *= PS[i]
                    i += 1
                else:
                    res *= NS[j]
                    j += 1
            else:
                if i < len(PS):
                    res *= PS[i]
                    i += 1
                else:
                    res *= NS[j]
                    j += 1
            res %= DVSR
            # print(res)
        # print("i:{} j:{}".format(i, j))
        if j % 2:
            if j < len(NS) and i < len(PS) and i > 0 and j > 0:
                if NS[j]*NS[j-1] > PS[i-1]*PS[i]:
                    res *= INV(PS[i-1])
                    res %= DVSR
                    res *= NS[j]
                    j += 1
                else:
                    res *= INV(NS[j-1])
                    res %= DVSR
                    res *= PS[i]
                    i += 1
            else:
                if j < len(NS) and i > 0:
                    res *= INV(PS[i-1])
                    res %= DVSR
                    res *= NS[j]
                    j += 1
                else:
                    res *= INV(NS[j-1])
                    res %= DVSR
                    res *= PS[i]
                    i += 1
            res %= DVSR
            # print(res)
    else:
        for i in range(N):
            res *= AS[i]
            res %= DVSR
else: # AS[0] <= 0
    if K % 2:
        v1 = 1
        v2 = 1
        for i in range(K):
            v1 *= AS[i]
            v1 %= DVSR
        res = v1
    else:
        res = 1
        for i in range(N-K, N):
            res *= AS[i]
            res %= DVSR

print(res%DVSR)

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:
    for x in a:
        ans *= x
        ans %= MOD
    print(ans % MOD)

#全部負かつ奇数個取る
elif max(a) < 0 and k % 2:
    a.sort()
    for i in range(1, k+1):
        ans *= a[-i]
        ans %= MOD
    print(ans % MOD)

else:
    pos = []
    neg = []
    
    for x in a:
        if x >= 0:
            pos.append(x)
        else:
            neg.append(x)
    
    pos.sort(reverse=True)
    neg.sort()
    
    
    if k % 2:
        ans *= pos.pop(0)
        k -= 1
     
    #2個ずつ取る
    num = []
    for x, y in zip(pos[::2], pos[1::2]):
        num.append(x * y)
    for x, y in zip(neg[::2], neg[1::2]):
        num.append(x * y)

    num.sort(reverse=True)

    for i in range(k // 2):
        ans *= num[i]
        ans %= MOD
    
    print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import deque

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

MOD = 10 ** 9 + 7

n_minus = 0
for a in A:
    if a < 0:
        n_minus += 1

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

elif n_minus == N and K % 2 == 1:
    A = sorted(A, key=lambda x: 10 ** 9 if x == 0 else abs(x))

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

    print(ans)

else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    padding = None
    plus = deque()
    minus = deque()
    buf_p = deque()
    buf_m = deque()

    for a in A:
        if a >= 0:
            if padding is None and K % 2 == 1:
                padding = a
            else:
                buf_p.append(a)

                if len(buf_p) == 2:
                    plus.append(buf_p.popleft() * buf_p.popleft())
        else:
            buf_m.append(a)

            if len(buf_m) == 2:
                minus.append(buf_m.popleft() * buf_m.popleft())

    ans = 1
    if padding is not None:
        ans *= padding
        ans %= MOD

    for _ in range(K // 2):
        if len(plus) == 0:
            ans *= minus.popleft()
            ans %= MOD
        elif len(minus) == 0:
            ans *= plus.popleft()
            ans %= MOD
        elif plus[0] >= minus[0]:
            ans *= plus.popleft()
            ans %= MOD
        else:
            ans *= minus.popleft()
            ans %= MOD

    print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x))
if k==n:
  ans=1
  for i in range(n):
    ans*=arr[i]
    ans%=mod
  print(ans)
else:
  if k%2==1 and max(arr)<0:
    ans=1
    for i in range(k):
      ans*=arr[n-1-i]
      ans%=mod
    print(ans)
  else:
    ans=1
    cnt=0
    for i in range(k):
      if arr[i]<0:
        cnt+=1
      ans*=arr[i]
      ans%=mod
    if cnt%2==0:
      print(ans)
    else:
      min_plus=-1
      min_minus=1
      for i in range(k):
        if arr[i]>=0:
          min_plus=arr[i]
        else:
          min_minus=arr[i]
      max_plus=-1
      max_minus=1
      for i in range(k,n):
        if arr[i]>=0 and max_plus==-1:
          max_plus=arr[i]
        if arr[i]<0 and max_minus==1:
          max_minus=arr[i]
      if min_plus==-1:        
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      elif min_minus==1:        
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_minus
        ans%=mod
      elif min_plus*max_plus>=min_minus*max_minus:
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      else:
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_minus
        ans%=mod
      print(ans)

Submission status: Accepted

Solution code:
import sys

mod = 10**9 + 7

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

# 0も入れておく
pos_list = []
neg_list = []
zero_count = 0
for a_i in A:
    if a_i > 0:
        pos_list.append(a_i)
    elif a_i == 0:
        zero_count += 1
    else:
        neg_list.append(a_i)

lp = len(pos_list)
ln = len(neg_list)

if min(2 * (ln // 2), 2 * (K // 2)) + lp >= K:
    # 降順
    pos_list.sort(reverse = True)
    neg_list.sort()

    pos_twins = [pos_list[2 * i] * pos_list[2 * i + 1] for i in range(lp // 2)] + [0]
    neg_twins = [neg_list[2 * i] * neg_list[2 * i + 1] for i in range(ln // 2)] + [0]
    pos_twins.sort()
    neg_twins.sort()
 
    ans = 1
    pos_select = 0
    for i in range(K // 2):
        if pos_twins[-1] <= neg_twins[-1]:
            ans *= neg_twins[-1]
            ans %= mod
            neg_twins.pop()
        else:
            ans *= pos_twins[-1]
            ans %= mod
            pos_twins.pop()
            pos_select += 1
 
    if K % 2 == 1:
        if K == 1:
            ans = pos_list[2 * pos_select]
        else:
            ans *= pos_list[2 * pos_select]
    print(ans % mod)    
elif zero_count > 0:
	print(0)
# マイナスになるため、最小化する
else:
    ans = 1
    abs_list = sorted([abs(a) for a in A])
    for a in abs_list[:K]:
        ans *= a
        ans %= mod
    print((-1) * ans % mod)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
p_cnt = 0
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
        p_cnt += 1
    else:
        nums.append((-i, False))
nums.sort()
if p_cnt == 0 and K%2!=0:
    ans = 1
    for k in range(K):
        ans *= -nums[k][0]
        ans %= mod
    print(ans)
    import sys
    sys.exit()
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    if x == 0:
        print(0)
        import sys
        sys.exit()
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    p = float("inf")
    px = float("inf")
    m = float("inf")
    mx = float("inf")
    while nums:
        x, b = nums.pop()
        if b:
            if ml and p == float("inf"):
                p = ml[-1]
                px = x
        else:
            if pl and m == float("inf"):
                m = pl[-1]
                mx = x
        if m != float("inf") and p != float("inf"):
            if px * m > mx * p:
                ml.pop()
                pl.append(px)
            else:
                pl.pop()
                ml.append(mx)
            break
    else:
        if p != float("inf"):
            ml.pop()
            pl.append(px)
        elif m != float("inf"):
            pl.pop()
            ml.append(mx)
ans = 1
for x in pl:
    ans *= x
    ans %= mod
for x in ml:
    ans *= -x
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys, math,os
from io import BytesIO, IOBase
#data = BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
from decimal import Decimal
from fractions import Fraction
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
#sys.setrecursionlimit(100000 + 1)
INF = 10**9
mod = 10**9 + 7


n,k=mdata()
a=mdata()
n1,p=-1,-1
a1=[(abs(a[i]),a[i]) for i in range(n)]
a1.sort(reverse=True)
ans=1
c=1
for i in range(k):
    if a1[i][1]>0:
        p=i
    elif a1[i][1]<0:
        n1=i
        c*=-1
    else:
        c=0
    ans=(ans*a1[i][1])%mod
if c>=0:
    out(ans%mod)
else:
    b1=0
    b2=0
    for i in range(k,n):
        if a1[i][1]>=0 and b1==0:
            u1,v1=a1[n1][1],a1[i][1]
            b1=1
            c=1
        if a1[i][1]<0 and p!=-1 and b2==0:
            u2,v2=a1[p][1],a1[i][1]
            b2=1
            c=1
    if c<0:
        ans=1
        for i in range(k):
            ans = (ans*a1[n-i-1][1])%mod
    else:
        if b1==1 and b2==1:
            if Fraction(v1,u1)<Fraction(v2,u2):
                ans=ans*pow(u1,mod-2,mod)*v1
            else:
                ans = ans * pow(u2, mod - 2, mod) * v2
        elif b1==1:
            ans = ans * pow(u1, mod - 2, mod) * v1
        else:
            ans = ans * pow(u2, mod - 2, mod) * v2
    out(ans%mod)

Submission status: Accepted

Solution code:
import heapq
#import random
# n = random.randint(1, 10)
# k = random.randint(1, n)
# A = [random.randint(-10, 10) for _ in range(n)]
# print(n, k)
# print(A)

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 *= a
        ans %= MOD
    print(ans)
    exit()

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

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if not neg:
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if not pos:
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

    if pos[0]<=neg[0]:
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if pos[0]>neg[0]:
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.remove(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.remove(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = -pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_neg*last_neg:
            L_ans.remove(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.remove(last_pos)
            L_ans.append(new_neg)

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    # @staticmethod
    # def __test01__():
    #     xs = HeapQueue([-3, 2, 9, -4], "min")
    #     x0 = xs.pop()
    #     x1 = xs.pop()
    #     x2 = xs.pop()
    #     x3 = xs.pop()
    #     return (x0 == -4 and x1 == -3 and x2 == 2 and x3 == 9)


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

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D

elif all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used_min_pos is None and used[k] >= 0: used_min_pos = k
            elif used_min_neg is None and used[k] <  0: used_min_neg = k
            if used_min_pos and used_min_neg: break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K):
            if   rest_min_pos is None and rest[k] >= 0: rest_min_pos = k
            elif rest_min_neg is None and rest[k] <  0: rest_min_neg = k
            if rest_min_pos and rest_min_neg: break

        # print(used)
        # print(used_min_pos)
        # print(used_min_neg)
        # print(rest)
        # print(rest_min_pos)
        # print(rest_min_neg)

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest[rest_min_pos]
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest[rest_min_neg]
        else:
            v1 = abs(used[used_min_pos] * rest[rest_min_pos])
            v2 = abs(used[used_min_neg] * rest[rest_min_neg])
            if v1 > v2:
                used[used_min_neg] = rest[rest_min_pos]
            else:
                used[used_min_pos] = rest[rest_min_neg]

    for a in used:
        r = (r * a) % D

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

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

if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod

    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

if K>len(B)+len(C):
    print(0)
    sys.exit()

if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS%mod)
            
    elif Z==[] and K%2==1:
        C.reverse()
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(-ANS%mod)
        
    elif K%2==1:
        print(0)
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS%mod)

    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)

        while True:
            if c_start+ind+1<len(C) and len(B)-2-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)+1

        while True:
            if c_start+ind+1<len(C) and len(B)-3-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-2-ind]*B[len(B)-3-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-2-ind]*B[len(B)-3-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    print(S%mod)

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))
absolute = deque(sorted(a, key=abs, 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:
    minus_num = 0
    for _ in range(k):
        v = absolute.popleft()
        if v < 0:
            minus_num += 1
        ans_lst.append(v)
    if minus_num % 2 != 0:
        abs_min_plus_zero, abs_min_minus = None, None
        abs_max_plus_zero, abs_max_minus = None, None
        for i in ans_lst:
            if i >= 0:
                if abs_min_plus_zero is None:
                    abs_min_plus_zero = i
                else:
                    abs_min_plus_zero = min(i, abs_min_plus_zero)
            else:
                if abs_min_minus is None:
                    abs_min_minus = i
                else:
                    abs_min_minus = max(abs_min_minus, i)
        for i in absolute:
            if i >= 0:
                if abs_max_plus_zero is None:
                    abs_max_plus_zero = i
                else:
                    abs_max_plus_zero = max(i, abs_max_plus_zero)
            else:
                if abs_max_minus is None:
                    abs_max_minus = i
                else:
                    abs_max_minus = min(abs_max_minus, i)
        case1, case2 = False, False
        if abs_min_plus_zero is not None and abs_max_minus is not None:
            case1 = True
        if abs_min_minus is not None and abs_max_plus_zero is not None:
            case2 = True
        if case1 and case2:
            if abs_max_minus * abs_min_minus <= abs_max_plus_zero * abs_min_plus_zero:
                ans_lst.remove(abs_min_minus)
                ans_lst.append(abs_max_plus_zero)
            else:
                ans_lst.remove(abs_min_plus_zero)
                ans_lst.append(abs_max_minus)
        elif case1:
            ans_lst.remove(abs_min_plus_zero)
            ans_lst.append(abs_max_minus)
        elif case2:
            ans_lst.remove(abs_min_minus)
            ans_lst.append(abs_max_plus_zero)


# functools.reduceはTLEをくらう場合があるので気をつける
ans = 1
for i in ans_lst:
    ans = (ans * i) % MOD
print(ans)

Submission status: Accepted

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

p = 1
n = 0
ans = 1
cnt = 0
while cnt < K-1:
  if A[n]*A[n+1] > A[-p]*A[-p-1]:
    ans = ans*A[n]*A[n+1]%mod
    n += 2
    cnt += 2
    
  else:
    ans = ans*A[-p]%mod
    p += 1
    cnt += 1
    
if cnt == K-1:
  ans = ans*A[-p]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*i%mod

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

B=[]
C=[]
Z=[]
 
for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)
 
B.sort(reverse=True)
C.sort(reverse=True)
 
if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod
 
    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()
 
if K>len(B)+len(C):
    print(0)
    sys.exit()
 
if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS)
 
    elif Z==[] and K%2==1:
        ANS=1
        C.reverse()
        for i in range(K):
            ANS=ANS*(-C[i])%mod
        print(ANS)
        
    elif K%2==1:
        print(0)
        
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(ANS)
 
    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)

        while True:
            if c_start+ind+1<len(C) and len(B)-2-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=0
        c_start=K-len(B)+1

        while True:
            if c_start+ind+1<len(C) and len(B)-3-ind>=0 and C[c_start+ind]*C[c_start+ind+1]>B[len(B)-2-ind]*B[len(B)-3-ind]:
                S=S*C[c_start+ind]*C[c_start+ind+1]*pow(B[len(B)-2-ind]*B[len(B)-3-ind],mod-2,mod)%mod
                ind+=2
            else:
                break

    print(S%mod)

Submission status: Accepted

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

pi = 1
ni = 0
ans = 1
i = 0
while i < K-1:
  if A[ni]*A[ni+1] > A[-pi]*A[-pi-1]:
    ans = ans*A[ni]*A[ni+1]%mod
    ni += 2
    i += 2
    
  else:
    ans = ans*A[-pi]%mod
    pi += 1
    i += 1
    
if i == K-1:
  ans = ans*A[-pi]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*i%mod

print(ans)