← 返回 openai 的题目列表Design a Memory Allocator with Coalescing
类型：online_judge
Problem: Design a Memory Allocator with Coalescing
You are given a contiguous memory region with addresses [0, n - 1]. Implement a simple memory allocator that supports two operations:
A size: Allocate a contiguous block of memory of length size.
Use the first-fit policy: choose the free block with the smallest starting address whose length is at least size.
If allocation succeeds, output the starting address of the allocated block.
If no sufficiently large contiguous free block exists, output -1.
F addr: Free a previously allocated block starting at address addr.
If addr is the starting address of a currently allocated block, free it and output the size of the freed block.
After freeing, if the newly freed block is adjacent to existing free blocks on the left or right, coalesce them into one larger free block to reduce fragmentation.
If addr is invalid or the block has already been freed, output -1.
Process q operations.
Input Format
n q
op1 arg1
op2 arg2
...
opq argq
n is the total memory size.
q is the number of operations.
op is either A or F.
Output Format
For each operation, output one integer representing the result of that operation.
Constraints
1 <= n <= 10^9
1 <= q <= 5000
1 <= size <= n
0 <= addr < n
Example
Input:
10 6
A 3
A 4
F 0
A 2
A 2
A 2
Output:
0
3
3
0
7
-1
Example
Input
10 6
A 3
A 4
F 0
A 2
A 2
A 2
Output
0
3
3
0
7
-1