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())
L = list(map(int,input().split()))
L = sorted(L)

MOD=10**9+7

ans=1
if N==K:
    for a in L:
        ans*=a
        ans%=MOD

#全部ふで奇数個
elif all(l<0 for l in L) and K%2==1:
    #小さい方からKこ
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))

    ans_cand=[v for v in absL[:K]]
    remain=[v for v in absL[K:]]

    if len(list(filter(lambda x:x<0,ans_cand)))%2==0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        ans_cand_min_neg = None
        ans_cand_min_pos=None
        remain_cand_max_neg=None
        remain_cand_max_pos=None

        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a

        #できるだけ絶対値が大きいやつ
        for a in remain:
            if a>=0:
                remain_cand_max_pos=a
                break

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
        for a in remain:
            if a<=0:
                remain_cand_max_neg=a
                break

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_pos*remain_cand_max_pos)
            B = abs(ans_cand_min_neg*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg


        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
            else:
                NG=None
print(ans)

Submission status: Accepted

Solution code:
def main() :
    N,K=map(int,input().split())              #N個の整数,K個の積
    A=list(map(int,input().split()))
    mod=10**9+7
    
    minusA=sorted([i for i in A if i < 0], reverse=True) #負で絶対値が小さい数字順
    plusA=sorted([i for i in A if i >= 0])               #正で絶対値が小さい数字順
 
    start=1
    if len(plusA)==0 and K%2==1 :        #負の整数のみ,Kの個数は奇数
        for i in minusA[:K] :
            start=start*i%mod
        print(start)
        exit()

    while K>0 :
        if K== 1 or len(minusA)<=1 :     #Kの個数が1個のとき、または負の整数が1個以下のとき
            if len(plusA)==0 :           #正の整数が存在しない場合
                start*=minusA.pop()
            elif len(plusA)>0 :          #正の整数が存在する場合
                start*=plusA.pop()
            K-=1                         #この場合、Kを1個減らしていってループさせている

        elif len(plusA)<= 1 :            #正の整数が1個以下のとき
            start*=minusA.pop()*minusA.pop()
            K-=2

        elif plusA[-1]*plusA[-2]>minusA[-1]*minusA[-2] :
            start*=plusA.pop()
            K-=1

        elif plusA[-1]*plusA[-2]<=minusA[-1]*minusA[-2] :
            start*=minusA.pop()*minusA.pop()
            K-=2

        start%=mod
    else :
        print(start)



if __name__=="__main__" :
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
plus,minus,zero = 0,0,0
for i in range(n):
    if a[i] > 0:
        plus += 1
    elif a[i] < 0:
        minus += 1
    else:
        zero += 1
if n==k:
    ans=1
    for i in range(n):
        ans*=a[i]
        ans=ans%(10**9+7)
    print(ans)
else:
    if k%2==1 and minus==n:
        a.sort(reverse=True)
        ans=1
        for i in range(k):
            ans*=a[i]
            ans=ans%(10**9+7)
        print(ans)
    else:
        l=[]
        for i in range(n):
            if a[i]>=0:
                fugou=1
            else:
                fugou=-1
            l.append((abs(a[i]),fugou))
        l.sort(reverse=True)
        ans=1
        hu=1
        for i in range(k):
            ans*=l[i][0]
            ans=ans%(10**9+7)
            hu*=l[i][1]
        if hu==1:
            print(ans)
        elif ans==0:
            print(0)
        else:
            ss,sh,ts,th=-1,-1,-1,-1
            for i in range(k)[::-1]:
                if l[i][1]>0:
                    ss=l[i][0]
                    break
            for i in range(k)[::-1]:
                if l[i][1]<0:
                    sh=l[i][0]
                    break
            for i in range(k,n):
                if l[i][1]>0:
                    ts=l[i][0]
                    break
            for i in range(k,n):
                if l[i][1]<0:
                    th=l[i][0]
                    break
            if ss>0 and sh>0 and ts>0 and th>0:
                if th*sh>=ts*ss:
                    ans=(ans*pow(ss,10**9+5,10**9+7)*th)%(10**9+7)
                else:
                    ans=(ans*pow(sh,10**9+5,10**9+7)*ts)%(10**9+7)
                print(ans)
            else:
                if th>0 and ss>0:
                    ans=(ans*pow(ss,10**9+5,10**9+7)*th)%(10**9+7)
                else:
                    ans=(ans*pow(sh,10**9+5,10**9+7)*ts)%(10**9+7)
                print(ans)

Submission status: Accepted

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

plus,minus,zero = 0,0,0
for i in range(N):
    if A[i] > 0:
        plus += 1
    elif A[i] < 0:
        minus += 1
    else:
        zero += 1

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

else:
    if K%2 == 1 and minus == N: # 負の場合
        A.sort(reverse=True)

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

    else: # そうじゃない場合
        l = []
        for i in range(N):
            if A[i] < 0:
                fugou = -1
            else:
                fugou = 1
            l.append((abs(A[i]),fugou))
        l.sort(reverse=True)
        #print(l)

        ans = 1
        fu = 0
        for i in range(K):
            if l[i][1] < 0:
                fu += 1
            ans *= l[i][0]
            ans %= MOD

        if fu%2 == 0:
            print(ans)
        elif ans == 0:
            print(0)
        else:
            sei_suteru = -1
            fu_suteru = -1
            for i in range(K)[::-1]:
                if sei_suteru == -1:
                    if l[i][1] > 0:
                        sei_suteru = l[i][0]
                if fu_suteru == -1:
                    if l[i][1] < 0:
                        fu_suteru = l[i][0]
                
            sei_ireru = -1
            fu_ireru = -1
            for i in range(K,N):
                if sei_ireru == -1:
                    if l[i][1] > 0:
                        sei_ireru = l[i][0]
                if fu_ireru == -1:
                    if l[i][1] < 0:
                        fu_ireru = l[i][0]

            #print(ans)
            #print(sei_suteru,fu_suteru,sei_ireru,fu_ireru)
            if sei_suteru >= 0 and fu_suteru >= 0 and sei_ireru >= 0 and fu_ireru >= 0:
                if sei_ireru*sei_suteru <= fu_ireru*fu_suteru: # 正を捨てて負を入れる方がいいとき
                    ans = -ans * -fu_ireru * pow(sei_suteru,MOD-2,MOD)
                    ans %= MOD
                else: # 負を捨てて正を入れる方がいいとき
                    ans = -ans * sei_ireru * pow(-fu_suteru,MOD-2,MOD)
                    ans %= MOD
            elif sei_ireru == -1 or fu_suteru == -1:
                ans = -ans * -fu_ireru * pow(sei_suteru,MOD-2,MOD)
                ans %= MOD
            else:
                ans = -ans * sei_ireru * pow(-fu_suteru,MOD-2,MOD)
                ans %= MOD

            print(ans)

Submission status: Accepted

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

mainasu=[]
purasu=[]
for aa in a:
    if aa>=0:
        purasu.append(aa)
    else:
        mainasu.append(aa*(-1))



mod=10**9+7

#回答がプラスになるケース
if (k<n and len(purasu)>0) or (k<n and k%2==0) or (k==n and len(mainasu)%2==0):
    p_pos=0
    m_pos=0
    mainasu.sort(reverse=True)
    purasu.sort(reverse=True)
    ans=1
    cnt=0
    while cnt<k:
        ans=ans%mod
        #どっちからでも選べる
        if p_pos<len(purasu) and m_pos+1 < len(mainasu) and cnt<k-1:
            #もし最後から2つ目
            if cnt<=k-2:
                if p_pos==len(purasu)-1:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
                elif purasu[p_pos]*purasu[p_pos+1]>mainasu[m_pos]*mainasu[m_pos+1]:
                    if cnt==k-2:
                        ans*=purasu[p_pos]%mod
                        p_pos+=1
                        ans*=purasu[p_pos]%mod
                        p_pos+=1
                        cnt+=2
                    else:
                        ans*=purasu[p_pos]%mod
                        p_pos+=1
                        cnt+=1

                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
            else:
                if purasu[p_pos]>mainasu[m_pos+1]:
                    ans=ans*purasu[p_pos]%mod
                    cnt+=1
                    p_pos+=1
                else:
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    ans*=mainasu[m_pos]%mod
                    m_pos+=1
                    cnt+=2
        elif p_pos<len(purasu):
            ans=ans*purasu[p_pos]%mod
            cnt+=1
            p_pos+=1
        else:
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            ans*=mainasu[m_pos]%mod
            m_pos+=1
            cnt+=2
    print(ans%mod)









#回答がマイナスになるケース
else:
    pm=purasu+mainasu
    pm.sort()
    ans=1
    for i in range(k):
        ans=ans*pm[i]%mod
        ans=ans%mod
    #print(-1*ans)
    print((-1*ans)%mod)

Submission status: Accepted

Solution code:
from functools import reduce

mod = 10**9+7

def modcumprod(*args):
    return reduce(lambda x, y: x*y%mod, args)

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

if n == k:
    print(modcumprod(*a))
elif max(a) < 0 and k % 2 == 1:
    a.sort(reverse=True)
    print(modcumprod(*a[:k]))
else:
    a.sort(key=abs, reverse=True)
    res = 1
    cnt_neg = 0
    pos1 = neg1 = 0
    for e in a[:k]:
        res *= e
        res %= mod
        if e > 0:
            pos1 = e
        else:
            cnt_neg += 1
            neg1 = e

    if res == 0 or cnt_neg % 2 == 0:
        print(res)
    else:
        pos2 = neg2 = 0
        for e in a[k:]:
            if e > 0 and not pos2:
                pos2 = e
            elif e < 0 and not neg2:
                neg2 = e
            if pos2 and neg2:
                break
        if abs(pos1 * pos2) < abs(neg1 * neg2) and pos1:
            res *= pow(pos1, -1, mod)
            res *= neg2
            res %= mod
        else:
            res *= pow(neg1, -1, mod)
            res *= pos2
            res %= mod
        print(res)

Submission status: Accepted

Solution code:
import sys

MOD = 10**9+7

N,K = map(int, input().split())
A = [[abs(int(x)),1 if int(x)<0 else 0] for x in input().split()]
A.sort(key=lambda x: x[0],reverse=True)
prod = 1
pn = 0
lastn = -1
lastp = -1


for i in range(K):
    if A[i][1] == 1: lastn = i
    else: lastp = i
    pn = (pn + A[i][1]) % 2


if pn == 0:
    if K == N and [0,0] in A:
        print(0)
        sys.exit()
    for i in range(K):
        prod = prod * A[i][0] % MOD
    print(prod)
    sys.exit()

elif pn == 1:
    if K == N:
        if [0,0] in A:
            print(0)
            sys.exit()
        for i in range(N):
            prod = prod * A[i][0] % MOD
        prod = prod * (-1) % MOD
        print(prod)
        sys.exit()
    indp = K
    indn = K
    while indp < N and A[indp][1] == 1:
        indp += 1
    while indn < N and A[indn][1] == 0:
        indn += 1
    if lastp == -1 and indp == N:
        for i in range(K):
            prod = prod * A[-1-i][0] % MOD
        prod = prod * (-1) % MOD
    elif indp == N:
        for i in range(K):
            if i == lastp:
                prod = prod * A[indn][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    elif lastp == -1 or indn == N:
        for i in range(K):
            if i == lastn:
                prod = prod * A[indp][0] % MOD
            else:
                prod = prod * A[i][0] % MOD
    else:
        for i in range(K):
            if A[indp][0] * A[lastp][0] > A[indn][0] * A[lastn][0]:
                if i == lastn:
                    prod = prod * A[indp][0] % MOD
                else: prod = prod * A[i][0] % MOD
            else:
                if i == lastp:
                    prod = prod * A[indn][0] % MOD
                else:
                    prod = prod * A[i][0] % MOD
    print(prod)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
p = 10**9+7
Aplus = []
Nplus = 0
Aminus = []
Nminus = 0
Aabs = []
for i in range(N):
    if A[i]>=0:
        Aplus.append(A[i])
        Nplus += 1
    else:
        Aminus.append(A[i])
        Nminus += 1
Aplus.sort(reverse=True)
Aminus.sort(reverse=False)

if K==N:
    out=1
    for i in range(K):
        out = out*A[i]%p
    print(out)
elif Nminus==N and K%2==1:
    out=1
    for i in range(K):
        out = out*Aminus[N-i-1]%p
    print(out)
else:
    l=0
    r=0
    out=1
    inf = float('inf')
    while K>0:
        if l+1<=Nplus-1:
            cand1 = Aplus[l]*Aplus[l+1]
        elif l==Nplus-1:
            cand1 = Aplus[l]
        else:
            cand1 = -1*inf

        if r+1<=Nminus-1:
            cand2 = Aminus[r]*Aminus[r+1]
        elif r==Nminus-1:
            cand2 = Aminus[r]
        else:
            cand2 = -1*inf

        if cand1>cand2 or K==1:
            out=out*Aplus[l]%p
            K += -1
            l += 1
        else:
            out=out*Aminus[r]*Aminus[r+1]%p
            K += -2
            r += 2
    print(out)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N or N == K:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevpos = None
    prevneg = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if ans != 0 and not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and (nextneg is None or nextpos is None):
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    multimul = lambda L,i=0: (L[i] * multimul(L,i+1) % P  if i+1 < len(L) else  L[i])
    INF = 10**18+10

    N,K = LMIIS()
    A = LMIIS()
    
    if N == K:
        print(multimul(A))
        return
    not_negative = []
    negative = []
    for a in A:
        if a < 0:
            negative.append(a)
        else:
            not_negative.append(a)
    if len(negative) == N and K % 2 == 1:
        print(multimul(sorted(negative,reverse=True)[:K]))
        return
    not_negative.sort(reverse=True)

    not_negative = deque(not_negative)
    negative.sort()
    negative = deque(negative)
    ans = 1
    num_multiplied = 0
    while num_multiplied < K:
        if num_multiplied == K-1 or len(negative) < 2 or len(not_negative) >= 2 and not_negative[0] * not_negative[1] > negative[0] * negative[1]:
            ans = ans * not_negative.popleft() % P
            num_multiplied += 1
        else:
            ans = ans * negative.popleft() * negative.popleft() % P
            num_multiplied += 2
    print(ans)
            


    
main()

Submission status: Accepted

Solution code:

INF = 10 ** 9 + 7
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

if K == 1:
    print(a[0])
    exit()

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

if a[0] < 0:
    ans = 1
    if K % 2 == 1:
        for i in range(K):
            ans *= a[i]
            ans %= INF
    else:
        for i in range(K):
            ans *= a[-i - 1]
            ans %= INF
    print(ans)
    exit()

sei = []
hu = []
for i in a:
    if i >= 0:
        sei.append(i)
    else:
        hu.append(i)
hu.sort()
seis = []
hus = []
total = []
ans = 1

if K % 2 != 0:
    ans = sei[0] % INF
    for i in range(2, len(sei), 2):
        seis.append(sei[i] * sei[i - 1])
else:
    for i in range(1, len(sei), 2):
        seis.append(sei[i] * sei[i - 1])
for i in range(1, len(hu), 2):
    hus.append(hu[i] * hu[i - 1])

total = hus + seis
total.sort(reverse=True)
for i in range(K // 2):
    ans *= total[i]
    ans %= INF

print(ans)

Submission status: Accepted

Solution code:
def solve():
    MOD = 10**9 + 7

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

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

    As.sort(key=lambda x: abs(x))

    if max(As) < 0 and K%2 != 0:
        ans = 1
        for A in As[:K]:
            ans *= A
            ans %= MOD
        print(ans)
        return

    pos0As, negAs = [], []
    for A in As:
        if A >= 0:
            pos0As.append(A)
        elif A < 0:
            negAs.append(A)
    pos0As.sort()
    negAs.sort(reverse=True)

    ans = 1
    rest = K
    while rest > 0:
        if rest == 1:
            ans *= pos0As.pop()
            rest -= 1
        else:
            if len(pos0As) < 2:
                ans *= negAs.pop()
                ans *= negAs.pop()
                rest -= 2
            elif len(negAs) < 2:
                ans *= pos0As.pop()
                rest -= 1
            else:
                pPos0 = pos0As[-1] * pos0As[-2]
                pNeg = negAs[-1] * negAs[-2]
                if pPos0 >= pNeg:
                    ans *= pos0As.pop()
                    rest -= 1
                else:
                    ans *= negAs.pop()
                    ans *= negAs.pop()
                    rest -= 2
        ans %= MOD

    print(ans)


solve()

Submission status: Accepted

Solution code:
def solve():
    MOD = 10**9 + 7
    INF = 10**10

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

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

    As.sort(key=lambda x: abs(x))

    if max(As) < 0 and K%2 != 0:
        ans = 1
        for A in As[:K]:
            ans *= A
            ans %= MOD
        print(ans)
        return

    As.reverse()

    ans = 1
    sgn = 1
    for A in As[:K]:
        ans *= A
        ans %= MOD
        if A < 0:
            sgn *= -1
        elif A == 0:
            sgn = 0

    if sgn >= 0:
        print(ans)
        return

    maxNeg, maxNotNeg = -INF, -INF
    minNeg, minPos = INF, INF
    for A in As[:K]:
        if A < 0:
            maxNeg = max(maxNeg, A)
        if A > 0:
            minPos = min(minPos, A)
    for A in As[K:]:
        if A < 0:
            minNeg = min(minNeg, A)
        if A >= 0:
            maxNotNeg = max(maxNotNeg, A)

    if maxNeg == -INF or maxNotNeg == -INF:
        ans *= pow(minPos, MOD-2, MOD) * minNeg
        ans %= MOD
    elif minNeg == INF or minPos == INF:
        ans *= pow(maxNeg, MOD-2, MOD) * maxNotNeg
        ans %= MOD
    else:
        if abs(maxNeg)*abs(minNeg) >= abs(minPos)*abs(maxNotNeg):
            ans *= pow(minPos, MOD-2, MOD) * minNeg
            ans %= MOD
        else:
            ans *= pow(maxNeg, MOD-2, MOD) * maxNotNeg
            ans %= MOD

    print(ans)


solve()

Submission status: Accepted

Solution code:
#正の場合、0の場合、負の場合で分ける
#負の数のみの場合は調整しようがない
#偶数の時は絶対値の大きい順
#奇数の時は絶対値の小さい順
#正の数のみの場合は大きい順
#大きい順

#他は調整できるので、正で大きくする方向で考える(正→0以上)
#負の数は偶数個ないと正にならないので二つ一組で先にかけて考える
#正の数も同様に先にかけて、その中で大きいものを選べば良い

#負の数が奇数個、正の数が奇数個の時(負の数が余る、正の数が余る)
#Kが偶数の時はいい感じに選んでく(N=kの時は仕方ないので全部)
#Kが奇数の時は正の中で最大のものを選ぶ
#負の数が偶数個、正の数が奇数個の時(正の数が余る)
#Kが偶数の時はいい感じに選んでく
#奇数の時は残りの正の中から選ぶ
#負の数が奇数個、正の数が偶数個の時(負の数が余る)
#N=Kの時は全部選ぶ、それ以外の場合は余った負の数はいらない
#Kが奇数の時は残りの正の中で最大のものを選べば良い
#負の数が偶数個、正の数が偶数個の時
#Kが奇数の時は残りの正の中で最大のものを選べば良い

#N=Kの時は別で分けて考えるとすると、負の数及び正の数によらず
#Kが偶数の時は大きいものからいい感じに選んでく
#Kが奇数の時は最後の残り一個は正の残りの中で最大のものを選ぶ
#と簡単に言い換えることができる

#x:配列
mod=10**9+7
def multarray(x):
    ret=1
    for i in x:
        ret*=i
        ret%=mod
    return ret

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

if n==k:
    print(multarray(a))
    exit()

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 len(am)==0:
    print(multarray(ap[:k]))
    exit()
if len(ap)==0:
    if k%2==0:
        print(multarray(am[:k]))
    else:
        print(multarray(am[::-1][:k]))
    exit()

apm2=[]
for i in range(len(am)//2):
    apm2.append((am[2*i]*am[2*i+1],0))
for i in range(len(ap)//2):
    apm2.append((ap[2*i]*ap[2*i+1],1))
apm2.sort(reverse=True)

#+の次にどこを見るのかをチェックしておく
p=0
ans=[]
for i in range(k//2):
    p+=(2*apm2[i][1])
    ans.append(apm2[i][0])

if k%2==0:
    print(multarray(ans))
    exit()

#ここで不正アクセスの可能性を避ける
#プラスが余ってない場合(一個減らして次のマイナス使う)
#余ってる場合もafter_contestで落ちる
#その一個をとるのが最適とは限らず、一個減らして次のマイナスの二個とる場合も
ans_cand=[]
#一個増やす場合
if p!=len(ap):
    ans_cand.append(multarray(ans)*ap[p]%mod)
if p>=2:
    #一個減らして二個増やす場合
    check_i=ans.index(ap[p-1]*ap[p-2])
    #0除算を避ける
    ans[check_i]=ap[p-2]
    ans.append(apm2[k//2][0])
    ans_cand.append(multarray(ans))
print(max(ans_cand))

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
z=-1
p=-1
mod=10**9+7
ans=1
for i in range(n):
    if a[i]==0:
        z=i
    elif a[i]>0:
        p=i
        break
a_abs=sorted(a,key=abs,reverse=True)
if (p==-1 and k%2==1) or n==k:
    for i in range(k):
        ans*=a[n-1-i]
        ans%=mod
    print(ans%mod)
    exit()
else:
    lp=-1
    lm=-1
    f=0
    for i in range(k):
        if a_abs[i]>=0:
            lp=i
        else:
            lm=i
            f+=1
    if f%2==0:
        for i in range(k):
          ans*=a_abs[i]
          ans%=mod
        print(ans)
    else:
        fp=-1
        fm=-1
        check_p=False
        check_m=False
        for i in range(k,n):
            if not check_p and a_abs[i]>=0:
                fp=i
                check_p=True
            elif not check_m and a_abs[i]<0:
                fm=i
                check_m=True
            if check_m and check_p:
                break
        if lp!=-1:
            if fp==-1:
              for i in range(k):
                if i==lp:
                  continue
                ans*=a_abs[i]
                ans%=mod
              ans*=a_abs[fm]
              ans%=mod
            elif fm==-1:
              for i in range(k):
                if i==lm:
                  continue
                ans*=a_abs[i]
                ans%=mod
              ans*=a_abs[fp]
              ans%=mod

            else:
                if a_abs[fm]*a_abs[lm]>=a_abs[fp]*a_abs[lp]:
                  for i in range(k):
                    if i==lp:
                      continue
                    ans*=a_abs[i]
                    ans%=mod
                  ans*=a_abs[fm]
                  ans%=mod
                else:
                  for i in range(k):
                    if i==lm:
                      continue
               	    ans*=a_abs[i]
                    ans%=mod
                  ans*=a_abs[fp]
                  ans%=mod
        else:
          for i in range(k):
            if i==lm:
              continue
            ans*=a_abs[i]
            ans%=mod
          ans*=a_abs[fp]
          ans%=mod
        print(ans%mod)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(key=abs, reverse=1)

mod = 10**9+7
ans = 1
sign = 1
for i in range(k):
    ans *= a[i]
    ans %= mod
    if a[i] < 0:
        sign *= -1
    elif a[i] == 0:
        sign = 0
if sign >= 0:
    print(ans)
else:
    t = None
    ok = True
    for i in reversed(range(k)):
        if a[i] < 0:
            break
    else:
        ok = False
    for j in range(k, n):
        if a[j] > 0:
            break
    else:
        ok = False

    if ok:
        t = (a[i], a[j])

    ok = True
    for i in reversed(range(k)):
        if a[i] > 0:
            break
    else:
        ok = False
    for j in range(k, n):
        if a[j] < 0:
            break
    else:
        ok = False

    if ok:
        if t is None:
            t = (a[i], a[j])
        else:
            if (t[1]*a[i] - t[0]*a[j]) * t[0]*a[j] < 0:
                t = (a[i], a[j])

    if t is None:
        ans = 1
        a.reverse()
        for i in range(k):
            ans *= a[i]
            ans %= mod
        print(ans)
    else:
        print(ans*t[1] * pow(t[0], mod-2, mod) % mod)

Submission status: Accepted

Solution code:
from sys import exit
from random import randrange
MOD = 10**9+7
n, k = map(int, input().split())
b = list(map(int, input().split()))
a = []
if n == k:
	ans = 1
	for x in b:
		ans *= x
		ans %= MOD
	print(ans)
	exit()
for x in b:
	if x != 0:
		a.append(x)
if len(a) < k:
	print(0)
	exit()

a.sort(key=lambda x: -abs(x))
#print(a)
ans = 1
minus = 0
for i in range(k):
	ans *= a[i]
	ans %= MOD
	if a[i] < 0:
		minus += 1

if minus%2 == 0:
	print(ans)
	exit()

if len(a) == k:
	if len(a) < n:
		print(0)
		exit()

for i in range(k, len(a)):
	if a[i] < 0:
		minus += 1

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

flg1 = False
for i in range(k-1, -1, -1):
	if a[i] * a[k] < 0:
		p, q = a[i], a[k]
		flg1 = True
		break

flg2 = False
for i in range(k, len(a)):
	if a[k-1] * a[i] < 0:
		r, s = a[k-1], a[i]
		flg2 = True
		break

if flg1 and flg2:
	if abs(q*r) >= abs(p*s):
		ans *= pow(p, MOD-2, MOD)
		ans *= q
		print(ans%MOD)
	else:
		ans *= pow(r, MOD-2, MOD)
		ans *= s
		print(ans%MOD)

elif flg1:
	ans *= pow(p, MOD-2, MOD)
	ans *= q
	print(ans%MOD)

elif flg2:
	ans *= pow(r, MOD-2, MOD)
	ans *= s
	print(ans%MOD)

else:
	print("コーナーケース多すぎん？")

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
mod=10**9+7
if n==k:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans)
    exit()
minus=[i for i in a if i<0]
plus=[i for i in a if i>=0]
from collections import deque
minus=deque(sorted(minus))
plus=deque(sorted(plus,reverse=True))

n_minus=len(minus)
n_plus=len(plus)
if n_minus==n:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=minus.popleft()
            ans+=mod
            ans%=mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans*=minus.pop()
            ans+=mod
            ans%=mod
        print(ans)
        exit()

ans=1
while k>1:
    if n_minus>1 and n_plus>1 and k!=3:
        if minus[0]*minus[1]>=plus[0]*plus[1]:
            n_minus-=2
            k-=2
            for _ in range(2):
                ans*=minus.popleft()
                ans%=mod
        else:
            n_plus-=2
            k-=2
            for _ in range(2):
                ans*=plus.popleft()
                ans%=mod
    elif n_minus>1 and n_plus>2 and k==3:
        ans*=max(minus[0]*minus[1]*plus[0],plus[0]*plus[1]*plus[2])
        ans%=mod
        k-=3
    elif n_minus>1:
        n_minus-=2
        k-=2
        for _ in range(2):
            ans*=minus.popleft()
            ans%=mod
    elif n_plus>1:
        n_plus-=2
        k-=2
        for _ in range(2):
            ans*=plus.popleft()
            ans%=mod

if k==1:
    if plus:
        ans*=plus.popleft()
        ans%=mod

print(ans)