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:
#!/usr/bin/env python3
import sys
from collections import deque
MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    mp = sum([int(a<=0) for a in A])
    pl = True
    if (N == K):
        if mp%2 == 0:     pl = True
        else:     pl = False
    if (mp == N):
        if K%2 == 0: pl = True
        else: pl = False

    absA = sorted(A, key=abs)
    sA = deque(absA)
    ans = 1
    k = 1
    if pl:
        for i in range(K):
            t = sA.pop()
            ans*= t
            k *= int(t>0)*2-1
            ans%= MOD

        if k<0:
            pre=absA[i]
            prei = i
            while((i!=N) and ((absA[i] * pre)>0) ): i+=1
            if i==N:
                pre = avsA[prei+1]
                i = prei
                while((absA[i]*pre)>0 ): i-=1
            
            ans//= absA[i]
            ans*= pre

        print(ans%MOD)

    else:
        for i in range(K):
            ans*= sA.popleft()
            ans%= MOD
        print(ans%MOD)


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    def solve():
        ret = 1
        for i in range(n):
            if L[i][2]:
                ret *= L[i][0]
                ret %= MOD
        return ret % MOD

    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    INF = float('inf')
    L = []
    p, m = 0, 0
    for a in A:
        if a < 0:
            m += 1
            L.append([abs(a), -1, False])
        else:
            L.append([a, 1, False])
    L = sorted(L, key= lambda x: x[0], reverse=True)
    pm = 1
    lp, lm = None, None
    for i in range(k):
        L[i][2] = True
        pm *= L[i][1]
        if L[i][1] >= 0:
            lp = i
        else:
            lm = i
    if pm >= 0:
        ans = solve()
    else:
        ans1, ans2 = -INF, -INF
        if lp:
            j = k
            while j < n:
                if L[j][1] < 0:
                    ans1 = L[j][0] / L[lp][0]
                    break
                j += 1
        if lm:
            l = k
            while j < n:
                if L[l][1] >= 0:
                    ans2 = L[l][0] / L[lm][0]
                    break
                j += 1
        if ans1 >= ans2:
            L[lp][2] = False
            L[j][2] = True
        else:
            L[lp][2] = False
            L[l][2] = True
        ans = solve()
        if ans1 == ans2 == -INF:
            L = sorted(L, key=lambda x: x[0])
            ans = 1
            for i in range(k):
                ans *= L[i][0]
                ans %= MOD
            ans = -1 * ans
    print(ans % MOD)
main()

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush

MOD = int(1e9+7)


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 = (ans * poshistory[0] * poshistory[1]) % MOD
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
                continue
            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 = (ans * neghistory[0] * neghistory[1]) % MOD
                    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()

Submission status: Runtime Error

Solution code:
def mergesort(l):
    n = len(l)
    if(n == 0):
        return 0
    elif(n == 1):
        return l
    elif(n <= 2):
        if(l[0] > l[1]):
            return [l[1],l[0]]
        else:
            return l
    else:
        tmp1 = mergesort(l[:n//2])
        tmp2 = mergesort(l[n//2:])
        x = n//2
        y = n-x
        l = []
        for i in range(n):
            if(tmp1[-x] < tmp2[-y]):
                l.append(tmp1[-x])
                x -= 1
            else:
                l.append(tmp2[-y])
                y -= 1
            if(x*y == 0):
                if(x == 0):
                    l += tmp2[-y:]
                else:
                    l += tmp1[-x:]
                break
        return l
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = []
c = []
s,t,u = 0,0,0
for i in range(n):
    if(a[i] < 0):
        t += 1
        c.append(a[i])
    else:
        s += 1
        b.append(a[i])
b = mergesort(b)
c = mergesort(c)
p = 1
if(s == 0 and k%2 == 1):
    for i in range(1,k+1):
        p *= c[-i]
        p %= 1000000007
else:
    if(k%2 == 1):
        s-=1
        p = b[s]
        k -= 1
    while(k>0):
        if(s >= 2 and t >= u+2):
            if(b[s-1]*b[s-2] > c[u]*c[u+1]):
                p *= b[s-1]*b[s-2]
                p %= 1000000007
                s -= 2
            else:
                p *= c[u]*c[u+1]
                p %= 1000000007
                u += 2
        elif(s <= 1):
            p *= c[u]*c[u+1]
            p %= 1000000007
            u += 2
        else:
            p *= b[s-1]*b[s-2]
            p %= 1000000007
            s -= 2
        k -= 2
print(p)

Submission status: Runtime Error

Solution code:

# Author : raj1307 - Raj Singh
# Date   : 05.07.2020

from __future__ import division, print_function

import os,sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def msi(): return map(str,input().strip().split(" "))
def li():  return list(mi())

def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import log,sqrt,factorial,cos,tan,sin,radians
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *
#import threading
#from itertools import permutations
#Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[1] 
def sort2(l):return sorted(l, key=getKey,reverse=True)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))

def ceil(x,y):
    if x%y==0:
        return x//y
    else:
        return x//y+1

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



def read():
    sys.stdin  = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 




def main():
    


    #for _ in range(ii()):


    n,k=mi()
    a=li()
    if n==k:
        ans=1
        for i in range(n):

            x=(a[i]%mod+mod)%mod;
            ans=(ans*x)%mod
        print(ans)
        return


    x=[]
    y=[]

    for i in range(n):
        if a[i]<0:
            y.append(a[i])
        else:
            x.append([a[i],1])

    neg=[]


    y.sort()
    ex=-1

    for i in range(0,len(y),2):
        if i==len(y)-1:
            ex=y[i]
            continue

        x.append([y[i]*y[i+1],2])



    x.sort(reverse=True)
   


    ans=1
    cnt=0


    p=[]
    q=[]

    ext=-1


    for i in range(len(x)):
        #print(cnt,x[i][1],cnt)


        if cnt+x[i][1]<=k:

            if x[i][1]==1:
                p.append(x[i][0])
            else:
                q.append(x[i][0])

            ans=(ans*x[i][0])%mod
            cnt+=x[i][1]

        elif cnt!=k:

            ext=max(ext,x[i][0])



    if cnt==k:
        print(ans)
        return



    if len(p)!=0:

        ans=1

        for i in range(len(p)-1):
            ans=(ans*p[i])%mod
        for j in range(len(q)):
            ans=(ans*q[j])%mod
        ans=ans*ext
        ans%=mod
        print(ans)
        return


    mm=[]
    y=[::-1]
    for i in range(0,len(y)),2:
        if i==len(y)-1:
            break

        mm.append([y[i]*y[i+1],2])

    for i in range(n):
        if a[i]>=0:
            mm.append([a[i],1])

    cnt=0
    mm.sort()

    ans=1
    for i in range(len(mm)):


         if cnt+mm[i][1]<=k:


            ans=(ans*mm[i][0])%mod
            cnt+=mm[i][1]

    


    if cnt==k:
        print(ans)
        return












    ans=1
    cnt=0
    for i in range(len(y)-1,-1,-1):
        if cnt==k:
            break

        x=(mod+y[i]%mod)%mod
        ans*=x
        ans%=mod
        cnt+=1

    print(ans)












    









    








# region fastio
# template taken from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
    #read()
    main()
    #dmain()

# Comment Read()

Submission status: Runtime Error

Solution code:
#create date: 2020-07-05 21:39

import sys
stdin = sys.stdin
mod = 10**9 + 7

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def calc(pos, neg):
    res = 1
    if pos:
        for p in pos:
            res *= p
            res %= mod
    if neg:
        for n in neg:
            res *= (-n)
            res %= mod
    return res

def main():
    n, k = na()
    a = na()
    po = list(); ne = list()
    for ai in a:
        if ai > 0:
            po.append(ai)
        if ai < 0:
            ne.append(ai)
    po.sort(reverse=True)
    ne.sort()
    if len(po) + len(ne) < k:
        print(0)
        quit()
    if len(po) == 0 and k % 2 == 1:
        if 0 in a:
            print(0)
            quit()
        else:
            ans = -calc(None, ne[(n-k):]) % mod
            print(ans)
            quit()
    if len(ne) == 0:
        ans = calc(po[:k], None)
        print(ans)
        quit()
    else:
        poi = len(po)
        nei = k - poi
        if nei % 2 == 1:
            poi -= 1
            nei += 1
        poi_pre = poi; nei_pre = nei
        while poi >= 0:
            poi -= 2
            nei += 2
            if poi < 0 or nei > len(ne):
                break
            positive = po[poi] * po[poi+1]
            negative = ne[nei-2] * ne[nei-1]
            if positive < negative:
                poi_pre = poi; nei_pre = nei
            else:
                ans = calc(po[:poi_pre], ne[(n-nei_pre):])
                print(ans)
                quit()
        ans = calc(po[:poi], ne[(n-nei):])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
mod = 10**9+7

import sys
input = sys.stdin.buffer.readline

def main():

    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    P = []
    N = []

    for a in A:
        if a >= 0:
            P.append(a)
        else:
            N.append(a)
    P.sort(reverse=True)
    N.sort()
    #print(P)
    #print(N)

    if len(P) == 0:
        if k%2 == 0:
            N.sort()
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
        else:
            N.sort(reverse=True)
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
        print(ans)
        exit()

    if len(P) == 1:
        if k%2 == 0:
            N.sort()
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
        else:
            ans = P[0]
            N.sort(reverse=True)
            for i in range(k-1):
                ans *= N[i]
                ans %= mod
        print(ans)
        exit()


    if len(N) == 0:
        ans = 1
        for i in range(k):
            ans *= P[i]
            ans %= mod
        print(ans)
        exit()

    if len(N) == 1:
        if len(P) >= k:
            ans = 1
            for i in range(k):
                ans *= P[i]
                ans %= mod
            print(ans)
            exit()
        else:
            print(N[0])
            exit()

    import heapq
    if k%2 == 0:
        P_ = []
        N_ = []
        if len(P) != 1:
            for i in range(len(P)):
                if i%2 == 1:
                    continue
                if i+1 <= len(P)-1:
                    P_.append(-P[i]*P[i+1])
            for i in range(len(N)):
                if i%2 == 1:
                    continue
                if i+1 <= len(N)-1:
                    N_.append(-N[i]*N[i+1])
            heapq.heapify(P_)
            heapq.heapify(N_)
            q = k//2
            ans = 1
            for i in range(q):
                if P_:
                    x = heapq.heappop(P_)*(-1)
                else:
                    x = -1
                if N_:
                    y = heapq.heappop(N_)*(-1)
                else:
                    y = -1
                if x >= y:
                    ans *= x
                    ans %= mod
                    if y >= 0:
                        heapq.heappush(N_, y*(-1))
                else:
                    ans *= y
                    ans %= mod
                    if x >= 0:
                        heapq.heappush(P_, x*(-1))
        else:
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
    else:
        p = P[0]
        P = P[1:]
        P_ = []
        N_ = []
        if len(P) != 1:
            for i in range(len(P)):
                if i%2 == 1:
                    continue
                if i+1 <= len(P)-1:
                    P_.append(-P[i]*P[i+1])
            for i in range(len(N)):
                if i%2 == 1:
                    continue
                if i+1 <= len(N)-1:
                    N_.append(-N[i]*N[i+1])
            heapq.heapify(P_)
            heapq.heapify(N_)
            q = k//2
            ans = p
            for i in range(q):
                if P_:
                    x = heapq.heappop(P_)*(-1)
                else:
                    x = -1
                if N_:
                    y = heapq.heappop(N_)*(-1)
                else:
                    y = -1
                if x >= y:
                    ans *= x
                    ans %= mod
                    if y >= 0:
                        heapq.heappush(N_, y*(-1))
                else:
                    ans *= y
                    ans %= mod
                    if x >= 0:
                        heapq.heappush(P_, x*(-1))
        else:
            ans = p
            for i in range(k):
                ans *= N[i]
                ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

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()

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, key=lambda x:abs(x))
cnt = 0
im = 0
ip = 0
cp = 0
mod = 10 ** 9 + 7

for i, ai in enumerate(a):
    if i < k:
        if ai < 0:
            im = i
            cnt += 1
        if ai > 0:
            ip = i
    if ai > 0:
        cp += 1

ans = 1
f = 0

# print(a)
if cnt % 2:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans)
    else:
        ans = 1
        cnt = 0
        f = 0
        for i, ai in enumerate(a):
            if cnt == k:
                f = 2
                break
            if i == im:
                f = 1
                continue
            if f == 1 and ai <= 0:
                continue
            ans *= abs(ai)
            ans %= mod
            # print(i, ai)
            cnt += 1
        if f == 2:
            print(ans)
        else:
            ans = 1
            cnt = 0
            f = 0
            for i, ai in enumerate(a):
                if cnt == k:
                    f = 2
                    break
                if i == ip:
                    f = 1
                    continue
                if f == 1 and ai >= 0:
                    continue
                ans *= abs(ai)
                ans %= mod
                # print(i, ai)
                cnt += 1
            if f == 2:
                print(ans)
            else:
                ans = 1
                a.sort(reverse=True)
                for i, ai in enumerate(a):
                    if i == k:
                        break
                    ans *= ai
                    ans %= mod
                print(ans)

else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= abs(ai)
        ans %= mod
    print(1/0)
    print(ans)

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:
        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:
        a = heappop(plus)
    else:
        flag = 1
        break
    if len(minus) > 0:
        b = heappop(minus)
    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)
        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
    print(num%mod)
    sys.exit()
else:
    num = 1
    for a in ans:
        num = (num * a)%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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
cnt = 1

def powmod(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x
            ans %= mod
        x = x*x
        n = n >> 1
    return ans % mod

def gyaku(n):
    return powmod(n, mod - 2)

def smp_solve(arr, n):
    ans = 1
    for i in range(n):
        ans *= arr[i]
        ans %= mod
    return ans

def compare_two_give_max(pos, neg, pos_pair, neg_pair, K):
    i = 0
    j = 0
    ans = 1
    neg_last = True
    while i < len(pos_pair) and j < len(neg_pair) and K > 0:
        if pos_pair[i] > neg_pair[j]:
            ans *= pos_pair[i]
            i += 1
            neg_last = False
        else:
            ans *= neg_pair[j]
            j += 1
            neg_last = True
        K -= 2
        ans %= mod

    while K > 0 and i == len(pos_pair) and j < len(neg_pair):
        # negがなくなるまでタス
        ans *= neg_pair[j]
        j += 1
        K -= 2
        ans %= mod
        neg_last = True

    while K > 0 and i < len(pos_pair) and j == len(neg_pair):
        # posがなくなるまでタス
        ans *= pos_pair[i]
        i += 1
        K -= 2
        ans %= mod
        neg_last = False

    if K == -1:
        if neg_last:
            # 足しすぎた分をわる
            ans *= gyaku(neg_pair[j-1])
            ans *= pos[2*i]
            # TODO: iがoutOfArray
            ans %= mod
        else:
            ans *= gyaku(pos_pair[2*i-1])
            ans %= mod
    return ans, K

def main():
    global cnt
    N, K = LI()
    A = LI()
    if N == K:
        ans = smp_solve(A, N)
        print(ans)
        return

    neg = []
    pos = []
    zero_exist = False
    for a in A:
        if a < 0:
            neg.append(a)
        elif a > 0:
            pos.append(a)
        else:
            zero_exist = True
    neg = sorted(neg) # -12, -3
    pos = sorted(pos)[::-1] # 4, 3, 2, 1
    if len(pos) == 0:
        ans = 1
        neg = neg[::-1] # -3, -12
        for n in neg[:K]:
            ans *= n
            ans %= mod
        if zero_exist:
            ans *= 0
        print(ans % mod)
        return

    if len(neg) == 0:
        ans = 1
        for p in pos[:K]:
            ans *= p
            ans %= mod
        print(ans % mod)
        return


    neg_paired = []
    pos_paired = []

    i = 0
    neg_amari = -inf
    while i+1 < len(neg):
        neg_paired.append(neg[i] * neg[i+1])
        i += 2
    if len(neg) % 2 == 1:
        neg_amari = neg[-1]

    i = 0
    pos_amari = -inf
    while i+1 < len(pos):
        pos_paired.append(pos[i] * pos[i+1])
        i += 2
    if len(pos) % 2 == 1:
        pos_amari = pos[-1]

    # print('pos: ', pos)
    # print('neg: ', neg)
    # print('pos_pair: ', pos_paired)
    # print('neg_pair: ', neg_paired)
    if len(pos_paired) == 0 and len(neg_paired) == 0:
        if K == 1:
            cnt *= pos_amari
        elif K == 2:
            if zero_exist:
                cnt = 0
            else:
                cnt = pos_amari * neg_amari


    else:
        res, k = compare_two_give_max(pos, neg, pos_paired, neg_paired, K)
        # print('res: ', res)
        # print('k: ', k)
        cnt *= res
        if k > 1:
            if pos_amari != -inf:
                cnt *= pos_amari
            elif neg_amari != -inf:
                if zero_exist:
                    cnt *= 0
                else:
                    cnt *= neg_amari
    print(cnt % mod)
    return

main()

Submission status: Runtime Error

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

is_all_neg = 1
for i in range(N):
    if A[i] > 0:
        is_all_neg = 0
        
if is_all_neg:
    if K%2 == 1:
        A_1 = sorted(A, reverse=True)
        for i in range(K):
            ans *= A_1[i]
        print(ans % p)
    else:
        A_1 = sorted(A)
        for i in range(K):
            ans *= A_1[i]
        print(ans % p)
else:
    A_1 = sorted(A, key=lambda x: abs(x), reverse=True)
    is_pos = 1
    ans = 1
    minus = []
    for i in range(K):
        ans *= A_1[i]
        if A_1[i] < 0:
            minus.append(i)
        if ans > 0:
            is_pos = 1
        else:
            is_pos = 0
        if i == K-1:
            if is_pos:
                
                break
            else:
                
                idx = minus.pop()
                ans /= A_1[idx]
                for j in range(K-1, N):
                    if A_1[j] > 0:
                        ans *= A_1[j]
                        break
    print(int(ans)%p)