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
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif A[-1] < 0 or A[0] >= 0:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        k = bisect.bisect_left(A, 0)
        neg = A[:k]
        pos = A[k:][::-1]
        
        n = 0
        p = 0
        while n + p < K:
            if -neg[n] <= pos[p]:
                p += 1
            else:
                n += 1
        if n % 2 == 1:
            if p == 0 or n == len(neg):
                n -= 1
                p += 1
            elif p == len(pos):
                n += 1
                p -= 1
            elif pos[p] * pos[p - 1]  <= neg[n] * neg[n - 1]:
                n += 1
                p -= 1
            else:
                n -= 1
                p += 1

        for a in pos[:p]:
            res *= a
            res %= mod
        
        for a in neg[:n]:
            res *= a
            res %= mod

    print(res % mod)

    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif A[-1] < 0:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        k = bisect.bisect_left(A, 0)
        neg = A[:k]
        pos = A[k:][::-1]
        
        n = 0
        p = 0
        while n + p < K:
            if -neg[n] <= pos[p]:
                p += 1
            else:
                n += 1
        if n % 2 == 1:
            if p == 0 or n == len(neg):
                n -= 1
                p += 1
            elif p == len(pos):
                n += 1
                p -= 1
            elif pos[p] * pos[p - 1]  <= neg[n] * neg[n - 1]:
                n += 1
                p -= 1
            else:
                n -= 1
                p += 1

        for a in pos[:p]:
            res *= a
            res %= mod
        
        for a in neg[:n]:
            res *= a
            res %= mod

    print(res % mod)

    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
def calc(A, div=1, sub=1):
    ret = 1
    for a in A:
        ret *= a
        ret %= MOD
    ret //= div
    ret *= sub
    return ret % MOD

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    minus = plus = 0
    for a in A:
        if a < 0: minus += 1
        else: plus += 1
    if minus == N and K % 2 == 1:
        # 負の値にしかならない
        A.sort(reverse=True)
        return calc(A[:K])
    # どうにかすれば0以上にはなる
    A.sort(key=lambda x:abs(x), reverse=True)
    minus = plus = 0
    for a in A[:K]:
        if a < 0: minus += 1
        else: plus += 1
    # 負の値が偶数個なら絶対値の降順が答えになる
    if minus % 2 == 0:
        return calc(A[:K])
    # 絶対値の大きい順に選択すると負の値になる場合
    minus_tmp1 = plus_tmp1 = 0
    for i in A[:K]:
        if i < 0: minus_tmp1 = i
        else: plus_tmp1 = i
    minus_tmp2 = plus_tmp2 = 1
    minus_ju = plus_ju = False
    for i in A[K:]:
        if minus_ju and plus_ju: break
        if i < 0:
            minus_tmp2 = i
            minus_ju = True
        else:
            plus_tmp2 = i
            plus_ju = True
    if plus_tmp1 * plus_tmp2 >= minus_tmp1 * minus_tmp2:
        return calc(A[:K], minus_tmp1, plus_tmp2)
    else:
        return calc(A[:K], plus_tmp1, minus_tmp2)

print(main())

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
def calc(A, div=1, sub=1):
    ret = 1
    for a in A:
        ret *= a
        ret %= MOD
    ret //= div
    ret *= sub
    return ret % MOD

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    minus = plus = 0
    for a in A:
        if a < 0: minus += 1
        else: plus += 1
    if minus == N and K % 2 == 1:
        # 負の値にしかならない
        A.sort(reverse=True)
        return calc(A[:K])
    # どうにかすれば0以上にはなる
    A.sort(key=lambda x:abs(x), reverse=True)
    minus = plus = 0
    for a in A[:K]:
        if a < 0: minus += 1
        else: plus += 1
    if minus % 2 == 0:
        return calc(A[:K])
    # 絶対値の大きい順に選択すると負の値になる場合
    minus_tmp1 = plus_tmp1 = 0
    for i in A[:K]:
        if i < 0: minus_tmp1 = i
        else: plus_tmp1 = i
    minus_tmp2 = plus_tmp2 = None
    for i in A[K:]:
        if i < 0 and minus_tmp2 == None: minus_tmp2 = i
        elif plus_tmp2 == None: plus_tmp2 = i
        elif minus_tmp2 != None and plus_tmp2 != None: break
    if plus_tmp1 * plus_tmp2 >= minus_tmp1 * minus_tmp2:
        return calc(A[:K], minus_tmp1, plus_tmp2)
    else:
        return calc(A[:K], plus_tmp1, minus_tmp2)

print(main())

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    minus = plus = 0
    for a in A:
        if a < 0: minus += 1
        else: plus += 1
    if minus == N and K % 2 == 1:
        # 負の値にしかならない
        A.sort(reverse=True)
        ans = 1
        for i in A[:K]:
            ans *= i
        return ans % MOD
    # どうにかすれば0以上にはなる
    A.sort(key=lambda x:abs(x), reverse=True)
    tmp = 1
    for i in A[:K]:
        tmp *= i
    if tmp >= 0:
        return tmp % MOD
    
    minus_tmp1 = plus_tmp1 = None
    for i in A[:K]:
        if i < 0: minus_tmp1 = i
        else: plus_tmp1 = i
    minus_tmp = plus_tmp = None
    idx = K
    while minus_tmp == None or plus_tmp == None:
        if A[idx] < 0: minus_tmp = A[idx]
        else: plus_tmp = A[idx]
        idx += 1
    return max(tmp // minus_tmp1 * plus_tmp > tmp // plus_tmp1 * minus_tmp1) % MOD

print(main())

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

# from random import randint
# n = 10
# k = 4
# A = []
# for i in range(10):
#     A.append(randint(-20,20))
# anss=0
# for i in range(n):
#     for j in range(i+1,n):
#         for ii in range(j+1,n):
#             for jj in range(ii+1,n):
#                 anss = max(anss, A[i]*A[j]*A[ii]*A[jj])
# print(anss)
# print(A)


B = [[], []]
for i in range(n):
    if A[i] >= 0:
        B[0].append(A[i])
    else:
        B[1].append(A[i])
B[0].sort(reverse=True)
B[1].sort()

if k%2==1 and len(B[0])==0:
    ans = 1
    ind = len(B[1])-1
    for i in range(k):
        ans = (ans * B[1][ind]) % mod
        ind -= 1
    print(ans)
else:
    k0 = min(len(B[0]), k)
    k1 = k-k0
    if k1%2==1:
        k0 -= 1
        k1 += 1
    # print(B,k0,k1)
    while k1+1 < len(B[1]) and k0-2 >= 0 and B[1][k1]*B[1][k1+1] > B[0][k0-1]*B[0][k0-2]:
        k1 += 2
        k0 -= 2
        # print(k0,k1)
        # print(k1+1 < len(B[1]),B[1][k1]*B[1][k1+1] , B[0][k0-1]*B[0][k0-2])
    ans = 1
    for i in range(k0):
        ans = (ans * B[0][i]) % mod
    for i in range(k1):
        ans = (ans * B[1][i]) % mod
    print(ans)

Submission status: Runtime Error

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

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

B = [[], []]
for i in range(n):
    if A[i] >= 0:
        B[0].append(A[i])
    else:
        B[1].append(A[i])
B[0].sort(reverse=True)
B[1].sort()

if k%2==1 and len(B[0])==0:
    ans = 1
    ind = len(B[1])-1
    for i in range(k):
        ans = (ans * B[1][ind]) % mod
        ind -= 1
    print(ans)
else:
    k0 = min(len(B[0]), k)
    k1 = k-k0
    if k1%2==1:
        k0 -= 1
        k1 += 1
    # print(B,k0,k1)
    if k1+1 < len(B[1]) and k0-2 >= 0 and B[1][k1]*B[1][k1+1] > B[0][k0-1]*B[0][k0-2]:
        k1 += 2
        k0 -= 2
    ans = 1
    for i in range(k0):
        ans = (ans * B[0][i]) % mod
    for i in range(k1):
        ans = (ans * B[1][i]) % mod
    print(ans)

Submission status: Runtime Error

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

for i in range(n):
  if a[i]<0:
    b.append([abs(a[i]),-1])
  if a[i]>0:
    b.append([abs(a[i]),1])
  if a[i]==0:
    b.append([0,0])

b.sort(key=lambda x:-x[0])

prod=1
p=10**9+7
for i in range(k):
  prod*=b[i][0]
  if b[i][1]<0:
    prod*=-1
  if abs(prod)>=p:
    prod%=p
    
if prod>=0:
  print(prod)
else:
  for i in range(k,-1,-1):
    if b[i][1]>0:
      prod11=b[i][0]
      break
  for i in range(k,-1,-1):
    if b[i][1]<0:
      prod21=b[i][0]
      break
      
  for i in range(k+1,n):
    if b[i][1]<=0:
      prod12=b[i][0]
      break
      
  for i in range(k+1,n):
    if b[i][1]>=0:
      prod22=b[i][0]
      break
  
  if abs(prod12*prod21)>=(prod11*prod22):
    print((prod//prod11)*prod12)
  else:
    print((prod//prod21)*prod22)

Submission status: Runtime Error

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

for i in range(n):
  if a[i]<0:
    b.append([abs(a[i]),-1])
  if a[i]>0:
    b.append([abs(a[i]),1])
  if a[i]==0:
    b.append([0,0])

a.sort(key=lambda x:-x[0])

prod=1
p=10**9+7
for i in range(k):
  prod*=b[i][0]
  if b[i][1]<0:
    prod*=-1
  if abs(prod)>=p:
    prod%=p
    
if prod>=0:
  print(prod)
else:
  for i in range(k,-1,-1):
    if b[i][1]>0:
      prod11=b[i][0]
      break
  for i in range(k,-1,-1):
    if b[i][1]<0:
      prod21=b[i][0]
      break
      
  for i in range(k+1,n):
    if b[i][1]<=0:
      prod12=b[i][0]
      break
      
  for i in range(k+1,n):
    if b[i][1]>=0:
      prod22=b[i][0]
      break
  
  if abs(prod12*prod21)>=(prod11*prod22):
    print((prod//prod11)*prod12)
  else:
    print((prod//prod21)*prod22)

Submission status: Runtime Error

Solution code:
from collections import deque
n , k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
a.sort(reverse=True)
ans = 1
plus = []
minus = []

if n == k:
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
    
for i in range(n):
    if a[i] >= 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])
if not plus and k % 2 == 1:
    minus.sort(reverse=True)
    for i in minus:
        ans *= minus
        ans %= mod
    print(ans)
    exit()
plus.sort(reverse=True)
minus.sort()
plus = deque(plus)
minus = deque(minus)
cou = []
while True:
    if len(cou) == k:
        break
    elif len(cou) == k-1:
        cou.append(plus.popleft())
        break
    else:
        if len(plus)>=2 and len(minus)>=2:
            p1 = plus.popleft()
            p2 = plus.popleft()
            m1 = minus.popleft()
            m2 = minus.popleft()
            if p1*p2 > m1*m2:
                cou.append(p1)
                cou.append(p2)
                minus.appendleft(m2)
                minus.appendleft(m1)
            else:
                cou.append(m1)
                cou.append(m2)
                plus.appendleft(p2)
                plus.appendleft(p1)
        elif len(plus) < 2:
            m1 = minus.popleft()
            m2 = minus.popleft()
            cou.append(m1)
            cou.append(m2)
        elif len(minus) < 2:
            p1 = plus.popleft()
            p2 = plus.popleft()
            cou.append(p1)
            cou.append(p2)
        
for i in cou:
    ans *= cou
    ans %= 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
a.sort(reverse=True)
ans = 1
plus = []
minus = []
zero = 0
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])
    elif a[i] == 0:
        zero += 1
if len(plus) + len(minus) < k:
    print(0)
elif len(minus) == 0:
    for i in range(k):
        ans *= plus[i]
        ans %= mod
    print(ans)
elif len(plus) == 0:
    if k % 2 == 0:
        for i in range(k):
            ans *= minus[n-1-i]
            ans %= mod
        print(ans)
    elif k % 2 == 1:
        if zero >= 1:
            print(0)
        elif zero == 0:
            for i in range(k):
                ans *= minus[i]
                ans %= mod
            print(ans)
elif len(plus) + len(minus) == k:
    if len(minus) % 2 == 1 and zero >= 1:
        print(0)
    else:
        for i in plus:
            ans *= i
            ans %= mod
        for i in minus:
            ans *= i
            ans %= mod
        print(ans)
elif len(plus) + len(minus) == k+1:
    if len(minus) % 2 == 1:
        for i in plus:
            ans *= i
            ans %= mod
        minus.sort()
        for i in range(len(minus)-1):
            ans *= minus[i]
            ans %= mod
        print(ans)
    elif len(minus) % 2 == 0:
        for i in range(len(plus)-1):
            ans *= plus[i]
            ans %= mod
        for i in minus:
            ans *= i
            ans %= mod
        print(ans)
elif len(plus) + len(minus) == k+2 and len(plus) % 2 == 1 and len(minus) % 2 == 1:
    for i in range(len(plus)-1):
        ans *= plus[i]
        ans %= mod
    minus.sort()
    for i in range(len(minus)-1):
        ans *= minus[i]
        ans %= mod
    print(ans)
else:
    if k % 2 == 1:
        ans = plus[0]
        del plus[0]
        k -= 1
    re = []
    for i in range(k//2):
        if 2*i + 1 >= len(plus):
            break
        re.append(plus[2*i]*plus[2*i+1])
    minus.sort()
    for i in range(k//2):
        if 2*i + 1 >= len(plus):
            break
        re.append(minus[2*i]*minus[2*i+1])
    re.sort(reverse=True)
    for i in range(k//2):
        ans *= re[i]
        ans %= 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
a.sort(reverse=True)
ans = 1
plus = []
minus = []
zero = 0
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])
    elif a[i] == 0:
        zero += 1
if len(plus) + len(minus) < k:
    print(0)
elif len(minus) == 0:
    for i in range(k):
        ans *= plus[i]
        ans %= mod
    print(ans)
elif len(plus) == 0:
    if k % 2 == 0:
        for i in range(k):
            ans *= minus[n-1-i]
            ans %= mod
        print(ans)
    elif k % 2 == 1:
        if zero >= 1:
            print(0)
        elif zero == 0:
            for i in range(k):
                ans *= minus[i]
                ans %= mod
            print(ans)
elif len(plus) + len(minus) == k:
    if len(minus) % 2 == 1 and zero >= 1:
        print(0)
    else:
        for i in plus:
            ans *= i
            ans %= mod
        for i in minus:
            ans *= i
            ans %= mod
        print(ans)
else:
    if k % 2 == 1:
        ans = plus[0]
        del plus[0]
        k -= 1
    re = []
    for i in range(k//2):
        if 2*i + 1 >= len(plus):
            break
        re.append(plus[2*i]*plus[2*i+1])
    minus.sort()
    for i in range(k//2):
        if 2*i + 1 >= len(plus):
            break
        re.append(minus[2*i]*minus[2*i+1])
    re.sort(reverse=True)
    for i in range(k//2):
        ans *= re[i]
        ans %= 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
a.sort(reverse=True)
ans = 1
plus = []
minus = []
zero = 0
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])
    elif a[i] == 0:
        zero += 1
if len(plus) + len(minus) < k:
    print(0)
elif len(minus) == 0:
    for i in range(k):
        ans *= plus[i]
        ans %= mod
    print(ans)
elif len(plus) == 0:
    if k % 2 == 0:
        for i in range(k):
            ans *= minus[n-1-i]
            ans %= mod
        print(ans)
    elif k % 2 == 1:
        if zero >= 1:
            print(0)
        elif zero == 0:
            for i in range(k):
                ans *= minus[i]
                ans %= mod
            print(ans)
else:
    if k % 2 == 1:
        ans = plus[0]
        del plus[0]
        k -= 1
    re = []
    for i in range(k//2):
        if 2*i + 1 >= len(plus):
            break
        re.append(plus[2*i]*plus[2*i+1])
    minus.sort()
    for i in range(k//2):
        if 2*i + 1 >= len(plus):
            break
        re.append(minus[2*i]*minus[2*i+1])
    re.sort(reverse=True)
    for i in range(k//2):
        ans *= re[i]
        ans %= 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
a.sort(reverse=True)
ans = 1
plus = []
minus = []
zero = 0
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus.append(a[i])
    elif a[i] == 0:
        zero += 1
if len(plus) + len(minus) < k:
    print(0)
elif len(minus) == 0:
    for i in range(k):
        ans *= plus[i]
        ans %= mod
    print(ans)
elif len(plus) == 0:
    if k % 2 == 0:
        for i in range(k):
            ans *= minus[n-1-i]
            ans %= mod
        print(ans)
    elif k % 2 == 1:
        if zero >= 1:
            print(0)
        elif zero == 0:
            for i in range(k):
                ans *= minus[i]
                ans %= mod
            print(ans)
else:
    rplus = [1]
    for i in range(len(plus)):
        rplus.append(rplus[-1] * plus[i])
    rminus = [1]
    for i in reversed(range(len(minus))):
        rminus.append(rminus[-1] * minus[i])
    for i in range(0,k+1,2):
        cou = 1
        if len(rminus) < i or len(rplus) < k - i:
            continue
        cou = rminus[i] * rplus[k-i]
        if cou > ans:
            ans = cou
    print(ans%mod)

Submission status: Runtime Error

Solution code:
n_valores_vetor = int(input())
n_valores_pegos = int(input())
contador=0
vetor_entrada=[]
vetor_entrada_abs=[]
while (contador<n_valores_vetor):
    valor = int(input())
    vetor_entrada.append(valor)
    vetor_entrada_abs.append(abs(valor))
    contador=contador+1
contador=0
produto=1
modulo=1
while (contador<n_valores_pegos):
    posicao_max = vetor_entrada.index(max(vetor_entrada))
    valor_max_abs = vetor_entrada_abs.pop(posicao_max)
    valor_max = vetor_entrada.pop(posicao_max)
    produto = produto*valor_max
    modulo = modulo*valor_max_abs
    contador=contador+1
def myLog(x, b):
    if x < b:
        return 0  
    return 1 + myLog(x/b, b)
valor_grande = 1000000007
if produto<0:
    print(valor_grande+produto)
elif modulo>valor_grande:
    expoente = int(myLog(produto,10))
    aux = int(valor_grande - 7**(expoente/9))
    print(aux)
else:
    print(modulo)

Submission status: Runtime Error

Solution code:
n_valores_vetor = int(input())
n_valores_pegos = int(input())
contador=0
vetor_entrada=[]
vetor_entrada_abs=[]
while (contador<n_valores_vetor):
    valor = int(input())
    vetor_entrada.append(valor)
    vetor_entrada_abs.append(abs(valor))
    contador=contador+1
contador=0
produto=1
modulo=1
while (contador<n_valores_pegos):
    posicao_max = vetor_entrada.index(max(vetor_entrada))
    valor_max_abs = vetor_entrada_abs.pop(posicao_max)
    valor_max = vetor_entrada.pop(posicao_max)
    produto = produto*valor_max
    modulo = modulo*valor_max_abs
    contador=contador+1
valor_grande = 1000000007
if produto<0:
    print(valor_grande+produto)
elif modulo>valor_grande:
    expoente = int(math.log(produto,10))+1
    aux = int(valor_grande - 7**(expoente/9))
    print(aux)
else:
    print(modulo)

Submission status: Runtime Error

Solution code:
n_valores_vetor = int(input())
n_valores_pegos = int(input())
contador=0
vetor_entrada=[]
vetor_entrada_abs=[]
while (contador<n_valores_vetor):
    valor = int(input())
    vetor_entrada.append(valor)
    vetor_entrada_abs.append(abs(valor))
    contador=contador+1
contador=0
produto=1
modulo=1
while (contador<n_valores_pegos):
    posicao_max = vetor_entrada.index(max(vetor_entrada))
    valor_max_abs = vetor_entrada_abs.pop(posicao_max)
    valor_max = vetor_entrada.pop(posicao_max)
    produto = produto*valor_max
    modulo = modulo*valor_max_abs
    contador=contador+1
import math
valor_grande = 1000000007
if produto<0:
    print(valor_grande+produto)
elif modulo>valor_grande:
    expoente = int(math.log(produto,10))+1
    aux = int(valor_grande - 7**(expoente/9))
    print(aux)
else:
    print(modulo)

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
p, n = [], []

for Ai in A:
    if Ai>=0:
        p.append(Ai)
    else:
        n.append(Ai)

if len(n)==N and K%2==1:
    n.sort(reverse=True)
    ans = 1
    
    for ni in n[:K]:
        ans *= ni
        ans %= MOD
    
    print(ans)
    exit()

if K==N and len(n)%2==1:
    for Ai in A:
        ans *= Ai
        ans %= MOD
    
    print(ans)
    exit()

p.sort(reverse=True)
n.sort()
l = []

if K%2==1:
    ans = p[0]
    p = p[1:]
else:
    ans = 1
    
for i in range(len(p)//2):
    l.append(p[2*i]*p[2*i+1])
    
for i in range(len(n)//2):
    l.append(n[2*i]*n[2*i+1])
    
l.sort(reverse=True)
    
for li in l[:K//2]:
    ans *= li
    ans %= MOD
    
print(ans)

Submission status: Runtime Error

Solution code:
# Problem E - Multiplication 4
def checkio(numbers_array):
    return sorted(numbers_array, key=lambda x: abs(x), reverse=True)

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

# initialization
a_nums = checkio(a_nums) # 大きい順
a_nums_r = a_nums[::-1] # 小さい順
is_all_minus = all(list(map(lambda x: x<0, a_nums)))
MOD = 10**9 + 7

if is_all_minus:
    ans = 1
    if K%2==0:
        for i in range(K):
            ans *= a_nums[i] % MOD
            ans %= MOD
        print(ans%MOD)
    else:
        for i in range(K):
            ans *= a_nums_r[i] % MOD
            ans %= MOD
        print(ans%MOD)
else: # 1つでも非負整数が含まれている場合
    plus_list = []
    minus_list = []
    plus_count = 0
    minus_count = 0
    cur_point = 1
    # 絶対値順に数をとってみる
    for i in range(K):
        a = a_nums.pop(0)
        cur_point *= a % MOD # 暫定の最大値
        if a>=0:
            plus_list.append(a)
        else:
            minus_list.append(a)
            minus_count += 1
    if minus_count%2==0: # 負の個数が偶数であればそれが答え
        ans = 1
        for p in plus_list:
            ans *= p % MOD
            ans %= MOD
        for m in minus_list:
            ans *= m % MOD
            ans %= MOD
        print(ans%MOD)
    else: # 負の個数が奇数の時
        # 正の数を加えてみる
        tmp_1 = (-1) * float('INF')
        tmp_2 = (-1) * float('INF')
        tmp_3 = 1
        if any(list(map(lambda x: x>=0, a_nums))):
            # 正の数を取得
            tmp = 0
            for a in a_nums:
                if a>=0:
                    tmp = a
                    break
            m = minus_list.pop()
            p = tmp
            tmp_1 = abs(p / m)

        if any(list(map(lambda x: x<0, a_nums))):
            # 負の数を取得
            tmp = 0
            for a in a_nums:
                if a<0:
                    tmp = a
                    break
            m = tmp
            p = plus_list.pop()
            tmp_2 = abs(m / p)

        if tmp_3>=tmp_1 and tmp_3>=tmp_2:
            print(cur_point)
        elif tmp_1>=tmp_2 and tmp_1>=tmp_3:
            cur_point *= tmp_1
            print(cur_point)
        else:
            cur_point *= tmp_2
            print(cur_point)

Submission status: Runtime Error

Solution code:
# Problem E - Multiplication 4
def checkio(numbers_array):
    return sorted(numbers_array, key=lambda x: abs(x), reverse=True)

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

# initialization
a_nums = checkio(a_nums) # 大きい順
a_nums_r = a_nums[::-1] # 小さい順
is_all_minus = all(list(map(lambda x: x<0, a_nums)))
MOD = 10**9 + 7

if is_all_minus:
    ans = 1
    if K%2==0:
        for i in range(K):
            ans *= a_nums[i] % MOD
            ans %= MOD
        print(ans%MOD)
    else:
        for i in range(K):
            ans *= a_nums_r[i] % MOD
            ans %= MOD
        print(ans%MOD)
else: # 1つでも非負整数が含まれている場合
    plus_list = []
    minus_list = []
    plus_count = 0
    minus_count = 0
    cur_point = 1
    # 絶対値順に数をとってみる
    for i in range(K):
        a = a_nums.pop(0)
        cur_point *= a % MOD # 暫定の最大値
        if a>=0:
            plus_list.append(a)
        else:
            minus_list.append(a)
            minus_count += 1
    if minus_count%2==0: # 負の個数が偶数であればそれが答え
        ans = 1
        for p in plus_list:
            ans *= p % MOD
            ans %= MOD
        for m in minus_list:
            ans *= m % MOD
            ans %= MOD
        print(ans%MOD)
    else: # 負の個数が奇数の時
        # 正の数を加えてみる
        tmp_1 = (-1) * float('INF')
        tmp_2 = (-1) * float('INF')
        tmp_3 = 1
        if any(list(map(lambda x: x>=0, a_nums))):
            # 正の数を取得
            tmp = 0
            for a in a_nums:
                if a>=0:
                    tmp = a
                    break
            m = minus_list[-1]
            p = tmp
            tmp_1 = abs(p / m)

        if any(list(map(lambda x: x<0, a_nums))):
            # 負の数を取得
            tmp = 0
            for a in a_nums:
                if a<0:
                    tmp = a
                    break
            m = tmp
            p = plus_list[-1]
            tmp_2 = abs(m / p)

        if tmp_3>=tmp_1 and tmp_3>=tmp_2:
            print(cur_point)
        elif tmp_1>=tmp_2 and tmp_1>=tmp_3:
            cur_point *= tmp_1
            print(cur_point)
        else:
            cur_point *= tmp_2
            print(cur_point)

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
# mod の逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

# 正,負 で分ける
b=[]
c=[]
for i in a:
    if i>=0:
        b.append(i)
    else:
        c.append(i)

b.sort(reverse=True)
c.sort()
ans=1
if k==n and len(c)%2==0:
    for i in range(n):
        ans*=a[i]
        ans%=mod

elif k%2==1 and len(c)==n:
    c.sort(reverse=True)
    for i in range(k):
        ans*=c[i]
        ans%=mod

else:
    x=k
    # プラスの配列をどこまで進めたか
    v=0
    # マイナスの配列をどこまで進めたか？
    w=0
    for i in range(k):
        if x>=2:
            x-=2
            if v+2<=len(b) and w+2<=len(c):
                if b[v]*b[v+1]>c[w]*c[w+1]:
                    ans*=b[v]*b[v+1]
                    v+=2
                else:
                    ans*=c[w]*c[w+1]
                    w+=2


            elif v+2<=len(b):
                ans*=b[v]*b[v+1]
                v+=2

            else:
                ans*=c[w]*c[w+1]
                w+=2
            ans%=mod
            if x==0:
                break
        else:
            ans*=b[v]
            ans%=mod
            break
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,K = LI()
A = LI()

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

plus = []
minus = []
zeros = []

for i in range(N):
    if A[i] > 0:
        plus.append(A[i])
    elif A[i] < 0:
        minus.append(-A[i])
    else:
        zeros.append(A[i])

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

if len(plus):
    if K%2:
        ans = plus[0]
        p_place = 1
        m_place = 0
        K -= 1
    else:
        ans = 1
        p_place = 0
        m_place = 0
    while K:
        val1 = plus[p_place]*plus[p_place+1] if p_place <= len(plus)-2 else -float('inf')
        val2 = minus[m_place]*minus[m_place+1] if m_place <= len(minus)-2 else -float('inf')
        if val1 == val2 == -float('inf'):
            if p_place == len(plus)-1:
                ans *= plus[p_place]
                ans %= mod
                K -= 1
            if K:
                print(0)
                exit()
        else:
            K -= 2
            if val1 == -float('inf'):
                ans *= val2
                ans %= mod
                m_place += 2
            elif val2 == -float('inf'):
                ans *= val1
                ans %= mod
                p_place += 2
            elif val1 >= val2:
                ans *= val1
                ans %= mod
                p_place += 2
            else:
                ans *= val2
                ans %= mod
                m_place += 2
    print(ans)
else:
    if K%2:
        if len(zeros):
            print(0)
        else:
            ans = 1
            for i in range(K):
                ans *= -minus[len(minus)-1-i]
                ans %= mod
            print(ans)
    else:
        m_place = 0
        while K:
            if m_place <= len(minus)-2:
                ans *= minus[m_place]*minus[m_place+1]
                ans %= mod
                m_place += 2
                K -= 2
            else:
                print(0)
                exit()
        print(ans)