Problem p03141 (python)

Fixed submission:
def cheat_solve(N, ABs):
    Ds = sorted([ab[0] + ab[1] for ab in ABs], reverse=True)
    bsum = sum([ab[1] for ab in ABs])
    dsum = sum(Ds[::2])
    return dsum - bsum

if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(cheat_solve(N, ABs))

Buggy submission (verdict: Runtime Error):
import heapq

def solve(N, ABs):
    # print(N, ",", ABs)
    K = 10 ** 9
    taken = {i: False for i in range(N)}
    As = [(K - ab[0], K - ab[1], i) for i, ab in enumerate(ABs)]
    Bs = [(K - ab[1], K - ab[0], i) for i, ab in enumerate(ABs)]
    heapq.heapify(As)
    heapq.heapify(Bs)
    ans = 0
    taken_count = 0
    while True:
        if taken_count >= N:
            break
        if not len(As):
            break
        am = heapq.heappop(As)
        while taken[am[2]]:
            am = heapq.heappop(As)

        if not len(Bs):
            ans += (K - am[0])
            break

        bm = heapq.heappop(Bs)
        while taken[bm[2]]:
            bm = heapq.heappop(Bs)
        if am[2] == bm[2]:
            ans += (K - am[0])
            taken[am[2]] = True
            taken_count += 1
            if taken_count < N:
                bm = heapq.heappop(Bs)
                while taken[bm[2]]:
                    bm = heapq.heappop(Bs)
                ans -= (K - bm[0])
                taken[bm[2]] = True
                taken_count += 1
        elif am[0] < bm[0]:
            ans += (K - am[0])
            ans -= (K - bm[0])
            taken[am[2]] = True
            taken[bm[2]] = True
            taken_count += 2
        elif am[0] > bm[0]:
            ans += (K - bm[0])
            ans -= (K - am[0])
            taken[am[2]] = True
            taken[bm[2]] = True
            taken_count += 2

    return ans

if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABs))

Buggy submission (verdict: Runtime Error):
import heapq

def solve(N, ABs):
    # print(N, ",", ABs)
    K = 10 ** 9
    taken = {i: False for i in range(N)}
    As = [(K - ab[0], K - ab[1], i) for i, ab in enumerate(ABs)]
    Bs = [(K - ab[1], K - ab[0], i) for i, ab in enumerate(ABs)]
    heapq.heapify(As)
    heapq.heapify(Bs)
    ans = 0
    taken_count = 0
    while True:
        if taken_count >= N:
            break
        if not len(As):
            break
        am = heapq.heappop(As)
        while taken[am[2]]:
            am = heapq.heappop(As)

        if not len(Bs):
            ans += (K - am[0])
            break

        bm = heapq.heappop(Bs)
        while taken[bm[2]]:
            bm = heapq.heappop(Bs)
        if am[2] == bm[2]:
            ans += (K - am[0])
            taken[am[2]] = True
            taken_count += 1
            if taken_count < N:
                bm = heapq.heappop(Bs)
                while taken[bm[2]]:
                    bm = heapq.heappop(Bs)
                ans -= (K - bm[0])
                taken[bm[2]] = True
                taken_count += 1
        elif am[0] > bm[0]:
            ans += (K - am[0])
            ans -= (K - bm[0])
            taken[am[2]] = True
            taken[bm[2]] = True
            taken_count += 2
        elif am[0] < bm[0]:
            ans += (K - bm[0])
            ans -= (K - am[0])
            taken[am[2]] = True
            taken[bm[2]] = True
            taken_count += 2

    return ans

if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABs))

Buggy submission (verdict: Runtime Error):
import heapq


def solve(N, ABs):
    # print(N, ",", ABs)
    taken = {i: False for i in range(N)}
    As = [(ab[0], ab[1], i) for i, ab in enumerate(ABs)]
    Bs = [(ab[1], ab[0], i) for i, ab in enumerate(ABs)]
    heapq.heapify(As)
    heapq.heapify(Bs)
    ans = 0
    taken_count = 0
    while True:
        if taken_count >= N:
            break
        if not len(As):
            break
        am = As.pop(len(As) - 1)
        while taken[am[2]]:
            am = As.pop(len(As) - 1)

        if not len(Bs):
            ans += am[2]
            break

        bm = Bs.pop(len(Bs) - 1)
        while taken[bm[2]]:
            bm = Bs.pop(len(Bs) - 1)
        if am[2] == bm[2]:
            ans += am[0]
            taken[am[2]] = True
            taken_count += 1
            if len(Bs):
                bm = Bs.pop(len(Bs) - 1)
                while taken[bm[2]]:
                    bm = Bs.pop(len(Bs) - 1)
                ans -= bm[0]
                taken[bm[2]] = True
                taken_count += 1
        elif am[0] > bm[0]:
            ans += am[0]
            ans -= bm[0]
            taken[am[2]] = True
            taken[bm[2]] = True
            taken_count += 2
        elif am[0] < bm[0]:
            ans += bm[0]
            ans -= am[0]
            taken[am[2]] = True
            taken[bm[2]] = True
            taken_count += 2

    return ans

if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABs))

Buggy submission (verdict: Runtime Error):
import heapq


def solve(N, ABs):
    # print(N, ",", ABs)
    taken = {i: False for i in range(N)}
    As = [(ab[0], i) for i, ab in enumerate(ABs)]
    Bs = [(ab[1], i) for i, ab in enumerate(ABs)]
    heapq.heapify(As)
    heapq.heapify(Bs)
    ans = 0
    taken_count = 0
    for _ in range(N // 2 + 1):
        if taken_count >= N:
            break
        if not len(As):
            break
        am = As.pop(len(As) - 1)
        while taken[am[1]]:
            am = As.pop(len(As) - 1)

        if not len(Bs):
            ans += am[1]
            break

        bm = Bs.pop(len(Bs) - 1)
        while taken[bm[1]]:
            bm = Bs.pop(len(Bs) - 1)
        if am[1] == bm[1]:
            ans += am[0]
            taken[am[1]] = True
            taken_count += 1
            if len(Bs):
                bm = Bs.pop(len(Bs) - 1)
                while taken[bm[1]]:
                    bm = Bs.pop(len(Bs) - 1)
                ans -= bm[0]
                taken[bm[1]] = True
                taken_count += 1
        elif am[0] > bm[0]:
            ans += am[0]
            ans -= bm[0]
            taken[am[1]] = True
            taken[bm[1]] = True
            taken_count += 2
        elif am[0] < bm[0]:
            ans += bm[0]
            ans -= am[0]
            taken[am[1]] = True
            taken[bm[1]] = True
            taken_count += 2

    return ans


if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABs))