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:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
negatives = []
num_zero = 0
positives = []
for a in A:
    if a < 0:
        negatives.append(a)
    elif a == 0:
        num_zero += 1
    else:
        positives.append(a)
negatives.sort(reverse=True)
positives.sort(reverse=True)

n = 0
while n + 2 <= len(negatives) and n + 2 <= K:
    n += 2
answer_is_positive = K - n <= len(positives)
if answer_is_positive:
    others = []
    if K <= len(positives):
        nums = positives[-K:]
    else:
        if (K - len(positives)) % 2 == 0:
            nums = positives[:]
        else:
            nums = positives[:-1]
        while len(nums) + len(others) < K:
            n1 = negatives.pop()
            n2 = negatives.pop()
            others.extend([n1, n2])

    while True:
        if not (2 <= len(negatives) and 2 <= len(positives)):
            break
        p1, p2 = nums[-1], nums[-2]
        n1, n2 = negatives.pop(), negatives.pop()
        if n1 * n2 <= p1 * p2:
            break
        others.extend([n1, n2])
        nums.pop()
        nums.pop()
    ans = 1
    for x in nums + others:
        ans = ans * x % MOD
elif K <= len(negatives) + len(positives):
    negatives.sort()
    nums = [negatives.pop()]
    while 2 <= len(negatives) and len(nums) + 2 <= K:
        nums.extend([negatives.pop(), negatives.pop()])
    nums.sort()
    others = []
    while len(nums) < K:
        others.append(positives.pop())

    while True:
        if not (2 <= len(nums) and 2 <= len(positives)):
            break
        p1, p2 = positives[-1], positives[-2]
        n1, n2 = nums[-1], nums[-2]
        if n1 * n2 <= p1 * p2:
            break
        others.extend([p1, p2])
        nums.pop()
        nums.pop()
    ans = 1
    for x in nums + others:
        ans = ans * x % MOD
else:
    ans = 0

if 0 < num_zero and ans < 0:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ans=set()
if 0 in ls:
  ans.add(0)
else:
  als=sorted(ls, key=lambda x: -abs(x))
  mul=1
  for i in range(K):
    mul*=als[i]
  if mul>0:
    ans.add(mul)
  else:
    ls2=als[:K]
    ls3=als[K:]
    M2=max(ls2)
    m2=min(ls2)
    M3=max(ls3)
    m3=max(ls3)
    ans=set()
    if M2!=0:
      ans.add(mul*m3//M2)
      ans.add(mul*m3//m2)
    if m2!=0:
      ans.add(mul*M3//M2)
      ans.add(mul*M3//m2)
print(max(ans)%MOD)

Submission status: Runtime Error

Solution code:
mod = 10**9+7

import sys
input = sys.stdin.buffer.readline

def main():

    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    P = []
    N = []

    for a in A:
        if a >= 0:
            P.append(a)
        else:
            N.append(a)
    P.sort(reverse=True)
    N.sort()
    #print(P)
    #print(N)

    if len(P) == 0:
        if k%2 == 0:
            N.sort()
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
        else:
            N.sort(reverse=True)
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
        print(ans)
        exit()

    if len(P) == 1:
        if k%2 == 0:
            N.sort()
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
        else:
            ans = P[0]
            N.sort(reverse=True)
            for i in range(k-1):
                ans *= N[i]
                ans %= mod
        print(ans)
        exit()


    if len(N) == 0:
        ans = 1
        for i in range(k):
            ans *= P[i]
            ans %= mod
        print(ans)
        exit()

    if len(N) == 1:
        if len(P) >= k:
            ans = 1
            for i in range(k):
                ans *= P[i]
                ans %= mod
            print(ans)
            exit()
        else:
            print(N[0])
            exit()

    import heapq
    if k%2 == 0:
        P_ = []
        N_ = []
        if len(P) != 1:
            for i in range(len(P)):
                if i%2 == 1:
                    continue
                P_.append(-P[i]*P[i+1])
            for i in range(len(N)):
                if i%2 == 1:
                    continue
                N_.append(-N[i]*N[i+1])
            heapq.heapify(P_)
            heapq.heapify(N_)
            q = k//2
            ans = 1
            for i in range(q):
                if P_:
                    x = heapq.heappop(P_)*(-1)
                else:
                    x = -1
                if N_:
                    y = heapq.heappop(N_)*(-1)
                else:
                    y = -1
                if x >= y:
                    ans *= x
                    if y >= 0:
                        heapq.heappush(N_, y*(-1))
                else:
                    ans *= y
                    if x >= 0:
                        heapq.heappush(P_, x*(-1))
        else:
            ans = 1
            for i in range(k):
                ans *= N[i]
                ans %= mod
    else:
        p = P[0]
        P = P[1:]
        P_ = []
        N_ = []
        if len(P) != 1:
            for i in range(len(P)):
                if i%2 == 1:
                    continue
                P_.append(-P[i]*P[i+1])
            for i in range(len(N)):
                if i%2 == 1:
                    continue
                N_.append(-N[i]*N[i+1])
            heapq.heapify(P_)
            heapq.heapify(N_)
            q = k//2
            ans = p
            for i in range(q):
                if P_:
                    x = heapq.heappop(P_)*(-1)
                else:
                    x = -1
                if N_:
                    y = heapq.heappop(N_)*(-1)
                else:
                    y = -1
                if x >= y:
                    ans *= x
                    if y >= 0:
                        heapq.heappush(N_, y*(-1))
                else:
                    ans *= y
                    if x >= 0:
                        heapq.heappush(P_, x*(-1))
        else:
            ans = p
            for i in range(k):
                ans *= N[i]
                ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

plus = []
minus = []

for a in Alist:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)

mflg = False

if K%2!=0:
    tmp1 = K-1
else:
    tmp1 = K

if len(minus)%2!=0:
    tmp2 = len(minus)-1
else:
    tmp2 = len(minus)

tmp = min(tmp1, tmp2)
if K - tmp > len(plus):
    mflg = True


if mflg:
    minus = [-m for m in minus]
    nums = minus + plus
    nums.sort()
    ans = 1
    for k in range(K):
        ans = ans * nums[k]
        ans %= (1000000007)
    
    ans = (-ans % 1000000007)
    print(ans)

else:
    plus.sort()
    minus.sort()
    plus = plus[::-1]
    minus = [-m for m in minus]

    for k in range(0, len(minus)+1, 2):
        if K - k > len(plus):
            continue
        km = k
        kp = K - k
        break

    m = plus[:km]
    p = plus[:kp]
    ans = 1
    for i in p+m:
        ans *= i
    
    for k in range(km+2, len(minus)+1, 2):
        kp = K - k
        tmp = tmp * minus[k-2:k] / plus[kp:kp+2]
        ans = max(ans, tmp)
    
    ans %= 1000000007
    print(ans)

Submission status: Runtime Error

Solution code:
PRIME = 10 ** 9 + 7

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

_a = sorted(a,key=abs,reverse=True)

ans = 1
if n == k:
  for i in range(k):
    ans = (ans * _a[i]) % PRIME
else:
  minus_n = 0
  minus_k = 0
  zero = 0
  min_minus = -1
  min_plus = -1
  max_minus = -1
  min_plus = -1
  
  for i in range(n):
    if _a[i] < 0:
      minus_n += 1
      if i < k:
        minus_k += 1
        min_minus = i
      else:
        max_minus = i
    elif _a[i] == 0:
      zero += 1
    elif i < k:
      min_plus = i
    else:
      max_plus = i
  
  if minus_n + zero == n and k % 2 == 1:
    for i in range(1, k + 1):
      ans = (ans * _a[-i]) % PRIME
  elif minus_k % 2 == 0:
    for i in range(k):
      ans = (ans * _a[i]) % PRIME
  elif max_plus >= 0 and (min_plus < 0 or max_minus < 0 or abs(a[max_minus] / a[min_plus]) < abs(a[max_plus] / a[min_minus])):
    for i in range(k):
      if i != min_minus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_plus]) % PRIME
  else:
    for i in range(k):
      if i != min_plus:
        ans = (ans * _a[i]) % PRIME
    ans = (ans * _a[max_minus]) % PRIME
    
print(ans)

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    print(-ans % mod)
    exit()
print(0/0)
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans%mod)
    exit()
if n==k:
    print(-ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Runtime Error

Solution code:
A = list(map(int,input().split()))
mod = 10**9 + 7
A1 = []  
A2 = []
for i in range(N):
    if A[i] > 0:
        A1.append(A[i])
    if A[i] < 0:
        A2.append(-A[i])
A1.sort(reverse=True)
A2.sort(reverse=True)
ans = 1
if max(A)< 0:
    if K%2 == 0:
        for i in range(K):
            ans = (ans * A2[i])%mod
    else:
        A2.sort()
        for i in range(K):
            ans = (ans * A2[i])%mod
            ans = (mod - ans)%mod
elif max(A) == 0:
    if K%2 == 1:
        ans = 0
    else:
        if len(A2) >= K:
            for i in range(K):
                ans = (ans * A2[i])%mod
        else:
            ans = 0
else:
    A3 = []
    for i in range(len(A2)//2):
        A3.append(A2[2 * i] * A2[2 * i + 1])
    A4 = []
    A5 = []
    for i in range(len(A1)//2):
        A4.append(A1[2 * i] * A1[2 * i + 1])
    for i in range((len(A1) - 1)//2):
        A5.append(A1[2 * i + 1] * A1[2 * i + 2])
    if len(A1) + 2 * len(A3) < K:
        if N == K:
            for i in range(N):
                ans = (ans * A[i])%mod
        else:
            ans = 0
    else:
        if K%2 == 0:
            A6 = A3 + A4
            A6.sort(reverse=True)
            for i in range(K//2):
                ans = (ans * A6[i])%mod
        else:
            A6 = A3 + A5
            A6.sort(reverse=True)
            ans = A1[0]
            for i in range((K - 1)//2):
                ans = (ans * A6[i])% mod
print(ans)

Submission status: Runtime Error

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

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

ans = 1
if k > len(plus) + len(minus):
    ans = 0
elif len(minus) == 0:
    plus.sort(reverse=True)
    for i in range(k):
        ans = (ans * plus[i]) % mod
elif len(plus) == 0:
    if k % 2 == 0:
        minus.sort()
        for i in range(k):
            ans = (ans * minus[i]) % mod
    else:
        minus.sort(reverse=True)
        for i in range(k):
            ans = (ans * minus[i]) % mod
elif k == len(plus) + len(minus) and (len(minus) % 2) == 1:
    if n != len(plus) + len(minus):
        ans = 0
    else:
        for x in plus:
            ans = (ans * x) % mod
        for y in minus:
            ans = (ans * y) % mod
else:
    plus.sort(reverse=True)
    minus.sort()
    i, j = 0, 0
    if k % 2 == 1:
        ans = plus[0]
        i = 1
    while i + j < k:
        tmp_p = plus[i] * plus[i + 1] if i <= len(plus) - 2 else 1
        tmp_m = minus[j] * minus[j + 1] if j <= len(plus) - 2 else 1
        if tmp_p >= tmp_m:
            ans = (ans * (tmp_p % mod)) % mod
            i += 2
        else:
            ans = (ans * (tmp_m % mod)) % mod
            j += 2
print(ans)

Submission status: Runtime Error

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

cnt = [0, 0]
for a in A:
    if 0 <= a:
        cnt[1] += 1
    else:
        cnt[0] += 1

if (k-cnt[1]) % 2 == 0:
    can_positive = 1
else:
    can_positive = 0

if can_positive:
    pos = []
    neg = []
    for a in A:
        if 0 <= a:
            pos.append(a)
        else:
            neg.append(a)
    pos.sort()
    neg.sort()
    neg_pair = []
    for a, b in zip(neg, neg[1:]):
        neg_pair.append(a*b)
    neg_pair.reverse()
    use = []
    cnt = 0
    while cnt != k:
        if 2 <= k-cnt:
            if neg_pair and 2 <= len(pos):
                if neg_pair[-1] < pos[-1]*pos[-2]:
                    cnt += 2
                    use.append(pos.pop())
                    use.append(pos.pop())
                else:
                    cnt += 2
                    use.append(neg_pair.pop())
            elif neg_pair:
                cnt += 2
                use.append(neg_pair.pop())
            else:
                cnt += 2
                use.append(pos.pop())
                use.append(pos.pop())
        else:
            a = pos.pop()
            cnt += 1
            use.append(a)

    ans = use[0]
    for a in use[1:]:
        ans *= a
        ans %= MOD
    print(ans)
else:
    pos = []
    neg = []
    for a in A:
        if 0 <= a:
            pos.append(a)
        else:
            neg.append(a)
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    use = [neg[0]]
    neg_pair = []
    for a, b in zip(neg[1:], neg[2:]):
        neg_pair.append(a*b)
    neg_pair.reverse()
    cnt = 1
    while cnt != k:
        if 2 <= k-cnt:
            if neg_pair and 2 <= len(pos):
                if neg_pair[-1] > pos[-1]*pos[-2]:
                    cnt += 2
                    use.append(pos.pop())
                    use.append(pos.pop())
                else:
                    cnt += 2
                    use.append(neg_pair.pop())
            elif neg_pair:
                cnt += 2
                use.append(neg_pair.pop())
            else:
                cnt += 2
                use.append(pos.pop())
                use.append(pos.pop())
        else:
            a = pos.pop()
            cnt += 1
            use.append(a)

    ans = use[0]
    for a in use[1:]:
        ans *= a
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import sys

input = sys.stdin.readline

def main(args):
    n, k = map(int,input().split())
    A = list(map(int,input().split()))
    
    A.sort()
    
    minus = bisect.bisect_right(A, -1)
    zeros = bisect.bisect_right(A, 0) - minus
    plus = n - (minus+zeros)
    
    mA = A[:minus]
    pA = A[minus+zeros:]
    
    mod = 10**9+7
    #print("pArev",pA[::-1])
    #print("mA",mA)
    
    #正の値が一個もないとき
    if plus == 0:
        if k%2 == 1:#負の数を奇数個とらなきゃならないとき
            if zeros > 0:#ゼロがあれば
                print(0)
            else:#ゼロがないとき
                ans = 1
                for i in range(k):
                    ans = ans*mA[-(i+1)]%mod
                print(ans)
        else:#負の数を偶数個とらなきゃならないとき
            ans = 1
            for i in range(k):
                ans = ans*mA[i]%mod
            print(ans)
    else:#正の値が一個でもあれば
        pickm = 0#マイナスからとってきた個数
        pickp = 0#プラスからとってきた個数
        indm = 0
        indp = 0
        pA.sort(reverse=True)
        ans = 1
        if minus > 0:
            if k%2 == 1:#正から必ず奇数個とるとき
                while pickm+pickp < k:
                    if pickm+pickp == k-1 and pickp%2 == 0:
                        ans = ans*pA[indp]%mod
                        break
                    if abs(pA[indp]) > abs(mA[indm]):
                        ans = ans*pA[indp]%mod
                        indp += 1
                        pickp += 1
                    else:
                        ans = ans*mA[indm]%mod
                        indm += 1
                        pickm += 1
            else:#正から必ず偶数個（０含む）とるとき
                while pickm+pickp < k:
                    if pickm+pickp == k-1:
                        if pickp%2 == 0:
                            ans = ans*mA[indm]%mod
                            break
                        else:
                            ans = ans*pA[indp]%mod
                            break
                    if abs(pA[indp]) > abs(mA[indm]):
                        ans = ans*pA[indp]%mod
                        indp += 1
                        pickp += 1
                    else:
                        ans = ans*mA[indm]%mod
                        indm += 1
                        pickm += 1
        else:
            if plus < k:
                print(0)
            else:
                ans = 1
                for i in range(k):
                    ans = ans*pA[i]%mod
        print(ans%mod)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Runtime Error

Solution code:
N,K = (int(x) for x in input().split())
A = [int(x) for x in input().split()]

X = sorted(A, key=lambda x: abs(x), reverse=True)
B = X
C = [0]*N

for i in range(N):
    if X[i] > 0:
        C[i] = 1
    elif X[i] < 0:
        B[i] = X[i] * (-1)
        C[i] = -1

hi = 0
score = 1

for j in range(K):
    score *= B[j]
    if C[j] == -1:
        hi += 1
        x = B[j]

if hi % 2 == 1:
    flg = 0
    for j in range(K,N):
        if C[j] == 1:
            score = score / x * B[j]
            flg = 1
            break
    if flg == 0:
        score = 1
        A = sorted(A, key=lambda x: abs(x))
        for j in range(K):
            score *= A[j]

print(int(score % (10**9 + 7)))

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

elif len(p)==1:
    if n==k:
        for i in range(len(m)):
            ans*=m[i]
            ans%=mod
        ans%p[-1]
    elif k%2==0:
        for i in range(k):
            ans*=m[i]
            ans%=mod
    else:
        for i in range(k-1):
            ans*=m[i]
            ans%=mod
        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:
MOD=10**9+7
import bisect
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ans=set()
if 0 in ls:
  ans.add(0)
else:
  als=sorted(ls, key=lambda x: -abs(x))
  mul=1
  for i in range(K):
    mul*=als[i]
  if mul>0:
    ans.add(mul)
  else:
    ls2=als[:K]
    ls3=als[K:]
    M2=max(ls2)
    m2=min(ls2)
    M3=max(ls3)
    m3=max(ls3)
    ans=set()
    if M2!=0:
      ans.add(mul*m3//M2)
      ans.add(mul*m3//m2)
    if m2!=0:
      ans.add(mul*M3//M2)
      ans.add(mul*M3//m2)
print(max(ans)%MOD)

Submission status: Runtime Error

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

cnt = [0, 0]
for a in A:
    if 0 <= a:
        cnt[1] += 1
    else:
        cnt[0] += 1

if (k-cnt[1]) % 2 == 0:
    can_positive = 1
else:
    can_positive = 0

if can_positive:
    print('pos')
    pos = []
    neg = []
    for a in A:
        if 0 <= a:
            pos.append(a)
        else:
            neg.append(a)
    pos.sort()
    neg.sort()
    neg_pair = []
    for a, b in zip(neg, neg[1:]):
        neg_pair.append(a*b)
    neg_pair.reverse()
    use = []
    cnt = 0
    while cnt != k:
        if 2 <= k-cnt:
            if neg_pair and 2 <= len(pos):
                if neg_pair[-1] < pos[-1]*pos[-2]:
                    cnt += 2
                    use.append(pos.pop())
                    use.append(pos.pop())
                else:
                    cnt += 2
                    use.append(neg_pair.pop())
            elif neg_pair:
                cnt += 2
                use.append(neg_pair.pop())
            else:
                cnt += 2
                use.append(pos.pop())
                use.append(pos.pop())
        else:
            a = pos.pop()
            cnt += 1
            use.append(a)

    ans = use[0]
    for a in use[1:]:
        ans *= a
        ans %= MOD
    print(ans)
else:
    pos = []
    neg = []
    for a in A:
        if 0 <= a:
            pos.append(a)
        else:
            neg.append(a)
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    use = [neg[0]]
    neg_pair = []
    for a, b in zip(neg[1:], neg[2:]):
        neg_pair.append(a*b)
    neg_pair.reverse()
    cnt = 1
    while cnt != k:
        if 2 <= k-cnt:
            if neg_pair and 2 <= len(pos):
                if neg_pair[-1] > pos[-1]*pos[-2]:
                    cnt += 2
                    use.append(pos.pop())
                    use.append(pos.pop())
                else:
                    cnt += 2
                    use.append(neg_pair.pop())
            elif neg_pair:
                cnt += 2
                use.append(neg_pair.pop())
            else:
                cnt += 2
                use.append(pos.pop())
                use.append(pos.pop())
        else:
            a = pos.pop()
            cnt += 1
            use.append(a)

    ans = use[0]
    for a in use[1:]:
        ans *= a
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
N, K =map(int,input().split())
A = list(map(int,input().split()))
A.sort()
z = 0
for i in range(0,N-1):
    if A[i]<0 and A[i+1]>0:
        P = A[i+1:][::-1]
        M = A[:i+1]
        break
    if A[N-1]<0:
        P = []
        M = A[:]
        break
    if A[0] >0:
        P=A[:]
        M=[]
MOD = 10**9+7

p = 0
m = 0
lp = None
lm = None
l = []
for i in range(K):
    if p>=len(P):
        l.append(M[m])
        lm = M[m]
        m+=1
    elif m>=len(M):
        l.append(P[p])
        lp = P[p]
        p+=1
    elif P[p] > -1*M[m]:
        l.append(P[p])
        lp = P[p]
        p+=1
    else:
        l.append(M[m])
        lm = M[m]
        m+=1
if m%2 == 0:
    ans = 1
    for i in range(K):
        ans = (ans*l[i])%MOD
    print(ans)
else:
    if p >= len(P):#+がもうない
        if lp == None:
            B = M[::-1]
            l = B[:K]
        MM = M[m]
        for i in range(0, K):
            if l[K-i-1] == lp:
                l[K-i-1] = MM
                break
    elif m >= len(M):#-がもうない
        MP = M[m]
        for i in range(0, K):
            if l[K-i-1] == lm:
                l[K-i-1] = MP
                break
    elif P[p] > -1*M[m]:
        MP = P[p]
        MM = M[m]
        if -1*lm < lp:#(i)
            if MP * lm > MM * lp:
                for i in range(0, K):
                    if l[K-i-1] == lm:
                        l[K-i-1] = MP
                        break
            else:
                for i in range(0, K):
                    if l[K-i-1] == lp:
                        l[K-i-1] = MM
                        break
        else:#(ii)
            for i in range(0, K):
                    if l[K-i-1] == lm:
                        l[K-i-1] = MP
                        break
    elif P[p] < -1*M[m]:
        MP = P[p]
        MM = M[m]
        if -1*lm < lp:#(i)
            for i in range(0, K):
                    if l[K-i-1] == lm:
                        l[K-i-1] = MP
                        break
            if MP * lm > MM * lp:
                for i in range(0, K):
                    if l[K-i-1] == lm:
                        l[K-i-1] = MP
                        break
            else:
                for i in range(0, K):
                    if l[K-i-1] == lp:
                        l[K-i-1] = MM
                        break
        else:#(ii)
            if MP * lm > MM * lp:
                for i in range(0, K):
                    if l[K-i-1] == lm:
                        l[K-i-1] = MP
                        break
            else:
                for i in range(0, K):
                    if l[K-i-1] == lp:
                        l[K-i-1] = MM
                        break
    ans = 1
    for i in range(K):
        ans = (ans*l[i])%MOD
    print(ans)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
print(A)
ans = 1
if len([v for v in A if v <= 0]) == N:
    for i in range(K):
        ans *= A[-(i + 1)]
        if abs(ans) > mod:
            ans %= mod
else:
    num_hu = len([v for v in A[:K] if v < 0])
    if num_hu % 2 == 0:
        for i in range(K):
            ans *= A[i]
            if abs(ans) > mod:
                ans %= mod
    else:
        if A[K - 1] < 0:
            if len([v for v in A[K:] if v > 0]):
                idx = K
                while True:
                    if A[idx] > 0:
                        break
                    idx += 1
                for i in range(K - 1):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[idx]
            else:
                idx = K - 2
                while True:
                    if A[idx] > 0:
                        break
                    idx -= 1
                for i in range(idx):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[K]
                for i in range(idx + 1, K):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
        else:
            if len([v for v in A[K:] if v < 0]):
                idx = K
                while True:
                    if A[idx] < 0:
                        break
                    idx += 1
                for i in range(K - 1):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[idx]
            else:
                idx = K - 2
                while True:
                    if A[idx] < 0:
                        break
                    idx -= 1
                for i in range(idx):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
                ans *= A[K]
                for i in range(idx + 1, K):
                    ans *= A[i]
                    if abs(ans) > mod:
                        ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[]
m=[]
z=0
a.sort(reverse=True)
for i in range(n):
    if a[i]>0:
        p.append(a[i])
    elif a[i]==0:
        z+=1
    else:
        m.append(a[i])
nump=len(p)
numm=len(m)
ans=1
if nump+numm<k:
    print(0)
elif numm<2 and nump>=k:
    for i in range(k):
        ans*=p[i]
        ans%=10**9+7
    print(ans)
elif 2*(numm//2)+nump<k:
    ans*=p
    if z!=0:
        print(0)
    else:
        for i in range(k):
            ans*=a[i]
            ans%=10**9+7
        print(ans)
elif  nump==0:
    print(1)
    if z!=0 and k%2==1:
        print(0)
    elif z!=0 and numm<k:
        print(0)
    else:
        if k%2==0:
            m.sort()
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        else:
            m.sort(reverse=True)
            for i in range(k):
                ans*=m[i]
                ans%=10**9+7
        print(ans)
else:
    if k%2==1:
        ans*=p[0]
    m.sort()
    nump=(nump-1)//2
    numm=numm//2
    nump1=0
    nump2=0
    numm1=0
    numm2=0
    for i in range(k//2):
        if nump2==nump:
            nump1=1
        else:
            nump1=p[nump2*2]*p[nump2*2+1]
        if numm2==numm:
            numm1=1
        else:
            numm1=m[numm2*2]*m[numm2*2+1]
        if numm1>nump1:
            num=numm1
            numm2+=1
        else:
            num=nump1
            nump2+=1
        ans*=num
        ans%=10**9+7
    print(ans)