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:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
minus=[]
plus=[]
zero=0
for i in range(n):
    if lis[i]<0:
        minus.append(lis[i])
    elif lis[i]>0:
        plus.append(lis[i])
    else:
        zero+=1
#print(plus)
#print(minus)
#print(zero)
p=len(plus)
m=len(minus)

if n-zero<k:
    ans=0
    print(ans%mod)
    sys.exit()
if p>=k:
    state="plus"
elif (k-p)%2==0:
    state="plus"
elif m>=k-p+1:
    if k%2==1:
        if p>0:
            state="plus"
        else:
            if zero>0:
                ans=0
                print(ans%mod)
                sys.exit()
            else:
                state="minus"
    else:    
        state="plus"
else:
    if zero>0:
        ans=0
        print(ans%mod)
        sys.exit()
    else:
        state="minus"
#print(state)
if state=="plus":
    ans=1
    plus.sort(reverse=True)
    minus.sort()
    pros=[]
    if k%2==1:
        ans*=plus[0]
        k-=1
        for i in range((p-1)//2):
            pros.append(plus[2*i+1]*plus[2*i+2])
    else:
        ans*=1
        for i in range(p//2):
            pros.append(plus[2*i]*plus[2*i+1])
    for i in range(m//2):
        pros.append(minus[2*i]*minus[2*i+1])
    pros.sort(reverse=True)
    for i in range(k//2):
        ans=(ans*pros[i])%mod
    print(ans%mod)
    sys.exit()
elif state=="minus":
    ans=1
    plus.sort()
    minus.sort(reverse=True)
    pros=[]
    ans*=minus[0]
    k-=1
    if k%2==1:
        ans*=plus[0]
        k-=1
        for i in range((p-1)//2):
            pros.append(plus[2*i+1]*plus[2*i+2])
    else:
        for i in range(p//2):
            pros.append(plus[2*i]*plus[2*i+1])
    for i in range((m-1)//2):
        pros.append(minus[2*i+1]*minus[2*i+2])
    pros.sort()
    for i in range(k//2):
        ans=(ans*pros[i])%mod
    print(ans%mod)
    sys.exit()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
from functools import reduce, lru_cache
import sys, copy


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def inverse(self):
        return pow(self.x, MOD - 2, MOD)

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N, K = LI()
    A = LI()

    if K == N:
        print(reduce(lambda x, y: x * y, A, ModInt(1)))
        exit()

    plus = sorted([ai for ai in A if ai >= 0], reverse=True)
    minus = sorted([ai for ai in A if ai < 0])

    if len(plus) == 0:
        if K % 2 == 1:
            print(reduce(lambda x, y: x * y, minus[-K:], ModInt(1)))
        else:
            print(reduce(lambda x, y: x * y, minus[:K], ModInt(1)))
        exit()

    ip, im = 0, 0
    ans = ModInt(1)

    j = 0

    while True:
        if j == K:
            break
        if j == K - 1:
            ans *= plus[ip]
            break

        # K - j >= 2
        if len(plus) - ip >= 2 and len(minus) - im >= 2:
            p = plus[ip] * plus[ip+1]
            m = minus[im] * minus[im+1]
            if p > m:
                ans *= p
                ip += 2
            else:
                ans *= m
                im += 2
            j += 2
        elif len(plus) - ip >= 2:
            ans *= plus[ip] * plus[ip+1]
            ip += 2
            j += 2
        elif len(minus) - im >= 2:
            ans *= minus[im] * minus[im+1]
            im += 2
            j += 2

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

pos = []
neg  = []
pool = []
zeros = 0
for i in range(n):
    if a[i]>0:
        pos.append(a[i])
    if a[i]<0:
        neg.append(a[i])
    if a[i]==0:
        zeros+=1
pos.sort()
neg.sort(reverse=True)
ans = []
if len(pos)==0:
    if len(neg)<k or (zeros>0 and k%2):
        ans = [0]
    else:
        if(k%2):
            for i in range(k):
                ans.append(neg[i])
        else:
            for i in range(k):
                ans.append(neg[-i-1])
    k = 0
elif len(pos)+len(neg)<k:
    ans = [0]
else:
    if k%2== 1:
        ans.append(pos[-1])
        pos.pop()
        k-=1
    while(k):
        if len(pos)<2 and len(neg)<2:
            if zeros>0:
                ans = [0]
                k = 0
            else:
                ans.append(pos[0])
                ans.append(neg[0])
                k -= 2
            break
        elif len(pos)<2:
            ans.append(neg[-1])
            ans.append(neg[-2])
            neg.pop()
            neg.pop()
        elif len(neg)<2:
            ans.append(pos[-1])
            ans.append(pos[-2])
            pos.pop()
            pos.pop()
        else:
            if neg[-1]*neg[-2] >= pos[-1]*pos[-2]:
                ans.append(neg[-1])
                ans.append(neg[-2])
                neg.pop()
                neg.pop()   
            else:
                ans.append(pos[-1])
                ans.append(pos[-2])
                pos.pop()
                pos.pop()
        k -= 2



res = 1
for i in range(len(ans)):
    res *= ans[i]
    res %= MOD

print(res)

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
MOD = 10**9+7
N, K = map(int, input().split())
X = list(map(int, input().split()))
if N==K:
    R = 1
    mc = 0
    for x in X:
        if x<0:
            mc += 1
        R = R*abs(x)%MOD
    if mc%2:
        print(((-1)*R)%MOD)
    else:
        print(R%MOD)
    sys.exit()
ps,ns=[],[]
for x in X:
    if x>=0:
        ps.append(x)
    else:
        ns.append(x)
ps.sort()
ns.sort()
if K%2 and len(ps)==0:
    R = 1
    ns = ns[::-1]
    for i in range(K):
        R = R*abs(ns[i])%MOD
    print((-1*R)%MOD)
    sys.exit()
if len(ps) == 0:
    R = 1
    for i in range(K):
        R = R*abs(ns[i])%MOD
    print(R)
    sys.exit()
nns = []
for i in range(len(ns)//2):
    nns.append(ns[2*i]*ns[2*i+1])
if K%2:
    R = ps.pop()
    K -= 1
else:
    R = 1
nns = nns[::-1]
K = K//2
#print(ps)
ps = ps[::-1]
pps  = []
for i in range(len(ps)//2):
    pps.append(ps[2*i]*ps[2*i+1])
pps =pps[::-1]
#print(pps, nns)
while K:
    x = 0
    f = 0
    if pps:
        x = pps.pop()
        f = 1
    if nns:
        if nns[-1] > x:
            if f:
                pps.append(x)
            x = nns.pop()
    R = R*x%MOD
    K-=1
print(R)

Submission status: Accepted

Solution code:
def solve(N, K, A):
    MOD = 10 ** 9 + 7
    ans = 1
    if A[-1] == 0 and K & 1:
        return 0
    if A[-1] < 0 and K & 1:
        for k in range(K):
            ans *= A[~k]
            ans %= MOD
        return ans

    i, j = 0, len(A) - 1
    if K & 1:
        ans *= A[-1]
        j -= 1
    for _ in xrange(K // 2):
        if A[i] * A[i + 1] > A[j] * A[j - 1]:
            ans *= A[i]
            ans %= MOD
            ans *= A[i+1]
            ans %= MOD
            i += 2
        else:
            ans *= A[j]
            ans %= MOD
            ans *= A[j-1]
            ans %= MOD
            j -= 2

    return ans

    

N, K = map(int, raw_input().split())
A = map(int, raw_input().split())
A.sort()
print solve(N, K, A)

Submission status: Accepted

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))

    Ap=[x for x in A if x>=0 ]
    Am=[abs(x) for x in A if x<0]

    if K==N:
        out=1
        for a in A:
            out*=a
            out%=10**9+7
        print(out)
        return


    if K%2==1 and len(Ap)==0:
        Am.sort()
        out=1
        for i in range(K):
            out*=Am[i]
            out%=10**9+7
        print((-out)%(10**9+7))
        return

    Ap.sort(reverse=True)
    Am.sort(reverse=True)
    
    ap_idx=0
    am_idx=0
    result=1

    for _ in range(0,K-1,2):
        if K%2==0 and ap_idx+1<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        elif K%2==1 and ap_idx+2<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        else:
            pmax=-1

        if am_idx+1<len(Am):
            mmax=Am[am_idx]*Am[am_idx+1]
        else:
            mmax=-1

        if pmax==-1 and mmax==-1:
            break

        if pmax>mmax:
            result*=pmax
            ap_idx+=2
        else:
            result*=mmax
            am_idx+=2

        result%=(10**9+7)
    
    if K%2==1:
        result*=Ap[ap_idx]

    print(result%(10**9+7))

main()

Submission status: Accepted

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
arr = sorted(list(map(int,stdin.readline().split())),key=lambda x:abs(x))
mod = 10**9+7
pos,neg = [],[]
for i in arr:
    if i>=0:
        pos.append(i)
    else:
        neg.append(i)
if not len(pos):
    ans = 1
    if k%2:
        for i in range(k):
            ans *= neg[i]
            ans %= mod
    else:
        for i in range(k):
            ans *= neg[-1-i]
            ans %= mod
else:
    ans = 1
    i=len(pos)-1
    j=len(neg)-1
    val = 0
    if n==k:
        for x in arr:
            ans *= x
            ans %= mod
    else:
        if k%2:
            ans *= pos[i]
            i -= 1
            val += 1
        while val != k:
            if i<1:
                ans *= neg[j]*neg[j-1]
                ans %= mod
                j -= 2
            elif j<1:
                ans *= pos[i]*pos[i-1]
                ans %= mod
                i -= 2
            else:
                if pos[i]*pos[i-1]>neg[j]*neg[j-1]:
                    ans *= pos[i]*pos[i-1]
                    ans %= mod
                    i -= 2
                else:
                    ans *= neg[j]*neg[j-1]
                    ans %= mod
                    j -= 2
            val += 2
print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
if n==k:
    p = 1
    for x in a:
        p = (p*x)%R
    print(p)
    exit()
a.sort()
b = [(abs(x),x) for x in a]
b.sort()
if a[-1]>0:
    c = [z[1] for z in b[n-k:n]]  # abs-max k elems
    neg = [x for x in c if x<0]
    if len(neg)%2 > 0:
        inmmin = BIG
        for j,y in enumerate(c):
            if y<0:
                inmmin = y
                inmminsuf = j
                break
        outpmax = BIG
        for j in range(n-1-k,-1,-1):
            if b[j][1]>0:
                outpmax = b[j][1]
                break
        inpmin = BIG
        for j,y in enumerate(c):
            if y>0:
                inpmin = y
                inpminsuf = j
                break
        outmmax = BIG
        for j in range(n-1-k,-1,-1):
            if b[j][1]<0:
                outmmax = b[j][1]
                break
        if inpmin==BIG or outmmax==BIG:
            useoutpmax = True
        elif outpmax==BIG:
            useoutpmax = False
        elif outpmax*inpmin>outmmax*inmmin:
            useoutpmax = True
        else:
            useoutpmax = False
        if useoutpmax:
            c[inmminsuf] = outpmax
        else:
            c[inpminsuf] = outmmax
elif k%2==0:
    c = [z[1] for z in b[n-k:n]]  # abs-max k elems
else:
    c = [z[1] for z in b[:k]]  # abs-min k elems
p = 1
for x in c:
    p = (p*x)%R
print(p)

Submission status: Accepted

Solution code:
from collections import deque

div = 10 ** 9 + 7

n, k = map(int, input().split())
A = deque(sorted([int(x) for x in input().split()]))
maxA = A[-1]
ans = 1
for i in range(k // 2):
    l1 = A[0]
    l2 = A[1]
    r1 = A[-1]
    r2 = A[-2]
    l = l1 * l2
    r = r1 * r2
    if k % 2 == 1 and maxA < 0:
        ans *= r
        ans %= div
        A.pop()
        A.pop()
    else:
        if l < r:
            ans *= r
            ans %= div
            A.pop()
            A.pop()
        else:
            ans *= l
            ans %= div
            A.popleft()
            A.popleft()
if k % 2 == 1:
    ans *= A[-1]
    ans %= div
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

arr.sort()
o_ind = bisect.bisect_left(arr,0)

minus = arr[:o_ind]
plus = arr[o_ind:]
plus.reverse()


mod = 10**9+7

canplus = True
types = -1

if (k == n and len(minus)%2==1):
    canplus = False
    types = 0
elif (k%2 == 1 and len(plus)==0):
    canplus = False

# print(canplus)

if canplus:
    if k % 2 == 0:
        ans = 1
        phead = 0
        mhead = 0

        for i in range(k // 2):
            tp1 = 1e-20
            tp2 = 1e-20
            if phead + 1 < len(plus):
                tp1 = plus[phead] * plus[phead + 1]

            if mhead + 1 < len(minus):
                tp2 = minus[mhead] * minus[mhead + 1]

            if tp1 < tp2:
                ans *= tp2
                ans %= mod
                mhead += 2
            else:
                ans *= tp1
                ans %= mod
                phead += 2
    else:
        if len(plus) > 0:
            ans = plus[0]
            phead = 1
            mhead = 0

            for i in range(k // 2):
                tp1 = 1e-20
                tp2 = 1e-20

                flag = False
                if phead + 1 < len(plus):
                    tp1 = plus[phead] * plus[phead + 1]

                if mhead + 1 < len(minus):
                    tp2 = minus[mhead] * minus[mhead + 1]


                if tp1 < tp2:
                    ans *= tp2
                    ans %= mod
                    mhead += 2
                else:
                    ans *= tp1
                    ans %= mod
                    phead += 2

    print(int(ans))
else:
    ans = 1
    if types == 0:
        for i in range(k):
            ans *= arr[i]
            ans %= mod

    else:
        minus.reverse()
        for i in range(k):
            ans *= minus[i]
            ans %= mod

    print(int(ans))

Submission status: Accepted

Solution code:
MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if all(ai < 0 for ai in a):
    ans = 1
    if k & 1:
        for ai in a[-k:]:
            ans = ans * ai % MOD
    else:
        for ai in a[:k]:
            ans = ans * ai % MOD
elif n == k:
    ans = 1
    for ai in a:
        ans = ans * ai % MOD
else:
    ans = 1
    a.sort(key=abs, reverse=True)
    cneg = sum(ai < 0 for ai in a[:k])
    cpos = sum(ai >= 0 for ai in a[:k])
    if cneg & 1 == 0:
        for ai in a[:k]:
            ans = ans * ai % MOD
    else:
        left = []
        r = k
        for ai in a:
            if ai < 0 and cneg > 1:
                ans = ans * ai % MOD
                cneg -= 1
                r -= 1
            elif ai >= 0 and cpos > 1:
                ans = ans * ai % MOD
                cpos -= 1
                r -= 1
            else:
                left.append(ai)
        ngs = [ai for ai in left if ai < 0]
        pss = [ai for ai in left if ai >= 0]
        if r == 1:
            ans = ans * pss[0] % MOD
        else:
            t = -1001001001001001001001
            if len(ngs) >= 2:
                t = ngs[0] * ngs[1]
            if len(pss) >= 2:
                t = max(t, pss[0] * pss[1])
            ans = ans * t % MOD
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
lis = list(map(int,input().split()))
def shinchan(before,after):
    an = 1
    key = 1
    for i in range(k):
        if key and abs(lis[i]) == before:
            an *= after
            key = 0
        else:
            an *= abs(lis[i])
        an %= 10 ** 9 + 7
    return an
plus = 0
minus = 0
zero = 0
p,m = [],[]
for num in lis:
    if num > 0:
        plus += 1
        p.append(num)
    elif num < 0:
        minus += 1
        m.append(num)
    else:
        zero += 1
p.sort(reverse=True)
m.sort(key = lambda x:abs(x),reverse=True)
lis.sort(key=lambda x:abs(x),reverse=True)
zissaiplus = 0
zissaiminus = 0
zissaizero = 0
for i in range(k):
    if lis[i] > 0:
        zissaiplus += 1
    elif lis[i] < 0:
        zissaiminus += 1
    else:
        zissaizero += 1
if zissaizero > 0:
    print(0)
    exit()
if zissaiminus % 2 == 0:
    ans = shinchan(-1,-1)
    print(ans)
    exit()
else:
    key1,key2 = 0,0
    if zissaiminus > 0 and plus-zissaiplus > 0:
        be1 = -m[zissaiminus-1]
        af1 = p[zissaiplus]
        key1 = 1
    if zissaiplus > 0 and minus-zissaiminus > 0:
        be2 = p[zissaiplus-1]
        af2 = -m[zissaiminus]
        key2 = 1
    if key1 == 1 and key2 == 1:
        if be2 * af1 >= be1 * af2:
            ans = shinchan(be1,af1)
        else:
            ans = shinchan(be2,af2)
    elif key1 or key2:
        if key1:
            ans = shinchan(be1,af1)
        else:
            ans = shinchan(be2,af2)
    else:
        if zero > 0:
            print(0)
            exit()
        lis.sort(key=lambda x:abs(x))
        ans = -shinchan(0,0)+10 ** 9 + 7
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from fractions import Fraction

MODULUS = 10**9+7

def all_negative(arr):
    for _, s in arr:
        if s != -1: return False
    return True

def has_negative(arr):
    for _, s in arr:
        if s == -1: return True
    return False

def has_positive(arr):
    for _, s in arr:
        if s == 1: return True
    return False

def largest_negative(arr):
    candidates = []
    for a, s in arr:
        if s == -1: candidates += [a]
    return max(candidates)

def largest_positive(arr):
    candidates = []
    for a, s in arr:
        if s == 1: candidates += [a]
    return max(candidates)

def smallest_negative(arr):
    candidates = []
    for a, s in arr:
        if s == -1: candidates += [a]
    return min(candidates)

def smallest_positive(arr):
    candidates = []
    for a, s in arr:
        if s == 1: candidates += [a]
    return min(candidates)

def prod(arr, MODULUS=None):
    ret = 1
    for a in arr:
        ret *= a
        if MODULUS is not None:
            ret = ret % MODULUS
    return ret

def sgn(x):
    if x == 0: return 0
    if x > 0: return 1
    if x < 0: return -1
    assert(False)

N, K = input().split(' ')
K = int(K)

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

def ans(A, K):

    if K == len(A):
        return prod(A, MODULUS)

    old_A = A
    A = [(abs(a), sgn(a)) for a in A]
    A = sorted(A)[::-1]

    if prod(s for (_, s) in A[0:K]) in [0, 1]:
        return prod([a for (a, _) in A[0:K]], MODULUS)

    chosen, not_chosen = A[0:K], A[K:]

    penalty_one = float("-inf")
    if has_positive(not_chosen):
        penalty_one = Fraction(largest_positive(not_chosen), smallest_negative(chosen))

    penalty_two = float("-inf")
    if has_positive(chosen) and has_negative(not_chosen):
        penalty_two = Fraction(largest_negative(not_chosen), smallest_positive(chosen))

    if penalty_one == float("-inf") and penalty_two == float("-inf"):
        if all_negative(chosen) and all_negative(not_chosen):
            A = A[::-1]
            return prod([a*s for (a, s) in A[0:K]], MODULUS)
        else:
            # print(chosen, not_chosen)
            assert(0 in old_A)
            return 0

    start = prod([a for (a, _) in chosen], MODULUS)

    penalty = max(penalty_one, penalty_two)

    start *= penalty.numerator
    start *= pow(penalty.denominator, MODULUS-2, MODULUS)

    start = ((start % MODULUS) + MODULUS) % MODULUS
    return start

# import random

# for _ in range(1000000):
#     test_case = [random.randint(-10, 10) for _ in range(5)]
#     # print(test_case)
#     ans(test_case, random.randint(0, 5))

print(ans(A, K))

Submission status: Accepted

Solution code:
import itertools


def out(X):
    return list(itertools.accumulate(X, func=lambda x, y: x * y % mod))[-1]


N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()], key=lambda x: -abs(x))
mod = 10**9 + 7
cnt = 0
ipos = ineg = -1
for i, a in enumerate(A[:K]):
    if a < 0:
        cnt += 1
        ineg = i
    else:
        ipos = i
if cnt % 2 == 0:
    print(out(A[:K]))
else:
    oneg = opos = -10**10
    for i, a in enumerate(A[K:]):
        if a < 0 and ipos != -1:
            X = A[:ipos] + A[ipos + 1:K] + [A[K + i]]
            oneg = out(X)
            beforeneg = A[ipos]
            afterneg = A[K + i]
            ipos = -1
        elif a > 0 and ineg != -1:
            Y = A[:ineg] + A[ineg + 1:K] + [A[K + i]]
            opos = out(Y)
            beforepos = A[ineg]
            afterpos = A[K + i]
            ineg = -1
    if oneg != -10**10 and opos != -10**10:
        #afterneg/beforeneg > afterpos>beforepos
        if afterneg * beforepos > afterpos * beforeneg:
            print(oneg)
        else:
            print(opos)
    elif oneg != -10**10 or opos != -10**10:
        print(max(opos, oneg))
    else:
        C = A[::-1]
        print(out(C[:K]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys


def main():
    mod = 1000000007                # 10^9+7
    def input():  return sys.stdin.readline().rstrip()
    def mi():     return map(int, input().split())
    def lmi():    return list(map(int, input().split()))
    def debug(x): print(x, file=sys.stderr)


    def check_positive(k, pos, neg):
        if k % 2 == 0:
            return (len(neg) // 2) * 2 + len(pos) >= k
        else:
            if pos:
                k -= len(pos) if len(pos) % 2 == 1 else len(pos) - 1
                return (len(neg) // 2) * 2 >= k
            return False

    def solve(n, k, L):
        pos = []
        zero_cnt = 0
        neg = []
        for elm in L:
            if elm < 0:
                neg.append(elm)
            elif elm > 0:
                pos.append(elm)
            else:
                zero_cnt += 1
        
        if check_positive(k, pos, neg):
            # 答えは正にできる。できるだけ大きい正の値を作ろう
            abs_neg = []
            tmp = sorted([abs(elm) for elm in neg], reverse=True)
            i = 0
            while i + 1 < len(tmp):
                abs_neg.append(tmp[i] * tmp[i+1])
                i += 2
            abs_neg.reverse()
            neg = abs_neg    # 昇順
            pos.sort()    # 昇順
            mul = 1
            cnt = 0
            # print(pos)
            # print(neg)
            while cnt < k:
                if pos and neg:
                    if (k - cnt) % 2 == 1:
                        mul = (mul * pos.pop()) % mod
                        cnt += 1
                    elif len(pos) >= 2 and pos[-1] * pos[-2] >= neg[-1]:
                        mul = (mul * pos.pop() * pos.pop()) % mod                            
                        cnt += 2
                    else:
                        mul = (mul * neg.pop()) % mod
                        cnt += 2                    
                elif pos:
                    mul = (mul * pos.pop()) % mod
                    cnt += 1
                elif neg:
                    assert cnt <= k - 2 and (k - cnt) % 2 == 0
                    mul = (mul * neg.pop()) % mod
                    cnt += 2
                else:
                    raise RuntimeError
            return mul

        elif zero_cnt != 0:
            # 答えは 0 にできる。0 が最善や
            return 0

        else:
            # 答えは負にしかならぬ。できるだけ 0 に近い負の値を作ろう
            tmp = [abs(elm) for elm in L]
            tmp.sort()
            mul = 1
            # print(tmp)
            for i in range(k):
                mul = (mul * tmp[i]) % mod
            return mod - mul
    
    
    n, k = mi()
    L = lmi()

    print(solve(n, k, L))




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def prod(l):
    r = 1
    mod = 10 ** 9 + 7
    for a in l:
        r = (r * a) % mod
    return r

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    P = [a for a in A if a >=0]
    M = [a for a in A if a < 0]
    PP, MM = len(P), len(M)
    P.sort(reverse=True)
    M.sort()
    k = 0
    p, m = 0, 0
    if PP == 0:
        if K % 2 == 0:
            return prod(M[:K])
        return prod(M[-K:])
    if P[0] == 0 and K % 2 == 1:
        return 0
    if K == N:
        return prod(A)
    while p + m < K:
        if m == MM:
            p += 1
        elif p == PP:
            m += 1
        elif P[p] > -M[m]:
            p += 1
        else:
            m += 1
    if m % 2 != 0:
        if m == MM or p == 0:
            m -= 1
            p += 1
        elif p == PP or m == 0:
            m += 1
            p -= 1
        elif M[m - 1] * M[m] >= P[p - 1] * P[p]:
            m += 1
            p -= 1
        else:
            m -= 1
            p += 1
    if p < 0 or p > PP:
        return prod(M[-K:])
    return prod(P[:p] + M[:m]) 

print(main())