Problem p02616 (python)

Fixed submission:
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
cnt_plus=0
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev_plus=0
prev_minus=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
    prev_plus=tmp
  if flag==-1:
    if cnt==0:
      prev_minus=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev_minus)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if (k%2==1 and cnt_plus==0) or (cand_plus==0 and cand_minus==0):
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if prev_plus*cand_plus>=prev_minus*cand_minus:
      pick.append(cand_plus)
    else:
      if prev_plus!=0:
        pick.remove(prev_plus)
        pick.append(prev_minus)
        pick.append(cand_minus)
      else:
        pick.append(cand_plus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)

Buggy submission (verdict: Runtime Error):
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)
  exit()
if k==n:
  if cnt_zero!=0:
    print(0)
  else:
    ans=1
    for i in range(cnt_plus):
      ans*=arr_plus[i]
      ans%=mod
    for i in range(cnt_minus):
      ans*=arr_minus[i]
      ans%=mod
    if cnt_minus%2==0:
      print(ans)
    else:
      print((-ans)%mod)
  exit()
if cnt_plus==0 and k%2==1:
  if cnt_zero!=0:
    print(0)
  else:
    arr_minus=sorted(arr_minus)
    tmp=1
    for i in range(k):
      tmp*=arr_minus[i]
      tmp%=mod
    print((-tmp)%mod)
  exit()
else:
  arr_plus=sorted(arr_plus,reverse=True)
  arr_minus=sorted(arr_minus,reverse=True)
  acum_plus=[1]
  for i in range(len(arr_plus)):
    acum_plus.append((acum_plus[-1]*arr_plus[i])%mod)
  acum_minus=[1]  
  for i in range(len(arr_minus)):
    acum_minus.append((acum_minus[-1]*arr_minus[i])%mod)  
  if k%2==0:
    ans=0
    for i in range(0,len(arr_plus)+1,2):
      j=k-i
      if len(arr_minus)<j:
        continue
      ans=max(ans,(acum_plus[i]*acum_minus[j])%mod)
    print(ans)
  else:
    ans=0
    for i in range(1,len(arr_plus)+1,2):
      j=k-i
      if len(arr_minus)<j:
        continue
      ans=max(ans,(acum_plus[i]*acum_minus[j])%mod)
    print(ans)
  exit()

Buggy submission (verdict: Runtime Error):
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x))
if k==n:
  ans=1
  for i in range(n):
    ans*=arr[i]
    ans%=mod
  print(ans)
else:
  if k%2==1 and max(arr)<0:
    ans=1
    for i in range(k):
      ans*=arr[n-1-i]
      ans%=mod
    print(ans)
  else:
    ans=1
    cnt=0
    for i in range(k):
      if arr[i]<0:
        cnt+=1
      ans*=arr[i]
      ans%=mod
    if cnt%2==0:
      print(ans)
    else:
      min_plus=0
      min_minus=0
      for i in range(k):
        if arr[i]>=0:
          min_plus=arr[i]
        else:
          min_minus=arr[i]
      max_plus=0
      max_minus=0
      for i in range(k,n):
        if arr[i]>=0 and max_plus==0:
          max_plus=arr[i]
        if arr[i]<0 and max_minus==0:
          max_minus=arr[i]
      if min_plus*max_plus>=min_minus*max_minus:
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      else:
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%-mod
        ans*=max_minus
        ans%=mod
      print(ans)

Buggy submission (verdict: Runtime Error):
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x))
if k==n:
  ans=1
  for i in range(n):
    ans*=arr[i]
    ans%=mod
  print(ans)
else:
  if k%2==1 and max(arr)<0:
    ans=1
    for i in range(k):
      ans*=arr[n-1-i]
      ans%=mod
    print(ans)
  else:
    ans=1
    cnt=0
    for i in range(k):
      if arr[i]<0:
        cnt+=1
      ans*=arr[i]
      ans%=mod
    if cnt%2==0:
      print(ans)
    else:
      min_plus=0
      min_minus=0
      for i in range(k):
        if arr[i]>=0:
          min_plus=arr[i]
        else:
          min_minus=arr[i]
      max_plus=0
      max_minus=0
      for i in range(k,n):
        if arr[i]>=0 and max_plus==0:
          max_plus=arr[i]
        if arr[i]<0 and max_minus==0:
          max_minus=arr[i]
      print(min_plus,min_minus,max_plus,max_minus)
      if min_plus*max_plus>=min_minus*max_minus:
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      else:
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%-mod
        ans*=max_minus
        ans%=mod
      print(ans)

Buggy submission (verdict: Runtime Error):
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x))
print(arr)
if k==n:
  ans=1
  for i in range(n):
    ans*=arr[i]
    ans%=mod
  print(ans)
else:
  if k%2==1 and max(arr)<0:
    ans=1
    for i in range(k):
      ans*=arr[n-1-i]
      ans%=mod
    print(ans)
  else:
    ans=1
    cnt=0
    for i in range(k):
      if arr[i]<0:
        cnt+=1
      ans*=arr[i]
      ans%=mod
    if cnt%2==0:
      print(ans)
    else:
      min_plus=0
      min_minus=0
      for i in range(k):
        if arr[i]>=0:
          min_plus=arr[i]
        else:
          min_minus=arr[i]
      max_plus=0
      max_minus=0
      for i in range(k,n):
        if arr[i]>=0 and max_plus==0:
          max_plus=arr[i]
        if arr[i]<0 and max_minus==0:
          max_minus=arr[i]
      print(min_plus,min_minus,max_plus,max_minus)
      if min_plus*max_plus>=min_minus*max_minus:
        arr.remove(min_minus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%=mod
        ans*=max_plus
        ans%=mod
      else:
        arr.remove(min_plus)
        ans=1
        for i in range(k-1):
          ans*=arr[i]
          ans%-mod
        ans*=max_minus
        ans%=mod
      print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
cnt_plus=0
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev_plus=0
prev_minus=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
    prev_plus=tmp
  if flag==-1:
    if cnt==0:
      prev_minus=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev_minus)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if (k%2==1 and cnt_plus==0) or (cand_plus==0 and cand_minus==0):
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if prev_plus*cand_plus>=prev_minus*cand_minus:
      pick.append(cand_plus)
    else:
      pick.remove(prev_plus)
      pick.append(prev_minus)
      pick.append(cand_minus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)

Buggy submission (verdict: Runtime Error):
import heapq
 
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
q=[]
cnt_plus=0
for i in range(n):
  if arr[i]>0:
    cnt_plus+=1
    heapq.heappush(q,(-arr[i],1))
  elif arr[i]<0:
    heapq.heappush(q,(arr[i],-1))
  else:
    heapq.heappush(q,(0,0))
pick=[]
prev_plus
prev_minus=0
cnt=0
for i in range(k):
  tmp,flag=heapq.heappop(q)
  tmp*=-1
  if flag==0:
    print(0)
    exit()
  if flag==1:
    pick.append(tmp)
    prev_plus=tmp
  if flag==-1:
    if cnt==0:
      prev_minus=tmp
      cnt+=1
    else:
      cnt=0
      pick.append(prev_minus)
      pick.append(tmp)
if cnt==0:
  ans=1
  for i in range(k):
    ans*=pick[i]
    ans%=mod
  print(ans%mod)
else:
  cand_plus=0
  cand_minus=0
  while len(q)!=0:
    tmp,flag=heapq.heappop(q)
    tmp*=-1
    if flag==1 and cand_plus==0:
      cand_plus=tmp
    if flag==-1 and cand_minus==0:
      cand_minus=tmp
  if (k%2==1 and cnt_plus==0) or (cand_plus==0 and cand_minus==0):
    if arr.count(0)!=0:
      print(0)
      exit()
    else:
      q=[]
      for i in range(n):
        heapq.heappush(q,abs(arr[i]))
      ans=1
      for _ in range(k):
        ans*=heapq.heappop(q)
        ans%=mod
      print((-ans)%mod)
  else:
    if prev_plus*cand_plus>=prev_minus*cand_minus:
      pick.append(cand_plus)
    else:
      pick=pick[:-1]
      pick.append(prev_minus)
      pick.append(cand_minus)
    ans=1
    for i in range(k):
      ans*=pick[i]
      ans%=mod
    print(ans%mod)

Buggy submission (verdict: Runtime Error):
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)
  exit()
if cnt_plus==0 and k%2==1:
  arr_minus=sorted(arr_minus)
  tmp=1
  for i in range(k):
    tmp*=arr_minus[i]
    tmp%=mod
  print((-tmp)%mod)
else:
  arr_plus=sorted(arr_plus,reverse=True)
  arr_minus=sorted(arr_minus,reverse=True)
  acum_plus=[1]
  for i in range(len(arr_plus)):
    acum_plus.append((acum_plus[-1]*arr_plus[i])%mod)
  acum_minus=[1]  
  for i in range(len(arr_minus)):
    acum_minus.append((acum_minus[-1]*arr_minus[i])%mod)  
  if k%2==0:
    ans=0
    for i in range(0,len(arr_plus)+1,2):
      j=k-i
      if len(arr_minus)<j:
        continue
      ans=max(ans,(acum_plus[i]*acum_minus[j])%mod)
    print(ans)
  else:
    ans=0
    for i in range(1,len(arr_plus)+1,2):
      j=k-i
      if len(arr_minus)<j:
        continue
      ans=max(ans,(acum_plus[i]*acum_minus[j])%mod)
    print(ans)