Это сложная версия задачи. Единственное различие между двумя версиями заключается в ограничениях на \(t\), \(m\) и сумму \(m\). Вы можете делать взломы, только если обе версии задачи решены.
Алиса и Боб играют в очередную игру на массиве \(a\) длины \(n\). Алиса начинает с пустого массива \(c\). Оба игрока ходят по очереди, причем Алиса начинает первой.
В свой ход Алиса выбирает один элемент из \(a\), добавляет его в \(c\), а затем удаляет из \(a\).
В свой ход Боб выбирает не более \(k\) элементов из \(a\), а затем удаляет их из \(a\).
Игра заканчивается, когда массив \(a\) становится пустым. Счет Алисы определяется как MEX\(^\dagger\) элементов \(c\). Алиса хочет максимизировать свой счет, а Боб — минимизировать его. Найдите итоговый счет Алисы, если оба игрока играют оптимально.
Массив будет дан в сжатом формате. Вместо того, чтобы давать элементы, присутствующие в массиве, мы будем давать их частоты. Формально, вам будет дано \(m\) — максимальный элемент массива, а затем \(m + 1\) целых чисел \(f_0, f_1, \ldots, f_{m}\), где \(f_i\) представляет собой количество раз, которое \(i\) встречается в массиве \(a\).
\(^\dagger\) \(\operatorname{MEX}\) (minimum excludant) массива целых чисел определяется как наименьшее целое неотрицательное число, которое не встречается в массиве. Например:
- MEX массива \([2,2,1]\) равен \(0\), потому что \(0\) не принадлежит массиву.
- MEX массива \([3,1,0,1]\) равен \(2\), потому что \(0\) и \(1\) принадлежат массиву, а \(2\) — нет.
- MEX массива \([0,3,1,2]\) равен \(4\), потому что \(0\), \(1\), \(2\) и \(3\) принадлежат массиву, а \(4\) — нет.
Выходные данные
Для каждого набора входных данных найдите счет Алисы, если оба игрока играют оптимально.
Примечание
В первом наборе входных данных массив \(a\) равняется \([0, 0, 0, 0, 1, 1, 1, 1, 1]\). Возможная игра со счетом \(2\) выглядит следующим образом:
- Алиса выбирает элемент \(0\). После этого хода \(a = [0, 0, 0, 1, 1, 1, 1, 1]\) и \(c=[0]\).
- Боб выбирает для удаления \(3\) элемента \(0\), \(0\) и \(1\). После этого хода \(a = [0, 1, 1, 1, 1]\) и \(c=[0]\).
- Алиса выбирает элемент \(1\). После этого хода \(a = [0,1,1,1]\) и \(c=[0,1]\).
- Боб удаляет оставшиеся \(4\) элемента \(0\), \(1\), \(1\) и \(1\). После этого хода \(a=[\,]\) и \(c=[0,1]\).
В конце массив \(c=[0,1]\), его MEX равен \(2\). Обратите внимание, что это пример игры и не обязательно представляет собой оптимальную стратегию для обоих игроков.
Во втором наборе входных данных Алиса может выбрать \(0\) в свой первый ход, гарантируя, что ее счет будет не меньше \(1\). Боб может удалить все копии элемента \(1\) в свой первый ход, гарантируя тем самым, что счет Алисы не будет превосходить \(1\). Таким образом, счет Алисы равен \(1\), если оба игрока играют оптимально.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 4
4 5
2 1000000000
1000000000 1000000000 1000000000
3 2
2 3 100 1
1 1
2 2
3 1
1 1 1 1
|
2
1
3
2
1
|