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:
		cp += 1
		cm -= 1

		if cp-1 != -1 and cm + 1 != lm:
			if pra[cp] != 0 and pra[cp-1]/-mina[cm] <= -mina[cm+1]/pra[cp]:
				cp -= 1
				cm -= 1
			else:
				cp += 1
				cm += 1
		elif cp-1 != -1:
			cp -= 1
			cm -= 1
		else:
			cp += 1
			cm += 1
		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:
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] + sorted(pos)
    neg = [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 n/c_pos[-1] < 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 itertools
mod = 1000000007
ml_number = 1
N, K = map(int, input().split())
num_list = list(map(int, input().split()))
result_list = [0] * N
t = itertools.combinations(num_list, K)
for i,group in enumerate(t):
    for j, num in enumerate(group, start=1):
        ml_number = ml_number * num
    result_list[i] = ml_number
    ml_number = 1
print(max(result_list) % mod)

Submission status: Runtime Error

Solution code:
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ans=set()
if 0 in ls:
  ans.add(0)
ls=sorted(ls, key=lambda x: -abs(x))
mul=1
for i in range(K):
  mul*=ls[i]
if mul>0:
  ans.add(mul)
else:
 #残りのプラスのものをマイナスと取り換える
 for j in range(K,N):
    if ls[j]>0:
      for k in range(K):
        if ls[K-1-k]<0:
          ans.add(mul*ls[j]//ls[K-1-k])
          break
      break
 #残りのマイナスのものをプラスと取り換える
 for j in range(K,N):
    if ls[j]<0:
      for k in range(K):
        if ls[K-1-k]>0:
          ans.add(mul*ls[j]//ls[K-1-k])
          break
      break
print(max(ans)%MOD)

Submission status: Runtime Error

Solution code:
def pf(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) %p
        if bi[i] == "1":
            res = (res*a) %p
    return res

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

pos=[]
neg=[]
for a in A:
    if a<0:
        neg.append(abs(a))
    elif a>0:
        pos.append(a)
pos=pos[::-1]

p=0
n=0
ans=[1]
mod=10**9+7
for k in range(K):
    if p<len(pos) and n<len(neg):
        if pos[p]>=neg[n]:
            ans.append(ans[-1]*pos[p]%mod)
            p+=1
        else:
            ans.append(ans[-1]*neg[n]%mod)
            n+=1
    elif p==len(pos) and n<len(neg):
        ans.append(ans[-1]*neg[n]%mod)
        n+=1
    elif n==len(neg) and p<len(pos):
        ans.append(ans[-1]*pos[p]%mod)
        p+=1
    else:
        ans.append(0)
        break

if n%2==1:
    if p<len(pos) and n<len(neg):
        temp=max(pos[p]*pf(neg[n-1],mod-2,mod),pos,neg[n]*pf(pos[p-1],mod-2,mod))
        ans.append(ans[-1]*temp)
    else:
        ABS=[]
        for a in A:
            ABS.append(abs(a))
        ABS.sort()
        ans=[1]
        for j in range(K):
            ans.append(ans[-1]*ABS[j]%mod)
        ans.append(-1*ans[-1])
print(ans[-1]%mod)

Submission status: Runtime Error

Solution code:
from functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return x2, y2, n

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
A = sorted(A, key=abs, reverse=True)
cand = []
minus = False
last_plus, last_minus = None, None
for a in A[:K]:
    cand.append(a)
    if a < 0: minus = not minus; last_minus = a
    elif a > 0: last_plus = a
ans = reduce(lambda x, y: x * y % MOD, cand)
if minus:
    ans *= modular_inverse(last_minus, MOD)
    ans %= MOD
    for a in A[K:]:
        if a >= 0: ans *= a; ans %= MOD; break
    else:
        if last_plus is not None:
            ans *= last_minus * modular_inverse(last_plus, MOD) * A[K]
            ans %= MOD
        else:
            ans = reduce(lambda x, y: x * y % MOD, A[::-1][:K])
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 %=1:
        for i in range(k):
            ans *= -li[i][0]
            ans %= mod
        print(ans)
        exit()
    else:
        for i in range(k):
            ans *= li[i][0]
            ans %0 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:
## coding: UTF-8
import sys
N, K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9 + 7

B = []
for i in range(N):
    B.append([abs(A[i]), A[i], A[i]//abs(A[i])])
#print(B)
B = sorted(B, reverse = True)
#print(B)

minus_count = 0
for i in range(K):
    if(B[i][2] == -1):
        minus_count += 1


all_minus = True
for i in range(N):
    if(B[i][2] == 1):
        all_minus = False

if(minus_count % 2 == 0):
    ans = 1
    for i in range(K):
        ans *= B[i][0]
        ans %= MOD
    print(ans)
elif(all_minus):
    C = sorted(B)
    #print(C)
    ans = 1
    for i in range(K):
        ans *= C[i][1]
        ans %= MOD
    print(ans)
else:
    #last plus -> minus
    C = B[:K]
    #print(C)
    for i in range(K-1, -1,-1):
        if(C[i][2] == 1):
            last_plus = C[i]
            del C[i]
            break
    search_minus = True
    index = K
    while search_minus:
        if(B[index][2] == -1):
            search_minus = False
            first_minus = B[index]
            C.append(first_minus)
        index += 1
    #print(first_minus, last_plus, C)
    if(search_minus):
        A_ans = -1
        A_kiroku = sys.maxsize
    else:
        A_ans = 1
        A_kiroku = last_plus[0] / first_minus[0] #割った数（これが小さい方が積が大きいはず）
        for i in range(K):
            A_ans *= C[i][1]
            A_ans %= MOD

    C = B[:K]    
    for i in range(K-1, -1,-1):
        if(C[i][2] == -1):
            last_minus = C[i]
            del C[i]
            break
    search_plus = True
    index = K
    while search_plus:
        if(B[index][2] == 1):
            search_plus = False
            first_plus = B[index]
            C.append(first_plus)
        index += 1
    #print(first_minus, last_plus, C)
    if(search_plus):
        B_ans = -1
        B_kiroku = sys.maxsize
    else:
        B_ans = 1
        B_kiroku = last_minus[0] / first_plus[0]
        for i in range(K):
            B_ans *= C[i][1]
            B_ans %= MOD
    if(search_minus and search_plus):
        C = sorted(B)
        #print(C)
        ans = 1
        for i in range(K):
            ans *= C[i][1]
            ans %= MOD
        print(ans)
    #print(A_ans, B_ans)
    #print(last_plus, first_minus, A_kiroku)
    #print(last_minus, first_plus, B_kiroku)
    else:
        if(A_kiroku > B_kiroku):
            print(B_ans)
        else:
            print(A_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))
p = []
n = []
for i in range(K):
    a = A[i]
    if a>0:
        p.append(a)
    elif a<0:
        n.append(a)

if len(n)%2==0:
    ans = 1
    for a in n:
        ans *= a
        ans %= mod
    for a in p:
        ans *= a
        ans %= mod
else:
    ap = 0
    an = 0
    for i in range(K,N):
        if ap==0 and A[i]>0:
            ap = A[i]
        if an==0 and A[i]<0:
            an = -A[i]
    if len(p)>0:
        ap_ = p[-1]
    else:
        ap_ = 1
    an_ = -n[-1]
    if ap==0 and an==0:
        ans = 0
    else:
        if ap*ap_>an*an_:
            n.pop()
            p.append(ap)
        else:
            p.pop()
            n.append(-an)
        ans = 1
        for a in n:
            ans *= a
            ans %= mod
        for a in p:
            ans *= a
            ans %= mod

if len(p)+len(n)<K:
    ans = 0
if len(p)==0 and len(n)==K and K%2==1:
    An = [A[i] for i in range(N) if A[i]<0]
    An.sort()
    An = An[::-1]
    ans = 1
    for i in range(K):
        ans *= An[i]
        ans %= mod
    if A[-1]==0:
        ans = 0
if N==K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
print(ans%mod)

Submission status: Runtime Error

Solution code:

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

  plus = []
  minus = []

  for n in input().split():
    n = int(n)
    if n >= 0:
      plus.append(n)
    else:
      minus.append(n)

  mod = 10 ** 9 + 7

  if len(plus) == 0 and k % 2 == 1:
    minus.sort(reverse=True)
    ans = 1
    for i in range(k):
      ans *= minus[i]

    print(ans % mod)
    return


  plus.sort(reverse = True)
  minus.sort()

  pn = min(len(plus), k)
  mn = k - pn

  if len(plus) >= 2 and len(minus) >= 2:
    while pn >= 2:
      if plus[pn - 2] * plus[pn - 1] > minus[mn] * minus[mn + 1]:
        break

      pn -= 2
      mn += 2

  ans = 1
  for i in range(pn):
    ans = (ans * plus[i]) % mod

  for i in range(mn):
    ans = ans * minus[i]

  print(ans % mod)


main()

Submission status: Runtime Error

Solution code:
from collections import deque
# N = int(input())
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
A_p = []
A_n = []
for a in A:
  if a >= 0:
    A_p.append(a)
  else:
    A_n.append(-a)

A_p.sort(reverse=True)
A_n.sort(reverse=True)
A_p = deque(A_p)
A_n = deque(A_n)

p_top = 0
n_top = 0
ans_p = deque([])
ans_n = deque([])
for i in range(K):
  if len(A_p) == 0:
    ans_n.append(A_n.popleft())
  elif len(A_n) == 0:
    ans_p.append(A_p.popleft())
  elif A_p[0] >= A_n[0]:
    ans_p.append(A_p.popleft())
  else:
    ans_n.append(A_n.popleft())
if len(ans_n) % 2 == 1:
  if len(ans_p) == 0 and len(A_p) > 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_n) == 0 and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
  elif len(ans_p) > 0 and len(ans_n) > 0 and ans_p[-1] >= ans_n[-1] and len(A_p) > 0 and A_p[0] != 0:
    ans_n.pop()
    ans_p.append(A_p.popleft())
  elif len(ans_p) > 0 and len(ans_n) > 0 and ans_p[-1] < ans_n[-1] and len(A_n) > 0:
    ans_p.pop()
    ans_n.append(A_n.popleft())
ans = 1
for a in ans_p:
  ans = (a * ans) % MOD
for a in ans_n:
  ans = (a * ans) % MOD
if ans != 0 and len(ans_n) % 2 == 1:
  ans = 1
  A = [a for a in A if a < 0]
  A.sort(reverse=True)
  for i in range(K):
    ans = (ans * A[i]) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
z=-1
p=-1
for i in range(n):
    if a[i]==0:
        z=i
    elif a[i]>0:
        p=i
        break
ans=1
mod=10**9+7
if p==0:
    ans=1
    for i in range(k):
        ans*=a[i]
        ans%=mod
    print(ans%mod)
elif p==-1:
    if k%2==0:
        for i in range(k):
            ans*=a[i]		
            ans%=mod
        print(ans%mod)
    elif z!=-1:
        print(0)
    else:
        for i in range(k):
            ans*=a[n-1-i]
            ans%=mod
        print(ans%mod)
else:
    if z==-1:
        res=0
        for i in range(0,p+1,2):
            if n-p<k-i or p<i:
                break
            for j in range(k-i):
                ans*=a[p+j]
            for j in range(i):
                ans*=a[j]
            if res<ans:
                res=ans
            ans=1
        print(res%mod)
    else:
        for i in range(0,z+1,2):
            if n-p<k-i or p<i:
                break
            for j in range(k-i):
                ans*=a[p+j]
            for j in range(i):
                ans*=a[j]
            if res<ans:
                res=ans
            ans=1
        print(res%mod)

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] + sorted(pos)
    neg = [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 n/c_pos[-1] > 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 sys
input=sys.stdin.readline
ans=1
n,k=map(int,input().split())
a=sorted(map(int,input().split()))
plus=[]
zero=[]
minus=[]
for i in a:
    if i>0:
        plus.append(i)
    elif i==0:
        zero.append(i)
    else:
        minus.append(i)

if k==1:
    if len(plus)>0:
        print(plus[-1])
        exit()
    elif len(zero)>0:
        print(0)
        exit()
    else:
        print(minus[-1]%(10**9+7))
        exit()
        
elif len(plus)+len(minus)<k:
    print(0)
    exit()

else:
    pm=plus+minus
    pm=sorted(pm,key=lambda x:-abs(x))
    minus_num=0
    plus_num=0
    last_minus_num=0
    last_plus_num=0
    numbers=[]
    for i in range(k):
        p=pm[i]
        if p<0:
            minus_num+=1
            last_minus_num=p
        if p>0:
            plus_num+=1
            last_plus_num=p
        numbers.append(p)
    if minus_num%2!=0:
        switch=0
        if last_plus_num!=0:
            basyo=pm.index(last_plus_num)
        else:
            if len(plus)==0:
                numbers=pm[:-k-1:-1]
                for i in numbers:
                    gomi,ans=divmod(ans*i,1000000007)
                print(ans)
                exit()
            else:
                numbers.remove(last_minus_num)
                numbers.append(max(plus))
            ans=1
            for i in numbers:
                gomi,ans=divmod(ans*i,1000000007)
            print(ans)
            exit()
        for i in pm[basyo+1:]:
            if i>0:
                numbers.append(i)
                numbers.remove(last_minus_num)
                switch=1
                break
        if switch==0:
            if plus_num==1:
                if len(zero)>1:
                    print(0)
                    exit()
                else:
                    numbers=pm[:-k-1:-1]
                    for i in numbers:
                        gomi,ans=divmod(ans*i,1000000007)
                    print(ans)
                    exit()
            m_basyo=pm.index(last_minus_num)
            for i in pm[m_basyo+1:]:
                if i<0:
                    numbers.append(i)
                    numbers.remove(last_plus_num)

for i in numbers:
    gomi,ans=divmod(ans*i,1000000007)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N,K = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype='int64')
    plus = A[np.where(A > 0)]
    minus = A[np.where(A < 0)] * -1
    
    count_p = np.count_nonzero(A > 0)
    count_m = np.count_nonzero(A < 0)
    count_zero = np.count_nonzero(A == 0)

    def p(plus, minus, K):
        plus = np.sort(plus)[::-1]
        minus = np.sort(minus)[::-1]

        if K % 2 == 0:
            r = 1
        else:
            r = plus[0]
            plus = plus[1:]
            K -= 1
        
        p = 0
        m = 0
        while K > 0:
            if len(plus) <= p+1:
                r *= int(minus[m]*minus[m+1])
                m+=2
                K -= 2
            elif len(minus) <= m+1:
                r *= int(plus[p])
                p+=1
                K -= 1
            elif plus[p]*plus[p+1] > minus[m]*minus[m+1]:
                r *= int(plus[p])
                p+=1
                K -= 1
            else:
                r *= int(minus[m]*minus[m+1])
                m+=2
                K -= 2
        return (r+(10**9+7))%(10**9+7)
            
    def m(plus, minus, K):
        plus = np.sort(plus)
        minus = np.sort(minus)

        if K % 2 == 0:
            r = 1
        else:
            r = minus[0]
            minus = minus[1:]
            K -= 1

        p = 0
        m = 0
        while K > 0:
            if len(plus) <= p+1:
                r *= int(minus[m]*minus[m+1])
                m+=2
                K -= 2
            elif len(minus) <= m+1:
                r *= int(plus[p])
                p+=1
                K -= 1
            elif plus[p]*plus[p+1] < minus[m]*minus[m+1]:
                r *= int(plus[p])
                p+=1
                K -= 1
            else:
                r *= int(minus[m]*minus[m+1])
                m+=2
                K -= 2
        return (-r+(10**9+7))%(10**9+7)
            
    
    if N-K == 0:
        if count_zero > 0:
            print(0)
            return
        else:
            if count_m % 2 == 1:
                #minus
                print(m(plus, minus, K))
                return
            else:
                #plus
                print(p(plus,minus,K))
                return
    else:
        if count_p > 0:
            if count_zero <= N-K:
                #plus
                print(p(plus,minus,K))
                return
            else:
                print(0)
                return
        else:
            if count_zero > 0:
                print(0)
                return
            else:
                #minus
                print(m(plus, minus, K))
                return

main()

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==0 and len(Am)%2==0 or len(Ap)==0 and K%2:
    c=1
    while K and (Am or Ap) :
        if Am and Ap:
            if Am[0]<Ap[0]:
                c*=Am.popleft()
            else:
                c*=Ap.popleft()
        elif Am:
            c*=Am.popleft()
        elif Ap:
            c*=Ap.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 numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if sum([1 for a in a_list if np.sign(a)==-1])==k:
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
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_min_big = max([num for num in a_list[:k] if np.sign(num)==-1])
        positive_min_big = min([num for num in a_list[:k] if np.sign(num)!=-1])
        negative_max_small = min([num for num in a_list[k:] if np.sign(num)==-1])
        positive_max_small = max([num for num in a_list[k:] if np.sign(num)!=-1])
        if positive_max_small/negative_min_big < negative_max_small/positive_min_big:
            remove = negative_min_big
            add = positive_max_small
        else:
            remove = positive_min_big
            add = negative_max_small
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:
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
cnt_plus=0
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev_plus
prev_minus=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
    prev_plus=tmp
  if flag==-1:
    if cnt==0:
      prev_minus=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev_minus)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if (k%2==1 and cnt_plus==0) or (cand_plus==0 and cand_minus==0):
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if prev_plus*cand_plus>=prev_minus*cand_minus:
      pick.append(cand_plus)
    else:
      pick=pick[:-1]
      pick.append(prev_minus)
      pick.append(cand_minus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)

Submission status: Runtime Error

Solution code:
        m.append(-aa)
        if cntp+cntm<K:
            cntm+=1
    
    if aa==0:
        zero=True

ans=1

if cntm%2==1:
    if cntm+1<=len(m) and cntm+1<=K and cntp+1<=len(p) and cntp+1<=K:
        if p[cntp]*p[cntp-1]>m[cntm]*m[cntm-1]:
            cntp+=1
            cntm-=1
        else:
            cntp+=1
            cntm-=1
    elif cntm+1<=len(m) and cntm+1<=K:
        cntm+=1
        cntp-=1
    elif cntp+1<=len(p) and cntp+1<=K:
        cntp+=1
        cntm-=1
    else:
        if zero:
            print(0)
            exit(0)
        
        for i in range(K):
            ans*=a[N-i-1]
            ans=(ans+mod*mod)%mod
        
        print(ans)
        exit(0)

for i in range(cntm):
    ans*=m[i]
    ans%=mod
for i in range(cntp):
    ans*=p[i]
    ans%=mod

print(ans)