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:
mod = 10 ** 9 + 7

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

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

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

if len(pos) == 0:
    res = 1
    if K % 2 == 0:
        neg.reverse()
    for a in neg[:K]:
        res *= a
        res %= mod
else:
    res = 1
    if K % 2 == 1:
        res = pos.pop()
        K -= 1
    while K > 1 and len(pos) > 1 and len(neg) > 1:
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            res *= pos.pop()
            res %= mod
            res *= pos.pop()
            res %= mod
        else:
            res *= neg.pop()
            res %= mod
            res *= neg.pop()
            res %= mod
        K -= 2
    while K > 1 and len(pos) > 1:
        res *= pos.pop()
        res %= mod
        res *= pos.pop()
        res %= mod
        K -= 2
    while K > 1 and len(neg) > 1:
        res *= neg.pop()
        res %= mod
        res *= neg.pop()
        res %= mod
        K -= 2
    while K and pos:
        res *= pos.pop()
        res %= mod
        K -= 1
    while K and neg:
        res *= neg.pop()
        res %= mod
        K -= 1


print(res)

Submission status: Accepted

Solution code:
from copy import deepcopy
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10 ** 9 + 7
ans = 1
i, j = 0, n - 1
k2 = deepcopy(k)
while k2 > 1:
    if a[i] * a[i + 1] > a[j] * a[j - 1]:
        ans *= a[i] * a[i + 1]
        ans %= mod
        i += 2
        k2 -= 2
    else:
        ans *= a[j]
        j -= 1
        ans %= mod
        k2 -= 1
if k2 == 1:
    ans *= a[j]
    ans %= mod
if a[-1] < 0 and k % 2:
    ans = 1
    for i in range(n - k, n):
        ans *= a[i]
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

n,k=map(int, input().split())
a=list(map(int, input().split()))
aplus,aminus=[],[]

for i in range(n):
    if a[i] >= 0: aplus.append(a[i])
    else: aminus.append(a[i])

      
if len(aplus) == 0 and k % 2 == 1:
    asort = sorted(a,reverse=True)
    ans = 1
    for i in range(k):
        ans = (ans * asort[i]) % MOD
    print(ans)
    exit()

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

newa = sorted(a,reverse=True,key=abs)
newaplus = sorted(aplus,reverse = True)
newaminus = sorted(aminus)

cntp,cntm,pp,mm=0,0,0,0

for i in range(k):
    if newa[i] >= 0:
        cntp += 1
        pp = i
    else:
        cntm += 1
        mm = i

if cntm % 2 == 1:
    if cntp == 0:
        newa[mm] = newaplus[cntp]
    elif len(newaplus) == cntp:
        newa[pp] = newaminus[cntm]
    elif len(newaminus) == cntm:
        newa[mm] = newaplus[cntp]
    else:
        if newa[pp] * newaplus[cntp] >= newa[mm] * newaminus[cntm]:
            newa[mm] = newaplus[cntp]
        else:
            newa[pp] = newaminus[cntm]

ans = 1
for i in range(k):
    ans = (ans * newa[i]) % MOD
    
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
D,E=[],[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append(0)
  elif i>0:
    D.append(i)
    scnt+=1
  else:
    E.append(i)
    fcnt+=1
mod=10**9+7
ans=1
if K==N:
  for i in A:
    ans*=i
    ans%=mod
  print(ans)
  exit()
#マイナスを奇数個絶対かける→確実に答えはマイナス
if K%2==1 and max(A)<0:
  A=sorted(A)[::-1]
  for i in range(K):
    ans*=A[i]
    ans%=mod
  print(ans)
  exit()
#絶対0をかけなきゃいけない
if K>scnt+fcnt:
  print(0)
  exit()
D,E=sorted(D)[::-1],sorted(E)
#print(D,E)
ans=1
cnt=0
a,b=0,0
while K-cnt>1:
  if a+1<=len(D)-1 and b+1<=len(E)-1:
    d,e=D[a]*D[a+1],E[b]*E[b+1]
    if d>e:
      ans*=D[a]
      a+=1
      cnt+=1
      ans%=mod
    else:
      ans*=e
      b+=2    
      ans%=mod
      cnt+=2
  elif a+1<=len(D)-1:
    d=D[a]*D[a+1]
    ans*=D[a]
    a+=1
    cnt+=1
    ans%=mod
  elif b+1<=len(E)-1:
    e=E[b]*E[b+1]
    ans*=e
    b+=2
    cnt+=2
    ans%=mod

if K-cnt==1:
  Z=[]
  if a!=scnt:
    Z.append(D[a])
  if b!=fcnt:
    Z.append(E[-1])
  if 0 in A:
    Z.append(0)
  ans*=max(Z)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
D,E=[],[]
zcnt,scnt,fcnt=0,0,0
for i in A:
  if i==0:
    zcnt+=1
    D.append(0)
  elif i>0:
    D.append(i)
    scnt+=1
  else:
    E.append(i)
    fcnt+=1
mod=10**9+7
ans=1
#全て使う場合は問答無用でかける
if K==N:
  for i in A:
    ans*=i
    ans%=mod
  print(ans)
  exit()
#マイナスを奇数個絶対かける→確実に答えはマイナス
if K%2==1 and max(A)<0:
  A=sorted(A)[::-1]
  for i in range(K):
    ans*=A[i]
    ans%=mod
  print(ans)
  exit()
#絶対0をかけなきゃいけない
if K>scnt+fcnt:
  print(0)
  exit()
D,E=sorted(D)[::-1],sorted(E)
#print(D,E)
ans=1
cnt=0
a,b=0,0
while K-cnt>1:
  if a+1<=len(D)-1 and b+1<=len(E)-1:
    d,e=D[a]*D[a+1],E[b]*E[b+1]
    if d>e:
      ans*=D[a]
      a+=1
      cnt+=1
      ans%=mod
    else:
      ans*=e
      b+=2    
      ans%=mod
      cnt+=2
  elif a+1<=len(D)-1:
    d=D[a]*D[a+1]
    ans*=D[a]
    a+=1
    cnt+=1
    ans%=mod
  elif b+1<=len(E)-1:
    e=E[b]*E[b+1]
    ans*=e
    b+=2
    cnt+=2
    ans%=mod

if K-cnt==1:
  Z=[]
  if a!=scnt:
    Z.append(D[a])
  if b!=fcnt:
    Z.append(E[-1])
  if 0 in A:
    Z.append(0)
  ans*=max(Z)
  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
ans = 1

if k == n:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if max(a) < 0 and k%2 == 1:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

plus, minus = [], []
for i in range(n):
    if a[i] >= 0: plus.append(a[i])
    else: minus.append(a[i])

plus.sort()
minus.sort(reverse=True)
while k > 0:
    if len(plus) >= 2 and len(minus) >= 2:
        nump = plus[-1] * plus[-2]
        numm = minus[-1] * minus[-2]
        if nump > numm or k == 1:
            ans *= plus.pop()
            ans %= mod
            k -= 1
        else:
            ans *= minus.pop()
            ans *= minus.pop()
            ans %= mod
            k -= 2
    elif len(minus) < 2:
        ans *= plus.pop()
        ans %= mod
        k -= 1
    elif len(plus) < 2:
        if k%2 == 0:
            ans *= minus.pop()
            ans *= minus.pop()
            ans %= mod
            k -= 2
        else:
            ans *= plus.pop()
            ans %= mod
            k -= 1
print(ans)

Submission status: Accepted

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

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

B.sort()
C.sort(key=lambda x:abs(x))

ans,flag=1,1
while k!=0:
    if k>=2:
        point=0
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()
                point=1
            else:ans *=C.pop()*C.pop()
        elif len(B)>=2:ans *=B.pop()*B.pop()
        elif len(C)>=2:ans *=C.pop()*C.pop()
        else:flag=0
        k -=2-point
    else:
        if len(B)>=1:ans *=B.pop()
        else:flag=0
        k -=1
    ans %=mod

if flag:print(ans)
else:
    ans=1
    A=sorted(A,key=lambda x:abs(x))
    for i in range(K):
        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
count=k

B,C=[],[]
for i in A:
    if i<=0:B.append(i)
    else:C.append(i)
B.sort(key=lambda x:abs(x))
C.sort()

ans,flag=1,1
while k!=0:
    if k>=2:
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()*B.pop()
                k -=2
            else:
                ans *=C.pop()
                k -=1
        elif len(B)>=2:
            ans *=B.pop()*B.pop()
            k -=2
        elif len(C)>=2:
            ans *=C.pop()*C.pop()
            k -=2
        else:flag=0;break
    else:
        if len(C)>0:
            ans *=C.pop()
            k -=1
        else:flag=0;break
    ans %=mod

if flag:print(ans)
else:
    ans=1
    A.sort(reverse=True)
    for i in range(count):
        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
ans = 1

if k == n:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
if max(a) < 0 and k%2 == 1:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

a.sort(key=lambda x: abs(x))
cnt = 0
for i in range(1, k+1):
    ans *= a[-i]
    ans %= mod
    if a[-i] < 0:
        cnt += 1

if cnt%2 == 0:
    print(ans)
else:
    a_plus = None
    a_minus = None
    b_plus = None
    b_minus = None
    for i in range(k, 0, -1):
        if a[-i] >= 0 and a_plus == None:
            a_plus = a[-i]
        if a[-i] < 0 and a_minus == None:
            a_minus = a[-i]
    for i in range(k+1, n+1):
        if a[-i] >= 0 and b_plus == None:
            b_plus = a[-i]
        if a[-i] < 0 and b_minus == None:
            b_minus = a[-i]
    if a_plus == None or b_minus == None:
        ans *= pow(a_minus, mod-2, mod)
        ans %= mod
        ans *= b_plus
        ans %= mod
    elif a_minus == None or b_plus == None:
        ans *= pow(a_plus, mod-2, mod)
        ans %= mod
        ans *= b_minus
        ans %= mod
    else:
        if abs(a_plus*b_plus) > abs(a_minus*b_minus):
            ans *= pow(a_minus, mod-2, mod)
            ans %= mod
            ans *= b_plus
            ans %= mod
        else:
            ans *= pow(a_plus, mod-2, mod)
            ans %= mod
            ans *= b_minus
            ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
import datetime
import string
import re
import math

def isort(list, _beg, _end):
    if _beg < _end:
        beg = _beg
        end = _end
        pivot = abs(list[int((beg + end)/2)])
        while(True):
            while abs(list[beg]) < pivot: beg += 1
            while abs(list[end]) > pivot: end -= 1
            if beg <= end:
                tmp = list[beg]
                list[beg] = list[end]
                list[end] = tmp
                beg += 1
                end -= 1
            else:
                break
        isort(list, _beg, end)
        isort(list, beg, _end)

def searchByBool(list):
    for i in range(len(list)):
        if check(list[i]): return i
    return -1

def check(num):
    if num >= 0: return True
    else: return False

sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True

isort(alist, 0, len(alist) - 1)
alist.reverse()

numMinus = 0
for i in range(K):
    if check(alist[i]) == False: numMinus += 1

# select biggest K numbers in terms of absolute value

# for all chosen numbers
# if the number of negative number is even
if numMinus % 2 == 0:
    isK = False

# if odd
# -> choose the smallest number, and search opposite number
if isK and K < N:
    _right = -1
    _left = -1
    for right in range(K,N):
        if check(alist[K-1]) != check(alist[right]):
            _right = right
            break
    for left in range(K):
        if check(alist[K-1-left]) != check(alist[K]):
            _left = left
            break
    isK = False
    if _right != -1 and _left != -1:
        if abs(alist[K-1-left]*alist[_right]) < abs(alist[K-1]*alist[K]):
            alist[K-1-_left] = alist[K]
        else:
            alist[K-1] = alist[_right]
    elif _right == -1 and _left != -1:
        alist[K-1-_left] = alist[K]
    elif _right != -1 and _left == -1:
        alist[K-1] = alist[_right]
    else:
        isK = True

if isK:
    alist.reverse()
klist = alist[0:K]

multi = klist[0]
for i in range(1, K):
    multi *= klist[i]
    multi = multi % 1000000007

print(multi)

Submission status: Accepted

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
sys.setrecursionlimit(int(1e+6))
MOD = int(1e+9) + 7
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

def main():
    N, K = i2nn()
    A = i2nn()
    # 選択の余地がない場合、全部掛けるしかない
    if N == K:
        n = 1
        for a in A:
            n = (n * a) % MOD
        print(n)
        return

    Ap = [ n for n in A if n >= 0]
    An = [-n for n in A if n < 0]
    Ap.sort()
    Ap.reverse()
    An.sort()
    An.reverse()
    Np = len(Ap)
    Nn = len(An)
    # 結果はプラスにしたい。Aiが全部マイナスかつKが奇数だとNG
    # 結果をプラスにできない場合、絶対値を最小化する
    if N == Nn and K % 2 == 1:
        n = 1
        A.sort()
        A.reverse()
        for i in range(K):
            n = (n * A[i]) % MOD
        print(n)
        return

    n = 1
    k = K
    i = 0
    j = 0
    # 結果をプラスに場合、プラスを維持しつつ、絶対値を最大化する
    # Kは偶数で考えたい。Kが奇数のとき、一番大きな正の数を取る
    if k % 2 == 1:
        n = (n * Ap[i]) % MOD
        i += 1
        k -= 1
    while k > 0:
        if Np - i < 2:
            n = (n * An[j]) % MOD
            j += 1
            n = (n * An[j]) % MOD
            j += 1
        elif Nn - j < 2:
            n = (n * Ap[i]) % MOD
            i += 1
            n = (n * Ap[i]) % MOD
            i += 1
        else:
            np = Ap[i] * Ap[i+1]
            nn = An[j] * An[j+1]
            if np >= nn:
                n = (n * np) % MOD
                i += 2
            else:
                n = (n * nn) % MOD
                j += 2
        k -= 2
    print(n)

main()

Submission status: Accepted

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

A.sort()

ans = 1
mod = 10 ** 9 + 7

if 0 <= A[0]:
    # All the values are positive -> Use the highest values
    for i in range(N - 1, N - K - 1, -1):
        ans = (ans * A[i]) % mod
elif A[-1] <= 0:
    # All the values are negative -> Check if the result becomes positive or negative
    if K % 2:
        # The result becomes negative -> Use the highest values
        for i in range(N - 1, N - K - 1, -1):
            ans = (ans * A[i]) % mod
    else:
        # The result becomes negative -> Use the highest values
        for i in range(K):
            ans = (ans * A[i]) % mod
else:
    # There exist both positive and negative values
    # If K is an odd number, make K even by extracting A[-1] in advance
    l, r = 0, N - 1
    if K % 2:
        ans = A[-1]
        r -= 1
        K -= 1
    # Compare A[l] * A[l + 1] and A[r -1] * A[r] -> use the bigger one
    # Why: a single negative value makes the result negative
    while K:
        if A[l] * A[l + 1] < A[r] * A[r - 1]:
            ans = (ans * A[r] * A[r - 1]) % mod
            r -= 2
        else:
            ans = (ans * A[l] * A[l + 1]) % mod
            l += 2
        K -= 2

print(ans)

Submission status: Accepted

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

A.sort()

ans = 1
mod = 10 ** 9 + 7

if 0 <= A[0]:
    for i in range(N - 1, N - K - 1, -1):
        ans = (ans * A[i]) % mod
elif A[-1] <= 0:
    if K % 2:
        for i in range(N - 1, N - K - 1, -1):
            ans = (ans * A[i]) % mod
    else:
        for i in range(K):
            ans = (ans * A[i]) % mod
else:
    l = 0
    r = N - 1
    if K % 2:
        ans = A[-1]
        r -= 1
        K -= 1

    while K:
        if A[l] * A[l + 1] < A[r] * A[r - 1]:
            ans = (ans * A[r] * A[r - 1]) % mod
            r -= 2
        else:
            ans = (ans * A[l] * A[l + 1]) % mod
            l += 2
        K -= 2

print(ans)

Submission status: Accepted

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

ans=1

if K==N:
    for i in range(N):
        ans*=A[i]
        if ans>0:
            ans=ans%MOD
elif max(A)<=0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
        if ans>0:
            ans=ans%MOD
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1 and Ap:
        ans*=Ap.pop(0)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1])
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1])
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]
        ans=ans%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
n,k = list(map(int,input().split())); arr = list(map(int,input().split())); arr.sort(reverse=True)
absarr = [[abs(i), 1 if i>0 else -1 if i<0 else 0] for i in arr]; absarr.sort(reverse=True, key=lambda x: x[0])
mod = 10**9+7

zeroflag = True if absarr[-1][0] == 0 else False
from collections import Counter
posnegarr = Counter([i[1] for i in absarr[:k]])
pos = posnegarr[1]; neg = posnegarr[-1]

if absarr[k-1] == 0:
    ans = 0
elif neg % 2 == 0 or n == k:
    ans = 1
    for i in absarr[:k]:
        ans *= i[0]; ans %= mod
    if n == k and neg % 2 == 1:
        ans = -ans % mod
else:
    ans = 1
    for i in absarr[:k]:
        ans *= i[0]; ans %= mod
    if pos > 0:
        if absarr[k][0] == 0:
            ans = 0
        nextpos = nextneg = 0
        tmp = k
        while tmp < n and (nextpos == 0 or nextneg == 0):
            num = absarr[tmp]
            if num[0] == 0:
                break
            elif num[1] > 0 and nextpos == 0:
                nextpos = num[0]
            elif num[1] < 0 and nextneg == 0:
                nextneg = num[0]
            tmp += 1
        backpos = backneg = 0
        tmp = k-1
        while backpos == 0 or backneg == 0:
            num = absarr[tmp]
            if num[1] > 0 and backpos == 0:
                backpos = num[0]
            elif num[1] < 0 and backneg == 0:
                backneg = num[0]
            tmp -= 1
        if ans == 0:
            pass
        elif nextpos*backpos > nextneg*backneg:
            ans *= nextpos*pow(backneg,-1,mod); ans %= mod
        else:
            ans *= nextneg*pow(backpos,-1,mod); ans %= mod
    else:
        nextpos = 0
        tmp = k
        while tmp < n and nextpos == 0:
            num = absarr[tmp]
            if num[1] > 0:
                nextpos = num[0]
            tmp += 1
        backneg = absarr[k-1][0]
        if nextpos != 0:
            ans *= nextpos * pow(backneg,-1,mod); ans %= mod
        elif zeroflag:
            ans = 0
        else:
            ans = 1
            for i in arr[:k]:
                ans *= i; ans %= mod
        
print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7

def moddiv(a,m):
    return pow(a,m-2,m)

def solve():
    res=-10**30
    minus,plus,zero=[],[],[]
    for i in range(N):
        if A[i]<0:
            minus.append(A[i])
        elif A[i]>0:
            plus.append(A[i])
        else:
            zero.append(A[i])
    cump=1
    plus.sort()
    minus.sort()
    for i in range(len(plus)):
        cump=cump*plus[i]%MOD
    j=0
    i=0
    cumm=1
    while(j<=min(len(minus),K)):
        if j>0:
            cumm=cumm*minus[j-1]*minus[j-2]%MOD
            newm=minus[j-1]*minus[j-2]
        else:
            newm=0
        isbig=True
        if K-j>len(plus):
            j+=2
            continue
        oldp=1
        while(K-j<len(plus)-i):
            cump=cump*moddiv(plus[i],MOD)%MOD
            if isbig:
                oldp*=plus[i]
            if oldp>newm:
                isbig=False
            i+=1
        if j>0:
            if newm>oldp:
                res=cumm*cump%MOD
        else:
            res=max(res,cumm*cump%MOD)
        j+=2
    if res!=-10**30:
        return res
    if len(zero)>0:
        return 0
    li=minus+plus
    li.sort(key=lambda x:abs(x))
    res=1
    for i in range(K):
        res=res*li[i]%MOD
    return res
N,K=map(int,input().split())
A=list(map(int,input().split()))

if min(A)>=0:
    res=1
    A.sort(reverse=True)
    for i in range(K):
        res=res*A[i]%MOD
elif max(A)<=0:
    res=1
    if not K%2:
        A.sort()
        for i in range(K):
            res=res*A[i]%MOD
    else:
        A.sort(reverse=True)
        for i in range(K):
            res=res*A[i]%MOD
else:
    res=solve()
print(res)

Submission status: Accepted

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

A.sort()

tmp1=1
tmp2=1

l=0
r=n-1
if k%2==1:
    tmp1=A[-1]%mod
    r-=1
    if A[-1]<0:
        flag=1
for i in range(k//2):
    vl=A[l]*A[l+1]
    vr=A[r]*A[r-1]
    if max(vl,vr)<0:
        flag=1
    if vl>vr:
        l+=2
        tmp1*=vl
    else:
        r-=2
        tmp1*=vr
    tmp1%=mod

from bisect import bisect_right
idx=bisect_right(A,0)
if idx==n:
    idx-=1
l=max(0,idx-1)
r=idx
for i in range(k):
    vl=A[l] if l>=0 else mod
    vr=A[r] if r<n else mod
    if abs(vl)<abs(vr) or r==n:
        l-=1
        tmp2*=vl
    else:
        r+=1
        tmp2*=vr
    tmp2%=mod

if flag==0:
    print(tmp1)
else:
    print(tmp2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7
n, k, *a = map(int, open(0).read().split())
a.sort(key=lambda x: abs(x))
ans = reduce(lambda a, b: (a * b) % mod, a[-k:])

c = a[-k:]
j = sum(i < 0 for i in c) % 2
if j:
    c = a[-k:]
    neg = [i for i in c if i < 0]
    pos = [i for i in c if i > 0]
    b = sorted(a[:n - k])
    if b == []:
        print(ans)
        exit()
    if neg == []:
        if pos[0] * b[0] < 0:
            ans = ans * pow(pos[0], mod - 2, mod) * b[0] % mod
        else:
            ans = reduce(lambda a, b: (a * b) % mod, a[:k])
    elif pos == []:
        if neg[0] * b[-1] < 0:
            ans = ans * pow(neg[0], mod - 2, mod) * b[-1] % mod
        else:
            ans = reduce(lambda a, b: (a * b) % mod, a[:k])
    elif pos[0] * b[-1] < neg[0] * b[0] and pos[0] * b[0] < 0:
        ans = ans * pow(pos[0], mod - 2, mod) * b[0] % mod
    elif 0 > b[-1] * neg[0]:
        ans = ans * pow(neg[0], mod - 2, mod) * b[-1] % mod
    else:
        ans = reduce(lambda a, b: (a * b) % mod, a[:k])
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v >= 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

mod = 10**9+7

ans = 1
if n == k:
    for a_i in a:
        ans = ans * a_i % mod
elif len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % mod
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i_p < len(a_pos) and (i == k - 1 or i_n+1 >= len(a_neg) or a_pos[i_p] * (a_pos[i_p+1] if i_p+1 < len(a_pos) else 1) > a_neg[i_n] * a_neg[i_n+1]):
            ans = ans * a_pos[i_p] % mod
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % mod * a_neg[i_n+1] % mod
            i_n += 2
            i += 2
print(ans)

Submission status: Accepted

Solution code:
def solve(n,k,a):
    mod = 10**9 + 7
    ans = 1
    l = 0
    r = n-1
    a.sort()
    
    if k%2 == 1:
        ans *= a[r]
        r-=1
    
    if ans < 0:
        ans = 1
        for i in range(k):
            ans*= a[n-i-1]
            ans%= mod
        return ans
    
    for i in range(k//2):
        tmp_min=a[l]*a[l+1]
        tmp_max=a[r]*a[r-1]
        if tmp_max> tmp_min:
            ans*=tmp_max
            ans%=mod
            r-=2
        else:
            ans*= tmp_min
            ans%=mod
            l+=2
    return ans


n, k = map(int, input().split())
A = list(map(int,input().split()))
ans = solve(n,k,A)
print(ans)

Submission status: Accepted

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

def main():
    n,k = map(int, input().split())
    A = sorted(map(int, input().split()))
    mod = 10**9 + 7
    ans, sign = 1, 1

    l, r = 0, n-1

    if k%2:
        ans = A[r]
        r-=1
        k-=1
        if ans < 0:
            sign = -1
    while k:
        x = A[l]*A[l+1]
        y = A[r]*A[r-1]

        if x*sign > y*sign:
            ans = x%mod * ans%mod
            l+=2
        else:
            ans = y%mod * ans%mod
            r-=2
        k-=2
    print((ans+mod)%mod)
main()

Submission status: Accepted

Solution code:
import copy
N, K=map(int,input().split())
A=list(map(int,input().split()))
B=sorted([(a,abs(a)) for a in A],key=lambda x:x[1],reverse=True)
R=10**9+7
P=1
minus=0
last_neg=-1
last_pos=-1
for i in range(K):
    if B[i][0]>0:
        if last_pos != -1:
            P = (P * B[last_pos][1]) % R
        last_pos=i
    elif B[i][0]<0:
        if last_neg != -1:
            P = (P * B[last_neg][1]) % R
        minus+=1
        last_neg=i
    else:
        print(0)
        exit()
F=copy.copy(P)
if last_pos!=-1:
    F=(F*B[last_pos][1]) % R
if last_neg!=-1:
    F=(F*B[last_neg][1]) % R
if minus%2==1:
    if K == N:
        print(-F %R)
        exit()
    first_neg=-1
    first_pos=-1
    count=[0,0]
    for i in range(K,N):
        if count[0]==0 and B[i][0]>0:
            first_pos=i
            count[0]=1
        elif count[1]==0 and B[i][0]<0:
            first_neg=i
            count[1]=1
        elif count==[1,1]:
            break
    if first_pos==-1 and last_pos==-1:
        P = 1
        for i in range(K):
           P = (P * B[N - i - 1][0]) % R
        print(P)
        exit()
    if first_pos==-1 and first_neg==-1:
        print(0)
        exit()
    list_product=[]
    if first_neg!=-1 and last_pos!=-1:
        list_product.append(B[last_neg][1]*B[first_neg][1])
    if first_pos!=-1:
        P1=B[first_pos][1]
        if last_pos!=-1:
            P1=P1*B[last_pos][1]
        list_product.append(P1)
    print(max(list_product)*P %R)
else:
    print(F)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
#import itertools
#import heapq
import bisect


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


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

    #    print(A)
    pp = int(bisect.bisect_left(A,0))
    A_minus = deque(A[:pp])
    A_plus = deque(A[pp:])

    #    print(A_plus)
    #    print(A_minus)
    AA = deque([])
    AAm = deque([])
    if N == K:
        ans = 1
        for i in A:
            ans *= i % mod
            ans %=mod
        print(ans % mod)

    elif K % 2 == 0:
        ans = 1

        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AAm.append(a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(a1 * a2)


        for i in range(K // 2):
            if len(AAm)==0:
                temp = AA.popleft()
            elif len(AA) ==0:
                temp = AAm.popleft()
            elif AAm[0] > AA[0]:
                temp = AAm.popleft()
            else:
                temp = AA.popleft()
            ans *= temp % mod
            ans %=mod
        print(ans % mod)

    elif len(A_plus) == 0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop() % mod
            ans %=mod
        print(ans % mod)

    else:
        ans = A_plus.pop()

        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AAm.append(a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(a1 * a2)

        for i in range(K // 2):
            if len(AAm) == 0:
                temp = AA.popleft()
            elif len(AA) == 0:
                temp = AAm.popleft()
            elif AAm[0] > AA[0]:
                temp = AAm.popleft()
            else:
                temp = AA.popleft()
            ans *= temp
            ans %=mod
        print(ans % mod)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, K = map(int, input().split())
table = list(map(int, input().split()))
jnum = K - sum(1 for i in table if i >= 0)
num_mins = sum(1 for i in table if i < 0)
q_plus = deque(sorted([i for i in table if i >= 0], reverse=True))
q_mins = deque(sorted([-i for i in table if i < 0], reverse=True))
s_plus = []
s_mins = []
total = 1


# if jnum < 0 or jnum % 2 == 0:
if (K % 2 == 1 and N == num_mins) or (N == K and num_mins % 2 == 1):
    for i in range(K):
        if not q_plus:
            total = -total * q_mins.pop() % (10 ** 9 + 7)
        elif not q_mins:
            total = total * q_plus.pop() % (10 ** 9 + 7)
        elif q_plus[-1] > q_mins[-1]:
            total = -total * q_mins.pop() % (10 ** 9 + 7)
        else:
            total = total * q_plus.pop() % (10 ** 9 + 7)
    total = total % (10 ** 9 + 7)
else:
    for i in range(K):
        if not q_plus:
            s_mins.append(q_mins.popleft())
        elif not q_mins:
            s_plus.append(q_plus.popleft())
        elif q_plus[0] > q_mins[0]:
            s_plus.append(q_plus.popleft())
        else:
            s_mins.append(q_mins.popleft())
    if len(s_mins) % 2 == 1:
        if not q_plus:
            s_plus[-1] = q_mins[0]
        elif not q_mins or not s_plus:
            s_mins[-1] = q_plus[0]
        elif q_mins[0] * s_mins[-1] > q_plus[0] * s_plus[-1]:
            s_plus[-1] = q_mins[0]
        else:
            s_mins[-1] = q_plus[0]
    s_plus.extend(s_mins)
    for j in s_plus:
        total = total * j % (10 ** 9 + 7)


print(total)