Codeforces Round 950 (Div. 3) |
---|
Закончено |
Это упрощённая версия задачи, она отличается от усложнённой только поставленным вопросом. Простая версия требует только определить, являются ли некоторые значения ненулевыми. В сложной версии нужно определить сами значения.
Алиса и Боб делят поле. Поле представляет собой прямоугольник $$$n \times m$$$ ($$$2 \le n, m \le 10^9$$$), строки пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, столбцы пронумерованы от $$$1$$$ до $$$m$$$ слева направо. Клетка на пересечении строки $$$r$$$ и столбца $$$c$$$ обозначается как ($$$r, c$$$).
У Боба есть $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) фонтанов, все из них расположены в разных клетках поля. Алиса отвечает за разделение поля, но должна соблюсти несколько условий:
Алиса хочет разделить поле так, чтобы получить как можно больше клеток.
Боб хочет сохранить владение всеми фонтанами, но один любой из них подарить Алисе. Выведите сначала целое число $$$\alpha$$$ — максимальный возможный размер участка Алисы, если Боб не подарит ей ни один фонтан (т.е. все фонтаны останутся на участке Боба). Далее выведите $$$k$$$ неотрицательных целых чисел $$$a_1, a_2, \dots, a_k$$$, где:
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n, m \le 10^9$$$, $$$2 \le k \le 2 \cdot 10^5$$$) — размеры поля и количество фонтанов, соответственно.
Далее следуют $$$k$$$ строк, содержащие по два числа $$$r_i$$$ и $$$c_i$$$ ($$$1 \le r_i \le n$$$, $$$1 \le c_i \le m$$$) — координаты клетки с $$$i$$$-м фонтаном. Гарантируется, что все клетки различны и среди них нет ($$$n, 1$$$).
Гарантируется, что сумма $$$k$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных сначала выведите $$$\alpha$$$ — максимальный размер участка, который может принадлежать Алисе, если Боб не подарит ей ни один из фонтанов. В следующую строку выведите $$$k$$$ неотрицательных целых чисел $$$a_1, a_2, \dots, a_k$$$, где:
Если вместо $$$1$$$ вы выведите любое другое положительное число, которое помещается в 64-битный целочисленный знаковый тип, оно также будет распознано как $$$1$$$. Таким образом, решение усложнённой версии этой задачи также проходит тесты упрощённой.
52 2 31 11 22 25 5 41 22 23 44 32 5 91 21 51 12 22 42 51 42 31 36 4 46 21 31 41 23 4 52 13 21 41 32 4
1 1 0 1 11 0 1 0 1 1 0 0 1 1 0 0 0 0 0 6 1 0 0 0 1 1 1 0 0 0
Ниже приведены изображения для второго примера:
Обратите внимание, что если Боб дарит Алисе фонтан $$$1$$$ или фонтан $$$3$$$, то этот фонтан не может находиться на участке Алисы.
Название |
---|