Problem p02616 (python)

Fixed submission:
N,K = map(int,input().split())
L = list(map(int,input().split()))
L = sorted(L)

MOD=10**9+7

ans=1
if N==K:
    for a in L:
        ans*=a
        ans%=MOD

#全部ふで奇数個
elif all(l<0 for l in L) and K%2==1:
    #小さい方からKこ
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))

    ans_cand=[v for v in absL[:K]]
    remain=[v for v in absL[K:]]

    if len(list(filter(lambda x:x<0,ans_cand)))%2==0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        ans_cand_min_neg = None
        ans_cand_min_pos=None
        remain_cand_max_neg=None
        remain_cand_max_pos=None

        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a

        #できるだけ絶対値が大きいやつ
        for a in remain:
            if a>=0:
                remain_cand_max_pos=a
                break

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
        for a in remain:
            if a<=0:
                remain_cand_max_neg=a
                break

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_pos*remain_cand_max_pos)
            B = abs(ans_cand_min_neg*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg


        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
            else:
                NG=None
print(ans)

Buggy submission (verdict: Runtime Error):
N,K = map(int,input().split())
L = list(map(int,input().split()))
L = sorted(L)

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))
    ans_cand=[v for v in absL[:K]]
    remain=[v for v in absL[K:]]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        #ans_candはabsの大きさでsortされている
        #できるだけ絶対ちが小さいやつ
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a
                break

        #できるだけ絶対値が大きいやつ
        remain_cand_max_pos=None
        for a in remain:
            if a>=0:
                remain_cand_max_pos=a

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる
        ans_cand_min_pos=None
        remain_cand_max_neg=None

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_neg*remain_cand_max_pos)
            B = abs(ans_cand_min_pos*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg
        else:
            assert 1==2


        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
            else:
                NG=None
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    absL = sorted(L,key=lambda x:-abs(x))
    cand=[v for v in absL[:K]]
    
    ans_cand=cand[-K:]
    remain=cand[:-K]

    ans_hugou=1
    for a in ans_cand:
        if a<0:
            ans_hugou*=-1

    if ans_hugou>=0:
        for a in ans_cand:
            ans*=a
            ans%=MOD
    else:
        assert 1==2
        #負の数をans_candから一つ取り除き、remain_candから一つ正の数を取ってくる
        ans_cand_min_neg = None
        for a in ans_cand:
            if a<0:
                ans_cand_min_neg=a

        remain_cand_max_pos=None
        for a in remain:
            if a>0:
                remain_cand_max_pos=a

        #正の数をans_candから一つ取り除いき、remain_candから負の数を一つ取ってくる
        ans_cand_min_pos=None
        remain_cand_max_neg=None

        for a in ans_cand:
            if a>0:
                ans_cand_min_pos=a
                break
        for a in remain:
            if a<0:
                remain_cand_max_neg=a
                break

        NG=None
        if not None in {ans_cand_min_pos,ans_cand_min_neg,remain_cand_max_neg,remain_cand_max_pos}:
            A = abs(ans_cand_min_neg*remain_cand_max_pos)
            B = abs(ans_cand_min_pos*remain_cand_max_neg)
            if A>=B:
                ans_cand.append(remain_cand_max_pos)
                NG=ans_cand_min_neg
            else:
                ans_cand.append(remain_cand_max_neg)
                NG=ans_cand_min_pos
        elif not None in {ans_cand_min_pos,remain_cand_max_neg}:
            ans_cand.append(remain_cand_max_neg)
            NG=ans_cand_min_pos
        elif not None in {ans_cand_min_neg,remain_cand_max_pos}:
            ans_cand.append(remain_cand_max_pos)
            NG=ans_cand_min_neg

        for a in ans_cand:
            if a!=NG:
                ans*=a
                ans%=MOD
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
            ans%=MOD
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    cand=[]
    poss=[]
    negs=[]
    replace=[]
    if K%2==1:#奇数個
        K-=1
        cand.append(L[-1])
        for l in L[:-1]:
            if l>0:
                heapq.heappush(poss,-l)
            else:
                heapq.heappush(negs,l)

    added = len(cand)
    while len(added)<K:
        if len(poss)>=2 and len(negs)>=2:
            pa = -heapq.heappop(poss)
            pb = -heapq.heappop(poss)

            na = heapq.heappop(negs)
            nb = heapq.heappop(negs)
            if pa*pb>na*nb:
                cand.append(pa*pb)
                added+=2
            else:
                cand.append(na*nb)
                added+=2
        elif len(poss)>=2:
            pa = -heapq.heappop(poss)
            pb = -heapq.heappop(poss)
            cand.append(pa*pb)
            added+=2
        if len(negs)>=2:
            na = heapq.heappop(negs)
            nb = heapq.heappop(negs)
            cand.append(na*nb)
            added+=2
        for c in cand:
            ans*=c
            ans%=MOD
print(ans%MOD)

Buggy submission (verdict: Runtime Error):
import heapq

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

MOD=10**9+7

ans=1
if L[-1]<=0:#全部負
    if K%2==1:
        #小さい方からKこ
        for l in L[-K:]:
            ans*=l
            ans%=MOD
    else:
        #大きい方からKこ
        for l in L[:K]:
            ans*=l
elif L[0]>=0:#全部生
    for l in L[-K:]:
        ans*=l
        ans%=MOD
else:#生徒ふが入り混じり
    cand=[]
    if K%2==1:#奇数個
        K-=1
        cand.append(L[-1])
        L=L[:-1]
    #N-1こ(偶数を選んでから)追加で、正の(一番大きいやつを取っておく?)怪しい
    poss=[]
    negs=[]
    replace=[]
    for l in L:
        if l<0:
            heapq.heappush(poss,l)
            if len(poss)>K:
                heapq.heappop(poss)#正の数でK番目より小さいやつは捨てる
        else:
            heapq.heappush(negs,l)
    while len(negs)>=2:
        a = heapq.heappop(negs)
        b = heapq.heappop(negs)
        replace.append(a*b)

    assert 1==2
    #posとnegから選んでいく

print(ans)