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: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if N-K==0 and len(Am)%2==0 or len(Ap)==0 and K%2:
    c=1
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[0]<Ap[0]:
                c*=Am.popleft()
            else:
                c*=Ap.popleft()
        elif Am:
            c*=Am.popleft()
        elif Ap:
            c*=Ap.popleft()
        K-=1
        c=-c
        c%=mod
    #print("unko")

else:
    c=1
    h=0
    w=0
    a="unko"
    b="unko"
    while K and (Am or Ap) :
        if K==1 and len(Ap)==0:
            break
        while K and (Am or Ap) :
            if Am and Ap:
                if Am[0]>Ap[0]:

                    a=Am.pop()
                    c*=a
                    h+=1
                else:

                    b=Ap.pop()
                    c*=b

            elif Am:
                a=Am.pop()
                c*=a
                h+=1
            elif Ap:
                b=Ap.pop()
                c*=b
            K-=1
            c%=mod
    if h%2==1:
        if Am and Ap and a!="unko" and b!="unko":
            if Am[-1]*pow(b,mod-2,mod)>Ap[-1]*pow(a,mod-2,mod):
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        if Am:
            a=Am.pop()
            c*=a
            c*=pow(b,mod-2,mod)
        else:
            b=Ap.pop()
            c*=b
            c*=pow(a,mod-2,mod)


print(c%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if sum([1 for a in a_list if np.sign(a)==-1])==k:
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_min_big = max([num for num in a_list[:k] if np.sign(num)==-1])
        positive_min_big = min([num for num in a_list[:k] if np.sign(num)!=-1])
        negative_max_small = min([num for num in a_list[k:] if np.sign(num)==-1])
        positive_max_small = max([num for num in a_list[k:] if np.sign(num)!=-1])
        if positive_max_small/negative_min_big < negative_max_small/positive_min_big:
            remove = negative_min_big
            add = positive_max_small
        else:
            remove = positive_min_big
            add = negative_max_small
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
M = 1000000007
n, k = map(int, input().split())
l = list(map(int, input().split()))
k1 = k
pos = []
neg = []
zero = []
for i in l:
    if i > 0: pos.append(i)
    if i < 0: neg.append(i)
    if i == 0: zero.append(i)
pos.sort(reverse = True)
neg.sort()


if k == 1:
    if len(pos) > 0: print(pos[0] % M)
    elif len(zero) > 0: print(0)
    else: print(neg[0] % M)
    exit(0)

check = 0
if k % 2 == 1:
    check = 1
    k -= 3

p1, p2 = 0, 0
n1, n2 = len(pos), len(neg)

ans = 1
ch1, ch2 = 1, 1
while 1:
    if k == 0: break
    
    if p1 + 1 >= n1: ch1 = 0 
    if p2 + 1 >= n2: ch2 = 0
    
    if ch1 and ch2:
        k -= 2
        t1 = pos[p1] * pos[p1 + 1]
        t2 = neg[p2] * neg[p2 + 1]
        if t1 >= t2:
            p1 += 2
            ans = (ans * t1) % M
        else:
            p2 += 2
            ans = (ans * t2) % M
    elif ch1:
        k -= 2
        t1 = pos[p1] * pos[p1 + 1]
        ans = (ans * t1) % M
        p1 += 2
    elif ch2:
        k -= 2
        t2 = neg[p2] * neg[p2 + 1]
        ans = (ans * t2) % M
        p2 += 2
    else: break

if k != 0:
    if p1 + 1 >= n1 and p2 + 1 >= n2:
        ans = (ans * pos[p1]) % M
        ans = (ans * neg[p2]) % M
else:
    ch1, ch2 = 1, 1
    if check:
        if p1 + 2 >= n1: ch1 = 0 
        if p2 + 1 >= n2: ch2 = 0
        
        if ch1 and ch2:
            t1 = pos[p1] * pos[p1 + 1] * pos[p1 + 2]
            t2 = neg[p2] * neg[p2 + 1] * pos[p1]
            if t1 >= t2:
                ans = (ans * t1) % M
            else:
                ans = (ans * t2) % M
        elif ch1:
            t1 = pos[p1] * pos[p1 + 1] * pos[p1 + 2]
            ans = (ans * t1) % M
        elif ch2:
            if p1 < n1:
                t2 = neg[p2] * neg[p2 + 1] * pos[p1]
                ans = (ans * t2) % M
            else:
                if len(zero) > 0: ans = 0
                else:
                    tmp = []
                    for i in range(n):
                        if l[i] >= 0: tmp.append([l[i], 1])
                        else: tmp.append([-l[i], 0])
                    tmp.sort()
                    Ans = 1
                    for i in range(k1):
                        if tmp[i][1] == 1: Ans = (Ans * tmp[i][0]) % M
                        else: Ans = (Ans * tmp[i][0] * -1) % M
                    ans = Ans
        else:
            if len(zero) > 0: ans = 0
            else:
                t2 = neg[p2] * pos[p1] * pos[p1 + 1]
                ans = (ans * t2) % M
print(ans)

Submission status: Runtime Error

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

plst=sorted([x for x in lst if x>=0],reverse=True)
nlst=sorted([abs(x) for x in lst if x<0],reverse=True)
lenn=len(nlst)
lenp=len(plst)



if lenp==0 and k%2==1:
    sm=1
    for i in range(lenn-1,lenn-k-1,-1):
        sm*=-nlst[i]
        sm%=res
    print(sm)
    exit()

if lenp==0 and k%2==0:
    sm=1
    for i in range(k):
        sm*=nlst[i]
        sm%=res
    print(sm)
    exit()

nlstw=[nlst[2*i]*nlst[2*i+1] for i in range(lenn//2)]
lennw=len(nlstw)

if lenn==0 :
    sm=1
    for i in range(k):
        sm*=plst[i]
        sm%=res
    print(sm)
    exit()


ptoken=0
ntoken=0
nwtoken=0
token=0


sm=1
while token<k:

    if nwtoken==lennw or ptoken+1>=lenp : break

    if token==(k-1) or plst[ptoken]>nlst[ntoken]:
        sm*=plst[ptoken]
        sm%=res
        ptoken+=1
        token+=1
    else :
        if nlstw[nwtoken]>plst[ptoken]*plst[ptoken+1]:
            sm*=nlstw[nwtoken]
            sm%=res
            ntoken+=2
            nwtoken+=1
        else :
            sm*=plst[ptoken]*plst[ptoken+1]
            sm%=res
            ptoken+=2
        token+=2
else : print(sm);exit()

if ptoken+1>=lenp:
    if (k-token)%2==1:
        sm*=plst[ptoken]
        sm%=res
        token+=1
        while k>token:
            sm*=nlstw[nwtoken]
            sm%=res
            token+=2
            nwtoken+=1
    else :
        while k>token:
            if nwtoken==lennw:break
            sm*=nlstw[nwtoken]
            sm%=res
            token+=2
            nwtoken+=1
        if k!=token:
            sm*=plst[ptoken]
            sm%=res
    print(sm)
    exit()

if nwtoken==lennw:
    while k>token:
        sm*=plst[ptoken]
        sm%=res
        ptoken+=1
        token+=1
    print(sm)
    exit()

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 1
pls = 1
mod = 10**9+7
a_minu = [i for i in a if i <0]
if k==len(a):
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)

elif len(a_minu)==len(a) and k%2==1:
    a.sort(reverse=True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)

else:
    alis = []
    lasim = -1
    lasip = -1
    for i in a:
        if i<0:
            alis.append([-i,-1])
        else:
            alis.append([i,1])
    alis.sort(key=lambda x:x[0], reverse=True)
    for i in range(k):
        if alis[i][1]==-1:
            lasim =  i
        else:
            lasip = i
        ans *= alis[i][0]
        ans %= mod
        pls *= alis[i][1]
    if pls ==1:
        print(ans)
    else:
        ju= 0
        jud = 0
        if lasim >= 0:
            tmp = ans*pow(alis[lasim][0],mod-2,mod)
            for i in range(k,n):
                if alis[i][1]==-1:
                    continue
                else:
                    #print(alis[i][0],tmp)
                    tmp *= alis[i][0]
                    ju = 1
                    break
            if ju==0:
                tmp = 0
        if lasip >= 0:
            tmp2 = ans*pow(alis[lasip][0],mod-2,mod)
            for i in range(k,n):
                if alis[i][1]==1:
                    continue
                else:
                    #print(alis[i][0],tmp2)
                    tmp2 *= alis[i][0]
                    jud = 1
                    break
            if jud==0:
                tmp2 = 0

        if tmp2>=tmp:
            print(tmp2%mod)
        else:
            print(tmp%mod)

Submission status: Runtime Error

Solution code:
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n, k = MI()
mylist = LI()
temp1 = sorted(mylist)
temp2 = sorted(mylist, reverse = True)
mod = 1.0e9 + 7
start = 1
for i in range(k):
    start *= temp1[i]

for i in range(k):
    s1 = temp1[k-1-i]
    r1 = temp2[i]
    if r1 >= 1:
        break
    if (r1 == 0 or s1 == 0) and start < 0:
        start = 0
    elif start < start * r1 / s1:
        start =  start * r1 / s1
        
print(int(start % mod))

Submission status: Runtime Error

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

n, k, *a = map(int, open(0).read().split())
a.sort(key=lambda x: abs(x))
ans = reduce(lambda a, b: a * b, a[-k:])
c = a[-k:]
if ans < 0:
    c = a[-k:]
    neg = [i for i in c if i < 0]
    pos = [i for i in c if i > 0]
    b = sorted(a[:-k])
    if 0 >= b[-1] / neg[0] > b[0] / pos[0]:
        c = neg + [b[0]] + pos[1:]
    elif b[-1] / neg[0] <= 0:
        c = pos + [b[-1]] + neg[1:]
    else:
        c = a[:k]
print(reduce(lambda a, b: a * b % (10**9 + 7), c))

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7

def sgn(v):
    return (v > 0) - (v < 0)

def compute_answer():
    v.sort(key=abs, reverse=True)
    prod = 1
    sg = 1
    for a in xrange(k):
        prod *= v[a]
        prod %= mod
        sg *= sgn(v[a])

    if sg >= 0:
        return prod

    if max(v) <= 0:
        prod = 1
        for a in xrange(-k,0):
            prod *= v[a]
            prod %= mod
        return prod

    def find_pair(comp):
        i = k-1
        while i >= 0 and comp(v[i]): i -= 1
        j = k
        while j < n and not comp(v[j]): j += 1
        if j == n: j = i
        return i, j
    i, j = find_pair(lambda w: w >= 0)
    I, J = find_pair(lambda w: w <= 0)
    if I >= 0 and v[j] * v[I] < v[i] * v[J]:
        i = I
        j = J

    prod = v[j]
    for a in xrange(k):
        if a != i:
            prod *= v[a]
            prod %= mod
    return prod

for cas in xrange(input()):
    n, k = map(int, raw_input().strip().split())
    v = map(int, raw_input().strip().split())
    print compute_answer()

Submission status: Runtime Error

Solution code:
#import numpy as np
from functools import lru_cache, reduce
import operator


def main():
    MOD = int(1e9 + 7)
    N, K = tuple(int(c) for c in input().split())
    A = [int(c) for c in input().split()]
    A_plus = [x for x in A if x > 0]
    A_plus.sort(reverse=True)
    A_minus = [x for x in A if x < 0]
    A_minus.sort()
    cnt_0 = A.count(0)
    #A_abs = [(abs(x), x) for x in A]
    #A_abs.sort()
    #print(A_plus)
    #print(A_minus)
    #print(A_abs)

    def cum_mat(A, N):
        if len(A) == 0:
            return []
        t = 1
        ret = []
        for i in range(N):
            t *= A[i]
            ret.append(t)
        assert len(ret) == N
        return ret


    #minusからちょうど2つ選んで良い
    A_p_mult = cum_mat(A_plus, max(K, len(A_plus)))
    A_m_mult = cum_mat(A_minus, max(K, len(A_minus)))
    #A_m_pair = [A_minus[i] * A_minus[i+1] for i in range(0,len(A_minus), 2)]
    #print(A_m_pair)

    if K == 1:
        return max(A)

    if len(A_plus) == 0:
        #0またはminusだけから選ぶ場合
        if cnt_0 >= 1:
            return 0
        else:
            if K % 2 == 1:
                #答えは負になるので、絶対値が小さい順に積を取る
                ans = 1
                for t in list(reversed(A_minus))[:K]:
                    ans *= t
                    ans %= MOD
                return ans
            else:
                #答えは正になるので、絶対値が大きい順に積をとる
                ans = 1
                for t in A_minus[:K]:
                    ans *= t
                    ans %= MOD
                return ans

    #答えが正にできない場合で、0を含む場合は0
    if cnt_0 >= 1:
        if len(A_plus) + len(A_minus) < K:
            #0を選ばないといけない場合
            return 0
        elif len(A_plus) + len(A_minus) == K and len(A_minus) % 2 == 1:
            #minusから偶数個取れない場合
            return 0


    @lru_cache(maxsize=None)
    def solve(l: int, m: int):
        #print(l, m)
        if m == 0:
            return A_p_mult[l-1]
        elif l == 0:
            if m % 2 == 0:
                return  A_m_mult[m-1]
            else:
                return reduce(operator.mul, list(reversed(A_minus))[:m])
        if m % 2 == 0:
            p_val = A_p_mult[l-1]
            m_val = A_m_mult[m-1]
            #m_val = A_m_pair[m//2-1]
            return p_val * m_val
        else:
            if ans > -10000000000000000000:
                return -10000000000000000000
            else:
                p_val = reduce(operator.mul, list(reversed(A_plus))[:l])
                m_val = reduce(operator.mul, list(reversed(A_minus))[:m])
                return p_val * m_val
        

    ans = -10000000000000000000
    for l in range(K+1):
        if l > len(A_plus):
            ans = max(ans, solve(len(A_plus), K-len(A_plus)))
        elif K - l > len(A_minus):
            ans = max(ans, solve(K-len(A_minus), len(A_minus)))
        else:
            m = K - l
            ans = max(ans, solve(l, m))
    return ans

if __name__ == "__main__":
    MOD = int(1e9 + 7)
    ret = main()
    ret %= MOD
    print(ret)

Submission status: Runtime Error

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


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()
    A = deque(A)
    #    print(A)
    A_minus = deque([s for s in A if s < 0])
    A_plus = deque([s for s in A if s >= 0])

    #    print(A_plus)
    #    print(A_minus)
    AA = deque([])
    AAm = deque([])
    if N == K:
        ans = 1
        for i in A:
            ans *= i % 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.pop(0)
            elif len(AA) ==0:
                temp = AAm.pop(0)
            elif AAm[0] > AA[0]:
                temp = AAm.popleft()
            else:
                temp = AA.popleft()
            ans *= temp % mod
        print(ans % mod)

    elif len(A_plus) == 0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop() % 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.pop(0)
            elif len(AA) ==0:
                temp = AAm.pop(0)
            elif AAm[0] > AA[0]:
                temp = AAm.popleft()
            else:
                temp = AA.popleft()
            ans *= temp % mod
        print(ans % mod)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
plist=[]
mlist=[]
ans=1
p=10**9+7
for i in range(N):
    if A[i]>=0:
        plist.append(A[i])
    else:
        mlist.append(A[i])
if len(plist)==0:
    if K%2==1:
        A.sort(reverse=True)
    else:
        A.sort()
    for i in range(K):
        ans=(ans*A[i])%p
    print(ans%p)
elif len(plist)==1:
    #print(plist,mlist)
    mlist.sort()
    if K%2==1:
        ans=plist[0]
    for i in range(K-1):
        ans=(ans*mlist[i])%p
    print(ans%p)
else:
    ans=1
    plist.sort(reverse=True)
    mlist.sort()
    pmap=deque()
    mmap=deque()
    if K%2==1:
        ans=plist[0]%p
        plist.pop(0)
        K=K-1
    #print(plist,mlist)
    for i in range(0,len(plist)-1,2):
        pmap.append(plist[i]*plist[i+1])
    for i in range(0,len(mlist)-1,2):
        mmap.append(mlist[i]*mlist[i+1])
    #print(K)
    mapnum=K//2
    #print(mapnum)
    #print(pmap,mmap,ans)
    for i in range(mapnum):
        if (len(pmap)>0)and(len(mmap)>0):
            pl=pmap.popleft()
            mi=mmap.popleft()
            if pl>mi:
                ans=(ans*pl)%p
                mmap.appendleft(mi)
            else:
                ans=(ans*mi)%p
                pmap.appendleft(pl)
        elif len(pmap)==0:
            mi=mmap.popleft()
            ans = (ans *mi) % p
        else:
            pl=pmap.popleft()
            ans = (ans *pl) % p
    print(ans)

Submission status: Runtime Error

Solution code:
n, k = (int(x) for x in input().split())
a = list(map(int, input().split()))
mod = pow(10,9)+7
a_po =[]
a_ne =[]
po = 0
ne = 0
for i in a:
	if i>=0:
		a_po.append(i)
	else:
		a_ne.append(i)
a_po.sort()
a_po.reverse()
a_ne.sort()
ans = 1
if len(a_po)==0 and k%2==1:
	a_ne.reverse()
	for i in range(k):
		ans*=a_ne[i]
	print((ans+mod)%mod)
elif len(a_po)==0:
	for i in range(k):
		ans*=a_ne[i]
	print((ans+mod)%mod)
elif len(a_ne)==0:
	for i in range(k):
		ans*=a_po[i]
	print((ans+mod)%mod)
else:
	if k%2==1:
		ans*=a_po.pop(0)
		k-=1
	for i in range(int(k/2)):
		
		if po*2<len(a_po) and ne*2<len(a_ne):
			su_po = a_po[2*po]*a_po[2*po+1]
			su_ne = a_ne[2*ne]*a_ne[2*ne+1]
			if su_po>su_ne:
				po+=1
				ans*=su_po
			else:
				ne+=1
				ans*=su_ne
		elif po*2<len(a_po) and po*2>=len(a_po):
			su_ne = a_ne[2*ne]*a_ne[2*ne+1]
			ans*=su_ne
			ne+=1
		elif po*2>=len(a_po) and po*2<len(a_po):
			su_po = a_po[2*po]*a_po[2*po+1]
			ans*=su_po
			po+=1
		ans = (ans+mod)%mod
	print((ans+mod)%mod)

Submission status: Runtime Error

Solution code:
def maxProductSubarrayOfSizeK(A, n, k): 
  
    MOD = 10**9+7
    A.sort()   
    product = 1
    
    ALL = []
    Po = []
    Ne = []
    for i in A:
        ALL.append(abs(i))
        if i > 0:
            Po.append(i)
        else:
            Ne.append(i)

    A.sort(reverse=True)
    ALL.sort(reverse=True)
    Po.sort(reverse=True)
    Ne.sort()
    
    if A[k-1] < 0 and k%2 ==1:
        for i in range(k):
            product *= -Ne[i]
            product %= MOD
        
  
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product *= A[i] 
            product %= MOD
        return product 
  
    i = 0  
    j = n - 1
  
    if (k & 1): 
        product *= A[j] 
        j-= 1
        k-=1
  
    k >>= 1
  
    for itr in range( k) : 
  
        left_product = A[i] * A[i + 1] 
  
        right_product = A[j] * A[j - 1] 
  
        if (left_product > right_product) : 
            product *= left_product 
            product %= MOD
            i += 2
          
        else : 
            product *= right_product 
            product %= MOD
            j -= 2
  
    return product
MOD = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
print((maxProductSubarrayOfSizeK(A, N, K))% MOD)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

A_p = []
A_n = []
A_z = []
mod = 10**9 + 7

for a in A:
    if a>0:
        A_p.append(a)
    elif a<0:
        A_n.append(a)
    else:
        A_z.append(a)

ans = 1

if (len(A_n) >= K-len(A_p)) and ((K-len(A_p))%2==0):
    # Z > 0:
    A_p.sort()
    A_n.sort()

    prev = None
    for a_n in A_n:
        idx = bisect.bisect_left(A_p, -a_n)
        if idx > len(A_p) - K:
            bisect.insort_left(A_p, -a_n)
            prev = idx
        else:
            if prev is not None:
                A_p.pop(idx)

    A_p.sort(reverse=True)
    # print(A_p)
    for i in range(K):
        ans = ans * A_p[i]
        ans = ans % mod

    print(ans)
    sys.exit()

if len(A_z)>0:
    print(0)
    sys.exit()


# Z < 0:
# print('Negative')
A_p.sort()
A_n.sort()

prev = None
for a_n in A_n:
    idx = bisect.bisect_left(A_p, -a_n)
    bisect.insort_left(A_p, -a_n)

for i in range(K):
    ans = ans * A_p[i]
    ans = ans % mod

ans = (-ans) % mod
print(ans)
sys.exit()

Submission status: Runtime Error

Solution code:
N , K = map(int, input().split())
A =list(map(int, input().split()))
mod = 10**9 + 7
count =0
for k in range(len(A)):
    if A[k] == 0:
        count +=1
        A[k] = float("inf")
if N-count < K:
    print(0)
    exit()
A.sort()
A = A[:N-count]
A.sort(reverse=True)
#print(A)
ans = 1
plus = 0
minus = -1
countp = 0
countm = 0
if A[0] >0:
    for k in range(K):
        if abs(A[plus]) >= abs(A[minus]):
            ans = ans*A[plus]%mod
            plus+=1
        else:
            ans = ans*A[minus]%mod
            if A[minus] <0:
                lasm = 0+minus
            minus-=1
            
    if minus%2 == 1:
        print(ans%mod)
    else:
        a = max(A[plus], A[minus])
        print(ans//A[lasm]*a%mod)
else:
    for k in range(K):
        ans = ans*A[k]%mod
    print(ans%mod)

Submission status: Runtime Error

Solution code:
def maxProductSubarrayOfSizeK(A, n, k): 
  
    MOD = 10**9+7
    A.sort()   
    product = 1
    
    ALL = []
    Po = []
    Ne = []
    for i in A:
        ALL.append(abs(i))
        if i > 0:
            Po.append(i)
        else:
            Ne.append(i)

    A.sort(reverse=True)
    ALL.sort(reverse=True)
    Po.sort(reverse=True)
    Ne.sort()
    
    if A[k-1] < 0 and k%2 ==1:
        for i in range(k):
            product *= -Ne[i]
            product %= MOD
        
  
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
  
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product *= A[i] 
            product %= MOD
        return product 
  
    i = 0  
    j = n - 1
  
    if (k & 1): 
        product *= A[j] 
        j-= 1
        k-=1
  
    k >>= 1
  
    for itr in range( k) : 
  
        left_product = A[i] * A[i + 1] 
  
        right_product = A[j] * A[j - 1] 
  
        if (left_product > right_product) : 
            product *= left_product 
            product %= MOD
            i += 2
          
        else : 
            product *= right_product 
            product %= MOD
            j -= 2
  
    return product

N,K = map(int,input().split())
A = list(map(int,input().split()))
print((maxProductSubarrayOfSizeK(A, N, K))% MOD)

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if N-K==0 and len(Am)%2==0 or len(Ap)==0 and K%2:
    c=1
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[0]<Ap[0]:
                c*=Am.popleft()
            else:
                c*=Ap.popleft()
        elif Am:
            c*=Am.popleft()
        elif Ap:
            c*=Ap.popleft()
        K-=1
        c=-c
        c%=mod
    #print("unko")

else:
    c=1
    h=0
    w=0
    a="unko"
    b="unko"
    while K and (Am or Ap) :
        if K==1 and len(Ap)==0:
            break
        while K and (Am or Ap) :
            if Am and Ap:
                if Am[0]>Ap[0]:

                    a=Am.pop()
                    c*=a
                    h+=1
                else:

                    b=Ap.pop()
                    c*=b

            elif Am:
                a=Am.pop()
                c*=a
                h+=1
            elif Ap:
                b=Ap.pop()
                c*=b
            K-=1
            c%=mod
    if h%2==1:
        if Am and Ap and a!="unko" and b!="unko":
            if Am[-1]*pow(b,mod-2,mod)>Ap[-1]*pow(a,mod-2,mod):
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        if len(Am) and b!="unko":
            a=Am.pop()
            c*=a
            c*=pow(b,mod-2,mod)
        else:
            b=Ap.pop()
            c*=b
            c*=pow(a,mod-2,mod)


print(c%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
n,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True,key=lambda x: abs(x))

def main(n,k,a):
    a = np.array(a)
    if (a<0).all() and k%2==1 : return np.prod(a[-1*k:])
    prod = 1
    for i in range(k-2):
        prod = (prod*a[i])%1000000007

    if prod<0:
        p_flag,n_flag = False,False
        p_done,n_done = False,False
        p,n = 0,0
        for i in range(k-2,len(a)):
            if a[i] > 0 :
                if not p_flag:
                    p = a[i]
                    p_flag =True
                if n_flag and not n_done:
                    n *= a[i]
                    n_done = True
            if a[i] < 0:
                if not n_flag:
                    n = a[i]
                    n_flag =True
                if p_flag and not p_done:
                    p *= a[i]
                    p_done = True
    if prod>0:
        p_flag,n_flag = False,False
        p_done,n_done = False,False
        p,n = 0,0
        for i in range(k-2,len(a)):
            if a[i] > 0 :
                if not p_flag:
                    p = a[i]
                    p_flag =True
                else:
                    p *= a[i]
                    p_done = True
            if a[i] < 0:
                if not n_flag:
                    n = a[i]
                    n_flag =True
                else:
                    n *= a[i]
                    n_done = True
    print(prod*n,prod*p)
    return max(prod*n,prod*p)

print(main(n,k,a)%1000000007)

Submission status: Runtime Error

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

if N - A.count(0) < K:
    print(0)
    exit(0)

plus = []
minus = []
for a in A:
    if a > 0:
        plus.append(a)
    elif a < 0:
        minus.append(a)
    else:
        plus.append(a)
        minus.append(a)


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

plus.sort(reverse=True)
minus.sort()

if len(minus) == 0:
    for k in range(K):
        ans *= plus[k]
        ans %= MOD
    print(ans)
    exit(0)

i = 0
j = 0

if K % 2 == 1 and len(plus) > 0:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
minusA = []
for i in A:
    if i < 0: minusA.append(-i)
minusA.sort(reverse=True)
ans = 1
minus = 0
seki = 1
for i in range(K):
    if A[i] < 0: seki *= -1
if K == 1: print(A[0])
else:
    for i in range(K - 1):
        if  i * 2 <= len(minusA) and minusA:
            if seki > 0:
                if A[K - i * 2 - 1] * A[K - i * 2 - 2] < minusA[i * 2] * minusA[i * 2 + 1]: minus += 2
    for i in range(K - minus):
        ans = ans * A[i] % (10 ** 9 + 7)
    for i in range(minus):
        ans = ans * minusA[i] % (10 ** 9 + 7)
    if ans < 0: ans += 10 ** 9 + 7
    print(ans)