Constraints

• 1 <= alignment <= capacity <= 2^20
• capacity and alignment are powers of two
• 1 <= len(operations) <= 2 * 10^5
• Each operation is either ('alloc', size) with 0 <= size <= capacity, or ('free', ptr) with 0 <= ptr < capacity

Examples

Solution

def solution(capacity, alignment, operations):
    import heapq

    def next_power_of_two(x):
        if x <= 1:
            return 1
        return 1 << ((x - 1).bit_length())

    max_order = capacity.bit_length() - 1
    free_sets = [set() for _ in range(max_order + 1)]
    free_heaps = [[] for _ in range(max_order + 1)]

    def add_free(order, start):
        free_sets[order].add(start)
        heapq.heappush(free_heaps[order], start)

    def pop_free(order):
        heap = free_heaps[order]
        blocks = free_sets[order]
        while heap and heap[0] not in blocks:
            heapq.heappop(heap)
        if not heap:
            return None
        start = heapq.heappop(heap)
        blocks.remove(start)
        return start

    add_free(max_order, 0)
    allocated = {}
    result = []

    for op, value in operations:
        if op == 'alloc':
            size = value
            if size <= 0:
                result.append(-1)
                continue

            block_size = max(alignment, next_power_of_two(size))
            if block_size > capacity:
                result.append(-1)
                continue

            target_order = block_size.bit_length() - 1
            order = target_order
            while order <= max_order and not free_sets[order]:
                order += 1

            if order > max_order:
                result.append(-1)
                continue

            start = pop_free(order)

            while order > target_order:
                order -= 1
                half_size = 1 << order
                right_start = start + half_size
                add_free(order, right_start)

            allocated[start] = target_order
            result.append(start)

        elif op == 'free':
            ptr = value
            if ptr not in allocated:
                result.append(0)
                continue

            order = allocated.pop(ptr)
            start = ptr

            while order < max_order:
                buddy = start ^ (1 << order)
                if buddy in free_sets[order]:
                    free_sets[order].remove(buddy)
                    start = min(start, buddy)
                    order += 1
                else:
                    break

            add_free(order, start)
            result.append(1)

        else:
            result.append(-1)

    return result

Time complexity: O(log(capacity / alignment) * log F) amortized per operation, where F is the number of free blocks tracked in the heaps. Space complexity: O(A + F), where A is the number of currently allocated blocks and F is the number of tracked free blocks.

Hints

1. Think in powers of two: each allocation belongs to a size class, and larger blocks can be split until the needed class is reached.
2. When freeing a block of size S at address ptr, its buddy's address is ptr XOR S. If that buddy is also free, they can be merged.