Рассмотрим массив $$$a$$$, состоящий из $$$n$$$ различных целых чисел. Декартово дерево массива $$$a$$$ определяется как уникальное бинарное дерево$$$^{\text{∗}}$$$, которое удовлетворяет следующим условиям:
Обозначим за $$$r(a)$$$ корень декартова дерева, а за $$$f_a(i)$$$ родителя $$$i$$$ в декартовом дереве.
Определим $$$E_a=\{(i,f_a(i)) \mid 1 \le i \le n, i \ne r(a)\}$$$.
Рассмотрим перестановку$$$^{\text{§}}$$$ $$$q$$$ длины $$$n$$$. Определим серию массивов $$$p_1,p_2,\ldots,p_n$$$ следующим образом:
Теперь вам даны $$$n$$$ и $$$S=\bigcup\limits_{i=1}^n E_{p_i}$$$. Чтобы минимизировать ввод, $$$S$$$ будет представлен в виде бинарной матрицы $$$n \times n$$$ $$$s$$$. Обозначим $$$s_{i,j}$$$ как $$$j$$$-й символ $$$i$$$-й строки. $$$s_{i,j}=1$$$ тогда и только тогда, когда $$$(i,j) \in S$$$.
Пожалуйста, найдите любую перестановку $$$q$$$, такую что $$$S$$$ может быть получено описанным выше процессом. Гарантируется, что наборы входных данных сгенерированы так, чтобы всегда существовала допустимая перестановка $$$q$$$.
$$$^{\text{∗}}$$$Бинарное дерево — это корневое дерево, в котором у каждой вершины не более $$$2$$$ детей, называемых левым и правым ребенком.
$$$^{\text{†}}$$$Родителем вершины $$$v$$$ называется первая вершина на простом пути от $$$v$$$ до корня. У корня нет родителя.
$$$^{\text{‡}}$$$Поддеревом вершины $$$v$$$ называется подграф, состоящий из вершины $$$v$$$, всех ее потомков, и всех ребер между ними.
$$$^{\text{§}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 3000$$$) — длина перестановки $$$q$$$, которую вам нужно найти.
$$$i$$$-я из следующих $$$n$$$ строк содержит бинарную строку длины $$$n$$$, представляющую $$$i$$$-ю строку матрицы $$$s$$$. Гарантируется, что $$$s_{i,i} = 0$$$ для всех $$$1 \le i \le n$$$.
Гарантируется, что наборы входных данных сгенерированы так, чтобы всегда существовала допустимая перестановка $$$q$$$.
Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$9 \cdot 10^6$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$q_1,q_2,\ldots,q_n$$$, представляющих найденную вами перестановку $$$q$$$.
320110301110001040101001010010110
1 22 1 33 1 2 4
| Codeforces Round 1077 (Div. 1) |
|---|
| Закончено |
