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:
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 != -1:
				cp -= 1
				cm -= 1
			elif cm + 1 != 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:
def mult(lis):
  ret=1
  for i in lis:
    ret*=i
    if ret<0 or ret>1000000007:
      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(a)==k:
  ch.extend(a)
elif 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)
  while k>0:
    inp=a.pop(0)
    if inp<0:
      if k==1 and pls==True:
        continue
      pls^=1
    ch.append(inp)
    k-=1
print(mult(ch))

Submission status: Runtime Error

Solution code:
import sys
n,k=map(int,input().split())
a = list(map(int,input().split()))
plus = sorted([i for i in a if i > 0],reverse=True)
minus = sorted([i for i in a if i < 0])
b = []
p = 0
m = 0
MOD = 10**9 + 7

while(True):
    if(len(plus) != 0 and len(minus) != 0):
        if(plus[p] >= -minus[m]):
            b.append(plus[p])
            p += 1
        else:
            b.append(minus[m])
            m += 1
    if(p == len(plus)):
        for i in range(k-p-m):
            b.append(minus[i+m])
        break
    if(m == len(minus)):
        for i in range(k-p-m):
            b.append(plus[i+p])
        break
    if(p+m == k):
        if(m % 2 == 1):
            if(minus[m]*minus[m-1] > plus[p]*plus[p-1]):
                b[b.index(plus[p-1])] = minus[m]
            else:
                b[b.index(minus[m-1])] = plus[p]
        break
if(len([i for i in b if i<0]) %2 != 0):
    if(0 in a):
        print(0)
        sys.exit()
    else:
        ans = 1
        for i in a:
            if(i < 0):
                i *= -1
        a = sorted(a,reverse=True)
        for i in range(k):
            ans = ans*a[i]
        #ans = -((-ans) % -MOD)
        ans = (ans % MOD)
        print(ans)
        sys.exit()
ans = 1
for i in b:
    ans = ans*i % MOD
print(ans)

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)
        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 math
ln,k=list(map(int,input().split()))
l=list(map(int,input().split()))
lul = 10**9 + 7

pos = []
neg = set()
temp = []
for i in range(ln):
	if l[i]<0:
		l.append(-1*l[i])
		temp.append(-1*l[i])
		neg.add(i)
	else:
		l.append(l[i])
l.sort(); l=l[::-1]
v = 1; ct = 0
p = -1; n = -1
ans = []
temp.sort()
for i in range(k):
	# v = (v*)%lul
	ans.append(i)
	if i in neg:
		ct+=1
		p = max(p,i)
	else:
		n = min(n,i)

if ct%2!=0:
	for i in range(k,ln):
		if i in neg and p!=-1:
			ans.remove(p)
			ans.append(i)
			ct+=1
			break
		elif i not in neg:
			ans.remove(n)
			ans.append(i)
			ct-=1
			break

if ct%2!=0:
	v = 1
	for i in range(k):
		v = (v*temp[i])%lul
	v = lul-v
else:
	v = 1
	for i in ans:
		v = (v*l[i])%lul
print(v)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left,bisect_right
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
pi=1
ni=1
ans=1
for _ in range(k//2):
  if a[ni]*a[ni+1]>a[-pi]*a[-pi-1]:
    ans=ans*a[ni]*a[ni+1]%p
    ni+=2
  else:
    ans=ans*a[-pi]*a[-pi-1]%p
    pi+=2
if k%2==1:
  ans=ans*a[-pi]%p
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
		if len(p_list) >= K:
			if K % 2 == 1:
				values_left = p_list.pop()
				p_count = K - 1
			else:
				p_count = K
			
			for i in range(0, p_count, 2):
				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)
			
			print(p_count)
			
			if p_count % 2 == 0:
				values_left = p_list.pop()
			
			for i in range(0, p_count, 2):
				v1 = p_list.pop()
				v2 = p_list.pop()
				values_pair.append((v1 * v2, v1, v2))
			
			for i in range(0, K - len(values_pair), 2):
				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:


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, k = map(int, input().split())
a = list( map(int, input().split()))
p = 10**9+7

a.sort()

from bisect import bisect_left, bisect_right
zerostart = bisect_left(a, 0)
posstart = bisect_right(a, 0)

aneg = a[:zerostart]
cntzero = posstart - zerostart
apos = a[posstart:]

cntneg = len(aneg)
cntpos = len(apos)

# 答えが0になる時
if k > n-cntzero:
    print(0)
    exit()

# 答えが正になる時
if k <= cntpos or (k%2==0 and  k <= (cntneg//2)*2 + cntpos) or (k%2==1 and cntpos%2==1 and k <= (cntneg//2)*2 + cntpos-1):
    pos_pair_mix=[]

    apos.sort(reverse=True)
    for i in range(cntpos//2):
        pos_pair_mix.append((apos[2*i]*apos[2*i+1],+1,2*i))

    for i in range(cntneg//2):
        pos_pair_mix.append((aneg[2*i]*aneg[2*i+1],-1,2*i))

    pos_pair_mix.sort(key=lambda x:x[0],reverse=True)

    ans = 1
    last_apos=0

    for i in range(k//2):
        ans*=pos_pair_mix[i][0]%p
        ans%=p
        if pos_pair_mix[i][1]==1:
            i_last_apos = pos_pair_mix[i][2]+2

    if k%2==0:
        print(ans%p)
        exit()
    else:
        print((ans*apos[i_last_apos])%p)
        exit()

# 答えが負になる時
a.sort(key=lambda x:abs(x) )

ans = 1
for i in range(k):
    ans*=a[i]
    ans%=p

print(ans%p)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
ans=1
p=[]
n=[]
for i in range(N):
    if A[i]<0:
        n.append(A[i])
    else:
        p.append(A[i])
p.sort(reverse=True)
n.sort()
numplus=len(p)
if N==K:
    for i in range(N):
        ans=(ans*A[i])%MOD
elif numplus==0 and K%2==1:
    for i in range(1,K+1):
        ans=(ans*n[i*(-1)])%MOD
else:
    minus=0
    A.sort(reverse=True,key=lambda x:abs(x))
    for i in range(K):
        ans=(ans*A[i])%MOD
        if A[i]<0:
            minus+=1
    if minus%2==1:
        B=A[:K]
        for i in range(K-1,-1,-1):
            if B[i]<0:
                waru=B[i]
                break
        for i in range(K,N):
            if A[i]>=0:
                kakeru=A[i]
                break
        ans=(ans*A[i]*pow(B[i],MOD-2,MOD))%MOD
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    if k %2 ==1:
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans *= li[n-i][0]
            ans %= mod
        print(ans)
        exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    if n-k-1 >= 0:
        for i in range(n-k-1, -1, -1):
            if li[i][1] > 0:
                plus = li[i][0]
                p = i
                p1 = False
                break
        for i in range(n-k-1, -1, -1):
            if li[i][1] < 0:
                mini = li[i][0]
                m = i
                m1 = False
                break
    ans1 = 1
    ans2 = 1
    if (not P1) and (not m1):
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if (not p1) and (not M1):
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans2 *= li[i][0]
            ans2 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if (not p1) and (not P1) and (not M1) and (not m1):
        if mini/Plus > plus/Mini:
            print(ans1)
        else:
            print(ans2)
    elif (not p1) and (not M1):
        print(ans2)
    elif (not m1) and (not P1):
        print(ans1)
    else:
        ans = 1
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)

Submission status: Runtime Error

Solution code:
def funct(x, k):
	x.sort()
	neg = []
	pos = []
	for i in range(len(x)):
		if(x[i] < 0):
			neg.append(abs(x[i]))
		else:
			pos = x[i :]
			break
	
	pdt = 1
	pos.sort(reverse = True)
	neg.sort(reverse = True)
	if(pos == []):
		if(k % 2 == 1):
			for i in range(k):
				pdt *= neg[-i - 1]
		else:
			for i in range(k):
				pdt *= neg[i]
		return pdt * -1	
	
	if(neg == []):
		for i in range(k):
			pdt *= pos[i]
		return pdt 
		
	pos.insert(0, 1)
	neg.insert(0, 1)
	for i in range(1, len(pos)):
		pos[i] *= pos[i - 1]
	for i in range(1, len(neg)):
		neg[i] *= neg[i - 1]
	
	m = -99999999
	i = 0
	while(2 * i < len(pos) and (k - 2 * i) < len(pos)):
		m = max(m, neg[2 * i] * pos[k - 2 * i])
		# print(m)
		i += 1
	
	return m
	
n, k = map(int, input().split())
x = [int(x) for x in input().split()]
print(funct(x, k) % (10 **9 + 7))

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n, k = nm()
pos = []
neg = []
zero = 0
ans = 1
MOD = 10**9 + 7

for a in nl():
    if a == 0:
        zero += 1
    elif a > 0:
        pos.append(a)
    else:
        neg.append(a)

if zero >= (n-k+1) or ( ( len(pos) + len(neg) == k ) and ( len(neg) % 2 == 1 ) ):
    ans = 0
elif len(pos) == 0 and k % 2 == 1:
    neg.sort()
    for _ in range(k):
        ans *= neg.pop()
        ans %= MOD
else:
    pos = [0,0] + sorted(pos)
    neg = [0,0] + sorted(neg, reverse=True) #absが大きい順にpopで取れるようにする
    c_pos = []
    c_neg = []
    for _ in range(k):
        if pos[-1] <= -neg[-1] or pos[-1] == 0: #negのabsの方が大きい
            c_neg.append(neg.pop())
        else:
            c_pos.append(pos.pop())
    if len(c_neg) % 2 == 1:
        p = pos.pop()
        n = neg.pop()
        if p == 0 or abs(n/c_pos[-1]) > abs(p/c_neg[-1]):
            c_pos.pop()
            c_neg.append(n)
        else:
            c_neg.pop()
            c_pos.append(p)
    for c in c_neg:
        ans *= -c
        ans %= MOD
    for c in c_pos:
        ans *= c
        ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import math
n,k=list(map(int,input().split()))
l=list(map(int,input().split()))
lul = 10**9 + 7

pos = []
neg = set()
temp = []
for i in range(n):
	if l[i]<0:
		l.append(-1*l[i])
		temp.append(-1*l[i])
		neg.add(i)
	else:
		l.append(l[i])
l.sort(); l=l[::-1]
v = 1; ct = 0
p = -1; n = -1
ans = []
temp.sort()
for i in range(k):
	# v = (v*)%lul
	ans.append(i)
	if i in neg:
		ct+=1
		p = max(p,i)
	else:
		n = min(n,i)

if ct%2!=0:
	for i in range(k,n):
		if i in neg and p!=-1:
			ans.remove(p)
			ans.append(i)
			ct+=1
			break
		elif i not in neg:
			ans.remove(n)
			ans.append(i)
			ct-=1
			break
v = 1
for i in ans:
	v = (v*l[i])%lul
if ct%2!=0:
	v = 1
	for i in range(k):
		v = (v*temp[i])%lul
	v = lul-v
print(v)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

n, k = nm()
pos = []
neg = []
zero = 0
ans = 1
MOD = 10**9 + 7

for a in nl():
    if a == 0:
        zero += 1
    elif a > 0:
        pos.append(a)
    else:
        neg.append(a)

if zero >= (n-k+1) or ( ( len(pos) + len(neg) == k ) and ( len(neg) % 2 == 1 ) ):
    ans = 0
elif len(pos) == 0 and k % 2 == 1:
    neg.sort()
    for _ in range(k):
        ans *= neg.pop()
        ans %= MOD
else:
    pos = [0,0] + sorted(pos)
    neg = [0,0] + sorted(neg, reverse=True) #absが大きい順にpopで取れるようにする
    c_pos = []
    c_neg = []
    for _ in range(k):
        if pos[-1] <= - neg[-1]: #negのabsの方が大きい
            c_neg.append(neg.pop())
        else:
            c_pos.append(pos.pop())
    if len(c_neg) % 2 == 1:
        p = pos.pop()
        n = neg.pop()
        if p == 0 or abs(n/c_pos[-1]) > abs(p/c_neg[-1]):
            c_pos.pop()
            c_neg.append(n)
        else:
            c_neg.pop()
            c_pos.append(p)
    for c in c_neg:
        ans *= -c
        ans %= MOD
    for c in c_pos:
        ans *= c
        ans %= MOD
print(ans)

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 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:
            idx = K - 1
            while True:
                if A[idx] < 0:
                    break
                idx -= 1
            for i in range(idx):
                ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
            ans *= A[K]
            ans %= mod
            for i in range(idx + 1, K):
                ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
        elif len([v for v in A[K:] if v <= 0]) == N - K:
            idx = K - 1
            while True:
                if A[idx] > 0:
                    break
                idx -= 1
            for i in range(idx):
                ans *= A[i]
                if abs(ans) > mod:
                    ans %= mod
            ans *= A[K]
            ans %= mod
            for i in range(idx + 1, K):
                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:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            else:
                if maxnega == 0:
                    maxnega = a[i]


        if abs(minposi*maxposi) < abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)
        else:
            pp
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)


print(ans % 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=-c
        c%=mod
    #print("unko")

else:
    #print(unko)
    c=1
    h=0
    w=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)
        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, 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
            multiply_left = list_a[left] * list_a[left+1]
            multiply_right = list_a[right] * list_a[right-1]
            flag_left = True

            while(K>0):
                if(K>1):
                    K -= 2

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

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

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

            print(multiplies)