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 heapq

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

# n=kのとき、積の最大値は負になる可能性がある
if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

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

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if (not neg) or (pos[0]<=neg[0]):
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if (not pos) or (pos[0]>neg[0]):
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue
print(L_ans)
if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.remove(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.remove(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = -pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_neg*last_neg:
            L_ans.remove(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.remove(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

plus_zero = []
minus = []

for i in a:
    if i >= 0:
        plus_zero.append(i)
    if i < 0:
        minus.append(-i)

from collections import deque

plus_zero = deque(sorted(plus_zero, reverse=True))
minus = deque(sorted(minus, reverse=True))
absolute = deque(sorted(a, key=abs, reverse=True))

ans_lst = []
# 境界条件: k == n
if k == n:
    ans_lst.extend(a)
# 負
elif len(plus_zero) == 0 and (k % 2) != 0:
    for _ in range(k):
        ans_lst.append(-minus.pop())
# 正 or 0
else:
    minus_num = 0
    for _ in range(k):
        v = absolute.popleft()
        if v < 0:
            minus_num += 1
        ans_lst.append(v)
    if minus_num % 2 != 0:
        abs_min_plus_zero, abs_min_minus = None, None
        abs_max_plus_zero, abs_max_minus = None, None
        for i in ans_lst:
            if i >= 0:
                if abs_min_plus_zero is None:
                    abs_min_plus_zero = i
                else:
                    abs_min_plus_zero = min(i, abs_min_plus_zero)
            else:
                if abs_min_minus is None:
                    abs_min_minus = i
                else:
                    abs_min_minus = max(abs_min_minus, i)
        for i in absolute:
            if i >= 0:
                if abs_max_plus_zero is None:
                    abs_max_plus_zero = i
                else:
                    abs_max_plus_zero = max(i, abs_max_plus_zero)
            else:
                if abs_max_minus is None:
                    abs_max_minus = i
                else:
                    abs_max_minus = min(abs_max_minus, i)
        case1, case2 = False, False
        if abs_min_plus_zero is not None and abs_max_minus is not None:
            case1 = True
        if abs_min_minus is not None and abs_max_plus_zero is not None:
            case2 = True
        if case1 and case2:
          	pass
        #    if abs_max_minus * abs_min_minus <= abs_max_plus_zero * abs_min_plus_zero:
        #        ans_lst.remove(abs_min_minus)
        #        ans_lst.add(abs_max_plus_zero)
        #    else:
        #        ans_lst.remove(abs_min_plus_zero)
        #        ans_lst.add(abs_max_minus)
        elif case1:
            ans_lst.remove(abs_min_plus_zero)
            ans_lst.add(abs_max_minus)
        #elif case2:
        #    ans_lst.remove(abs_min_minus)
        #    ans_lst.add(abs_max_plus_zero)

# functools.reduceはTLEをくらう場合があるので気をつける
ans = 1
for i in ans_lst:
    ans = (ans * i) % MOD
print(ans)

Submission status: Runtime Error

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

p = 1
n = 0
ans = 1
cnt = 0
while cnt < K-1:
  if A[n]*A[n+1] > A[-p]*A[-p-1]:
    ans = ans*A[n]*A[n+1]%mod
    n += 2
    cnt += 2
    
  else:
    ans = ans*A[-p]%mod
    p += 1
    cnt += 1
    
if i == K-1:
  ans = ans*A[-p]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*cnt%mod

print(ans)

Submission status: Runtime Error

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

p = 1
n = 0
ans = 1
cnt = 0
while cnt < K-1:
  if A[n]*A[n+1] > A[-p]*A[-p-1]:
    ans = ans*A[ni]*A[n+1]%mod
    n += 2
    cnt += 2
    
  else:
    ans = ans*A[-p]%mod
    p += 1
    cnt += 1
    
if i == K-1:
  ans = ans*A[-p]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*cnt%mod

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9 + 7
A.sort()
ans = 1
if A[n - 1] <= 0 and k % 2 == 1:
    for i in range(k):
        ans *= A[n - 1 - i]
        ans %= p
    print(ans)
    exit()
if k % 2 == 1:
    ans *= A.pop()
    ans %= p
    n -= 1
A = [A[i] * A[i + 1] for i in range(0, n, 2)]
A.sort(reverse=True)
for i in range(k // 2):
    ans *= A[i]
    ans %= p
print(ans)

Submission status: Runtime Error

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

p = 1
n = 0
ans = 1
cnt = 0
while cnt < K-1:
  if A[n]*A[n+1] > A[-p]*A[-p-1]:
    ans = ans*A[ni]*A[ni+1]%mod
    n += 2
    cnt += 2
    
  else:
    ans = ans*A[-p]%mod
    p += 1
    cnt += 1
    
if i == K-1:
  ans = ans*A[-p]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*cnt%mod

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9 + 7
A.sort()
ans = 1
if A[n - 1] <= 0 and k % 2 == 1:
    for i in range(k):
        ans *= A[n - 1 - i]
        ans %= p
    print(ans)
    exit()
if k % 2 == 1:
    ans *= A.pop()
    ans %= p
A = [A[i] * A[i + 1] for i in range(0, n, 2)]
A.sort(reverse=True)
for i in range(k // 2):
    ans *= A[i]
    ans %= p
print(ans)

Submission status: Runtime Error

Solution code:
import heapq

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

# n=kのとき、積の最大値は負になる可能性がある
if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

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

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if (not neg) or (pos[0]<=neg[0]):
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if (not pos) or (pos[0]>neg[0]):
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.remove(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.remove(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_pos*last_neg:
            L_ans.remove(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.remove(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

A.sort()
A.reverse()
A_p = deque([i for i in A if i >= 0])
A_n = deque([i for i in A if i < 0])

ans = 1
if K % 2 == 0:
    while K != 0:
        if len(A_p) >= 2 and len(A_n) >= 2:
            if A_p[0] * A_p[1] > A_n[-1] * A_n[-2]:
                ans *= A_p[0] * A_p[1]
                A_p.popleft()
                A_p.popleft()
            else:
                ans *= A_n[-1] * A_n[-2]
                A_n.pop()
                A_n.pop()
        elif len(A_p) >= 2:
            ans *= A_p[0] * A_p[1]
            A_p.popleft()
            A_p.popleft()
        elif len(A_n) >= 2:
            ans *= A_n[-1] * A_n[-2]
            A_n.pop()
            A_n.pop()
        K -= 2
elif len(A_p) > 0:
    while K != 0:
        if K >= 2:
            if len(A_p) >= 2 and len(A_n) >= 2:
                if A_p[0] * A_p[1] > A_n[-1] * A_n[-2]:
                    ans *= A_p[0] * A_p[1]
                    A_p.popleft()
                    A_p.popleft()
                else:
                    ans *= A_n[-1] * A_n[-2]
                    A_n.pop()
                    A_n.pop()
            elif len(A_p) >= 2:
                ans *= A_p[0] * A_p[1]
                A_p.popleft()
                A_p.popleft()
            elif len(A_n) >= 2:
                ans *= A_n[-1] * A_n[-2]
                A_n.pop()
                A_n.pop()
            K -= 2
        elif K == 1:
            ans *= A_p[0]
            A_p.popleft()
            K -= 1
else:
    ans *= A_n[0: K]

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

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
mod = 10**9 + 7
if k%2==0:
  i = 0
  left = 0
  right = n-1
  ans = 1
  while i<k:
    m1 = a[left]*a[left+1]
    m2 = a[right]*a[right-1]
    #print(m1,m2)
    if m1<m2:
      m2%=mod
      ans*=m2
      #print("r",right)
      right -=2
    else:
      m1 %= mod
      ans *= m1
      #print(left)
      left+=2
    ans %= mod
    i+=2
  print(ans)
else:
  pos = []
  neg = []
  for i in a:
    if i<0:
      neg.append(i)
    else:
      pos.append(i)
  if len(pos)+2*(len(neg)//2)>=k:
    i = 0
    left = 0
    right = n-1
    ans = 1
    while i<k-1:
      m1 = a[left]*a[left+1]
      m2 = a[right]*a[right-1]
      #print(m1,m2)
      if m1<m2:
        m2%=mod
        ans*=m2
        #print("r",right)
        right -=2
      else:
        m1 %= mod
        ans *= m1
        #print(left)
        left+=2
      ans %= mod
      i+=2
    ans *= a[right]
    ans %= mod
    a = []
    print(a[2])
  else:
    for i in range(n):
      a[i] = abs(a[i])
    a.sort()
    ans = 1
    for i in range(k):
      ans *= a[i]
      ans %= mod
    ans = -ans
    ans %= mod
    print(ans)

Submission status: Runtime Error

Solution code:
import heapq

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

# n=kのとき、積の最大値は負になる可能性がある
if n == k:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

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

# Aの要素全て負かつkが奇数の時、積の最大値は必ず負
if len(pos)==0 and k%2==1:
    neg.sort(reverse=True)
    ans = 1
    for a in neg[:k]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

# これより下は積の最大値は必ず正
pos = [-x for x in pos]
heapq.heapify(pos)
heapq.heapify(neg)

L_ans = []
last_pos = None
last_neg = None

ans_is_neg = False

for i in range(k):
    if (not neg) or (pos[0]<=neg[0]):
        last_pos = -heapq.heappop(pos)
        L_ans.append(last_pos)
        continue

    if (not pos) or (pos[0]>neg[0]):
        last_neg = heapq.heappop(neg)
        L_ans.append(last_neg)
        ans_is_neg = not ans_is_neg
        continue

if ans_is_neg:
    if (last_pos==None) or (not neg):
        L_ans.pop(last_neg)
        L_ans.append(-heapq.heappop(pos))

    elif not pos:
        L_ans.pop(last_pos)
        L_ans.append(heapq.heappop(neg))

    else:
        new_pos = pos[0]
        new_neg = neg[0]

        if new_pos*last_pos>=new_pos*last_neg:
            L_ans.pop(last_neg)
            L_ans.append(new_pos)
        else:
            L_ans.pop(last_pos)
            L_ans.append(new_neg)

ans = 1
for a in L_ans:
    ans *= a
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq
import collections

class HeapQueue:

    def __init__(self, xs, mode):
        if   mode == "min": self.xs = [+x for x in xs]
        elif mode == "max": self.xs = [-x for x in xs]
        else              : raise NotImplementedError("HeapQueue.__init__: mode should be 'min' or 'max'")
        heapq.heapify(xs)
        self.mode = mode

    def __len__(self):
        return len(self.xs)

    def pop(self):
        if   self.mode == "min": return heapq.heappop(self.xs)
        elif self.mode == "max": return heapq.heappop(self.xs) * (-1)

    def push(self, x):
        if   self.mode == "min": return heapq.heappush(self.xs,  x)
        elif self.mode == "max": return heapq.heappush(self.xs, -x)

    # @staticmethod
    # def __test01__():
    #     xs = HeapQueue([-3, 2, 9, -4], "min")
    #     x0 = xs.pop()
    #     x1 = xs.pop()
    #     x2 = xs.pop()
    #     x3 = xs.pop()
    #     return (x0 == -4 and x1 == -3 and x2 == 2 and x3 == 9)


N, K = tuple(map(int, input().strip().split()))
As = list(map(int, input().strip().split()))

D = int(1E9 + 7)
r = 1

if N == K:

    for a in As:
        r = (r * a) % D

elif all(a >= 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 1 and all(a < 0 for a in As):

    As = sorted(As, reverse=True)
    for a in As[:K]:
        r = (r * a) % D

elif K % 2 == 0 and all(a < 0 for a in As):

    As = sorted(As)
    for a in As[:K]:
        r = (r * a) % D

else:

    As = sorted(As, key = lambda a: abs(a), reverse=True)

    used = As[:K]
    rest = As[K:]
    num_negative_sign = sum([1 if x < 0 else 0 for x in used])

    if num_negative_sign % 2 != 0:

        used_min_pos = None
        used_min_neg = None
        for k in range(K-1, -1, -1):
            if   used_min_pos is None and used[k] >= 0: used_min_pos = k
            elif used_min_neg is None and used[k] <  0: used_min_neg = k
            if used_min_pos and used_min_neg: break

        rest_min_pos = None
        rest_min_neg = None
        for k in range(N-K):
            if   rest_min_pos is None and rest[k] >= 0: rest_min_pos = k
            elif rest_min_neg is None and rest[k] <  0: rest_min_neg = k
            if rest_min_pos and rest_min_neg: break

        # print(used)
        # print(used_min_pos)
        # print(used_min_neg)
        # print(rest)
        # print(rest_min_pos)
        # print(rest_min_neg)

        if used_min_pos is None or rest_min_neg is None:
            used[used_min_neg] = rest[rest_min_pos]
        elif used_min_neg is None or rest_min_pos is None:
            used[used_min_pos] = rest[rest_min_neg]
        else:
            v1 = abs(used[used_min_pos] / rest[rest_min_neg])
            v2 = abs(used[used_min_neg] / rest[rest_min_pos])
            if v1 > v2:
                used[used_min_pos] = rest[rest_min_neg]
            else:
                used[used_min_neg] = rest[rest_min_pos]

    for a in used:
        r = (r * a) % D

print(r)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

plus_zero = []
minus = []

for i in a:
    if i >= 0:
        plus_zero.append(i)
    if i < 0:
        minus.append(-i)

from collections import deque

plus_zero = deque(sorted(plus_zero, reverse=True))
minus = deque(sorted(minus, reverse=True))
absolute = deque(sorted(a, key=abs, reverse=True))

ans_lst = []
# 境界条件: k == n
if k == n:
    ans_lst.extend(a)
# 負
elif len(plus_zero) == 0 and (k % 2) != 0:
    for _ in range(k):
        ans_lst.append(-minus.pop())
# 正 or 0
else:
    minus_num = 0
    for _ in range(k):
        v = absolute.popleft()
        if v < 0:
            minus_num += 1
        ans_lst.append(v)
    if minus_num % 2 != 0:
        abs_min_plus_zero, abs_min_minus = None, None
        abs_max_plus_zero, abs_max_minus = None, None
        for i in ans_lst:
            if i >= 0:
                if abs_min_plus_zero is None:
                    abs_min_plus_zero = i
                else:
                    abs_min_plus_zero = min(i, abs_min_plus_zero)
            else:
                if abs_min_minus is None:
                    abs_min_minus = i
                else:
                    abs_min_minus = max(abs_min_minus, i)
        for i in absolute:
            if i >= 0:
                if abs_max_plus_zero is None:
                    abs_max_plus_zero = i
                else:
                    abs_max_plus_zero = max(i, abs_max_plus_zero)
            else:
                if abs_max_minus is None:
                    abs_max_minus = i
                else:
                    abs_max_minus = min(abs_max_minus, i)
        case1, case2 = False, False
        if abs_min_plus_zero is not None and abs_max_minus is not None:
            case1 = True
        if abs_min_minus is not None and abs_max_plus_zero is not None:
            case2 = True
        if case1 and case2:
            if abs_max_minus * abs_min_minus <= abs_max_plus_zero * abs_min_plus_zero:
                ans_lst.remove(abs_min_minus)
                ans_lst.add(abs_max_plus_zero)
            else:
                ans_lst.remove(abs_min_plus_zero)
                ans_lst.add(abs_max_minus)
        elif case1:
            ans_lst.remove(abs_min_plus_zero)
            ans_lst.add(abs_max_minus)
        elif case2:
            ans_lst.remove(abs_min_minus)
            ans_lst.add(abs_max_plus_zero)

# functools.reduceはTLEをくらう場合があるので気をつける
ans = 1
for i in ans_lst:
    ans = (ans * i) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans = ans*AP[p]%mod
                print(ans%mod)
                break
                
            elif 2 <= (len(AM) - m) and 2 <= (len(AP) - p):   
                if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                    ans = ans*AP[p]*AP[p+1]%mod
                    p += 2
                    cnt += 2
                
                else:
                    ans = ans*AM[m]*AM[m+1]%mod
                    m += 2
                    cnt += 2 
                    
            elif 1 >= (len(AP) - p) and 2 <= (len(AM) - m):
                ans = ans*AM[m]*AM[m+1]%mod
                m += 2
                cnt += 2 
            
            elif 2 <= (len(AP) - p) and 1 >= (len(AM) - m):
                ans = ans*AP[p]*AP[p+1]%mod
                p += 2
                cnt += 2
            
            

            if cnt == K:
                print(ans%mod)
                break

Submission status: Runtime Error

Solution code:
n,k,*a=map(int,open(0).read().split())
a.sort(reverse=True,key=lambda x:abs(x))
MOD=10**9+7
ans=1
if n==k:
  for i in a:
    ans*=i
    ans%=MOD
  print(ans)
  exit()
if k%2==1 and sum([i>=0 for i in a])==0:
  ans=1
  for i in range(k):
    ans*=a[-1-i]
    ans%=MOD
  print(ans)
  exit()

sp=[]
sn=[]
negidx=False
posidx=False
flg=1
for i in range(k):
  if a[i]>=0:
    posidx=i
  else:
    negidx=i
    flg*=-1
  sp.append(a[i])
  sn.append(a[i])
  
if flg==1:
  ans=1
  for si in sp:
    ans*=si
    ans%=MOD
  print(ans)
  exit()
else:
  for i in range(k,n):
    if a[i]>0:
      sn[negidx]=a[i]
      ans1=1
      for si in sn:
        ans1*=si
        ans1%=MOD
      break
  for i in range(k,n):
    if a[i]<0:
      sp[posidx]=a[i]
      ans2=1
      for si in sp:
        ans2*=si
        ans2%=MOD        
      break
  print(max(ans1,ans2))

Submission status: Runtime Error

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse = True)
ans = 1
p = 0
m = 0
plus = []
minus = []
f = 0
for i in range(n):
    if a[i] >= 0:
        plus.append(a[i])
        p += 1
        if i < k:
            ans *= a[i]
            ans %= mod
    else:
        minus.append(a[i])
        m += 1
        if i < k:
            f ^= 1
            ans *= -a[i]
            ans %= mod
if f:
    ans = -ans
if ans < 0:
    if k == n:
        print(ans)
    elif p == 0:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in range(k):
            ans *= -a[i]
            ans %= mod
        if k % 2:
            ans = -ans
        print(ans % mod)
    else:
        ans1 = ans // minus[-1]
        f1 = 0
        f2 = 0
        for i in range(k, n):
            if a[i] >= 0:
                ans1 *= a[i]
                f1 = 1
                break
        ans2 = ans // plus[-1]
        ans2 = -ans2
        for i in range(k, n):
            if a[i] < 0:
                ans2 *= -a[i]
                f2 = 1
                break
        if f1 and f2:
            print(max(ans1, ans2) % mod)
        elif f1:
            print(ans1 % mod)
        else:
            print(ans2 % mod)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
mod = 10**9 + 7
if k%2==0:
  i = 0
  left = 0
  right = n-1
  ans = 1
  while i<k:
    m1 = a[left]*a[left+1]
    m2 = a[right]*a[right-1]
    #print(m1,m2)
    if m1<m2:
      m2%=mod
      ans*=m2
      #print("r",right)
      right -=2
    else:
      m1 %= mod
      ans *= m1
      #print(left)
      left+=2
    ans %= mod
    i+=2
  print(ans)
else:
  pos = []
  neg = []
  for i in a:
    if i<0:
      neg.append(i)
    else:
      pos.append(i)
  if len(pos)+2*(len(neg)//2)>=k:
    i = 0
    left = 0
    right = n-1
    ans = 1
    while i<k-1:
      m1 = a[left]*a[left+1]
      m2 = a[right]*a[right-1]
      #print(m1,m2)
      if m1<m2:
        m2%=mod
        ans*=m2
        #print("r",right)
        right -=2
      else:
        m1 %= mod
        ans *= m1
        #print(left)
        left+=2
      ans %= mod
      i+=2
    ans *= a[right]
    ans %= mod
    print(ans)
  else:
    a = [0]
    print(a[2])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
N,K=map(int, input().split())
A=list(map(int, input().split()))
p=10**9+7
A=sorted(A)
thresh=bisect_left(A,0)
minus=A[:thresh]
plus=A[thresh:][::-1]

#print(plus, minus)
if len(plus)==0:
    ans=1
    if K%2!=0:
        minus=minus[::-1]
        for i in range(K):
            ans*=minus[i]
            ans%=p
    else:
        for i in range(K):
            ans*=minus[i]
            ans%=p
    print(ans)
    exit()

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

midx=0
pidx=0
ans=1

while K>0 and (0<=midx<len(minus) or 0<=pidx<len(plus)):
    if midx==len(minus)-1:
        nexmin=minus[midx]
    elif midx>=len(minus):
        nexmin=-1
    else:
        nexmin=minus[midx]*minus[midx+1]

    if pidx==len(plus)-1:
        nexplus=plus[pidx]
        fact=newplus
    elif pidx>=len(plus):
        nexplus=-float("INF")
        fact=nexplus
    else:
        #if plus[pidx+1]!=0:
        #    nexplus=plus[pidx]*plus[pidx+1]
        #else:
        #    nexplus=plus[pidx]
        nexplus=plus[pidx]*plus[pidx+1]
        fact=plus[pidx]

    if nexmin>=nexplus and K>=2:
        ans*=nexmin
        ans%=p
        midx+=2
        K-=2
    else:
        ans*=fact
        ans%=p
        pidx+=1
        K-=1


print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
mod = 10**9 + 7
if k%2==0:
  i = 0
  left = 0
  right = n-1
  ans = 1
  while i<k:
    m1 = a[left]*a[left+1]
    m2 = a[right]*a[right-1]
    #print(m1,m2)
    if m1<m2:
      m2%=mod
      ans*=m2
      #print("r",right)
      right -=2
    else:
      m1 %= mod
      ans *= m1
      #print(left)
      left+=2
    ans %= mod
    i+=2
  print(ans)
else:
  pos = []
  neg = []
  for i in a:
    if i>0:
      neg.append(i)
    else:
      pos.append(i)
  if len(pos)+2*(len(neg)//2)>=k:
    i = 0
    left = 0
    right = n-1
    ans = 1
    while i<k-1:
      m1 = a[left]*a[left+1]
      m2 = a[right]*a[right-1]
      #print(m1,m2)
      if m1<m2:
        m2%=mod
        ans*=m2
        #print("r",right)
        right -=2
      else:
        m1 %= mod
        ans *= m1
        #print(left)
        left+=2
      ans %= mod
      i+=2
    ans *= a[right]
    ans %= mod
    print(ans)
  else:
    a = [0]
    print(a[2])

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
mod = 10**9 + 7
if k%2==0:
  i = 0
  left = 0
  right = n-1
  ans = 1
  while i<k:
    m1 = a[left]*a[left+1]
    m2 = a[right]*a[right-1]
    #print(m1,m2)
    if m1<m2:
      m2%=mod
      ans*=m2
      #print("r",right)
      right -=2
    else:
      m1 %= mod
      ans *= m1
      #print(left)
      left+=2
    ans %= mod
    i+=2
  print(ans)
else:
  pos = []
  neg = []
  for i in a:
    if i>0:
      neg.append(i)
    else:
      pos.append(i)
  if len(pos)+2*(len(neg)//2)>=k:
    i = 0
    left = 0
    right = n-2
    ans = a[n-1]
    while i<k-1:
      m1 = a[left]*a[left+1]
      m2 = a[right]*a[right-1]
      #print(m1,m2)
      if m1<m2:
        m2%=mod
        ans*=m2
        #print("r",right)
        right -=2
      else:
        m1 %= mod
        ans *= m1
        #print(left)
        left+=2
      ans %= mod
      i+=2
    print(ans)
  else:
    a = [0]
    print(a[2])

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if (sum([1 for a in a_list if np.sign(a)!=-1])==0 and k%2==1) or (k==n and len([1 for a in a_list if np.sign(a)==-1])%2==1):
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    add = 1
    remove = 1
    if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
        negative_big = [num for num in a_list[:k] if np.sign(num)==-1]
        positive_big = [num for num in a_list[:k] if np.sign(num)!=-1]
        negative_small = [num for num in a_list[k:] if np.sign(num)==-1]
        positive_small = [num for num in a_list[k:] if np.sign(num)!=-1]
        
        
        if len(negative_big)==0 or len(positive_small)==0:
            remove = min(positive_big)
            add = min(negative_small)
        elif len(positive_big)==0 or len(negative_small)==0:
            remove = max(negative_big)
            add = max(positive_small)
        else:
            positive_small_max = max(positive_small)
            negative_big_max = max(negative_big)
            negative_small_min = min(negative_small)
            positive_big_min = min(positive_big)
            if positive_small_max/negative_big_max <= negative_small_min/positive_big_min:
                remove = negative_big_max
                add = positive_small_max
            else:
                remove = positive_big_min
                add = negative_small_min
a_list[a_list.index(remove)]=add
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
print(ans)

Submission status: Runtime Error

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

B = sorted(A, key=lambda x: abs(x), reverse=True)

score = 1
x = 0
y = 0
for j in range(K):
    score *= B[j]
    if B[j] > 0:
        x = B[j]
    elif B[j] < 0:
        y = B[j]

if score < 0 and (not N == K):
    scoreX = 0
    scoreY = 0
    flgX = 0
    flgY = 0
    for j in range(K,N):
        if B[j] > 0 and (not y == 0) and flgX == 0:
            scoreX = score / y * B[j]
            flgX = 1
        elif B[j] < 0 and (not x == 0) and flgY == 0:
            scoreY = score / x * B[j]
            flgY = 1
        elif B[j] == 0:
            scoreX = 0
            scoreY = 0
            flgX = 1
            flgY = 1
        if flgX == 1 and flgY == 1:
            break
    if flgX == 0 and flgY == 0:
        score = 1
        for j in range(N-K,N):
            score *= B[j]
    else:
        score = max(scoreX,scoreY)

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