Implement a Contiguous Memory Allocator with Primitive Lists

Simulate an allocator over the contiguous address range [0, capacity), initially one free block. Process two kinds of operation:

• ("alloc", size) chooses the smallest free block whose size is at least size; ties go to the lower starting address. Split any unused suffix and return the allocated block's starting address. Return -1 if no block fits.
• ("free", pointer) releases the currently allocated block that begins exactly at pointer, coalesces it with adjacent free blocks, and returns 1. Return 0 for an unknown pointer, an interior pointer, or a double free.

Function Contract

def run_allocator(
 capacity: int,
 operations: list[tuple],
) -> list[int]:
 ...

Return one integer result for every operation in order.

Constraints

• 1 <= capacity <= 10_000
• 1 <= len(operations) <= 10_000
• An allocation size is an integer in [1, capacity].
• A free pointer is an integer in [0, capacity - 1].
• Use primitive Python lists and scalar variables for allocator state; do not use a tree, heap, hash map, ordered-map package, or bisect.
• If you maintain a size-ordered free list, implement its binary search and insertion directly.
• Block boundaries and coalescing must be derived from allocator-owned list state.

Example

capacity = 8
operations = [
 ("alloc", 3),
 ("alloc", 2),
 ("free", 0),
 ("alloc", 4),
]
result = [0, 3, 1, -1]