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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,K=map(int,input().split())
A=list(map(int,input().split()))
A_m=[x for x in A if x<0]
A_pz=[x for x in A if x>=0]
A_m.sort()
A_pz.sort(reverse=1)
if N==K:
    ans=1
    for x in A:
        ans*=x
        ans%=MOD
elif not A_pz and K%2==1:
    ans=1
    for x in A_m[::-1][:K]:
        ans*=x
        ans%=MOD
else:
    B=[]
    for i in range(len(A_m)//2):
        B.append(A_m[i*2]*A_m[i*2+1])
    B.sort(reverse=1)
    i,j=0,0
    ans=1
    while i+j*2<=K-2:
        if i<len(A_pz)-1 and j<len(B):
            if A_pz[i]*A_pz[i+1]>B[j]:
                ans*=A_pz[i]*A_pz[i+1]
                i+=2
            else:
                ans*=B[j]
                j+=1
        elif i<len(A_pz):
            ans*=A_pz[i]
            i+=1
        else:
            ans*=B[j]
            j+=1
        ans%=MOD
    if i+j*2==K-2:
        if i<len(A_pz)-1 and j<len(B):
            ans*=max(A_pz[i]*A_pz[i+1],B[j])
        elif i<len(A_pz)-1:
            ans*=A_pz[i]*A_pz[i+1]
        else:
            ans*=B[j]
    elif i+j*2==K-1:
        if i<len(A_pz):
            ans*=A_pz[i]
        else:
            ans*=A_m[-1]
    ans%=MOD
ans%=MOD
print(ans)

Submission status: Wrong Answer

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

a_plus = []
a_minus = []
cnt_0 = 0

for ai in a:
    if(ai==0):
        cnt_0 += 1
    elif(ai > 0):
        a_plus.append(ai)
    else:
        a_minus.append(ai)

a_plus.sort(reverse = True)
a_minus.sort()

cnt_p = len(a_plus)
cnt_m = len(a_minus)

if(cnt_p + cnt_m < k):
    print(0)
    exit()


if(cnt_m == n)&(k%2==1):
    ans = 1
    for i in range(k):
        ans *= a_minus[cnt_m - 1 - i]
        ans %= mod
    print(ans)
    exit()

if(cnt_p == 0)&(k%2==1):
    print(0)
    exit()

p_ind = 0
m_ind = 0

ans = 1
if(k%2==1):
    last_p = a_plus[0]
    cnt_p -= 1
    a_plus = a_plus[1:]

for i in range(k//2):
    tmp_p = 0
    tmp_m = 0
    if(p_ind + 2 <= cnt_p ):
        tmp_p = a_plus[p_ind] * a_plus[p_ind+1]

    if(m_ind + 2 <= cnt_m ):
        tmp_m = a_minus[m_ind] * a_minus[m_ind+1]

    if(tmp_p > tmp_m):
        ans *= tmp_p
        p_ind += 2
    else:
        ans *= tmp_m
        m_ind += 2
    ans %= mod

if(k%2==1):
    ans *= last_p

ans %= mod
print(ans)

Submission status: Wrong Answer

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

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

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

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(lst,k):  # fix inputs here
    console("----- solving ------")

    MOD = 10**9 + 7

    lst = sorted(lst)[::-1]
    lst = sorted(lst, key=lambda x: abs(x))[::-1]
    sign = [0 if x == 0 else x//abs(x) for x in lst]

    console(lst)
    console(sign)

    # no choice negative
    if all([x == -1 for x in sign]) and k%2 == 1:
        res = 1
        for i in lst[::-1][:k]:
            res = (res*i)%MOD 
        return res

    # no choice take all
    if k == len(lst):
        res = 1
        for i in lst:
            res = (res*i)%MOD 
        return res

    # not enough nonzeros
    if lst[k-1] == 0:
        return 0

    pos = max(lst[k-1:])
    neg = min(lst[k-1:])

    initial_sign = 1
    for i in sign[:k-1]:
        initial_sign = initial_sign*i

    if initial_sign == 1:
        res = pos
        for i in lst[:k-1]:
            res = (res*i)%MOD
        return res

    if initial_sign == -1:
        res = neg
        for i in lst[:k-1]:
            res = (res*i)%MOD
        return res

    # return a string (i.e. not a list or matrix)
    return 0


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return


for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    _,k = list(map(int,input().split()))
    lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

    res = solve(lst,k)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Wrong Answer

Solution code:
n,k,*a=map(int,open(0).read().split())
mod=10**9+7
b=[i for i in a if i>0]
c=[i for i in a if i<0]
b.sort()
c.sort()
B,C=len(b),len(c)
D=n-B-C
b=b[::-1]+[0]*k
c+=[0]*k
ans=1
i=j=0
while k:
    if b[i]>abs(c[j]):
        ans*=b[i]
        if ans>=0:
            ans%=mod
        i+=1
    else:
        ans*=c[j]
        if ans>=0:
            ans%=mod
        j+=1
    k-=1  
    print(ans)
if ans>=0:
    print(ans)
else:
    print(ans*pow(c[i-1],mod-2,mod)*c[i]%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9 + 7
b_p = []
b_n = []
ab = []
for i in range(n):
    ab.append(abs(a[i]))
    if a[i] >= 0:
        b_p.append(a[i])
    else:
        b_n.append(a[i])
b_p = sorted(b_p,reverse=True)
b_n = sorted(b_n)
ab = sorted(ab)
ans = 1
i = 0
x = 0
y = 0
if k%2 == 1:
    if len(b_p) >= 1:
        ans *= b_p[0]
        x += 1
        i += 1
while i < k-1:
    i += 2
    if x < len(b_p)-1 and y < len(b_n)-1:
        if b_p[x]*b_p[x+1] > b_n[y]*b_n[y+1]:
            ans *= b_p[x]*b_p[x+1]
            ans %= mod
            x += 2
        else:
            ans *= b_n[y]*b_n[y+1]
            ans %= mod
            y += 2
    
    elif x < len(b_p)-1:
        ans *= b_p[x]*b_p[x+1]
        ans %= mod
        x += 2
    elif y < len(b_n)-1:
        ans *= b_n[y]*b_n[y+1]
        ans %= mod
        y += 2
    else:
        break
if i != k:
    if x < len(b_p):
        ans *= b_p[x]
        ans %= mod
    else:
        if 0 in b_p:
            ans = 0
        else:
            ans = 1
            for i in range(k):
                ans *= ab[i]
                ans %= mod
            ans *= -1
print(ans%mod)

Submission status: Wrong Answer

Solution code:
def main():

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

    mod = pow(10, 9) + 7

    pos = []
    neg = []
    zero = 0
    for v in A:
        if v > 0: pos.append(v)
        elif v < 0: neg.append(v)
        else: zero += 1

    if len(pos) + len(neg) < K:
        return 0

    pos.sort(reverse = True)
    neg.sort()

    cnt_p, cnt_n = 0, 0
    h = []
    for v in pos:
        h.append([v, 1])
    for v in neg:
        h.append([-v, -1])

    h.sort(reverse = True)
    v = 1
    for k in range(K):
        if h[k][1] > 0:
            cnt_p += 1
        else:
            cnt_n += 1

    if cnt_n % 2 == 0:
        v = 1
        for i in range(cnt_p):
            v *= pos[i]
            v %= mod
        for j in range(cnt_n):
            v *= neg[j]
            v %= mod
        return v
    else:
        if cnt_p < len(pos) and cnt_n < len(neg):
            if pos[cnt_p-1] * abs(neg[cnt_n]) < pos[cnt_p] * abs(neg[cnt_n-1]):
                cnt_p += 1
                cnt_n -= 1
            else:
                cnt_p -= 1
                cnt_n += 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        elif cnt_p < len(pos) and cnt_n > 0:
            cnt_p += 1
            cnt_n -= 1
            v = 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        elif cnt_n < len(neg) and cnt_p > 0:
            cnt_p -= 1
            cnt_n += 1
            for i in range(cnt_p):
                v *= pos[i]
                v %= mod
            for j in range(cnt_n):
                v *= neg[j]
                v %= mod
            return v
        else:
            if zero > 0:
                return 0
            else:
                h.sort()
                v = 1
                for i in range(K):
                    v *= h[i][0] * h[i][1]
                    v %= mod
                return v 



if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import heapq

mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
cnt_plus=0
cnt_zero=0
cnt_minus=0
arr_plus=[]
arr_minus=[]
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    arr_plus.append(arr[i])
  elif arr[i]<0:
    cnt_minus+=1
    arr_minus.append(-arr[i])
  else:
    cnt_zero+=1
if cnt_plus+cnt_minus<k:
  print(0)
else:
  if (k%2==1 and cnt_plus==0) or (cnt_plus+2*(cnt_minus//2)<k):
    q=[]
    for i in range(n):
      if arr[i]>0:
        heapq.heappush(q,(arr[i],1))
      if arr[i]<0:
        heapq.heappush(q,(-arr[i],-1))
    pick=[]
    for i in range(k):
      tmp,flag=heapq.heappop(q)
      if flag==1:
        pick.append(tmp)
      else:
        pick.append(-tmp)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans)
  else:
    q=[]
    for i in range(n):
      if arr[i]>0:
        heapq.heappush(q,(-arr[i],1))
      if arr[i]<0:
        heapq.heappush(q,(arr[i],-1))
    pick=[]
    prev=0
    cnt=0
    for _ in range(k):
      tmp,flag=heapq.heappop(q)
      tmp*=-1
      if flag==1:
        pick.append(tmp)
      else:
        if cnt==0:
          prev=tmp
          cnt+=1
        else:
          cnt=0
          pick.append(prev)
          pick.append(tmp)
          prev=0
    if cnt==0:
      ans=1
      for i in range(k):
        ans*=pick[i]
        ans%=mod
      print(ans)
    else:
      cand_plus=0
      cand_minus=0
      while len(q)!=0:
        tmp,flag=heapq.heappop(q)
        if flag==1 and cand_plus==0:
          cand_plus=tmp
        if flag==-1 and cand_minus==0:
          cand_minus=tmp
        if cand_plus!=0 and cand_minus!=0:
          break
      if pick[-1]*cand_plus>=prev*cand_minus:
        pick.append(cand_plus)
      else:
        pick=pick[:-1]
        pick.append(prev)
        pick.append(cand_minus)      
      ans=1
      for i in range(k):
        ans*=pick[i]
        ans%=mod
      print(ans)

Submission status: Wrong Answer

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

listA.sort()
hidariI = 0
migiI = len(listA)-1

hidatiKouho = 1
migiKouho = 1

for i in range(k):
    hidatiKouho*=listA[hidariI]
    migiKouho*=listA[migiI]
    if hidatiKouho > 0:
        hidatiKouho %= 10**9 + 7
    if migiKouho > 0:
        migiKouho %= 10**9 + 7
    hidariI+=1
    migiI-=1

print(max(hidatiKouho, migiKouho)%(10**9 + 7))

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def doubling_LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.depth=[None]*self.node_size
            self.depth=self.bfs(0,func=lambda pr,prv,nxt,dist:prv+1)
            self.par=self.bfs(0,func=lambda pr,prv,nxt,dist:pr)
            self.db=[self.par]
            for i in range(self.node_size.bit_length()):
                #show(self.db)
                self.db+=[[self.db[-1][self.db[-1][i]] for i in range(self.node_size)]]
            self.LCA_init_stat=True
        dx=self.depth[x]
        dy=self.depth[y]
        if dx>dy:
            dx,dy=dy,dx
        c=self.node_size.bit_length()
        while c>0:
            if dx+c<=dy:
                x=self.db[c][x]
                dx+=1<<c
            c>>=1
        
        if x==y:
            return x
        
        c=self.node_size.bit_length()
        while c>0:
            if self.db[c][x]!=self.db[c][y]:
                x=self.db[c][x]
                y=self.db[c][y]
            c>>=1
        
        return self.par[x]
        
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)
 
    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos

    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True

ans=0

#h,w,K=LI()
n,k=LI()
b=LI()
a=sorted(b)
b.sort(key=lambda x:abs(x))

pl,mn,zr=[],[],[]
for i in a:
    if i>0:
        pl+=i,
    elif i<0:
        mn+=i,
    else:
        zr+=i,
    
def maximize(b,k):
    p,m=0,0
    mn_p,mn_m=inf,inf
    rt=1
    for i in range(k):
        x=b.pop()
        if x>0:
            p+=1
            if mn_p>x:
                mn_p=x
                #show('mn_p',mn_p,x)
        elif x<0:
            m+=1
            if mn_m>x:
                mn_m=-x
                #show('mn_n',mn_m,x)
        rt*=x
        rt%=mo
    #show(rt)
    if m%2==1:
        while b:
            x=b.pop()
            if x>0:
                #show('?',rt,rt//mn_m,mn_m,x)
                rt*=pow(-mn_m,mo-2,mo)
                #rt//=mn_m
                rt*=x
                rt%=mo
                return rt
            elif x<0 and p>0:
                rt*=pow(mn_p,mo-2,mo)
                #rt//=mn_p
                rt*=x
                rt%=mo
                return rt
    return rt

#M=maximize(b,k)
#show(M,(M-mo))

if k+len(zr)==n:
    al=1
    for i in pl:
        al*=i
        al%=mo
    for i in mn:
        al*=i
        al%=mo
    ans=max(0,al)
    st=0
elif k+len(zr)>n:
    ans=0
    st=1
elif k%2==1 and len(pl)==0: # minus case
    ans=1
    for i in range(k):
        x=b[i]
        ans*=x
        ans%=mo
    if len(zr)>0:
        ans=0
    st=2
else:
    ans=maximize(b,k)
    st=3


print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N ,K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
mod = 10 ** 9 + 7
# ans = 0
if A.count(0) > (N - K):
  print(0)
  quit()
  
# ans = minus
plus = bisect.bisect_right(A, 0)
minus = bisect.bisect_left(A, 0) 
if N == K:
  ans = 1
  for i in range(N):
    ans *= A[i]
    ans %= mod
  print(ans % mod)
  quit()
  
if minus == N:
  ans = 1
  for i in range(1, K + 1):
    ans *= A[-i]
    ans %= mod
  print(ans % mod)
  quit()
  
ans = 1

count = 0
i = 0
j = -1
while count < K:
  if K - count >= 2:
    fo = A[i] * A[i + 1]
    re = A[j] * A[j - 1]
    #print(fo, re)
    if fo > re:
      ans *= (fo % mod) 
      ans %= mod
      i += 2
    #elif (A[j - 1] < 1) or (A[j - 2] < 1):
    #  ans *= (fo % mod) 
    #  ans %= mod
    #  i += 2      
    else:
      ans *= (re % mod)
      ans %= mod
      j -= 2
    count += 2  
  else:
    count += 1
    ans *= A[j]
      
  #print(ans)
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    mod = 10**9+7
    n,k = map(int,input().split())
    arr = list(map(int,input().split()))
    pos = []
    neg = []
    zero = 0
    for i in arr:
        if i > 0:
            pos.append(i)
        elif i < 0:
            neg.append(i)
        else:
            zero += 1

    pos.sort()
    neg.sort()
    if not pos:
        prod = 1
        if k%2 == 0:
            while neg and k > 0:
                prod *= neg.pop(0)
                k -= 1
                prod %= mod
        else:
            while neg and k > 0:
                prod *= neg.pop()
                k -= 1
                prod %= mod

        while k > 0:
            prod *= 0
            zero -= 1
            k -= 1

        print(prod)
        return 
    
    heap = []
    while pos:
        heapq.heappush(heap,(-pos.pop(),1))

    while len(neg) >= 2:
        a = neg.pop(0)
        b = neg.pop(0)
        heapq.heappush(heap,(-(a*b/2),2))
        heapq.heappush(heap,(-a,1))
        heapq.heappush(heap,(-b,1))

    while neg:
        heapq.heappush(heap,(-neg.pop(),1))

    while zero > 0:
        heapq.heappush(heap,(0,1))
        zero -= 1

    prod = 1
    while k > 0:
        cost,count = heapq.heappop(heap)
        cost = -cost
        if count == 2:
            if k >= 2:
                cost *= 2
                cost = int(cost)
                prod *= cost
                k -= 2
        else:
            prod *= cost
            k -= 1

        prod %= mod
        
    print(prod)

main()