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:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
import math
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math as M
MOD=10**9+7
#####################################
from collections import deque as D
#first we need to know whether our answer will be negative or positive if
#negative then among the neg values take the ones which have the least abs value
n,k=INPUT()
A=INPUT()
p1=[]
n1=[]
pos=D()
neg=D()
for i in A:
    if i>0:
        p1.append(i)
    elif i<0:
        n1.append(i)
p1.sort()
n1.sort(reverse=True)
for i in range(len(p1)):
    pos.append(p1[i])
for i in range(len(n1)):
    neg.append(n1[i])
P=len(pos)
N=len(neg)
if k>len(pos)+len(neg):
    print(0)

elif P==0 and k%2==1:
    #we know for sure ans will be negative here
    if P+N!=n:
        print(0)
    else:
        ans=1
        while(k>0 and P>0 and N>0):
            if abs(neg[0])<abs(neg[0]):
                ans*=neg[0]
                ans%=MOD
                neg.popleft()
                k-=1
                N-=1
            else:
                ans*=pos[0]
                ans%=MOD
                pos.popleft()
                k-=1
                P-=1
        if k==0:
            print(ans)
        else:
            if P==0:
                while(k>0):
                    ans*=neg.popleft()
                    ans%=MOD
                    k-=1
                    N-=1
                print(ans)
            else:
                while(k>0):
                    ans*=pos.posleft()
                    ans%=MOD
                    k-=1
                    P-=1
                print(ans)


else:
    bool=False
    ans=1
    while(k>0):
        #when both are len>=2
        while(k>1 and P>=2 and N>=2):
            if pos[-1]*pos[-2]>neg[-1]*neg[-2]:
                ans=ans*pos[-1]*pos[-2]
                ans%=MOD
                pos.pop()
                pos.pop()
                k-=2
                P-=2
            else:
                ans*=neg[-1]*neg[-2]
                ans%=MOD
                neg.pop()
                neg.pop()
                k-=2
                N-=2
            #print(ans)
        if k==0:
            print(ans%MOD)
            bool=True
            break
        elif k==1:
            #answer will be positive
            if P>0:
                ans=ans*pos[-1]
                ans%=MOD
                print(ans)
                bool=True
                break
            else:
                ans*=neg[-1]
                ans%=MOD
                print(ans)
                bool=True
                break
        else:
            #till now ans is positive and k>1 in both of them
            #the combiantion possible is p->1 to inf  n->1/0 ,n->1 to inf and p->1/0
            #k>1  and one of P or N is 0 now
            if P==0:
                if k%2==0:
                    while(k>0):
                        ans*=neg[-1]
                        ans%=MOD
                        neg.pop()
                        N-=1
                        k-=1
                    print(ans)
                    bool=True
                    break
                else:
                    while(k>0):
                        ans*=neg[0]
                        ans%=MOD
                        neg.popleft()
                        N-=1
                        k-=1
                    print(ans%MOD)
                    bool=True
                    break
            elif P==1:
                if k%2==0:
                    while(k>0):
                        ans*=neg[-1]
                        ans%=MOD
                        k-=1
                        neg.pop()
                        N-=1
                    print(ans)
                    bool=True
                    break
                else:
                    ans*=pos[-1]
                    P-=1
                    k-=1
                    while(k>0):
                        ans*=neg[-1]
                        ans%=MOD
                        neg.pop()
                        k-=1
                        N-=1
                    print(ans)
                    bool=True
                    break

            elif N==0:
                while(k>0):
                    ans*=pos[-1]
                    ans%=MOD
                    pos.pop()
                    k-=1
                    P-=1
                print(ans)
                bool=True
                break
            elif N==1:
                while(k>0):
                    ans*=pos[-1]
                    ans%=MOD
                    pos.pop()
                    k-=1
                    P-=1
                print(ans)
                bool=True
                break
            else:
                ans*=pos[-1]
                ans%=MOD
                pos.pop()
                P-=1
                k-=1

    if bool is False:
        print(ans%MOD)

Submission status: Runtime Error

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
import math
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math as M
MOD=10**9+7
#####################################
from collections import deque as D
#first we need to know whether our answer will be negative or positive if
#negative then among the neg values take the ones which have the least abs value
n,k=INPUT()
A=INPUT()
p1=[]
n1=[]
pos=D()
neg=D()
for i in A:
    if i>0:
        p1.append(i)
    elif i<0:
        n1.append(i)
p1.sort()
n1.sort(reverse=True)
for i in range(len(p1)):
    pos.append(p1[i])
for i in range(len(n1)):
    neg.append(n1[i])
P=len(pos)
N=len(neg)
if k>len(pos)+len(neg):
    print(0)

elif P==0 and k%2==1:
    #we know for sure ans will be negative here
    if P+N!=n:
        print(0)
    else:
        ans=1
        while(k>0 and P>0 and N>0):
            if abs(neg[0])<abs(neg[0]):
                ans*=neg[0]
                ans%=MOD
                neg.popleft()
                k-=1
                N-=1
            else:
                ans*=pos[0]
                ans%=MOD
                pos.popleft()
                k-=1
                P-=1
        if k==0:
            print(ans)
        else:
            if P==0:
                while(k>0):
                    ans*=neg.popleft()
                    ans%=MOD
                    k-=1
                    N-=1
                print(ans)
            else:
                while(k>0):
                    ans*=pos.posleft()
                    ans%=MOD
                    k-=1
                    P-=1
                print(ans)


else:
    bool=False
    ans=1
    while(k>0):
        #when both are len>=2
        while(k>1 and P>=2 and N>=2):
            if pos[-1]*pos[-2]>neg[-1]*neg[-2]:
                ans=ans*pos[-1]*pos[-2]
                ans%=MOD
                pos.pop()
                pos.pop()
                k-=2
                P-=2
            else:
                ans*=neg[-1]*neg[-2]
                ans%=MOD
                neg.pop()
                neg.pop()
                k-=2
                N-=2
            #print(ans)
        if k==0:
            print(ans%MOD)
            bool=True
            break
        elif k==1:
            #answer will be positive
            if P>0:
                ans=ans*pos[-1]
                ans%=MOD
                print(ans)
                bool=True
                break
            else:
                ans*=neg[-1]
                ans%=MOD
                print(ans)
                bool=True
                break
        else:
            #till now ans is positive and k>1 in both of them
            #the combiantion possible is p->1 to inf  n->1/0 ,n->1 to inf and p->1/0
            #k>1  and one of P or N is 0 now
            if P==0:
                if k%2==0:
                    while(k>0):
                        ans*=neg[-1]
                        ans%=MOD
                        neg.pop()
                        N-=1
                        k-=1
                    print(ans)
                    bool=True
                    break
                else:
                    while(k>0):
                        ans*=neg[0]
                        ans%=MOD
                        neg.popleft()
                        N-=1
                        k-=1
                    print(ans%MOD)
                    bool=True
                    break
            elif P==1:
                if k%2==0:
                    while(k>0):
                        ans*=neg[-1]
                        ans%=MOD
                        k-=1
                        neg.pop()
                        N-=1
                    print(ans)
                    bool=True
                    break
                else:
                    ans*=pos[-1]
                    P-=1
                    k-=1
                    while(k>0):
                        ans*=neg[-1]
                        ans%=MOD
                        neg.pop()
                        k-=1
                        N-=1
                    print(ans)
                    bool=True
                    break

            elif N==0:
                while(k>0):
                    ans*=pos[-1]
                    ans%=MOD
                    pos.pop()
                    k-=1
                    P-=1
                print(ans)
                bool=True
                break
            elif N==1:
                while(k>0):
                    ans*=pos[-1]
                    ans%=MOD
                    ans.pop()
                    k-=1
                    P-=1
                print(ans)
                bool=True
                break
            else:
                ans*=pos[-1]
                ans%=MOD
                pos.pop()
                P-=1
                k-=1

    if bool is False:
        print(ans%MOD)

Submission status: Runtime Error

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
import math
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math as M
MOD=10**9+7
#####################################
from collections import deque as D
#first we need to know whether our answer will be negative or positive if
#negative then among the neg values take the ones which have the least abs value

n,k=INPUT()
A=INPUT()
p1=[]
n1=[]
pos=D()
neg=D()
for i in A:
    if i>0:
        p1.append(i)
    elif i<0:
        n1.append(i)
p1.sort()
n1.sort(reverse=True)
for i in range(len(p1)):
    pos.append(p1[i])
for i in range(len(n1)):
    neg.append(n1[i])
P=len(pos)
N=len(neg)
if k==n:
    ans=1
    for i in range(n):
        ans*=A[i]
        ans%=MOD
    print(ans)

elif k>len(pos)+len(neg):
    print(0)

elif P==0 and k%2==1:
    #we know for sure ans will be negative here
    if P+N!=n:
        print(0)
    else:
        ans=1
        while(k>0 and P>0 and N>0):
            if abs(neg[0])<abs(neg[0]):
                ans*=neg[0]
                ans%=MOD
                neg.popleft()
                k-=1
                N-=1
            else:
                ans*=pos[0]
                ans%=MOD
                pos.popleft()
                k-=1
                P-=1
        if k==0:
            print(ans)
        else:
            if P==0:
                while(k>0):
                    ans*=neg.popleft()
                    ans%=MOD
                    k-=1
                    N-=1
                print(ans)
            else:
                while(k>0):
                    ans*=pos.posleft()
                    ans%=MOD
                    k-=1
                    P-=1
                print(ans)


else:
    bool=False
    ans=1
    while(k>0):
        #when both are len>=2
        while(k>1 and P>=2 and N>=2):
            if pos[-1]*pos[-2]>neg[-1]*neg[-2]:
                ans=ans*pos[-1]*pos[-2]
                ans%=MOD
                pos.pop()
                pos.pop()
                k-=2
                P-=2
            else:
                ans*=neg[-1]*neg[-2]
                ans%=MOD
                neg.pop()
                neg.pop()
                k-=2
                N-=2
            #print(ans)
        if k==0:
            print(ans%MOD)
            bool=True
            break
        elif k==1:
            #answer will be positive
            if P>0:
                ans=ans*pos[-1]
                ans%=MOD
                print(ans)
                bool=True
                break
            else:
                ans*=neg[-1]
                ans%=MOD
                print(ans)
                bool=True
                break
        else:
            #till now ans is positive and k>1 in both of them
            #the combiantion possible is p->1 to inf  n->1/0 ,n->1 to inf and p->1/0
            #k>1  and one of P or N is 0 now
            if P==0:
                if k%2==0:
                    while(k>0):
                        ans*=neg[-1]
                        ans%=MOD
                        neg.pop()
                        N-=1
                        k-=1
                    print(ans)
                    bool=True
                    break
                else:
                    while(k>0):
                        ans*=neg[0]
                        ans%=MOD
                        neg.popleft()
                        N-=1
                        k-=1
                    print(ans%MOD)
                    bool=True
                    break
            elif P==1:
                if k%2==0:
                    while(k>0):
                        ans*=neg[-1]
                        ans%=MOD
                        k-=1
                        neg.pop()
                        N-=1
                    print(ans)
                    bool=True
                    break
                else:
                    ans*=pos[-1]
                    P-=1
                    k-=1
                    while(k>0):
                        ans*=neg[-1]
                        ans%=MOD
                        neg.pop()
                        k-=1
                        N-=1
                    print(ans)
                    bool=True
                    break

            elif N==0:
                while(k>0):
                    ans*=pos[-1]
                    ans%=MOD
                    pos.pop()
                    k-=1
                    P-=1
                print(ans)
                bool=True
                break
            elif N==1:
                while(k>0):
                    ans*=pos[-1]
                    ans%=MOD
                    ans.pop()
                    k-=1
                    P-=1
                print(ans)
                bool=True
                break
            else:
                ans*=pos[-1]
                ans%=MOD
                pos.pop()
                P-=1
                k-=1

    if bool is False:
        print(ans%MOD)

Submission status: Runtime Error

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

def cross(xn,xp,z):
  N = n//2*2
  ans = 1
  cnt = 0
  if z == 0 | z == n:
    if z == 0:x = xp
    if z == n:x = xn
    for i in range(1,k+1):
      ans *= x[-i]
      cnt += 1
  else:
    r = 0
    for i in range(1,len(xn),2):
      r = bisect.bisect(ap,xn[i]*-1)
      if (len(xp)-r) + (r+1) >= N:break
    
    if r > 1:
      for i in range(r):
        ans *= xn[i]
    if n-r-1 > 0:
      for i in range(1,n-r):
        ans *= xp[-i]
  return ans 

import bisect
a.sort()
z = bisect.bisect(a,0)
if z != 0 and z != n:
  an = a[:z]
  ap = a[z:]
elif z == 0:
  an = []
  ap = a
elif z == n:
  ap = []
  an = a

print(cross(an,ap,z)%mod)

Submission status: Runtime Error

Solution code:
from functools import reduce
import numpy as np


def print_result(num):
    print(num%(pow(10,9)+7))

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

A = np.array(sorted(A, key=abs, reverse=True))
num_negative = np.count_nonzero(A<0)
if N == num_negative:
    if K % 2 == 0:
        print_result(np.prod(A[:K]))
    else:
        print_result(np.prod(A[-K:]))
elif np.count_nonzero(A[:K]<0) % 2 == 0:
    print_result(np.prod(A[:K]))
else:
    for a in A[K:]:
        if a >= 0:
            last = a
    print_result(np.prod(A[:K-1])*last)

Submission status: Runtime Error

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

if N==K: #全部
    ans=1
    for i in range(N):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()
if max(A)<0 and K%2==1: #答えがマイナス
    A.sort(reverse=True)
    ans=1
    for i in range(K):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()

plus=[]
minus=[]
for i in range(N):
    if A[i]>=0:
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True) #5,3,1
minus.sort() #-5,-3,-1
plus_k=0
minus_k=0
if K%2==0:
    ans=1
else:
    ans=plus[0]
    plus_k=1

for _ in range(K):
    if plus_k+minus_k==K:
        break
    if plus_k==len(plus):
        ans*=minus[minus_k]*minus[minus_k+1]%mod
        ans%=mod
        minus_k+=2
        continue
    if minus_k==len(minus):
        ans*=plus[plus_k]*plus[plus_k+1]%mod
        ans%=mod
        plus_k+=2
        continue
    if plus[plus_k]*plus[plus_k+1]>minus[minus_k]*minus[minus_k+1]:
        ans*=plus[plus_k]*plus[plus_k+1]%mod
        ans%=mod
        plus_k+=2
        continue
    else:
        ans*=minus[minus_k]*minus[minus_k+1]%mod
        ans%=mod
        minus_k+=2
        continue
print(ans)

Submission status: Runtime Error

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

if N==K: #全部
    ans=1
    for i in range(N):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()
if max(A)<0 and K%2==1: #答えがマイナス
    A.sort(reverse=True)
    ans=1
    for i in range(K):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()

plus=[]
minus=[]
for i in range(N):
    if A[i]>=0:
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True) #5,3,1
minus.sort() #-5,-3,-1
plus_k=0
minus_k=0
if K%2==0:
    ans=1
else:
    ans=plus[0]
    plus_k=1

for _ in range(K):
    if plus_k+minus_k==K:
        break
    if plus_k==len(plus)-1:
        ans*=minus[minus_k]*minus[minus_k+1]%mod
        ans%=mod
        minus_k+=2
        continue
    if minus_k==len(minus)-1:
        ans*=plus[plus_k]*plus[plus_k+1]%mod
        ans%=mod
        plus_k+=2
        continue
    if plus[plus_k]*plus[plus_k+1]>minus[minus_k]*minus[minus_k+1]:
        ans*=plus[plus_k]*plus[plus_k+1]%mod
        ans%=mod
        plus_k+=2
        continue
    else:
        ans*=minus[minus_k]*minus[minus_k+1]%mod
        ans%=mod
        minus_k+=2
        continue
print(ans)

Submission status: Runtime Error

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

if N==K: #全部
    ans=1
    for i in range(N):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()
if max(A)<0 and K%2==1: #答えがマイナス
    A.sort(reverse=True)
    ans=1
    for i in range(K):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()

plus=[]
minus=[]
for i in range(N):
    if A[i]>=0:
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True) #5,3,1
minus.sort() #-5,-3,-1
plus_k=0
minus_k=0
if K%2==0:
    ans=1
else:
    ans=plus[0]
    plus_k=1

for _ in range(K):
    if plus_k+minus_k==K:
        break
    if plus_k==len(plus)-1:
        ans*=minus[minus_k+1]*minus[minus_k+2]%mod
        ans%=mod
        minus_k+=2
        continue
    if minus_k==len(minus)-1:
        ans*=plus[plus_k+1]*plus[plus_k+2]%mod
        ans%=mod
        plus_k+=2
        continue
    if plus[plus_k+1]*plus[plus_k+2]>minus[minus_k+1]*minus[minus_k+2]:
        ans*=plus[plus_k+1]*plus[plus_k+2]%mod
        ans%=mod
        plus_k+=2
        continue
    else:
        ans*=minus[minus_k+1]*minus[minus_k+2]%mod
        ans%=mod
        minus_k+=2
        continue
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp
import bisect as bs
import sys

def cal(array):
  ans = 1
  for i in range(len(array)):
    ans *= array[i]
    ans %= 10**9+7
    
  return ans

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

a = sorted(list(map(int, input().split())))
index = bs.bisect_left(a, 0)

c = a[:index]
index = bs.bisect_right(a, 0)

b = a[index:]

if len(b) + len(c) < k:
  print(0)
  sys.exit()
  
if len(a) == k:
  print(cal(a))
  sys.exit()
    

if len(b) == 0 and k % 2 != 0:
  ans = 1
  c = list(reversed(c))
  
  print(cal(c[:k]))
  sys.exit()
  
  
if len(b) < k:
  if (k - len(b)) % 2 == 0:
    for i in range(k-len(b)):
      b.append(hp.heappop(c) * (-1))
      
    print(cal(b))
    sys.exit()
  
  else:
    d = []
    c = reversed(c)
    for i in range(len(b)-1):
      d.append(c[i])
      
    if (k-len(b)+1) > len(b):
      print(0)
      sys.exit()
    
    else:
      for i in range(k-len(b)+1):
        d.append(c[i])
        
      ans = 1
      for i in range(len(d)):
        ans *= d[i]
        ans %= 10 ** 9 + 7
      
      print(ans)
  
while True:
  if len(c) < 2:
    break
  
  b1 = hp.heappop(b)
  b2 = hp.heappop(b)
    
  c1 = hp.heappop(c)
  c2 = hp.heappop(c)
    
  
  if b1*b2 <= c1*c2:
    hp.heappush(b, c1)
    hp.heappush(b, c2)
  else:
    break
    
ans = 1
for i in range(len(b)):
  ans *= b[i]
  ans %= 10 ** 9 + 7
  
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp
import bisect as bs
import sys

def cal(array):
  ans = 1
  for i in range(len(array)):
    ans *= array[i]
    ans %= 10**9+7
    
  return ans

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

a = sorted(list(map(int, input().split())))
index = bs.bisect_left(a, 0)

c = a[:index]
index = bs.bisect_right(a, 0)

b = a[index:]

if len(b) + len(c) < k:
  print(0)
  sys.exit()
  
if len(a) == k:
  print(cal(k))
  sys.exit()
    

if len(b) == 0 and k % 2 != 0:
  ans = 1
  c = list(reversed(c))
  
  print(cal(c[:k]))
  sys.exit()
  
  
if len(b) < k:
  if (k - len(b)) % 2 == 0:
    for i in range(k-len(b)):
      b.append(hp.heappop(c) * (-1))
      
    print(cal(b))
    sys.exit()
  
  else:
    d = []
    c = reversed(c)
    for i in range(len(b)-1):
      d.append(c[i])
      
    if (k-len(b)+1) > len(b):
      print(0)
      sys.exit()
    
    else:
      for i in range(k-len(b)+1):
        d.append(c[i])
        
      ans = 1
      for i in range(len(d)):
        ans *= d[i]
        ans %= 10 ** 9 + 7
      
      print(ans)
  
while True:
  if len(c) < 2:
    break
  
  b1 = hp.heappop(b)
  b2 = hp.heappop(b)
    
  c1 = hp.heappop(c)
  c2 = hp.heappop(c)
    
  
  if b1*b2 <= c1*c2:
    hp.heappush(b, c1)
    hp.heappush(b, c2)
  else:
    break
    
ans = 1
for i in range(len(b)):
  ans *= b[i]
  ans %= 10 ** 9 + 7
  
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp
import bisect as bs
import sys

def cal(array):
  ans = 1
  for i in range(len(array)):
    ans *= array[i]
    ans %= 10**9+7
    
  return ans

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

a = sorted(list(map(int, input().split())))
index = bs.bisect_left(a, 0)

c = a[:index]
index = bs.bisect_right(a, 0)

b = a[index:]

if len(b) + len(c) < k:
  print(0)
  sys.exit()
  
if len(a) == k:
  print(cal(k))
  sys.exit()
    

if len(b) == 0 and k % 2 != 0:
  ans = 1
  c = list(reversed(c))
  
  print(c[:k])
  sys.exit()
  
  
if len(b) < k:
  if (k - len(b)) % 2 == 0:
    for i in range(k-len(b)):
      b.append(hp.heappop(c) * (-1))
      
    print(cal(b))
    sys.exit()
  
  else:
    d = []
    c = reversed(c)
    for i in range(len(b)-1):
      d.append(c[i])
      
    if (k-len(b)+1) > len(b):
      print(0)
      sys.exit()
    
    else:
      for i in range(k-len(b)+1):
        d.append(c[i])
        
      ans = 1
      for i in range(len(d)):
        ans *= d[i]
        ans %= 10 ** 9 + 7
      
      print(ans)
  
while True:
  if len(c) < 2:
    break
  
  b1 = hp.heappop(b)
  b2 = hp.heappop(b)
    
  c1 = hp.heappop(c)
  c2 = hp.heappop(c)
    
  
  if b1*b2 <= c1*c2:
    hp.heappush(b, c1)
    hp.heappush(b, c2)
  else:
    break
    
ans = 1
for i in range(len(b)):
  ans *= b[i]
  ans %= 10 ** 9 + 7
  
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp
import bisect as bs
import sys
n,k = map(int, input().split())

a = sorted(list(map(int, input().split())))
index = bs.bisect_left(a, 0)

c = a[:index]
index = bs.bisect_right(a, 0)

b = a[index:]

if len(b) + len(c) < k:
  print(0)
  sys.exit()
  
if len(a) == k:
  ans = 1
  for i in range(len(a)):
    ans *= a[i]
    ans %= 10**9+7
  
  print(ans)
  sys.exit()
    

if len(b) == 0 and k % 2 != 0:
  ans = 1
  c = list(reversed(c))
  for v in c[:k]:
    ans *= v
    ans %= 10**9+7
  
  print(ans)
  sys.exit()
  
  
if len(b) < k:
  if (k - len(b)) % 2 == 0:
    for i in range(k-len(b)):
      b.append(c.pop() * (-1))
  
  else:
    d = []
    c = reversed(c)
    for i in range(len(b)-1):
      d.append(c[i])
      
    if (k-len(b)+1) > len(b):
      print(0)
      sys.exit()
    
    else:
      for i in range(k-len(b)+1):
        d.append(c[i])
        
      ans = 1
      for i in range(len(d)):
        ans *= d[i]
        ans %= 10 ** 9 + 7
      
      print(ans)
  
while True:
  if len(c) < 2:
    break
  
  b1 = hp.heappop(b)
  b2 = hp.heappop(b)
    
  c1 = hp.heappop(c)
  c2 = hp.heappop(c)
    
  
  if b1*b2 <= c1*c2:
    hp.heappush(b, c1)
    hp.heappush(b, c2)
  else:
    break
    
ans = 1
for i in range(len(b)):
  ans *= b[i]
  ans %= 10 ** 9 + 7
  
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)

l = [list(_) for _ in comb]  
A = (functools.reduce(operator.mul,l[_]) for _ in range(len(l)))

l_max = max(A)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

Submission status: Runtime Error

Solution code:
import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
a.sort()
D = [[a[i+j-k] for j in range(k)] for i in range(-k,k)]
A = (functools.reduce(operator.mul,D[_]) for _ in range(len(D)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

Submission status: Runtime Error

Solution code:
import heapq as hp
import bisect as bs
import sys
n,k = map(int, input().split())

a = sorted(list(map(int, input().split())))
index = bs.bisect_left(a, 0)

c = a[:index]
index = bs.bisect_right(a, 0)

b = a[index:]

if len(b) + len(c) < k:
  print(0)
  sys.exit()
  
if len(a) == k:
  ans = 1
  for i in range(len(a)):
    ans *= a[i]
    ans %= 10**9+7
  
  print(ans)
  sys.exit()
    

if len(b) == 0 and k % 2 != 0:
  ans = 1
  c = list(reversed(c))
  for v in c[:k]:
    ans *= v
    ans %= 10**9+7
  
  print(ans)
  sys.exit()
  
  
if len(b) < k:
  if (k - len(b)) % 2 == 0:
    for i in range(k-len(b)):
      b.append(c.pop() * (-1))
  
  else:
    d = []
    c = reversed(c)
    for i in range(len(b)-1):
      d.append(c[i])
      
    if (k-len(b)+1) > len(b):
      print(0)
      sys.exit()
    
    else:
      for i in range(k-len(b)+1):
        b.append(c[i] * (-1))
  
  
while True:
  if len(c) < 2:
    break
  
  b1 = hp.heappop(b)
  b2 = hp.heappop(b)
    
  c1 = hp.heappop(c)
  c2 = hp.heappop(c)
    
  
  if b1*b2 <= c1*c2:
    hp.heappush(b, c1)
    hp.heappush(b, c2)
  else:
    break
    
ans = 1
for i in range(len(b)):
  ans *= b[i]
  ans %= 10 ** 9 + 7
  
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp
import bisect as bs
import sys
n,k = map(int, input().split())

a = sorted(list(map(int, input().split())))
index = bs.bisect_left(a, 0)

c = a[:index]
index = bs.bisect_right(a, 0)

b = a[index:]

if len(b) + len(c) < k:
  print(0)
  sys.exit()
  
if len(a) == k:
  ans = 1
  for i in range(len(a)):
    ans *= a[i]
    ans %= 10**9+7
  
  print(ans)
  sys.exit()
    

if len(b) == 0 and k % 2 != 0:
  ans = 1
  c = list(reversed(c))
  for v in c[:k]:
    ans *= v
    ans %= 10**9+7
  
  print(ans)
  sys.exit()
  
  
if len(b) < k:
  if (k - len(b)) % 2 == 0:
    for i in range(k-len(b)):
      b.append(c.pop() * (-1))
  
  else:
    d = []
    c = reversed(c)
    for i in range(len(b)-1):
      d.append(c[i])
      
    if (k-len(b)+1) > len(b):
      print(0)
    
    else:
      for i in range(k-len(b)+1):
        b.append(c[i] * (-1))
  
  
while True:
  if len(c) < 2:
    break
  
  b1 = hp.heappop(b)
  b2 = hp.heappop(b)
    
  c1 = hp.heappop(c)
  c2 = hp.heappop(c)
    
  
  if b1*b2 <= c1*c2:
    hp.heappush(b, c1)
    hp.heappush(b, c2)
  else:
    break
    
ans = 1
for i in range(len(b)):
  ans *= b[i]
  ans %= 10 ** 9 + 7
  
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp
import bisect as bs
import sys
n,k = map(int, input().split())

a = sorted(list(map(int, input().split())))
index = bs.bisect_left(a, 0)

c = a[:index]
index = bs.bisect_right(a, 0)

b = a[index:]

if len(b) + len(c) < k:
  print(0)
  sys.exit()
  
if len(a) == k:
  ans = 1
  for i in range(len(a)):
    ans *= a[i]
    ans %= 10**9+7
  
  print(ans)
    

if len(b) == 0 and k % 2 != 0:
  ans = 1
  c = list(reversed(c))
  for v in c[:k]:
    ans *= v
    ans %= 10**9+7
  
  print(ans)
  sys.exit()
  
  
if len(b) < k:
  if (k - len(b)) % 2 == 0:
    for i in range(k-len(b)):
      b.append(c.pop() * (-1))
  
  else:
    d = []
    c = reversed(c)
    for i in range(len(b)-1):
      d.append(c[i])
      
    if (k-len(b)+1) > len(b):
      print(0)
    
    else:
      for i in range(k-len(b)+1):
        b.append(c[i] * (-1))
  
  
while True:
  if len(c) < 2:
    break
  
  b1 = hp.heappop(b)
  b2 = hp.heappop(b)
    
  c1 = hp.heappop(c)
  c2 = hp.heappop(c)
    
  
  if b1*b2 <= c1*c2:
    hp.heappush(b, c1)
    hp.heappush(b, c2)
  else:
    break
    
ans = 1
for i in range(len(b)):
  ans *= b[i]
  ans %= 10 ** 9 + 7
  
print(ans)