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:
a = list(map(int, input().split()))
N = int(a[0])
K = int(a[1])
A_i = list(map(int, input().split()))
A_pos = [i for i in A_i if i >= 0]
A_neg = [i for i in A_i if i < 0]

A_pos = sorted(A_pos)
A_neg = sorted(A_neg)
A_neg.reverse()

ret = 1
flag = 0
if K % 2 == 1:
    if len(A_pos) == 0:
        for i in range(K):
            ret = ret * A_neg[i]
            ret = ret % (10**9+7)
        if ret < 0:
            ret += 10**9+7
        print(ret)
        flag = 1
    else:
        ret *= A_pos[-1]
        A_pos = A_pos[:-1]

if flag == 0:
    for i in range(K//2):
        if len(A_pos) == 0 and len(A_neg) == 2:
            ret = ret * A_neg[0] * A_neg[1]
            break
        if len(A_pos) == 1 and len(A_neg) == 1:
            ret = ret * A_neg[0] * A_pos[0]
            break
        if len(A_pos) == 2 and len(A_pos) == 0:
            ret = ret * A_pos[0] * A_pos[1]
            break

        c1 = A_pos[-1] * A_pos[-2]
        if len(A_neg) >= 2:
            c2 = A_neg[-1] * A_neg[-2]
        else:
            c2 = 0
        if c1 > c2:
            ret = ret * A_pos[-1] * A_pos[-2]
            A_pos = A_pos[:-2]
        else:
            ret = ret * A_neg[-1] * A_neg[-2]
            A_neg = A_neg[:-2]
        ret = ret % (10**9+7)
        if ret < 0:
            ret += 10**9+7
    print(ret)

Submission status: Runtime Error

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

    plus = [A[i] for i in range(N) if A[i] >= 0]
    minus = [A[i] for i in range(N) if A[i] < 0]

    ans = 1

    id = 0
    id2 = 0
    P = len(plus)
    M = len(minus)
    plus.sort(reverse=True)

    mod = 10**9 + 7

    if P == 0:
        if K % 2 == 0:
            minus.sort()
            for i in range(K):
                ans *= minus[i]
                ans %= mod
        else:
            minus.sort(reverse=True)
            for i in range(K):
                ans *= minus[i]
                ans %= mod

    elif M == 0:
        for i in range(K):
            ans *= plus[i]
            ans %= mod

    else:

        p = P // 2
        m = M // 2
        if K > (p+m)*2 and (K % 2 == 1 and P % 2 == 0):  # 絶対値が小さい方から貪欲
            A.sort(key=lambda x: abs(x))
            for i in range(K):
                ans *= A[i]
                ans %= mod

        else:  # 絶対値が大きい方から貪欲
            minus.sort()
            pp = [plus[i]*plus[i+1] for i in range(M // 2)]
            mm = [minus[i] * minus[i+1] for i in range(P//2)]

            id = 0
            id2 = 0

            pp.sort(reverse=True)
            mm.sort(reverse=True)

            for i in range(K // 2):
                if id == p:
                    ans *= mm[id2]
                    id2 += 1
                elif id2 == m:
                    ans *= pp[id]
                    id += 1

                elif pp[id] >= mm[id2]:
                    ans *= pp[id]
                    id += 1
                else:
                    ans *= mm[id2]
                    id2 += 1

                ans %= mod

            if K % 2 == 1:
                ans *= plus[id * 2]

    print(ans % mod)


main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    Z = sum(1 if a == 0 else 0 for a in A)
    if Z + K > N:
        print(0)
        return
    P = []
    M = []
    for a in A:
        if a > 0:
            P.append(a)
        else:
            M.append(a)
    
    if len(P) == 0:
        M.sort(reverse = True)
        ans = 1
        for i in range(K):
            ans *= M[i]
            ans %= MOD
        print(ans)
        return
    
    if K%2 == 0:
        P.sort(reverse = True)
        number = []
        for i in range(0,len(P) - 1,2):
            number.append((P[i]*P[i + 1],0))

        M.sort()
        for i in range(0,len(M) - 1,2):
            number.append((M[i]*M[i + 1],1))
        
        number.sort(reverse = True)
        cnt = 0
        cnt_p = 0
        cnt_m = 0
        i = 0
        ans = 1
        while i < len(number):
            if cnt + 2 <= K:
                cnt += 2
                ans *= number[i][0]
                ans %= MOD
                if number[i][1] == 0:
                    cnt_p += 2
                else:
                    cnt_m += 2
            i += 1
        if cnt < K:
            ans *= P[cnt_p]
            ans *= M[cnt_m]
            ans %= MOD
        print(ans)
    
    else:
        ans = 1
        P.sort(reverse = True)
        number = []
        for i in range(0,len(M) - 1,2):
            number.append((P[i]*P[i + 1],0))
        M.sort()
        idx = 0
        if len(P)%2 == 0:
            while K > len(P):
                ans *= M[idx]
                if idx + 1 < len(M):
                    ans *= M[idx + 1]
                    ans %= MOD
                else:
                    K -= 1
                    break
                idx += 2
                K -= 2
        for i in range(idx,len(M) - 1,2):
            number.append((M[i]*M[i + 1],1))
        
        number.sort(reverse = True)
        cnt = 0
        i = 0
        cnt_p = 0
        while i < len(number):
            if cnt + 2 <= K:
                cnt += 2
                ans *= number[i][0]
                if number[i][1] == 0:
                    cnt_p += 2
                ans %= MOD
            i += 1
        ans *= P[cnt_p]
        ans %= MOD
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

P = []
M = []
for i in A:
  if i < 0:
    M.append(abs(i))
  if i > 0:
    P.append(i)

if len(M) + len(P) < K:
  print(0)
  exit()
elif len(M) + len(P) == K:
  ans = 1
  for i in M:
    ans = ans * i % MOD
  for i in P:
    ans = ans * i % MOD
  if len(M) % 2 == 1:
    ans *= -1
    ans += MOD
  print(ans)
  exit()

M.sort(reverse = True)
P.sort(reverse = True)

if len(P) == 0:
  ans = 1
  if K % 2 == 0:
    x = 1 / 0
    for i in range(K):
      ans = ans * M[i] % MOD
  else:
    for i in range(K):
      ans = ans * -M[-1 -i] % MOD
    while ans < 0:
      ans += MOD
  print(ans)
else:
  ans = 1
  pn = 0
  mn = 0
  if K % 2 == 1:
    K -= 1
    ans *= P[0]
    pn = 1
  for i in range(K // 2):
    if pn + 2 > len(P):
      ans = ans * M[mn] * M[mn + 1] % MOD
      mn += 2
    elif mn + 2 > len(M):
      ans = ans * P[pn] * P[pn + 1] % MOD
      pn += 2
    else:
      p = P[pn] * P[pn + 1]
      m = M[mn] * M[mn + 1]
      if p > m:
        ans = ans * p % MOD
        pn += 2
      else:
        ans = ans * m % MOD
        mn += 2
  print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
am = []
ap = []
for ai in a:
    if ai > 0:
        ap.append(ai)
    elif ai < 0:
        am.append(-ai)
am.sort(reverse=True)
ap.sort(reverse=True)

nm = len(am)
np = len(ap)
nz = n - np - nm
# print(am)
# print(ap)

if np + nm < k:
    ans = 0
elif np == 0:
    if k % 2 == 1:
        am.sort()
        ans = -1
        for i in range(k):
            ans *= am[i]
            ans %= MOD
    else:
        ans = 1
        for i in range(k):
            ans *= am[i]
            ans %= MOD
elif np < k:
    if (k - np) % 2 == 1:
        idx1 = np - 1
        idx2 = k - np + 1
    else:
        idx1 = np
        idx2 = k - np

    while idx1 >= 2 and idx2 + 1 < nm and ap[idx1 - 1] * ap[
            idx1 - 2] < am[idx2] * am[idx2 + 1]:
        idx1 -= 2
        idx2 += 2
    ans = 1
    for i in range(idx1):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx2):
        ans *= am[i]
        ans %= MOD
else:
    idx = 0
    while idx + 2 <= k and idx + 1 < nm and ap[k - idx - 1] * ap[
            k - idx - 2] < am[idx] * am[idx + 1]:
        idx += 2
    ans = 1
    for i in range(k - idx):
        ans *= ap[i]
        ans %= MOD
    for i in range(idx):
        ans *= am[i]
        ans %= MOD

print(ans)

Submission status: Runtime Error

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

arr = list(map(abs(int),input().split())
           
arr.sort(reverse=True)

print(reduce(a*b%1000000007,arr[:k],1))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 1
mod = 10**9 + 7
c = 0
z = 0
for i in a:
    if i < 0:
        c += 1
    elif i == 0:
        z += 1
if c == n and k & 1:
    a.reverse()
    for i in range(k):
        ans *= -a[i]
        ans %= mod
    print(-ans % mod)
elif c == n:
    for i in range(k):
        ans *= -a[i]
        ans %= mod
    print(ans)
else:
    plus = [i for i in a if i > 0]
    minus = [i for i in a if i <= 0]
    plus.sort(reverse=1)
    minus.sort()
    x = len(plus)
    y = len(minus)
    plus += [0] * z
    p, m = 0, 0
    for i in range(k // 2):
        if x <= p:
            ans *= minus[m] * minus[m + 1]
            m += 2
        elif y <= m:
            ans *= plus[p] * plus[p + 1]
            p += 2
        else:
            if minus[m] * minus[m + 1] >= plus[p] * plus[p + 1]:
                ans *= minus[m] * minus[m + 1]
                m += 2
            else:
                ans *= plus[p] * plus[p + 1]
                p += 2
        ans %= mod
    if k & 1:
        if p < x:
            ans *= plus[p]
        else:
            ans *= minus[-1]
        ans %= mod

    print(ans % mod)

Submission status: Runtime Error

Solution code:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
s=1
c=0
l=0
r=-1
while True:
    if k-c>=2:
        if a[r]*a[r-1]>=a[l]*a[l+1]:
            s*=a[r]*a[r-1]
            r-=2
            c+=2
        else:
            s*=a[l]*a[l+1]
            l+=2
            c+=2
    else:
        if a[r]<0:
            s=1
            a=np.abs(a)
            a=list(a)
            a.sort()
            print(a)
            while True:
                s*=a[c1]
                c1+=1
                s%=10**9+7
                print(s)
                if c1==k:
                    s=-s
                    print(s%10**9+7)
                    exit()
        else:s*=a[r]
        c+=1
    s%=10**9+7
    if k==c:break
print(s)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

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

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

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

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

next_minus = 0
next_plus = 0

for i in range(k, n):
    if blst[i][1] == -1:
        next_minus = blst[i][0]
    else:
        next_plus = blst[i][0]

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

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

Submission status: Runtime Error

Solution code:
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.append(i)
        if i<0:y.append(i)
    x.sort(reverse=1)
    y.sort()
    if len(x)+len(y)<k or len(x)<k and (k-len(x))%2 and len(x)+len(y)<n:
        print(0)
        exit()
    if len(x)<k and (k-len(x))%2:
        1/0
        c=1
        for i in x+y[::-1][:k-len(x)]:
            c=c*i%M
        print(c)
        exit()
    x=x[:k]
    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:
#

import sys
input=sys.stdin.readline
MOD=10**9+7


def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    if N==1:
        print(A[0])
        exit()
    A.sort()
    A2n=[]
    for i in range(0,N,2):
        if i+1>=N:
            break
        if A[i]<=0 and A[i+1]<=0:
            A2n.append(A[i]*A[i+1])
        else:
            break

    A.sort(reverse=True)
    ans=1
    if A[0]<=0 and K%2==1:
        for i in range(K):
            ans=(ans*A[i])%MOD
        print(ans)
        exit()
    ni=0
    i=0
    while(K>0):
        if len(A2n)-ni>0 and A[i]*A[i+1]<A2n[ni] and K>=2:
            ans=(ans*A2n[ni])%MOD
            K-=2
            ni+=1
        else:
            ans=(ans*A[i])%MOD
            i+=1
            K-=1
    print(ans)
            
    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
aplus = []
aminus = []
for x in a:
  if x >= 0:
    aplus.append(x)
  else:
    aminus.append(x)
aplus = sorted(aplus, reverse=True)
aminus = sorted(aminus)
if k % 2 == 1 and len(aplus) == 0:
  ans = 1
  for i in range(k):
    ans *= aminus[-(i + 1)]
    ans %= mod
  print(ans)
  exit()
ans = 1
l = min(k, len(aminus))
lminus = l // 2 * 2
for i in range(lminus):
  ans *= aminus[i]
  ans %= mod
for i in range(k - lminus):
  ans *= aplus[i]
  ans %= mod
if ans == 0:
  print(ans)
  exit()
for i in range(lminus - 2, -1, -2):
  if k - i - 1 >= len(aplus):
    break
  m_old = aminus[i] * aminus[i + 1]
  m_new = aplus[k - i - 1] * aplus[k - i - 2]
  if m_old >= m_new:
    break
  ans *= pow(m_old, mod - 2)
  ans *= m_new
  ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
N = int(a[0])
K = int(a[1])
A_i = list(map(int, input().split()))
A_pos = [i for i in A_i if i >= 0]
A_neg = [i for i in A_i if i < 0]

A_pos = sorted(A_pos)
A_neg = sorted(A_neg)
A_neg.reverse()

print(A_pos)
print(A_neg)

ret = 1
flag = 0
if K % 2 == 1:
    if len(A_pos) == 0:
        for i in range(K):
            ret = ret * A_neg[i]
            ret = ret % (10**9+7)
        print(ret)
        if ret < 0:
            ret += 10**9+7
        print(ret)
        flag = 1
    else:
        ret *= A_pos[-1]
        A_pos = A_pos[:-1]
if flag == 0:
    for i in range(K//2):
        if len(A_pos) == 0 and len(A_neg) == 2:
            ret = ret * A_neg[0] * A_neg[1]
            continue
        if len(A_pos) == 1 and len(A_neg) == 1:
            ret = ret * A_neg[0] * A_pos[0]
            continue
        if len(A_pos) == 2 and len(A_pos) == 0:
            ret = ret * A_pos[0] * A_pos[1]
            continue

        c1 = A_pos[-1] * A_pos[-2]
        if len(A_neg) >= 2:
            c2 = A_neg[-1] * A_neg[-2]
        else:
            c2 = 0
        if c1 > c2:
            ret = ret * A_pos[-1] * A_pos[-2]
            A_pos = A_pos[:-2]
        else:
            ret = ret * A_neg[-1] * A_neg[-2]
            A_neg = A_neg[:-2]
        ret = ret % (10**9+7)
        if ret < 0:
            ret += 10**9+7
    print(ret)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

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

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

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

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

next_minus = 0
next_plus = 0

for i in range(k, n):
    if blst[i][1] == -1:
        next_minus = blst[i][0]
    else:
        next_plus = blst[i][0]

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

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

Submission status: Runtime Error

Solution code:
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.append(i)
        if i<0:y.append(i)
    x.sort(reverse=1)
    y.sort()
    if len(x)+len(y)<k or len(x)<k and (k-len(x))%2 and len(x)+len(y)<n:
        1/0
        print(0)
        exit()
    if len(x)<k and (k-len(x))%2:
        c=1
        for i in x+y[::-1][:k-len(x)]:
            c=c*i%M
        print(c)
        exit()
    x=x[:k]
    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:
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]
all_minus = 0
for t in data:
    if t[1]:
        all_minus += 1
if all_minus == n:
    ans = 1
    data.sort()
    for i in range(k):
        ans = ans * data[i][0] % mod
    print(-ans % mod)
    exit()
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]
    ans = ans * elem % mod
    minus_amount += sign
    if sign:
        last_minus = elem
    else:
        last_plus = elem
if minus_amount % 2 == 0:
    print(ans)
    exit()
tmp_plus = 0
tmp_minus = 0
temp_plus = 0
temp_minus = 0
for i in range(k, n):
    elem, sign = data[i][0], data[i][1]
    if last_plus and sign and not tmp_plus:
        tmp_plus = elem / last_minus
        temp_plus = elem
    elif last_minus and not sign and not tmp_minus:
        tmp_minus = elem / last_plus
        temp_minus = elem
if tmp_plus > tmp_minus:
    ans * pow(last_minus, mod - 1, mod) * temp_plus % mod
else:
    ans * pow(last_plus, mod - 1, mod) * temp_minus % mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

A = LIST()
if N == 1:
    print(A[0])
    exit()

plus0 = []
minus = []
zero = []

for a in A:
    if a >= 0:
        plus0.append(a)
    if a == 0:
        zero.append(a)
    if a < 0:
        minus.append(a)

# print(plus0)
# print(minus)
# print(zero)

if len(minus) == 0 or (len(minus) == N and K%2 == 0) or (plus0 and minus and N != K) or (plus0 and minus and N == K and K%2 == 0):
    # 最大化を目指す
    ans = 1
    cnt = 0
    plus0.sort()
    minus.sort(reverse=True)
    # print(plus0)
    # print(minus)
    while cnt != K:
        if cnt == K-1 or len(minus) <= 1:
            ans *= plus0.pop()
            cnt += 1
        else:
            if not plus0:
                ans *= minus.pop()
                ans *= minus.pop()
                cnt += 2
            elif not minus:
                ans *= plus0.pop()
                cnt += 1
            else:
                if plus0[-1] > minus[-1]*minus[-2]:
                    ans *= plus0.pop()
                    cnt += 1
                else:
                    ans *= minus.pop()
                    ans *= minus.pop()
                    cnt += 2
        ans %= mod
    print(ans)
else:
    # 最小化を目指す
    if zero:
        print(0)
        exit()
    ans = 1
    cnt = 0
    plus0.sort(reverse=True)
    minus.sort()
    while cnt != K:
        if not plus0:
            ans *= minus.pop()
        elif not minus:
            ans *= plus0.pop()
        else:
            if plus0[-1] < -minus[-1]:
                ans *= plus0.pop()
            else:
                ans *= minus.pop()
        cnt += 1
        ans %= mod
    print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n,k=map(int,input().split())
    a = [int(x) for x in input().split() if x!='0']
    fl=n!=len(a)
    # print(fl)
    mod=10**9+7
    a.sort(key=lambda v:-abs(v))
    def ft(a):
        ans=1
        for x in a:
            ans=(ans*x)%mod
        return ans
    
    # print(a)
    def solve(a,k):
        ans=1
        nv=1
        for x in a:
            if k==0:
                break
            if x>0:
                ans=(ans*x)%mod
                k-=1
            if x<0:
                if nv!=1 and k>1:
                    k-=2
                    ans=(ans*x*nv)%mod
                    nv=1
                elif nv==1:
                    nv=x
        assert(k==0)
        return ans
    
    pv,nv=0,0
    for x in a:
        if x>0:
            pv+=1
        if x<0:
            nv+=1
    
    n=len(a)
    if k>n:
        print(0)
        exit(0)
    
    if k==n:
        if nv%2 and fl:
            print(0)
        else:
            print(ft(a))
        exit(0)
    
    if nv==0:
        print(ft(a[:k]))
        exit(0)
    
    if pv==0 and k%2==0:
        print(ft(a[:k]))
        exit(0)
    
    if pv==0 and k%2:
        if fl:
            print(0)
        else:
            a=a[::-1]
            print(ft(a[:k]))
        exit(0)
    
    print(solve(a,k))
# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

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=[]
Z=[]
N=[]
for i in range(n):
  if a[i]>0:
    P.append(a[i])
  elif a[i]==0:
    Z.append(a[i])
  else:
    N.append(-a[i])
P.sort()
P3=[1]
for i in range(len(P)):
  P3.append(P3[-1]*P[i]%mod)
P.reverse()
P2=[1]
for i in range(len(P)):
  P2.append(P2[-1]*P[i]%mod)
N.sort()
N3=[1]
for i in range(len(N)):
  N3.append(N3[-1]*N[i]%mod)
N.reverse()
N2=[1]
for i in range(len(N)):
  N2.append(N2[-1]*N[i]%mod)

if len(P)+len(N)<k:
  print(0)
  exit()

if len(N)==0:
  print(P2[k])
  exit()

ans=[]

for i in range(len(N)//2+1):
  if i*2<=k and k-i*2<=len(P):
    ans.append(N2[i*2]*P2[k-i*2])

if len(ans)!=0:
  print(max(ans)%mod)
  exit()

for i in range(k+1):
  if k-i<=len(P):
    ans.append(N3[i]*P3[k-i])

print(-min(ans)%mod)

Submission status: Runtime Error

Solution code:
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    cand=[]
    if K%2==1:#奇数個
        K-=1
        cand.append(L[-1])
        L=L[:-1]
    #N-1こ(偶数を選んでから)追加で、正の(一番大きいやつを取っておく?)怪しい
    poss=[]
    negs=[]
    replace=[]
    for l in L:
        if l<0:
            heapq.heappush(poss,l)
            if len(poss)>K:
                heapq.heappop(poss)#正の数でK番目より小さいやつは捨てる
        else:
            heapq.heappush(negs,l)
    while len(negs)>=2:
        a = heapq.heappop(negs)
        b = heapq.heappop(negs)
        replace.append(a*b)

    assert 1==2
    #posとnegから選んでいく

print(ans)

Submission status: Runtime Error

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

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

arr.sort(reverse=True,key=abs)

print(reduce(lambda x,y : x*y%1000000007,arr[:k],1))

Submission status: Runtime Error

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
pm = 1
ans = 1
odd = False
if k%2 == 1:
    odd = True
for i in range(n):
    if a[i] == 0: a.pop(i)

if len(a) < k:
    print(0)
    sys.exit()
ispop = False if len(a) == n else True
n = len(a)
a.sort()
if odd and a[n - 1] < 0:
    if ispop:
        print(0)
        sys.exit()
    for i in range(k):
        ans = (ans * a[n - 1 - i])%mod
    print(ans%mod)
    sys.exit()
for i in range(k//2):
    p = a[n-1] * a[n-2]
    m = a[0] * a[1]
    if p >= m:
        ans = (ans * p)%mod
        a.pop(n - 1)
        a.pop(n - 2)
    else:
        ans = (ans * m)%mod
        a.pop(1)
        a.pop(0)
    n -= 2
if k%2 == 1:
    if a[n - 1] > 0:
        ans = (ans * a[n - 1])%mod
    else:
        if ispop:
            ans = 0
        else:
            ans = (ans * a[n - 1])%mod
print(ans%mod)