Bài tập | NEU OJ

Trong quản lý bộ nhớ bằng đếm tham chiếu (reference counting), mỗi đối tượng trên heap có một bộ đếm số tham chiếu (refcount) trỏ tới nó. Khi refcount giảm về 0, đối tượng được giải phóng ngay lập tức.

Một chương trình có $k$ biến con trỏ, đánh số $0..k-1$ ; ban đầu tất cả đều là NULL (không trỏ tới đối tượng nào). Cho $m$ lệnh, mỗi lệnh thuộc một trong ba dạng:

NEW v x: tạo đối tượng mới có id là $x$ (id nguyên dương, duy nhất, không bao giờ được dùng lại), refcount ban đầu $= 1$ , rồi gán biến $v$ trỏ tới đối tượng này. Nếu trước đó $v$ đang trỏ tới một đối tượng khác, refcount của đối tượng cũ giảm đi 1 trước khi gán.
COPY v w: gán $v := w$ . Đối tượng mà $w$ đang trỏ tới (nếu có) được tăng refcount thêm 1; đối tượng mà $v$ đang trỏ tới trước đó (nếu có) bị giảm refcount đi 1. Nếu $w$ đang là NULL thì sau lệnh này $v$ cũng là NULL.
CLEAR v: gán $v :=$ NULL; đối tượng cũ mà $v$ trỏ tới (nếu có) bị giảm refcount đi 1.

Mỗi khi refcount của một đối tượng giảm về 0, đối tượng đó bị giải phóng ngay lập tức.

Input:
2 4
NEW 0 100
NEW 1 200
CLEAR 0
CLEAR 1

Output:
FREE 100
FREE 200
LIVE:

Định dạng đầu vào:
Dòng 1: hai số nguyên $k$ và $m$ ( $0 \le k \le 1000$ , $0 \le m \le 2000$ ). $m$ dòng tiếp theo, mỗi dòng là một lệnh theo một trong ba dạng: NEW v x, COPY v w, hoặc CLEAR v ( $0 \le v, w < k$ ; $x$ là số nguyên dương).
Định dạng đầu ra:
Mỗi khi một đối tượng bị giải phóng, in ngay một dòng FREE x (theo đúng thứ tự thời gian xảy ra trong quá trình xử lý các lệnh). Sau khi xử lý xong toàn bộ $m$ lệnh, in thêm một dòng cuối cùng bắt đầu bằng LIVE: theo sau là danh sách id các đối tượng còn sống (refcount > 0), sắp xếp tăng dần, cách nhau bởi dấu cách (nếu không còn đối tượng nào sống thì chỉ in LIVE:).

solution

Đề bài: [Trình biên dịch] Mô phỏng đếm tham chiếu (reference counting)