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:
#!/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


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 solve_all(data):
    ans = ModInt(1)
    for d in data:
        ans *= ModInt(d)
    return ans

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

def take_p(pk, mk):
    return pk + 1, mk

def take_m(pk, mk):
    return pk, mk + 1

def take(ps, pk, ms, mk):
    if not takable(ps, pk)
        return take_m(pk, mk)
    if not takable(ms, mk):
        return take_p(pk, mk)
    p = ps[pk]
    m = ms[mk]
    if p > -1 * m:
        return take_p(pk, mk)
    else:
        return take_m(pk, mk)

def ans_is_minus(mk):
    if mk % 2 == 0:
        return False
    else:
        return True

def factorize(ps, pk, ms, mk):
    ans = ModInt(1)
    for i in range(pk):
        ans *= ModInt(ps[i])
    for i in range(mk):
        ans *= ModInt(ms[i])
    return ans

def takable(s, k):
    if k < len(s):
        return True
    else:
        return False

def rm_m_add_p(pk, mk):
    return pk + 1, mk - 1

def rm_p_add_m(pk, mk):
    return pk - 1, mk + 1

def adjust(ps, pk, ms, mk):
    if not takable(ps, pk):
        return rm_p_add_m(pk, mk)
    if not takable(ms, mk):
        return rm_m_add_p(pk, mk)
    rm_p = ps[pk - 1]
    add_p = ps[pk]
    rm_m = ms[mk - 1]
    add_m = ms[mk]
    if add_p * rm_p > add_m * rm_m: # ans * add_p / abs(rm_m) > ans * abs(add_m) / rm_p
        return rm_m_add_p(pk, mk)
    else:
        return rm_p_add_m(pk, mk)


def solve_main(ps, ms, k):
    pk = 0
    mk = 0
    while k > 0:
        pk, mk = take(ps, pk, ms, mk)
        k -= 1
    if not ans_is_minus(mk):
        return factorize(ps, pk, ms, mk)
    pk, mk = adjust(ps, pk, ms, mk)
    return factorize(ps, pk, ms, mk)



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

def solve(data, k):
    if len(data) == k:
        return solve_all(data)
    ps, ms = mysplit(data)
    if len(ps) == 0 and k % 2 != 0:
        return solve_minus(ms, k)
    return solve_main(ps, ms, k)


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:
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N or N == K:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if ans != 0 and not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    multimul = lambda L,i=0: (L[i] * multimul(L,i+1) % P  if i+1 < len(L) else  L[i])
    INF = 10**18+10

    N,K = LMIIS()
    A = LMIIS()
    
    if N == K:
        print(multimul(A))
        return
    not_negative = []
    negative = []
    for a in A:
        if a < 0:
            negative.append(a)
        else:
            not_negative.append(a)
    if len(negative) == N and K % 2 == 1:
        print(multimul(sorted(negative,reverse=True)[:K]))
        return
    not_negative.sort(reverse=True)

    not_negative = deque(not_negative)
    negative.sort()
    negative = deque(negative)
    ans = 1
    num_multiplied = 0
    while num_multiplied < K:
        if num_multiplied == K-1 or not_negative[0] * not_negative[1] > negative[0] * negative[1]:
            ans = ans * not_negative.popleft() % P
            num_multiplied += 1
        else:
            ans = ans * negative.popleft() * negative.popleft() % P
            num_multiplied += 2
    print(ans)
            


    
main()

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if ans != 0 and not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#正の場合、0の場合、負の場合で分ける
#負の数のみの場合は調整しようがない
#偶数の時は絶対値の大きい順
#奇数の時は絶対値の小さい順
#正の数のみの場合は大きい順
#大きい順

#他は調整できるので、正で大きくする方向で考える(正→0以上)
#負の数は偶数個ないと正にならないので二つ一組で先にかけて考える
#正の数も同様に先にかけて、その中で大きいものを選べば良い

#負の数が奇数個、正の数が奇数個の時(負の数が余る、正の数が余る)
#Kが偶数の時はいい感じに選んでく(N=kの時は仕方ないので全部)
#Kが奇数の時は正の中で最大のものを選ぶ
#負の数が偶数個、正の数が奇数個の時(正の数が余る)
#Kが偶数の時はいい感じに選んでく
#奇数の時は残りの正の中から選ぶ
#負の数が奇数個、正の数が偶数個の時(負の数が余る)
#N=Kの時は全部選ぶ、それ以外の場合は余った負の数はいらない
#Kが奇数の時は残りの正の中で最大のものを選べば良い
#負の数が偶数個、正の数が偶数個の時
#Kが奇数の時は残りの正の中で最大のものを選べば良い

#N=Kの時は別で分けて考えるとすると、負の数及び正の数によらず
#Kが偶数の時は大きいものからいい感じに選んでく
#Kが奇数の時は最後の残り一個は正の残りの中で最大のものを選ぶ
#と簡単に言い換えることができる

#x:配列
mod=10**9+7
def multarray(x):
    ret=1
    for i in x:
        ret*=i
        ret%=mod
    return ret

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

if n==k:
    print(multarray(a))
    exit()

ap,am=[],[]
for i in range(n):
    if a[i]>=0:
        ap.append(a[i])
    else:
        am.append(a[i])
#絶対値の順番
ap.sort(reverse=True)
am.sort()

if len(am)==0:
    print(multarray(ap[:k]))
    exit()
if len(ap)==0:
    if k%2==0:
        print(multarray(am[:k]))
    else:
        print(multarray(am[::-1][:k]))
    exit()

apm2=[]
for i in range(len(am)//2):
    apm2.append((am[2*i]*am[2*i+1],0))
for i in range(len(ap)//2):
    apm2.append((ap[2*i]*ap[2*i+1],1))
apm2.sort(reverse=True)

#+の次にどこを見るのかをチェックしておく
p=0
ans=[]
for i in range(k//2):
    p+=(2*apm2[i][1])
    ans.append(apm2[i][0])

if k%2==0:
    print(multarray(ans))
    exit()

#ここで不正アクセスの可能性を避ける
#プラスが余ってない場合(一個減らして次のマイナス使う)
#余ってる場合もafter_contestで落ちる
#その一個をとるのが最適とは限らず、一個減らして次のマイナスの二個とる場合も
ans_cand=[]
#一個増やす場合
if p!=len(ap)
    ans_cand.append(multarray(ans)*ap[p]%mod)
if p>=2:
    #一個減らして二個増やす場合
    check_i=ans.index(ap[p-1]*ap[p-2])
    #0除算を避ける
    ans[check_i]=ap[p-2]
    ans.append(apm2[k//2][0])
    ans_cand.append(multarray(ans))
print(max(ans_cand))

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextpos = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N:
        ans = 1
        neg = []
        while len(q):
            num, _ = heappop(q)
            neg.append(num)
        for i in range(K):
            num = neg[-i-1]
            ans = (ans * num) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    while K:
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        K -= 1
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextpos = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
c = []
for i in range(n):
  if a[i]>=0:
    b.append(a[i])
  else:
    c.append(a[i])

ans = 1
if max(0, k-len(b)) % 2 == 0:
  b = sorted(b)[::-1] + [0, 0]
  c = sorted(c) + [0]
  b_i = 0
  c_i = 0
  while b_i+c_i<k:
    if k-(b_i+c_i)>1 and c[c_i]*c[c_i + 1]>b[b_i]:
      ans *= (c[c_i] * c[c_i+1])
      ans %= (10**9+7)
      c_i += 2
    else:
      ans *= b[b_i]
      ans %= (10**9+7)
      b_i += 1
else:
  b = sorted(b)
  c = sorted(c)[::-1]
  b_i = 0
  c_i = 0
  while b_i+c_i<k:
    if b_i==len(b):
      ans *= c[c_i]
      ans %= (10**9+7)
      c_i += 1
    elif c_i==len(c):
      ans *= b[b_i]
      b_i += 1
    else:
      if b[b_i] < c[c_i]:
        ans *= b[b_i]
        ans %= (10**9+7)
        b_i += 1
      else:
        ans *= c[c_i]
        ans %= (10**9+7)
        c_i += 1


ans %= (10**9+7)
if ans<0:
  ans -= (10**9+7)
print(abs(ans))

Submission status: Runtime Error

Solution code:
def calc(arr):
    res = 1
    for a in arr:
        res *= a
        res %= MOD
    return res

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x), reverse=True)
cnt = sum(1 if a <= 0 else 0 for a in A)
if cnt == N:
    if K % 2 == 0:
        res = calc(A[:N])
    else:
        res = calc(A[N-1:N-K-1:-1])
else:
    plus = MOD
    minus = -MOD
    cnt = 0
    tmp = [0] * K
    for i, a in enumerate(A[:K]):
        tmp[i] = a
        if a > 0:
            plus = i
        else:
            cnt += 1
            minus = i
    if cnt % 2 == 1:
        p = -1
        m = 1
        for a in A[K:]:
            if a >= 0 and p < 0:
                p = a
            if a < 0 and m > 0:
                m = a
            if p >= 0 and m < 0:
                break
        if tmp[plus] * p < tmp[minus] * m:
            tmp[plus] = m
        else:
            tmp[minus] = p
    res = calc(tmp)
print(res)

Submission status: Runtime Error

Solution code:
n, k = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
p = list(filter(lambda x: x>=0, l))
n = list(filter(lambda x: x<0, l))
p.sort()
n.sort()
pIndex = len(p)-1
nIndex = len(n)-1
ans = 1
nThere = True

if pIndex>0:
    pp = p[pIndex]*p[pIndex-1]
else:
    pp=-1
    
if nIndex>0:
    np = n[nIndex]*n[nIndex-1]
else:
    np = 1
	nThere = False
    
while(k>0):
    if k>1 and nThere:
        k-=2
        if np>pp:
            ans*=np%1000000007
            nIndex-=2
            if nIndex>0:
                np=n[nIndex]*n[nIndex-1]
            else:
             	nThere = False
        else:
            ans*=pp%1000000007
            pIndex-=2
            if pIndex>0:
                pp=p[pIndex]*p[pIndex-1]
            else:
              	pp=-1
    elif pIndex>-1:
        k-=1
        ans*=p[pIndex]%1000000007
        pIndex-=1
        if pIndex>0:
                pp=p[pIndex]*p[pIndex-1]
        else:
          		pp=-1
    else:
        k-=1
        ans*=n[nIndex]%1000000007
        nIndex-=1
        
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
BC = []
for a in A:
    if a >= 0:
        B.append(a)
        BC.append(a)
    else:
        C.append(-a)
        BC.append(-a)
ans = 1
if len(B) == 0:
    C = sorted(C)
    for i in range(K):
        ans *= C[i]
        ans %= MOD
    if K % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    sys.exit()
if N == K:
    for i in range(K):
        ans *= BC[i]
        ans %= MOD
    if len(C) % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    sys.exit()  
negs_p = 0
non_negs_p = 0
for i in range(K):
    if negs_p == len(C):
        non_negs_p += 1
    elif non_negs_p == len(B):
        negs_p += 1
    elif C[negs_p] > B[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)
BC = sorted(BC,reverse = True)

for i in range(K):
    ans *= BC[i]
    ans %= MOD

if negs_p % 2 == 1:
    if negs_p == len(C):      
        b,c = C[negs_p-1],B[non_negs_p]
        ans = (ans*MOD // b) * c % MOD
    elif non_negs_p == len(B):
        a,d = C[negs_p],B[non_negs_p-1]
        ans = (ans*MOD // d) * a % MOD
    else:
        a,b,c,d = C[negs_p],C[negs_p-1],B[non_negs_p],B[non_negs_p-1]
        if a*b > c*d:
            ans = (ans*MOD // d) * a % MOD
        else:
            ans = (ans*MOD // b) * c % MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
BC = []
for a in A:
    if a >= 0:
        B.append(a)
        BC.append(a)
    else:
        C.append(-a)
        BC.append(-a)
ans = 1
if len(B) == 0:
    C = sorted(C)
    for i in range(K):
        ans *= C[i]
        ans %= MOD
    ans *= -1
    ans %= MOD
    print(ans)
    sys.exit()
if N == K:
    for i in range(K):
        ans *= BC[i]
        ans %= MOD
    if len(C) % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    sys.exit()  
negs_p = 0
non_negs_p = 0
for i in range(K):
    if negs_p == len(C):
        non_negs_p += 1
    elif non_negs_p == len(B):
        negs_p += 1
    elif C[negs_p] > B[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)
BC = sorted(BC,reverse = True)

for i in range(K):
    ans *= BC[i]
    ans %= MOD

if negs_p % 2 == 1:
    if negs_p == len(C):      
        b,c = C[negs_p-1],B[non_negs_p]
        ans = (ans*MOD // b) * c % MOD
    elif non_negs_p == len(B):
        a,d = C[negs_p],B[non_negs_p-1]
        ans = (ans*MOD // d) * a % MOD
    else:
        a,b,c,d = C[negs_p],C[negs_p-1],B[non_negs_p],B[non_negs_p-1]
        if a*b > c*d:
            ans = (ans*MOD // d) * a % MOD
        else:
            ans = (ans*MOD // b) * c % MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from operator import mul
from functools import reduce
from collections import deque

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


MOD = 10**9 + 7

# negを奇数個選ばないといけないシチュエーションかどうか
neg = [x < 0 for x in arr]

if all(neg) and k % 2 == 1:
    arr.sort(reverse=True)
    print(reduce(mul, arr[:k]) % MOD)
    sys.exit()

arr_p = [x for x in arr if x >= 0]
arr_n = [x for x in arr if x < 0]

arr_p.sort(reverse=True)
arr_n.sort()

arr_p = deque(arr_p)
arr_n = deque(arr_n)

ans = 1
cnt = 0
while len(arr_p) >= 2 and len(arr_n) >= 2 and k // 2 * 2 >= cnt:
    a = arr_p.popleft()
    b = arr_p.popleft()
    c = arr_n.popleft()
    d = arr_n.popleft()
    if a * b <= c * d:
        ans *= c * d
        ans %= MOD
        arr_n.appendleft(c)
        arr_n.appendleft(d)
    else:
        ans *= a * b
        ans %= MOD
        arr_p.appendleft(a)
        arr_p.appendleft(b)
    cnt += 2

if k != cnt:
    while k > cnt:
        a = arr_p.popleft()
        ans *= a
        ans %= MOD
        cnt += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
A = list(map(int,readline().split()))
MOD = 10**9 +7
B = []
C = []
BC = []
for a in A:
    if a >= 0:
        B.append(a)
        BC.append(a)
    else:
        C.append(-a)
        BC.append(-a)
ans = 1
if len(B) == 0:
    C = sorted(C)
    for i in range(K):
        ans *= C[i]
        ans %= MOD
    ans *= -1
    ans %= MOD
    print(ans)
    sys.exit()
if N == K:
    for i in range(K):
        ans *= BC[i]
        ans %= MOD
    if len(C) % 2 == 1:
        ans *= -1
        ans %= MOD
    print(ans)
    sys.exit()  
negs_p = 0
non_negs_p = 0
for i in range(K):
    if negs_p == len(C):
        non_negs_p += 1
    elif non_negs_p == len(B):
        negs_p += 1
    elif C[negs_p] > B[non_negs_p]:
        negs_p += 1
    else:
        non_negs_p += 1
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)
BC = sorted(BC,reverse = True)

print(BC)
for i in range(K):
    ans *= BC[i]
    ans %= MOD

if negs_p % 2 == 1:
    if negs_p == len(C):      
        b,c = C[negs_p-1],B[non_negs_p]
        ans = (ans*MOD // b) * c % MOD
    elif non_negs_p == len(B):
        a,d = C[negs_p],B[non_negs_p-1]
        ans = (ans*MOD // d) * a % MOD
    else:
        a,b,c,d = C[negs_p],C[negs_p-1],B[non_negs_p],B[non_negs_p-1]
        if a*b > c*d:
            ans = (ans*MOD // d) * a % MOD
        else:
            ans = (ans*MOD // b) * c % MOD
print(ans)

Submission status: Runtime Error

Solution code:
# E - Multiplication 4
import heapq
N, K = map(int, input().split())
A = list(int(a) for a in input().split())
MOD = 10**9 + 7

# N = K の時
if N == K:
    ans = 1
    for a in A:
        ans = (ans * a) % MOD

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

    # 必ずマイナスになる時＝全てがマイナスの値であり、
    # かつKが奇数の時
    if len(neg) == N and K&1 == 1:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD

    # それ以外のプラスになるケース
    # プラスの要素とマイナスの要素を絶対値の大きい順にソートし、
    # Kが奇数であれば、プラスのリストから1つ選び、
    # 残りの偶数個のKに対して、２つずつを選んだ時の
    # 大きい方から取得していく
    else:
        pos.sort(reverse=True)
        pos2 = []
        ans = 1
        ini = 0
        rem = K
        if K&1 == 1:
            ans = (ans * pos[0]) % MOD
            ini = 1
            rem -= 1
        for i in range(0, len(pos)//2):
            heapq.heappush(pos2, (pos[i*2+ini] * pos[i*2+ini+1])*-1)
        neg.sort()
        neg2 = []
        for i in range(0, len(neg)//2):
            heapq.heappush(neg2, (neg[i*2] * neg[i*2+1]) * -1)
        while rem > 0:
            if (pos2 != [] and neg2 != [] and pos2[0] <= neg2[0]) or (pos2 != [] and neg2 == []):
                tmp = heapq.heappop(pos2) * -1
            else:
                tmp = heapq.heappop(neg2) * -1
            ans = (ans * tmp) % MOD
            rem -= 2

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from operator import mul
from functools import reduce
from collections import deque

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


MOD = 10**9 + 7

# negを奇数個選ばないといけないシチュエーションかどうか
neg = [x < 0 for x in arr]

if all(neg) and k % 2 == 1:
    arr.sort(reverse=True)
    print(reduce(mul, arr[:k]) % MOD)
    sys.exit()

arr_p = [x for x in arr if x >= 0]
arr_n = [x for x in arr if x < 0]

arr_p.sort(reverse=True)
arr_n.sort()

arr_p = deque(arr_p)
arr_n = deque(arr_n)

ans = 1
cnt = 0
while len(arr_p) >= 2 and len(arr_n) >= 2 and k // 2 * 2 >= cnt:
    a = arr_p.popleft()
    b = arr_p.popleft()
    c = arr_n.popleft()
    d = arr_n.popleft()
    if a * b <= c * d:
        ans *= c * d
        ans %= MOD
        arr_n.appendleft(c)
        arr_n.appendleft(d)
    else:
        ans *= a * b
        ans %= MOD
        arr_p.appendleft(a)
        arr_p.appendleft(b)
    cnt += 2

if k != cnt:
    ans *= reduce(mul, arr_p[:k - cnt])

print(ans % MOD)

Submission status: Runtime Error

Solution code:
# E - Multiplication 4
import heapq
N, K = map(int, input().split())
A = list(int(a) for a in input().split())
MOD = 10**9 + 7

# N = K の時
if N == K:
    ans = 1
    for a in A:
        ans = (ans * a) % MOD

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

    # 必ずマイナスになる時＝全てがマイナスの値であり、
    # かつKが奇数の時
    if len(neg) == N and K&1 == 1:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD

    # それ以外のプラスになるケース
    # プラスの要素とマイナスの要素を絶対値の大きい順にソートし、
    # Kが奇数であれば、プラスのリストから1つ選び、
    # 残りの偶数個のKに対して、２つずつを選んだ時の
    # 大きい方から取得していく
    else:
        pos.sort(reverse=True)
        pos2 = []
        ans = 1
        ini = 0
        rem = K
        if K&1 == 1:
            ans = (ans * pos[0]) % MOD
            ini = 1
            rem -= 1
        for i in range(0, len(pos)//2, 2):
            heapq.heappush(pos2, (pos[i*2+ini] * pos[i*2+ini+1])*-1)
        neg.sort()
        neg2 = []
        for i in range(0, len(neg)//2, 2):
            heapq.heappush(neg2, (neg[i*2] * neg[i*2+1]) * -1)
        while rem > 0:
            if (pos2 != [] and neg2 != [] and pos2[0] <= neg2[0]) or (pos2 != [] and neg2 == []):
                tmp = heapq.heappop(pos2) * -1
            else:
                tmp = heapq.heappop(neg2) * -1
            ans = (ans * tmp) % MOD
            rem -= 2

print(ans)

Submission status: Runtime Error

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

ze = []
pl,mi = [],[]
for i in range(n):
    if a[i] < 0:
        ze.append((-a[i],1))
        mi.append(a[i])
    else:
        ze.append((a[i],0))
        pl.append(a[i])
        
ze.sort(reverse = True)
pl.sort(reverse = True)
mi.sort()

one = 0
for i in range(k):
    one += ze[i][1]
    
ans = 1
zero = k-one

if one % 2 == 0:
    for i in range(k):
        ans = ans * ze[i][0] % MOD
    print(ans)
        
elif len(pl) == 0:
    for i in range(k):
        ans = ans * mi[n-1-i] % MOD
    print(ans)
        
else:
    if (zero == len(pl) and one == len(mi)) or one == 0 or zero == 0:
        ak = [zero,one]
    elif (zero != len(pl) and one == len(mi)):
        ak = [zero+1,one-1]
    elif zero == len(pl) and one != len(mi):
        ak = [zero-1,one+1]
    else:
        if abs(mi[zero])/pl[one-1] >= pl[one]/abs(mi[zero-1]):
            ak = [zero+1,one-1]
        else:
            ak = [zero-1,one+1]
            
    ans = 1
    for i in range(ak[0]):
        ans = ans * pl[i] % MOD
    for i in range(ak[1]):
        ans = ans * mi[i] % MOD
        
    print(ans)