Codeforces Beta Round 7 |
---|
Закончено |
До релиза первой национальной операционной системы BerlOS осталось совсем чуть-чуть. В ней не готовы всего несколько компонентов — менеджер памяти в том числе. По задумке разработчиков, в первой версии он будет очень прост и прямолинеен. Менеджер памяти будет поддерживать три операции:
Модель памяти в данном случае очень проста. Память представляет собой последовательность m байт, условно пронумерованных от первого до m-го.
Первая операция alloc n принимает в качестве единственного параметра размер блока памяти, который предстоит выделить. При обработке этой операции в памяти выбирается свободный блок из n байт, идущих подряд. Если таких блоков несколько, то выбирается ближайший к началу памяти (первому байту). Все эти байты помечаются использованными, и менеджер возвращает 32-битное целое знаковое число, являющееся идентификатором этого блока. Если свободный блок такого размера найти невозможно, то функция возвращает специальное значение NULL.
Вторая операция erase x принимает в качестве параметра идентификатор некоторого блока. Она возвращает память системе, помечая байты этого блока свободными для последующего использования. В том случае, если этому идентификатору не соответствует ранее выделенный блок, который еще не был удален, то функция возвращает специальное значение ILLEGAL_ERASE_ARGUMENT.
Последняя операция defragment не имеет аргументов и просто перемещает занятые участки памяти вплотную к ее началу, не меняя их относительный порядок. Таким образом, после этой операции вся свободная память образует один непрерывный участок, который идет следом за использованной памятью.
В текущей реализации требуется использовать в качестве идентификаторов последовательные целые числа от 1. Каждый успешный вызов alloc должен возвращать очередное число. Неудачные вызовы alloc не оказывают влияния на описанную нумерацию.
Ваша задача состоит в том, чтобы написать реализацию менеджера памяти. Для каждой команды alloc нужно выводить возвращаемое значение. Также следует выводить ILLEGAL_ERASE_ARGUMENT для всех неудачных вызовов erase.
В первой строке входных данных содержатся два целых положительных числа t и m (1 ≤ t ≤ 100;1 ≤ m ≤ 100), где t — количество операций, заданных менеджеру памяти на исполнение, а m — размер доступной памяти в байтах. Далее в t строках заданы сами операции. Первая операция задается строкой alloc n (1 ≤ n ≤ 100), где n целое число. Вторая задается строкой erase x, где x произвольное 32-битное целое знаковое число. Третья операция задается строкой defragment.
Выведите последовательность строк. Каждая строка должна содержать либо результат работы операции alloc, либо ILLEGAL_ERASE_ARGUMENT как результат неудачного выполнения операции erase. Вывод следует осуществлять в порядке совершения операций. Реализация alloc должна возвращать в качестве идентификаторов выделенных блоков целые числа, начиная с 1.
6 10
alloc 5
alloc 3
erase 1
alloc 6
defragment
alloc 6
1
2
NULL
3
Название |
---|