Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

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

    Một chiến lược quản lý bộ nhớ tự động phổ biến trong các máy ảo (như CPython) là đếm tham chiếu (reference counting): mỗi đối tượng trên heap giữ một bộ đếm số lượng biến/thanh ghi đang trỏ tới nó; khi bộ đếm giảm về 000, đối tượng lập tức bị giải phóng (không cần đợi một chu kỳ thu gom rác riêng).

    Xét một máy ảo có NNN thanh ghi gốc (root) đánh số 0,…,N−10, \dots, N-10,…,N−1, ban đầu đều không trỏ tới đối tượng nào. Các đối tượng trên heap được đảm bảo không chứa trường tham chiếu tới đối tượng khác (chỉ các thanh ghi mới trực tiếp giữ tham chiếu), do đó không xảy ra hiện tượng giải phóng dây chuyền hay chu trình tham chiếu. Chương trình gồm MMM lệnh, mỗi lệnh là một trong ba dạng sau (x,yx, yx,y là chỉ số thanh ghi):

    • NEW x: cấp phát một đối tượng mới trên heap (ID của đối tượng là số thứ tự cấp phát, đánh số tăng dần từ 111, không bao giờ trùng hay tái sử dụng), rồi gán thanh ghi xxx trỏ tới đối tượng mới này (bộ đếm tham chiếu của đối tượng mới bắt đầu là 111). Nếu trước đó thanh ghi xxx đang trỏ tới một đối tượng khác, bộ đếm của đối tượng cũ đó giảm đi 111.
    • MOVE x y: thanh ghi xxx được gán trỏ tới cùng đối tượng mà thanh ghi yyy đang trỏ tới (hoặc không trỏ tới gì nếu yyy đang không trỏ tới đối tượng nào). Nếu đối tượng mới mà xxx trỏ tới có tồn tại, bộ đếm của nó tăng 111; nếu thanh ghi xxx trước đó đang trỏ tới một đối tượng khác, bộ đếm đối tượng cũ đó giảm 111.
    • CLEAR x: thanh ghi xxx được gán thành không trỏ tới đối tượng nào; nếu trước đó nó đang trỏ tới một đối tượng, bộ đếm đối tượng đó giảm 111.

    Ngay sau bất kỳ thao tác nào làm bộ đếm tham chiếu của một đối tượng giảm về đúng 000, đối tượng đó bị giải phóng ngay lập tức. Hãy in ra ID của các đối tượng bị giải phóng, theo đúng thứ tự thời điểm chúng bị giải phóng trong quá trình thực thi tuần tự các lệnh (mỗi lệnh làm giảm bộ đếm của tối đa một đối tượng cũ, nên không có hai đối tượng nào bị giải phóng đồng thời bởi cùng một lệnh).

    Ví dụ: với N=1N=1N=1, các lệnh NEW 0 rồi CLEAR 0: đối tượng ID 111 được tạo (bộ đếm 111), sau đó CLEAR 0 làm bộ đếm về 000 và bị giải phóng — in ra 1.

    • Định dạng đầu vào:
      • Dòng đầu tiên chứa hai số nguyên NNN và MMM (1≤N≤1001 \le N \le 1001≤N≤100, 0≤M≤20000 \le M \le 20000≤M≤2000) — số thanh ghi và số lệnh.
      • MMM dòng tiếp theo, mỗi dòng một lệnh NEW x, MOVE x y, hoặc CLEAR x đúng cú pháp mô tả ở trên (0≤x,y<N0 \le x, y < N0≤x,y<N).
    • Định dạng đầu ra:

      In ra, mỗi dòng một số nguyên, là ID của một đối tượng bị giải phóng, theo đúng thứ tự các sự kiện giải phóng xảy ra khi thực thi tuần tự các lệnh. Nếu không có đối tượng nào bị giải phóng, không in gì.

    Ví dụ:

    Đầu vào:

    1 2
NEW 0
CLEAR 0

    Đầu ra:

    1

    Đầu vào:

    2 4
NEW 0
MOVE 1 0
CLEAR 0
CLEAR 1

    Đầu ra:

    1

    Đang tải editor...