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())
alst = list(map(int, input().split()))

if n == 1:
    print(alst[0])
    exit()

alst.sort()

if alst[0] >= 0:
    ans = 1
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

if alst[-1] <= 0:
    ans = 1
    if k % 2 == 1:
        alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    try:
        blst.append([abs(num), abs(num) // num])
    except ZeroDivisionError:
        blst.append([abs(num), 0])
blst.sort(reverse = True)
if blst[k - 1] == 0:
    print(0)
    exit()
    
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    else:
        last_plus = blst[i][0]
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0
flg_minus = False
flg_plus = False

for i in range(k, n):
    if blst[i][1] == -1 and (not flg_minus):
        next_minus = blst[i][0]
        flg_minus = True
    elif blst[i][1] == 1 and (not flg_plus):
        next_plus = blst[i][0]
        flg_plus = True
    if flg_plus and flg_minus or blst[i][1] == 0:
        break

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    ans = 1
    if minus_s == plus_s == 0:
        if last_minus == 0:
            ans_lst.remove(last_plus)
            ans_lst.append(next_minus)
        else:
            ans_lst.remove(last_minus)
            ans_lst.append(next_plus)
        
    elif minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
P = sum(x>0 for x in a)
Z = sum(x==0 for x in a)
M = sum(x<0 for x in a)
ans = 1
mod = 10**9+7
pal = 1
if (P == 0 and K%2 == 1) or (M%2 == 1 and K == N):
  if Z != 0:
    #print('here')
    print(0)
  else:
    aabs = sorted([abs(x) for x in a])
    #print('HERE')
    #print(aabs)
    for i in aabs[:K]:
      ans *= i
      #print(ans)
      ans %= mod
      #print(ans)
    print(-1*ans+mod)
else:
  if P+M < K:
    print(0)
  else:
    aabs = sorted([(abs(x),x/abs(x)) for x in a],reverse=True)
    for i in range(K-1):
      ans *= aabs[i][0]
      ans %= mod
      pal *= aabs[i][1]
    if pal == 1:
      for i in range(K-1,N):
        if aabs[i][1] == 1:
          ans *= aabs[i][0]
          ans %= mod
          break
    if pal == -1:
      for i in range(K-1,N):
        if aabs[i][1] == -1:
          ans *= aabs[i][0]
          ans %= mod
          break
  print(ans)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k,*A = get_all_int()
    A = list(A)

    # 答えが負である条件
    # ・Aが全て負で、Kが奇数
    # ・Aの負数が奇数個かつ0が存在せず、K=N

    # 答えが0である条件
    # ・N-(Aの0の個数) < K

    positives = 0
    zeros = 0
    negatives = 0

    for a in A:
        if a > 0:
            positives += 1
        elif a == 0:
            zeros += 1
        else:
            negatives += 1
    

    if k == 1:
        # 1個だけの場合はたんに最大値を出力する
        A.sort(reverse=True)
        print(A[0])
        exit()

    if (n-zeros) < k:
        # 答えが0
        print(0)
        exit()
    
    elif (k==n and negatives%2==1  or  n==negatives and k%2==1):
        # 答えが負
        # 絶対値小さい順にK個掛ける
        A.sort(key=lambda a: abs(a))
        # log(A)
        ans = 1
        for i in range(k):
            ans =  (ans * A[i]) % MOD
        print(ans%MOD)
        exit()

    else:
        # 答えが正
        # 絶対値大きい順にK個掛ける
        A.sort(reverse=True, key=lambda a: abs(a))
        # log(A)
        ans = 1
        n_count = 0
        last_n = 0
        last_p = 0
        for i in range(k):
            a = A[i]
            ans =  (ans * a) % MOD
            if a < 0:
                n_count += 1
                last_n = a
            elif a > 0:
                last_p = a
                # log(i, last_n)

        # log(ans, n_count, last_n)
        
        # 負数を奇数個選んでいる場合は調整する
        if n_count%2 == 1:
            x = None
            y = None
            for i in range(k,n):
                a = A[i]
                if a > 0 :
                    ans_a = ans*inv(last_n, MOD) * a
                    x = a
                    break
            if last_p != 0:
                for i in range(k,n):
                    a = A[i]
                    if a < 0 and last_p!=0:
                        ans_b = ans*inv(last_p, MOD) * a
                        y = a
                        break
                if y is not None:
                    if x is not None:
                        xx = abs(x) / abs(last_n)
                        yy = abs(y) / abs(last_p)
                        if yy > xx:
                            ans_a = ans_b
                    else:
                        ans_a = ans_b
            ans = ans_a
        
        print(ans%MOD)
        exit()

main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
li_a = list(map(int, input().split()))
mod = 10**9+7
li = []
lll = 0
for i in li_a:
    if i < 0:
        li.append((abs(i), -1))
        lll += 1
    else:
        li.append((i, 1))
li.sort()
if lll == n:
    ans = 1
    for i in range(k):
        ans *= -li[i][0]
        ans %= mod
    print(ans)
    exit()
ans = 1
guki = 1
for i in range(n-1, n-k-1, -1):
    ans *= li[i][0]
    ans %= mod
    guki *= li[i][1]
if guki > 0:
    print(ans)
else:
    P, M, p, m = 10**6, 1000000, 1000000, 1000000
    P1, M1, p1, m1 = True, True, True, True
    for i in range(n-k, n-1):
        if li[i][1] > 0:
            Plus = li[i][0]
            P = i
            P1 = False
            break
    for i in range(n-k, n-1):
        if li[i][1] < 0:
            Mini = li[i][0]
            M = i
            M1 = False
            break
    for i in range(n-k, -1, -1):
        if li[i][1] > 0:
            plus = li[i][0]
            p = i
            p1 = False
            break
    for i in range(n-k, -1, -1):
        if li[i][1] < 0:
            mini = li[i][0]
            m = i
            m1 = False
            break
    ans1 = 1
    ans2 = 1
    if not P1 and not m1:
        for i in range(n-1, n-k-1, -1):
            if i == P:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans1 *= li[m][0]
        ans1 %= mod
    if not p1 and not M1:
        for i in range(n-1, n-k-1, -1):
            if i == M:
                continue
            ans1 *= li[i][0]
            ans1 %= mod
        ans2 *= li[p][0]
        ans2 %= mod
    if p1 or P1 or M1 or m1:
        print(max(ans1, ans2))
    else:
        ans = 1
            for i in range(k):
            ans *= -li[i][0]
            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

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

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

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

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

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

if n == 1:
    print(alst[0])
    exit()

alst.sort()

if alst[0] >= 0:
    ans = 1
    alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

if alst[-1] <= 0:
    ans = 1
    if k % 2 == 1:
        alst.sort(reverse = True)
    for i in range(k):
        ans *= alst[i]
        ans %= MOD
    print(ans)
    exit()

blst = []
for num in alst:
    try:
        blst.append([abs(num), abs(num) // num])
    except ZeroDivisionError:
        blst.append([abs(num), 0])
blst.sort(reverse = True)
if blst[k - 1] == 0:
    print(0)
    exit()
    
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
    if blst[i][1] == -1:
        minus += 1
        last_minus = blst[i][0]
    else:
        last_plus = blst[i][0]
    ans_lst.append(blst[i][0])

next_minus = 0
next_plus = 0
flg_minus = False
flg_plus = False

for i in range(k, n):
    if blst[i][1] == -1 and (not flg_minus):
        next_minus = blst[i][0]
    elif blst[i][1] == 1 and (not flg_plus):
        next_plus = blst[i][0]
    if flg_plus and flg_minus or blst[i][1] == 0:
        break

if minus % 2 == 0:
    ans = 1
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

else:
    minus_s = last_minus * next_minus
    plus_s = last_plus * next_plus
    ans = 1
    if minus_s == plus_s == 0:
        if last_minus == 0:
            ans_lst.remove(last_plus)
            ans_lst.append(next_minus)
        else:
            ans_lst.remove(last_minus)
            ans_lst.append(next_plus)
        
    elif minus_s > plus_s:
        ans_lst.remove(last_plus)
        ans_lst.append(next_minus)
    else:
        ans_lst.remove(last_minus)
        ans_lst.append(next_plus)
    for num in ans_lst:
        ans *= num
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
M = 10**9 + 7
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = [] # 1以上
C = [] # -1以下

for x in A:
  if (x == 0):
    N-=1
  elif x > 0:
    B.append(x)
  elif x < 0:
    C.append(-x)

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

if K%2 == 1 and len(B) == 0:
  AN = 1
  C.sort()
  for i,x in enumerate(C):
    if i == K:
      break
    AN *= x
    AN %= M
  AN *= -1; AN %= M; AN += M; AN %= M;
  print(AN)
  exit(0)

AN = 1
if K % 2 == 1:
  AN *= max(C)
  C.remove(max(C))
  K -= 1

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

for i in range(len(B), K):
  B.append(1)
for i in range(len(C), K):
  C.append(1)
for i in range(K):
  AN *= B[i]
MA = AN
# print(AN)
for i in range(0,K,2):
  AN //= B[K-1-i] * B[K-2-i]
  AN *= C[i] * C[i+1]
  MA = max(AN, MA)
  # print(AN)

# print(B)
# print(C)
# print(K)
print(MA%M)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from collections import deque

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

idx = bisect_left(A, 0)
minus_A = A[:idx]
plus_A = A[idx:][::-1]
# print(f'{plus_A=}, {minus_A=}')

ans = 1
if len(plus_A) == 0:
    if K % 2 == 1:
        minus_A = minus_A[::-1]
    for i in range(K):
        ans *= minus_A[i]
        ans %= MOD
    print(ans)
    exit()

len_minus_A = len(minus_A)
if len_minus_A == 0:
    for i in range(K):
        ans *= plus_A[i]
        ans %= MOD
    print(ans)
    exit()

minus_A = deque(minus_A)
plus_A = deque(plus_A)
while len_minus_A >= 2 and K >= 2:
    if minus_A[0] * minus_A[1] > plus_A[0] * plus_A[1]:
        v1 = minus_A.popleft()
        v2 = minus_A.popleft()
        len_minus_A -= 2
    else:
        v1 = plus_A.popleft()
        v2 = plus_A.popleft()
    ans *= v1
    ans %= MOD
    ans *= v2
    ans %= MOD
    K -= 2

if K >= 1:
    for i in range(K):
        ans *= plus_A[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

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) > 0 and (k - len(plus)) % 2 == 1:
    plus.sort(reverse=True)
    minus.sort()
    ans = minus[0]
    i, j = 0, 1
    while i + j < k:
        tmp_p = plus[i] * plus[i + 1] if i <= len(plus) - 2 else float('inf')
        tmp_m = minus[j] * minus[j + 1] if i <= len(minus) - 2 else float('inf')
        if tmp_p <= tmp_m:
            ans = (ans * (tmp_p % mod)) % mod
            i += 2
        else:
            ans = (ans * (tmp_m % mod)) % mod
            j += 2
else:
    plus.sort()
    minus.sort(reverse=True)
    i, j = 0, 0
    while i + j < k:
        tmp_p = plus[i] * plus[i + 1] if i <= len(plus) - 2 else 0
        tmp_m = minus[j] * minus[j + 1] if j <= len(plus) - 2 else 0
        if tmp_p >= tmp_m:
            ans = (ans * plus[i]) % mod
            i += 1
        else:
            ans = (ans * (tmp_m % mod)) % mod
            j += 2
print(ans)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k,*A = get_all_int()
    A = list(A)

    # 答えが負である条件
    # ・Aが全て負で、Kが奇数
    # ・Aの負数が奇数個かつ0が存在せず、K=N

    # 答えが0である条件
    # ・N-(Aの0の個数) < K

    positives = 0
    zeros = 0
    negatives = 0

    for a in A:
        if a > 0:
            positives += 1
        elif a == 0:
            zeros += 1
        else:
            negatives += 1
    

    if k == 1:
        # 1個だけの場合はたんに最大値を出力する
        A.sort(reverse=True)
        print(A[0])
        exit()

    if (n-zeros) < k:
        # 答えが0
        print(0)
        exit()
    
    elif (k==n and negatives%2==1  or  n==negatives and k%2==1):
        # 答えが負
        # 絶対値小さい順にK個掛ける
        A.sort(key=lambda a: abs(a))
        # log(A)
        ans = 1
        for i in range(k):
            ans =  (ans * A[i]) % MOD
        print(ans%MOD)
        exit()

    else:
        # 答えが正
        # 絶対値大きい順にK個掛ける
        A.sort(reverse=True, key=lambda a: abs(a))
        # log(A)
        ans = 1
        n_count = 0
        last_n = 0
        last_p = 0
        for i in range(k):
            a = A[i]
            ans =  (ans * a) % MOD
            if a < 0:
                n_count += 1
                last_n = a
            elif a > 0:
                last_p = a
                # log(i, last_n)

        # log(ans, n_count, last_n)
        
        # 負数を奇数個選んでいる場合は調整する
        if n_count%2 == 1:
            x = None
            y = None
            for i in range(k,n):
                a = A[i]
                if a > 0 :
                    ans_a = ans*inv(last_n, MOD) * a
                    x = a
                    break
            if last_p != 0:
                for i in range(k,n):
                    if a < 0 and last_p!=0:
                        ans_b = ans*inv(last_p, MOD) * a
                        y = a
                        break
                if y is not None:
                    if x is not None:
                        xx = abs(x) / abs(last_n)
                        yy = abs(y) / abs(last_p)
                        if yy > xx:
                            ans_a = ans_b
                    else:
                        ans_a = ans_b
            ans = ans_a
        
        print(ans%MOD)
        exit()

main()

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
all_minus = True
for i in range(n):
  if a[i] >= 0:
    all_minus = False
    break
if all_minus:
  a.sort(key = lambda x: abs(x))
  ans = 1
  for i in range(k):
    ans *= a[i]
  ans %= mod
  print(ans)
  exit()
a.sort(key = lambda x: abs(x))
a.reverse()
ans = 1
mcnt = 0
zcnt = 0
for i in range(n):
  if a[i] == 0:
    zcnt += 1
if zcnt > n - k:
  print(0)
  exit()
b = []
for i in range(n):
  if a[i] == 0:
    continue
  b.append(a[i])
m = len(b)
for i in range(k):
  ans *= b[i]
  if b[i] < 0:
    mcnt += 1
if mcnt % 2 == 0:
  ans = max(0, ans) % mod
  print(ans)
  exit()
lp = 0
lm = 0
for i in reversed(range(k)):
  if b[i] > 0:
    lp = b[i]
    break
for i in reversed(range(k)):
  if b[i] < 0:
    lm = b[i]
    break
base = ans
for i in range(k, m):
  temp = base
  if b[i] > 0:
    temp //= lm
    temp *= b[i]
    ans = max(ans, temp)
  else:
    temp //= lp
    temp *= b[i]
    ans = max(ans, temp)
ans = max(0, ans) % mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from math import log2
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N, K = MAP()
A = LIST()

A1 = []
A2 = []
B1 = []
B2 = []
for a in A:
    if a >= 0:
        A1.append(a)
        B1.append(log2(a))
    else:
        A2.append(-a)
        B2.append(log2(-a))

A1.sort()
A2.sort()
B1.sort()
B2.sort()
acc1 = [0] + list(accumulate(B1))
accrev1 = [0] + list(accumulate(B1[::-1]))
acc2 = [0] + list(accumulate(B2))
accrev2 = [0] + list(accumulate(B2[::-1]))
mx = -INF
mn = INF
idx1 = (-1, -1)
idx2 = (-1, -1)
for i in range(K+1):
    j = K - i
    if len(B1) < i or len(B2) < j:
        continue
    if j % 2 == 0:
        sm = accrev1[i] + accrev2[j]
        if sm > mx:
            mx = sm
            idx1 = (i, j)
    else:
        sm = acc1[i] + acc2[j]
        if sm < mn:
            mn = sm
            idx2 = (i, j)

if mx != -INF:
    ans = 1
    n, m = idx1
    A1.reverse()
    A2.reverse()
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)
else:
    ans = 1
    n, m = idx2
    for i in range(n):
        ans *= A1[i]
        ans %= MOD
    for i in range(m):
        ans *= -A2[i]
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:

def main():
    MOD = 10**9+7
    n,k = map(int, input().split())
    al = list(map(int, input().split()))
    al_abs = []
    al_nl = []
    for a in al: 
        if a > 0: sig = 1
        elif a < 0 : 
            sig = -1
            al_nl.append(a)
        else: sig = 0
        al_abs.append((abs(a), sig))

    al_abs.sort(reverse=True)
    n_cnt = 0
    last_p = -1
    last_n = -1
    for i in range(k):
        a, sig = al_abs[i]
        if sig == -1:
            n_cnt+=1
            last_n = i
        elif sig == 1:
            last_p = i
    
    ans = 1
    if n_cnt%2 == 0:
        for i in range(k):
            a, sig = al_abs[i]
            ans *= a
            ans %= MOD
        print(ans)
        exit()


    next_p = -1
    next_n = -1 
    for i in range(k,n):
        a, sig = al_abs[i]
        if sig == 1 and next_p == -1:
            next_p = i
        elif sig == -1 and next_n == -1:
            next_n = i
        if next_n != -1 and next_p != -1:
            break

    comp_np = 0
    if next_p != -1:
        last_n_val = al_abs[last_n][0]
        next_p_val = al_abs[next_p][0]
        comp_np = next_p_val*(1.0)/last_n_val

    comp_pn = 0
    if next_n != -1 and last_p != -1:
        last_p_val = al_abs[last_p][0]
        next_n_val = al_abs[next_n][0]
        comp_pn = next_n_val*(1.0)/last_p_val

    if comp_np > comp_pn: 
        np_or_pn = True
    else:
        np_or_pn = False

    if comp_np == 0 and comp_pn == 0:
        if 0 in al:
            print(0)
            exit()
        else:
            al_nl.sort(reverse=True)
            for i in range(k):
                a = al_nl[i]
                ans *= (a)
                ans %= MOD
            print(ans)
            exit()


    # print(next_p, next_n, comp_np, comp_pn)

    for i in range(k):
        if np_or_pn and i == last_n:
            continue
        if (not np_or_pn) and i == last_p:
            continue
        a, sig = al_abs[i]
        ans *= a
        ans %= MOD

    if np_or_pn:
        ans *= next_p_val
        ans %= MOD
    else:
        ans *= next_n_val
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = []
for i in range(N):
    if A[i] > 0:
        p = i
D = A[:p]
B = []
for i in D:
    B.append(i)
B.sort()
C = A[p:]
for i in range(p):
    S.append(-A[i])
for i in range(p,N):
    S.append(A[i])
S.sort()
i = 0
while B:
    if S[i] == B[0]:
        S[i] = -S[i]
        B.pop(0)
    i += 1

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

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


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

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

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

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

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

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

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

main()

Submission status: Runtime Error

Solution code:
MOD = 10**9+7

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a, key=abs, reverse=True)
_a = sorted(a, reverse=True)
if k%2 == 1 and _a[0] < 0:
    ans = 1
    for i in range(1, k+1):
        ans *= -a[-i]
        ans %= MOD
    print((-ans)%MOD)
elif a[k-1] == 0:
    print(0)
else:
    plus = True
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= MOD
        if a[i] < 0:
            plus = not plus
    if plus:
        print(ans)
    else:
        j = k-1
        l = k
        while a[j] > 0:
            j -= 1
        while a[l] < 0:
            l += 1
        ans = 1
        for i in range(k):
            if i != j:
                ans *= abs(a[i])
                ans %= MOD
        ans *= abs(a[l])
        ans %= MOD
        print(ans)