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] Cấp phát bộ nhớ heap theo chiến lược best-fit

    Một bộ cấp phát bộ nhớ (heap allocator) quản lý một vùng nhớ liên tục kích thước SSS byte, đánh địa chỉ từ 000 đến S−1S-1S−1. Ban đầu toàn bộ vùng nhớ là một khối trống duy nhất.

    Cho mmm yêu cầu, mỗi yêu cầu là một trong hai dạng:

    • ALLOC id size: cấp phát sizesizesize byte cho đối tượng có id là ididid (chuỗi/số duy nhất), theo chiến lược best-fit: tìm trong các khối trống hiện có khối có kích thước ≥size\ge size≥size và nhỏ nhất; nếu có nhiều khối cùng kích thước nhỏ nhất, chọn khối có địa chỉ bắt đầu nhỏ nhất. Vùng được cấp là sizesizesize byte đầu tiên của khối đó; nếu khối lớn hơn sizesizesize, phần dư trở thành một khối trống mới nằm ngay sau vùng vừa cấp. Nếu không khối nào đủ lớn, cấp phát thất bại.
    • FREE id: giải phóng vùng nhớ đã cấp cho ididid; vùng này trở thành khối trống, sau đó được gộp (merge) với khối trống liền kề bên trái và/hoặc bên phải (nếu có) thành một khối trống lớn hơn.
    Input:
100 5
ALLOC 1 30
ALLOC 2 20
FREE 1
ALLOC 3 25
ALLOC 4 10

Output:
OK 1 0
OK 2 30
OK 3 0
OK 4 50
    • Định dạng đầu vào:

      Dòng 1: hai số nguyên SSS và mmm (1≤S≤1091 \le S \le 10^91≤S≤109, 0≤m≤20000 \le m \le 20000≤m≤2000). mmm dòng tiếp theo, mỗi dòng là một lệnh ALLOC id size hoặc FREE id (ididid là một token không chứa khoảng trắng, sizesizesize là số nguyên dương).

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

      Với mỗi lệnh ALLOC, theo đúng thứ tự xuất hiện trong input, in ra một dòng: OK id addr nếu cấp phát thành công (addraddraddr là địa chỉ bắt đầu vùng vừa cấp), hoặc FAIL id nếu thất bại. Lệnh FREE không in gì.

    Ví dụ:

    Đầu vào:

    100 5
ALLOC 1 30
ALLOC 2 20
FREE 1
ALLOC 3 25
ALLOC 4 10

    Đầu ra:

    OK 1 0
OK 2 30
OK 3 0
OK 4 50

    Đầu vào:

    10 2
ALLOC 1 10
ALLOC 2 1

    Đầu ra:

    OK 1 0
FAIL 2

    Đang tải editor...