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()))
mod = 10 ** 9 + 7
negs = [-x for x in A if x < 0]
non_negs = [x for x in A if x >= 0]


def inv(a):
    return pow(a, mod - 2, mod)


# 負の数を選ばざるを得ない数を考える
# 選べる負の数の個数の最小
n_min = k - (max(n - len(negs), 0))
# 　選べる負の数の個数の最大
n_max = min(n, k)

# この2数が一致していて、更に奇数のときにのみ負になる。(はず)
if n_max == n_min and n_max % 2 == 1:
    negs.sort()
    non_negs.sort()
    cnt = 0
    ans = 1
    n_idx, nn_idx = 0, 0
    while cnt < k:
        if n_idx == len(negs):
            ans *= non_negs[nn_idx]
            nn_idx += 1
        elif nn_idx == len(non_negs):
            ans *= negs[n_idx]
            n_idx += 1
        else:
            if non_negs[nn_idx] < negs[n_idx]:
                ans *= non_negs[nn_idx]
                nn_idx += 1
            else:
                ans *= negs[n_idx]
                n_idx += 1
        ans %= mod
        cnt += 1
    ans *= -1
    print(ans % mod)
    exit()

negs.sort(reverse=True)
non_negs.sort(reverse=True)

cnt = 0
ans = 1
neg_cnt = 0
n_idx, nn_idx = 0, 0
# idx番号と配列の長さを比較して、その配列から取得可能かをみる
while cnt < k:
    if n_idx == len(negs):
        ans *= non_negs[nn_idx]
        nn_idx += 1
    elif nn_idx == len(non_negs):
        ans *= negs[n_idx]
        n_idx == 1
        neg_cnt += 1
    else:
        if non_negs[nn_idx] > negs[n_idx]:
            ans *= non_negs[nn_idx]
            nn_idx += 1
        else:
            ans *= negs[n_idx]
            n_idx += 1
            neg_cnt += 1
    ans %= mod
    cnt += 1

if neg_cnt % 2 == 0:
    print(ans % mod)
else:
    # 次にかけるのはnegs[n_idx] or non_negs[nn_idx]
    # 一つ戻すならnegs[n_idx]-1 or non_negs[nn_idx-1]

    # negsが右にずらせるかどうか
    if n_idx == len(negs):
        ans *= inv(negs[n_idx - 1])
        ans *= non_negs[nn_idx]
        ans %= mod
    # non_negsが右にずらせるか
    elif nn_idx == len(non_negs):
        ans *= inv(non_negs[nn_idx - 1])
        ans *= negs[n_idx]
        ans %= mod
    else:
        # 両方ともずらせないのはすでに除外済み(のはず)
        if non_negs[nn_idx] * non_negs[nn_idx - 1] > negs[n_idx] * negs[n_idx - 1]:
            ans *= non_negs[nn_idx]
            ans *= inv(negs[n_idx])
            ans %= mod

    print(ans % mod)

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 = 1
                tmp_m_seki = 1
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    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 = a[n-1-pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)
        print(a[n*n])

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
arr = [int(x) for x in input().split()]
pos = []
neg = []
for ele in arr:
    if ele < 0:
        neg.append(ele)
    else: #zero bhi hoga isme
        pos.append(ele)

MOD = int(1e9) + 7
max_prod = 1

#agar result mei negative sign ayega hi toh phir sabse chhote element lene pdhenge
contains_neg = False
required_neg = k - len(pos)
if required_neg % 2 != 0:
    contains_neg = True

if contains_neg:
    abs_arr = [abs(x) for x in arr]
    abs_arr.sort()
    for i in range(k):
        ele = abs_arr[ele]
        max_prod = ((max_prod % MOD) * (ele % MOD)) % MOD
    max_prod *= -1
    print(max_prod % MOD)
else:
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    positive_pairs = []
    negative_pairs = []
    for i in range(0, len(pos), 2):
        if i + 1 >= len(pos):
            break
        positive_pairs.append(pos[i] * pos[i+1])
    for i in range(0, len(neg), 2):
        if i + 1 >= len(neg):
            break
        negative_pairs.append(neg[i] * neg[i+1])
    i, j = 0, 0
    for _ in range(k//2):
        if j == len(negative_pairs) and i < len(positive_pairs):
            best = positive_pairs[i] % MOD
            i += 1
        elif i == len(positive_pairs) and j < len(negative_pairs):
            best = negative_pairs[j] % MOD
            j += 1
        elif positive_pairs[i] > negative_pairs[j]:
            best = positive_pairs[i] % MOD
            i += 1
        else:
            best = negative_pairs[j] % MOD
            j += 1
        max_prod = ((max_prod % MOD) * (best % MOD)) % MOD
    if k % 2 != 0:
        max_prod = ((max_prod % MOD) * (pos[-1] % MOD)) % MOD
    print(max_prod % MOD)

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)
    print(a[n*n])
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 = 1
                tmp_m_seki = 1
                if pl_num+1 <= pl:
                    tmp_p_seki = a[n-1-pl_num]*a[n-1-pl_num-1]
                if mn_num+1 <= mn:
                    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 = a[n-1-pl_num]
                tmp -= 1
            tmp_ans *= tmp_seki
            tmp_ans %= mod
                    
            
        print(tmp_ans%mod)

Submission status: Runtime Error

Solution code:
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
if max(a)<0:
  if k%2:a.sort(reverse=1)
  else:a.sort()
  ans=1
  for i in a[:k]:ans=(ans*i)%mod
  exit(print(ans))
p=[(0,0)]
m=[(0,0)]
for i in a:
  if i<0:m.append((-i,1))
  else:p.append((i,0))
pp=mm=None
p.sort()
m.sort()
oe=0
ans=1
for i in range(k):
  if p[-1][0]>m[-1][0]:
    t,f=p.pop()
    pp=t
  else:
    t,f=m.pop()
    mm=t
  ans=(ans*t)%mod
  if ans==0:exit(print(0))
  oe^=f
if oe:
  if (pp*p[-1][0]>mm*m[-1][0] and mm!=None) or pp!=None:
    ans=(ans*pow(mm,mod-2,mod)*p[-1][0])%mod
  else:
    ans=(ans*pow(pp,mod-2,mod)*m[-1][0])%mod
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
negs = [-x for x in A if x < 0]
non_negs = [x for x in A if x >= 0]


def inv(a):
    return pow(a, mod - 2, mod)


# 負の数を選ばざるを得ない数を考える
# 選べる負の数の個数の最小
n_min = k - (n - len(negs))
# 　選べる負の数の個数の最大
n_max = min(n, k)

# この2数が一致していて、更に奇数のときにのみ負になる。(はず)
if n_max == n_min and n_max % 2 == 1:
    negs.sort()
    non_negs.sort()
    cnt = 0
    ans = 1
    n_idx, nn_idx = 0, 0
    while cnt < k:
        if n_idx == len(negs):
            ans *= non_negs[nn_idx]
            nn_idx += 1
        elif nn_idx == len(non_negs):
            ans *= negs[n_idx]
            n_idx == 1
        else:
            if non_negs[nn_idx] < negs[n_idx]:
                ans *= non_negs[nn_idx]
                nn_idx += 1
            else:
                ans *= negs[n_idx]
                n_idx += 1
        ans %= mod
        cnt += 1
    print(ans % mod)

negs.sort(reverse=True)
non_negs.sort(reverse=True)

cnt = 0
ans = 1
neg_cnt = 0
n_idx, nn_idx = 0, 0
# idx番号と配列の長さを比較して、その配列から取得可能かをみる
while cnt < k:
    if n_idx == len(negs):
        ans *= non_negs[nn_idx]
        nn_idx += 1
    elif nn_idx == len(non_negs):
        ans *= negs[n_idx]
        n_idx == 1
        neg_cnt += 1
    else:
        if non_negs[nn_idx] > negs[n_idx]:
            ans *= non_negs[nn_idx]
            nn_idx += 1
        else:
            ans *= negs[n_idx]
            n_idx += 1
            neg_cnt += 1
    ans %= mod
    cnt += 1

if neg_cnt % 2 == 0:
    print(ans % mod)
else:
    # 次にかけるのはnegs[n_idx] or non_negs[nn_idx]
    # 一つ戻すならnegs[n_idx]-1 or non_negs[nn_idx-1]

    # negsが右にずらせるかどうか
    if n_idx == len(negs):
        ans *= inv(negs[n_idx - 1])
        ans *= non_negs[nn_idx]
        ans %= mod
    # non_negsが右にずらせるか
    elif nn_idx == len(non_negs):
        ans *= inv(non_negs[nn_idx - 1])
        ans *= negs[n_idx]
        ans %= mod
    else:
        # 両方ともずらせないのはすでに除外済み(のはず)
        if non_negs[nn_idx] * non_negs[nn_idx - 1] > negs[n_idx] * negs[n_idx - 1]:
            ans *= non_negs[nn_idx]
            ans *= inv(negs[n_idx])
            ans %= mod

    print(ans % mod)

Submission status: Runtime Error

Solution code:
from functools import reduce
from operator import mul

N, K = map(int, input().split())
A = list(map(int, input().split()))
def multip(array):
    ret = 1
    for i in array:
        ret *= i
        ret = ret % (10**9 + 7)
    return ret

sign = [1 if i >= 0 else 0 for i in A]
abs_A = list(map(abs, A))
indice = range(N)
indice = sorted(indice, key=lambda i: -abs_A[i])
sign = [sign[i] for i in indice]
abs_A = [abs_A[i] for i in indice]
'''                                                                                                                                    
print(indice)                                                                                                                          
print(sign)                                                                                                                            
print(abs_A)                                                                                                                           
'''
# exception, no choice.                                                                                                                
if K == len(A):
    #print('no choice')                                                                                                                
    print(multip(A))
    exit()

# must negative pattern.                                                                                                               
if K - sum(sign) > 0 and (K - sum(sign)) % 2 == 1:
    #print('must negative')                                                                                                            
    print(-multip(abs_A[-K:]) % (10**9 + 7))
    exit()
    
if (K - sum(sign[:K])) % 2 == 1:
    #print('odd patten')                                                                                                               
    #print(sum(abs_A[:K]))                                                                                                             
    base = abs_A[:K]
    base_sign = sign[:K]
    for i in range(K-1, 0, -1):
        if base_sign[i] == 0:
            min_neg = i
            break
    else:
        min_neg = -1
    for i in range(K-1, 0, -1):
        if base_sign[i] == 1:
            min_pos = i
            break
    else:
        max_neg = -1

    for i in range(N-K):
        if sign[K:][i] == 0:
            max_neg = i
            break
    else:
        max_neg = -1
    for i in range(N-K):
        if sign[K:][i] == 1:
            max_pos = i
            break
    else:
        max_pos = -1
    if max_neg == -1 or min_neg == -1:
        target = abs_A[:K]
        target.pop(min_neg)
        target.append(max_pos)
        print(multip(target))
    elif max_pos == -1 or min_pos == -1:
        target = abs_A[:K]
        target.pop(min_pos)
        target.append(max_neg)
        print(multip(target))
    else:
        if base[min_neg] * abs_A[K:][max_neg] > base[min_pos] * abs_A[K:][max_pos]:
            target = abs_A[:K]
            target.pop(min_pos)
            target.append(max_neg)
            print(multip(target))
        else:
            target = abs_A[:K]
            target.pop(min_neg)
            target.append(max_pos)
            print(multip(target))
else:
    #print('even pattern')                                                                                                             
    #print(abs_A[:K])                                                                                                                  
    print(multip(abs_A[:K]))

Submission status: Runtime Error

Solution code:
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
if max(a)<0:
  if k%2:a.sort(reverse=1)
  else:a.sort()
  ans=1
  for i in a[:k]:ans=(ans*i)%mod
  exit(print(ans))
p=[(0,0)]
m=[(0,0)]
for i in a:
  if i<0:m.append((-i,1))
  else:p.append((i,0))
pp=mm=1
p.sort()
m.sort()
oe=0
ans=1
for i in range(k):
  if p[-1][0]>m[-1][0]:
    t,f=p.pop()
    pp=t
  else:
    t,f=m.pop()
    mm=t
  ans=(ans*t)%mod
  oe^=f
if ans==0:exit(print(0))
if oe:
  if pp*p[-1][0]>mm*m[-1][0]:
    ans=(ans*pow(mm,mod-2,mod)*p[-1][0])%mod
  else:
    ans=(ans*pow(pp,mod-2,mod)*m[-1][0])%mod
print(ans)

Submission status: Runtime Error

Solution code:
N=10**9+7
n , k = map(int, input().split())
x = list(map(int,input().split()))
posi=[]
nega=[]
ze=[]
p=0
ne=0
z=0



for i in range(n):
    if x[i]<0:
        nega.append(x[i]*(-1))
        ze.append([x[i]*(-1),-1])
        ne+=1
    elif x[i]>0:
        posi.append(x[i])
        ze.append([x[i],1])
        p+=1
    else:
        z+=1

if ne+p<k:
    print('0')
    exit()



elif k%2==1 and p==0:
    if z>=1:
        print('0')
        exit()
    else:
        ans=1
        nega.sort()
        for i in range(k):
            ans*=nega[i]
            ans%=N
        print(ans*(-1)%N)

else:
    ze.sort(key = lambda x:x[0],reverse=True)
    ans=1
    nn=0
    for i in range(k):
        ans*=ze[i][0]
        if ze[i][1]==-1:
            nn+=1
        ans%=N
    if nn%2==1:
        ans=1
        posi.sort(reverse=True)
        nega.sort(reverse=True)
        if nn+1>p and k-nn+1>p:
            print('0')
            exit()
        elif (k-nn+1<p and posi[k-nn]>=nega[nn-1]):
            for j in range(k-nn+1):
                ans*=posi[j]
                ans%=N
            for k in range(nn-1):
                ans*=nega[k]
                ans%=N
        else:
            for j in range(k-nn-1):
                ans*=posi[j]
                ans%=N
            for k in range(nn+1):
                ans*=nega[k]
                ans%=N
    print(ans)

Submission status: Runtime Error

Solution code:
N=10**9+7
n , k = map(int, input().split())
x = list(map(int,input().split()))
posi=[]
nega=[]
ze=[]
p=0
ne=0
z=0



for i in range(n):
    if x[i]<0:
        nega.append(x[i]*(-1))
        ze.append([x[i]*(-1),-1])
        ne+=1
    elif x[i]>0:
        posi.append(x[i])
        ze.append([x[i],1])
        p+=1
    else:
        z+=1

if ne+p<k:
    print('0')
    exit()



elif k%2==1 and p==0:
    if z>=1:
        print('0')
        exit()
    else:
        ans=1
        nega.sort()
        for i in range(k):
            ans*=nega[i]
            ans%=N
        print(ans*(-1)%N)

else:
    ze.sort(key = lambda x:x[0],reverse=True)
    ans=1
    nn=0
    for i in range(k):
        ans*=ze[i][0]
        if ze[i][1]==-1:
            nn+=1
        ans%=N
    if nn%2==1:
        ans=1
        posi.sort(reverse=True)
        nega.sort(reverse=True)
        if k-nn+1<p and posi[k-nn]>=nega[nn-1]:
            for j in range(k-nn+1):
                ans*=posi[j]
                ans%=N
            for k in range(nn-1):
                ans*=nega[k]
                ans%=N
        else:
            for j in range(k-nn-1):
                ans*=posi[j]
                ans%=N
            for k in range(nn+1):
                ans*=nega[k]
                ans%=N
    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 K % 2 == 1 and len(B) == 0:
    C = sorted(C)
    for i in range(K):
        ans *= C[i]
        ans %= MOD
    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 and N != K:
    if negs_p == len(C) and non_negs_p == len(B):
        pass
    elif negs_p == len(C):      
        b,c = C[negs_p-1],B[non_negs_p]
        ans = ans // b * c % MOD
    elif non_negs_p == len(B):
        a,d = C[negs_p],B[non_negs_p-1]
        ans = ans // 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 // d * a % MOD
        else:
            ans = ans // b * c % MOD
print(ans)

Submission status: Runtime Error

Solution code:
N=10**9+7
n , k = map(int, input().split())
x = list(map(int,input().split()))
posi=[]
nega=[]
ze=[]
p=0
ne=0
z=0

for i in range(n):
    if x[i]<0:
        nega.append(x[i]*(-1))
        ze.append([x[i]*(-1),-1])
        ne+=1
    elif x[i]>0:
        posi.append(x[i])
        ze.append([x[i],1])
        p+=1
    else:
        z+=1


if ne+p<k:
    print('0')
    exit()



elif k%2==1 and p==0:
    if z>=1:
        print('0')
        exit()
    else:
        ans=1
        nega.sort()
        for i in range(k):
            ans*=nega[i]
            ans%=N
        print(ans*(-1)%N)
else:
    ze.sort(key = lambda x:x[0],reverse=True)
    ans=1
    nn=0
    for i in range(k):
        ans*=ze[i][0]
        if ze[i][1]==-1:
            nn+=1
        ans%=N
    if nn%2==1:
        ans=1
        if k-nn+1<=p:
            for j in range(k-nn+1):
                ans*=posi[j]
                ans%=N
            for k in range(nn-1):
                ans*=nega[k]
                ans%=N
        else:
            for j in range(k-nn-1):
                ans*=posi[j]
                ans%=N
            for k in range(nn+1):
                ans*=nega[k]
                ans%=N
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N or len(A) == K:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
sign = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if sign < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            sign *= -1
            continue

        if len(P) == len(N) == 1:
            ans *= P.pop() * N.pop()
            K -= 2
            sign *= -1
            continue

        if len(N) == 1:
            n = N.pop()
            if sign < 0:
                ans *= n
                K -= 1
                sign *= -1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1 and sign > 0 or K % 2 == 0 and sign < 0:
                ans *= p
                K -= 1
            continue

if ans == 0:
    1 / 0
print(ans % MOD)

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 K % 2 == 1 and len(B) == 0:
    C = sorted(C)
    for i in range(K):
        ans *= C[i]
        ans %= MOD
    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) and non_negs_p == len(B):
        pass
    elif negs_p == len(C):      
        b,c = C[negs_p-1],B[non_negs_p]
        ans = ans // b * c % MOD
    elif non_negs_p == len(B):
        a,d = C[negs_p],B[non_negs_p-1]
        ans = ans // 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 // d * a % MOD
        else:
            ans = ans // b * c % MOD
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N:
    1 / 0
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
sign = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if sign < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            sign *= -1
            continue

        if len(P) == len(N) == 1:
            ans *= P.pop() * N.pop()
            K -= 2
            sign *= -1
            continue

        if len(N) == 1:
            n = N.pop()
            if sign < 0:
                ans *= n
                K -= 1
                sign *= -1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1 and sign > 0 or K % 2 == 0 and sign < 0:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

Submission status: Runtime Error

Solution code:
N=10**9+7
n , k = map(int, input().split())
x = list(map(int,input().split()))
posi=[]
nega=[]
ze=[]
p=0
ne=0
z=0

for i in range(n):
    if x[i]<0:
        nega.append(x[i]*(-1))
        ze.append([x[i]*(-1),-1])
        ne+=1
    elif x[i]>0:
        posi.append(x[i])
        ze.append([x[i],1])
        p+=1
    else:
        z+=1

if n+p<k:
    print('0')
    exit()

elif k%2==1 and p==0:
    if z>=1:
        print('0')
        exit()
    else:
        ans=1
        nega.sort()
        for i in range(k):
            ans*=nega[i]
            ans%=N
        print(ans*(-1)%N)
else:
    ze.sort(key = lambda x:x[0],reverse=True)
    ans=1
    nn=0
    for i in range(k):
        ans*=ze[i][0]
        if ze[i][1]==-1:
            nn+=1
        ans%=N
    if nn%2==1:
        ans=1
        if k-nn+1<=p:
            for j in range(k-nn+1):
                ans*=posi[j]
                ans%=N
            for k in range(nn-1):
                ans*=nega[k]
                ans%=N
        else:
            for j in range(k-nn-1):
                ans*=posi[j]
                ans%=N
            for k in range(nn+1):
                ans*=nega[k]
                ans%=N
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    1 / 0
    exit()

if not P or not N:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
sign = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if sign < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            sign *= -1
            continue

        if len(P) == len(N) == 1:
            ans *= P.pop() * N.pop()
            K -= 2
            sign *= -1
            continue

        if len(N) == 1:
            n = N.pop()
            if sign < 0:
                ans *= n
                K -= 1
                sign *= -1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1 and sign > 0 or K % 2 == 0 and sign < 0:
                ans *= p
                K -= 1
            continue

print(ans % MOD)

Submission status: Runtime Error

Solution code:
from collections import deque

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

P = [a for a in A if a >= 0]
N = [a for a in A if a < 0]

def canPositive():
    for i in range(0, len(N) + 1, 2):
        p = K - i
        if p < 0:
            break
        if len(P) >= p:
            return True
    return False

if not canPositive():
    A.sort(key=lambda a: abs(a))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

if not P or not N:
    A.sort(key=lambda a: abs(a), reverse=True)
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

P.sort(key=lambda a: abs(a))
N.sort(key=lambda a: abs(a))
P = deque(P)
N = deque(N)

ans = 1
sign = 1
while K > 0:
    ans %= MOD
    if ans == 0:
        break
    if K == 1:
        if sign < 0:
            ans *= N.pop()
        else:
            ans *= P.pop()
        break

    if len(P) >= 2 and len(N) >= 2:
        p = P[-1] * P[-2]
        n = N[-1] * N[-2]
        if p > n:
            ans *= P.pop() * P.pop()
        else:
            ans *= N.pop() * N.pop()
        K -= 2
        continue
    if len(P) <= 1 or len(N) <= 1:
        if len(N) == 0:
            ans *= P.pop()
            K -= 1
            sign *= -1
            continue

        if len(P) == 0:
            ans *= N.pop()
            K -= 1
            continue

        if len(P) == len(N) == 1:
            ans *= P.pop() * N.pop()
            K -= 2
            sign *= -1
            continue

        if len(N) == 1:
            n = N.pop()
            if sign < 0:
                ans *= n
                K -= 1
                sign *= -1
            continue

        if len(P) == 1:
            p = P.pop()
            if K % 2 == 1 and sign > 0 or K % 2 == 0 and sign < 0:
                ans *= p
                K -= 1
            continue

print(ans % MOD)