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:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N,K = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype='int64')
    plus = A[np.where(A > 0)]
    minus = A[np.where(A < 0)] * -1
    
    count_p = np.count_nonzero(A > 0)
    count_m = np.count_nonzero(A < 0)
    count_zero = np.count_nonzero(A == 0)

    def p(plus, minus, K):
        plus.sort()
        minus.sort()

        if K % 2 == 0:
            r = 1
        else:
            plus[0]
            plus = plus[1:]
        
        p = 0
        m = 0
        while K > 0:
            if len(plus) <= p+1:
                r *= int(minus[m]*minus[m+1])
                m+=2
            elif len(minus) <= m+1:
                r *= int(plus[p]*plus[p+1])
                p+=2
            elif plus[p]*plus[p+1] > minus[m]*minus[m+1]:
                r *= int(plus[p]*plus[p+1])
                p+=2
            else:
                r *= int(minus[m]*minus[m+1])
                m+=2
            K -= 2
        return (r+(10**9+7))%(10**9+7)
            
    def m(plus, minus, K):
        plus = np.sort(plus)[::-1]
        minus = np.sort(minus)[::-1]

        if K % 2 == 0:
            r = 1
        else:
            minus[0]
            minus = minus[1:]

        p = 0
        m = 0
        while K > 0:
            if len(plus) <= p+1:
                r *= int(minus[m]*minus[m+1])
                m+=2
            elif len(minus) <= m+1:
                r *= int(plus[p]*plus[p+1])
                p+=2
            elif plus[p]*plus[p+1] < minus[m]*minus[m+1]:
                r *= int(plus[p]*plus[p+1])
                p+=2
            else:
                r *= int(minus[m]*minus[m+1])
                m+=2
            K -= 2
        return (r+(10**9+7))%(10**9+7)
            
    
    if N-K == 0:
        if count_zero > 0:
            print(0)
            return
        else:
            if count_m % 2 == 1:
                #minus
                print(m(plus, minus, K))
                return
            else:
                #plus
                print(p(plus,minus,K))
                return
    else:
        if count_p > 0:
            if count_zero <= N-K:
                #plus
                print(p(plus,minus,K))
                return
            else:
                print(0)
                return
        else:
            if count_zero > 0:
                print(0)
                return
            else:
                #minus
                print(m(plus, minus, K))
                return

main()

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:
from collections import deque

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

A.sort(reverse=True)

deque = deque()
for a in A:
    deque.append(a)

ans = 1
cnt = 0
if K%2 == 1:
    ans *= deque.popleft()
    cnt += 1
    
if ans <= 0:
    for i in range(K-1):
        ans *= deque.popleft()
        ans %= mod
else:
    while cnt < K:
        x1 = deque.popleft()
        x2 = deque.popleft()
        deque.appendleft(x2)
        deque.appendleft(x1)
        y1 = deque.pop()
        y2 = deque.pop()
        if x1*x2 < y1*y2:
            ans *= y1*y2
            ans %= mod
            cnt += 2
        else:
            ans *= x1*x2
            ans %= mod
            x1 = deque.popleft()
            x2 = deque.popleft()
            deque.append(y2)
            deque.append(y1)
            cnt += 2
            
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int, raw_input().split(' '))
ais = map(int , raw_input().split(' '))

pos = [ai for ai in ais if ai > 0]
pos.sort(key = lambda x:-x)
neg = [-ai for ai in ais if ai < 0]
neg.sort(key = lambda x:-x)

def g(neg, k):
	i = len(neg) -1
	r = 1
	while(k):
		r *= -neg[i]
		i -=1
		k -=1
		r %= (10 ** 9) + 7
	return r
def gg(pos, k):
	r =  1
	for i in range(k):
		r *= pos[i]
		r %= (10 **9) + 7
	return r
def f(pos,neg, k):

	if len(pos) == 0: return g(neg, k)
	if len(neg) <= 1: return gg(pos, k)

	i,j = 0,0
	p = 1
	mod = (10 ** 9) + 7
	while(k >= 2 and i < len(pos) and j+1 < len(neg) and (len(pos) - i + len(neg) - j) >= k):
		if j + 1 < len(neg):
			if neg[j] * neg[j+1] > pos[i] * (pos[i+1] if i+1 < len(pos) else 1):
				p *= neg[j] * neg[j+1]
				p %= mod
				j += 2
				k -= 2
			else:
				p *= pos[i]
				i +=1
				p %= mod
				k -=1
	while(k and i < len(pos)):
		p *= pos[i]
		p %+ mod
		k-=1
		i+=1
	return p
print f(pos,neg, k) if k > 1 else max(ais)

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.pop(0)
            else:
                temp = AA.pop(0)
            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.pop(0)
            else:
                temp = AA.pop(0)
            ans *= temp % mod
        print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop, heapify, heappush
mod = 10**9 + 7
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
plus = []
minus = []
zero = []
ans = []
for a in A:
    if a > 0:
        plus.append(-a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(a)
heapify(plus)
heapify(minus)
cnt = 0
last_minus = 0
last_plus = 0
if len(plus) + len(minus) < K:
    print(0)
    sys.exit()

if len(plus) == 0:
    num = 1
    minus.sort(reverse=True)
    for x in minus[:K]:
        num *= x
        num %= mod
    print(num%mod)
    sys.exit()

if len(minus) == 0:
    num = 1
    plus.sort(reverse=True)
    for x in plus[:K]:
        if x < 0:
            x = -x
        num *= x
        num %= mod
    print(num%mod)
    sys.exit()

flag = 0

for i in range(K):
    if len(plus) > 0 and len(minus) > 0:
        a = heappop(plus)
        b = heappop(minus)
    elif len(plus) == 0:
        flag = 1
        break
    else:
        flag = 2
        break
    if a >= b:
        ans.append(b)
        if a == 0:
            continue
        heappush(plus, a)
        cnt += 1
        last_minus = b
    else:
        ans.append(a)
        if b == 0:
            continue
        heappush(minus, b)
        last_plus = a

if flag == 2:
    for i in range(K - len(ans)):
        a = heappop(plus)
        last_plus = a
        ans.append(a)

if flag == 1:
    for i in range(K - len(ans)):
        a = heappop(minus)
        last_minus = a
        cnt += 1
        ans.append(a)

if cnt%2 == 0:
    num = 1
    for a in ans:
        if a < 0:
            a = -a
        num = (num * a%mod)%mod
    print(num%mod)
    sys.exit()
else:
    num = 1
    for a in ans:
        num = (num * a%mod)%mod
    if len(plus) == 0:
        a = heappop(minus)
        num = (num * a //last_plus)%mod
        print(num%mod)
    elif len(minus) == 0:
        a = heappop(plus)
        num = (num * a //last_minus)%mod
        print(num%mod)
    else:
        a = heappop(plus)
        b = heappop(minus)
        if a / (-last_minus) >= -b / last_plus:
            num = (num * a //last_minus)%mod
            print(num%mod)
        else:
            num = (num * b //last_plus)%mod
            print(num%mod)

Submission status: Runtime Error

Solution code:
import sys, math
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=lambda x: abs(x))[::-1]
P = int(1e9+7)

ans = 1
hu = None
sei = None
flg = False
for a in A:
    flg = a > 0
    if flg:
        break
if not flg:
    for i in range(1, K+1):
        ans = (ans * A[-i]) % P
    print(ans)
    sys.exit()
if K == N:
    for a in A:
        ans = (ans * a) % P
    print(ans)
    sys.exit()

for i, a in zip(range(K), A):
    if a > 0:
        if sei:
            ans = (ans * sei) % P
        sei = a
    else:
        if not hu:
            hu = a
        else:
            ans = (ans * a * hu) % P
            hu = None

ptn1, ptn2 = -math.inf, -math.inf
if hu:
    if not sei:
        for i in range(K, N):
            if A[i] > 0:
                ptn1 = sei * A[i]
                break
        for i in range(K, N):
            if A[i] <= 0:
                ptn2 = hu * A[i]
                break
        ans = (ans * max(ptn1, ptn2)) % P
    else:
        for i in range(K, N):
            if A[i] > 0:
                ans = (ans*A[i])%P
                break
else:
    if sei:
        ans = (ans * sei) % P
print(ans % P)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
large_p = 10**9 + 7
from collections import deque
from copy import deepcopy
from operator import mul
from functools import reduce

def main():
    n, k, *a = map(int, read().split())
    if n == 1:
        print(a[0] % large_p)
        sys.exit()
    elif n == 2:
        r = max(a[0], a[1], a[0] * a[1])
        print(r % large_p)
        sys.exit()
    a2 = [i for i in a if i > 0] #plus
    a3 = [-i for i in a if i < 0] #minus
    a2.sort()
    a3.sort(reverse=True)
    #res = deepcopy(a2[(n - k):])
    if k < len(a2):
        res = deepcopy(a2[:-k])
    else:
        res = deepcopy(a2)
    resd = deque(res)
    a3d = deque(a3)
    a2dd = deque()
    a3dd = deque()
    cnt = 0
    while cnt < k:
        if a3d and resd[-1] < a3d[0]:
            a2dd.append(resd.pop())
            t = a3d.popleft()
            resd.appendleft(t)
            a3dd.append(t)
            cnt += 1
        else:
            break
    r = reduce(mul, resd)
    if r < 0:
        r = r // a3dd[-1] * -1
        r *= a2dd[-1]
    r = r % large_p
    if r < 0:
        r += large_p
    print(r)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
mod=10**9+7
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
nega=[]
pos=[]
for m in a:
  if m<0:
    nega.append(m)
  elif m>0:
    pos.append(m)
nega.sort()
pos.sort(reverse=True)
nlen=len(nega)
plen=len(pos)
if nlen+plen<k:
  print(0)
  exit()
ans=1
if plen==0 and k%2==1:
  nega.sort(reverse=True)
  for i in range(k):
    ans*=nega[i]%mod
    ans%=mod
  print(ans)
  exit()
i,j,c=0,0,0
while i<nlen and j<plen and c<k:
  if abs(nega[i])<=pos[j] or i==nlen:
    ans*=pos[j]%mod
    ans%=mod
    j+=1
    c+=1
  elif abs(nega[i])>pos[j] or j==plen:
    ans*=abs(nega[i])%mod
    ans%=mod
    i+=1
    c+=1
if c<k:
  if i<nlen:
    for i2 in range(i,nlen):
      ans*=abs(nega[i])%mod
      ans%=mod
      i+=1
      c+=1
      if c==k:
        break
  elif j<plen:
    for j2 in range(j,plen):
      ans*=pos[j]%mod
      ans%=mod
      j+=1
      c+=1
      if c==k:
        break
if i%2==1:
  if j<plen:
    ans*=pow(abs(nega[i-1]),mod-2,mod)*(pos[j]%mod)
  elif j==plen and i<nlen:
    ans*=pow(pos[j-1],mod2,mod)*(abs(nega[i])%mod)
print(ans%mod)

Submission status: Runtime Error

Solution code:
aa=input("").split(" ")
bb=input("").split(" ")
n=int(aa[0])
k=int(aa[1])
b=[]
for i in range(n):
    b+=[int(bb[i])]
b.sort(reverse=True)
bbb=[]
for i in range(n):
    bbb+=[b[i]]
blist=[]
for i in range(n):
    if (abs(bbb[0])>abs(bbb[n-i-1])):
        blist+=[bbb[0]]
        bbb=bbb[1:]
    else:
        blist+=[bbb[n-1-i]]
        bbb=bbb[:n-1-i]
        
print(b)
print(bbb)
print(blist)
s=1
if (b[0]<=0 ):
    if (k%2==1):
        for i in range(k):
            s*=b[i]
            s%=(10*9+7)
    else:
        for i in range(k):
            s*=b[n-i]
            s%=(10**9+7)
        
else:
    
    aaaa=1
    for i in range(k):
        s*=blist[i]
        s%=(10**9+7)
        aaaa*=blist[i]/abs(blist[i])
    kkkkk=k
    while(aaaa<0):
        s/=blist[kkkk-1]
        s*=blist[kkkk]
        s%=(10**9+7)
        aaaa=blist[i]/abs(blist[i])
        kkkk+=1


        

        
        
    
    
    


print(s)

Submission status: Runtime Error

Solution code:
import heapq
mod = 10**9+7
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = []
M = []
for a in A:
    if a > 0:
        P.append(-a)
    else:
        M.append(a) 
A.sort(reverse=True)
heapq.heapify(P)
heapq.heapify(M)
ans2 = 1
i = 0
while i < K-1:
    i += 1
    if(len(P)>=2 and len(M)>=2):
        i +=1
        if(P[0]*P[1]<M[0]*M[1]):
            ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
        else:
            ans2 = ans2*(heapq.heappop(P)*heapq.heappop(P))%mod
    elif len(P)==0:
        if len(M)>=2:
            ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            i += 1
        else:
            ans2 = ans2*heapq.heappop(M)%mod
    elif len(M)==0:
        ans2 = -ans2*heapq.heappop(P)%mod
    elif len(M)==1 and len(P)==1:
        ans2 = -ans2*heapq.heappop(P)%mod
    elif len(P)==1:
        if(P[0]<M[0]*M[1]):
            ans2 = ans2*(heapq.heappop(M)*heapq.heappop(M))%mod
            i +=1
        else:
            ans2 = -ans2*heapq.heappop(P)%mod
    elif len(M)==1:
        ans2 = -ans2*heapq.heappop(P)%mod
if i < K:
    if len(P)==1:
        ans2 = -ans2*heapq.heappop(P)%mod
    else:
        ans2 = ans2*heapq.heappop(M)%mod


print(ans2)

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]*b>Ap[-1]*a:
                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:
from sys import stdin
input = stdin.readline

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

ans = 1
mod = 10 ** 9 + 7

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

if K == 1:
    print(max(A))
elif K == N:
    for a in A:
        ans *= abs(a)
        ans %= mod
    if minus_cnt % 2 == 1:
        ans *= (-1)
    print(ans % mod)
else:
    minus_cnt = 0
    new_A = []
    select_ls = []

    for a in A:
        new_A.append([abs(a), 0 if a >= 0 else -1])
    new_A.sort(reverse=True)

    for i in range(K):
        select_ls.append(new_A[i])
        minus_cnt += new_A[i][1]

    if minus_cnt % 2 == 0:
        for s in select_ls:
            ans *= s[0]
            ans %= mod
        print(ans)
    else:
        ok = False
        for i in range(K, N):
            if new_A[i][1] == 0:
                exit(1)
                ok = True
                ans *= new_A[i][0]
                select_ls.sort()
                skip = False
                for j in range(len(select_ls)):
                    if select_ls[j][1] == -1:
                        if skip:
                            ans *= select_ls[j][0]
                        else:
                            skip = True
                            continue
                    else:
                        ans *= select_ls[j][0]
                    ans %= mod
            break
        if not ok:
            if 0 in A:
                print(0)
                exit()
            new_A.sort()
            for i in range(K):
                ans *= new_A[i][0]
                ans %= mod
            ans *= (-1)
        print(ans % mod)

Submission status: Runtime Error

Solution code:
n,k = map(int, raw_input().split(' '))
ais = map(int , raw_input().split(' '))

pos = [ai for ai in ais if ai > 0]
pos.sort(key = lambda x:-x)
neg = [-ai for ai in ais if ai < 0]
neg.sort(key = lambda x:-x)

def g(neg, k):
	i = len(neg) -1
	r = 1
	while(k):
		r *= -neg[i]
		i -=1
		k -=1
		r %= (10 ** 9) + 7
	return r
def gg(pos, k):
	r =  1
	for i in range(k):
		r *= pos[i]
		r %= (10 **9) + 7
	return r
def f(pos,neg, k):

	if len(pos) == 0: return g(neg, k)
	if len(neg) <= 1: return gg(pos, k)

	i,j = 0,0
	p = 1
	mod = (10 ** 9) + 7
	while(k >= 2 and i < len(pos) and j+1 < len(neg) and (len(pos) - i) >= k):
		if j + 1 < len(neg):
			if neg[j] * neg[j+1] > pos[i] * (pos[i+1] if i+1 < len(pos) else 1):
				p *= neg[j] * neg[j+1]
				p %= mod
				j += 2
				k -= 2
			else:
				p *= pos[i]
				i +=1
				p %= mod
				k -=1
	while(k and i < len(pos)):
		p *= pos[i]
		p %+ mod
		k-=1
		i+=1
	return p
print f(pos,neg, k) if k > 1 else max(ais)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
P = []
M = []
zero = []
for a in A:
    if a>0:
        P.append(a)
    elif a<0:
        M.append(a)
    else:
        zero.append(a)
if N==K and zero: print(0);exit()
if len(P)==0:
    if K%2==0:
        ans = 1
        if len(M)>=K:
            M.sort(reverse=True)
            for i in range(K):
                ans *=M[i]
                ans %=mod
            print(ans);exit()
        else: print(0);exit()
    else:
        ans = 1
        if len(M)>=K:
            M.sort()
            for i in range(K):
                ans *=M[i]
                ans %=mod
            print(ans);exit()
        else: print(0);exit()
P.sort(reverse=True)
M.sort(reverse=True)
if K==1:
    A.sort()
    print(A[-1]);exit()
if len(P)>=K:
    ans = 1
    P = P[:K]
    for i in range(K):
        ans *=P[i]
        ans %=mod
    while P:
        while len(M)>=2:
            a1 = M.pop()
            a2 = M.pop()
            b1 = P.pop()
            b2 = P.pop()
            if a1*a2 > b1*b2:
                ans = ans/b1
                ans = ans/b2
                ans *=a1*a2
                ans %=mod
            else:
                break
        break
else:
    ans = 1
    
    K -=len(P)
    if K>len(M):print(0);exit()
    else:
        if K%2!=0:
            if zero:print(0);exit()
            else:
                for i in range(len(P)-1):
                    ans *=P[i]
                    ans %=mod
                if K+1<=len(M):
                    while P:
                        while len(M)>=2:
                            a1 = M.pop()
                            a2 = M.pop()
                            b1 = P.pop()
                            b2 = P.pop()
                            if a1*a2 > b1*b2:
                                ans = ans/b1
                                ans = ans/b2
                                ans *=a1*a2
                                ans %=mod
                            else:
                                break
                        break
                else:
                    print(0);exit()
        else:
            for i in range(len(P)):
                ans *=P[i]
                ans %=mod
            if K<=len(M):
                while P:
                    while len(M)>=2:
                        a1 = M.pop()
                        a2 = M.pop()
                        b1 = P.pop()
                        b2 = P.pop()
                        if a1*a2 > b1*b2:
                            ans = ans/b1
                            ans = ans/b2
                            ans *=a1*a2
                            ans %=mod
                        else:
                            break
                    break
            else:
                print(0);exit()
print(int(ans%mod))

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop, heapify, heappush
mod = 10**9 + 7
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
plus = []
minus = []
zero = []
ans = []
for a in A:
    if a > 0:
        plus.append(-a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(a)
heapify(plus)
heapify(minus)
cnt = 0
last_minus = 0
last_plus = 0
if len(plus) + len(minus) > K:
    print(0)
    sys.exit()

if len(plus) == 0:
    num = 1
    minus.sort(reverse=True)
    for x in minus[:K]:
        num *= x
        num %= mod
    print(num%mod)
    sys.exit()

if len(minus) == 0:
    num = 1
    plus.sort(reverse=True)
    for x in plus[:K]:
        if x < 0:
            x = -x
        num *= x
        num %= mod
    print(num%mod)
    sys.exit()

flag = 0

for i in range(K):
    if len(plus) > 0 and len(minus) > 0:
        a = heappop(plus)
        b = heappop(minus)
    elif len(plus) == 0:
        flag = 1
        break
    else:
        flag = 2
        break
    if a >= b:
        ans.append(b)
        if a == 0:
            continue
        heappush(plus, a)
        cnt += 1
        last_minus = b
    else:
        ans.append(a)
        if b == 0:
            continue
        heappush(minus, b)
        last_plus = a

if flag == 2:
    for i in range(K - len(ans)):
        a = heappop(plus)
        last_plus = a
        ans.append(a)

if flag == 1:
    for i in range(K - len(ans)):
        a = heappop(minus)
        last_minus = a
        cnt += 1
        ans.append(a)

if cnt%2 == 0:
    num = 1
    for a in ans:
        if a < 0:
            a = -a
        num = (num * a%mod)%mod
    print(num%mod)
    sys.exit()
else:
    num = 1
    for a in ans:
        num = (num * a%mod)%mod
    if len(plus) == 0:
        a = heappop(minus)
        num = (num * a //last_plus)%mod
        print(num%mod)
    elif len(minus) == 0:
        a = heappop(plus)
        num = (num * a //last_minus)%mod
        print(num%mod)
    else:
        a = heappop(plus)
        b = heappop(minus)
        if a / (-last_minus) >= -b / last_plus:
            num = (num * a //last_minus)%mod
            print(num%mod)
        else:
            num = (num * b //last_plus)%mod
            print(num%mod)

Submission status: Runtime Error

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()))
    pos = []
    neg = []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a > 0:
            pos.append(a)
    numzero = N - len(neg) - len(pos)
    if len(pos) + len(neg) < K:
        print(0)
        return
    if K % 2 == 1 and len(neg) == N:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD
        print(ans)
        return
    elif K % 2 == 1 and len(pos) == 0:
        print(0)
        return
    q = []
    for i in range(len(pos)):
        heappush(q, [-pos[i], "p"])
    for i in range(len(neg)):
        heappush(q, [neg[i], "n"])
    ans = 1
    is_positive = True
    prevneg = 0
    prevpos = 0
    poshistory = []
    neghistory = []
    while K and len(q):
        num, posneg = heappop(q)
        if K == 1:
            if not is_positive:
                if posneg == "p" and len(poshistory) < 2:
                    poshistory.append(-num)
                elif posneg == "n":
                    if len(poshistory) == 2 and prevneg * -num < poshistory[0] * poshistory[1]:
                        ans = div(ans * poshistory[0] * poshistory[1], prevneg)
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
            if is_positive:
                if posneg == "n" and len(neghistory) < 2:
                    neghistory.append(-num)
                elif posneg == "p":
                    if len(neghistory) == 2 and prevpos * -num < neghistory[0] * neghistory[1]:
                        ans = div(ans * neghistory[0] * neghistory[1], prevpos)
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
            continue
        ans = (ans * -num) % MOD
        K -= 1
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = pos
    if K != 0:
        if is_positive:
            ans = (ans * neghistory[0] * neghistory[1]) % MOD
        else:
            ans = (ans * poshistory[0] * poshistory[1]) % MOD
    print(ans)


if __name__ == "__main__":
    main()