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 bisect
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
minus = deque(a[:bisect.bisect_left(a, 0)])
plus = deque(a[bisect.bisect_left(a, 0):])
nm = len(minus)
np = len(plus)
mod = 10**9+7
ans = -float("inf")
repeat = min(nm//2, k//2)

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

flg=False
must1 = k-np
must2 = min(k, nm)
start = must1//2
start += must1%2

if must1 % 2 == 1 and must2 - must1 ==0:
  flg = True

if flg:
  ans = 1
  for i in range(k):
    ans *= minus.pop()
    ans %= mod
  print(ans)
  quit()
    
for i in range(start, repeat+1):
  temp = 1
  kuri = 0
  #print("i " + str(i))
  for j in range(i*2):
    temp*=minus.popleft()  
    temp%=mod
  for j in range(k-i*2):
    temp*=plus.pop()
    temp%=mod
  #print(i)
  #print(temp)
  ans=max(ans, temp)

print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
lis = list(map(int,input().split()))
def shinchan(before,after):
    an = 1
    key = 1
    for i in range(k):
        if key and abs(lis[i]) == before:
            an *= after
            key = 0
        else:
            an *= abs(lis[i])
        an %= 10 ** 9 + 7
    return an
plus = 0
minus = 0
zero = 0
p,m = [],[]
for num in lis:
    if num > 0:
        plus += 1
        p.append(num)
    elif num < 0:
        minus += 1
        m.append(num)
    else:
        zero += 1
p.sort(reverse=True)
m.sort(key = lambda x:abs(x),reverse=True)
lis.sort(key=lambda x:abs(x),reverse=True)
zissaiplus = 0
zissaiminus = 0
zissaizero = 0
for i in range(k):
    if lis[i] > 0:
        zissaiplus += 1
    elif lis[i] < 0:
        zissaiminus += 1
    else:
        zissaizero += 1
if zissaizero > 0:
    print(0)
    exit()
if zissaiminus % 2 == 0:
    ans = shinchan(-1,-1)
    print(ans)
    exit()
else:
    key1,key2 = 0,0
    if zissaiminus > 0 and plus-zissaiplus > 0:
        be1 = -m[zissaiminus-1]
        af1 = p[zissaiplus]
        key1 = 1
    if zissaiplus > 0 and minus-zissaiminus > 0:
        be2 = p[zissaiplus-1]
        af2 = -m[zissaiplus]
        key2 = 1
    if key1 == 1 and key2 == 1:
        if be2 * af1 >= be1 * af2:
            ans = shinchan(be1,af1)
        else:
            ans = shinchan(be2,af2)
    elif key1 or key2:
        if key1:
            ans = shinchan(be1,af1)
        else:
            ans = shinchan(be2,af2)
    else:
        if zero > 0:
            print(0)
            exit()
        lis.sort(key=lambda x:abs(x))
        ans = -shinchan(0,0)+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

ans = 1
sei = 0
for i in a:
    if i>0:
        sei += 1

if max(0,k-sei)%2==0:
    b = sorted(a, key=lambda x: abs(x),reverse=True)
    cnt = 0
    sei = []
    hu = []
    for i in b:
        if i>0:
            sei.append(i)
        else:
            hu.append(i)
    hu_seki = []
    for i in range(len(hu)//2):
        hu_seki.append(hu[i*2]*hu[i*2+1]%mod)

    for i in range(min(k,len(sei))):
        ans = ans*sei[i]%mod
    index = 0
    if k>len(sei):
        for i in range((k-len(sei))//2):
            ans = ans*hu_seki[i]%mod
            index += 1
    sei.sort()
    while index<len(hu_seki) and index*2+1<len(sei):
        if sei[len(sei)-k+index*2]*sei[len(sei)-k+index*2+1]<hu_seki[index]:
            ans = ans//(sei[index*2]*sei[index*2+1])
            ans = ans*hu_seki[index]%mod
            index += 1
        else:
            break
else:
    b = sorted(a, key=lambda x: abs(x))
    for i in range(k):
        ans *= b[i]
        ans %= mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))

    MOD = 10**9 + 7

    absA = [abs(a) for a in A]
    flg = 0
    m = []
    p = []
    dict = []
    T = []
    for i in A:
        if i < 0:
            m.append(i)
            T.append(tuple([abs(i),-1]))
        elif i > 0:
            p.append(i)
            T.append(tuple([abs(i),1]))
        else:
            flg = 1

    T.sort(reverse=True)
    # print(T)


    ans = T[:k]
    # print(ans)
    c = 0
    for i in ans:
        if i[1] == -1:
            c += 1

    if c % 2 == 0:
        l = 1
        for i in ans:
            l *= i[0]
        print(l)

    else:
        flg_1,flg_2 = 0,0
        # print(T)
        for j in range(k-1,-1,-1):
            if T[j][1] == -1:
                flg_1 = 1
                min_m = T[j][0]
                break

        for j in range(k,len(T)):
            if T[j][1] == 1:
                flg_2 ^= 1
                # print('AaA')
                max_p = T[j][0]
                break

        # print(min_m,max_p)

        if flg_1 and flg_2:
            flg = 1
        else:
            flg = 0

        flg_1,flg_2 = 0,0

        for j in range(k-1,-1,-1):
            if T[j][1] == 1:
                flg_1 = 1
                min_p = T[j][0]
                break
        
        for j in range(k,len(T)):
            if T[j][1] == -1:
                flg_2 = 1
                max_m = T[j][0]
                break

        if flg_1 and flg_2:
            flg2 = 1
        else:
            flg2 = 0


        l = 1
        for i in ans:
            l *= abs(i[0])
            l %= MOD 

        # print(l)

        if flg == 1 and flg2 == 1:
            if min_p * max_p >= min_m * max_p:
                l *= max_p
                l *= pow(min_m,MOD-2,MOD)
            else:
                l *= max_m
                l *= pow(min_p,MOD-2,MOD)
        elif flg == 1:
                l *= max_p
                t = pow(min_m,MOD-2,MOD)
                l *= pow(min_m,MOD-2,MOD)
        elif flg2 == 1:
                l *= max_m
                l *= pow(min_p,MOD-2,MOD)
        else:
            if 0 in A:
                l = 0
            else:
                A.sort(reverse=True)
                l = 1
                for i in range(k):
                    l *= A[i]
                    l %= MOD
                print(l)
                exit()
                # print(A)


            
        print(l%MOD)




    

            

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    m = 10**9+7
    p = []
    q = []
    r = []
    for i in range(N):
        if A[i] > 0:
            p.append(A[i])
        elif A[i] < 0:
            q.append(A[i])
        else:
            r.append(A[i])
    p.sort()
    q.sort()
    P = len(p)
    Q = len(q)
    if P > 0:
        if Q < 2:
            ans = 1
            for i in range(K):
                ans = ans * p[P-1-i] % m
            print(ans)
        elif P < K:
            print(0)
        else:
            # pの小さい２つとqの大きい２つを取り換えていく
            i = min(K, P)
            j = 0
            while i >= 0 and j < Q-1:
                if p[P-i]*p[P-i+1] < q[Q-j-1]*q[Q-j-2]:
                    i -= 2
                    j += 2
                else:
                    break
            ans = 1
            # print(i,j)
            for k in range(max(0,i)):
                ans = ans * p[P-k-1] % m
            for l in range(min(Q,j)):
                ans = ans * q[Q-l-1] % m
            print(ans)
    else:
        if K % 2 == 0:
            if Q >= K:
                ans = 1
                for i in range(K):
                    ans = ans * q[Q-1-i] % m
                print(ans)
            else:
                print(0)
        else:
            if len(r) > 0:
                print(0)
            else:
                ans = 1
                for i in range(K):
                    ans = ans * q[Q-1-i] % m
                print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#E
import math
from collections import deque
N,K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7

P = []
M = []
Z = 0

for i in range(N):
  if A[i] == 0:
    Z += 1
  elif A[i] >= 0:
    P.append(A[i])
  else:
    M.append(A[i])


if N-K < Z:
  print(0)
  exit()



P.sort()
M.sort()
P = deque(P)
M = deque(M)

if len(P) == 0 and K%2 == 1:
  ans = 1
  for i in range(K):
    ans *= M.pop()
    ans = ans%MOD
  print(ans)
  exit()

ans = 1
if K - len(P) > 0:
  for i in range(((K-len(P))//2)):
    ans *= M.pop()
    ans = ans%MOD
    K -= 1

while K > 2:
  if len(P) < 2:
    ans *= M.pop()
    ans *= M.pop()
    ans = ans%MOD
    K -= 2
  elif len(M) < 2:
    ans *= P.popleft()
    ans = ans%MOD
    K -= 1

  elif P[0]*P[1] < M[-1]*M[-2]:
    ans *= M.pop()
    ans *= M.pop()
    ans = ans%MOD
    K -= 2
  else:
    ans *= P.popleft()
    K -= 1

if K == 2:
  if len(P) < 2:
    ans *= M.pop()
    ans *= M.pop()
    ans = ans%MOD
    K -= 2
  elif len(M) < 2:
    ans *= P.popleft()
    ans = ans%MOD
    K -= 1

  elif P[0]*P[1] < M[-1]*M[-2]:
    ans *= M.pop()
    ans *= M.pop()
    ans = ans%MOD
    K -= 2
  else:
    ans *= P.popleft()
    ans *= P.popleft()
    ans = ans%MOD
    K -= 2

if K == 1:
  ans *= P.popleft()
  ans = ans%MOD
  K -= 1

print(ans)

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 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:
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

B=[]
C=[]
Z=[]

for a in A:
    if a>0:
        B.append(a)
    elif a<0:
        C.append(-a)
    else:
        Z.append(0)

B.sort(reverse=True)
C.sort(reverse=True)

if K==len(B)+len(C):
    ANS=1
    for b in B:
        ANS=ANS*b%mod
    for c in C:
        ANS=ANS*(-c)%mod

    if len(C)%2==1 and Z!=[]:
        print(0)
    else:
        print(ANS)
    sys.exit()

if K>len(B)+len(C):
    print(0)
    sys.exit()

if B==[]:
    if Z==[] and K%2==0:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
            
    elif Z==[] and K%2==1:
        C.reverse()
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod
        print(-ANS%mod)
        
    elif K%2==1:
        print(0)
    else:
        ANS=1
        for i in range(K):
            ANS=ANS*(C[i])%mod

    sys.exit()

if K<=len(B):
    S=1
    for i in range(K):
        S=S*B[i]%mod

    ind=0
    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[K-1-ind]*B[K-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[K-1-ind]*B[K-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

else:
    if (K-len(B))%2==0:
        S=1
        for i in range(len(B)):
            S=S*B[i]%mod

        for j in range(K-len(B)):
            S=S*C[j]%mod

        ind=K-len(B)

    else:
        S=1
        for i in range(len(B)-1):
            S=S*B[i]%mod

        for j in range(K-len(B)+1):
            S=S*C[j]%mod

        ind=K-len(B)+1
        

    while True:
        if ind+1<len(C) and K-2-ind>=0 and C[ind]*C[ind+1]>B[len(B)-1-ind]*B[len(B)-2-ind]:
            S=S*C[ind]*C[ind+1]*pow(B[len(B)-1-ind]*B[len(B)-2-ind],mod-2,mod)%mod
            ind+=2
        else:
            break

    print(S%mod)

Submission status: Runtime Error

Solution code:
def find(lst, k):
  for i in range(len(lst)):
    if lst[i] == k:
      return True
  return False
  
 
n, k = map(int, input().split())
 
lst = list(map(int, input().split()))
 
plus_list = []
minus_list = []
for i in range(n):
  if lst[i] >= 0:
    plus_list.append(lst[i])
  else:
    minus_list.append(lst[i])
    lst[i] = -1 * lst[i]
lst.sort()    
plus_list.sort()
minus_list.sort()
minus_cand = []
ans_list = []
ans = 1
sum = 1
if k == 1:
  ans = lst[n-1]
else:
  for i in range(1, k+1):
      ans_list.append(lst[len(lst)-i])
      ans *= ans_list[i-1]
  if len(minus_list) >= 2:
    for i in range(k // 2):
      if ans_list[len(ans_list)-i-1]*ans_list[len(ans_list)-i-2] < minus_list[i]*minus_list[i+1]:
        ans = ans / (ans_list[len(ans_list)-i-1]*ans_list[len(ans_list)-i-2])
        ans = ans * minus_list[i]*minus_list[i+1]
      else:
        break
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
MOD = 10**9 + 7
A = list(map(int,input().split()))
Ap = [a for a in A if a >= 0]
An = [-a for a in A if a < 0]
Ap.sort()
Ap.reverse()
An.sort()
An.reverse()

if len(Ap) == 0 and K % 2 == 1:
	ans = 1
	An.reverse()
	for i in range(K):
		ans = (ans * -An[i]) % MOD
	print(ans)
	exit()

B = [(a, 1) if a >= 0 else (-a, -1) for a in A]
B.sort()
B.reverse()
M = [0 if B[0][1] > 0 else 1]
for i in range(1, N):
	M.append(M[i-1] + (0 if B[i][1] > 0 else 1))

i = K-1
if M[i] % 2 == 0 or K == N:
	ans = 1
	for j in range(K):
		ans = (ans * B[j][0]) % MOD
	print(ans)
else:
	n = M[i]
	p = K - M[i]
	if len(An) == M[i] or p == 0:
		n -= 1
		p += 1
	elif len(Ap) == p+1:
		n += 1
		p -= 1
	elif Ap[p-1] * Ap[p] >= An[n-1] * An[n]:
		n -= 1
		p += 1
	else:
		n += 1
		p -= 1
	ans = 1
	for i in range(p):
		ans = (ans * Ap[i]) % MOD
	for i in range(n):
		ans = (ans * An[i]) % MOD
	print(ans)

Submission status: Runtime Error

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

if N - A.count(0) < K:
    print(0)
    exit(0)

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

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

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


i = 0
j = 0

ans = 1
if K % 2 == 1:
    ans = plus[0]
    K -= 1
    plus = plus[1:]

for _ in range(K//2):
    if i+1 >= len(plus):
        ans *= (minus[j] * minus[j+1])
        ans %= MOD
        j += 2
        continue
    elif j+1 >= len(minus):
        ans *= (plus[i] * plus[i+1])
        ans %= MOD
        i += 2
        continue

    a = plus[i] * plus[i+1]
    b = minus[j] * minus[j+1]
    if a > b:
        ans *= a
        i += 2
    else:
        ans *= b
        j += 2
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
lis = list(map(int,input().split()))
def shinchan(before,after):
    ans = 1
    key = 1
    for i in range(k):
        if key and abs(lis[i]) == before:
            ans *= after
            key = 0
        else:
            ans *= abs(lis[i])
        ans %= 10 ** 9 + 7
    return ans
plus = 0
minus = 0
zero = 0
p,m = [],[]
for num in lis:
    if num > 0:
        plus += 1
        p.append(num)
    elif num < 0:
        minus += 1
        m.append(num)
    else:
        zero += 1
p.sort(reverse=True)
m.sort(key = lambda x:abs(x),reverse=True)
lis.sort(key=lambda x:abs(x),reverse=True)
zissaiplus = 0
zissaiminus = 0
zissaizero = 0
for i in range(k):
    if lis[i] > 0:
        zissaiplus += 1
    elif lis[i] < 0:
        zissaiminus += 1
    else:
        zissaizero += 1
if zissaizero > 0:
    print(0)
    exit()
if zissaiminus % 2 == 0:
    ans = shinchan(-1,-1)
    print(ans)
    exit()
else:
    key1,key2 = 0,0
    if zissaiminus > 0 and plus-zissaiplus > 0:
        be1 = -m[zissaiminus-1]
        af1 = p[zissaiplus]
        key1 = 1
    if zissaiplus > 0 and minus-zissaiminus > 0:
        be2 = p[zissaiplus-1]
        af2 = -m[zissaiplus]
        key2 = 1
    if key1 == 1 and key2 == 1:
        if be2 * af1 >= be1 * af2:
            ans = shinchan(be1,af1)
        else:
            ans = shinchan(be2,af2)
    elif key1 or key2:
        if key1:
            ans = shinchan(be1,af1)
        else:
            ans = shinchan(be2,af2)
    else:
        if zero > 0:
            print(0)
            exit()
        lis.sort(key=lambda x:abs(x))
        ans = -shinchan(0,0)+10 ** 9 + 7
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))

    Ap=[x for x in A if x>=0 ]
    Am=[abs(x) for x in A if x<0]

    if K==N:
        out=1
        for a in A:
            out*=a
            out%=10**9+7
        print(out)
        return


    if K%2==1 and len(Ap)==0:
        Am.sort()
        out=1
        for i in range(K):
            out*=Am[i]
            out%=10**9+7
        print((-out)%(10**9+7))
        return

    Ap.sort(reverse=True)
    Am.sort(reverse=True)
    
    ap_idx=0
    am_idx=0
    result=1
    for _ in range(0,K,2):
        if K%2==0 and ap_idx+1<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        elif K%2==1 and ap_idx+2<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        else:
            pmax=-1

        if am_idx+1<len(Am):
            mmax=Am[am_idx]*Am[am_idx+1]
        else:
            mmax=-1

        if pmax==-1 and mmax==-1:
            break

        if pmax>mmax:
            result*=pmax
            ap_idx+=2
        else:
            result*=mmax
            am_idx+=2

        result%=(10**9+7)
    
    if K%2==1:
        kkkkkkkkkkkkkkkkkkkkkkkkkk
        result*=Ap[ap_idx]

    print(result%(10**9+7))

main()

Submission status: Runtime Error

Solution code:
def f(P,M):
    return P[0]*M+P[1]

def g(X,Y,M):
    (a,b)=X
    (x,y)=Y

    return (a*x*M+a*y+b*x+(y*b)//M,(y*b)%M)

N,K=map(int,input().split())
A=list(map(int,input().split()))
M=10**9+7

P,Q=[],[] #P,Q...+,-の要素
Z=0 #Z...0の個数

for a in A:
    if a>0:
        P.append(divmod(a,M))
    elif a<0:
        Q.append(divmod(a,M))
    else:
        Z+=1

P.sort(reverse=True)
X=[(0,1)]
(a,b)=(0,1)
for (x,y) in P:
    a,b=g((a,b),(x,y),M)
    X.append((a,b))

Q.sort()
Y=[(0,1)]
(a,b)=(0,1)
for (x,y) in Q:
    a,b=g((a,b),(x,y),M)
    Y.append((a,b))

J=-1
S=len(P)
for m in range(0,len(Q)+1,2):
    if 0<=K-m<=S:
        J=max(J,f(g(X[K-m],Y[m],M),M))

if J>0:
    print(J%M)
else:
    if Z==0:
        J=1
        for i in range(K):
            J*=Q[-(i+1)]
        print(J%M)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
arr = sorted(list(map(int,stdin.readline().split())),key=lambda x:abs(x))
mod = 10**9+7
pos,neg = [],[]
for i in arr:
    if i>=0:
        pos.append(i)
    else:
        neg.append(i)
if not len(pos):
    ans = 1
    if k%2:
        for i in range(k):
            ans *= neg[i]
            ans %= mod
    else:
        for i in range(k):
            ans *= neg[-1-i]
            ans %= mod
else:
    ans = 1
    i=len(pos)-1
    j=len(neg)-1
    val = 0
    if n==k:
        for x in arr:
            ans *= x
            ans %= mod
    elif k==1:
        ans = pos[i]%mod
    else:
        while val != k-2:
            if i == 0:
                ans *= neg[j]
                j -= 1
            elif j == 0:
                ans *= pos[i]
                i -= 1
            else:
                if pos[i]>neg[j]:
                    ans *= pos[i]
                    i -= 1
                else:
                    ans *= neg[j]
                    j -= 1
            ans %= mod
            val += 1
        if (len(neg)-1-j)%2:
            ans *= pos[i]*neg[j]
        else:
            if i==0:
                ans *= neg[j]*neg[j-1]
            elif j==0:
                ans *= pos[i]*pos[i-1]
            else:
                ans *= max(pos[i]*pos[i-1],neg[j]*neg[j-1])
        ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, K = ZZ()
    A = ZZ()
    p = []
    z = []
    m = []
    for a in A:
        if a > 0: p.append(a)
        elif a == 0: z.append(a)
        else: m.append(a)
    p.sort(reverse=True)
    m.sort()
    if len(p) == 0 and len(z) == 0 and K%2 == 1: #答えが負
        m = m[::-1]
        ans = 1
        for i in range(K):
            ans *= m[i]
            ans %= MOD
        print(ans)
        return
    else:
        if K - len(p) - len(m) > 0:
            print(0)
            return
        else:
            ans = 1
            itr = 0
            itrp = 0
            while K > 0:
                if itr+1 < len(m): c1 = (m[itr] * m[itr+1])
                else: c1 = 0
                if itrp+1 < len(p): c2 = (p[itrp] * p[itrp+1])
                else: c2 = 0

                if c1 > c2 and K >= 2:
                    ans *= c1
                    ans %= MOD
                    itr += 2
                    K -= 2
                else:
                    ans *= p[itrp]
                    ans %= MOD
                    itrp += 1
                    K -= 1
            print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
MOD=10**9+7
if N==K:
    ans=1
    for i in A:
        ans=ans*i%MOD
    print(ans)
    exit()
if K==1:
    print(A[0]%MOD)
    exit()
if K%2==1 and A[0]==0:
    print(0)
    exit()
if K%2==1 and A[0]<0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
if N-A.count(0) <K:
    print(0)
    exit()
if A[-1]>=0:
    ans=1
    for i in range(K):
        ans=ans*A[i]%MOD
    print(ans)
    exit()
l=0
r=N-1
t=[]
c=0
if K%2==1:
    tk=K-1
    flg=True
else:
    tk=K
    flg=False
while c<tk:
    if A[l]*A[l+1]<=A[r]*A[r-1]:
        t.append(A[r])
        t.append(A[r-1])
        r+=2
        c+=2
    else:
        t.append(A[l])
        t.append(A[l+1])
        l+=2
        c+=2
if flg:
    t.append(A[l])
ans=1
for i in t:
    ans=ans*i%MOD
print(ans)

Submission status: Runtime Error

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

pos, neg = [], []
zero_count = 0

for x in a:
	if x > 0:
		pos.append(x)
	elif x < 0:
		neg.append(x)
	else:
		zero_count += 1

# max_v = pos[0]
# min_v = neg[0]

# max_p_idx = 1
# max_n_idx = 0
# min_p_idx = 0
# min_n_idx = 1

# for kk in range(1, min(k, len(pos) + len(neg))):
# 	if max_p_idx < len(pos):
# 		max_v 


MOD = 10**9 + 7

if len(pos) >= k:
	pos_res = pos[:k]
	idx = 0
	while idx + 1 < len(neg) and pos_res[k - idx - 1] * pos_res[k - idx - 2] < neg[idx] * neg[idx + 1]:
		idx += 2

	result = 1
	for i in range(idx):
		result = result * neg[i] % MOD

	for i in range(k - idx):
		result = result * pos[i] % MOD

	print(result)

else:
	left = k - len(pos)
	if left > len(neg):
		print(0) 
	else:
		if left % 2 == 0:
			idx = left
			while idx + 1 < len(neg) and pos_res[k - idx - 1] * pos_res[k - idx - 2] < neg[idx] * neg[idx + 1]:
				idx += 2

			result = 1
			for i in range(idx):
				result = result * neg[i] % MOD

			for i in range(k - idx):
				result = result * pos[i] % MOD

			print(result)
		else:
			if zero_count > 0:
				print(0)
			else:
				b = sorted(map(abs, a))
				result = 1
				for i in range(k):
					result = result * b[i] % MOD
				print(result)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
A = li()

d = defaultdict(int)
mod = 10**9+7
K_ = K

for i in range(N):
    d[A[i]] += 1
    if A[i] < 0:
        A[i] *= -1

A = sorted(A, reverse=True)
l = []

for num in A:
    if d[-num] > 0:
        l.append(1)
        d[-num] -= 1
    else:
        l.append(0)
        d[num] -= 1

#print(l)
#print(sum(l[:K]))

if not sum(l[:K])%2:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= mod
    print(ans)

else:
    flag = False
    ans = 1
    for i in range(K, N):
        if not l[i]:
            flag = True
            ans *= A[i]
            break
    
    if flag:
        for i in reversed(range(K)):
            if flag and l[i]:
                flag = 0
                continue
            ans *= A[i]
            ans %= mod
        print(ans)
    
    else:
        if K%2:
            for i in range(N-K, N):
                ans *= -A[i]
                ans %= mod
            print(ans)
        else:
            for i in range(N):
                if l[i] == 1:
                    K -= 1
                    ans *= -A[i]
                    ans %= mod
                if K == 0:
                    break
            else:
                ans = 1
                flag = True
                for i in reversed(range(K_)):
                    if flag and not l[i]:
                        flag = 0
                        continue
                    ans *= A[i]
                    ans %= mod
                ans *= A[K_]
                ans %= mod
                print(ans)
                exit()
            print(ans)

Submission status: Runtime Error

Solution code:
import sys

MOD = 10**9 + 7

def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)

def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]

def sign(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

def prod(A, K, add, remove):
    prod = 1
    for i in range(K):
        if i == remove:
            continue
        prod *= abs(A[i])
        prod %= MOD
    if add != None:
        prod *= abs(A[i])
        prod %= MOD
    return prod

N, K = read_int_list()
A = read_int_list()

A.sort(key=lambda i: -abs(i))

last_plus = None
last_minus = None
sig = 1
for i in range(K):
    sig *= sign(A[i])
    if A[i] > 0:
        last_plus = i
    if A[i] < 0:
        last_minus = i
remove_plus = None
add_plus = None
remove_minus = None
add_minus = None
if sig < 0:
    for i in range(K, N):
        if A[i] > 0 and last_minus != None and remove_minus == None:
            remove_minus = last_minus
            add_minus = i
            sig = 1
        elif A[i] < 0 and last_plus != None and remove_plus == None:
            remove_plus = last_plus
            add_plus = i
            sig = 1
        elif A[i] == 0:
            sig = 0
            break

if sig == 0:
    print(0)
elif sig > 0:
    if remove_plus != None and remove_minus != 0:
        if abs(A[remove_plus]/A[add_plus]) > abs(A[remove_minus]/A[add_minus]):
            ap = prod(A, K, add_minus, remove_minus)
        else:
            ap = prod(A, K, add_plus, remove_plus)
    elif remove_plus != None:
        ap = prod(A, K, add_plus, remove_plus)
    else:
        ap = prod(A, K, add_minus, remove_minus)
    print(ap)
else:
    ap = prod(A[::-1], K, None, None)
    print((MOD-ap) % MOD)