broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(pages, events):
    pages = {p: dict(v) for p, v in pages.items()}
    epoch = 0
    unswept = []
    log = []
    def sweep(p):
        parity = epoch % 2
        dead = sorted(o for o, m in pages[p].items() if m != parity)
        for o in dead:
            del pages[p][o]
        log.append([p, dead])
        unswept.remove(p)
    for ev in events:
        if ev[0] == 'gc':
            while unswept:
                sweep(unswept[0])
            epoch += 1
            for p in pages:
                for o in pages[p]:
                    if o in ev[1]:
                        pages[p][o] = epoch % 2
            unswept = sorted(pages)
        elif ev[0] == 'alloc':
            if ev[2] in unswept:
                sweep(ev[2])
            pages[ev[2]][ev[1]] = 0
        else:
            while unswept:
                sweep(unswept[0])
    return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
  ('second cycle with an unswept page',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
   {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
  ('three cycles',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
   {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
    'pages': {'1': [], '2': ['d1']}}),
  ('control: everything live',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
  ('second cycle with an unswept page',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
   {'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
  ('three cycles',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
   {'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
    'pages': {'1': [], '2': ['d2']}}),
  ('control: everything live',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
  ('second cycle with an unswept page',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
   {'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
  ('three cycles',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
   {'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
    'pages': {'1': [], '2': ['d3']}}),
  ('control: everything live',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
  ('second cycle with an unswept page',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
   {'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
  ('three cycles',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
   {'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
    'pages': {'1': [], '2': ['d4']}}),
  ('control: everything live',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
  ('second cycle with an unswept page',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
   {'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
  ('three cycles',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
   {'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
    'pages': {'1': [], '2': ['d5']}}),
  ('control: everything live',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(pages, events):
    pages = {p: dict(v) for p, v in pages.items()}
    epoch = 0
    unswept = []
    log = []
    def sweep(p):
        parity = epoch % 2
        dead = sorted(o for o, m in pages[p].items() if m != parity)
        for o in dead:
            del pages[p][o]
        log.append([p, dead])
        unswept.remove(p)
    for ev in events:
        if ev[0] == 'gc':
            while unswept:
                sweep(unswept[0])
            epoch += 1
            for p in pages:
                for o in pages[p]:
                    if o in ev[1]:
                        pages[p][o] = epoch % 2
            unswept = sorted(pages)
        elif ev[0] == 'alloc':
            if ev[2] in unswept:
                sweep(ev[2])
            pages[ev[2]][ev[1]] = (epoch + 1) % 2
        else:
            while unswept:
                sweep(unswept[0])
    return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
  ('second cycle with an unswept page',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
   {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
  ('three cycles',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
   {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
    'pages': {'1': [], '2': ['d1']}}),
  ('control: everything live',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
  ('second cycle with an unswept page',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
   {'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
  ('three cycles',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
   {'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
    'pages': {'1': [], '2': ['d2']}}),
  ('control: everything live',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
  ('second cycle with an unswept page',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
   {'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
  ('three cycles',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
   {'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
    'pages': {'1': [], '2': ['d3']}}),
  ('control: everything live',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
  ('second cycle with an unswept page',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
   {'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
  ('three cycles',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
   {'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
    'pages': {'1': [], '2': ['d4']}}),
  ('control: everything live',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
  ('second cycle with an unswept page',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
   {'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
  ('three cycles',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
   {'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
    'pages': {'1': [], '2': ['d5']}}),
  ('control: everything live',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Objects allocated in odd epochs look dead to the current cycle and alive to the next one.

Mark bits flip meaning every cycle: an object is live when its mark equals epoch % 2. Initially every object has mark 0 at epoch 0. gc live_ids: finish sweeping every unswept page, advance the epoch, set the mark of each listed live object to the new parity, and mark all pages unswept. alloc id page: sweep the page first if it is unswept, then create the object with the current parity. finish sweeps the remaining pages. Sweeping a page removes objects whose mark differs from the current parity and logs [page, removed]. Return the sweep log and surviving objects per page.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(pages, events):
    pages = {p: dict(v) for p, v in pages.items()}
    epoch = 0
    unswept = []
    log = []
    def sweep(p):
        parity = epoch % 2
        dead = sorted(o for o, m in pages[p].items() if m != parity)
        for o in dead:
            del pages[p][o]
        log.append([p, dead])
        unswept.remove(p)
    for ev in events:
        if ev[0] == 'gc':
            while unswept:
                sweep(unswept[0])
            epoch += 1
            for p in pages:
                for o in pages[p]:
                    if o in ev[1]:
                        pages[p][o] = (epoch - 1) % 2
            unswept = sorted(pages)
        elif ev[0] == 'alloc':
            if ev[2] in unswept:
                sweep(ev[2])
            pages[ev[2]][ev[1]] = epoch % 2
        else:
            while unswept:
                sweep(unswept[0])
    return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
  ('second cycle with an unswept page',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
   {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
  ('three cycles',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
   {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
    'pages': {'1': [], '2': ['d1']}}),
  ('control: everything live',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
  ('second cycle with an unswept page',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
   {'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
  ('three cycles',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
   {'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
    'pages': {'1': [], '2': ['d2']}}),
  ('control: everything live',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
  ('second cycle with an unswept page',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
   {'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
  ('three cycles',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
   {'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
    'pages': {'1': [], '2': ['d3']}}),
  ('control: everything live',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
  ('second cycle with an unswept page',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
   {'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
  ('three cycles',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
   {'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
    'pages': {'1': [], '2': ['d4']}}),
  ('control: everything live',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
  ('second cycle with an unswept page',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
   {'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
  ('three cycles',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
   {'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
    'pages': {'1': [], '2': ['d5']}}),
  ('control: everything live',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(pages, events):
    pages = {p: dict(v) for p, v in pages.items()}
    epoch = 0
    unswept = []
    log = []
    def sweep(p):
        parity = epoch % 2
        dead = sorted(o for o, m in pages[p].items() if m != parity)
        for o in dead:
            del pages[p][o]
        log.append([p, dead])
        unswept.remove(p)
    for ev in events:
        if ev[0] == 'gc':
            while unswept:
                sweep(unswept[0])
            epoch += 1
            for p in pages:
                for o in pages[p]:
                    if o in ev[1]:
                        pages[p][o] = 1
            unswept = sorted(pages)
        elif ev[0] == 'alloc':
            if ev[2] in unswept:
                sweep(ev[2])
            pages[ev[2]][ev[1]] = epoch % 2
        else:
            while unswept:
                sweep(unswept[0])
    return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
  ('second cycle with an unswept page',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
   {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
  ('three cycles',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
   {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
    'pages': {'1': [], '2': ['d1']}}),
  ('control: everything live',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
  ('second cycle with an unswept page',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
   {'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
  ('three cycles',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
   {'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
    'pages': {'1': [], '2': ['d2']}}),
  ('control: everything live',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
  ('second cycle with an unswept page',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
   {'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
  ('three cycles',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
   {'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
    'pages': {'1': [], '2': ['d3']}}),
  ('control: everything live',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
  ('second cycle with an unswept page',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
   {'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
  ('three cycles',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
   {'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
    'pages': {'1': [], '2': ['d4']}}),
  ('control: everything live',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
  ('second cycle with an unswept page',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
   {'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
  ('three cycles',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
   {'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
    'pages': {'1': [], '2': ['d5']}}),
  ('control: everything live',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Every object reported live is swept as dead.

Mark bits flip meaning every cycle: an object is live when its mark equals epoch % 2. Initially every object has mark 0 at epoch 0. gc live_ids: finish sweeping every unswept page, advance the epoch, set the mark of each listed live object to the new parity, and mark all pages unswept. alloc id page: sweep the page first if it is unswept, then create the object with the current parity. finish sweeps the remaining pages. Sweeping a page removes objects whose mark differs from the current parity and logs [page, removed]. Return the sweep log and surviving objects per page.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(pages, events):
    pages = {p: dict(v) for p, v in pages.items()}
    epoch = 0
    unswept = []
    log = []
    def sweep(p):
        parity = epoch % 2
        dead = sorted(o for o, m in pages[p].items() if m == 0)
        for o in dead:
            del pages[p][o]
        log.append([p, dead])
        unswept.remove(p)
    for ev in events:
        if ev[0] == 'gc':
            while unswept:
                sweep(unswept[0])
            epoch += 1
            for p in pages:
                for o in pages[p]:
                    if o in ev[1]:
                        pages[p][o] = epoch % 2
            unswept = sorted(pages)
        elif ev[0] == 'alloc':
            if ev[2] in unswept:
                sweep(ev[2])
            pages[ev[2]][ev[1]] = epoch % 2
        else:
            while unswept:
                sweep(unswept[0])
    return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
  ('second cycle with an unswept page',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
   {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
  ('three cycles',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
   {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
    'pages': {'1': [], '2': ['d1']}}),
  ('control: everything live',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
  ('second cycle with an unswept page',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
   {'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
  ('three cycles',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
   {'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
    'pages': {'1': [], '2': ['d2']}}),
  ('control: everything live',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
  ('second cycle with an unswept page',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
   {'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
  ('three cycles',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
   {'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
    'pages': {'1': [], '2': ['d3']}}),
  ('control: everything live',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
  ('second cycle with an unswept page',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
   {'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
  ('three cycles',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
   {'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
    'pages': {'1': [], '2': ['d4']}}),
  ('control: everything live',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
  ('second cycle with an unswept page',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
   {'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
  ('three cycles',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
   {'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
    'pages': {'1': [], '2': ['d5']}}),
  ('control: everything live',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(pages, events):
    pages = {p: dict(v) for p, v in pages.items()}
    epoch = 0
    unswept = []
    log = []
    def sweep(p):
        parity = epoch % 2
        dead = sorted(o for o, m in pages[p].items() if m < parity)
        for o in dead:
            del pages[p][o]
        log.append([p, dead])
        unswept.remove(p)
    for ev in events:
        if ev[0] == 'gc':
            while unswept:
                sweep(unswept[0])
            epoch += 1
            for p in pages:
                for o in pages[p]:
                    if o in ev[1]:
                        pages[p][o] = epoch % 2
            unswept = sorted(pages)
        elif ev[0] == 'alloc':
            if ev[2] in unswept:
                sweep(ev[2])
            pages[ev[2]][ev[1]] = epoch % 2
        else:
            while unswept:
                sweep(unswept[0])
    return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
  ('second cycle with an unswept page',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
   {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
  ('three cycles',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
   {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
    'pages': {'1': [], '2': ['d1']}}),
  ('control: everything live',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
  ('second cycle with an unswept page',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
   {'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
  ('three cycles',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
   {'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
    'pages': {'1': [], '2': ['d2']}}),
  ('control: everything live',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
  ('second cycle with an unswept page',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
   {'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
  ('three cycles',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
   {'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
    'pages': {'1': [], '2': ['d3']}}),
  ('control: everything live',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
  ('second cycle with an unswept page',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
   {'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
  ('three cycles',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
   {'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
    'pages': {'1': [], '2': ['d4']}}),
  ('control: everything live',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
  ('second cycle with an unswept page',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
   {'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
  ('three cycles',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
   {'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
    'pages': {'1': [], '2': ['d5']}}),
  ('control: everything live',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
In even epochs live objects are swept and dead ones kept.

Mark bits flip meaning every cycle: an object is live when its mark equals epoch % 2. Initially every object has mark 0 at epoch 0. gc live_ids: finish sweeping every unswept page, advance the epoch, set the mark of each listed live object to the new parity, and mark all pages unswept. alloc id page: sweep the page first if it is unswept, then create the object with the current parity. finish sweeps the remaining pages. Sweeping a page removes objects whose mark differs from the current parity and logs [page, removed]. Return the sweep log and surviving objects per page.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -(k - c)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if not table[c]:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -(k - c)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Cards entered by a spanning object keep pointing back even though an object starts inside them.

A contiguous heap of [start, size] objects is covered by cards of the given size. For each card the table stores the offset of the first object that starts inside the card; a card with no object start that is covered by an object from card c stores -(k - c), a direct back-skip to that card. To find the object containing address q: from q's card follow back-skips; if the card's first start lies after q, move to the previous card; then walk objects forward until one contains q (an entry that does not land on an object start yields corrupt-table). Return the table and the owner start for each query.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, last):
            if table[k] is None:
                table[k] = -(k - c)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 2, last + 1):
            if table[k] is None:
                table[k] = -(k - c)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Lookups in the final card covered by a large object find no owner.

A contiguous heap of [start, size] objects is covered by cards of the given size. For each card the table stores the offset of the first object that starts inside the card; a card with no object start that is covered by an object from card c stores -(k - c), a direct back-skip to that card. To find the object containing address q: from q's card follow back-skips; if the card's first start lies after q, move to the previous card; then walk objects forward until one contains q (an entry that does not land on an object start yields corrupt-table). Return the table and the owner start for each query.

split: open-access