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:

# 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:
N, K = map(int, input().split())
mod = 10 ** 9 + 7
m = []
p = []
z = []
for a in [int(i) for i in input().split()]:
    if a > 0:
        p.append(a)
    elif a < 0:
        m.append(a)
    else:
        z.append(a)
p.sort()
m.sort(reverse=True)
#プラスが０
if len(p) == 0:
    if len(m) < K:
        print(0)
        exit()
    # Kが奇数
    if K & 1:
        if z:
            print(0)
            exit()
        ans = 1
        for i in range(K):
            ans *= m[i]
            ans %= mod
        print(ans)
    else:
        ans = 1
        for i in range(1, K + 1):
            ans *= m[-i]
            ans %= mod
        print(ans)
    exit()

else:
    if len(p) + len(m) < K:
        print(0)
        exit()
    elif len(p) + len(m) == K:
        if len(m) ^ 1:
            if z:
                print(0)
                exit()
        ans = 1
        for n in p:
            ans *= n
            ans %= mod
        for n in m:
            ans *= n
            ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        m.sort()
        p.sort(reverse=True)
        pi = 0
        mi = 0
        t = 0
        if K & 1:
            ans *= p[0]
            ans %= mod
            pi += 1
            t += 1
        while t < K:
            tmp = 0
            if pi >= len(p) - 1:
                for _ in range(t, K):
                    ans *= m[mi]
                    ans %= mod
                    mi += 1
                break
            elif mi >= len(m) - 1:
                for _ in range(t, K):
                    ans *= p[pi]
                    ans %= mod
                    pi += 1
            a = p[pi] * p[pi+1]
            b = m[mi] * m[mi + 1]
            if a > b:
                ans *= a
                pi += 2
                t+=2
            elif b > a:
                ans *= b
                mi += 2
                t += 2
            else:
                if K - t >= 4:
                    ans *= a
                    ans %= mod
                    ans *= b
                    pi += 2
                    mi += 2
                    t+=4
                else:
                    if K - t == 3:
                        ans *= b
                        ans %= mod
                        ans *= p[pi]
                        ans %= mod
                    else:
                        for _ in range(t, K):
                            ans *= p[pi]
                            ans %= mod
                            p += 1
                    break
            ans %= mod
        print(ans)
        exit()

Submission status: Runtime Error

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7

    plus = []
    minus = []
    for a in A:
        if a >= 0:
            heapq.heappush(plus, -a)
        else:
            heapq.heappush(minus, a)

    ans = 1

    # 絶対マイナスになる場合
    if len(plus) < K - min((K - K % 2), (len(minus) - len(minus) % 2)):
        plus = []
        minus = []
        for a in A:
            if a >= 0:
                heapq.heappush(plus, a)
            else:
                heapq.heappush(minus, -a)

        while K > 0:
            if plus:
                x = plus[0]
            else:
                x = float("inf")

            if minus:
                y = -minus[0]
            else:
                y = float("inf")

            if abs(x) <= abs(y):
                ans *= x
                if plus:
                    heapq.heappop(plus)
            else:
                ans *= y
                if minus:
                    heapq.heappop(minus)

            ans %= MOD
            K -= 1

        print(ans)

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

        plusruiseki = [0]
        minusruiseki = [0]
        for i, v in enumerate(plus):
            if i == 0:
                plusruiseki.append(v)
            else:
                plusruiseki.append((plusruiseki[-1] * v))

        for i, v in enumerate(minus):
            if i == 0:
                minusruiseki.append(v)
            else:
                minusruiseki.append((minusruiseki[-1] * v))

        ans = 0
        for i in range(0, len(minus) + 1, 2):
            if i == 0:
                if K <= len(plusruiseki) - 1:
                    ans = max(ans, plusruiseki[K])
            else:
                if i > len(minusruiseki):
                    break

                if K - i > len(plusruiseki):
                    continue

                if K - i == 0:
                    ans = max(ans, minusruiseki[i])
                else:
                    ans = max(ans, minusruiseki[i] * plusruiseki[K - i])

        print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
import fractions
import collections
import itertools
import pprint
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]
    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]
    print(ans%p)
else:
    ans=1
    plist.sort(reverse=True)
    mlist.sort()
    pmap=[]
    mmap=[]
    if K%2==1:
        ans=plist[0]
        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):
            if pmap[0]>mmap[0]:
                ans=(ans*pmap[0])%p
                pmap.pop(0)
            else:
                ans=(ans*mmap[0])%p
                mmap.pop(0)
        elif len(pmap)==0:
            ans = (ans * mmap[0]) % p
            mmap.pop(0)
        else:
            ans = (ans * pmap[0]) % p
            pmap.pop(0)
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n, k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7

p = []
m = []
for i in a:
    if i > 0:p.append(i)
    elif i < 0:p.append(i)

flag = 0
if (k - len(p))%2 == 1:
    flag = 1
    p, m = m, p

p.sort(reverse=True)
m.sort()
double = []
    
for i in range(len(p) - 1):
    if i % 2 == 0:
        temp = p[i] * p[i + 1]
        double.append([temp, 1])
for i in range(len(m) - 1):
    if i % 2 == 0:
        temp = m[i] * m[i + 1]
        double.append([temp, 2])

if p[0] < 0:
    double.sort()
else:
    double.sort(reverse=True)

res = 1
p = deque(p)
m = deque(m)
double = deque(double)
while k:
    if double and k - 2 >= 0:
        temp, ind = double.popleft()
        if ind == 1:
            p.popleft()
            p.popleft()
        else:
            m.popleft()
            m.popleft()
        res = (res * temp) 
        k -= 2
    else:
        if not flag:
            if p:
                res = (res * p.popleft()) 
            else:
                res = (res * m.pop()) 
        else:
            if not m:
                res = (res * p.popleft())
            else:
                temp1 = m.popleft()
                temp2 = p.popleft()
                if temp1 <= -temp2:
                    res = (res * temp1)
                    p.appendleft(temp2)
                else:
                    res = (res * temp2)
                    m.appendleft(temp1)
        k -= 1
        
print(res%mod)

Submission status: Runtime Error

Solution code:
class modNumber:
    prime = 10**9 + 7
    def __init__(self, num):
        self.num = num % modNumber.prime

    def __add__(self, other):
        return modNumber(self.num + other.num)

    def __sub__(self, other):
        return modNumber(self.num - other.num)

    def __mul__(self, other):
        return modNumber(self.num*other.num)

    def __truediv__(self, other):
        return modNumber(self.num*other.reciprocal())

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

    def reciprocal(self):
        ans = modNumber(1)
        buffer = modNumber(self.num)
        exp = modNumber.prime - 2
        while exp:
            if exp & 1:
                ans = ans * buffer
            buffer = buffer * buffer
            exp = exp >> 1
        return ans.num

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

A_p = [a for a in A if a > 0]
A_p.sort(reverse=True)
A_m = [a for a in A if a < 0]
if len(A_m) == 1:
    A_m = []
else:
    if len(A_m)%2:
        A_m = A_m[:-1]
    A_m.sort()
    A_m = [a1*a2 for a1, a2 in zip(A_m[::2], A_m[1::2])]


result = modNumber(1)

if len(A_p) + len(A_m)*2 >= K or (len(A_p) == 0 and K%2 == 1):
    # answer is positive
    i = 0
    j = 0
    A_p.append(-float("inf"))
    A_m.append(-float("inf"))
    while K > 1:
        if A_p[i] + A_p[j] > A_m[j]:
            result = result * modNumber(A_p[i])
            i += 1
            K -= 1
        else:
            result = result * modNumber(A_m[j])
            j += 1
            K -= 2
    if K == 1:
        if i == len(A_p) - 1:
            result = result * modNumber(A_m[j])
            result = result / modNumber(A_p[-2])
        else:
            result = result * modNumber(A_p[i])
else:
    # answer is negative
    result = modNumber(-1)
    A = list(map(abs, A))
    A.sort()
    for a in A[:K]:
        result = result * modNumber(a)

# ZERO


print(result)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7
sei = []
hu = []
zero = []
for i in range(N):
    a = A[i]
    if a > 0:
        sei.append(a)
    elif a < 0:
        hu.append(a)
    else:
        zero.append(0)
sei.sort(reverse = True)
if len(zero) > N - K:
    print(0)
else:
    ans = 1
    p = len(sei)
    q = len(hu)
    if p == 0:
        hu.sort(reverse = True)
        for i in range(K):
            ans *= hu[i]
            ans %= MOD
        if K % 2 == 1 and len(zero) != 0:
            print(0)
        else:
            print(ans)
    elif p + q == K :
        if len(q) %= 2 == 1 and len(zero) != 0:
            print(0)
        else:
            hu.sort()
            for i in range(p):
                ans *= sei[i]
                ans %= MOD
            for j in range(q):
                ans *= hu[j]
                ans %= MOD
            print(ans%MOD)
    elif q == 0:
        for i in range(K):
            ans *= sei[i]
            ans %= MOD
        print(ans)
    else:
        hu.sort()
        flag = 0
        pin = 0
        qin = 0
        r = K
        while r > 0:
            if pin == -1 and qin == -1:
                break
            elif pin == -1:
                qin += 1
                if qin == q:
                    qin = -1
                if flag == 1:
                    flag = 0
                else:
                    flag = 1
            elif qin == -1:
                pin += 1
                if pin == p:
                    pin = -1
            else:
                if abs(sei[pin])>abs(hu[qin]):
                    pin += 1
                    if pin == p:
                        pin = -1
                else:
                    qin += 1
                    if qin == q:
                        qin = -1
                    if flag == 0:
                        flag = 1
                    else:
                        flag = 0
            r -= 1
        if pin == -1:
            pin = p
        if qin == -1:
            qin = q
        if p+q == K:
            for i in range(p):
                ans *= sei[i]
                ans %= MOD
            for j in range(q):
                ans *= hu[j]
                ans %= MOD
            print(ans%MOD)
        else:
            if flag == 0:
                for i in range(pin):
                    ans *= sei[i]
                    ans %= MOD
                for j in range(qin):
                    ans *= hu[j]
                    ans %= MOD
                print(ans%MOD)
            else:
                if pin == p:
                    for i in range(pin-1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin+1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)
                else:
                    for i in range(pin+1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin-1):
                        ans *= hu[j]
                        ans %= MOD
                    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):
		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)

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

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:
def mult(lis):
  ret=1
  for i in lis:
    ret*=i
    ret%=1000000007
  return ret
n,k=map(int,input().split())
a=list(map(int,input().split()))
minus=[]
plus=[]
ch=[]
for i in a:
  if i<0:
    minus.append(i)
  else:
    plus.append(i)
if len(plus)==0 and k%2:
  minus.sort(reverse=True)
  ch.extend(minus[:k])
else:
  pls=True
  a.sort(key=lambda x: abs(x), reverse=True)
  print(a)
  while k>0:
    inp=a.pop(0)
    if inp<0:
      if k==1 and pls:
        continue
      pls^=1
    ch.append(inp)
    k-=1
print(mult(ch))

Submission status: Runtime Error

Solution code:
PRIME = 10 ** 9 + 7

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

_a = sorted(a,key=abs,reverse=True)

ans = 1
if n == k:
  for i in range(k):
    ans = (ans * _a[i]) % PRIME
else:
  minus_n = 0
  minus_k = 0
  zero = 0
  min_minus = -1
  min_plus = -1
  max_minus = -1
  min_plus = -1
  
  for i in range(n):
    if _a[i] < 0:
      minus_n += 1
      if i < k:
        minus_k += 1
        min_minus = i
      else:
        max_minus = i
    elif _a[i] == 0:
      zero += 1
    elif i < k:
      min_plus = i
    else:
      max_plus = i
  
  if minus_n + zero == n and k % 2 == 1:
    for i in range(1, k + 1):
      ans = (ans * _a[-i]) % PRIME
  elif minus_k % 2 == 0:
    for i in range(k):
      ans = (ans * _a[i]) % PRIME
  elif max_minus < 0 or min_plus < 0 or (max_plus >= 0 and (max_minus < 0 or abs(a[max_minus] / a[min_plus]) < abs(a[max_plus] / a[min_minus]))):
    for i in range(k):
      if i != min_minus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_plus]) % PRIME
  else:
    for i in range(k):
      if i != min_plus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_minus]) % PRIME
    
print(ans)

Submission status: Runtime Error

Solution code:
import functools
import operator

prod = functools.partial(functools.reduce, operator.mul)


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

    a.sort(reverse=True)
    if a[-1] >= 0:
        print(prod(a[:k]))
        return
    if a[0] == 0:
        for i, _a in enumerate(a):
            if a[i] != 0:
                break
        else:
            print(0)
            return
        if k > len(a) - ind - 1:
            print(0)
            return
        if k % 2 == 1:
            print(0)
            return
        print(prod(a[len(a)-k:]))
        return
    
    left = 0
    right = len(a) - 1
    ret = 1
    i = 0
    while i < k:
        if i < k - 1:
            if a[left] * a[left+1] < a[right] * a[right-1]:
                ret *= a[right] * a[right-1]
                right -= 2
            else:
                ret *= a[left] * a[left+1]
                left += 2
            i += 2
        else:
            ret *= a[left]
            left += 1
            i += 1
    print(ret)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from heapq import *
from collections import deque

N,K,*A = map(int, open(0).read().split())
pos = []
zero = 0
neg = []
m = 1000000007
for x in A:
    if x > 0:
        pos.append(x)
    elif x == 0:
        zero += 1
    else:
        neg.append(x)
if K == N:
    ans = A[0] % m
    for x in A[1:]:
        ans = (ans*x) % m
    print(ans)
elif K % 2 == 1 and len(neg) == N:
    ai = [x * (-1) for x in A]
    heapify(ai)
    ans = (heappop(ai)*(-1)) % m
    for i in range(K-1):
        ans = (ans*heappop(ai)*(-1)) % m
    print(ans)
elif K > N - zero:
    print(0)
else:
    heapify(neg)
    ans = 1
    negpos = []
    for i in range(len(neg)//2):
        temp = heappop(neg)
        negpos.append(temp*heappop(neg))
    dnp = deque(negpos)
    posi = [x * (-1) for x in pos]
    heapify(posi)
    if len(posi) > 0:
        t1 = heappop(posi) * (-1)
    if len(posi) > 0:
        t2 = heappop(posi) * (-1)
    else:
        t2 = 1
    while K > 0:
        if len(dnp) > 0:
            if t1 * t2 >= dnp[0]:
                ans = (ans*t1) % m
                t1 = t2
                if len(posi) > 0:
                    t2 = heappop(posi) * (-1)
                else:
                    t2 = 1
                K -= 1
            else:
                if K > 1:
                    ans = (ans*dnp.popleft()) % m
                    K -= 2
        else:
            ans = (ans*t1) % m
            if len(posi) > 0:
                    t1 = heappop(posi) * (-1)
            K -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

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

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

M.sort()

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1
elif K % 2 == 1 and len(P) == 0:
    M.sort(reverse=True)
elif len(M) == 0:
    answer = 1
    for i in range(K):
        answer = (answer * P[i]) % 1000000007

    print(answer)
    sys.exit()

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M) and p < len(P):
        Ans.append(P[p])
        if len(Ans) == K:
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P) and m < len(M):
        Ans.append(M[m])
        if len(Ans) == K:
            break
        Ans.append(M[m + 1])
        m += 2
    elif m >= len(M):
        Ans.append(P[p])
        p += 1
    elif p >= len(P):
        Ans.append(M[m])
        m += 1
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)