Problem p02616 (python)

Fixed submission:
from bisect import bisect_left,bisect_right
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
pi=1
ni=0
ans=1
i=0
while i<k-1:
  if a[ni]*a[ni+1]>a[-pi]*a[-pi-1]:
    ans=ans*a[ni]*a[ni+1]%p
    ni+=2
    i+=2
  else:
    ans=ans*a[-pi]%p
    pi+=1
    i+=1
if i==k-1:
  ans=ans*a[-pi]%p
if a[-1]<0 and k%2==1:
  ans=1
  for i in a[n-k:]:
    ans=ans*i%p
print(ans)

Buggy submission (verdict: Runtime Error):
mod = 10**9+7
N, K = map(int,input().split())
A = sorted(list(map(int,input().split())))

p = 1
n = 0
ans = 1
cnt = 0
while cnt < K-1:
  if A[n]*A[n+1] > A[-p]*A[-p-1]:
    ans = ans*A[n]*A[n+1]%mod
    n += 2
    cnt += 2
    
  else:
    ans = ans*A[-p]%mod
    p += 1
    cnt += 1
    
if i == K-1:
  ans = ans*A[-p]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*cnt%mod

print(ans)

Buggy submission (verdict: Runtime Error):
mod = 10**9+7
N, K = map(int,input().split())
A = sorted(list(map(int,input().split())))

p = 1
n = 0
ans = 1
cnt = 0
while cnt < K-1:
  if A[n]*A[n+1] > A[-p]*A[-p-1]:
    ans = ans*A[ni]*A[n+1]%mod
    n += 2
    cnt += 2
    
  else:
    ans = ans*A[-p]%mod
    p += 1
    cnt += 1
    
if i == K-1:
  ans = ans*A[-p]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*cnt%mod

print(ans)

Buggy submission (verdict: Runtime Error):
mod = 10**9+7
N, K = map(int,input().split())
A = sorted(list(map(int,input().split())))

p = 1
n = 0
ans = 1
cnt = 0
while cnt < K-1:
  if A[n]*A[n+1] > A[-p]*A[-p-1]:
    ans = ans*A[ni]*A[ni+1]%mod
    n += 2
    cnt += 2
    
  else:
    ans = ans*A[-p]%mod
    p += 1
    cnt += 1
    
if i == K-1:
  ans = ans*A[-p]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*cnt%mod

print(ans)

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans = ans*AP[p]%mod
                print(ans%mod)
                break
                
            elif 2 <= (len(AM) - m) and 2 <= (len(AP) - p):   
                if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                    ans = ans*AP[p]*AP[p+1]%mod
                    p += 2
                    cnt += 2
                
                else:
                    ans = ans*AM[m]*AM[m+1]%mod
                    m += 2
                    cnt += 2 
                    
            elif 1 >= (len(AP) - p) and 2 <= (len(AM) - m):
                ans = ans*AM[m]*AM[m+1]%mod
                m += 2
                cnt += 2 
            
            elif 2 <= (len(AP) - p) and 1 >= (len(AM) - m):
                ans = ans*AP[p]*AP[p+1]%mod
                p += 2
                cnt += 2
            
            

            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
mod = 10**9+7
N,K = map(int,input().split())

A = sorted(list(map(int,input().split())))

p = 1
m = 0
ans = 1
cnt = 0

while cnt < K-1:
  if A[m]*A[m+1] > A[-p]*A[-p-1]:
    ans*= A[ni]*A[n+1]%mod
    m += 2
    cnt += 2
    
  else:
    ans *= A[-p]%mod
    p += 1
    cnt += 1
    
if cnt == k-1:
  ans *= A[-p]%mod
  
if A[-1]<0 and K%2 == 1:
  ans = 1
  for i in A[N-K:]:
    ans*= i%mod
    
print(ans)

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        p = 0
        m = 0
        ans = 1
        cnt = 0

        while True:
            if p+1 <= len(AP) - 1 and m+1 <= len(AM) - 1 and AM[m]*AM[m+1] > AP[p]*A[p+1]:
                ans *= AM[m]*AM[m+1]%mod
                m += 2
                cnt += 2
                
            else:
                ans *= AP[p]%mod
                p += 1
                cnt += 1
            
            if K == cnt:
                break

        print(ans%mod)

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

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

A = sorted(list(map(int,input().split())))

p = 1
m = 0
ans = 1
cnt = 0

while cnt < K-1:
  if A[m]*A[m+1] > A[-p]*A[-p-1]:
    ans*= A[ni]*A[n+1]%mod
    m += 2
    cnt += 2
    
  else:
    ans *= A[-p]%mod
    p += 1
    cnt += 1
    
if cnt == k-1:
  ans=ans*a[-pi]%p
  
if a[-1]<0 and k%2==1:
  ans=1
  for i in a[n-k:]:
    ans=ans*i%p
print(ans)

from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        p = 0
        m = 0
        ans = 1
        cnt = 0

        while cnt <= K:
          if p+1 <= len(AP) and m+1 <= len(AP) and AM[m]*AM[m+1] > AP[p]*A[p+1]:
            ans*= A[m]*A[m+1]%mod
            m += 2
            cnt += 2
            
          else:
            ans *= AP[p]%mod
            p += 1
            cnt += 1

        print(ans%mod)

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[p]
                print(ans%mod)
                break
                
            elif 2 <= (len(AM) - m) and 2 <= (len(AP) - p):   
                if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                    ans *= (AP[p]*AP[p+1])%mod
                    p += 2
                    cnt += 2
                
                else:
                    ans *= (AM[m]*AM[m+1])%mod
                    m += 2
                    cnt += 2 
                    
            elif 1 >= (len(AP) - p) and 2 <= (len(AM) - m):
                ans *= (AM[m]*AM[m+1])%mod
                m += 2
                cnt += 2 
            
            elif 2 <= (len(AP) - p) and 1 >= (len(AM) - m):
                ans *= (AP[p]*AP[p+1])%mod
                p += 2
                cnt += 2
            
            

            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[p]
                print(ans%mod)
                break
                
            elif 2 <= (len(AM) - m) and 2 <= (len(AP) - p):   
                if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                    ans *= (AP[p]*AP[p+1])%mod
                    p += 2
                    cnt += 2
                
                else:
                    ans *= (AM[m]*AM[m+1])%mod
                    m += 2
                    cnt += 2 
                    
            elif 1 >= (len(AP) - p) and 2 <= (len(AM) - m):
                ans *= (AM[m]*AM[m+1])%mod
                m += 2
                cnt += 2 
            
            elif 2 <= (len(AP) - p) and 1 >= (len(AM) - m):
                ans *= (AP[p]*AP[p+1])%mod
                p += 2
                cnt += 2
            
            

            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul
import heapq

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(-abs(i)%mod)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        AP = list(map(lambda x: x*(-1), AP))
        heapq.heapify(AP)
        heapq.heapify(AM)
        
        ans = 1
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[0]
                print(ans%mod)
                break
                
            if 2 <= len(AP):
                AP2 = heapq.heappop(AP)*(-1)
                AP1 = heapq.heappop(AP)*(-1)
                

            if 2 <= len(AM):
                AM1 = heapq.heappop(AM)
                AM2 = heapq.heappop(AM)

                
            if AP1*AP2 >= AM1*AM2:
                ans *= AP1*AP2
                cnt += 2
                
            else:
                ans *= AM1*AM2
                m += 2
                cnt += 2 
                    
            if 1 >= len(AP) and 2 <= len(AM):
                ans *= AM1*AM2
                cnt += 2 
            
            if 2 <= len(AP) and 1 >= len(AM):
                ans *= AP1*AP2
                cnt += 2
            
            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul
import heapq

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(-abs(i)%mod)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        AP = list(map(lambda x: x*(-1), AP))
        heapq.heapify(AP)
        heapq.heapify(AM)
        
        ans = 1
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[0]
                print(ans%mod)
                break
                
            if 2 <= len(AM):
                AP2 = heapq.heappop(AP)*(-1)
                AP1 = heapq.heappop(AP)*(-1)
                

            if 2 <= len(AP):
                AM1 = heapq.heappop(AM)
                AM2 = heapq.heappop(AM)

                
            if AP1*AP2 >= AM1*AM2:
                ans *= AP1*AP2
                cnt += 2
                
            else:
                ans *= AM1*AM2
                m += 2
                cnt += 2 
                    
            if 1 >= len(AP) and 2 <= len(AM):
                ans *= AM1*AM2
                cnt += 2 
            
            if 2 <= len(AP) and 1 >= len(AM):
                ans *= AP1*AP2
                cnt += 2
            
            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(-abs(i)%mod)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[p]
                print(ans%mod)
                break
                
            elif 2 <= (len(AM) - m) and 2 <= (len(AP) - p):   
                if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                    ans *= (AP[p]*AP[p+1])
                    p += 2
                    cnt += 2
                
                else:
                    ans *= (AM[m]*AM[m+1])
                    m += 2
                    cnt += 2 
                    
            elif 1 >= (len(AP) - p) and 2 <= (len(AM) - m):
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 
            
            elif 2 <= (len(AP) - p) and 1 >= (len(AM) - m):
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
            
            

            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()
        
        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[p]
                print(ans%mod)
                break
                
            elif 1 >= len(AP) and 2 <= len(AM):
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 
            
            elif 2 <= len(AP) and 1 >= len(AM):
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
            
            else:   
                if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                    ans *= (AP[p]*AP[p+1])
                    p += 2
                    cnt += 2
                
                else:
                    ans *= (AM[m]*AM[m+1])
                    m += 2
                    cnt += 2 

            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()

        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[p]
                print(ans%mod)
                break
                
            if 1 == len(AP):
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 
            
            elif 1 == len(AM):
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
            else:   
                if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                    ans *= (AP[p]*AP[p+1])
                    p += 2
                    cnt += 2
                
                else:
                    ans *= (AM[m]*AM[m+1])
                    m += 2
                    cnt += 2 

            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()

        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[p]
                print(ans%mod)
                break
                
            if 1 == len(AP):
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 
            
            if 1 == len(AM):
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
                
            if AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
                
            if m+1 <= len(AM):
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 

            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()

        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[p]
                print(ans%mod)
                break
                
            if p+1 <= len(AP) and AP[p]*AP[p+1] >= AM[m]*AM[m+1]:
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
                
            if m+1 <= len(AM):
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 

            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort()
        AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()

        ans = 1
        p = 0
        m = 0
        cnt = 0
        while True:
            if (p+1 <= len(AP) and AP[p]*AP[p+1] >= AM[m]*AM[m+1]) or (K - cnt) == 1:
                ans *= (AP[p]*AP[p+1])
                p += 2
                cnt += 2
            if m+1 <= len(AM):
                ans *= (AM[m]*AM[m+1])
                m += 2
                cnt += 2 

            if cnt == K:
                print(ans%mod)
                break

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)
    
    else:
        
        AP.sort(reverse=True)
        AM.sort()

        AP = AP[:K]
        AM = AM[:K]

        P = reduce(mul, AP)
        M = 1
        ans = P
        for i in range(0, len(AM)):
            if i < len(AP): 
                M *= AM[i]
                ans = max(ans, P*M/AP[-(i+1)])

        print(int(ans%mod))

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import mul

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(i)
        else:
            AP.append(i)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        
        AP.sort(reverse=True)
        AM.sort()

        AP = AP[:K]
        AM = AM[:K]

        P = reduce(mul, AP)
        M = 1
        ans = P
        for i in range(0, len(AM)):
            if i < len(AP): 
                M *= AM[i]
                ans = max(ans, P*M/AP[-(i+1)])

        print(int(ans)%mod)