Кучи: планировщик NIGHTBUILD

Шесть задач про кучи на сюжете ночного сбоя планировщика NIGHTBUILD: от проверки инварианта пирамиды до фибоначчиевой кучи. Решения сдаются на sort-me.org на GNU C++20, у каждой задачи свои баллы, задача F со звёздочкой.

A. Core Invariant

[02:47] Ночной билд остановлен. [02:48] Планировщик перешёл в аварийный режим. [02:49] Принято решение восстановить ядро вручную.

Сердце планировщика NIGHTBUILD — приоритетная очередь в виде неубывающей пирамиды. Если хотя бы один элемент нарушает иерархию, система не запустится.

Дан массив $a$ длины $n$ — состояние очереди в момент сбоя. Планировщик корректен, если для каждого $i$ ($1 \le i \le n$):

• если $2i \le n$, то $a_i \le a_{2i}$;
• если $2i + 1 \le n$, то $a_i \le a_{2i+1}$.

Нужно определить, можно ли безопасно перезапустить NIGHTBUILD.

Входные данные

• Первая строка: целое число $n$ ($1 \le n \le 10^5$).
• Вторая строка: $n$ целых чисел $a_i$ ($|a_i| \le 2 \cdot 10^9$) — приоритеты процессов.

Выходные данные

YES, если массив удовлетворяет инварианту пирамиды, иначе NO.

Лимит памяти: 128 МБ.

Пример

5
1 0 1 2 0

NO

Примечание. $a_1 = 1 > a_2 = 0$ — инвариант нарушен уже у корня. Числа до $2 \cdot 10^9$ по модулю не помещаются в int, нужен 64-битный тип.

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <cstdint>
#include <iostream>
 
// Возвращает true, если a[1..n] — неубывающая пирамида: каждый элемент
// не больше своих детей a[2i] и a[2i + 1]. Нумерация с 1, a[0] не занят.
bool IsHeap(const int64_t* a, int n) {
  // TODO
  return false;
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int n;
  std::cin >> n;
  int64_t* a = new int64_t[n + 1];
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
  }
  std::cout << (IsHeap(a, n) ? "YES" : "NO") << "\n";
  delete[] a;
  return 0;
}

B. Wakeup Queue

[03:12] Планировщик остаётся в аварийном режиме. [03:14] Автоматическая очередь пробуждения не инициализировалась. [03:15] Система ожидает ручного восстановления приоритетов.

После аварии очередь пробуждения сбросилась в неупорядоченное состояние. Дан массив $a$ из $n$ целых чисел — приоритеты процессов. Выведите их в порядке неубывания.

Входные данные

• Первая строка: целое число $n$ ($1 \le n \le 10^6$).
• Вторая строка: $n$ целых чисел $a_i$ ($|a_i| \le 10^9$).

Выходные данные

$n$ чисел — элементы массива в порядке неубывания.

Лимит памяти: 128 МБ.

Пример

10
1 8 2 1 4 7 3 2 3 6

1 1 2 2 3 3 4 6 7 8

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функции.

#include <iostream>
 
// Просеивает a[i] вниз в пирамиде из первых n элементов массива.
void SiftDown(int* a, int n, int i) {
  // TODO
}
 
// Сортирует a[0..n-1] по неубыванию пирамидальной сортировкой.
// Готовыми функциями сортировки и кучами из STL пользоваться нельзя.
void HeapSort(int* a, int n) {
  // TODO
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int n;
  std::cin >> n;
  int* a = new int[n];
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  HeapSort(a, n);
  for (int i = 0; i < n; ++i) {
    std::cout << a[i] << " ";
  }
  std::cout << "\n";
  delete[] a;
  return 0;
}

C. Priority Dispatcher

[03:42] Планировщик частично восстановлен. [03:45] Очередь диспетчера пуста. [03:47] Необходимо срочно восстановить механизм выборки приоритетов.

Диспетчер выбирает задачи и для немедленного выполнения, и для отложенных операций, поэтому очередь должна поддерживать три команды:

• Insert(x) — добавить процесс с приоритетом $x$;
• GetMin — извлечь и вывести минимальный приоритет;
• GetMax — извлечь и вывести максимальный приоритет.

Гарантируется, что извлечения из пустой очереди не будет.

Входные данные

• Первая строка: целое число $q$ ($1 \le q \le 10^5$) — количество операций.
• Далее $q$ строк с командами. Число в Insert пишется в скобках, без пробела.
• $|x| \le 2 \cdot 10^9$.

Выходные данные

Для каждой команды GetMin и GetMax — извлечённое значение в отдельной строке.

Лимит памяти: 256 МБ.

Пример

10
Insert(100)
Insert(99)
Insert(1)
Insert(2)
GetMin
GetMax
Insert(1)
GetMin
GetMin
GetMax

1
100
1
2
99

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функции.

#include <cstdint>
#include <iostream>
#include <string>
 
// Очередь, из которой можно извлекать и минимум, и максимум.
// Устройство — на ваше усмотрение: память под capacity элементов.
struct Dispatcher {
  int capacity;
  // TODO
};
 
void Init(Dispatcher* dispatcher, int capacity) {
  dispatcher->capacity = capacity;
  // TODO
}
 
void Destroy(Dispatcher* dispatcher) {
  // TODO
}
 
void Insert(Dispatcher* dispatcher, int64_t x) {
  // TODO
}
 
// Извлекает и возвращает минимальный элемент. Очередь не пуста.
int64_t ExtractMin(Dispatcher* dispatcher) {
  // TODO
  return 0;
}
 
// Извлекает и возвращает максимальный элемент. Очередь не пуста.
int64_t ExtractMax(Dispatcher* dispatcher) {
  // TODO
  return 0;
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int q;
  std::cin >> q;
  Dispatcher dispatcher;
  Init(&dispatcher, q);
  std::string command;
  for (int i = 0; i < q; ++i) {
    std::cin >> command;
    if (command == "GetMin") {
      std::cout << ExtractMin(&dispatcher) << "\n";
    } else if (command == "GetMax") {
      std::cout << ExtractMax(&dispatcher) << "\n";
    } else {
      // Команда вида Insert(x): число между скобками.
      Insert(&dispatcher, std::stoll(command.substr(7)));
    }
  }
  Destroy(&dispatcher);
  return 0;
}

D. CPU Allocator

[04:10] Планировщик проснулся, но распределение ядер отключено. [04:12] Очередь свободных CPU пуста, занятые не освобождаются. [04:14] Требуется восстановить модуль назначения задач на ядра по минимальной стоимости.

У каждого из $n$ ядер своя ставка $a_i$ — стоимость минуты работы, все ставки различны.

• Задача $j$ приходит в момент $t_j$ и длится $f_j$ минут.
• В момент прихода она сразу назначается на свободное ядро с минимальной ставкой.
• Если свободных ядер нет, задача отбрасывается.
• Ядро занято на полуинтервале $[t_j, t_j + f_j)$ и снова свободно ровно в момент $t_j + f_j$.

Суммарная стоимость — сумма (ставка ядра) $\times$ (длительность задачи) по всем назначенным задачам. Задачи даны по возрастанию $t_j$, все $t_j$ различны.

Входные данные

• Первая строка: $n$ и $m$ ($1 \le n, m \le 3 \cdot 10^5$) — количество ядер и задач.
• Вторая строка: $n$ различных целых чисел $a_1, \ldots, a_n$ — ставки ядер.
• Далее $m$ строк по два целых числа $t_j$ и $f_j$ ($1 \le t_j \le 10^9$, $1 \le f_j \le 10^6$).

Выходные данные

Одно целое число — суммарная стоимость по назначенным задачам.

Лимит памяти: 128 МБ.

Пример

4 7
3 2 6 4
1 3
2 5
3 7
4 10
5 5
6 100
9 2

105

Примечание. Как распределятся задачи:

Итого $6 + 15 + 28 + 20 + 30 + 6 = 105$. Ядро 2 освобождается в момент 4 ровно к приходу четвёртой задачи, ядро 3 — в момент 7 и успевает взять последнюю.

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функцию.

#include <cstdint>
#include <iostream>
 
// Возвращает суммарную стоимость: каждая задача j в момент start[j] уходит
// на свободное ядро с минимальной ставкой и занимает его на duration[j]
// минут, а если свободных ядер нет — отбрасывается.
int64_t TotalCost(const int64_t* rates, int n, const int64_t* start,
                  const int64_t* duration, int m) {
  // TODO
  return 0;
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  int n;
  int m;
  std::cin >> n >> m;
  int64_t* rates = new int64_t[n];
  for (int i = 0; i < n; ++i) {
    std::cin >> rates[i];
  }
  int64_t* start = new int64_t[m];
  int64_t* duration = new int64_t[m];
  for (int j = 0; j < m; ++j) {
    std::cin >> start[j] >> duration[j];
  }
  std::cout << TotalCost(rates, n, start, duration, m) << "\n";
  delete[] rates;
  delete[] start;
  delete[] duration;
  return 0;
}

E. Memory Manager

[04:45] Очередь задач стабилизировалась. [04:46] Мониторинг памяти сообщает об утечках. [04:48] Модуль управления памятью не реагирует на запросы.

Память выделяется блоками с номерами от 1 до $N$. Запрос на выделение получает свободный блок с минимальным номером. Занятый блок освобождается сам через фиксированное время $L$ после последнего обращения.

• <Time> + — выделить новый блок в момент Time.
• <Time> . <BlockNo> — обратиться к блоку BlockNo в момент Time: если блок занят, запрос успешен и время освобождения сдвигается на $L$ вперёд; если свободен — запрос ошибочный.

События даны по возрастанию времени, одновременные обрабатываются в порядке входа. Памяти гарантированно хватает.

Входные данные

Каждая строка — один запрос в одном из двух форматов выше. Time от 0 до 65000, номера блоков от 1 до 30000, запросов не больше 80000. Ввод читается до конца файла.

Выходные данные

Для выделения — номер выделенного блока. Для обращения — +, если блок был занят, и -, если свободен.

Лимит памяти: 256 МБ.

Пример

1 +
1 +
1 +
2 . 2
2 . 3
3 . 30000
601 . 1
601 . 2
602 . 3
602 +
602 +
1202 . 2

1
2
3
+
+
-
-
+
-
1
3
-

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функции.

#include <iostream>
 
constexpr int kBlocks = 30000;
 
// Состояние памяти: какие блоки заняты и когда освобождаются.
struct MemoryManager {
  // TODO
};
 
void Init(MemoryManager* memory) {
  // TODO
}
 
void Destroy(MemoryManager* memory) {
  // TODO
}
 
// Выделяет свободный блок с минимальным номером в момент time.
int Allocate(MemoryManager* memory, int time) {
  // TODO
  return 0;
}
 
// Обращение к блоку в момент time: true, если блок занят (тогда его время
// освобождения продлевается), false, если он свободен.
bool Access(MemoryManager* memory, int time, int block) {
  // TODO
  return false;
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  MemoryManager memory;
  Init(&memory);
  int time;
  char type;
  while (std::cin >> time >> type) {
    if (type == '+') {
      std::cout << Allocate(&memory, time) << "\n";
    } else {
      int block;
      std::cin >> block;
      std::cout << (Access(&memory, time, block) ? '+' : '-') << "\n";
    }
  }
  Destroy(&memory);
  return 0;
}

F. [*] Queue Fabric

[05:45] Ядро NIGHTBUILD стабилизировано, но производительность критически низкая. [05:47] Обычные структуры планировщика не справляются с нагрузкой. [05:49] Принято решение активировать экспериментальный модуль Fib-Kernel.

Нужно реализовать фибоначчиеву кучу: она поддерживает быстрое слияние очередей и амортизированное уменьшение ключа. Очереди нумеруются с 0 в порядке создания. Команды, по одной в строке:

• create — создать новую пустую кучу;
• insert k x — добавить $x$ в кучу $k$;
• extract-min k — извлечь и вывести минимум кучи $k$, если куча пуста — вывести *;
• merge k m — создать новую кучу как результат слияния куч $k$ и $m$;
• decrease-key k x y — в куче $k$ заменить значение $x$ на $y$; гарантируется, что $x$ есть в куче $k$ и $x \ge y$.

Числа по модулю не больше $10^9$, команд не больше $10^6$, все номера куч корректны.

Входные данные

Последовательность команд в описанном формате, до конца файла.

Выходные данные

Для каждой команды extract-min — минимум кучи или *, если она пуста.

Лимит памяти: 128 МБ.

Пример

create
insert 0 1
insert 0 3
insert 0 5
extract-min 0
create
insert 1 2
insert 1 4
insert 1 6
merge 0 1
decrease-key 2 5 1
extract-min 2
extract-min 2
extract-min 0
extract-min 0
extract-min 0

1
1
2
3
5
*

Примечание. Куча 0 после первого извлечения — $\{3, 5\}$, куча 1 — $\{2, 4, 6\}$, куча 2 после слияния и decrease-key — $\{1, 2, 3, 4, 6\}$. Из кучи 2 извлекаются 1 и 2, из кучи 0 — 3, 5, а затем она пуста.

Заготовка

Ввод и вывод уже написаны, остаётся реализовать функции. Для decrease-key по значению понадобится способ быстро найти узел с ключом $x$ в куче $k$.

#include <cstdint>
#include <iostream>
#include <string>
 
// Узел фибоначчиевой кучи.
struct Node {
  int64_t key;
  int degree = 0;
  bool marked = false;
  Node* parent = nullptr;
  Node* child = nullptr;
  Node* left = this;   // Соседи по циклическому списку.
  Node* right = this;
};
 
struct FibHeap {
  Node* min = nullptr;
  int size = 0;
};
 
void Insert(FibHeap* heap, int64_t x) {
  // TODO
}
 
// Извлекает минимум в *result. Возвращает false, если куча пуста.
bool ExtractMin(FibHeap* heap, int64_t* result) {
  // TODO
  return false;
}
 
// Возвращает новую кучу из элементов first и second.
FibHeap* Merge(FibHeap* first, FibHeap* second) {
  // TODO
  return new FibHeap;
}
 
// Заменяет значение x на y <= x.
void DecreaseKey(FibHeap* heap, int64_t x, int64_t y) {
  // TODO
}
 
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  constexpr int kMaxHeaps = 1000000;
  FibHeap** heaps = new FibHeap*[kMaxHeaps];
  int count = 0;
  std::string command;
  while (std::cin >> command) {
    if (command == "create") {
      heaps[count++] = new FibHeap;
    } else if (command == "insert") {
      int k;
      int64_t x;
      std::cin >> k >> x;
      Insert(heaps[k], x);
    } else if (command == "extract-min") {
      int k;
      std::cin >> k;
      int64_t result;
      if (ExtractMin(heaps[k], &result)) {
        std::cout << result << "\n";
      } else {
        std::cout << "*\n";
      }
    } else if (command == "merge") {
      int k;
      int m;
      std::cin >> k >> m;
      heaps[count++] = Merge(heaps[k], heaps[m]);
    } else if (command == "decrease-key") {
      int k;
      int64_t x;
      int64_t y;
      std::cin >> k >> x >> y;
      DecreaseKey(heaps[k], x, y);
    }
  }
  delete[] heaps;
  return 0;
}

• Язык решений — GNU C++20.
• Лимит 1 секунда; память 128 МБ в задачах A, B, D, F и 256 МБ в C и E.
• Каждая задача оценивается автоматически по тестам на sort-me.org.
• В задаче B обязательна пирамидальная сортировка.

Решения отправляются на sort-me.org: откройте задачу, прикрепите файл с кодом и нажмите «Отправить». Дедлайн указан в таймере контеста.