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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
A = sorted(A, key = lambda x:abs(x), reverse=True)
#print(A)
 
ans = []
negidx = 0
posidx = 0
neg = False
for i in range(K):
  a = A[i]
  ans.append(a)
  if a<0:
    negidx = i
    neg = not neg
  else:
    posidx = i
#print(ans, neg, negidx)
answer = 1
if neg:
  poppos = list(ans)
  pg = poppos.pop(posidx)
  popneg = list(ans)
  ng = popneg.pop(negidx)
  pgratio = None
  ngratio = None
  found = 0
  for i in range(K+1, N):
    if A[i]>=0 and ngratio is None:
      found = 1
      popneg.append(A[i])
      ngratio = -A[i]/ng
    if A[i]<0 and pgratio is None:
      found = 2
      poppos.append(A[i])
      pgratio = -A[i]/pg
    if pgratio is not None and npratio is not None:
      found = 3
      break
  if found == 1:
    for a in popnep:
      answer *= abs(a)%1000000007
    print(answer%1000000007)
  elif found == 2:
    for a in poppos:
      answer *= abs(a)%1000000007
    print(answer%1000000007)
  elif found == 3:
    if pgratio > ngratio:
      for a in poppos:
        answer *= abs(a)%1000000007
      print(answer%1000000007)
    else:
      for a in popneg:
        answer *= abs(a)%1000000007
      print(answer%1000000007)
  else:
    for i in range(K):
      answer *= A[-(i+1)]%1000000007
    print(answer%1000000007)
else:
  for a in ans:
    answer *= abs(a)%1000000007
  print(answer%1000000007)

Submission status: Runtime Error

Solution code:
import sys
n,k=map(int,input().split())
a = list(map(int,input().split()))
plus = sorted([i for i in a if i > 0],reverse=True)
minus = sorted([i for i in a if i < 0])
b = []
p = 0
m = 0
MOD = 10**9 + 7

while(True):
    if(len(plus) != 0 and len(minus) != 0):
        if(plus[p] >= -minus[m]):
            b.append(plus[p])
            p += 1
        else:
            b.append(minus[m])
            m += 1
    if(p == len(plus)):
        for i in range(k-p-m):
            b.append(minus[i+m])
        break
    if(m == len(minus)):
        for i in range(k-p-m):
            b.append(plus[i+p])
        break
    if(p+m == k):
        if(m % 2 == 1):
            if(minus[m]*minus[m-1] > plus[p]*plus[p-1]):
                b[b.index(plus[p-1])] = minus[m]
            else:
                b[b.index(minus[m-1])] = plus[p]
        break
if(len([i for i in b if i<0]) %2 != 0):
    if(0 in a):
        print(0)
        sys.exit()
    else:
        ans = 1
        for i in a:
            if(i < 0):
                i *= -1
        a = sorted(a,reverse=True)
        for i in range(k):
            ans = ans*a[i] % MOD
        ans = -((-1 * ans) % -MOD)
        print(ans)
        sys.exit()
ans = 1
for i in b:
    ans = ans*i % MOD
print(ans)

Submission status: Runtime Error

Solution code:
N, K, *A = map(int, open(0).read().split())
MOD = 10 ** 9 + 7

z_num = sum(v == 0 for v in A)
p_num = sum(v > 0 for v in A)
m_num = sum(v < 0 for v in A)

if p_num + m_num < K:
    print(0)
    exit()
    
if m_num % 2 == 1 and p_num + m_num == K and z_num > 0:
    print(0)
    exit()
    
if p_num == 0 and m_num >= K and K % 2 == 1:
    if z_num > 0:
        print(0)
    else:
        x = sorted([v for v in A if v < 0], reversed=True)
        ans = 1
        n = len(x)
        for i in range(n - K, n):
            ans = ans * x[i] % MOD
        print(ans)
    exit()


x = sorted([(abs(v), v // abs(v)) for v in A if v != 0])
plus = []
minus = []
for i in range(K):
    v, s = x.pop()
    if s == 1:
        plus.append(v)
    else:
        minus.append(v)


if len(minus) % 2 != 0:
    p_cand = MOD
    m_cand = MOD
    while x:
        v, s = x.pop()
        if s == 1 and p_cand == MOD:
            p_cand = v
        elif s == -1 and m_cand == MOD:
            m_cand = v

    if p_cand == MOD and m_cand != MOD and plus:
        plus.pop()
        minus.append(m_cand)
    elif m_cand == MOD and p_cand != MOD and minus:
        minus.pop()
        plus.append(p_cand)
    elif p_cand != MOD and m_cand != MOD and plus and minus:
        p_org = plus.pop()
        m_org = minus.pop()
        if p_org * p_cand > m_org * m_cand:
            plus.append(p_org)
            plus.append(p_cand)
        else:
            minus.append(m_org)
            minus.append(m_cand)


ans = 1
for v in plus:
    ans = ans * v % MOD
for v in minus:
    ans = ans * (-v) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = sorted(map(int, input().split()), reverse = True, key = lambda x: abs(x))

nn = len([ai for ai in a if ai < 0])
ans = 1
if nn == n:
    for i in range(k):
        ans *= a[::-1][i]
    print(ans % (10**9 + 7))
    exit()

cnt = 0
mspn = float("inf")
msnn = -float("inf")
for i in range(k):
        ans *= a[i]
        if a[i] < 0:
            cnt += 1
            msnn = max(msnn, a[i])
        else:
            mspn = min(mspn, a[i])

mbnn = 0
l = [ai for ai in a[i+1:] if ai < 0]
if len(l) > 0:
    mnnn = l[0]
    
if cnt%2 == 1:
    ans1 = ans // msnn * max(a[i+1:])
    ans2 = ans // mspn * mbnn
    print(max(ans1, ans2) % (10**9 + 7))
else:
    print(ans % (10**9 + 7))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

pl = 0
zr = 0
mn = 0

a.sort()

for i in range(n):
    if a[i] == 0:
        zr += 1
    elif a[i] > 0:
        pl += 1
    elif a[i] < 0:
        mn += 1

hugo = 0

tmp = k-pl
        
if zr == 0 and pl == 0 and k % 2 == 1:
    hugo = 3#mn
elif zr == 1 and pl == 0 and k % 2 == 1:
    hugo = 2#zr
else:
    hugo = 1#pl

ans = 1
tmp_ans = 1
    
if hugo == 3:
    for i in range(k):
        ans *= a[mn-1-i]
        ans %= mod
    print(ans%mod)
elif hugo == 2:
    print(0)
else:
    if mn == 0:
        for i in range(k):
            tmp_ans *= a[n-1-i]
            tmp_ans %= mod
        print(tmp_ans)
    else:
        tmp = k
        pl_num = 0
        mn_num = 0
        while tmp > 0:
            if tmp >= 2:
                tmp -= 2
                tmp_p_seki = a[pl_num+0]*a[pl_num+1]
                tmp_m_seki = a[mn_num+0]*a[mn_num+1]
                if tmp_p_seki > tmp_m_seki:
                    tmp_seki = tmp_p_seki
                    pl_num += 2
                else:
                    tmp_seki = tmp_m_seki
                    mn_num += 2
            elif tmp == 1:
                tmp_seki = pl[pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = 10**9+7
if K == 1:
    print(max(A)%m)
    exit()
p = []
q = []
r = []
for i in range(N):
    if A[i] > 0:
        p.append(A[i])
    elif A[i] < 0:
        q.append(A[i])
    else:
        r.append(A[i])
p.sort()
q.sort()
P = len(p)
Q = len(q)
if P+Q < K:
    print(0)
    exit()
else:
    if P == Q == 1:
        print(p[0]*q[0]%m)
        exit()
    if P == 0:
        if K%2 == 0:
            ans = 1
            for i in range(K):
                ans = ans * q[Q-1-i] % m
            print(ans)
        else:
            if len(r) > 0:
                print(0)
            else:
                ans = 1
                for i in range(K):
                    ans = ans * q[Q-1-i] % m
            print(ans)
    else:
        i = K# pから使う個数
        j = 0# qから使う個数
        while i > P:
            i -= 2
            j += 2
        
        while j < Q-1:
            if p[P-i]*p[P-i+1] < q[Q-j-1]*q[Q-j-2]:
                if i>1:
                    i -= 2
                j += 2
            else:
                break
        ans = 1
        for k in range(i):
            ans = ans * p[P-k-1] % m
        for l in range(j):
            ans = ans * q[Q-l-1] % m
        print(ans)

Submission status: Runtime Error

Solution code:

Copy
Copy
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
A = sorted(A, key = lambda x:abs(x), reverse=True)
#print(A)
 
ans = []
negidx = 0
posidx = 0
neg = False
for i in range(K):
  a = A[i]
  ans.append(a)
  if a<0:
    negidx = i
    neg = not neg
  else:
    posidx = i
#print(ans, neg, negidx)
answer = 1
if neg:
  poppos = list(ans)
  pg = poppos.pop(posidx)
  popneg = list(ans)
  ng = popneg.pop(negidx)
  pgratio = None
  ngratio = None
  found = 0
  for i in range(K+1, N):
    if A[i]>=0 and ngratio is None:
      found = 1
      popneg.append(A[i])
      ngratio = -A[i]/ng
    if A[i]<0 and pgratio is None:
      found = 2
      poppos.append(A[i])
      pgratio = -A[i]/pg
    if pgratio is not None and npratio is not None:
      found = 3
      break
  if found == 1:
    for a in popnep:
      answer *= abs(a)%1000000007
    print(answer%1000000007)
  elif found == 2:
    for a in poppos:
      answer *= abs(a)%1000000007
    print(answer%1000000007)
  elif found == 3:
    if pgratio > ngratio:
      for a in poppos:
        answer *= abs(a)%1000000007
      print(answer%1000000007)
    else:
      for a in popneg:
        answer *= abs(a)%1000000007
      print(answer%1000000007)
  else:
    for i in range(K):
      answer *= A[-(i+1)]%1000000007
    print(answer%1000000007)
else:
  for a in ans:
    answer *= abs(a)%1000000007
  print(answer%1000000007)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
MOD = 1000000007  # type: int


def solve(N: int, K: int, A: "List[int]"):
    mp = sum([int(a<=0) for a in A])
    pl = True
    if N == K:
        if mp%2 == 0:     pl = True
        else:     pl = False
    if mp == N:
        if K%2 == 0: pl = True
        else: pl = False

    absA = sorted(A, key=abs)
    sA = deque(absA)
    ans = 1
    k = 1
    if pl:
        for i in range(K):
            t = sA.pop()
            ans*= t
            k *= int(t>0)*2-1
            ans%= MOD

        if k<0:
            pre=absA[i]
            prei = i
            while((i!=N) and ((absA[i] * pre)>0) ): i+=1
            if i==N:
                pre = avsA[prei+1]
                i = prei
                while((absA[i]*pre)>0 ): i-=1
            
                ans//= absA[i]
                ans*= pre
            else:
                ans //= pre
                ans *= ansA[i]

        print(ans%MOD)

    else:
        for i in range(K):
            ans*= sA.popleft()
            ans%= MOD
        print(ans%MOD)


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

mod = 10**9 + 7
p = []
m = []
z_cnt = 0

for i in range(N):
    if A[i] < 0:
        m.append(-A[i])
    elif A[i] > 0:
        p.append(A[i])
    else:
        z_cnt += 1

p.sort(reverse=True)
m.sort(reverse=True)

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

if len(p) == 0:
    if K % 2 == 0:
        ans = 1
        for i in range(K):
            ans = (ans * m[i]) % mod
        print(ans)
        exit()
    else:
        ans = 1
        for i in range(K):
            ans = (ans * m[N-i-1]) % mod
        print(-ans%mod)
        exit()

tmp = K
while(tmp > len(p)):
    tmp -= 2

flg = True
while(tmp >= 0 and K - tmp <= len(m)):
    if flg:
        ans = 1
        tmp_list = p[:tmp] + m[:K-tmp]
        for i in tmp_list:
            ans = (ans * i) % mod
        flg = False

    elif p[tmp] * p[tmp+1] < m[K-tmp-2] * m[K-tmp-1]:
        tmp_list = p[:tmp] + m[:K-tmp]
        ans = 1
        for i in tmp_list:
            ans = (ans * i) % mod
    
    tmp -= 2

print(ans)

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n, k = inpl()
a = inpl()
data = [[abs(i), i < 0] for i in a]
for t in data:
    if t[1]:
        all_minus += 1
data.sort(reverse=True)
last_minus = 0
last_plus = 0
ans = 1
minus_amount = 0
for i in range(k):
    elem, sign = data[i][0], data[i][1]
    if elem == 0:
        print(0)
        exit()
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans%mod)
    exit()
all_minus = 0
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    ans=ans*((-1)%mod)
    print(ans % mod)
    exit()
tmp_plus = 0
tmp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_minus:
        tmp_minus = elem
    elif last_minus and not sign and not tmp_plus:
        tmp_plus = elem
if tmp_plus == 0 and tmp_minus == 0:
    ans = 0
elif last_plus == 0:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
elif last_minus == 0:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
elif tmp_plus * last_plus > tmp_minus * last_minus:
    ans = ans * pow(last_minus, mod - 2, mod) * tmp_plus % mod
else:
    ans = ans * pow(last_plus, mod - 2, mod) * tmp_minus % mod
print(ans)

Submission status: Runtime Error

Solution code:
def mult(lis):
  ret=1
  for i in lis:
    ret*=i
    ret%=1000000007
  return ret
n,k=map(int,input().split())
a=list(map(int,input().split()))
minus=[]
plus=[]
ch=[]
for i in a:
  if i<0:
    minus.append(i)
  else:
    plus.append(i)
if len(plus)==0 and k%2:
  minus.sort(reverse=True)
  ch.extend(minus[:k])
else:
  pls=True
  a.sort(key=lambda x: abs(x), reverse=True)
  while k>0:
    inp=a.pop(0)
    if inp<0:
      if k==1 and pls==False:
        continue
      pls^=1
    ch.append(inp)
    k-=1
print(mult(ch))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
a.sort()
mi = []
pl = []
zero = 0
for i in a:
    if i < 0:
        mi.append(i)
    elif i == 0:
        zero += 1
    else:
        pl.append(i)

if n-zero < k:
    print(0)
    exit()
if mi == []:
    ans = 1
    count = 0
    while count < k:
        ans *= a[-1-count]
        ans %= mod
        count += 1
    print(ans)
    
    exit()
if pl == []:
    if k%2:
        if zero:
            print(0)
        else:
            ans = 1
            count = 0
            while count < k:
                ans *= a[-1-count]
                ans %= mod
                count += 1
            print(ans)
            
    else:
        ans = 1
        count = 0
        while count < k:
            ans *= a[count]
            ans %= mod
            count += 1
        print(ans)
        
    exit()

ans = 0
ip = 0
im = 0
if k%2:
    count = pl[-1]
    k -= 1
    ip += 1
else:
    count = 1
while k > 0:
    check1 = True
    check2 = True
    if ip+2 <= len(pl):
        x = pl[-1-ip]*pl[-2-ip]
        
    else:
        x = 1
        check1 = False
    if im+2 <= len(pl):
        y = mi[im]*mi[im+1]
    else:
        y = 1
        check2 = False
    if x >= y:
        if check1:
            ip += 2
        count = (x*count)%mod
    else:
        if check2:
            im += 2
        count = (y*count)%mod
    if check1 == False and check2 == False:
        break
    k -= 2
if k:
    print(0)
else:
    print(count%mod)

Submission status: Runtime Error

Solution code:
import sys
n,k=map(int,input().split())
a = list(map(int,input().split()))
plus = sorted([i for i in a if i > 0],reverse=True)
minus = sorted([i for i in a if i < 0])
b = []
p = 0
m = 0
MOD = 10**9 + 7

while(True):
    if(plus[p] >= -minus[m]):
        b.append(plus[p])
        p += 1
    else:
        b.append(minus[m])
        m += 1
    if(p == len(plus)):
        for i in range(k-p-m):
            b.append(minus[i+m])
        break
    if(m == len(minus)):
        for i in range(k-p-m):
            b.append(plus[i+p])
        break
    if(p+m == k):
        if(m % 2 == 1):
            if(minus[m]*minus[m-1] > plus[p]*plus[p-1]):
                b[b.index(plus[p-1])] = minus[m]
            else:
                b[b.index(minus[m-1])] = plus[p]
        break
if(len([i for i in b if i<0]) %2 != 0):
    if(0 in a):
        print(0)
        sys.exit()
    else:
        ans = 1
        for i in a:
            if(i < 0):
                i *= -1
        a = sorted(a,reverse=True)
        for i in range(k):
            ans = ans*a[i] % MOD
        ans = -((-1 * ans) % -MOD)
        print(ans)
        sys.exit()
ans = 1
for i in b:
    ans = ans*i % MOD
print(ans)

Submission status: Runtime Error

Solution code:
def mult(lis):
  ret=1
  for i in lis:
    ret*=i
    ret%=1000000007
  return ret
n,k=map(int,input().split())
a=list(map(int,input().split()))
minus=[]
plus=[]
ch=[]
for i in a:
  if i<0:
    minus.append(i)
  else:
    plus.append(i)
if len(plus)==0 and k%2:
  minus.sort(reverse=True)
  ch.extend(minus[:k])
else:
  pls=True
  a.sort(key=lambda x: abs(x), reverse=True)
  while k>0:
    inp=a.pop(0)
    if inp<0:
      if k==1 and pls=False:
        continue
      pls^=1
    ch.append(inp)
    k-=1
print(mult(ch))

Submission status: Runtime Error

Solution code:
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
min_num = -1
good_num = -1
if len(pos) == 0 and n == k:
    ans = 1
    neg.sort(reverse = True)
    for i in range(k):
        ans *= neg[i]
        ans %= mod
    print(ans % mod)
else:
    #最大化するとき
    for i in range(0,k+1,2):
        #i個だけnegから取る。
        if i > len(neg) or k - i > len(pos):
            continue
        m = 0
        if i - 1 >= 0:
            m = abs(neg[i-1])
        if k-i-1 >= 0:
            m = min(m, pos[k-i-1])
        if m > min_num:
            min_num = m
            good_num = i
    ans = 1
    #print(good_num)
    for i in range(good_num):
        ans *= neg[i]
        ans %= mod
    for i in range(k - good_num):
        ans *= pos[i]
        ans %= mod
    print(ans % mod)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7

n, k = [int(_) for _ in input().split()]

a = [int(_) for _ in input().split()]

m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))

m.sort()
p.sort(reverse=True)


if len(p)+len(m) < k:
    print(0)
    exit()
if len(p)+len(m) == k:
    ans = 1
    for p_ in p:
        ans = (ans*p_) % MOD
    for q_ in m:
        ans = (ans*q_) % MOD
    print(ans)
    exit()

if len(p) == 0 and k % 2 == 1:
    ans = 1
    for i in range(k):
        ans = (ans*m[-i-1]) % MOD
    if 0 in a:
        ans *= 0
    print(ans)
    exit()

i, j = 0, 0
if k % 2 == 1:
    d = p.pop(-1)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
# print(p, m)
ans = 1
for c in range(k//2):
    # print(i, j)
    if m[i]*m[i+1] >= p[j]*p[j+1]:
        ans = (ans*m[i]*m[i+1]) % MOD
        i += 2
    else:
        ans = (ans*p[j]*p[j+1]) % MOD
        j += 2

if k % 2 == 1:
    ans = (ans*max(p[j], d)) % MOD


if ans > MOD:
    ans -= MOD
print(ans)
MOD = 10**9+7

n, k = [int(_) for _ in input().split()]

a = [int(_) for _ in input().split()]

m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))

m.sort()
p.sort(reverse=True)


if len(p)+len(m) < k:
    print(0)
    exit()
if len(p)+len(m) == k:
    ans = 1
    for p_ in p:
        ans = (ans*p_) % MOD
    for q_ in m:
        ans = (ans*q_) % MOD
    print(ans)
    exit()

if len(p) == 0 and k % 2 == 1:
    ans = 1
    for i in range(k):
        ans = (ans*m[-i-1]) % MOD
    if 0 in a:
        ans *= 0
    print(ans)
    exit()

i, j = 0, 0
if k % 2 == 1:
    d = p.pop(-1)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
# print(p, m)
ans = 1
MOD = 10**9+7

n, k = [int(_) for _ in input().split()]

a = [int(_) for _ in input().split()]

m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))

m.sort()
p.sort(reverse=True)


if len(p)+len(m) < k:
    print(0)
    exit()
if len(p)+len(m) == k:
    ans = 1
    for p_ in p:
        ans = (ans*p_) % MOD
    for q_ in m:
        ans = (ans*q_) % MOD
    print(ans)
    exit()

if len(p) == 0 and k % 2 == 1:
    ans = 1
    for i in range(k):
        ans = (ans*m[-i-1]) % MOD
    if 0 in a:
        ans *= 0
    print(ans)
    exit()

i, j = 0, 0
if k % 2 == 1:
    d = p.pop(-1)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
# print(p, m)
ans = 1
for c in range(k//2):
    # print(i, j)
    if m[i]*m[i+1] >= p[j]*p[j+1]:
        ans = (ans*m[i]*m[i+1]) % MOD
        i += 2
    else:
        ans = (ans*p[j]*p[j+1]) % MOD
        j += 2

if k % 2 == 1:
    ans = (ans*max(p[j], d)) % MOD


if ans > MOD:
    ans -= MOD
print(ans)
for c in range(k//2):
    # print(i, j)
    if m[i]*m[i+1] >= p[j]*p[j+1]:
        ans = (ans*m[i]*m[i+1]) % MOD
        i += 2
    else:
        ans = (ans*p[j]*p[j+1]) % MOD
        j += 2

if k % 2 == 1:
    ans = (ans*max(p[j], d)) % MOD


if ans > MOD:
    ans -= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import math
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
plist=[]
mlist=[]
ans=1
p=10**9+7
for i in range(N):
    if A[i]>=0:
        plist.append(A[i])
    else:
        mlist.append(A[i])
if len(plist)==0:
    if K%2==1:
        A.sort(reverse=True)
    else:
        A.sort()
    for i in range(K):
        ans=(ans*A[i])%p
    print(ans%p)
elif len(plist)==1:
    #print(plist,mlist)
    mlist.sort()
    if K%2==1:
        ans=plist[0]
    for i in range(K-1):
        ans=(ans*mlist[i])%p
    print(ans%p)
else:
    ans=1
    plist.sort(reverse=True)
    mlist.sort()
    pmap=deque()
    mmap=deque()
    if K%2==1:
        ans=plist[0]%p
        plist.pop(0)
        K=K-1
    #print(plist,mlist)
    for i in range(0,len(plist)-1,2):
        pmap.append(plist[i]*plist[i+1])
    pres=plist[len(plist)-1]
    mres=mlist[len(mlist)-1]
    for i in range(0,len(mlist)-1,2):
        mmap.append(mlist[i]*mlist[i+1])
    #print(K)
    mapnum=K//2
    #print(mapnum)
    #print(pmap,mmap,ans)
    for i in range(mapnum):
        if (len(pmap)>0)and(len(mmap)>0):
            pl=pmap.popleft()
            mi=mmap.popleft()
            if pl>mi:
                ans=(ans*pl)%p
                mmap.appendleft(mi)
            else:
                ans=(ans*mi)%p
                pmap.appendleft(pl)
        elif (len(pmap)==0)and(len(mmap)>0):
            mi=mmap.popleft()
            ans = (ans *mi) % p
        elif (len(mmap)==0)and(len(pmap)>0):
            pl=pmap.popleft()
            ans = (ans *pl) % p
        else:
            ans=(ans*pres*mres)%p
    print(ans)

Submission status: Runtime Error

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

x, y, z = 0, 0, 0
for i in range(n):
    if a[i]>0:
        y+=1
    elif a[i]<0:
        x+=1
    else:
        z+=1

if n==k and z>0:
    print(0)
        
elif n==k:
    ans = 1
    for i in range(n):
        ans*=a[i]
        ans%=mod
    print(ans)
elif n==x:
    ans = 1
    a.sort(reverse=True)
    for i in range(k):
        ans*=a[i]
        ans%= mod
    print(ans)
else:
    ans = 0
    a.sort() # 小さい順
    aa=[] #負の2数の積
    for i in range(x//2):
        aa.append(a[2*i]*a[2*i+1]) #大きい順
    if k%2==1:
        ans=a[-1]
        c = 1
        i  =0
        j =n-1
        b = True
        while c<k:
            
            if aa[i]>a[j-1]*a[j-2] and b:
                ans+=aa[i]
                ans%=mod
                c+=2
                i+=1
                if i>=len(aa):
                    b = False
                    i=0
            else:
                ans+=a[j-1]+a[j-2]
                j-=2
                c+=2
                ans%=mod

        print(ans)
    else:
        #ans=0
        c = 0
        i  =0
        j =n-1
        b = True
        while c<k:
            if aa[i]>a[j]*a[j-1] and b:
                ans+=aa[i]
                ans%=mod
                c+=2
                i+=1
                if i>=len(aa):
                    b = False
                    i =0
            else:
                ans+=a[j]+a[j-1]
                j-=2
                c+=2
                ans%=mod
        print(ans)

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 = []
    numpos = 0
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a > 0:
            heappush(q, [-a, "p"])
            numpos += 1
    numzero = N - numneg - numpos
    if numpos + numneg < K:
        print(0)
        return
    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
    elif K % 2 == 1 and numpos == 0:
        print(0)
        return
    ans = 1
    is_positive = True
    prevneg = 0
    prevpos = 0
    poshistory = []
    neghistory = []
    while K and len(q):
        num, posneg = heappop(q)
        if K == 1:
            if not is_positive:
                if posneg == "p" and len(poshistory) < 2:
                    poshistory.append(-num)
                elif posneg == "n":
                    if len(poshistory) == 2 and prevneg * -num < poshistory[0] * poshistory[1]:
                        ans = div(ans * poshistory[0] * poshistory[1], prevneg)
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
            if is_positive:
                if posneg == "n" and len(neghistory) < 2:
                    neghistory.append(-num)
                elif posneg == "p":
                    if len(neghistory) == 2 and prevpos * -num < neghistory[0] * neghistory[1]:
                        ans = div(ans * neghistory[0] * neghistory[1], prevpos)
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
            continue
        ans = (ans * -num) % MOD
        K -= 1
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if K != 0:
        if is_positive:
            ans = (ans * neghistory[0] * neghistory[1]) % MOD
        else:
            ans = (ans * poshistory[0] * poshistory[1]) % MOD
    print(ans)


if __name__ == "__main__":
    main()