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
input = sys.stdin.buffer.readline
MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, (input().split())))
ap = []
neg_cnt = 0
zero_cnt = 0
for a in A:
    if a<0:
        ap.append((-a, 1))     # sortで先に来るようマイナスを1にする
        neg_cnt += 1
    elif a==0:
        ap.append((0, 0))
        zero_cnt += 1
    else:
        ap.append((a, -1))
ap.sort(reverse=True)
# print(ap)
ans = 1
if neg_cnt==N and K%2:      # 全てが負で奇数個選ぶので、答えは負
    for i in range(K):
        ans *= ap[N-i-1][0] * ap[N-i-1][1] * -1
        ans %= MOD
else:                       # 答えは正
    neg_num = 0
    for i in range(K):
        if ap[i][1] == 1:
            neg_num += 1
    if neg_num % 2:     # 負の数が奇数だったら、-1して偶数回にし、正が出るまで見る
        neg_num -= 1
        K += 1
    i = 0
    while i < K:
    # for i in range(K):
        if ap[i][1] == 1:  # 負の数だったら、neg_num回まで
            if neg_num == 0:
                i += 1
                continue
            else:
                neg_num -= 1
        ans *= ap[i][0] * ap[i][1] * -1
        ans %= MOD
        i += 1

print(ans)

Submission status: Runtime Error

Solution code:

n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
m=[]
p=[]
for i in range(n):
    if a[i]<0:
        m.append(a[i])
    else:
        p.append(a[i])
m.sort(reverse=True)
p.sort()
ans=1

if len(m)==n and k%2==1:
    for i in range(k):
        ans*=m[i]
elif k==1:
    ans=p[-1]

else:
    cnt=0
    for i in range(k-2):
        if len(m)==0:
            ans*=p.pop()
        elif len(p)==0:
            ans*=m.pop()
            cnt+=1
        else:
            if abs(m[-1])<p[-1]:
                ans*=p.pop()
            else:
                ans*=m.pop()
        ans%=mod
    if cnt%2==0:
        if len(p)>1 and len(m)>1:
            ans*=max(p[-1]*p[-2],m[-1]*m[-2])
        elif len(p)<2:
            ans*=m[-1]*m[-2]
        else:
            ans*=p[-1]*p[-2]
    else:
        ans*=p[-1]*m[-1]

print(ans%mod)

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]*minus[midx+1]
    elif midx<len(minus):
        nexmin=minus[midx]
    else:
        nexmin=-1


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

    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()))

A.sort(reverse=True)

P = []
M = []
Ans = []
p = 0
m = 0

for i in range(N):
    if 0 <= A[i]:
        P.append(A[i])
    else:
        M.append(A[i])

if K % 2 == 1 and len(P) != 0:
    Ans.append(P[p])
    p += 1

while len(Ans) < K:

    #Mのストックがもうない時
    if m+1 >= len(M):
        Ans.append(P[p])
        if p+1 >= len(P):
            break
        Ans.append(P[p + 1])
        p += 2
    elif p+1 >= len(P):
        Ans.append(M[m])
        if m+1 >= len(M):
            break
        Ans.append(M[m + 1])
        m += 2
    else:
        if P[p]*P[p+1] < M[m]*M[m+1]:
            Ans.append(M[m])
            Ans.append(M[m+1])
            m += 2
        else:
            Ans.append(P[p])
            Ans.append(P[p + 1])
            p += 2

answer = 1
for i in range(K):
    answer = (answer * Ans[i]) % 1000000007

print(answer)

Submission status: Runtime Error

Solution code:
def maxProductSubarrayOfSizeK(A, n, k):  
    A.sort()  
    product = 1
    if (A[n - 1] == 0 and (k & 1)): 
        return 0
    if (A[n - 1] <= 0 and (k & 1)) : 
        for i in range(n - 1, n - k + 1, -1): 
            product *= A[i] 
        return product  
    i = 0
    j = n - 1
    if (k & 1): 
        product *= A[j] 
        j-= 1
        k-=1
    k >>= 1
    for itr in range( k) : 
        left_product = A[i] * A[i + 1] 
        right_product = A[j] * A[j - 1] 
        if (left_product > right_product) : 
            product *= left_product 
            i += 2    
        else : 
            product *= right_product 
            j -= 2
    M=(10**9+7)
    return product/M

N=list(map(int,input().split()))
b=N[1]
c=list(map(int,input().split()))
print(maxProductSubarrayOfSizeK(c,len(c),b))

Submission status: Runtime Error

Solution code:
N=10**9+7
n , k = map(int, input().split())
x = list(map(int,input().split()))
posi=[]
nega=[]

p=0
ne=0
z=0

for i in range(n):
    if x[i]<0:
        nega.append(x[i]*(-1))
        ne+=1
    elif x[i]>0:
        posi.append(x[i])
        p+=1
    else:
        z+=1


if k%2==1 and p==0:
    if z>=1:
        print('0')
        exit()
    else:
        ans=1
        nega.sort()
        for i in range(k):
            ans*=nega[i]
            ans%=N
        print(ans*(-1)%N)
else:
    ab=nega+posi
    ab.sort(reverse=True)
    ans=1
    for i in range(k):
        ans*=ab[i]
        ans%=N
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

mod = 10**9 + 7

A = sorted(A, key=lambda x:-abs(x))

s = 1
ans = 1
for a in A[:K]:
  s *= np.sign(a)
  ans *= a
  ans %= mod
if s < 0:
  for a in A[K-1::-1]:
    if a > 0:
      x = a
  for b in A[K:]:
    if b < 0:
      y = b
  for c in A[K-1::-1]:
    if c < 0:
      z = c
  for d in A[K:]:
    if d > 0:
      w = d
  if (c == 0) or ((a * c != 0) and (b / a >= d / c)):
    ans *= b
    ans %= mod
    ans *= pow(a, -1, mod=mod)
    ans %= mod
  else:
    ans *= d
    ans %= mod
    ans *= pow(c, -1, mod=mod)
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
def findMaxProduct(arr, n, k) :
    MaxProduct = 1
    for i in range(0, k) :
        MaxProduct = MaxProduct * arr[i]
    prev_product = MaxProduct
    for i in range(1, n - k + 1) :
        curr_product = (prev_product // arr[i-1]) * arr[i+k-1]
        MaxProduct = max(MaxProduct, curr_product)
        prev_product = curr_product
    return MaxProduct


mod = 10 ** 9 + 7
n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
ans = findMaxProduct(arr,n,k)
print(ans % mod)

Submission status: Runtime Error

Solution code:
from collections import Counter, deque

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

MOD = 10 ** 9 + 7

c = Counter()
for a in A:
    if a == 0:
        c['0'] += 1
    elif a < 0:
        c['-'] += 1
    else:
        c['+'] += 1

if c['-'] + c['+'] < K:
    print(0)
elif (c['-'] == N and K % 2 == 1) or (N == K and c['-'] % 2 == 1):
    def f(x):
        if x == 0:
            return 10 ** 9
        else:
            return abs(x)


    A = sorted(A, key=f)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD

    print(ans)
else:
    A = sorted(A, key=lambda x: abs(x), reverse=True)
    plus = deque()
    minus = deque()

    for i in range(K):
        if A[i] >= 0:
            plus.append(A[i])
        else:
            minus.append(A[i])

    if len(minus) % 2 == 1:
        p = None
        m = None
        for i in range(K, N):
            if A[i] >= 0 and p is None:
                p = A[i]
            if A[i] < 0 and m is None:
                m = A[i]
            if p is not None and m is not None:
                break
        if m is None and p is None:
            pass
        if m is None and p is not None:
            minus.pop()
            plus.append(p)
        elif m is not None and p is None:
            plus.pop()
            minus.append(m)
        elif minus[-1] * m > plus[-1] * p:
            plus.pop()
            minus.append(m)
        else:
            minus.pop()
            plus.append(p)

    ans = 1
    while plus:
        ans *= plus.popleft()
        ans %= MOD
    while minus:
        ans *= minus.popleft()
        ans %= MOD

    print(ans)

Submission status: Runtime Error

Solution code:
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
A = sorted(A, reverse = True, key = lambda x:abs(x))

cnt = 0
for i in A[:K]:
  if i < 0:
    cnt += 1
    
if cnt % 2 == 0:
 
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans = ans%(10**9+7)
  print(ans)
else:
  if all([i <= 0 for i in A]):
    if K % 2 == 0:
      for i in range(K):
        ans *= A[i]
        ans = ans%(10**9+7)
    if K % 2 == 1:
      A = sorted(A, key = lambda x:abs(x))
      for i in range(K):
        ans *= A[i]
        ans = ans%(10**9+7)
    print(ans)

Submission status: Runtime Error

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

ps = []
ns = []
zs = []
for i in range(n):
  if a[i] > 0:
    ps.append(a[i])
  elif a[i] < 0:
    ns.append(a[i])
  else:
    zs.append(a[i])
    
if len(ps) + len(ns) < k:
  print(0)
elif len(ps) == 0:
  ans = 1
  if k % 2 == 0:
    ns = sorted(ns)
    for i in range(k):
      ans = ans * ns[i] % mod
  elif len(zs) > 0:
    print(0)
  else:
    ns = sorted(ns, reverse=True)
    for i in range(k):
      ans = ans * ns[i] % mod
  print(ans)
else:
  ans = 1
  ps = sorted(ps, reverse=True)
  ns = sorted(ns)
  if k % 2 == 0:
    pp = []
    for i in range(0,min(k, len(ps)), 2):
      try:
        pp.append(ps[i] * ps[i+1])
      except:
        pass
  else:
    pp = []
    ans = ps[0]
    for i in range(1,min(k, len(ps)), 2):
      try:
        pp.append(ps[i] * ps[i+1])
      except:
        pass
  np = []
  for i in range(0,min(k, len(ps)), 2):
    try:
      np.append(ns[i] * ns[i+1])
    except:
      pass
  pnp = sorted(pp + np, reverse=True)
  for i in range(k//2):
    ans = ans * pnp[i] % mod
  print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
B = [0]*N
C = [1]*N
neg = 0
for i in range(N):
    B[i]=abs(A[i])
    if A[i]<0:
        C[i]=-1
        neg += 1
Neg = [0]*neg
Pos = [0]*(N-neg)
cneg = cpos = 0
for i in range(N):
    if A[i]<0:
        Neg[cneg] = A[i]
        cneg += 1
    elif A[i]>0:
        Pos[cpos] = A[i]
        cpos += 1

Neg.sort(reverse =True)
Pos.sort(reverse=True)
print(Neg,Pos)

Ans = 1
mod = 10**9 + 7
flag = 0
if neg == N and K%2 == 1:
    for i in range(K):
        Ans = (Ans*Neg[i])%mod
    flag = 1
elif K==N:
    for i in range(K):
        Ans = (Ans*A[i])%mod
    flag = 1
j=1


while j*2<= K:
    if flag == 1:
        break
    if cneg>1 and cpos>1:
        if Neg[cneg-1]*Neg[cneg-2] > Pos[0]*Pos[1]:
            S = Neg[cneg-1]*Neg[cneg-2]
            Ans = (Ans*S)%mod
            Neg.pop(-1)
            Neg.pop(-1)
            cneg -= 2
        else:
            S = Pos[0]*Pos[1]
            Ans = (Ans*S)%mod
            S.pop(0)
            S.pop(0)
            cpos -= 2
    elif cneg>1 and cpos<2:
        S = Neg[cneg-1]*Neg[cneg-2]
        Ans = (Ans*S)%mod
        Neg.pop(-1)
        Neg.pop(-1)
        cneg -= 2
    elif cneg<2 and cpos>1:
        S = Pos[0]*Pos[1]
        Ans = (Ans*S)%mod
        Pos.pop(0)
        Pos.pop(0)
        cpos -= 2
    elif cneg<2 and cpos<2:
        Ans = 0
    j += 1

K = K - 2*j
if K==1 and flag == 0:
    Ans = (Ans*Pos[0])%mod
    print(Ans)
else:
    print(Ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    m=[]
    p=[]
    z=False
    for i in range(N):
        if A[i]<0:
            m.append(A[i])
        elif A[i]==0:
            z=True
        else:
            p.append(A[i])
    p.sort(reverse=True)
    m.sort()
    if N==K:
        ans=1
        for i in range(N):
            ans=(ans*A[i])%MOD
        print(ans)
        return

    ans=1
    mi=0
    pi=0
    Fail=False
    K2=K
    while K > 0:
        if K > 1 and mi+1 < len(m):
            if pi+1 < len(p):
                if (m[mi]*m[mi+1]) > (p[pi]*p[pi+1]):
                    ans = (ans * m[mi] * m[mi+1])%MOD
                    mi+=2
                else:
                    ans = (ans * p[pi] * p[pi+1])%MOD
                    pi+=2
                K-=2
            else:
                ans = (ans * m[mi] * m[mi+1])%MOD
                mi+=2
                K-=2
            #print("#2", K, ans, mi, pi)
        else:
            if pi < len(p):
                ans = (ans * p[pi])%MOD
                pi+=1
                K-=1
            else:
                Fail=True
                K-=1
            #print("#1", K, ans, mi, pi)
    if Fail==False:
        print(ans)
        return

    ans=1
    mi=len(m)-1
    pi=len(p)-1
    while K2 > 0:
        if K2 > 1 and mi > 1:
            if pi > 1:
                if (m[mi]*m[mi-1]) > (p[pi]*p[pi-1]):
                    ans = (ans * m[mi] * m[mi-1])%MOD
                    mi-=2
                else:
                    ans = (ans * p[pi] * p[pi-1])%MOD
                    pi-=2
                K2-=2
            else:
                #print("##",mi)
                ans = (ans * m[mi] * m[mi-1])%MOD
                mi-=2
                K2-=2
            #print("#2", K, ans, mi, pi)
        else:
            ans = (ans * m[mi])%MOD
            mi-=1
            K2-=1
            #if pi < len(p):
            #    ans = (ans * p[pi])%MOD
            #    pi+=1
            #    K-=1
            #else:
            #    Fail=True
            #print("#1", K, ans, mi, pi)
    print(ans)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

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)-1:
        ans.append(ans[-1]*pos[p+1]*pf(neg[n-1],mod-2,mod))
    else:
        ans=[1]
        for j in range(K):
            ans.append(ans[-1]*neg[-1-j]%mod)
        ans.append(-1*ans[-1]%mod)
print(ans[-1])

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    an = sorted([i for i in a if i < 0])
    ap = sorted([i for i in a if i > 0], reverse = True)
    a_s = list(sorted(a, key = lambda x: -abs(x)))
    num_n = 0
    num_p = 0
    zero = False
    ans = 1
    old_n = 0
    ald_p = 0
    for ai in a_s[:k]:
        if ai < 0:
            old_n = ai
            num_n += 1
        elif ai > 0:
            old_p = ai
            num_p += 1
        else:
            zero = True
    if zero:
        print(0)
        return
    if num_n%2 == 0:
        for ai in a_s[:k]:
            ans *= ai
            ans %= mod
        print(ans)
        return
    elif len([i for i in a if i > 0]) == 0:
        a_sr = list(sorted(a, reverse=True))[:k]
        for ai in a_sr:
            ans *= ai
            ans %= mod
        print(ans)
        return
    else:
        next_n = 0
        next_p = 0
        for i in a_s[k:]:
            if i < 0:
                next_n = i
                break
        for i in a_s[k:]:
            if i > 0:
                next_p = i
                break
        if old_p*next_p > old_n*next_n:
            for ai in a_s[:k]:
                if ai == old_n:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_p
            ans %= mod
            print(ans)
            return
        else:
            for ai in a_s[:k]:
                if ai == old_p:
                    continue
                ans *= ai
                ans %= mod
            ans *= next_n
            ans %= mod
            print(ans)
            return
        

if __name__ == "__main__":
    main()

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):
			i = -(1+i)
			ans *= (mina[i]*mina[i-1]) % mod
			ans %= mod
		ans *= mina[-(3+i)]
		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:
		mina.append(pra[0])
		mina.sort()
		for i in range(k):
			i = -(1+i)
			ans *= mina[i]
		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

	#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

	"""
	while co <= k:
		if k - co >= 2:
			if data[co] * data[co+1] >= 0:
				ans *= (data[co] * data[co+1]) % mod
				ans %= mod
				co += 2
			else:
				ans *= data[co]
				ans %= mod
				ans *= data[co+1]
				ans %= mod
				co += 2
		elif k - co == 1:
			ans *= data[co]
			ans %= mod
			co += 1
		else:
			break
	"""

		
	print(ans)

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
import bisect
def do():
    n, k = map(int, input().split())
    dat = list(map(int, input().split()))
    buf = []
    nump, numm, numz = 0, 0, 0
    for i in range(n):
        if dat[i] == 0:
            numz += 1
        elif dat[i] > 0:
            nump += 1
            buf.append([dat[i], dat[i]])
        elif dat[i] < 0:
            numm += 1
            buf.append([dat[i], -dat[i]])
    indm = []
    indp = []
    for i in range(n):
        if buf[i][0] < 0:
            indm.append(i)
        else:
            indp.append(i)
    buf.sort(key=lambda x: x[1], reverse=True)
    #print(nump, numm, numz)
    #print(buf)
    #print(indm)
    #print(indp)
    # +と-を足してもk個に満たないなら 0 をかけるしかないので
    if nump + numm < k:
        print(0)
        return

    res = 1
    lastp = None
    lastm = None
    flagPosi = True
    for i in range(k):
        res *= buf[i][0]
        res %= mod
        if buf[i][0] > 0:
            lastp = buf[i][0]
        elif buf[i][0] < 0:
            lastm = buf[i][0]
            flagPosi = not flagPosi

    # k個選んで正なら、無条件にオッケー
    if flagPosi:
        print(res%mod)
        return

    def do2(): # negaしか作れないなら最も小さい値
        buf.sort(key=lambda x: x[1], reverse=False)
        res2 = 1
        for i in range(k):
            res2 *= buf[i][0] % mod
            res2 %= mod
        print(res2%mod)

    def do3(anti, kawari): # negaしか作れないなら最も小さい値
        ispass = False
        buf.sort(key=lambda x: x[1], reverse=True)
        res2 = 1
        for i in range(k):
            if ispass is False and buf[i][0] == anti:
                ispass = True
                continue
            res2 *= buf[i][0] % mod
            res2 %= mod
        res2 *= kawari
        print(res2%mod)

    # 負の場合は二パターン
    # 1. 正を抜いて、次に大きい負をかける
    # 2. 負を抜いて、次に大きい正をかける
    nextp = None
    nextm = None
    for i in range(k, len(buf)):
        if buf[i][0] > 0 and nextp is None:
            nextp = buf[i][0]
        elif buf[i][0] < 0 and nextm is None:
            nextm = buf[i][0]
    #print("---",lastp, lastm, nextp,nextm)
    if nextm is None and nextp is None: # これはないはず
        do2()
        return
    if (lastp is None or nextm is None) and (lastm is None or nextp is None):
        # この場合、動かせないので負しかないから
        do2()
        return
    if lastp is not None and lastm is not None and nextp is not None and nextm is not None:
        # 全部あるなら戦い
        if abs(nextm / lastp) > abs(nextp / lastm):
            # pをmにした方がいいので
            do3(lastp, nextm)
            return
        else:
            do3(lastm, nextp)
            return
    # この場合、どっちしかないので
    if (lastp is None or nextm is None):
        # この場合、 m-> p
        do3(lastm, nextp)
        return
    else:
        do3(lastp, nextm)
        return


do()

Submission status: Runtime Error

Solution code:
from collections import deque
MOD = pow(10,9)+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
P = []; M = []; Z = []
for i in range(N):
  if A[i] >0:
    P.append(A[i])
  elif A[i] <0:
    M.append(A[i])
  else:
    Z.append(0)
P.sort(reverse=True)
M.sort(reverse=True)
ans = 1
if K == 1:
  print(P[0]%MOD)
  exit()
if len(Z) > N-K:
  print(0)
  exit()
if len(M) == 0: #全て正の場合:
  for i in range(K):
    ans = ans*P[i]%MOD
  print(ans)
  exit()
if len(P) == 0: #全て負の場合
  for i in range(K):
    ans = ans*M[i]%MOD
  print(ans)
  exit()
L = [[],[]]
M.sort()
P = deque(P); M = deque(M)
pm = [0,0] #正負の数を保存
pnow = 0; mnow = 0
#print(P,M)

for i in range(K):
  if not P:
    temp = M.popleft()
    pm[1] +=1
    L[1].append(temp)
  elif not M:
    temp = P.popleft()
    pm[0] +=1
    L[0].append(temp)
  elif P and M:
    if P[0] >= abs(M[0]):
      temp = P.popleft()
      pm[0] += 1
      L[0].append(temp)
    else:
      temp = M.popleft()
      pm[1] += 1
      L[1].append(temp)
#一個ずらす
#print(L)

if pm[1]%2 == 1:
  if not P and not M:
    pass
  elif not M: #もう負の数が残っていない
    L[1].pop()
    L[0].append(P[0])
  elif not P: #もう正の数が残っていない
    L[0].pop()
    L[1].append(M[0])
  elif M and P:
    if L[0][-1]*P[0] >= L[1][-1]*M[0]:
      L[1].pop()
      L[0].append(P[0])
    else:
      L[0].pop()
      L[1].append(M[0])
#print(L)    
for num in range(2):
  for s in L[num]:
    ans = ans*s%MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys
mod=10**9+7
n,k=map(int,input().split())
ax=list(map(int,input().split()))
a=[]

chkp,chkm=1,1
for i in range(n):
    if ax[i]>0: a.append([abs(ax[i]),1]);chkm=0
    elif ax[i]<0: a.append([abs(ax[i]),-1]);chkp=0
    else: a.append([0,0])
a=sorted(a,reverse=True)

if chkp==1:
    ans=1
    for i in range(k):
        ans=ans*a[i][0]%mod
    print(ans)
    sys.exit()

if chkm==1:
    ans=1
    for i in range(n-1,n-k-1,-1):
        ans=ans*a[i][0]%mod
    print(mod-ans)
    sys.exit()


lp,lm=[],[]
cntm=0
ans=1
for i in range(k):
    [p,sgn]=a[i]
    ans=ans*p%mod
    if sgn==1: lp.append(p)
    elif sgn==-1:
        lm.append(p)
        cntm=cntm^1

if cntm==0 or ans==0:
    print(ans%mod)
    sys.exit()

newp,newm=-1,-1
for i in range(k+1,n):
    if a[i][1]==-1: newm=a[i][0];break
for i in range(k+1,n):
    if a[i][1]>=0: newp=a[i][0];break

x=1 if (lp and newm) else 0
y=1 if (lm and newp) else 0
if x==1 and y==1:
    if newp*lp[-1]>=newm*lm[-1]: ans=ans*inv(lm[-1],mod)*newp
    else: ans=ans*inv(lp[-1],mod)*newm
elif x==-1 and y==1: ans=ans*inv(lm[-1],mod)*newp
elif x==1 and y==-1: ans=ans*inv(lp[-1],mod)*newm
print(ans%mod)



def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7
sei = []
hu = []
zero = []
for i in range(N):
    a = A[i]
    if a > 0:
        sei.append(a)
    elif a < 0:
        hu.append(a)
    else:
        zero.append(0)
sei.sort(reverse = True)
if len(zero) > N - K:
    print(0)
else:
    ans = 1
    p = len(sei)
    q = len(hu)
    if p+q == K:
        for i in range(p):
            ans *= sei[i]
            ans %= MOD
        for i in range(q):
            ans *= hu[q]
            ans %= MOD
        print(ans%MOD)
    if p == 0:
        hu.sort(reverse = True)
        for i in range(K):
            ans *= hu[i]
            ans %= MOD
        print(ans)
    elif q == 0:
        for i in range(K):
            ans *= sei[i]
            ans %= MOD
        print(ans)
    else:
        hu.sort()
        flag = 0
        pin = 0
        qin = 0
        r = K
        while r > 0:
            if pin == -1 and qin == -1:
                break
            elif pin == -1:
                qin += 1
                if qin == q:
                    qin = -1
                if flag == 1:
                    flag = 0
                else:
                    flag = 1
            elif qin == -1:
                pin += 1
                if pin == p:
                    pin = -1
            else:
                if abs(sei[pin])>abs(hu[qin]):
                    pin += 1
                    if pin == p:
                        pin = -1
                else:
                    qin += 1
                    if qin == q:
                        qin = -1
                    if flag == 0:
                        flag = 1
                    else:
                        flag = 0
            r -= 1
        if pin == -1:
            pin = p
        if qin == -1:
            qin = q
        if False:
            print(100)
        else:
            if flag == 0:
                for i in range(pin):
                    ans *= sei[i]
                    ans %= MOD
                for j in range(qin):
                    ans *= hu[j]
                    ans %= MOD
                print(ans%MOD)
            else:
                if pin == p:
                    for i in range(pin-1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin+1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)
                else:
                    for i in range(pin+1):
                        ans *= sei[i]
                        ans %= MOD
                    for j in range(qin-1):
                        ans *= hu[j]
                        ans %= MOD
                    print(ans%MOD)