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:

def inverse(a): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

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

B = []
zero = 0
pl = 0
mi = 0
for i in A:
    if i == 0:
        zero += 1
    else:
        B.append( ( abs(i) , i // abs(i) ) )
        if i < 0:
            mi += 1
        else:
            pl += 1

last_pl = None

B.sort()
B.reverse()
mod = 10**9+7

if N - zero < K:
    print (0)
    sys.exit()

if pl == 0:

    if K % 2 == 0:
        now = 1
        for i in range(K):
            now *= B[i][0]
            now %= mod
        print (now % mod)
        sys.exit()
    else:
        now = 1
        if zero > 0:
            print (0)
            sys.exit()
        
        for i in range(K):
            now *= B[N-i-1][0] * B[N-i-1][1]
            now %= mod
        print (now % mod)
        sys.exit()


lasp = None
lasm = None

now = 1
for i in range(K):
    now *= B[i][0] * B[i][1]

    if now >= 0:
        now %= mod
    else:
        now = now % mod - mod

    if B[i][1] > 0:
        lasp = B[i][0]
    else:
        lasm = -1 * B[i][0]

#print (lasp,lasm)
if now > 0:
    print (now % mod)
    sys.exit()

else:

    if lasp == None:
        change2 = float("-inf")
        a2 = 0
    else:
        a2 = now * inverse(lasp)
        change2 = 1 / lasp
        for i in range(K+1,len(B)):
            if B[i][1] < 0:
                a2 *= -1 * B[i][0]
                change2 *= B[i][0]
                break
        else:
            change2 = float("-inf")

    if lasm == None:
        change3 = float("-inf")
        a3 = 0
    else:
    
        a3 = now * inverse(lasm % mod)
        change3 = 1 / abs(lasm)
        for i in range(K+1,len(B)):
            if B[i][1] > 0:
                a3 *= B[i][0]
                change3 *= B[i][0]
                break
        else:
            change3 = float("-inf")

    #print (a2,a3)
    if min(chage2,chage3) == float("-inf"):
        print (0)
            
    elif change2 > change3:
        print (a2 % mod)
    else:
        print (a3 % 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(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(plus[p] >= -minus[m]):
        b.append(plus[p])
        p += 1
    else:
        b.append(minus[m])
        m += 1
    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)
        print(a)
        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:
from bisect import bisect_left
import numpy as np
N,K = map(int,input().split())
a_list = list(map(int,input().split()))
np.abs(a_list).sort()

ans = 1

for i in range(K):
    ans *= a_list[i]
    if a_list[i]>=0:
        last_p = a_list[i]
    else:
        last_n = a_list[i]

if ans <0:
    next_p = None
    next_n = None
    for i in range(K,N):
        if a_list[i] >=0:
            if next_p is None:
                next_p = a_list[i]
        else:
            if next_n is None:
                next_n = a_list[i]
        if (next_n is not None and next_p is not None):
            break
    if next_n is None:
        ans = ans/last_n * next_p
    elif next_p is None:
        ans = ans/last_n * next_n
    else:
        ans = max(ans/last_n * next_p, ans/last_n * next_n)
    
print(int(ans%1_000_000_007))

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7


def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    Q = []
    ans = 1
    p = 0
    m = 0
    P = []
    M = []
    zero = 0
    for a in A:
        if a > 0:
            P.append(a)
        elif a < 0:
            M.append(a)
        else:
            zero += 1
    if k >= n - zero:
        print(0)
        return
    P.sort(reverse=True) + [-1*float("inf")]
    M.sort()
    count = 0
    pl = len(P)
    ml = len(M)
    while count < n:
        if ml - m - 1 >= 2:
            if P[p]*P[p+1] > M[m]*M[m+1]:
                count += 2
                p += 2
                ans = ((P[p]*P[p + 1] % mod)*ans) % mod
            else:
                count += 2
                m += 2
                ans = ((M[m]*M[m + 1] % mod)*ans) % mod
        elif p < pl - 1:
            count += 1
            ans = ans*P[p]%mod
            p += 1
        else:
            if (ml - 1 - m)%2 == 0:
                for j in range(m,ml):
                    ans = ans*-1*M[j]%mod
            else:
                if zero > 0:
                    print(0)
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
minusA = []
for i in A:
    if i < 0: minusA.append(-i)
minusA.sort(reverse=True)
ans = 1
minus = 0
seki = 1
for i in range(K):
    if A[i] < 0: seki *= -1
if K == 1: print(A[0])
else:
    for i in range(K):
        if  i * 2 <= len(minusA) and minusA:
            if seki > 0:
                if A[K - i * 2 - 1] * A[K - i * 2 - 2] < minusA[i * 2] * minusA[i * 2 + 1]: minus += 2
    for i in range(K - minus):
        ans = ans * A[i] % (10 ** 9 + 7)
    for i in range(minus):
        ans = ans * minusA[i] % (10 ** 9 + 7)
    if ans < 0: ans += 10 ** 9 + 7
    print(ans)

Submission status: Runtime Error

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

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

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

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


    if 0<=pidx<len(plus)-1:
        nexplus=plus[pidx]*plus[pidx+1]
    elif pidx==len(plus)-1:
        nexplus=plus[pidx]
    else:
        nexplus=-float("INF")

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

print(ans)

Submission status: Runtime Error

Solution code:
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
a_minus = [ai for ai in a if ai < 0]
a_minus.sort()#昇順にする
a_minus_len = len(a_minus)
a_plus = [ai for ai in a if ai > 0]
a_plus.sort()#降順にする
a_plus_len = len(a_plus)
a_zero = a.count(0)

MOD = 10**9+7
from itertools import accumulate
mul_mod = lambda x,y:x*y%MOD
a_minus_acc = list(accumulate(a_minus,mul_mod))
a_plus_acc = list(accumulate(a_plus,mul_mod))

inf=float("inf")
ret = -inf

if 0 in a:
    ret = 0
can_minus_even=False
for i in range(0,k+1,2):
    #負が偶数こ取れるか調べる
    if n-i <= a_plus_len and i <= a_minus_len:
        can_minus_even=True
        break
prev = None
if can_minus_even:
    #負が取る個数で場合分けする。
    for i in range(0,k+1,2):
        if i > a_minus_len:
            break
        if k-i <= a_plus_len and i <= a_minus_len:
            if not prev:
                if i==0:
                    ret = a_plus_acc[k-1]
                elif i==k:
                    ret = a_minus[k-1]
                else:
                    ret = a_plus_acc[k-i-1] * a_minus_acc[i-1] %MOD
                prev = i
            else:
                if a_minus[i-1] * a_minus[i-2] > a_plus[k-i-1] * a_plus[k-i]:
                    ret = a_plus_acc[k-i-1] * a_minus_acc[i-1] %MOD
else:
    ret = max(ret,a_minus_acc[k-1])

print(ret)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
A = list(map(int,input().split()))
B  =[0]*n
C = [0]*n
ff = 0
an = 1
t=0
u=0
for i in range(n):
  if(A[i]>=0):
    B[i]=A[i]
    C[i]= 0
    t +=1 
  else:
    B[i]=0
    C[i]=-A[i]
    u +=1
D = sorted(B,reverse=True)
E = sorted(C,reverse=True)
if(n>=2):
  if(t==0):
    for i in range(k-2):
      an = an*E[n-i]
  else:    
  for j in range(k-2):
    if(D[0]>=E[0]):
      an = an*D[0]
      D.pop(0)
      print(an)
    else:
      an = an*E[0]
      E.pop(0)
      ff +=1
  if(ff%2==1):
    an = an*D[0]*E[0]
  else:
    an = an*max(D[0]*D[1],E[0]*E[1])
else:
  an = D[0]
print(an)

Submission status: Runtime Error

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

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

    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        l = 0
        r = -1
        mlt1 = a[0] * a[1]
        mlt2 = a[-2] * a[-1]
        for _ in range(k//2):
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                l += 2
                if l <= n-1:
                    mlt1 = a[l+1] * a[l]
            else:
                ret *= mlt2 % mod
                r -= 2
                if r >= -n+1:
                    mlt2 = a[r-1] * a[r]
            ret %= mod

        if k % 2 == 1:
            ret *= a[r-1]
            ret %= mod

    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

upper_n = 0
downer_n = 0 

dp = [[0]*(K+1) for _ in range(2)]
dp[0][0] = A[upper_n]
dp[0][1] = A[downer_n]

for _ in range(N):
  if A[upper_n] > 0 and A[N-1-downer_n] < 0:
    if A[upper_n] > -A[downer_n]:
      if upper_n == 0:
        dp[0][0] = A[upper_n]
      else:
        
        dp[upper_n + downer_n][0] = dp[upper_n + downer_n - 1][0] * A[upper_n + 1]
        dp[upper_n + downer_n][1] = dp[upper_n + downer_n - 1][1] * A[upper_n + 1]
      upper_n += 1
    else:
      if downer_n == 0:
        dp[0][1] = A[downer_n]
      else:
        dp[upper_n + downer_n][1] = dp[upper_n + downer_n - 1][0] * A[downer_n + 1]
        dp[upper_n + downer_n][0] = dp[upper_n + downer_n - 1][1] * A[downer_n + 1]
      downer_n += 1
  elif A[upper_n] > 0:
    if upper_n == 0:
      dp[0][0] = A[upper_n]
    else:
      
      dp[upper_n + downer_n][0] = dp[upper_n + downer_n - 1][0] * A[upper_n + 1]
      dp[upper_n + downer_n][1] = dp[upper_n + downer_n - 1][1] * A[upper_n + 1]
    upper_n += 1
  else:
    else:
      if downer_n == 0:
        dp[0][1] = A[downer_n]
      else:
        dp[upper_n + downer_n][1] = dp[upper_n + downer_n - 1][0] * A[downer_n + 1]
        dp[upper_n + downer_n][0] = dp[upper_n + downer_n - 1][1] * A[downer_n + 1]
      downer_n += 1
print(dp[K][0])

Submission status: Runtime Error

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

plst=sorted([x for x in lst if x>=0],reverse=True)
nlst=sorted([abs(x) for x in lst if x<0],reverse=True)
lenn=len(nlst)
lenp=len(plst)



if lenp==0 and k%2==1:
    sm=1
    for i in range(lenn-1,lenn-k-1,-1):
        sm*=-nlst[i]
        sm%=res
    print(sm)
    exit()

if lenp==0 and k%2==0:
    sm=1
    for i in range(k):
        sm*=nlst[i]
        sm%=res
    print(sm)
    exit()

nlstw=[nlst[2*i]*nlst[2*i+1] for i in range(lenn//2)]
lennw=len(nlstw)

if lenn==0 :
    sm=1
    for i in range(k):
        sm*=nlst[i]
        sm%=res
    print(sm)
    exit()


ptoken=0
ntoken=0
nwtoken=0
token=0


sm=1
while token<k:

    if nwtoken==lennw or ptoken+1>=lenp : break

    if token==(k-1) or plst[ptoken]>nlst[ntoken]:
        sm*=plst[ptoken]
        sm%=res
        ptoken+=1
        token+=1
    else :
        if nlstw[nwtoken]>plst[ptoken]*plst[ptoken+1]:
            sm*=nlstw[nwtoken]
            sm%=res
            ntoken+=2
            nwtoken+=1
        else :
            sm*=plst[ptoken]*plst[ptoken+1]
            sm%=res
            ptoken+=2
        token+=2
else : print(sm);exit()

if ptoken+1>=lenp:
    if (k-token)%2==1:
        sm*=plst[ptoken]
        sm%=res
        token+=1
        while k>token:
            sm*=nlstw[nwtoken]
            sm%=res
            token+=2
            nwtoken+=1
    else :
        while k>token:
            if nwtoken==lennw:break
            sm*=nlstw[nwtoken]
            sm%=res
            token+=2
            nwtoken+=1
        if k!=token:
            sm*=plst[ptoken]
            sm%=res
    print(sm)
    exit()

if nwtoken+1==lennw:
    while k>token:
        sm*=plst[ptoken]
        sm%=res
        ptoken+=1
        token+=1
    print(sm)
    exit()

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
num=list(map(int,input().split()))
ans=0
limit=10**9+6
plus=[n for n in num if n>0 ]
mins=[n for n in num if n<0 ]
mins.sort(reverse=True)
if K==1:
    print(plus[0])
    exit()
if len(mins)==1:
    ans=plus[0]
    for i in range(1,K):
        ans*=plus[i]
    print(ans)
    exit()
ans=0
a=0
b=0
while(True):
    if K==1:
        ans*=plus[a]
        break
    elif K==0:
        break
    else:
        K-=2
        if b+1>=len(mins):
            ans*=plus[a]*plus[a+1]
            a+=2
        elif a+1>=len(plus):
            if b+1<len(mins):
                ans*=mins[b]*mins[b+1]
                b+=2
            else:break
        else:
            c=plus[a]*plus[a+1]
            d=mins[b]*mins[b+1]
            if c>d:
                ans*=c
                a+=2
            else:
                ans*=d
                b+=2

Submission status: Runtime Error

Solution code:
import numpy as np
import math
from functools import reduce
N, K = map(int, input().split())
num = np.array(list(map(int, input().split())), dtype=int)
DIVZ = 10**9 + 7

ans = -DIVZ
num.sort()
for ii in range(K//2+1):
    #s1 = reduce((lambda x, y: x * y), num[:ii*2])
    #s2 = reduce((lambda x, y: x * y), num[-ii * 2:])
    s1 = np.prod(num[:ii*2])
    s2 = np.prod(num[N - (K-ii*2):])
    if ans < float(s1)*float(s2):
        ans = float(s1)*float(s2)

print(int((ans % DIVZ))

Submission status: Runtime Error

Solution code:
import numpy as np

def kmaxprod_v2(data, k):
    if len(data) < k:
        return np.nan
    data = np.asanyarray(data)
    # for integer dtypes convert to python ints to have unlimited range for the
    # final product
    dfp = data.astype(object) if data.dtype in (
        int, np.int64, np.int32, np.int16, np.int8) else data
    # np.argpartition raises an exception if len(data) == k, therefore
    if len(data) == k:
        return np.prod(dfp) % 1000000007
    neg = data <= 0
    # if k is odd and there are no positive elements we must settle for the
    # least negative
    if k % 2 == 1 and np.count_nonzero(neg) == len(data):
        return np.prod(-np.partition(-data, k)[:k].astype(dfp.dtype))
    # now n > k and we have at least one positive element
    ap = np.argpartition(-np.absolute(data), k)
    low, high = ap[k:], ap[:k]
    # try multiplying the k with highest absolute value
    greedy = np.prod(dfp[high])
    if greedy >= 0:
        return greedy
    # there are two possible ways of fixing the sign:
    # either swap the worst negative inside for the best positive outside
    # or swap the worst positive inside for the best negative outside
    # compute both and compare
    # bpo in, wni out
    bpo = np.max(dfp[low])
    if bpo <= 0:
        spfn = 0
    else:
        neg_high = np.where(neg[high])[0]
        wni_ind = np.argmax(data[high[neg_high]])
        # translate to index in high
        wni_ind = neg_high[wni_ind]
        spfn = bpo*np.prod(dfp[high[:wni_ind]])*np.prod(dfp[high[wni_ind+1:]]) % 1000000007
        spfn %= 1000000007
    # bno in, wno out
    pos_high = np.where(~neg[high])[0]
    if len(pos_high) == 0:
        snfp = 0
    else:
        wpi_ind = np.argmin(data[high[pos_high]])
        wpi_ind = pos_high[wpi_ind]
        bno = np.min(dfp[low])
        snfp = bno* % 1000000007 np.prod(dfp[high[:wpi_ind]])* % 1000000007 np.prod(dfp[high[wpi_ind+1:]]) % 1000000007
        snfp %= 1000000007
    return max(spfn, snfp)
  
n,k = map(int,input().split())
li = list(map(int,input().split()))
a = kmaxprod_v2(li, k)
print(a % 1000000007)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
u = []
o = []
l = len(a)
for i in range(l):
    if a[i] >= 0:
        o.append(a[i])
    else:
        u.append(a[i])
u = list(map(abs, u))
u.sort(reverse=True)
o.sort(reverse=True)
ans = 1
lo = len(o)
lu = len(u)
oi = 0
ui = 0
if lo == 0 and k % 2 == 1:
    u.sort()
    for i in range(k):
        ans = ans*u[i]*-1
else:
    for j in range(n):
        if oi+ui == k:
            break
        elif oi < lo:
            if ui < lu:
                ot = o[oi]*[oi+1]
                if k-ui-oi > 1:
                    ut = u[ui]*u[ui+1]
                    if ut < ot:
                        ans = ans*ot
                        oi += 2
                    else:
                        ans = ans*ut
                        ui += 2
                else:
                    ans = ans*o[oi]
                    break
            else:
                ans = ans*o[oi]
                oi += 1
        elif ui < lu:
            ans = ans*u[ui]*-1
            ui += 1
ans = ans % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,k = map(int,input().split())
a_list = sorted(map(int,input().split()))
mod = 10**9+7
if n-k < a_list.count(0):
    print(0)
    exit()
if sum([1 for a in a_list if np.sign(a)==-1])==k:
    a_list.sort(key = abs)
    ans = 1
    for num in a_list[:k]:
        ans *= num
        ans %= mod
    print(ans)
    exit()
else:
    a_list.sort(key = abs,reverse = True)
    negative_min_big = max([num for num in a_list[:k] if np.sign(num)==-1])
    positive_min_big = min([num for num in a_list[:k] if np.sign(num)!=-1])
    negative_max_small = min([num for num in a_list[k:] if np.sign(num)==-1])
    positive_max_small = max([num for num in a_list[k:] if np.sign(num)!=-1])
    if positive_max_small/negative_min_big < negative_max_small/positive_min_big:
        remove = negative_min_big
        add = positive_max_small
    else:
        remove = positive_min_big
        add = negative_max_small
ans = 1
for num in a_list[:k]:
    ans *= num
    ans %= mod
    
if len([a for a in a_list[:k] if np.sign(a)==-1])%2!=0:
    ans *= add
    ans %= mod
    ans *= pow(remove, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
p=10**9+6
import heapq
A1=[-i for i in A if i>0]
A2=[i for i in A if i<0]
l1=len(A1)
l2=len(A2)
heapq.heapify(A1)
heapq.heapify(A2)
ans=0
count=0
while True:
    if l2>1:
        x2_1=heapq.heappop(A2)
        x2_2=heapq.heappop(A2)
        l2-=2
    if l1>0:
        while True:
            x1=heapq.heappop(A1)
            l1-=1
            if -x1>=x2_1*x2_2:
                ans+=-x1
                count+=1
            else:
                ans+=x2_1*x2_2
                count+=2
                break
    if count==K:
        break
print(ans)

Submission status: Runtime Error

Solution code:
from sys import exit
import heapq

n, k, *aa = map(int, open(0).read().split())

has_zero = 0 in aa

poses = [-a for a in aa if a>0]
negs = [a for a in aa if a<0]

MOD = 10**9+7

if k%2==0:
    even = True
    maximize = True
elif (k%2==1 and len(poses)>0):
    even = False
    maximize = True
elif has_zero:
    print(0)
    exit()
else:
    maximize = False

ans = 1

if maximize:
    heapq.heapify(poses)
    heapq.heapify(negs)
    if not even:
        ans *= -heapq.heappop(poses)
        ans %= MOD
        k -= 1
    while k:
        pnx = None
        nnx = None
        if len(poses):
            p1 = heapq.heappop(poses)
            p2 = heapq.heappop(poses)
            pnx = p1*p2
        if len(negs):
            n1 = heapq.heappop(negs)
            n2 = heapq.heappop(negs)
            nnx = n1*n2
        if pnx and not nnx:
            ans *= pnx
            k -= 2
        if nnx and not pnx:
            ans *= nnx
            k -= 2
        if pnx and nnx:
            if pnx >= nnx:
                ans *= pnx
                ans %= MOD
                heapq.heappush(negs, n1)
                heapq.heappush(negs, n2)
            else:
                ans *= n1
                ans %= MOD
                ans *= n2
                ans %= MOD
                heapq.heappush(poses, p1)
                heapq.heappush(poses, p2)
            k -= 2
else:
    while k:
        negs = [-a for a in negs]
        if len(negs):
            n1 = heapq.heappop(negs)
            ans *= n1
            ans %= MOD
            k -= 1

print(ans)

Submission status: Runtime Error

Solution code:
MOD=10**9+7
def solve1():
    global K
    i,j=0,0
    ans=1
    while(K>0):
        if K==1:
            break
        if i+1<S and j+1<M:
            a,b=p[i]*p[i+1],m[i]*m[i+1]
            if a>b:
                ans=ans*a%MOD
                i+=2
            else:
                ans=ans*b%MOD
                j+=2
        elif i+1>=S and j+1<M:
            ans=ans*m[j]*m[j+1]%MOD
            j+=2
    
        elif i+1<S and j+1>=M:
            ans=ans*p[i]*p[i+1]%MOD
            i+=2
        K-=2
    print(ans)
    return

def solve2():
    global K
    i,j=0,0
    ans=1
    while(K>0):
        if K==1:
            break
        if i+1<S and j+1<M:
            a,b=p[i]*p[i+1],m[i]*m[i+1]
            if a>b:
                if i+2<S:
                    ans=ans*a%MOD
                    i+=2
                else:
                    ans=ans*b%MOD
                    j+=2
            else:
                ans=ans*b%MOD
                j+=2
        elif i+1>=S and j+1<M:
            ans=ans*m[j]*m[j+1]%MOD
            j+=2
        elif i+1<S and j+1>=M:
            ans=ans*p[i]*p[i+1]%MOD
            i+=2
        K-=2
    if K==1:
        if i<S:
            ans=ans*p[i]%MOD
        elif z>0:
            ans*=0
        else:
            ans*=m[j]%MOD
    print(ans)
    return
        

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

m,p,z=[],[],0
for i in range(N):
    if A[i]<0:
        m.append(A[i])
    elif A[i]>0:
        p.append(-A[i])
    else:
        z+=1
if len(p)+len(m)<K:
    print(0)
    exit()
m.sort()
p.sort(reverse=True)
S,M=len(p),len(m)

if K%2==0:
    solve1()
else:
    solve2()

Submission status: Runtime Error

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a=sorted(a)
    a2=[]
    minus=0
    for i in range(n):
        if a[i]<0:
            a2.append([abs(a[i]),i,1])
            minus+=1
        else:
            a2.append([abs(a[i]), i,0])
    a2=sorted(a2,reverse=True)
    temp=1
    m2=0
    ans=1
    for i in range(k):
        m2+=a2[i][2]
    if m2%2==0 or n==k:
        for i in range(k):
            ans*=a2[i][0]
            ans=ans%MOD
    elif minus-m2<=0 and n>k:
        for i in reversed((range(k))):
            if a2[i][2]==1:
                a2[i][0]=a2[k][0]
        for i in range(k):
            ans*=a2[i][0]
            ans=ans%MOD
    else:
        temp1p = -1
        temp1m = -1
        paru1 = 0
        maru1 = 0
        for i in reversed((range(k))):
            if a2[i][2]==0:
                temp1p=max(i,temp1p)
                paru1=1
            else:
                temp1m=max(i,temp1m)
                maru1=1
        temp2p=INFI
        temp2m=INFI
        paru2=0
        maru2=0
        for i in range(k,n):
            if a2[i][2]==0:
                temp2p=min(i,temp2p)
                paru2=1
            else:
                temp2m=min(i,temp2m)
                maru2=1
        if paru1==0 or maru2==0:
            a2[temp1m][0]=a2[temp2p][0]
        elif maru1==0 or paru2==0:
            a2[temp1p][0]=a2[temp2m][0]
        else:
            tem2=a2[temp2p][0]*a2[temp1p][0]
            tem3=a2[temp1m][0]*a2[temp2m][0]
            if tem2>=tem3:
                a2[temp1m][0]=a2[temp2p][0]
            else:
                a2[temp1p][0]=a2[temp2m][0]
        for i in range(k):
            ans*=a2[i][0]
            ans=ans%MOD
    print(ans)





if __name__ == "__main__":

    main()

Submission status: Runtime Error

Solution code:
import numpy as np

MOD = 10**9 + 7
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
ans = 1
plus = a[a >= 0]
plus = np.sort(plus)[::-1]
plus = np.append(plus, [0, 0])
minus = a[a < 0]
minus = np.sort(minus)
minus = np.append(minus, [0, 0])
if n == k:
    for i in range(len(a)):
        ans *= a[i]
        ans %= MOD
    print(ans)
    exit()
if len(plus) == 2 and k % 2 == 1:
    for i in range(3, k + 3):
        ans *= minus[-i]
        ans %= MOD
else:
    if k % 2 == 1:
        p = k // 2
        ans *= plus[0]
        cplus = 1
        cminus = 0
    else:
        p = k // 2
        cplus = 0
        cminus = 0
    for l in range(p):
        if plus[cplus] * plus[cplus + 1] > minus[cminus] * minus[cminus + 1]:
            ans *= plus[cplus] * plus[cplus + 1]
            ans %= MOD
            cplus += 2
        else:
            ans *= minus[cminus] * minus[cminus + 1]
            ans %= MOD
            cminus += 2
print(int(ans))

Submission status: Runtime Error

Solution code:
import math
from numba import jit
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a=input()
al=[int(i) for i in a.split()]
al.sort()
plus=sum([1 for x in al if x>0])
minus=sum([1 for x in al if x<0])
zero=n-plus-minus
f=0
if n==minus and round(k/2)-k/2!=0:
    f=1
if zero==0 and round(minus/2)-minus/2!=0 and n==k:
    f=1
a=1
if f==0:
    @jit
    def aaa(al,k)
        for i in range(math.floor(k/2)):
            a1=al[0]*al[1]
            a2=al[-1]*al[-2]
            if a1>=a2:
                a*=a1
                del al[0]
                del al[0]
            else:
                a*=a2
                del al[-1]
                del al[-1]
            a=a%(10**9+7)
        if math.floor(k/2)-k/2!=0:
                a*=max(al)
        return(a%(10**9+7)))
    print(aaa(al,k))
else:
    def checkio(al):
        return sorted(al, key=abs)
    al=checkio(al)
    for i in range(k):
        a*=al[i]
        a=a%(10**9+7)
    print(a)