Problem p02616 (python)

Fixed submission:
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N or N == K:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevpos = None
    prevneg = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if ans != 0 and not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and (nextneg is None or nextpos is None):
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N or N == K:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if ans != 0 and not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if ans != 0 and not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextneg = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N:
        ans = 1
        A.sort(reverse=True)
        for i in range(K):
            ans = (ans * A[i]) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    for i in range(K):
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextpos = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a >= 0:
            heappush(q, [-a, "p"])
    if K % 2 == 1 and numneg == N:
        ans = 1
        neg = []
        while len(q):
            num, _ = heappop(q)
            neg.append(num)
        for i in range(K):
            num = neg[-i-1]
            ans = (ans * num) % MOD
        print(ans)
        return
    ans = 1
    is_positive = True
    prevneg = None
    prevpos = None
    while K:
        num, posneg = heappop(q)
        ans = (ans * -num) % MOD
        K -= 1
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if not is_positive:
        nextpos = None
        nextneg = None
        while len(q) and nextneg is None and nextpos is None:
            num, posneg = heappop(q)
            if posneg == "p" and nextpos is None:
                nextpos = num
            elif posneg == "n" and nextneg is None:
                nextpos = num
        # nextneg / prevpos < nextpos / prevneg
        if prevpos is None or nextneg is None:
            ans = div(ans * nextpos, prevneg)
        elif prevneg is None or nextpos is None:
            ans = div(ans * nextneg, prevpos)
        else:
            if nextneg * prevneg < nextpos * prevpos:
                ans = div(ans * nextpos, prevneg)
            else:
                ans = div(ans * nextneg, prevpos)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    q = []
    numpos = 0
    numneg = 0
    for a in A:
        if a < 0:
            heappush(q, [a, "n"])
            numneg += 1
        elif a > 0:
            heappush(q, [-a, "p"])
            numpos += 1
    numzero = N - numneg - numpos
    if numpos + numneg < K:
        print(0)
        return
    if K % 2 == 1 and numneg == N:
        ans = 1
        neg = []
        while len(q):
            num, _ = heappop(q)
            neg.append(num)
        for i in range(K):
            num = neg[-i-1]
            ans = (ans * num) % MOD
        print(ans)
        return
    elif K % 2 == 1 and numpos == 0:
        print(0)
        return
    ans = 1
    is_positive = True
    prevneg = 0
    prevpos = 0
    poshistory = []
    neghistory = []
    while K and len(q):
        num, posneg = heappop(q)
        if K == 1:
            if not is_positive:
                if posneg == "p" and len(poshistory) < 2:
                    poshistory.append(-num)
                elif posneg == "n":
                    if len(poshistory) == 2 and prevneg * -num < poshistory[0] * poshistory[1]:
                        ans = div(ans * poshistory[0] * poshistory[1], prevneg)
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
            if is_positive:
                if posneg == "n" and len(neghistory) < 2:
                    neghistory.append(-num)
                elif posneg == "p":
                    if len(neghistory) == 2 and prevpos * -num < neghistory[0] * neghistory[1]:
                        ans = div(ans * neghistory[0] * neghistory[1], prevpos)
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
            continue
        ans = (ans * -num) % MOD
        K -= 1
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = num
    if K != 0:
        if is_positive:
            ans = (ans * neghistory[0] * neghistory[1]) % MOD
        else:
            ans = (ans * poshistory[0] * poshistory[1]) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    pos = []
    neg = []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a > 0:
            pos.append(a)
    numzero = N - len(neg) - len(pos)
    if len(pos) + len(neg) < K:
        print(0)
        return
    if K % 2 == 1 and len(neg) == N:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD
        print(ans)
        return
    elif K % 2 == 1 and len(pos) == 0:
        print(0)
        return
    q = []
    for i in range(len(pos)):
        heappush(q, [-pos[i], "p"])
    for i in range(len(neg)):
        heappush(q, [neg[i], "n"])
    ans = 1
    is_positive = True
    prevneg = 0
    prevpos = 0
    poshistory = []
    neghistory = []
    while K and len(q):
        num, posneg = heappop(q)
        if K == 1:
            if not is_positive:
                if posneg == "p" and len(poshistory) < 2:
                    poshistory.append(-num)
                elif posneg == "n":
                    if len(poshistory) == 2 and prevneg * -num < poshistory[0] * poshistory[1]:
                        ans = div(ans * poshistory[0] * poshistory[1], prevneg)
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
            if is_positive:
                if posneg == "n" and len(neghistory) < 2:
                    neghistory.append(-num)
                elif posneg == "p":
                    if len(neghistory) == 2 and prevpos * -num < neghistory[0] * neghistory[1]:
                        ans = div(ans * neghistory[0] * neghistory[1], prevpos)
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
            continue
        ans = (ans * -num) % MOD
        K -= 1
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = pos
    if K != 0:
        if is_positive:
            ans = (ans * neghistory[0] * neghistory[1]) % MOD
        else:
            ans = (ans * poshistory[0] * poshistory[1]) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush

MOD = int(1e9+7)


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    pos = []
    neg = []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a > 0:
            pos.append(a)
    numzero = N - len(neg) - len(pos)
    if len(pos) + len(neg) < K:
        print(0)
        return
    if K % 2 == 1 and len(neg) == N:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD
        print(ans)
        return
    elif K % 2 == 1 and len(pos) == 0:
        print(0)
        return
    q = []
    for i in range(len(pos)):
        heappush(q, [-pos[i], "p"])
    for i in range(len(neg)):
        heappush(q, [neg[i], "n"])
    ans = 1
    is_positive = True
    prevneg = 0
    prevpos = 0
    poshistory = []
    neghistory = []
    while K and len(q):
        num, posneg = heappop(q)
        if K == 1:
            if not is_positive:
                if posneg == "p" and len(poshistory) < 2:
                    poshistory.append(-num)
                elif posneg == "n":
                    if len(poshistory) == 2 and prevneg * -num < poshistory[0] * poshistory[1]:
                        ans = (ans * poshistory[0] * poshistory[1]) % MOD
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
                continue
            if is_positive:
                if posneg == "n" and len(neghistory) < 2:
                    neghistory.append(-num)
                elif posneg == "p":
                    if len(neghistory) == 2 and prevpos * -num < neghistory[0] * neghistory[1]:
                        ans = (ans * neghistory[0] * neghistory[1]) % MOD
                    else:
                        ans = (ans * -num) % MOD
                    print(ans)
                    return
                continue
        ans = (ans * -num) % MOD
        K -= 1
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
        else:
            prevpos = pos
    if K != 0:
        if is_positive:
            ans = (ans * neghistory[0] * neghistory[1]) % MOD
        else:
            ans = (ans * poshistory[0] * poshistory[1]) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush

MOD = int(1e9+7)


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    pos = []
    neg = []
    for a in A:
        if a < 0:
            neg.append(a)
        elif a > 0:
            pos.append(a)
    numzero = N - len(neg) - len(pos)
    if len(pos) + len(neg) < K:
        print(0)
        return
    if K % 2 == 1 and len(neg) == N:
        neg.sort(reverse=True)
        ans = 1
        for i in range(K):
            ans = (ans * neg[i]) % MOD
        print(ans)
        return
    elif K % 2 == 1 and len(pos) == 0:
        print(0)
        return
    q = []
    for i in range(len(pos)):
        heappush(q, [-pos[i], "p"])
    for i in range(len(neg)):
        heappush(q, [neg[i], "n"])
    ans = 1
    is_positive = True
    prevneg = 0
    poshistory = []
    while K and len(q):
        num, posneg = heappop(q)
        if K == 1 and not is_positive:
            if posneg == "p" and len(poshistory) < 2:
                poshistory.append(-num)
            elif posneg == "n":
                if len(poshistory) == 2 and prevneg * num < poshistory[0] * poshistory[1]:
                    ans = (ans * poshistory[0] * poshistory[1]) % MOD
                else:
                    ans = (ans * -num) % MOD
                print(ans)
                return
            continue
        ans = (ans * -num) % MOD
        K -= 1
        if posneg == "n":
            is_positive = not is_positive
            prevneg = num
    if K != 0:
        ans = (ans * poshistory[0] * poshistory[1]) % MOD
    print(ans)


if __name__ == "__main__":
    main()