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
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])
    elif a[i]>0:
        p.append(a[i])
    else:
        z+=1
m=sorted(m,reverse=True)
p=sorted(p,reverse=True)

if k>len(m)+len(p):
    print(0)
    sys.exit()

if len(p)==0:
    ans=1
    if k%2==0:
        for i in range(k):
            ans*=m[i]
            ans%=mod
        print(ans)
        sys.exit()
    else:
        for i in range(k):
            if i==k-1:
                ans*=-m[-i-1]
                ans%=mod
            else:
                ans*=m[-i-1]
                ans%=mod
        print(ans)
        sys.exit()

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


i=0
q=[]
if len(m)%2==0:
    for i in range(len(m)//2):
        q.append(m[2*i]*m[2*i+1])
else:
    for i in range(len(m)//2):
        q.append(m[2*i]*m[2*i+1])
        q.append(m[-1]-1)

pp=0
qq=0
c=0
ans=1
if k%2==1:
    ans*=p[pp]
    pp+=1
    c+=1
while c<k:
    if pp<len(p) and qq<len(q):
        if p[pp]*p[pp+1]>q[qq]:
            ans*=p[pp]*p[pp+1]
            pp+=2
        else:
            ans*=q[qq]
            qq+=1
        ans%=mod
        c+=2

    elif pp>=len(p)-1:
        ans*=q[qq]
    else:
        ans*=p[pp]*p[pp+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 m is None and p is None:
            pass
        elif 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 = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

mod = 10**9 + 7

import copy
import bisect
index = bisect.bisect_right(A, 0)

plus_list = copy.copy(A[index:])
minus_list = copy.copy(A[:index])

count = 0
ans = 1

plus_num = len(plus_list) - 1
minus_num = 0
while count < K:
    if K - count == 1:
        ans *= plus_list.pop() % mod
        count += 1
    else:
        if not plus_list or plus_num < 0:
            if ans > 0 and (K - count) % 2 == 0:
                for i in range(K - count):
                    ans *= minus_list[minus_num + i] % mod
                    count += 1
            else:
                for i in range(K - count):
                    ans *= minus_list[i*(-1)-1] % mod
                    count += 1
            continue

        if len(minus_list) < 2 or minus_num > len(minus_list):
            for i in range(K - count):
                ans *= plus_list[plus_num - i] % mod
                count += 1
            continue

        if plus_list[plus_num] >= minus_list[minus_num] * minus_list[minus_num+1]:
            ans *= plus_list[plus_num] % mod
            plus_num -= 1
            count += 1
        else:
            ans *= minus_list[minus_num] * minus_list[minus_num+1] % mod
            minus_num += 2
            count += 2
print(ans % mod)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
d1, d2 = sorted([q for q in a if q > 0], reverse=True), sorted([q for q in a if q < 0])
C = 1000000007
if len(d1)+len(d2) < k:
    print(0)
elif k == n:
    ans = 1
    for q in a:
        ans = ans*q % C
    print(ans)
elif len(d1) == 0 and k % 2 == 0:
    ans = 1
    for q in range(k):
        ans = ans*d2[q] % C
    print(ans)
elif len(d1) == 0 and len(d2) < n:
    print(0)
elif len(d1) == 0:
    ans = 1
    for q in range(len(d2)-1, len(d2)-k-1, -1):
        ans = ans*d2[q] % C
    print(ans)
elif len(d2) == 0:
    ans = 1
    for q in range(k):
        ans = ans*d1[q] % C
    print(ans)
else:
    ind = 0
    ans, now, w = 0, 0, min(k+1, len(d2)+1)
    for q in range(max(0, (k-len(d1)+1)//2*2), w, 2):
        if now == 0:
            """now = 1
            for q1 in range(q):
                now *= d2[q1]
            for q1 in range(k-q):
                now *= d1[q1]
            ans = now"""
            now = 1
        else:
            if d1[k-q+1]*d1[k-q] <= d2[q-2]*d2[q-1]:
                ind = q
    ans = 1
    for q in range(ind):
        ans = ans*d2[q] % C
    for q in range(k-ind):
        ans = ans*d1[q] % C
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

mod = 10**9+7

#全部使う
if n == k:
    ans = 1
    for i in lst1:
        ans *= i
        ans %= mod
    print(ans)
    exit() 

lst1.sort()
i = 0
minus = []
m = 0
while i < n and lst1[i] < 0:
    minus.append(lst1[i])
    m += 1
    i += 1
zero = 0
while i < n and lst1[i] == 0:
    zero += 1
    i += 1
plus = []
p = 0
while i < n:
    plus.append(lst1[i])
    p += 1
    i += 1

#必ず0を使う
if n-zero < k:
    print(0)
    exit()

#少なくともans<=0になる(負数にしかならない場合、0を掛けた方が良い場合)
if p==0 and not even(k):
    if zero:
        print(0)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= minus[-1-i]
            ans %= mod
        print(ans)
        exit()

#0を使わないようにすると、ちょうど負数が奇数個になってしまう場合
if n-zero == k and not even(m):
    print(0)
    exit()

#以下、必ず正の数にできる
#まだなんか見落としあるかも…

#負数はこの時点で上位からペアとして良い
pair = []
for i in range(0,m-1,2): #絶対値が大きい順
    pair.append(minus[i]*minus[i+1])

ans = 1
midx = 0 #cost2
pidx = 0 #cost1
plus.reverse() #降順
while k:
    if k == 1:
        if pidx < len(plus):
            ans *= plus[pidx]
            ans %= mod
            k -= 1
            pidx += 1
        else:
            print(0)
            exit()
    elif k == 2:
        if midx < len(pair) and pidx+1 < len(plus):
            if pair[midx] >= plus[pidx]*plus[pidx+1]:
                ans *= pair[midx]
                ans %= mod
            else:
                ans *= plus[pidx]*plus[pidx+1]
                ans %= mod

        elif midx <= len(pair):
            ans *= pair[midx]
            ans %= mod
        else:
            ans *= plus[pidx]*plus[pidx+1]
            ans %= mod
        
        break
    elif k >= 3:
        if midx < len(pair):
            if pidx+2 < len(plus): #max-2がある
                if pair[midx] >= plus[pidx+1]*plus[pidx+2]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            elif pidx+1 < len(plus): #max-1がある
                if pair[midx] >= plus[pidx]*plus[pidx+1]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            elif pidx < len(plus): #maxしかない
                if pair[midx] >= plus[pidx]:
                    ans *= pair[midx]
                    ans %= mod
                    midx += 1
                    k -= 2
                else:
                    ans *= plus[pidx]
                    ans %= mod
                    pidx += 1
                    k -= 1
            else: #plusにない
                ans *= pair[midx]
                ans %= mod
                midx += 1
                k -= 2

                
        else:
            ans *= plus[pidx]
            ans %= mod
            pidx += 1
            k -= 1

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush

MOD = int(1e9+7)


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    pos = []
    neg = []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a > 0:
            pos.append(a)
    numzero = N - len(neg) - len(pos)
    if len(pos) + len(neg) < K:
        print(0)
        return
    if K % 2 == 1 and len(neg) == N:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD
        print(ans)
        return
    elif K % 2 == 1 and len(pos) == 0:
        print(0)
        return
    q = []
    for i in range(len(pos)):
        heappush(q, [-pos[i], "p"])
    for i in range(len(neg)):
        heappush(q, [neg[i], "n"])
    ans = 1
    is_positive = True
    prevneg = 0
    poshistory = []
    while K and len(q):
        num, posneg = heappop(q)
        if K == 1 and not is_positive:
            if posneg == "p" and len(poshistory) < 2:
                poshistory.append(-num)
            elif posneg == "n":
                if len(poshistory) == 2 and prevneg * num < poshistory[0] * poshistory[1]:
                    ans = (ans * poshistory[0] * poshistory[1]) % MOD
                else:
                    ans = (ans * -num) % MOD
                print(ans)
                return
            continue
        ans = (ans * -num) % MOD
        K -= 1
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
    if K != 0:
        ans = (ans * poshistory[0] * poshistory[1]) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

mod = 10**9 + 7

Am, Ap = [], []
pm = [0, 0, 0]
Flag = True

for x in A:
  if x < 0:
    Am.append(-x)
    pm[0] += 1
  elif x == 0:
    pm[1] += 1
  else:
    Ap.append(x)
    pm[2] += 1

Am.sort()
Ap.sort()
ans = 1

if N-K < pm[1]:
  print(0)
  exit()

if pm[0] == N:
  for i in range(K):
    ans *= Am[i]
    ans %= mod
  ans *= (-1)
  print(ans%mod)
  exit()

Bm = sorted(zip(Am, [1]*pm[0]))
Bp = sorted(zip(Ap, [0]*pm[2]))

B = Bm + Bp
B.sort(reverse = True)
cnt = 0

for i in range(K):
  if i == K-1:
    cnt %= 2
    if cnt != B[i][1]:
      break
    else:
      ans *= B[i][0]
      ans %= mod
      print(ans)
      exit()
  else:
    ans *= B[i][0]
    ans %= mod
    cnt += B[i][1]

ans1 = ans
ans2 = ans * B[K][0] % mod

mcnt1 = 0
for i in range(K, N-pm[1]):
  if B[i][1] == cnt:
    mcnt1 += 1
    ans1 *= B[i][0]
    ans1 %= mod
    break

#mcnt2 = 0
for i in range(K-1, -1, -1):
  if B[i][1] == cnt:
    #mcnt2 += 1
    r = pow(B[i][0], mod-2, mod)
    ans1 *= r
    ans1 %= mod
    break

if mcnt1 == 1:
  print(max(ans1, ans2))
else:
  print(ans2)

Submission status: Runtime Error

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

ans = 1

p_list, m_list = [], []
for i in a:
    if i<0: m_list.append(i)
    elif i>0: p_list.append(i)
    else: zero_flag = True

n = len(p_list)+len(m_list)

if n<k:
    print(0)
    sys.exit()
if k==n:
    for i in p_list:
        ans *= i
        ans %= mod
    for i in m_list:
        ans *= i
        ans %= mod
    print(ans)
    sys.exit()

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


p_num, m_num = len(p_list)-1, 0

while k>0:
    p_mul, m_mul = 0, 0
    
    if k==3:
        if m_mul+1<len(m_list) and p_mul+1==2:
            m_mul = m_list[m_num]*m_list[m_num+1]*p_list[p_num]
            p_mul = p_list[p_num]*p_list[p_num-1]*m_list[m_num]
            if p_mul>m_mul:
                ans *= p_mul
                ans %= mod 
            else:
                ans *= m_mul
                ans %= mod
        elif m_mul+1<len(m_list) and p_mul+1<len(p_list):
            m_mul = m_list[m_num]*m_list[m_num+1]*p_list[p_num]
            p_mul = p_list[p_num]*p_list[p_num-1]*m_list[m_num]
            mm_mul = p_list[p_num]*p_list[p_num-1]*p_list[p_num-2]
            if p_mul>m_mul and p_mul>mm_mul:
                ans *= p_mul
                ans %= mod 
            elif m_mul>p_mul and m_mul>mm_mul:
                ans *= m_mul
                ans %= mod
            else:
                ans *= mm_mul
                ans %= mod
            break
    if k==1:
        if p_num<0:
            if zero_flag:
                print(0)
                sys.exit()
        ans *= p_list[p_num]
        ans %= mod
        break
    if m_mul+1<len(m_list):
        m_mul = m_list[m_num]*m_list[m_num+1]
    if p_mul+1<len(p_list):
        p_mul = p_list[p_num]*p_list[p_num-1]
    if p_mul>m_mul:
        ans *= p_mul
        ans %= mod
        p_num -= 2
    else:
        ans *= m_mul
        ans %= mod
        m_num += 2
    k -= 2
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

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

    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        l = 0
        r = -1
        mlt1 = a[0] * a[1]
        mlt2 = a[-2] * a[-1]
        for _ in range(k//2):
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                l += 2
                mlt1 = a[l+1] * a[l]
            else:
                ret *= mlt2 % mod
                r -= 2
                mlt2 = a[r-1] * a[r]
            ret %= mod

        if k % 2 == 1:
            ret *= a[-1]
            ret %= mod

    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    mp = sum([int(a<=0) for a in A])
    pl = True
    if (N == K):
        if mp%2 == 0:     pl = True
        else:     pl = False
    if (mp == N):
        if K%2 == 0: pl = True
        else: pl = False

    absA = sorted(A, key=abs)
    sA = deque(absA)
    ans = 1
    if pl:
        for i in range(K):
            ans*= sA.pop()
            # print(ans)
        if ans<0:
            pre=absA[i]
            prei = i
            while((i!=N) or (absA[i] * pre)>0 ): i+=1
            if i==N:
                pre = avsA[prei+1]
                i = prei-1
                while( (i!=-1) or (absA[i]*pre)>0 ): i-=1
                if i == -1: raise
            ans//= absA[i]
            ans*= pre

        print(ans%MOD)



    else:
        for i in range(K):
            ans*= sA.popleft()
        print(ans%MOD)


    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:
# 
import sys

from sys import stdin
input = lambda: stdin.readline().rstrip()


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

tl = []
for A in map(int,input().split()):
    tl.append((abs(A), A > 0))

tl.sort()
l = list(reversed(tl))

f = True
answer = 1
M = 10**9 + 7

last_Posi_idx = -1
last_Nega_idx = -1

answers = []
for i in range(K):
    A, F = l[i]
    answers.append(A)
    f = f == F
    if F:
        last_Posi_idx = i
    else:
        last_Nega_idx = i

# end with positive
if f:
    answer = 1
    for num in answers:
        answer = answer * num % M
    print(answer)
    exit()

alt_p_answer = -1
alt_n_answer = -1

alt_p = 'NOTFOUND'
alt_n = 'NOTFOUND'

# alt p
if last_Posi_idx > -1:
    for i in range(K,len(l)):
        A, F = l[i]
        if not F:
            alt_p = A
    if alt_p != 'NOTFOUND':
        alt_p_answer = 1
        for i in range(answers):
            num = answers[i] if i != last_Posi_idx else alt_p
            alt_p_answer = alt_p_answer * num % M

if last_Nega_idx > -1:
    for i in range(K,len(l)):
        A, F = l[i]
        if F:
            alt_n = A
    if alt_n != 'NOTFOUND':
        alt_n_answer = 1
        for i in range(answers):
            num = answers[i] if i != last_Posi_idx else alt_p
            alt_p_answer = alt_p_answer * num % M

if alt_p == alt_n:
    answer = 1
    for i in range(K):
        A, F = tl[i]
        answer = answer * A
    print(answer * -1 % M)
else:
    answer = max(alt_n_answer, alt_p_answer)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10**9+7
M = []
P = []
Z = []
for i in a:
    if i < 0:
        M.append(i)
    elif i > 0:
        P.append(i)
    else:
        Z.append(i)
P.sort(reverse=True)
M.sort()
lenZ = len(Z)
lenM = len(M)
lenP = len(P)
if n - k < lenZ:
    print(0)
    exit()
elif lenZ != 0 and n - k == lenZ and lenM % 2 == 1:
    print(0)
    exit()
elif n - k == lenZ:
    ans = 1
    for i in P:
        ans*=i
        ans%=MOD
    for i in M:
        ans*=i
        ans%=MOD
    if lenZ != 0 and lenM % 2 == 1: #必要ないと思うけど頭の中がこんがらがって居るので一応
        print(0)
        exit()
    print(ans)
    exit()
elif lenP == 0:
    M = M[::-1]
    ans = 1
    for i in range(k):
        ans*=M[i]
        ans%=MOD
    print(ans)
    exit()
count = 0
ans = []
i = 0
j = 0
if k % 2 == 1:
    ans.append(P[0])
    i+=1
    k-=1
    if k == 0:
        print(P[0])
        exit()
k //= 2
while count < k:
    if i+2>lenP and j+2<=lenM:
        ans.append(M[j]*M[j+1])
        j+=2
        count+=1
        continue
    if j+2>lenM and i+2<=lenP:
        ans.append(P[i]*P[i+1])
        i+=2
        count+=1
        continue
    if i+2>lenP and j+2 > lenM:
        print(0)
        exit()
    p = P[i]*P[i+1]
    m = M[i]*M[i+1]
    if p > m:
        ans.append(p)
        i+=2
        count+=1
    else:
        ans.append(m)
        j+=2
        count+=1

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=[]

chkm=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])
    else: a.append([0,0])
a=sorted(a,reverse=True)

if chkm==1:
    ans=1
    for i in range(k):
        ans=ans*a[n-1-i][0]%mod
    if ans==0: print(0)
    else: 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
    else: ans=0

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!=-1) else 0
y=1 if (lm and newp!=-1) 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
else: ans=0
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:
n, k = map(int,input().split())
li = list(map(int,input().split()))
x = [] #正の数
y = [] #負の数
ans = 0

for i in li:
    if i > 0:
        x.append(i)
    else:
        y.append(i)

if len(y)==0:
    x.sort(reverse=True)
    for i in range(k-1):
        x[i+1] *= x[i]
    print(x[k-1]%(10**9+7))
    exit()

if len(x)==0 and k%2==1:
    y.sort(reverse=True)
    for i in range(k-1):
        y[i+1] *= y[i]
    print(y[k-1]%(10**9+7))
    exit()

#以下、どちらにも要素がある場合
x.sort(reverse=True)
y.sort()

for i in range(len(x)-1):
    x[i+1] = x[i]*x[i+1]
for i in range(len(y)-1):
    y[i+1] = y[i]*y[i+1]

x.insert(0, 1)
y.insert(0, 1)

for i in range(n-len(x), min(len(y),k)+1): #iは負の数を使う数
    if i%2==1: #奇数なら
        continue
    else:
        m = y[i]*x[k-i]
        if m > ans:
            ans = m

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

Submission status: Runtime Error

Solution code:
from math import log
from math import e

n, k = map(int, input().split())
c = [int(i) for i in input().split()]
a = []
b = []
for i in c:
    if i >= 0:
        a.append(i)
    else:
        b.append(i)
a.sort()
a.reverse()
b.sort()
p = [0] * (len(a)+1)
m = [0] * (len(b)+1)

for i in range(len(a)):
    p[i+1] = p[i] + log(a[i])
for i in range(1, len(b)+1):
    if i == 1:
        m[i] = log(-b[-1])
    elif i%2:
        m[i] = m[i-2] + log(-b[-i+1]) + log(-b[-i])
    else:
        m[i] = m[i-2] + log(-b[i-2]) + log(-b[i-1])

ans = 0
ind = 0
for i in range(len(p)):
    if k-i >= 0 and k-i<len(m):
        if ans < p[i]+m[k-i]:
            ans = p[i]+m[k-i]
            ind = i

res = 1
for i in range(ind):
    res *= a[i]
if (k-ind)%2:
    for i in range(k-ind):
        res *= b[-i-1]
else:
    for i in range(k-ind):
        res *= b[i]
print(res%1000000007)

Submission status: Runtime Error

Solution code:
MOD = 1000000007

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

A.sort(key=lambda x: abs(x))

neg = []
pos = []
zero = 0

for i in range(N):
    if A[i] > 0:
        pos.append(A[i])
    elif A[i] < 0:
        neg.append(A[i])
    else:
        zero += 1

res = 1
sign = 1

for i in range(K):
    res *= A[~i]
    res %= MOD
    if A[~i] < 0:
        sign *= -1

    if A[~i] == 0:
        sign = 0

if sign == 1:
    print(res % MOD)

elif sign == 0:
    print(0)

else:
    flag1 = False
    tmp1 = -1
    minneg = None
    for i in range(K):
        if A[~i] < 0:
            minneg = ~i
    maxpos = None
    for i in range(N - K):
        if A[i] > 0:
            flag1 = True
            maxpos = i
    if maxpos is not None:
        tmp1 *= A[maxpos]
        tmp1 /= A[minneg]
    flag2 = False
    tmp2 = -1
    minpos = None
    for i in range(K):
        if A[~i] > 0:
            flag2 = True
            minpos = ~i
    maxneg = None
    for i in range(N - K):
        if A[i] < 0:
            maxneg = i
    if maxneg is not None and minpos is not None:
        tmp2 *= A[maxneg]
        tmp2 /= A[minpos]
    if flag1 and flag2:
        if A[maxpos] * A[minpos] > A[maxneg] * A[minneg]:
            print(res * A[maxpos] * pow(A[minneg], MOD - 2, MOD) % MOD)
        else:
            print(res * A[maxneg] * pow(A[minpos], MOD - 2, MOD) % MOD)
    elif flag1:
        print(res * A[maxpos] * pow(A[minneg], MOD - 2, MOD) % MOD)
    elif flag2:
        print(res * A[maxneg] * pow(A[minpos], MOD - 2, MOD) % MOD)
    else:
        if zero:
            print(0)
        else:
            res = 1
            for i in range(K):
                res *= A[i]
                res %= MOD
            print(res % MOD)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
zero=a.count(0)
a=[x for x in a if x!=0]
a.sort()
res=1
cnt=0
p=1000000007
while 1:
  #print(a,res)
  if cnt==k:
    break
  if len(a)==1:
    res =res*a[0]
    cnt+=1
    break
  if a[-1] < 0:
    res *= a[-1]
    cnt += 1
    a.pop(-1)
    continue
  tmp_a = res * a[0]*a[1] % p
  tmp_b = res * a[-1] % p
  if tmp_b > tmp_a:
    res = tmp_b
    cnt += 1
    a.pop(-1)
  elif cnt < k-1:
    res = tmp_a
    cnt += 2
    a.pop(0)
    a.pop(0)
  else:
    res = tmp_b
    cnt+=1
    break
if cnt < k and zero >0:
  res=0
print(res%p)

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)

    if len(p) == 0 and len(z) == 0 and K%2 == 1: #答えが負
        m = sorted(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:
            p.sort(reverse=True)
            m.sort()
            ans = 1
            itr = 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:
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 0<=midx<len(minus)-1:
        nexmin=minus[midx]*minus[midx+1]
    elif midx==len(minus)-1:
        nexmin=minus[midx]
    else:
        nexmin=-1


    if 0<=pidx<len(plus)-1:
        nexplus=plus[pidx]*plus[pidx+1]
    elif pidx==len(plus)-1:
        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()))
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]
        ans%=mod
elif k==1:
    ans=p[-1]
elif len(m)==1:
    if n==k:
        for i in range(len(p)):
            ans*=p[i]
            ans%=mod
        ans%m[-1]
    else:
        for i in range(k):
            ans*=p[i]
            ans%=mod
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:
import sys
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
mod = 10**9+7
T = {"mi":0, "pu":0, "zero":0}
M = []
P = []
for i in range(N):
    if A[i] < 0:
        T["mi"] += 1
        M.append(A[i])
    elif A[i] == 0:
        T["zero"] += 1
    else:
        T["pu"] += 1
        P.append(A[i])

M.sort(reverse=True)
ans = 1
if K > T["pu"]+T["mi"]:
    print(0)
    sys.exit()
if T["mi"] == 1 and K > T["pu"]:
    for i in range(N):
        ans *= A[i]
        ans %= mod
    if T["zero"] != 0:
        ans = 0
    print(ans)
    sys.exit()
if T["pu"] == 0:
    if K % 2 == 1:
        for i in range(K):
            ans *= A[i]
            ans %= mod
        if T["zero"] != 0:
            ans = 0
    else:
        for i in range(K):
            A.sort()
            ans *= A[i]
            ans %= mod
    print(ans)
    sys.exit()

i = 0
j = 0
while(True):
    if K == 0:
        break
    if K == 1:
        ans *= P[i]
        ans %= mod
        break
    if i + 1 >= len(P) and j + 1 >= len(M):
        ans *= P[i]*M[j]
        ans %= mod
        break
    elif i + 1 >= len(P):
        ans *= M[j]*M[j+1]
        ans %= mod
        j += 2
        K -= 2
    elif j + 1 >= len(M):
        ans *= P[i]*P[i+1]
        ans %= mod
        i += 2
        K -= 2
    elif P[i]*P[i+1] >= M[j]*M[j+1]:
        ans *= P[i]*P[i+1]
        ans %= mod
        i += 2
        K -= 2
    else:
        ans *= M[j]*M[j+1]
        ans %= mod
        j += 2
        K -= 2
if ans < 0 and T["zero"] != 0:
    ans = 0
print(ans)