Problem p02616 (python)

Fixed submission:
def sgn(x):
    if x>0:
        return 1
    elif x<0:
        return -1
    else:
        return 0
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
mod=10**9+7
if K==N:
    ans=1
    for i in range(N):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if max(A)<0 and K%2==1:
    ans=1
    A.sort()
    for i in range(K):
        ans=ans*A[-i-1]
        ans%=mod
    print(ans)
    exit()
A.sort(key=lambda x:abs(x),reverse=True)
P=1
Pfugou=1
for i in range(K):
    P=P*A[i]
    P%=mod
    Pfugou=Pfugou*sgn(A[i])
if Pfugou!=-1:
    print(P)
    exit()
X=[]
Y=[]
for i in range(N):
    if A[i]>=0:
        X.append(A[i])
    else:
        Y.append(-A[i])
X.sort()
Y.sort()
S=[]
while(len(S)<K):
    if len(S)==K-1:
        S.append(X[-1])
        X.pop()
    elif len(X)<=1 and len(Y)<=1:
        #選んでないのが2個以下
        #len(S)<K<=N-1
        #len(S)=N-len(X)-len(Y)>=N-2
        #よってlen(S)=N-2,K=N-1
        #前述で処理済み
        #なのでここでやることはない
        pass
    elif len(X)<=1:
        S.append(Y[-1])
        S.append(Y[-2])
        Y.pop()
        Y.pop()
    elif len(Y)<=1:
        S.append(X[-1])
        S.append(X[-2])
        X.pop()
        X.pop()
    else:
        if X[-1]*X[-2]>Y[-1]*Y[-2]:
            S.append(X[-1])
            X.pop()
        else:
            S.append(Y[-1])
            S.append(Y[-2])
            Y.pop()
            Y.pop()
ans=1
for i in S:
    ans=ans*i
    ans%=mod
print(ans)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())
mod=10**9+7
A=list(map(int,input().split()))
A.sort(reverse=True)
Plus=[]
Minus=[]
Zero=[]
for i in range(N):
    if A[i]>0:
        Plus.append(A[i])
    elif A[i]<0:
        Minus.append(-A[i])
    else:
        Zero.append(A[i])
Plus.sort(reverse=True)
Minus.sort(reverse=True)
if K==N:
    ans=1
    for i in range(K):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if len(Plus)==0:
    if len(Zero)==0:
        if K%2==0:
            ans=1
            for i in range(K):
                ans=ans*Minus[i]
                ans%=mod
            print(ans)
        else:
            ans=1
            for i in range(K):
                ans=ans*Minus[-i-1]
                ans%=mod
            print((-ans)%mod)
    else:
        if len(Minus)>=K:
            if K%2==0:
                ans=1
                for i in range(K):
                    ans=ans*Minus[i]
                    ans%=mod
                print(ans)
            else:
                print(0)
        else:
            print(0)
    exit()
if len(Minus)==0:
    ans=1
    for i in range(K):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if len(Zero)>N-K:
    print(0)
    exit()
if len(Zero)+K==N:
    if len(Minus)%2==0:
        ans=1
        for i in range(N):
            if A[i]!=0:
                ans=ans*abs(A[i])
                ans%=mod
        print(ans)
    else:
        print(0)
    exit()
n=len(Plus)
m=len(Minus)
'''
+:x0,...,x(n-1)
-:y0,...,y(m-1)

x0*...x(K-l-1)*y0*...y(l-1)
yl*y(l+1)/x(K-l-1)*x(K-l-2)
これはlについて単調減少
<1となるはじめてのタイミングでbreak
'''
l=K-n
if l%2==1:
    l+=1
x=l
while(l<=m and l<=K):
    if (l+2)<=min(m,K):
        if Minus[l]*Minus[l+1]>=Plus[K-l-1]*Plus[K-l-2]:
            x=l+2
    l+=2
ans=1
for i in range(x):
    ans=ans*Minus[i]
    ans%=mod
for i in range(K-x):
    ans=ans*Plus[i]
    ans%=mod
print(ans)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())
mod=10**9+7
A=list(map(int,input().split()))
A.sort(reverse=True)
Plus=[]
Minus=[]
Zero=[]
for i in range(N):
    if A[i]>0:
        Plus.append(A[i])
    elif A[i]<0:
        Minus.append(-A[i])
    else:
        Zero.append(A[i])
Plus.sort(reverse=True)
Minus.sort(reverse=True)
if K==N:
    ans=1
    for i in range(N):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if len(Plus)==0:
    if len(Zero)==0:
        if K%2==0:
            ans=1
            for i in range(K):
                ans=ans*Minus[i]
                ans%=mod
            print(ans)
        else:
            ans=1
            for i in range(K):
                ans=ans*Minus[-i-1]
                ans%=mod
            print((-ans)%mod)
    else:
        if len(Minus)>=K:
            if K%2==0:
                ans=1
                for i in range(K):
                    ans=ans*Minus[i]
                    ans%=mod
                print(ans)
            else:
                print(0)
        else:
            print(0)
    exit()
if len(Minus)==0:
    ans=1
    for i in range(K):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if len(Zero)>N-K:
    print(0)
    exit()
if len(Zero)+K==N:
    if len(Minus)%2==0:
        ans=1
        for i in range(N):
            if A[i]!=0:
                ans=ans*abs(A[i])
                ans%=mod
        print(ans)
    else:
        print(0)
    exit()
n=len(Plus)
m=len(Minus)
'''
+:x0,...,x(n-1)
-:y0,...,y(m-1)

x0*...x(K-l-1)*y0*...y(l-1)
yl*y(l+1)/x(K-l-1)*x(K-l-2)
これはlについて単調減少
<1となるはじめてのタイミングでbreak
'''
l=K-n
if l%2==1:
    l+=1
x=l
while(l<=m and l<=K):
    if (l+2)<=min(m,K) and Minus[l]*Minus[l+1]>=Plus[K-l-1]*Plus[K-l-2]:
        x=l+2
    l+=2
ans=1
for i in range(x):
    ans=ans*Minus[i]
    ans%=mod
for i in range(K-x):
    ans=ans*Plus[i]
    ans%=mod
print(ans)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())
mod=10**9+7
A=list(map(int,input().split()))
A.sort(reverse=True)
Plus=[]
Minus=[]
Zero=[]
for i in range(N):
    if A[i]>0:
        Plus.append(A[i])
    elif A[i]<0:
        Minus.append(-A[i])
    else:
        Zero.append(A[i])
Plus.sort(reverse=True)
Minus.sort(reverse=True)
if K==N:
    ans=1
    for i in range(N):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if len(Plus)==0:
    if len(Zero)==0:
        if K%2==0:
            ans=1
            for i in range(K):
                ans=ans*Minus[i]
                ans%=mod
            print(ans)
        else:
            ans=1
            for i in range(K):
                ans=ans*Minus[-i-1]
                ans%=mod
            print((-ans)%mod)
    else:
        if len(Minus)<=K:
            if K%2==0:
                ans=1
                for i in range(K):
                    ans=ans*Minus[i]
                    ans%=mod
                print(ans)
            else:
                print(0)
        else:
            print(0)
    exit()
if len(Minus)==0:
    ans=1
    for i in range(K):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if len(Zero)>N-K:
    print(0)
    exit()
if len(Zero)+K==N:
    if len(Minus)%2==0:
        ans=1
        for i in range(N):
            if A[i]!=0:
                ans=ans*abs(A[i])
                ans%=mod
        print(ans)
    else:
        print(0)
    exit()
n=len(Plus)
m=len(Minus)
'''
+:x0,...,x(n-1)
-:y0,...,y(m-1)

x0*...x(K-l-1)*y0*...y(l-1)
yl*y(l+1)/x(K-l-1)*x(K-l-2)
これはlについて単調減少
<1となるはじめてのタイミングでbreak
'''
l=K-n
if l%2==1:
    l+=1
x=l
while(l<=m and l<=K):
    if (l+2)<=min(m,K) and Minus[l]*Minus[l+1]>=Plus[K-l-1]*Plus[K-l-2]:
        x=l+2
    l+=2
ans=1
for i in range(x):
    ans=ans*Minus[i]
    ans%=mod
for i in range(K-x):
    ans=ans*Plus[i]
    ans%=mod
print(ans)

Buggy submission (verdict: Runtime Error):
N,K=map(int,input().split())
mod=10**9+7
A=list(map(int,input().split()))
A.sort(reverse=True)
Plus=[]
Minus=[]
Zero=[]
for i in range(N):
    if A[i]>0:
        Plus.append(A[i])
    elif A[i]<0:
        Minus.append(-A[i])
    else:
        Zero.append(A[i])
Plus.sort(reverse=True)
Minus.sort(reverse=True)
if len(Plus)==0:
    if len(Zero)==0:
        if K%2==0:
            ans=1
            for i in range(K):
                ans=ans*Minus[i]
                ans%=mod
            print(ans)
        else:
            ans=1
            for i in range(K):
                ans=ans*Minus[-i-1]
                ans%=mod
            print((-ans)%mod)
    else:
        if len(Minus)<=K:
            if K%2==0:
                ans=1
                for i in range(K):
                    ans=ans*Minus[i]
                    ans%=mod
                print(ans)
            else:
                print(0)
        else:
            print(0)
    exit()
if len(Minus)==0:
    ans=1
    for i in range(K):
        ans=ans*A[i]
        ans%=mod
    print(ans)
    exit()
if len(Zero)>N-K:
    print(0)
    exit()
if len(Zero)+K==N:
    if len(Minus)%2==0:
        ans=1
        for i in range(N):
            if A[i]!=0:
                ans=ans*abs(A[i])
                ans%=mod
        print(ans)
    else:
        print(0)
    exit()
n=len(Plus)
m=len(Minus)
'''
+:x0,...,x(n-1)
-:y0,...,y(m-1)

x0*...x(K-l-1)*y0*...y(l-1)
yl*y(l+1)/x(K-l-1)*x(K-l-2)
これはlについて単調減少
<1となるはじめてのタイミングでbreak
'''
l=0
while(l+2<=n and l+2<=K):
    if Minus[l]*Minus[l+1]<Plus[K-l-1]*Plus[K-l-2]:
        break
    l+=2
ans=1
for i in range(l):
    ans=ans*Minus[i]
    ans%=mod
for i in range(K-l):
    ans=ans*Plus[i]
    ans%=mod
print(ans)