solution

Hệ thống cấp phát buddy (buddy system) quản lý một vùng nhớ kích thước $2^K$ byte (địa chỉ $0..2^K-1$). Bộ nhớ luôn được chia thành các khối có kích thước là lũy thừa của 2; một khối bậc (order) $k$ có kích thước $2^k$ byte. Ban đầu có một khối trống duy nhất ở bậc $K$.

Cho $m$ yêu cầu:

• ALLOC id size: cấp phát $size$ byte cho đối tượng $id$. Tìm bậc nhỏ nhất $k$ sao cho $2^k \ge size$ (nếu $k > K$ thì thất bại luôn). Nếu đang có khối trống ở đúng bậc $k$, lấy khối có địa chỉ nhỏ nhất trong số đó. Nếu không có, tìm bậc $j$ nhỏ nhất thoả $j > k$ và đang có khối trống ở bậc $j$ (lấy khối địa chỉ nhỏ nhất ở bậc đó); nếu không tồn tại bậc nào $\ge k$ còn khối trống, cấp phát thất bại. Nếu tìm được khối bậc $j > k$, tách (split) liên tục: mỗi lần tách một khối bậc $t$ thành hai khối "buddy" bậc $t-1$ nằm liền kề nhau (khối có địa chỉ nhỏ hơn giữ nguyên vị trí để tiếp tục tách hoặc cấp phát; khối có địa chỉ lớn hơn trở thành khối trống mới ở bậc $t-1$), lặp lại cho tới khi đạt bậc $k$, rồi cấp khối bậc $k$ đó cho $id$.
• FREE id: giải phóng khối đã cấp cho $id$ về trạng thái khối trống ở đúng bậc $k$ mà nó đã được cấp. Sau đó gộp (merge) liên tục với buddy của nó — khối cùng bậc $k$ có địa chỉ bằng $addr \oplus 2^k$ (XOR bit) — nếu buddy đó cũng đang là khối trống nguyên vẹn ở bậc $k$: hai khối gộp thành một khối trống bậc $k+1$ (địa chỉ là địa chỉ nhỏ hơn trong hai buddy), rồi tiếp tục thử gộp lên bậc cao hơn, cho tới khi buddy không trống hoặc đã đạt bậc $K$.

Input:
3 5
ALLOC A 3
ALLOC B 3
ALLOC C 1
FREE A
ALLOC C 1

Output:
OK A 0 2
OK B 4 2
FAIL C
OK C 0 0