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:
mod = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
ans = 1
if N == K:
    for i in range(K):
        ans *= A[i]
        if abs(ans) > mod:
            ans %= mod
elif len([v for v in A if v < 0]) == N:
    for i in range(K):
        ans *= A[-(i + 1)]
        if abs(ans) > mod:
            ans %= mod
else:
    num_hu = len([v for v in A[:K] if v < 0])
    if num_hu % 2 == 0:
        for i in range(K):
            ans *= A[i]
            if abs(ans) > mod:
                ans %= mod
    else:
        if len([v for v in A[K:] if v >= 0]) == N - K:
            min_hu_idx = K - 1
            while True:
                if A[min_hu_idx] < 0:
                    break
                min_hu_idx -= 1
            max_sei_idx = K
            for i in range(K):
                if i == min_hu_idx:
                    ans *= A[max_sei_idx]
                else:
                    ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
        elif len([v for v in A[K:] if v <= 0]) == N - K:
            print('aaa')
            min_sei_idx = K - 1
            while True:
                if A[min_sei_idx] > 0:
                    break
                min_sei_idx -= 1
            max_hu_idx = K
            for i in range(K):
                if i == min_sei_idx:
                    ans *= A[max_hu_idx]
                else:
                    ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
        else:
            ans_1 = 1
            ans_2 = 1
            # ans_1
            min_hu_idx = K - 1
            while True:
                if A[min_hu_idx] < 0:
                    break
                min_hu_idx -= 1
            max_sei_idx = K
            while True:
                if A[max_sei_idx] > 0:
                    break
                max_sei_idx += 1
            for i in range(K):
                if i == min_hu_idx:
                    ans_1 *= A[max_sei_idx]
                else:
                    ans_1 *= A[i]
                if abs(ans_1) > mod:
                    ans_1 %= mod
            # ans_2
            min_sei_idx = K - 1
            while True:
                if A[min_sei_idx] > 0:
                    break
                min_sei_idx -= 1
            max_hu_idx = K
            while True:
                if A[max_hu_idx] < 0:
                    break
                max_hu_idx += 1
            for i in range(K):
                if i == min_sei_idx:
                    ans_2 *= A[max_hu_idx]
                else:
                    ans_2 *= A[i]
                if abs(ans_2) > mod:
                    ans_2 %= mod
            ans = max(ans_1, ans_2)
print(ans % mod)

Submission status: Runtime Error

Solution code:
import sys, bisect


if(__name__ == "__main__"):


    N, K = map( int, input().strip().split() )
    divisor = 10**9+7

    list_a = list( map(int, input().strip().split()) )

    """
    left, right側の2項の積で大きい方を選択
    選べるのが残り1項ならright側を選択
    """
    multiplies = 1

    if(N==K):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
        print(multiplies)
    else:
        list_a.sort()

        flag_overzero = True
        if(list_a[-1] < 0 and K % 2 != 0):
            flag_overzero = False
        """
        解が負になるのはN>Kの時には
        正の項が1つもなく、Kが奇数の時
        """
        if(flag_overzero == True):
            left = 0
            right = N-1

            if(K%2 != 0):
                multiplies = multiplies * list_a[right] % divisor
                K -= 1
                right -= 1
            multiply_left = list_a[left] * list_a[left+1]
            multiply_right = list_a[right] * list_a[right-1]
            for k in range(K//2):

                if(multiply_left < multiply_right):
                    multiply_right %= divisor
                    multiplies = multiplies * multiply_right % divisor
                    right -= 2
                    multiply_right = list_a[right] * list_a[right-1]

                else:
                    multiply_left %= divisor
                    multiplies = multiplies * multiply_left % divisor
                    left += 2
                    multiply_left = list_a[left] * list_a[left+1]


            print(multiplies)
        else:
            list_a = [ abs(list_a[i]) for i in range(N)]
            list_a.sort()
            multiplies = -1
            for i in range(K):
                multiplies = multiplies * list_a[i] % divisor

            print(multiplies)

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:
        print(0)
        sys.exit()
    else:
        num = 1
        minus.sort()
        for x in minus[:K]:
            if x < 0:
                x = -x
            num *= x
            num %= mod
        print(num%mod)
        sys.exit()

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

flag = 0

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

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

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

if cnt%2 == 0:
    num = 1
    for a in ans:
        if a < 0:
            a = -a
        num = (num * a%mod)%mod
    print(num%mod)
    sys.exit()
else:
    num = 1
    ls = []
    for a in ans:
        if a < 0:
            ls.append(-a)
        else:
            ls.append(a)
    if 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)
    else:
        a = heappop(plus)
        b = heappop(minus)
        if a < 0:
            a = -a
        if b < 0:
            b = -b
        if last_minus < 0:
            last_minus = -a
        if last_plus < 0:
            last_plus = -last_plus

        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)

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if N==K:
    c=1
    for a in A:
        c*=a
        c%=mod

elif len(Ap)==0 and K%2:
    c=1
    while K :
        c*=Am.popleft()

        K-=1

        c%=mod
    c=-c
    c%=mod
    #print("unko")

else:
    #print(unko)
    c=1
    h=0
    a="unko"
    b="unko"
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[-1]>Ap[-1]:

                a=Am.pop()
                c*=a
                h+=1
            else:

                b=Ap.pop()
                c*=b

        elif Am:
            a=Am.pop()
            c*=a
            h+=1
        elif Ap:
            b=Ap.pop()
            c*=b
        K-=1
        c%=mod

    if h%2:
        if Am and Ap and a!="unko" and b!="unko":
            if Am[-1]*a>Ap[-1]*b:
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        elif Am:
            a=Am.pop()
            c*=a
            c*=pow(b,mod-2,mod)
        else:
            b=Ap.pop()
            c*=b
            c*=pow(a,mod-2,mod)


print(c%mod)

Submission status: Runtime Error

Solution code:
#!/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

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 *= ms[i]
    return ans

def take_p(ans, k, ps, pk):
    ans *= ps[pk]
    pk += 1
    return ans, k - 1, pk

def take_m(ans, k, ms, mk, sign_p):
    ans *= ms[mk]
    mk += 1
    return ans, k - 1, mk, sign_p

def take_all_m(ans, k, ms, mk, sign_p):
    while k > 0:
        ans, mk, sign_p = take_m(ans, ms, mk, sign_p)
        k -= 1
    return ans

def solve(data, k):
    ps, ms = mysplit(data)
    if len(ps) == 0:
        return small_abs(ms, k)
    ans = ModInt(1)
    sign_p = True
    pk = 0
    mk = 0
    while k > 0:
        if pk == len(ps) - 1: # last p
            if k % 2 == 1:
                ans, k, pk = take_p(ans, k, ps, pk)
                k -= 1
                print('hoge') # debug
            return take_all_m(ans, k, ms, mk, sign_p)
        if mk >= len(ms) or ps[pk] > -1 * ms[mk]:
            ans, k, pk = take_p(ans, k, ps, pk)
        else:
            ans, k, mk, sign_p = take_m(ans, k, ms, mk, sign_p)
    return ans



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()))
ap=[]
a0=[]
am=[]
for i in range(n):
    if a[i]>0:
        ap.append(a[i])
    elif a[i]==0:
        a0.append(a[i])
    else:
        am.append(a[i])
ap.sort(reverse=True)
am.sort()
ap2=[]
for i in range(len(ap)//2):
    ap2.append([ap[i*2]*ap[i*2+1],i+1])
am2=[]
for i in range(len(am)//2):
    am2.append([am[i*2]*am[i*2+1],0])
aa3=[]
pc=0
mc=0
print(ap2,am2)
while pc<len(ap2) and mc<len(am2):
    if ap2[pc][0]<=am2[mc][0]:
        aa3.append(am2[mc])
        mc+=1
    elif ap2[pc][0]>am2[mc][0]:
        aa3.append(ap2[pc])
        pc+=1
while pc<len(ap2):
    aa3.append(ap2[pc])
    pc+=1
while mc<len(am2):
    aa3.append(am2[mc])
    mc+=1
f=0
ans=1
for i in range(len(aa3)):
    if k>=2:
        ans*=aa3[i][0]
        ans%=(10**9+7)
        k-=2
        if aa3[i][1]!=0:
            f=aa3[1]
    elif k==1:
        if f*2<len(ap):
            ans*=ap[f*2]
            ans%=10**9+7
            k-=1
        else:
            break
    else:
        break
if k==0:
    print(ans%(10**9+7))
else:
    if len(ap)%2==0:
        if len(a0)>0:
            print(0)
        else:
            print((ans*am[len(am)-1])%(10**9+7))
    else:
        ans*=ap[f*2]
        ans%=10**9+7
        k-=1
        if k>0:
            if len(a0)>0:
                print(0)
            else:
                print((ans*am[len(am)-1])%(10**9+7))

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())

A=list(map(int,input().split()))
mod=10**9+7
Am=[-i for i in A if i<0]
Ap=[i for i in A if i>=0]

Am.sort()
Ap.sort()
Am=deque(Am)
Ap=deque(Ap)



if N==K:
    c=1
    for a in A:
        c*=a
        c%=mod

elif len(Ap)==0 and K%2:
    c=1
    while K :
        c*=Am.popleft()

        K-=1

        c%=mod
    c=-c
    c%=mod
    #print("unko")

else:
    #print(unko)
    c=1
    h=0
    a="unko"
    b="unko"
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[-1]>Ap[-1]:

                a=Am.pop()
                c*=a
                h+=1
            else:

                b=Ap.pop()
                c*=b

        elif Am:
            a=Am.pop()
            c*=a
            h+=1
        elif Ap:
            b=Ap.pop()
            c*=b
        K-=1
        c%=mod
    break
    if h%2:
        if Am and Ap and a!="unko" and b!="unko":
            if Am[-1]*a>Ap[-1]*b:
                a=Am.pop()
                c*=a
                c*=pow(b,mod-2,mod)
            else:
                b=Ap.pop()
                c*=b
                c*=pow(a,mod-2,mod)
        if Am:
            a=Am.pop()
            c*=a
            c*=pow(b,mod-2,mod)
        else:
            b=Ap.pop()
            c*=b
            c*=pow(a,mod-2,mod)


print(c%mod)

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lp,2):
			if i == lp-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	#data = []
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1
					else:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1

				else:
					count += 1
					#ans *= pra[cp]
					#data.append(pra[cp])
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1
					else:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1


				else:
					count += 1
					#ans *= mina[cm]
					#data.append(mina[cm])
					cm += 1
		elif cp != lp:
			#ans *= pra[cp]
			#data.append(pra[cp])
			cp -= 1
			count += 1
		elif cm != lm:
			#ans *= mina[cm]
			#data.append(mina[cm])
			cm += 1
			count += 1

		else:
			break
	if cm % 2 != 0:
		if cp == 0:
			cp -= 1
			cm -= 1

		else:
			if cp != -1 and cm != lm:
				if pra[cp+1] != 0 and pra[cp]/-mina[cm-1] <= -mina[cm]/pra[cp+1]:
					cp += 1
					cm += 1
				else:
					cp -= 1
					cm -= 1
			elif cp != -1:
				cp -= 1
				cm -= 1
			elif cm != lm:
				cp += 1
				cm += 1

		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod


		
	print(ans)

Submission status: Runtime Error

Solution code:
M = 10 ** 9 + 7
N, K = map(int, input().split())

p_list = []
n_list = []
z_count = 0

for A in map(int, input().split()):
	if A < 0:
		n_list.append(A)
	elif A > 0:
		p_list.append(A)
	else:
		z_count += 1

p_list.sort()
n_list.sort()

#print(p_list)
#print(n_list)

if len(p_list) + len(n_list) < K:
	print(0)
else:
	values = []
	
	if len(p_list) + len(n_list) == K:
		values = p_list + n_list
	elif len(p_list) + len(n_list) == K + 1 and len(p_list) == 0 and K % 2 == 1:
		for i in range(min(len(n_list), K)):
			values.append(n_list.pop())
	else:
		p_list.reverse()
		values_pair = []
		values_left = None
		values_left_count = 0
		if len(p_list) >= K:
			if K % 2 == 1:
				values_left = p_list.pop()
				values_left_count = 1
				p_count = K - 1
			else:
				p_count = K
			
			while len(values_pair) * 2 + values_left_count < K:
				v1 = p_list.pop()
				v2 = p_list.pop()
				values_pair.append((v1 * v2, v1, v2))
		
		else:
			if (K - len(p_list)) % 2 == 1:
				p_count = len(p_list) - 1
			else:
				p_count = len(p_list)
			
			if p_count % 2 == 1:
				values_left = p_list.pop()
				values_left_count = 1
				p_count -= 1
			
			for i in range(0, p_count - 1, 2):
				v1 = p_list.pop()
				v2 = p_list.pop()
				values_pair.append((v1 * v2, v1, v2))
			
			while len(values_pair) * 2 + values_left_count < K:
				v1 = n_list.pop()
				v2 = n_list.pop()
				values_pair.append((v1 * v2, v1, v2))
		
		values_pair.sort()
		
		i = 0
		for i in range(len(values_pair)):
			if len(n_list) < 2:
				break
			elif values_pair[i][0] < n_list[-1] * n_list[-2]:
				v1 = n_list.pop()
				v2 = n_list.pop()
				values_pair[i] = (v1 * v2, v1, v2)
			else:
				break
		if values_left != None:
			values.append(values_left)
		
		for prod, v1, v2 in values_pair:
			values.append(v1)
			values.append(v2)
	
#	print(values)
	total = 1
	for v in values:
		total = (total * v) % M
	print(total)

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

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

Ps = [-a for a in As if a > 0]
Qs = [a for a in As if a < 0]
Zs = [ 0 for a in As if a == 0]
D  = int(1E9 + 7)

if len(Ps) == 0 and K % 2 == 1:
    Qs = [- a for a in As if a < 0]
    r = 1
    for k in range(K):
        q = - heapq.heappop(Qs)
        r = (r * q % D) % D
    print(r)
    exit()


heapq.heapify(Ps)
heapq.heapify(Qs)


k = 0
r = 1

while k < K:

    if len(Ps) == 0 and len(Qs) == 0:
        k = 0
        break

    if (K - k) == 1 and len(Ps) > 0:
        p = - heapq.heappop(Ps)
        r = (r * (p % D)) % D
        k += 1

    elif (K - k) == 1 and len(Qs) > 0:
        q = - heapq.heappop(Qs)
        r = (r * (q % D)) % D
        k += 1

    elif len(Qs) < 2:
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2
        r  = (r * (p % D)) % D
        k += 2

    elif len(Ps) < 2:
        q1 = - heapq.heappop(Qs)
        q2 = - heapq.heappop(Qs)
        q  = q1 * q2
        r  = (r * (q % D)) % D
        k += 2

    else: 
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2

        q1 = - heapq.heappop(Qs)
        q2 = - heapq.heappop(Qs)
        q  = q1 * q2

        if p > q:
            r  = (r * (p % D)) % D
            heapq.heappush(Qs, -q1)
            heapq.heappush(Qs, -q2)
        else:
            r  = (r * (q % D)) % D
            heapq.heappush(Ps, -p1)
            heapq.heappush(Ps, -p2)

        k += 2

print(r)

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

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()

a.sort()

mina = []

pra = []

for i in range(n):
	if a[i] >= 0:
		pra.append(a[i])
	else:
		mina.append(a[i])

lp = len(pra)

lm = len(mina)
ans = 1
if lp == 0:
	if k % 2 != 0:
		for i in range(0,k,2):
			if i == k-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		for i in range(0,k,2):
			ans *= (mina[i]*mina[i+1]) % mod
			ans %= mod
		print(ans % mod)
elif lp == 1:
	if n == k:
		ans *= pra[0]
		for i in range(0,lp,2):
			if i == lp-1:
				i = -(1+i)
				ans *= mina[i]
			else:
				i = -(1+i)
				ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		print(ans % mod)
	else:
		if k % 2 == 0:
			for i in range(0,k,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
		else:
			ans *= pra[0] 
			for i in range(0,k-1,2):
				ans *= (mina[i]*mina[i+1]) % mod
				ans %=  mod
			print(ans % mod)
else:
	cp = lp-1
	cm = 0
	count = 0
	#data = []
	
	for _ in range(k):
		if cp != -1 and cm != lm:
			if abs(mina[cm]) <= pra[cp]:
				if cp == 0:
					if (k-lp) % 2 == 0:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1
					else:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1

				else:
					count += 1
					#ans *= pra[cp]
					#data.append(pra[cp])
					cp -= 1
			else:
				if cm == lm-1:
					if lm % 2 == 0:
						count += 1
						#ans *= mina[cm]
						#data.append(mina[cm])
						cm += 1
					else:
						count += 1
						#ans *= pra[cp]
						#data.append(pra[cp])
						cp -= 1


				else:
					count += 1
					#ans *= mina[cm]
					#data.append(mina[cm])
					cm += 1
		elif cp != lp:
			#ans *= pra[cp]
			#data.append(pra[cp])
			cp -= 1
			count += 1
		elif cm != lm:
			#ans *= mina[cm]
			#data.append(mina[cm])
			cm += 1
			count += 1

		else:
			break
	if cm % 2 != 0:
		if cp == 0:
			cp += 1
			cm += 1

		else:
			if cp != -1 and cm != lm:
				if pra[cp+1] != 0 and pra[cp]/-mina[cm-1] <= -mina[cm]/pra[cp+1]:
					cp += 1
					cm += 1
				else:
					cp -= 1
					cm -= 1
			elif cp != -1:
				cp -= 1
				cm -= 1
			elif cm != lm:
				cp += 1
				cm += 1

		

	#data.sort()
	co = 0

	for i in range(0,cm,2):
		ans *= (mina[i] * mina[i+1]) % mod
		ans %= mod
	for i in range(lp-1,cp,-1):
		ans *= pra[i] % mod
		ans %= mod


		
	print(ans)

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

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

Ps = [-a for a in As if a > 0]
Qs = [a for a in As if a < 0]
Zs = [ 0 for a in As if a == 0]
D  = int(1E9 + 7)

if len(Ps) == 0 and K % 2 == 1:
    Qs = [- a for a in As if a < 0]
    r = 1
    for k in range(K):
        q = - heapq.heappop(Qs)
        print(q)
        r = (r * q % D) % D
    print(r)
    exit()


heapq.heapify(Ps)
heapq.heapify(Qs)


k = 0
r = 1

while k < K:

    if len(Ps) == 0 and len(Qs) == 0:
        k = 0
        break

    if (K - k) == 1 and len(Ps) > 0:
        p = - heapq.heappop(Ps)
        r = (r * (p % D)) % D
        k += 1

    elif (K - k) == 1 and len(Qs) > 0:
        q = - heapq.heappop(Qs)
        r = (r * (q % D)) % D
        k += 1

    elif len(Qs) < 2:
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2
        r  = (r * (p % D)) % D
        k += 2

    elif len(Ps) < 2:
        q1 = - heapq.heappop(Qs)
        q2 = - heapq.heappop(Qs)
        q  = q1 * q2
        r  = (r * (q % D)) % D
        k += 2

    else: 
        p1 = - heapq.heappop(Ps)
        p2 = - heapq.heappop(Ps)
        p  = p1 * p2

        q1 = - heapq.heappop(Qs)
        q2 = - heapq.heappop(Qs)
        q  = q1 * q2

        if p > q:
            r  = (r * (p % D)) % D
            heapq.heappush(Qs, -q1)
            heapq.heappush(Qs, -q2)
        else:
            r  = (r * (q % D)) % D
            heapq.heappush(Ps, -p1)
            heapq.heappush(Ps, -p2)

        k += 2

print(r)

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