broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_left(starts, p) - 1
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in starts:
            if s in live:
                fwd[s] = top
                top += info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd[s] + (p - s)
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_left(starts, p)
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in starts:
            if s in live:
                fwd[s] = top
                top += info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd[s] + (p - s)
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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:
References to an object's first byte are reported as dangling or attributed to its neighbour.

Mark-compact with sliding. objs are [start, size, fields] in arbitrary order; pointers (fields and roots) may point anywhere inside an object and belong to the object whose [start, start+size) contains them; a pointer outside every object is ["dangling-pointer", p]. Mark from the roots, assign new addresses to live objects in address order starting at base with no gaps, and relocate every pointer to new start + original offset. Return the new layout [new, old, fields], new roots and the new top.

split: open-access


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

N = 1
observations = []
def solve(blocks, requests):
    free = []
    for addr, size, marked in sorted(blocks):
        if marked:
            continue
        if free and free[-1][0] + free[-1][1] <= addr:
            free[-1][1] += size
        else:
            free.append([addr, size])
    swept = [list(b) for b in free]
    got = []
    for req in requests:
        need = (req + 7) // 8 * 8
        choice = None
        for b in free:
            if b[1] >= need:
                choice = b
                break
        if choice is None:
            got.append(None)
            continue
        got.append(choice[0])
        rem = choice[1] - need
        if rem >= 16:
            choice[0] += need
            choice[1] = rem
        else:
            free.remove(choice)
    return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('exact fit uses the first block',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [48, 64]),
   {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [32, 40]),
   {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder too small to split',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [44, 50, 1]),
   {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [1]),
   {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
  ('control: fully marked heap',
   ([[1024, 32, True], [1056, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('exact fit uses the first block',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [48, 64]),
   {'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [32, 40]),
   {'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder too small to split',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [44, 50, 1]),
   {'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [1]),
   {'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
  ('control: fully marked heap',
   ([[2048, 32, True], [2080, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('exact fit uses the first block',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [48, 64]),
   {'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [32, 40]),
   {'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder too small to split',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [44, 50, 1]),
   {'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [1]),
   {'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
  ('control: fully marked heap',
   ([[3072, 32, True], [3104, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('exact fit uses the first block',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [48, 64]),
   {'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [32, 40]),
   {'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder too small to split',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [44, 50, 1]),
   {'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [1]),
   {'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
  ('control: fully marked heap',
   ([[4096, 32, True], [4128, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('exact fit uses the first block',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [48, 64]),
   {'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [32, 40]),
   {'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder too small to split',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [44, 50, 1]),
   {'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [1]),
   {'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
  ('control: fully marked heap',
   ([[5120, 32, True], [5152, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})]]
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(blocks, requests):
    free = []
    for addr, size, marked in sorted(blocks):
        if marked:
            continue
        if free and free[-1][0] + size == addr:
            free[-1][1] += size
        else:
            free.append([addr, size])
    swept = [list(b) for b in free]
    got = []
    for req in requests:
        need = (req + 7) // 8 * 8
        choice = None
        for b in free:
            if b[1] >= need:
                choice = b
                break
        if choice is None:
            got.append(None)
            continue
        got.append(choice[0])
        rem = choice[1] - need
        if rem >= 16:
            choice[0] += need
            choice[1] = rem
        else:
            free.remove(choice)
    return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('exact fit uses the first block',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [48, 64]),
   {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [32, 40]),
   {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder too small to split',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [44, 50, 1]),
   {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [1]),
   {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
  ('control: fully marked heap',
   ([[1024, 32, True], [1056, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('exact fit uses the first block',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [48, 64]),
   {'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [32, 40]),
   {'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder too small to split',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [44, 50, 1]),
   {'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [1]),
   {'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
  ('control: fully marked heap',
   ([[2048, 32, True], [2080, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('exact fit uses the first block',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [48, 64]),
   {'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [32, 40]),
   {'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder too small to split',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [44, 50, 1]),
   {'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [1]),
   {'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
  ('control: fully marked heap',
   ([[3072, 32, True], [3104, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('exact fit uses the first block',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [48, 64]),
   {'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [32, 40]),
   {'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder too small to split',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [44, 50, 1]),
   {'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [1]),
   {'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
  ('control: fully marked heap',
   ([[4096, 32, True], [4128, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('exact fit uses the first block',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [48, 64]),
   {'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [32, 40]),
   {'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder too small to split',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [44, 50, 1]),
   {'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [1]),
   {'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
  ('control: fully marked heap',
   ([[5120, 32, True], [5152, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})]]
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:
Coalesced free blocks swallow live objects that sit between them.

blocks are [address, size, marked] covering the heap in any order. Sweep in address order: unmarked blocks become free and physically adjacent free blocks coalesce. Then serve requests first-fit in address order: round the request up to 8 bytes; split the chosen block when the remainder is at least 16 bytes (the allocation takes the low end), otherwise hand out the whole block; no fit yields None. Return the swept free list (as it was right after sweeping), the allocation addresses and the final free list.

split: open-access


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

N = 1
observations = []
def solve(blocks, requests):
    free = []
    for addr, size, marked in sorted(blocks):
        if marked:
            continue
        if free and free[-1][0] + free[-1][1] == addr:
            free[-1][1] += size
        else:
            free.append([addr, size])
    swept = [list(b) for b in free]
    got = []
    for req in requests:
        need = (req + 7) // 8 * 8
        choice = None
        for b in free:
            if b[1] >= need:
                choice = b
                break
        if choice is None:
            got.append(None)
            continue
        got.append(choice[0])
        rem = choice[1] - need
        if rem > 0:
            choice[0] += need
            choice[1] = rem
        else:
            free.remove(choice)
    return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('exact fit uses the first block',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [48, 64]),
   {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [32, 40]),
   {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder too small to split',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [44, 50, 1]),
   {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [1]),
   {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
  ('control: fully marked heap',
   ([[1024, 32, True], [1056, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('exact fit uses the first block',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [48, 64]),
   {'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [32, 40]),
   {'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder too small to split',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [44, 50, 1]),
   {'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [1]),
   {'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
  ('control: fully marked heap',
   ([[2048, 32, True], [2080, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('exact fit uses the first block',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [48, 64]),
   {'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [32, 40]),
   {'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder too small to split',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [44, 50, 1]),
   {'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [1]),
   {'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
  ('control: fully marked heap',
   ([[3072, 32, True], [3104, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('exact fit uses the first block',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [48, 64]),
   {'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [32, 40]),
   {'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder too small to split',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [44, 50, 1]),
   {'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [1]),
   {'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
  ('control: fully marked heap',
   ([[4096, 32, True], [4128, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('exact fit uses the first block',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [48, 64]),
   {'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [32, 40]),
   {'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder too small to split',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [44, 50, 1]),
   {'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [1]),
   {'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
  ('control: fully marked heap',
   ([[5120, 32, True], [5152, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})]]
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(blocks, requests):
    free = []
    for addr, size, marked in sorted(blocks):
        if marked:
            continue
        if free and free[-1][0] + free[-1][1] == addr:
            free[-1][1] += size
        else:
            free.append([addr, size])
    swept = [list(b) for b in free]
    got = []
    for req in requests:
        need = (req + 7) // 8 * 8
        choice = None
        for b in free:
            if b[1] >= need:
                choice = b
                break
        if choice is None:
            got.append(None)
            continue
        got.append(choice[0])
        rem = choice[1] - need
        if rem > 16:
            choice[0] += need
            choice[1] = rem
        else:
            free.remove(choice)
    return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('exact fit uses the first block',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [48, 64]),
   {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [32, 40]),
   {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder too small to split',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [44, 50, 1]),
   {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [1]),
   {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
  ('control: fully marked heap',
   ([[1024, 32, True], [1056, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('exact fit uses the first block',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [48, 64]),
   {'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [32, 40]),
   {'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder too small to split',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [44, 50, 1]),
   {'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [1]),
   {'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
  ('control: fully marked heap',
   ([[2048, 32, True], [2080, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('exact fit uses the first block',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [48, 64]),
   {'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [32, 40]),
   {'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder too small to split',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [44, 50, 1]),
   {'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [1]),
   {'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
  ('control: fully marked heap',
   ([[3072, 32, True], [3104, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('exact fit uses the first block',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [48, 64]),
   {'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [32, 40]),
   {'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder too small to split',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [44, 50, 1]),
   {'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [1]),
   {'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
  ('control: fully marked heap',
   ([[4096, 32, True], [4128, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('exact fit uses the first block',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [48, 64]),
   {'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [32, 40]),
   {'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder too small to split',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [44, 50, 1]),
   {'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [1]),
   {'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
  ('control: fully marked heap',
   ([[5120, 32, True], [5152, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})]]
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:
Allocations leave 8-byte free fragments that can never hold a block header.

blocks are [address, size, marked] covering the heap in any order. Sweep in address order: unmarked blocks become free and physically adjacent free blocks coalesce. Then serve requests first-fit in address order: round the request up to 8 bytes; split the chosen block when the remainder is at least 16 bytes (the allocation takes the low end), otherwise hand out the whole block; no fit yields None. Return the swept free list (as it was right after sweeping), the allocation addresses and the final free list.

split: open-access


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

N = 1
observations = []
def solve(blocks, requests):
    free = []
    for addr, size, marked in sorted(blocks):
        if marked:
            continue
        if free and free[-1][0] + free[-1][1] == addr:
            free[-1][1] += size
        else:
            free.append([addr, size])
    swept = [list(b) for b in free]
    got = []
    for req in requests:
        need = (req + 7) // 8 * 8
        choice = None
        for b in free:
            if b[1] >= need:
                choice = b
                break
        if choice is None:
            got.append(None)
            continue
        got.append(choice[0])
        rem = choice[1] - need
        if rem >= 16:
            choice[1] = rem
        else:
            free.remove(choice)
    return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('exact fit uses the first block',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [48, 64]),
   {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [32, 40]),
   {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder too small to split',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [44, 50, 1]),
   {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [1]),
   {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
  ('control: fully marked heap',
   ([[1024, 32, True], [1056, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('exact fit uses the first block',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [48, 64]),
   {'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [32, 40]),
   {'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder too small to split',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [44, 50, 1]),
   {'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [1]),
   {'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
  ('control: fully marked heap',
   ([[2048, 32, True], [2080, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('exact fit uses the first block',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [48, 64]),
   {'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [32, 40]),
   {'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder too small to split',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [44, 50, 1]),
   {'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [1]),
   {'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
  ('control: fully marked heap',
   ([[3072, 32, True], [3104, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('exact fit uses the first block',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [48, 64]),
   {'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [32, 40]),
   {'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder too small to split',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [44, 50, 1]),
   {'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [1]),
   {'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
  ('control: fully marked heap',
   ([[4096, 32, True], [4128, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('exact fit uses the first block',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [48, 64]),
   {'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [32, 40]),
   {'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder too small to split',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [44, 50, 1]),
   {'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [1]),
   {'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
  ('control: fully marked heap',
   ([[5120, 32, True], [5152, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})]]
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(blocks, requests):
    free = []
    for addr, size, marked in sorted(blocks):
        if marked:
            continue
        if free and free[-1][0] + free[-1][1] == addr:
            free[-1][1] += size
        else:
            free.append([addr, size])
    swept = [list(b) for b in free]
    got = []
    for req in requests:
        need = (req + 7) // 8 * 8
        choice = None
        for b in free:
            if b[1] >= need:
                choice = b
                break
        if choice is None:
            got.append(None)
            continue
        got.append(choice[0])
        rem = choice[1] - need
        if rem >= 16:
            choice[0] += rem
            choice[1] = rem
        else:
            free.remove(choice)
    return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('exact fit uses the first block',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [48, 64]),
   {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [32, 40]),
   {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder too small to split',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [44, 50, 1]),
   {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [1]),
   {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
  ('control: fully marked heap',
   ([[1024, 32, True], [1056, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('exact fit uses the first block',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [48, 64]),
   {'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [32, 40]),
   {'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder too small to split',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [44, 50, 1]),
   {'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [1]),
   {'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
  ('control: fully marked heap',
   ([[2048, 32, True], [2080, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('exact fit uses the first block',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [48, 64]),
   {'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [32, 40]),
   {'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder too small to split',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [44, 50, 1]),
   {'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [1]),
   {'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
  ('control: fully marked heap',
   ([[3072, 32, True], [3104, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('exact fit uses the first block',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [48, 64]),
   {'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [32, 40]),
   {'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder too small to split',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [44, 50, 1]),
   {'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [1]),
   {'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
  ('control: fully marked heap',
   ([[4096, 32, True], [4128, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('exact fit uses the first block',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [48, 64]),
   {'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [32, 40]),
   {'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder too small to split',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [44, 50, 1]),
   {'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [1]),
   {'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
  ('control: fully marked heap',
   ([[5120, 32, True], [5152, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})]]
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:
The next allocation is handed the same address again.

blocks are [address, size, marked] covering the heap in any order. Sweep in address order: unmarked blocks become free and physically adjacent free blocks coalesce. Then serve requests first-fit in address order: round the request up to 8 bytes; split the chosen block when the remainder is at least 16 bytes (the allocation takes the low end), otherwise hand out the whole block; no fit yields None. Return the swept free list (as it was right after sweeping), the allocation addresses and the final free list.

split: open-access


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

N = 1
observations = []
def solve(blocks, requests):
    free = []
    for addr, size, marked in sorted(blocks):
        if marked:
            continue
        if free and free[-1][0] + free[-1][1] == addr:
            free[-1][1] += size
        else:
            free.append([addr, size])
    swept = free
    got = []
    for req in requests:
        need = (req + 7) // 8 * 8
        choice = None
        for b in free:
            if b[1] >= need:
                choice = b
                break
        if choice is None:
            got.append(None)
            continue
        got.append(choice[0])
        rem = choice[1] - need
        if rem >= 16:
            choice[0] += need
            choice[1] = rem
        else:
            free.remove(choice)
    return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('exact fit uses the first block',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [48, 64]),
   {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [32, 40]),
   {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder too small to split',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [44, 50, 1]),
   {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [1]),
   {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
  ('control: fully marked heap',
   ([[1024, 32, True], [1056, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('exact fit uses the first block',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [48, 64]),
   {'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [32, 40]),
   {'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder too small to split',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [44, 50, 1]),
   {'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [1]),
   {'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
  ('control: fully marked heap',
   ([[2048, 32, True], [2080, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('exact fit uses the first block',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [48, 64]),
   {'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [32, 40]),
   {'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder too small to split',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [44, 50, 1]),
   {'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [1]),
   {'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
  ('control: fully marked heap',
   ([[3072, 32, True], [3104, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('exact fit uses the first block',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [48, 64]),
   {'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [32, 40]),
   {'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder too small to split',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [44, 50, 1]),
   {'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [1]),
   {'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
  ('control: fully marked heap',
   ([[4096, 32, True], [4128, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('exact fit uses the first block',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [48, 64]),
   {'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [32, 40]),
   {'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder too small to split',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [44, 50, 1]),
   {'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [1]),
   {'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
  ('control: fully marked heap',
   ([[5120, 32, True], [5152, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})]]
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(blocks, requests):
    free = []
    for addr, size, marked in sorted(blocks):
        if marked:
            continue
        if free and free[-1][0] + free[-1][1] == addr:
            free[-1][1] += size
        else:
            free.append([addr, size])
    swept = list(free)
    got = []
    for req in requests:
        need = (req + 7) // 8 * 8
        choice = None
        for b in free:
            if b[1] >= need:
                choice = b
                break
        if choice is None:
            got.append(None)
            continue
        got.append(choice[0])
        rem = choice[1] - need
        if rem >= 16:
            choice[0] += need
            choice[1] = rem
        else:
            free.remove(choice)
    return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('exact fit uses the first block',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [48, 64]),
   {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [32, 40]),
   {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder too small to split',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [44, 50, 1]),
   {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [1]),
   {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
  ('control: fully marked heap',
   ([[1024, 32, True], [1056, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('exact fit uses the first block',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [48, 64]),
   {'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [32, 40]),
   {'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder too small to split',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [44, 50, 1]),
   {'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [1]),
   {'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
  ('control: fully marked heap',
   ([[2048, 32, True], [2080, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('exact fit uses the first block',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [48, 64]),
   {'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [32, 40]),
   {'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder too small to split',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [44, 50, 1]),
   {'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [1]),
   {'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
  ('control: fully marked heap',
   ([[3072, 32, True], [3104, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('exact fit uses the first block',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [48, 64]),
   {'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [32, 40]),
   {'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder too small to split',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [44, 50, 1]),
   {'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [1]),
   {'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
  ('control: fully marked heap',
   ([[4096, 32, True], [4128, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('exact fit uses the first block',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [48, 64]),
   {'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [32, 40]),
   {'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder too small to split',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [44, 50, 1]),
   {'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [1]),
   {'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
  ('control: fully marked heap',
   ([[5120, 32, True], [5152, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})]]
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:
The reported post-sweep free list changes as allocations consume blocks.

blocks are [address, size, marked] covering the heap in any order. Sweep in address order: unmarked blocks become free and physically adjacent free blocks coalesce. Then serve requests first-fit in address order: round the request up to 8 bytes; split the chosen block when the remainder is at least 16 bytes (the allocation takes the low end), otherwise hand out the whole block; no fit yields None. Return the swept free list (as it was right after sweeping), the allocation addresses and the final free list.

split: open-access