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] Thu gom rác theo Thế hệ (Generational GC)

    Bộ thu gom rác theo thế hệ (generational GC) chia đối tượng thành Young Generation (thế hệ trẻ) và Old Generation (thế hệ già). Đối tượng mới luôn được cấp phát ở Young Generation. Mỗi lần Minor GC quét Young Generation: đối tượng không còn được truy cập bị thu hồi ngay; đối tượng còn sống được tăng "số lần sống sót" (survive count) lên 1; nếu số lần sống sót đạt ngưỡng TTT, đối tượng được THĂNG CẤP (promote) sang Old Generation. Old Generation trong bài này KHÔNG bao giờ bị thu gom.

    Mô phỏng qqq "thế hệ" (epoch) liên tiếp, với ngưỡng thăng cấp TTT. Ở mỗi epoch, cho theo thứ tự:

    1. Dòng k id_1 ... id_k: kkk đối tượng MỚI được cấp phát vào Young Generation trong epoch này (định danh chưa từng dùng, survive count khởi tạo =0=0=0).
    2. Dòng r id_1 ... id_r: danh sách rrr định danh đối tượng ĐANG Ở Young Generation (kể cả những đối tượng vừa cấp phát ở dòng trên) mà vẫn còn được truy cập (sống sót) sau Minor GC epoch này. Mọi đối tượng đang ở Young Generation nhưng KHÔNG có trong danh sách này bị thu hồi ngay trong epoch này.

    Với mỗi đối tượng sống sót: survive count +1+1+1; nếu sau đó survive count ≥T\ge T≥T, thăng cấp sang Old Generation (rời khỏi Young Generation).

    Ví dụ: T=2T=2T=2, 3 epoch: epoch 1 cấp phát {1,2,3}\{1,2,3\}{1,2,3}, sống sót {1,2}\{1,2\}{1,2} (đối tượng 333 bị thu hồi); epoch 2 cấp phát {4}\{4\}{4}, sống sót {1,2,4}\{1,2,4\}{1,2,4} (1,21,21,2 đạt survive count =2=2=2 nên thăng cấp lên Old); epoch 3 không cấp phát thêm, sống sót rỗng (đối tượng 444 bị thu hồi). Kết quả: Young rỗng, Old ={1,2}=\{1,2\}={1,2}, tổng số bị thu hồi =2=2=2.

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

      Dòng đầu: hai số nguyên TTT, qqq (1≤T≤1001 \le T \le 1001≤T≤100, 0≤q≤5000 \le q \le 5000≤q≤500). Với mỗi trong qqq epoch, có ĐÚNG 2 dòng như mô tả ở trên (LUÔN có đủ 2 dòng, kể cả khi k=0k=0k=0 hoặc r=0r=0r=0 thì dòng đó chỉ có duy nhất số 000). Đảm bảo mọi định danh trong dòng thứ 2 là tập con hợp lệ của các đối tượng đang tồn tại trong Young Generation tại thời điểm đó; toàn bộ định danh đối tượng xuất hiện trong input là duy nhất.

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

      In 3 dòng:

      • Dòng 1: danh sách định danh đối tượng còn trong Young Generation sau khi kết thúc, tăng dần, cách nhau dấu cách (trống nếu rỗng).
      • Dòng 2: danh sách định danh đối tượng trong Old Generation, tăng dần (trống nếu rỗng).
      • Dòng 3: tổng số đối tượng đã bị thu hồi trong toàn bộ quá trình.

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

      
1 2
2

    Ví dụ:

    Đầu vào:

    1 1
1 1
1 1

    Đầu ra:

    
1
0

    Đầu vào:

    2 3
3 1 2 3
2 1 2
1 4
3 1 2 4
0
0

    Đầu ra:

    
1 2
2

    Đang tải editor...