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
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    # @staticmethod
    # def __test01__():
    #     xs = HeapQueue([-3, 2, 9, -4], "min")
    #     x0 = xs.pop()
    #     x1 = xs.pop()
    #     x2 = xs.pop()
    #     x3 = xs.pop()
    #     return (x0 == -4 and x1 == -3 and x2 == 2 and x3 == 9)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D
    print(r)
    exit()

if all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()

if K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()

if K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used[k] >= 0 and used_min_pos is None: used_min_pos = k
            elif used[k] <  0 and used_min_neg is None: used_min_neg = k
            if used_min_pos and used_min_neg:
                break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K, -1, -1):
            if   rest[k] >= 0 and rest_min_pos is None: rest_min_pos = k
            elif rest[k] <  0 and rest_min_neg is None: rest_min_neg = k
            if rest_min_pos and rest_min_neg:
                break

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest_min_pos
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest_min_neg
        else:
            v1 = abs(used[used_min_pos] * rest[rest_min_neg])
            v2 = abs(used[used_min_neg] * rest[rest_min_pos])
            if v1 < v2:
                used[used_min_pos] = rest_min_neg
            else:
                used[used_min_neg] = rest_min_pos

    for a in As[:K]:
        r = (r * a) % D
    print(r)
    exit()


##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
a =list(map(int, input().split()))
ans =1

if n == k:
   for i in a:
       ans *= i
       if abs(ans) >10**9+7:
           ans = ans%(10**9+7)

elif all(i <= 0 for i in a) and k%2 ==1:
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        if abs(ans) > 10 ** 9 + 7:
            ans = ans % (10 ** 9 + 7)

else:
    am =[]
    ap =[]

    a.sort(key = abs,reverse = True)
    amax = a[:k]
    amin = a[k:]
    c=1
    if 0 in amax:
        ans = 0
    else:
        for i in amax:
            if i<0:
                am.append(i)
                c *=-1
            elif i>0:
                ap.append(i)
        if c ==1:
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)
        else:

            if min(amin)/min(ap) > max(amin)/max(am):
                amax.remove(max(am))
                amax.append(max(amin))
            else:
                amax.remove(min(ap))
                amax.append(min(amin))
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

def list_safe_get(l, index, default=None):
    if 0 < index < len(l):
        return l[index]
    return default

class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def mysplit(data):
    ps = [] # include 0
    ms = []
    for d in data:
        if d < 0:
            ms.append(ModInt(d))
        else:
            ps.append(ModInt(d))
    return list(reversed(sorted(ps))), sorted(ms)

def small_abs(ms, k):
    ans = ModInt(1)
    ms = list(reversed(ms))
    for i in range(k):
        ans *= ModInt(ms[i])
    return ans

def factor_all(ps, pk, ms, mk):
    ans = ModInt(1)
    for i in range(pk):
        #print('ps[i]', ps[i]) # debug
        ans *= ps[i]
    for i in range(mk):
        #print('ms[i]', ms[i]) # debug
        ans *= ms[i]
    return ans

def adjust(ps, pk, ms, mk):
    if pk == 0:
        return pk + 1, mk - 1
    if mk == 0:
        return pk - 1, mk + 1
    if pk == len(ps):
        return pk - 1, mk + 1
    if mk == len(ms):
        return pk + 1, mk - 1
    cand_rm_p = ps[pk - 1]
    cand_add_m = ms[mk]
    cand_rm_m = ms[mk - 1]
    cand_add_p = ps[pk]
    if cand_rm_m * cand_add_m > cand_rm_p * cand_add_p:
        return pk - 1, mk + 1
    else:
        return pk + 1, mk - 1

def solve(data, k):
    if len(data) == k:
        ans = ModInt(1)
        for d in data:
            ans *= d
        return ans % ModInt.Mod
    ps, ms = mysplit(data)
    if len(ps) == 0:
        return small_abs(ms, k)
    pk = 0
    mk = 0
    while k > 0:
        if pk >= len(ps):
            mk += 1; k -= 1; continue
        if mk >= len(ms):
            pk += 1; k -= 1; continue
        if ps[pk] > -1 * ms[mk]:
            pk += 1; k -= 1; continue
        else:
            mk += 1; k -= 1; continue
    #print('pk, mk') # debug
    #print(pk, mk) # debug
    if mk % 2 != 0:
        pk, mk = adjust(ps, pk, ms, mk)
    #print('pk, mk') # debug
    #print(pk, mk) # debug
    return factor_all(ps, pk, ms, mk)


if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)



    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
a =  list(map(int,input().split()))

list.sort(a, reverse=True)
total = 1
count_a = 0
count_b = N-1


if a[0]<0 and K%2 != 0:
	for i in range(N):
		a[i] = abs(a[i])
	list.sort(a, reverse=False)
	for i in range(K):
		total *= a[i]
		total  =total%(10**9 +7)
	total *= -1
	total  =total%(10**9 +7)
else:
	while K>0:
		if K> 1:
			if a[count_a]*a[count_a+1] >a[count_b]*a[count_b-1]:
				total *= a[count_a] * a[count_a+1]
				total  =total%(10**9 +7)
				count_a += 2
			else:
				total *= a[count_b]*a[count_b-1]
				count_b += 2
				total  =total%(10**9 +7)
			K-=2
		else:
			total *= max( a[count_a], a[count_b])
			total  =total%(10**9 +7)
		K -= 1
print(total)

Submission status: Runtime Error

Solution code:
from math import *
ln,k=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort(reverse=True,key = lambda s: abs(s))

lul = 10**9 + 7

temp = []
for i in range(ln):
	if l[i]<0:
		temp.append(-1*l[i])
ct = 0
p = -1; n = -1
ans = []
temp = temp[::-1]
for i in range(k):
	ans.append(i)
	if l[i]<0:
		ct+=1
		n = max(n,i)
	else:
		p = max(p,i)
# print(ct)
if ct%2!=0:
	for i in range(k,ln):
		if l[i]<0 and p!=-1:
			ans.remove(p)
			ans.append(i)
			ct+=1
			break
		elif l[i]>=0:
			ans.remove(n)
			ans.append(i)
			ct-=1
			break
# print(ct)
if ct%2!=0:
	v = 1
	for i in range(k):
		v = (v*temp[i])%lul
	v = ((lul-1)*v)%lul
else:
	v = 1
	# print(ans)
	# print(l)
	for i in ans:
		v = (v*abs(l[i]))%lul
print(v)

Submission status: Runtime Error

Solution code:
from math import *
ln,k=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort(reverse=True,key = lambda s: abs(s))

lul = 10**9 + 7

temp = []
for i in range(ln):
	if l[i]<0:
		temp.append(-1*l[i])
ct = 0
p = -1; n = -1
ans = []
temp = [::-1]
for i in range(k):
	ans.append(i)
	if l[i]<0:
		ct+=1
		n = max(n,i)
	else:
		p = max(p,i)
# print(ct)
if ct%2!=0:
	for i in range(k,ln):
		if l[i]<0 and p!=-1:
			ans.remove(p)
			ans.append(i)
			ct+=1
			break
		elif l[i]>=0:
			ans.remove(n)
			ans.append(i)
			ct-=1
			break
# print(ct)
if ct%2!=0:
	v = 1
	for i in range(k):
		v = (v*temp[i])%lul
	v = ((lul-1)*v)%lul
else:
	v = 1
	# print(ans)
	# print(l)
	for i in ans:
		v = (v*abs(l[i]))%lul
print(v)

Submission status: Runtime Error

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

a_p =[]
a_m =[]
for i in a:
    if i >= 0:
        a_p.append(i)
    else :
        a_m.append(i)

a_p.sort()
a_m.sort(reverse=True)


a_select =[]

if n == k:
    a_select = a
elif len(a_p) == 0:
    for i in range(k):
        a_select.append(a_m[i])


while len(a_select) < k:
    if len(a_select) == k - 1:
        a_select.append(a_p[-1])
        break
    if len(a_p) == 1 and (k-len(a_select))%2 == 1:
        a_select.append(a_p.pop(-1))
    elif len(a_p) == 0:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))
    elif len(a_m) <= 1:
        a_select.append(a_p.pop(-1))
    elif a_p[-1]*a_p[-2] > a_m[-1]*a_m[-2] :
        a_select.append(a_p.pop(-1))
    else:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))

#print(a_select)
ans = 1
for i in a_select:
    ans = ans*i % (10**9 + 7)

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1


def min_pos(arr):
    pass


if neg_cnt == n:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
elif k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[i]))
    pos.sort(key=lambda v: abs(arr[i]))

    if k % 2:
        res = arr[pos[0]] % modulo
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k:
        if j == len(neg) or i < len(pos) and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo

    print(res)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
a =list(map(int, input().split()))
ans =1

if n == k:
   for i in a:
       ans *= i
       if abs(ans) >10**9+7:
           ans = ans%(10**9+7)

elif all(i <= 0 for i in a) and k%2 ==1:
    a.sort()
    for i in range(k):
        ans *= a[i]
        if abs(ans) > 10 ** 9 + 7:
            ans = ans % (10 ** 9 + 7)

else:
    am =[]
    ap =[]

    a.sort(key = abs,reverse = True)
    amax = a[:k]
    amin = a[k:]
    c=1
    if 0 in amax:
        ans = 0
    else:
        for i in amax:
            if i<0:
                am.append(i)
                c *=-1
            elif i>0:
                ap.append(i)
        if c ==1:
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)
        else:

            if min(amin)/min(ap) > max(amin)/max(am):
                amax.remove(max(am))
                amax.append(max(amin))
            else:
                amax.remove(min(ap))
                amax.append(min(amin))
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)

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

Submission status: Runtime Error

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        break
    if k%2 and not x:
        c=1
        for i in sorted(y)[-k:]:
            c=c*i%M
        print(c)
        break
    x=sorted(x)[::-1][:k]
    i=len(x)
    y.sort()
    m=len(y)
    j=k-i
    if j%2:
        x=x[:-1]
        i-=1
        j+=1
    x+=y[:j]
    if len(x)!=k:
        print(0)
        break
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

Submission status: Runtime Error

Solution code:
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(-abs(i)%mod)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[p]
                print(ans%mod)
                break
                
            elif 2 <= (len(AM) - m) and 2 <= (len(AP) - p):   
                if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                    ans *= (AP[p]*AP[p+1])
                    p += 2
                    cnt += 2
                
                else:
                    ans *= (AM[m]*AM[m+1])
                    m += 2
                    cnt += 2 
                    
            elif 1 >= (len(AP) - p) and 2 <= (len(AM) - m):
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 
            
            elif 2 <= (len(AP) - p) and 1 >= (len(AM) - m):
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
            
            

            if cnt == K:
                print(ans%mod)
                break

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1


def min_pos(arr):
    pass


if neg_cnt == n:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
elif k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[i]))
    pos.sort(key=lambda v: abs(arr[i]))

    if k % 2:
        res = arr[pos[0]] % modulo
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k:
        if j == len(pos) or i < len(pos) and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo

    print(res)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
a =list(map(int, input().split()))
ans =1

if n == k:
   for i in a:
       ans *= i
       if abs(ans) >10**9+7:
           ans = ans%(10**9+7)

elif all(i <= 0 for i in a) and k%2 ==1:
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        if abs(ans) > 10 ** 9 + 7:
            ans = ans % (10 ** 9 + 7)

else:
    am =[]
    ap =[]

    a.sort(key = abs,reverse = True)
    amax = a[:k]
    amin = a[k:]
    c=1
    if 0 in amax:
        ans = 0
    else:
        for i in amax:
            if i<0:
                am.append(i)
                c *=-1
            elif i>0:
                ap.append(i)
        if c ==1:
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)
        else:

            if min(amin)/min(ap) > max(amin)/max(am):
                amax.remove(max(am))
                amax.append(max(amin))
            else:
                amax.remove(min(ap))
                amax.append(min(amin))
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)

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

Submission status: Runtime Error

Solution code:
mod = 10**9+7

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

def modInverse(a,p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a,p-2,p)

d = {}
for a in A:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
        
absA = list(map(lambda x:abs(x),A))

absA.sort(reverse=True)


ans = 1
minus = 0
last = None
for i in range(k):
    if (absA[i] not in d) or (d[absA[i]] == 0):
        minus += 1
        last = absA[i]
    else:
        d[absA[i]] -= 1
    ans = ans*absA[i]%mod

if not minus%2:
    print(ans)
else:
    ans = ans*modInverse(ans, mod)
    while True:
        i += 1
        if absA[i] in d:
            ans = ans*absA[i]%mod
            break
        if i == n-1:
            ans = 1
            for i in range(k):
                ans *= absA[-(i+1)]%mod
            ans = -ans%mod
            break
    print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    N, K = list(map(int, input().split()))
    A = list(map(int, sysread().split()))
    mod = 10 ** 9 + 7

    plus = [a for a in A if a >= 0]
    minus = [-a for a in A if a < 0]

    plus = sorted(plus, reverse=True)
    minus = sorted(minus, reverse=True)

    P, M  = [1], [1]
    for p in plus:
        P.append((P[-1] * p) % mod)
    for m in minus:
        M.append(((M[-1] * (-m)) % mod))
    #print(P, M)
    max_ans = -1

    for i in range(K, -1, -2):
        if len(plus) < i:continue
        if len(minus) < K - i:continue
        if max_ans == -1:
            max_ans = P[i] * M[K-i] % mod
        else:
            if not plus[i] or not plus[i + 1]:
                max_ans = P[i] * M[K-i] % mod
            if plus[i+1] / minus[K-i-2] < minus[K-i-3] / plus[i]:
                max_ans = P[i] * M[K-i] % mod

    if max_ans == -1:
        plus = plus[::-1]
        minus = minus[::-1]
        P, M = [1], [1]
        for p in plus:
            P.append((P[-1] * p) % mod)
        for m in minus:
            M.append(((M[-1] * (-m)) % mod))

        for i in range(K-1, -1, -2):
            if len(plus) < i: continue
            if len(minus) < K - i: continue
            if max_ans == -1:
                max_ans = P[i] * M[K - i] % mod
            else:
                if not plus[i] or not plus[i+1]:
                    max_ans = 0
                    break
                if plus[i + 1] / minus[K - i - 2] > minus[K - i - 3] / plus[i]:
                    max_ans = P[i] * M[K - i] % mod

    print(max_ans)

if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    N, K = list(map(int, input().split()))
    A = list(map(int, sysread().split()))
    mod = 10 ** 9 + 7

    plus = [a for a in A if a >= 0]
    minus = [-a for a in A if a < 0]

    plus = sorted(plus, reverse=True)
    minus = sorted(minus, reverse=True)

    P, M  = [1], [1]
    for p in plus:
        P.append((P[-1] * p) % mod)
    for m in minus:
        M.append(((M[-1] * (-m)) % mod))
    #print(P, M)
    max_ans = -1

    for i in range(K, -1, -2):
        if len(plus) < i:continue
        if len(minus) < K - i:continue
        if max_ans == -1:
            max_ans = P[i] * M[K-i] % mod
        else:
            if not plus[i] or not plus[i + 1]:
                max_ans = max(max_ans, 0)
            if plus[i+1] / minus[K-i-2] < minus[K-i-3] / plus[i]:
                max_ans = P[i] * M[K-i] % mod

    if max_ans == -1:
        plus = plus[::-1]
        minus = minus[::-1]
        P, M = [1], [1]
        for p in plus:
            P.append((P[-1] * p) % mod)
        for m in minus:
            M.append(((M[-1] * (-m)) % mod))

        for i in range(K-1, -1, -2):
            if len(plus) < i: continue
            if len(minus) < K - i: continue
            if max_ans == -1:
                max_ans = P[i] * M[K - i] % mod
            else:
                if not plus[i] or not plus[i+1]:
                    max_ans = 0
                    break
                if plus[i + 1] / minus[K - i - 2] > minus[K - i - 3] / plus[i]:
                    max_ans = P[i] * M[K - i] % mod

    print(max_ans)

if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
ar=list(map(int,input().split()))
p,n=[],[]
mod=10**9+7
ans=1
for i in ar:
    if i>=0: p.append(i)
    else: n.append(i)
if len(p)<k and k%2:
    ar.sort(key=lambda x:abs(x))
    for i in range(k):
        ans*=ar[i]
        ans%=mod
else:
    p.sort(reverse=True)
    n.sort()
    pp,np=[],[]
    for i in range(1,len(p),2):
        pp.append((p[i]*p[i-1])%mod)
    for i in range(1,len(n),2):
        np.append((n[i]*n[i-1])%mod)
    i,j=0,0
    for l in range(k//2):
        if i<len(pp) and (j>=len(np) or pp[i]>np[j]):
            ans*=pp[i]
            ans%=mod
            i+=1
        else:
            if j<len(np):
                ans*=np[i]
                ans%=mod
                j+=1
    if k%2:
        ans*=p[2*i-1]
        ans%=mod
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()]
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:
    if K%2 == 1:
        if len(zero) != 0:
            print(0)
            sys.exit()
        else:
            minus.sort(reverse=True)
            num = 1
            for x in minus:
                num *= x%mod
            print(num%mod)
    else:
        A.sort()
        num = 1
        for x in A[:K]:
            num *= x%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()

if len(plus) + len(minus) == K:
    if len(minus)%2 == 0:
        num = 1
        for x in plus:
            num *= x%mod
        for x in minus:
            num *= x%mod
        print(num%mod)
        sys.exit()
    else:
        print(0)
        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)
        heappush(plus, a)
        cnt += 1
        last_minus = b
    else:
        ans.append(a)
        heappush(minus, b)
        last_plus = a

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

if flag == 2:
    for i in range(K - len(ans)):
        a = heappop(plus)
        last_plus = a
        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
    ls = []
    for a in ans:
        if a < 0:
            ls.append(-a)
        else:
            ls.append(a)

    if len(plus) != 0 and len(minus) != 0:
        a = heappop(plus)
        b = heappop(minus)
        if a < 0:
            a = -a
        if b < 0:
            b = -b
        if last_minus < 0:
            last_minus = -last_minus
        if last_plus < 0:
            last_plus = -last_plus
        
        if last_plus == 0:
            for c in ls[:-1]:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
            sys.exit()
        if last_minus == 0:
            for c in ls[:-1]:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)
            sys.exit()

        if a *last_plus >= b*last_minus:
            ls.remove(last_minus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
        else:
            ls.remove(last_plus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)
    elif len(plus) == 0:
        c = heappop(minus)
        if c < 0:
            c = -c
        if last_plus < 0:
            last_plus = -last_plus
        ls.remove(last_plus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)
    elif len(minus) == 0:
        c = heappop(plus)
        if c < 0:
            c = -c
        if last_minus < 0:
            last_minus = -last_minus
        ls.remove(last_minus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    N, K = list(map(int, input().split()))
    A = list(map(int, sysread().split()))
    mod = 10 ** 9 + 7

    plus = [a for a in A if a >= 0]
    minus = [-a for a in A if a < 0]

    plus = sorted(plus, reverse=True)
    minus = sorted(minus, reverse=True)

    P, M  = [1], [1]
    for p in plus:
        P.append((P[-1] * p) % mod)
    for m in minus:
        M.append(((M[-1] * (-m)) % mod))
    #print(P, M)
    max_ans = -1

    for i in range(K, -1, -2):
        if len(plus) < i:continue
        if len(minus) < K - i:continue
        if max_ans == -1:
            max_ans = P[i] * M[K-i] % mod
        else:
            if plus[i+1] / minus[K-i-2] < minus[K-i-3] / plus[i]:
                max_ans = P[i] * M[K-i] % mod

    if max_ans == -1:
        plus = plus[::-1]
        minus = minus[::-1]
        P, M = [1], [1]
        for p in plus:
            P.append((P[-1] * p) % mod)
        for m in minus:
            M.append(((M[-1] * (-m)) % mod))

        for i in range(K-1, -1, -2):
            if len(plus) < i: continue
            if len(minus) < K - i: continue
            if max_ans == -1:
                max_ans = P[i] * M[K - i] % mod
            else:
                if not plus[i] or not plus[i+1]:
                    max_ans = 0
                    break
                if plus[i + 1] / minus[K - i - 2] > minus[K - i - 3] / plus[i]:
                    max_ans = P[i] * M[K - i] % mod

    print(max_ans)

if __name__ == "__main__":
    run()