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 tham chiếu (Reference Counting) cơ bản

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

    Xét nnn biến con trỏ đánh số 1..n1..n1..n, ban đầu tất cả trỏ tới NULL (không trỏ tới đối tượng nào). Các đối tượng ở đây không chứa trường trỏ tới đối tượng khác (đối tượng lá), refcount chỉ tăng/giảm do gán biến.

    Có qqq câu lệnh, mỗi câu lệnh là một trong ba dạng:

    • NEW v x: tạo đối tượng mới có định danh x (số nguyên dương, không trùng với bất kỳ định danh nào đã xuất hiện trước đó) và gán biến v trỏ tới x (refcount(x) khởi tạo =1=1=1). Nếu trước đó v đang trỏ tới một đối tượng y, refcount(y) giảm 1; nếu về 000, y bị giải phóng.
    • COPY v1 v2: gán v1 trỏ tới đối tượng mà v2 đang trỏ (nếu v2 là NULL thì v1 cũng thành NULL). Refcount đối tượng mới (nếu có) tăng 1 TRƯỚC, sau đó refcount đối tượng cũ của v1 (nếu có) giảm 1 và giải phóng nếu về 000 (thứ tự này đảm bảo trường hợp v1, v2 cùng trỏ một đối tượng không bị giải phóng nhầm).
    • CLEAR v: gán v = NULL; refcount đối tượng cũ (nếu có) giảm 1, giải phóng nếu về 000.

    Ví dụ: n=3n=3n=3, các lệnh NEW 1 100, COPY 2 1, NEW 1 200, CLEAR 2, NEW 3 300, COPY 2 3, CLEAR 3 cho ra: đối tượng 100 bị giải phóng (khi NEW 1 200 không giảm hết vì còn biến 2 giữ, nhưng CLEAR 2 mới thực sự giải phóng nó); cuối cùng còn sống 200 và 300.

    • Định dạng đầu vào:

      Dòng đầu: hai số nguyên nnn, qqq (1≤n≤10001 \le n \le 10001≤n≤1000, 0≤q≤20000 \le q \le 20000≤q≤2000). qqq dòng tiếp theo, mỗi dòng là một lệnh NEW v x, COPY v1 v2 hoặc CLEAR v (1≤v,v1,v2≤n1 \le v, v_1, v_2 \le n1≤v,v1​,v2​≤n; 1≤x≤1091 \le x \le 10^91≤x≤109).

    • Định dạng đầu ra:

      In 2 dòng:

      • Dòng 1: danh sách định danh các đối tượng đã bị giải phóng, theo ĐÚNG THỨ TỰ giải phóng, cách nhau bởi 1 dấu cách (dòng trống nếu không có đối tượng nào bị giải phóng).
      • Dòng 2: danh sách định danh các đối tượng còn sống (refcount >0>0>0) tại thời điểm kết thúc, sắp xếp tăng dần, cách nhau 1 dấu cách (dòng trống nếu không còn đối tượng nào).

      Với ví dụ trên, kết quả là:

      100
200 300

    Ví dụ:

    Đầu vào:

    3 7
NEW 1 100
COPY 2 1
NEW 1 200
CLEAR 2
NEW 3 300
COPY 2 3
CLEAR 3

    Đầu ra:

    100
200 300

    Đầu vào:

    1 2
NEW 1 10
CLEAR 1

    Đầu ra:

    10

    Đang tải editor...