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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
A = IL()
A = sorted(A,key= lambda x:-abs(x))

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

if max(A)<0 and K%2==1:
  ans = 1
  for i in range(K):
    ans *= A[N-1-i]
    ans %= MOD
  print(ans)
  exit()

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if A[i] < 0:
    last_M = i
    count_M += 1
  else:
    last_P = i

if count_M%2 == 0:
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans %= MOD
  print(ans)
  exit()

else:
  ANS1 = -INF
  ANS2 = -INF
  if last_M!=None:
    for i in range(K,N):
      if A[i] >= 0:
        CHANGE1 = A[i]
        ans = A[i]%MOD
        for ii in range(K):
          if ii != last_M:
            ans *= A[ii]
            ans %= MOD
        ANS1 = ans
        break
  if last_P!=None:
    for i in range(K,N):
      if A[i] <= 0:
        CHANGE2 = A[i]
        ans = A[i]%MOD
        for ii in range(K):
          if ii != last_P:
            ans *= A[ii]
            ans %= MOD
        ANS2 = ans
        break
  if last_M == None:
    print(ANS2)
  elif last_P == None:
    print(ANS1)
  else:
    if abs(last_M*CHANGE2)<abs(last_P*CHANGE1):
      print(ANS1)
    else:
      print(ANS2)

Submission status: Runtime Error

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        exit()
    if k%2 and not x:
        c=1
        for i in sorted(y)[-k:]:
            c=c*i%M
        print(c)
        exit()
    x=sorted(x)[::-1][:k]
    i=len(x)
    y.sort()
    m=len(y)
    j=0
    if i<k:
        j=k-i
        if j%2:1/0
        x+=y[:j]
        j+=1
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

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)
	else:
		minus.append(i)

plus.sort(key=lambda x:-x)
minus.sort()

#print(plus, minus)

"""
貪欲チックに求める
numplus … 前からnumplus番目まで掛け合わせる
numminus … 前からnumminus番目まで掛け合わせる

入力例2に合わせるのは場合分けが必要だが, minusは2個単位で管理する.
"""
numplus = k
numminus = 0

"""
kがplusを超える場合, うまく処理ができないのでリスト参照できる範囲まで下げる.
"""
while numplus > len(plus):
	numplus -= 2
	numminus += 2

if numplus < 0:
	numminus += numplus
	ans = 1
	tmp = sorted(a, key=lambda x:-x)
	for i in range(numminus):
		ans = ans * tmp[i] % mod
	print(ans)
	exit()

#print(numplus, numminus)

tmpplus = -1
tmpminus = -1

while numplus-2 >= 0 and numminus+2 <= len(minus):
	if plus[numplus-1] * plus[numplus-2] <= plus[numminus] * plus[numminus+1]:
		numplus -= 2
		numminus += 2
		tmpminus = numminus
		tmpplus = numplus
	else:
		break

#print(tmpminus, tmpplus)

ans = 1
for i in range(numplus):
	ans = ans * plus[i] % mod
for i in range(numminus):
	ans = ans * minus[i] % mod
print(ans)

Submission status: Runtime Error

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

a_p =[]
a_m =[]
for i in a:
    if i >= 0:
        a_p.append(i)
    else :
        a_m.append(i)

a_p.sort()
a_m.sort(reverse=True)


a_select =[]

if n == k:
    a_select = a
elif len(a_p) == 0:
    for i in range(k):
        a_select.append(a_m[i])


while len(a_select) < k:
    if len(a_select) == k - 1:
        a_select.append(a_p[-1])
        break
    if len(a_p) == 1 and (k-len(a_select))%2 == 1:
        a_select.append(a_p[-1])
    elif len(a_p) == 0:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))
    elif len(a_m) <= 1:
        a_select.append(a_p.pop(-1))
    elif a_p[-1]*a_p[-2] > a_m[-1]*a_m[-2] :
        a_select.append(a_p.pop(-1))
    else:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))

#print(a_select)
ans = 1
for i in a_select:
    ans = ans*i % (10**9 + 7)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import reduce
from operator import mul
from bisect import bisect_left


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def sign(x):
    if x == 0:
        return 0
    if x < 0:
        return -1
    return 1


class ModInt(int):
    
    MOD = 10**9+7

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)

    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)

    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)

    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)

    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()

    def __truediv__(self, other):
        inv = ModInt(other).inverse()
        return ModInt(super().__mul__(inv) % ModInt.MOD)

    def __floordiv__(self, other):
        return self.__truediv__(other)

    def __rtruediv__(self, other):
        return ModInt(self.inverse().__mul__(other))

    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)

    def _extgcd(self, a, b):
        assert not isinstance(a, ModInt) and not isinstance(b, ModInt)
        if a < b:
            m, y, x = self._extgcd(b, a)
            return (m, x, y)
        if b == 0:
            x = 1
            y = 0
            return (a, x, y)
        m, y, x = self._extgcd(b, a % b)
        y = y - a // b * x
        return (m, x, y)

    def inverse(self):
        a = int(self)
        m = int(ModInt.MOD)
        n, x, y = self._extgcd(a, m)
        if n != 1:
            raise ValueError("{} and {} are not mutually prime.".format(a, m))
        return ModInt(x)


def solve(N, K, A, p=10**9+7):
    A.sort(key=lambda x: -abs(x))
    base = 1
    sns = 1
    last_minus = -1
    last_plus = -1
    for i in range(K):
        a = A[i]
        base *= a
        base %= p
        sn = sign(a)
        sns *= sn
        if sn < 0:
            last_minus = i
        else:
            last_plus = i
    if sns >= 0:
        return base % p
    
    if last_plus == -1:
        base = 1
        for i in range(K):
            a = A[N-i-1]
            base *= a
            base %= p
        return base % p
    
    base1, base2 = base, base
    # 最も小さい負の数を1つ取り除いて、正の数を1つ足す(絶対値が大きいほど良い)
    assert last_minus < 0 or A[last_minus] < 0
    base1 *= pow(A[last_minus], p-2, p)
    base1 %= p
    m1 = max(A[K:])
    fac1 = abs(1.0 * m1 / A[last_minus])
    has_answer1 = (last_minus > 0 and m1 >= 0)
    base1 *= m1
    base1 %= p
    # 最も小さい"正の数"を1つ取り除いて、負の数を1つ足す(絶対値が大きいほど良い)
    assert last_plus < 0 or A[last_plus] > 0
    base2 *= pow(A[last_plus], p-2, p)
    base2 %= p
    m2 = min(A[K:])
    fac2 = abs(1.0 * m2 / A[last_plus])
    has_answer2 = (last_plus >= 0 and m2 < 0)
    base2 *= m2
    base2 %= p
    if not has_answer1:
        return base2 % p
    elif not has_answer2:
        return base1 % p
    elif fac1 >= fac2:
        return base1 % p
    else:
        return base2 % p



if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Runtime Error

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

a_p =[]
a_m =[]
for i in a:
    if i >= 0:
        a_p.append(i)
    else :
        a_m.append(i)

a_p.sort()
a_m.sort(reverse=True)


a_select =[]

if n == k:
    a_select = a

if len(a_p) == 0:
    for i in range(k):
        a_select.append(a_m[i])


while len(a_select) < k:
    if len(a_select) == k - 1:
        a_select.append(a_p[-1])
        break
    if len(a_p) == 1 and (k-len(a_select))%2 == 1:
        a_select.append(a_p[-1])
    elif len(a_p) == 0:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))
    elif len(a_m) <= 1:
        a_select.append(a_p.pop(-1))
    elif a_p[-1]*a_p[-2] > a_m[-1]*a_m[-2] :
        a_select.append(a_p.pop(-1))
    else:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))

#print(a_select)
ans = 1
for i in a_select:
    ans = ans*i % (10**9 + 7)

print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9+7
a1 = []
a2 = []
cnt = 0
for i in a:
    if (i >= 0):
        a1.append(i)
    else:
        a2.append(-i)
a1.sort()
a2.sort()
#print(a1,a2)
if (k==1):
    print(max(a)%mod)
    exit()
#n==kの場合
if (n==k):
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()
#負のみの場合
if (len(a1)==0):
    if (k%2==0):
        ans = 1
        for i in range(k):
            ans *= a2.pop()
            ans %= mod
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(k):
            ans *= -a2[i]
            ans %= mod
        print(ans)
        exit()
#正のみの場合
elif (len(a2)==0):
    ans = 1
    for i in range(k):
        ans *= a1.pop()
        ans %= mod
    print(ans)
    exit()

bef1 = 10**10　#
bef2 = 10**10
index1 = 0
index2 = 0
ans = 1
for i in range(k):
    if (len(a1)==0):
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        bef2 = x
        continue
    if (len(a2)==0 or a1[-1]>=a2[-1]):
        x = a1.pop()
        ans *= x
        ans %= mod
        index1 += 1
        bef1 = x
    else:
        x = a2.pop()
        ans *= x
        ans %= mod
        index2 += 1
        cnt += 1
        bef2 = x
if (cnt%2==1):
    if len(a1)>0 and len(a2)>0:
        if (index1==0):
            ans *= a1[-1]
            ans *= pow(bef2,mod-2,mod)
            ans %= mod
        elif (index2==0):
            ans *= a2[-1]
            ans *= pow(bef1,mod-2,mod)
            ans %= mod
        else:
            A = a1[-1]/bef2
            B = a2[-1]/bef1
            if (A>=B):
                ans *= a1[-1]
                ans *= pow(bef2,mod-2,mod)
                ans %= mod
            else:
                ans *= a2[-1]
                ans *= pow(bef1,mod-2,mod)
                ans %= mod
    elif (len(a1)==0):
        ans *= a2[-1]
        ans *= pow(bef1,mod-2,mod)
        ans %= mod
    else:
        ans *= a1[-1]
        ans *= pow(bef2,mod-2,mod)
        ans %= mod
if 0 in a:
    print(max(0,ans%mod))
else:
    print(ans%mod)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = sorted(list(map(int,input().split())))
ans = 1
ansb = 1
if K % 2 == 0:
    for i in range(K//2):
        if A[0]*A[1] >= A[-1]*A[-2]:
            ans *= A[0]*A[1]
            A.pop(0)
            A.pop(1)
        elif A[0]*A[1] < A[-1]*A[-2]:
            ans *= A[-1]*A[-2]
            A.pop(-1)
            A.pop(-2)
elif K == 1:
    ans = A[-1]
elif K % 2 == 1 and K != 1:
    B = list.copy(A)
    for i in range(K//2):
        if A[0]*A[1] >= A[-1]*A[-2]:
            ans *= A[0]*A[1]
            A.pop(0)
            A.pop(0)
        elif A[0]*A[1] < A[-1]*A[-2]:
            ans *= A[-1]*A[-2]
            A.pop(-1)
            A.pop(-1)
    ans *= A[-1]
    for i in range(K//2):
        if B[0]*B[1] <= B[-1]*B[-2]:
            ansb *= B[0]*B[1]
            B.pop(0)
            B.pop(0)
        elif B[0]*B[1] > B[-1]*B[-2]:
            ansb *= B[-1]*B[-2]
            B.pop(-1)
            B.pop(-1)
    ansb *= B[-1]
    ans = max(ans,ansb)
print(ans%(7+10**9))

Submission status: Runtime Error

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        1/0
        exit()
    if k%2 and not x:
        c=1
        for i in sorted(y)[-k:]:
            c=c*i%M
        print(c)
        exit()
    x=sorted(x)[::-1][:k]
    y.sort()
    m=len(y)
    i=len(x)
    j=0
    if i<k:
        j=k-i
        x+=y[:j]
        j+=1
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
A = IL()
A = sorted(A,key=lambda x:-abs(x))

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

if max(A)<0 and K%2==1:
  ans = 1
  for i in range(K):
    ans *= A[N-1-i]
    ans %= MOD
  print(ans)
  exit()

count_M = 0
last_M = None
last_P = None
for i in range(K):
  if A[i] < 0:
    last_M = i
    count_M += 1
  else:
    last_P = i

if count_M%2 == 0:
  ans = 1
  for i in range(K):
    ans *= A[i]
    ans %= MOD
  print(ans)
  exit()

else:
  ANS1 = -INF
  ANS2 = -INF
  if last_M!=None:
    for i in range(K,N):
      if A[i] >= 0:
        CHANGE1 = A[i]
        break
  if last_P!=None:
    for i in range(K,N):
      if A[i] < 0:
        CHANGE2 = A[i]
        break
  if last_M!=None and last_P!=None:
    if abs(last_M*CHANGE2)<abs(last_P*CHANGE1):
      ans = CHANGE1%MOD
      for i in range(K):
        if i!=last_M:
          ans*=A[i]
          ans%=MOD
    else:
      ans = CHANGE2%MOD
      for i in range(K):
        if i!=last_P:
          ans*=A[i]
          ans%=MOD
  elif last_M!=None:
    ans = CHANGE1%MOD
    for i in range(K):
      if i!=last_M:
        ans*=A[i]
        ans%=MOD
  else:
    ans = CHANGE2%MOD
    for i in range(K):
      if i!=last_P:
        ans*=A[i]
        ans%=MOD
  print(ans)

Submission status: Runtime Error

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

a_p =[]
a_m =[]
for i in a:
    if i >= 0:
        a_p.append(i)
    else :
        a_m.append(i)

a_p.sort()
a_m.sort(reverse=True)


a_select =[]

if len(a_p) == 0:
    for i in range(k):
        a_select.append(a_m[i])


while len(a_select) < k:
    if len(a_select) == k - 1:
        a_select.append(a_p[-1])
        break
    if len(a_p) == 1 and (k-len(a_select))%2 == 1:
        a_select.append(a_p[-1])
    elif len(a_p) == 0:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))
    elif len(a_m) <= 1:
        a_select.append(a_p.pop(-1))
    elif a_p[-1]*a_p[-2] > a_m[-1]*a_m[-2] :
        a_select.append(a_p.pop(-1))
    else:
        a_select.append(a_m.pop(-1))
        a_select.append(a_m.pop(-1))

#print(a_select)
ans = 1
for i in a_select:
    ans = ans*i % (10**9 + 7)

print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
pos = [*filter(lambda x: x>0, A)]
neg = [*filter(lambda x: x<0, A)]
pos.sort(reverse=True)
neg.sort()
if len(pos) + len(neg) < K:
    print(0)
    exit()

ans = 1
i,j = 0,0# 使った数
while i+j < K:
    flag = True
    if i == len(pos):
        flag = False
    elif j == len(neg):
        flag = True
    elif pos[i] >= -neg[j]:
        flag = True
    else:
        flag = False

    if flag:
        ans = ans * pos[i] % m
        i += 1
    else:
        ans = ans * neg[j] % m
        j += 1
# print(i,j)
if j % 2 == 0 or N==K:
    print(ans)
elif len(pos) == 0:
    ans = 1
    for i in range(K):
        ans = ans * neg[len(neg)-1-i] % m
    print(ans)
else:
    flag2 = True
    if i == len(pos):
        flag2 = False
    elif j == len(neg):
        flag2 = True
    elif pos[i-1]*pos[i] >= neg[j-1]*neg[j]:
        flag2 = True
    else:
        exit(1)
        flag2 = False

    if flag2:
        ans = ans * pow(neg[j-1],m-2,m) % m
        ans = ans * pos[i] % m
    else:
        ans = ans * pow(pos[i-1],m-2,m) % m
        ans = ans * neg[j] % m
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        exit()
    if k%2 and not x:
        c=1
        for i in sorted(y)[-k:]:
            c=c*i%M
        print(c)
        1/0
        exit()
    x=sorted(x)[::-1][:k]
    y.sort()
    m=len(y)
    i=len(x)
    j=0
    if i<k:
        j=k-i
        x+=y[:j]
        j+=1
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

def list_safe_get(l, index, default=None):
    if index < len(l):
        return l[index]
    return default

class ModInt(int):

    MOD = 10 ** 9 + 7

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def mysplit(data):
    ps = [] # include 0
    ms = []
    for d in data:
        if d < 0:
            ms.append(ModInt(d))
        else:
            ps.append(ModInt(d))
    return list(reversed(sorted(ps))), sorted(ms)

def small_abs(ms, k):
    ans = ModInt(1)
    ms = list(reversed(ms))
    for i in range(k):
        ans *= ms[i]
    return ans

def factor_all(factors):
    #print('factors') # debug
    #print(factors) # debug
    ans = ModInt(1)
    for f in factors:
        ans *= f
    return ans

def solve(data, k):
    if len(data) == k:
        ans = ModInt(1)
        for d in data:
            ans *= d
        return ans
    ps, ms = mysplit(data)
    if len(ps) == 0:
        return small_abs(ms, k)
    factors = []
    sign_p = True
    pk = 0
    mk = 0
    while k > 0:
        if pk >= len(ps):
            factors.append(ms[mk]); mk += 1; k -= 1; sign_p = not sign_p; continue
        if mk >= len(ms):
            factors.append(ps[pk]); pk += 1; k -= 1; continue
        if ps[pk] > -1 * ms[mk]:
            factors.append(ps[pk]); pk += 1; k -= 1; continue
        else:
            factors.append(ms[mk]); mk += 1; k -= 1; sign_p = not sign_p; continue
    if sign_p is False:
        cand_rm_p = ps[pk - 1]
        cand_add_m = list_safe_get(ms, mk)
        cand_rm_m = ms[mk - 1]
        cand_add_p = list_safe_get(ps, pk)
        if cand_add_m is not None and cand_rm_m * cand_add_m < cand_rm_p * cand_add_p:
            factors.remove(cand_rm_p)
            factors.append(cand_add_m)
        else:
            factors.remove(cand_rm_m)
            factors.append(cand_add_p)
    return factor_all(factors)


if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    data = list(map(int, input().split()))
    ans = solve(data, k)
    #print('ans') # debug
    print(ans)



    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop, heapify, heappush
mod = 10**9 + 7
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
plus = []
minus = []
zero = []
ans = []
for a in A:
    if a > 0:
        plus.append(-a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(a)
heapify(plus)
heapify(minus)
cnt = 0
last_minus = 0
last_plus = 0
if len(plus) + len(minus) < K:
    print(0)
    sys.exit()

if len(plus) == 0:
    if K%2 == 1:
        print(0)
        sys.exit()
    else:
        num = 1
        minus.sort()
        for x in minus[:K]:
            if x < 0:
                x = -x
            num *= x
            num %= mod
        print(num%mod)
        sys.exit()

if len(minus) == 0:
    num = 1
    plus.sort(reverse=True)
    for x in plus[:K]:
        if x < 0:
            x = -x
        num *= x
        num %= mod
    print(num%mod)
    sys.exit()

if len(plus) + len(minus) == K:
    if len(minus)%2 == 0:
        num = 1
        for x in plus:
            num *= x%mod
        for x in minus:
            num *= x%mod
        print(num%mod)
        sys.exit()
    else:
        print(0)
        sys.exit()
        
flag = 0

for i in range(K):
    if len(plus) > 0 and len(minus) > 0:
        a = heappop(plus)
        b = heappop(minus)
    elif len(plus) == 0:
        flag = 1
        break
    else:
        flag = 2
        break
    if a >= b:
        ans.append(b)
        heappush(plus, a)
        cnt += 1
        last_minus = b
    else:
        ans.append(a)
        heappush(minus, b)
        last_plus = a

if flag == 1:
    for i in range(K - len(ans)):
        a = heappop(minus)
        last_minus = a
        cnt += 1
        ans.append(a)

if flag == 2:
    for i in range(K - len(ans)):
        a = heappop(plus)
        last_plus = a
        ans.append(a)

if cnt%2 == 0:
    num = 1
    for a in ans:
        if a < 0:
            a = -a
        num = (num * a%mod)%mod
    print(num%mod)
else:
    num = 1
    ls = []
    for a in ans:
        if a < 0:
            ls.append(-a)
        else:
            ls.append(a)

    if len(plus) != 0 and len(minus) != 0:
        a = heappop(plus)
        b = heappop(minus)
        if a < 0:
            a = -a
        if b < 0:
            b = -b
        if last_minus < 0:
            last_minus = -last_minus
        if last_plus < 0:
            last_plus = -last_plus
        
        if last_plus == 0:
            for c in ls[:-1]:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
        if last_minus == 0:
            for c in ls[:-1]:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)

        if a *last_plus >= b*last_minus:
            ls.remove(last_minus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * a%mod)%mod
            print(num%mod)
        else:
            ls.remove(last_plus)
            for c in ls:
                num = (num * c%mod)%mod
            num = (num * b%mod)%mod
            print(num%mod)
    elif len(plus) == 0:
        c = heappop(minus)
        if c < 0:
            c = -c
        if last_plus < 0:
            last_plus = -last_plus
        ls.remove(last_plus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)
    elif len(minus) == 0:
        c = heappop(plus)
        if c < 0:
            c = -c
        if last_minus < 0:
            last_minus = -last_minus
        ls.remove(last_minus)
        for a in ls:
            if a < 0:
                a = -a
            num = (num * a%mod)%mod
        num = (num * c%mod)%mod
        print(num%mod)