solution

Bộ thu gom rác kiểu copying (Cheney's algorithm) chia bộ nhớ thành hai nửa (from-space / to-space); mỗi lần GC, nó sao chép toàn bộ object còn sống từ from-space sang to-space theo thứ tự duyệt theo chiều rộng (BFS) bắt đầu từ các gốc (root), rồi cập nhật lại con trỏ — nhờ đó vùng nhớ được dồn nén (compact), không còn phân mảnh, đồng thời rác được thu hồi trong một lượt duyệt duy nhất.

Cho $n$ object (id $1..n$), object thứ $i$ có kích thước $size_i$ byte và một danh sách trường con trỏ (fields) — mỗi trường trỏ tới id một object khác, hoặc $0$ nếu là con trỏ null. Cho $r$ gốc (id các object được biến/stack trỏ trực tiếp tới, có thể lặp lại).

Hãy mô phỏng chính xác thuật toán Cheney (dùng một hàng đợi FIFO):

1. Duyệt lần lượt các gốc theo đúng thứ tự cho trong danh sách gốc; với mỗi gốc chưa từng được sao chép, gán cho nó địa chỉ mới kế tiếp trong to-space (bắt đầu từ $0$, các object xếp liên tiếp không khoảng trống — địa chỉ mới của object tiếp theo = địa chỉ mới object trước + kích thước của nó), rồi đẩy vào hàng đợi.
2. Lặp lại: lấy object ở đầu hàng đợi ra, duyệt lần lượt các trường con trỏ của nó (theo đúng thứ tự trong danh sách trường, bỏ qua con trỏ null); với mỗi trường trỏ tới object chưa từng được sao chép, gán địa chỉ mới kế tiếp cho nó và đẩy vào hàng đợi. Tiếp tục tới khi hàng đợi rỗng.

Object nào không bao giờ được gán địa chỉ mới (không tới được từ gốc) là rác, bị thu hồi.

Yêu cầu: in số lượng object còn sống $S$; sau đó $S$ dòng, mỗi dòng "id địa_chỉ_mới" theo đúng thứ tự được gán địa chỉ (thứ tự duyệt BFS ở trên); dòng cuối in tổng số byte được thu hồi ($=$ tổng kích thước tất cả $n$ object $-$ tổng kích thước các object còn sống).

Ví dụ: $3$ object: obj$1$ (size $2$, field $\to 2$), obj$2$ (size $3$, field $\to 3$), obj$3$ (size $1$, không field). Gốc $=\{1\}$. Kết quả: obj$1$ được địa chỉ mới $0$, obj$2$ địa chỉ $2$, obj$3$ địa chỉ $5$; không byte nào bị thu hồi (mọi object đều sống).