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()))
ans = int(input().strip())

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

if N == K:

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

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

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

elif 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

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

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

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_min_pos is None and used[k] >= 0: used_min_pos = k
            elif used_min_neg is None and used[k] <  0: 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, -1):
            if   rest_min_pos is None and rest[k] >= 0: rest_min_pos = k
            elif rest_min_neg is None and rest[k] <  0: 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 used:
        r = (r * a) % D

print(r)

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

Submission status: Runtime Error

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

if n==k:
  ans=1
  for i in range(k):ans=ans*a[i]%MOD
  print(ans)
  exit()

p=[]
m=[]
for q in a:
  if q>=0:p+=q,
  else:m+=q,

if p==[] and k%2==1:
  m.sort(reverse=True)
  ans=1
  for i in range(k):ans=ans*m[i]%MOD
  print(ans)
  exit()

a.sort(key=lambda x:abs(x),reverse=True)

s=[]
flg=1
for i in range(k):
  s.append(a[i])
  if a[i]<0:
    flg*=-1
if flg==-1:
  tmp=s.pop()
  if -tmp in s:
    s.append(a[k])
    break
  for i in range(k,n):
    if a[i]*tmp<=0:
      s.append(a[i])
      break
ans=1
for i in s:
  ans=ans*i%MOD
print(ans)

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(i)
        else:
            AP.append(i)
            
    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])%mod
                    p += 2
                    cnt += 2
                
                else:
                    ans *= (AM[m]*AM[m+1])%mod
                    m += 2
                    cnt += 2 
                    
            elif 1 >= (len(AP) - p) and 2 <= (len(AM) - m):
                ans *= (AM[m]*AM[m+1])%mod
                m += 2
                cnt += 2 
            
            elif 2 <= (len(AP) - p) and 1 >= (len(AM) - m):
                ans *= (AP[p]*AP[p+1])%mod
                p += 2
                cnt += 2
            
            

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

Submission status: Runtime Error

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


plus_lst = list(filter(lambda num: num >= 0 , a_lst))
minus_lst = list(filter(lambda num: num < 0 , a_lst))
plus_lst.sort(reverse=True)
minus_lst.sort(reverse=True)


# +,-どちらもk以上ある
	# max(abs+,abs-)で大きい方をk-1回目までとる, k-1回目で+だったら+, -だったら-
# +: kない, -: kある
	# +の数が残り1になるまでabsでやる,最後に+を使って調整する
# +: kある, -: kない
	# -の数が1になるまでabsでやる, 最後に-を使って調整
# +: kない, -: kない
	# どちらかが残り1になるまでやる,最後に調整
# -のみ
	# absでできるだけ小さいものを使う

# 0を抜いたらk個なかった場合、絶対どっかで0を掛けるので0
# 全部-の場合
if(len(plus_lst) == 0):
	total = 1
	for i in range(k):
		total *=minus_lst[i]
	print(total % (10**9 + 7))
elif(len(minus_lst) == 0):
	total = 1
	for i in range(k):
		total *= plus_lst[i]
	print(total % (10**9 + 7))
else:
	total = 1
	for i in range(k):
		if(i == k - 1):
			if(total > 0):
				total *= plus_lst.pop(0)
			else:
				total *= minus_lst.pop(-1)
		else:
			# plus残り1の場合
			if(len(plus_lst) == 1):
				total *= minus_lst.pop(-1)
			# minus残り1の場合
			elif(len(minus_lst) == 1):
				total *= plus_lst.pop(0)					
			# +-どっちも十分あった場合
			else:
				plus_max = plus_lst[0]
				minus_max = minus_lst[0]
				if(abs(plus_max) > abs(minus_max)):
					plus_lst.pop(0)
					total *= plus_max
				else:
					minus_lst.pop(-1)
					total *= minus_max
	print(total % (10**9 + 7))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if False:
  print("test")
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        
        if True:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max/negative_big_max < negative_small_min/positive_big_min:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
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(i)
        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])%mod
                    p += 2
                    cnt += 2
                
                else:
                    ans *= (AM[m]*AM[m+1])%mod
                    m += 2
                    cnt += 2 
                    
            elif 1 >= (len(AP) - p) and 2 <= (len(AM) - m):
                ans *= (AM[m]*AM[m+1])%mod
                m += 2
                cnt += 2 
            
            elif 2 <= (len(AP) - p) and 1 >= (len(AM) - m):
                ans *= (AP[p]*AP[p+1])%mod
                p += 2
                cnt += 2
            
            

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

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
mod = 10**9 + 7
nums = []
for i in list(map(int, input().split())):
    if i >= 0:
        nums.append((i, True))
    else:
        nums.append((-i, False))
rev_nums = sorted(nums, reverse=True)
nums.sort()
print(rev_nums)
print(nums)
ans = 1
pl = []
ml = []
for k in range(K):
    x, b = nums.pop()
    ans *= x
    ans %= mod
    if b:
        pl.append(x)
    else:
        ml.append(x)
if len(ml) % 2 != 0:
    while nums:
        x, b = nums.pop()
        if b:
            ans //= ml[-1]
            ans %= mod
            ans *= x
            ans %= mod
            break
        else:
            ans //= pl[-1]
            ans %= mod
            ans *= x
            ans %= mod
            break
    else:
        ans = -1
        for k in range(K):
            x, b = rev_nums.pop()
            ans *= x
            ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if False:
  print("test")
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max/negative_big_max < negative_small_min/positive_big_min:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import math
import numpy as np

# 標準入力を取得
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

# 求解処理
A = sorted(A, reverse=True)
ans = 0
if (A[0] < 0) and (K % 2 == 1):
    ans = sum(A[:K])
else:
    A = sorted(A, key=abs, reverse=True)
    ans = 1
    for k in range(K):
        ans *= A[k]
    if ans < 0:
        ans_mp = ans
        M_high = sorted([m for m in A[:K] if m < 0], key=abs)
        P_low = sorted([p for p in A[K:] if p >= 0], key=abs, reverse=True)
        if min(len(M_high), len(P_low)) > 0:
            ans_mp = ans_mp / M_high[0] * P_low[0]

        ans_pm = ans
        P_high = sorted([p for p in A[:K] if p > 0], key=abs)
        M_low = sorted([m for m in A[K:] if m <= 0], key=abs, reverse=True)
        if min(len(P_high), len(M_low)) > 0:
            ans_pm = ans_pm / P_high[0] * M_low[0]

        ans = max(ans_mp, ans_pm)
ans %= pow(10, 9) + 7

# 結果出力
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
mod = 10*9 + 7
if k%2==0:
  i = 0
  left = 0
  right = n-1
  ans = 1
  while i<k:
    m1 = a[left]*a[left+1]
    m2 = a[right]*a[right-1]
    #print(m1,m2)
    if m1<m2:
      ans*=m2
      right -=2
    else:
      ans *= m1
      left+=2
    ans %= mod
    i+=2
  print(ans)
else:
  a = [0]
  print(a[2])

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 = -1
ip = -1
cp = 0
mod = 10 ** 9 + 7
nm = 0
np = 0

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

ans = 1
f = 0

# print(a)
if cnt % 2 and k < n:
    if cp == 0:
        a.sort(reverse=True)
        for i, ai in enumerate(a):
            if i == k:
                break
            ans *= ai
            ans %= mod
        print(ans) # ok
    else:
        ans = 1
        cnt = 0
        f1 = 0
        f2 = 0
        for i, ai in enumerate(a):
            if cnt == k - 2:
                break
            if i == im:
                f1 = 1
                continue
            if i == ip:
                f2 = 1
                continue
            if f1 and ai <= 0:
                continue
            if f2 and ai >= 0:
                continue
            ans *= abs(ai)
            ans %= mod
            # print(i, ai)
            cnt += 1
        ans *= max(a[ip] * np, a[im] * nm)
        ans %= mod
        print(1/0)
else:
    for i, ai in enumerate(a):
        if i == k:
            break
        ans *= abs(ai)
        ans %= mod
    print(ans) # ok

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
N,K=map(int, input().split())
A=list(map(int, input().split()))
p=10**9+7
A=sorted(A)
thresh=bisect_left(A,0)
minus=A[:thresh]
plus=A[thresh:][::-1]

#print(plus, minus)
if len(plus)==0:
    ans=1
    if K%2!=0:
        minus=minus[::-1]
        for i in range(K):
            ans*=minus[i]
            ans%=p
    else:
        for i in range(K):
            ans*=minus[i]
            ans%=p
    print(ans)
    exit()

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

midx=0
pidx=0
ans=1
while K>0 and (0<=midx<len(minus) or 0<=pidx<len(plus)):
    if midx==len(minus)-1:
        nexmin=minus[midx]
    elif midx>=len(minus):
        nexmin=-1
    else:
        nexmin=minus[midx]*minus[midx+1]

    if pidx==len(plus)-1:
        nexplus=plus[pidx]
    elif pidx>=len(plus):
        nexplus=-float("INF")
    else:
        if plus[pidx+1]!=0:
            nexplus=plus[pidx]*plus[pidx+1]
        else:
            nexplus=plus[pidx]

    if nexmin>=nexplus and K>=2:
        ans*=nexmin
        ans%=p
        midx+=2
        K-=2
    else:
        ans*=plus[pidx]
        ans%=p
        pidx+=1
        K-=1

print(ans)

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 am == []:
                amax.remove(max(am))
                amax.append(max(amin))

            elif 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:
n, k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7

plus = []
minus = []

for i in a:
	if i >= 0:
		plus.append(i)
	else:
		minus.append(i)

plus.sort(key = lambda x:-x)
minus.sort()

#print(plus, minus)

"""
貪欲チックに求める
numplus … 前からnumplus番目まで掛け合わせる
numminus … 前からnumminus番目まで掛け合わせる

入力例2に合わせるのは場合分けが必要だが, minusは2個単位で管理する.
"""

numplus = k
numminus = 0

"""
kがplusを超える場合, うまく処理ができないのでリスト参照できる範囲まで下げる.
"""
while numplus > len(plus):
	numplus -= 2
	numminus += 2

#print(numplus, numminus)

while numplus-2 >= 0 and numminus+1 < len(minus):
	if plus[numplus-1] * plus[numplus-2] <= minus[numminus] * minus[numminus+1]:
		numplus -= 2
		numminus += 2
	else:
		break

#print(numplus, numminus)

ans = 1

if numplus >= 0 and numminus >= 0:
	for i in range(numplus):
		ans = ans * plus[i] % mod
	for i in range(numminus):
		ans = ans * minus[i] % mod
else:
	"""
	これは, ansが負になる場合や, minusが1個だけの場合, minusしかない場合, plusしかない場合に使える.
	"""
	#print("ここに来ました！")
	tmp = sorted(a, key=lambda x:-x)
	for i in range(k):
		ans = ans * tmp[i]%mod

print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
N,K=map(int, input().split())
A=list(map(int, input().split()))
p=10**9+7
A=sorted(A)
thresh=bisect_left(A,0)
minus=A[:thresh]
plus=A[thresh:][::-1]

#print(plus, minus)
if len(plus)==0:
    ans=1
    if K%2!=0:
        minus=minus[::-1]
        for i in range(K):
            ans*=minus[i]
            ans%=p
    else:
        for i in range(K):
            ans*=minus[i]
            ans%=p
    print(ans)
    exit()

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

midx=0
pidx=0
ans=1
while K>0 and (0<=midx<len(minus) or 0<=pidx<len(plus)):
    if midx==len(minus)-1:
        nexmin=minus[midx]
    elif midx>=len(minus):
        nexmin=-1
    else:
        nexmin=minus[midx]*minus[midx+1]

    if pidx==len(plus)-1:
        nexplus=plus[pidx]
    elif pidx>=len(plus):
        nexplus=-float("INF")
    else:
        nexplus=plus[pidx]*plus[pidx+1]

    if nexmin>=nexplus and K>=2:
        ans*=nexmin
        ans%=p
        midx+=2
        K-=2
    else:
        ans*=plus[pidx]
        ans%=p
        pidx+=1
        K-=1

print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
from operator import mul
import heapq

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 = list(map(lambda x: x*(-1), AP))
        heapq.heapify(AP)
        heapq.heapify(AM)
        
        ans = 1
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[0]
                print(ans%mod)
                break
                
            if 2 <= len(AP):
                AP2 = heapq.heappop(AP)*(-1)
                AP1 = heapq.heappop(AP)*(-1)
                

            if 2 <= len(AM):
                AM1 = heapq.heappop(AM)
                AM2 = heapq.heappop(AM)

                
            if AP1*AP2 >= AM1*AM2:
                ans *= AP1*AP2
                cnt += 2
                
            else:
                ans *= AM1*AM2
                m += 2
                cnt += 2 
                    
            if 1 >= len(AP) and 2 <= len(AM):
                ans *= AM1*AM2
                cnt += 2 
            
            if 2 <= len(AP) and 1 >= len(AM):
                ans *= AP1*AP2
                cnt += 2
            
            if cnt == K:
                print(ans%mod)
                break

Submission status: Runtime Error

Solution code:
from functools import reduce
from operator import mul
import heapq

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 = list(map(lambda x: x*(-1), AP))
        heapq.heapify(AP)
        heapq.heapify(AM)
        
        ans = 1
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[0]
                print(ans%mod)
                break
                
            if 2 <= len(AM):
                AP2 = heapq.heappop(AP)*(-1)
                AP1 = heapq.heappop(AP)*(-1)
                

            if 2 <= len(AP):
                AM1 = heapq.heappop(AM)
                AM2 = heapq.heappop(AM)

                
            if AP1*AP2 >= AM1*AM2:
                ans *= AP1*AP2
                cnt += 2
                
            else:
                ans *= AM1*AM2
                m += 2
                cnt += 2 
                    
            if 1 >= len(AP) and 2 <= len(AM):
                ans *= AM1*AM2
                cnt += 2 
            
            if 2 <= len(AP) and 1 >= len(AM):
                ans *= AP1*AP2
                cnt += 2
            
            if cnt == K:
                print(ans%mod)
                break

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 =[-10**8]
    ap =[10**8]

    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 python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
MOD = pow(10, 9) + 7

N, K, *A = map(int, read().split())
A_pos = [a for a in A if a > 0]
A_neg = [a for a in A if a < 0]

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
elif len(A_neg) == N and K % 2 == 1:
    A = sorted(A, key=lambda x: abs(x))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD

else:
    A_pos = sorted(A_pos, key=lambda x: -abs(x))
    A_neg = sorted(A_neg, key=lambda x: -abs(x))
    ans = 1
    cnt = 0
    while True:
        if len(A_pos) > 1:
            acc_pos = A_pos[0] * A_pos[1]
        else:
            acc_pos = 0
        if len(A_neg) > 1:
            acc_neg = A_neg[0] * A_neg[1]
        else:
            acc_neg = 0

        if acc_pos > acc_neg or cnt == K - 1:
            if len(A_pos) > 0:
                ans *= A_pos[0]
                A_pos = A_pos[1:]
            else:
                ans *= A_neg[0]
                A_neg = A_neg[1:]
            ans %= MOD
            cnt += 1
        else:
            ans *= acc_neg
            ans %= MOD
            A_neg = A_neg[2:]
            cnt += 2

        if cnt == K:
            break

print(ans % 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 not plus[i] or not plus[i + 1]:
                max_ans = P[i] * M[K-i] % mod
            if plus[i+1] / minus[K-i-1] < minus[K-i-2] / 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 - 1] > minus[K - i - 2] / plus[i]:
                    max_ans = P[i] * M[K - i] % mod

    print(max_ans)

if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
from collections import deque
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x))
res = 1
if N == K:
    for a in A:
        res *= a
        res %= MOD
    print(res)
    exit()
cnt = sum(1 if a < 0 else 0 for a in A)
if cnt == N and K % 2 == 1:
    for a in A[:K]:
        res *= a
        res %= MOD
    print(res)
    exit()
plus = [a for a in A if a >= 0]
minus = [a for a in A if a < 0]
cnt = 0
res = 1
while cnt < K:
    if len(plus) >= 2:
        tmp1 = plus[-1] * plus[-2]
    elif len(plus) == 1:
        tmp1 = plus[0]
    if len(minus) >= 2:
        tmp2 = minus[-1] * minus[-2]
    else:
        tmp2 = -1
    if tmp1 < tmp2 and cnt < K - 1:
        res *= minus.pop() * minus.pop()
        res %= MOD
        cnt += 2
    else:
        res *= plus.pop()
        res %= MOD
        cnt += 1
print(res)