← 返回 openai 的题目列表Implement a Simple Memory Allocator with First-Fit and Best-Fit
类型：online_judge
Problem: Implement a Simple malloc/free Allocator
Implement a simplified memory allocator on a fixed-size heap. The allocator supports two allocation policies:
first-fit: choose the first free block, in increasing address order, that can fit the requested size.
best-fit: choose the smallest free block that can fit the requested size; if tied, choose the lower address.
The heap address range is [0, N). Initially, the entire heap is free.
Process Q operations:
A id size: allocate size contiguous bytes for object id.
If successful, print the starting address.
If not enough contiguous memory exists, print -1.
You may assume A is never called for an already allocated id.
F id: free the memory owned by id.
If id exists and is currently allocated, print OK.
Otherwise print INVALID.
After every free, adjacent free blocks must be coalesced.
Input Format
N Q strategy
op_1
op_2
...
op_Q
Constraints:
1 <= N <= 10^6
1 <= Q <= 2 * 10^5
strategy is either first or best
1 <= size <= N
Output Format
Print one line per operation.
Example
Input:
10 6 first
A a 3
A b 4
F a
A c 2
A d 5
F x
Output:
0
3
OK
0
-1
INVALID
Example
Input
10 6 first
A a 3
A b 4
F a
A c 2
A d 5
F x
Output
0
3
OK
0
-1
INVALID