Bài tập | NEU OJ

Một trình quản lý bộ nhớ đơn giản quản lý một vùng nhớ liên tục kích thước $N$ đơn vị, đánh địa chỉ từ $0$ đến $N-1$ . Ban đầu toàn bộ vùng nhớ là một khối trống duy nhất.

Bạn cần mô phỏng $M$ thao tác cấp phát / giải phóng theo chiến lược First-Fit:

A id size: cấp phát một khối kích thước size cho đối tượng id. Duyệt các khối trống theo thứ tự địa chỉ tăng dần, chọn khối trống ĐẦU TIÊN có kích thước $\ge$ size. Nếu khối đó lớn hơn size, cắt thành khối đã cấp (đầu, kích thước đúng bằng size) và một khối trống mới (phần còn lại). Nếu không tìm được khối trống nào đủ lớn, cấp phát THẤT BẠI.
F id: giải phóng khối đang cấp cho id. Sau khi giải phóng, nếu có các khối trống liền kề (về địa chỉ) thì phải hợp nhất (coalesce) chúng thành một khối trống lớn hơn.

Đề bảo đảm: các thao tác A luôn dùng id mới (chưa từng được cấp phát, hoặc đã bị giải phóng và không dùng lại id đó nữa), các thao tác F luôn tham chiếu tới id đang thực sự được cấp phát tại thời điểm đó.

Ví dụ: với $N=10$ : A 1 4 cấp tại địa chỉ 0; A 2 3 cấp tại địa chỉ 4; F 1 giải phóng; A 3 5 thất bại (không có khối trống nào $\ge 5$ ); F 2; A 3 5 cấp tại địa chỉ 0 (toàn bộ vùng nhớ đã hợp nhất lại đủ lớn).

Định dạng đầu vào:
Dòng đầu: hai số nguyên $N$ và $M$ ( $0 \le N \le 10^6$ , $0 \le M \le 1000$ ). $M$ dòng tiếp theo, mỗi dòng là một thao tác dạng A id size hoặc F id ( $1 \le$ id, size $\le 10^6$ ).
Định dạng đầu ra:
In ra $M$ dòng, mỗi dòng tương ứng kết quả của một thao tác theo đúng thứ tự:
- Với A id size: in địa chỉ bắt đầu (số nguyên $\ge 0$ ) nếu cấp phát thành công, in -1 nếu thất bại.
- Với F id: in OK.
Ví dụ ( $N=10$ , 6 thao tác như trên) cho kết quả:
```
0
4
OK
-1
OK
0
```

solution

Đề bài: [Trình biên dịch] Cấp phát bộ nhớ theo First-Fit