P9054 [CTT Mutual Test 2022] Heartbeat Permutation Graph.

The distributed files can be found in the attachment.

Note: In this problem, all sequence indices start from $1$. What does the robot heartbeats look like when arranged into a graph? You have a competitive programming robot that beats $n$ times per minute. The intensity of the $i$-th beat is $a_i$. Here, $a_1 \sim a_n$ is exactly a permutation of $1 \sim n$. Let $A_i$ be the sequence obtained by deleting the $i$-th element from sequence $a$, i.e., $A_i = [a_1,\dots,a_{i-1},a_{i+1},\dots,a_n]$. For a sequence $p$ with all distinct elements, let $G(p)$ be an undirected graph with $|p|$ vertices, numbered $1 \sim |p|$. For every pair of positive integers $1 \le i \lt j \le |p|$, if for all $k \in [i,j] \cap \mathbb{Z}$, we have $p_k \in [\min(p_i,p_j), \max(p_i,p_j)]$, then there is an edge between vertex $i$ and vertex $j$ in $G(p)$. Let $F(p)$ be the length of the shortest path from vertex $1$ to vertex $|p|$ in $G(p)$, where the length of a path is defined as its number of edges. Let $f(a) = [F(A_1), F(A_2), \dots, F(A_n)]$. Given a sequence $[b_1,\dots,b_n]$ of length $n$, please find any permutation $a$ of $1 \sim n$ such that $f(a) = b$. **It is guaranteed that a solution exists.** In some subtasks, the competitive programming robot little G will give you some “hints”. Let $G_0 = G(a)$. Let $path_0$ be the set of vertices visited by some shortest path from $1$ to $n$ in $G_0$. Let $path_j$ be the set of vertices visited by some shortest path from the start vertex to the end vertex in $G(A_j)$ (note: for convenience, the vertex indices in $path_j$ still use the indices from the original graph, see Sample 2). Then little G may additionally tell you all $path_j$ (including $path_0$), or may only tell you $path_0$, or may provide no hints. See the input format for details. It is guaranteed that the given hints are correct, i.e., there exists a permutation that satisfies all hints. The distributed files include `checker.cpp`, which you can use to check whether your output is correct. Usage: `./checker input output output`, where `input` and `output` are the input file and your output. `testlib.h` is also provided; please compile the checker with `testlib.h` placed in the same directory as the checker.

The first line contains two positive integers: the subtask number $S$ and the number of test cases $T$. Then follow $T$ test cases. Each test case is: - The first line contains one positive integer $n$. - The second line contains $n$ positive integers $b_1,\dots,b_n$. **In particular,** 1. If $S = 5$, then for each test case, there will be an additional $n+1$ lines. In these $n+1$ lines, the $i$-th line is a binary string $c_i$ of length $n$, where $c_{i,j} = [j \in path_{i-1}]$. 2. If $S = 6$, then for each test case, there will be a third line containing a binary string $c$ of length $n$, where $c_i = [i \in path_0]$. Notes: 1. Even if your program does not need the hints, when $S = 5$ or $S = 6$ you still need to read the array $c$. 2. For the same input $b$, the valid $a$ may not be unique, and thus $c$ may also not be unique. Your output is **not required** to satisfy the constraints given by our $c$; it will be judged correct as long as it satisfies the constraints of $b$. Different variables on the same line are separated by a single space.

For each test case, output one line with $n$ positive integers: the permutation $a$ you found.

**Explanation of Sample 1** Consider the first test case in the sample. One solution is $a = [1,2,4,3]$. Then $A_1, A_2, A_3, A_4$ are $[2,4,3]$, $[1,4,3]$, $[1,2,3]$, $[1,2,4]$, respectively. The edges in the four graphs $G(A_1), G(A_2), G(A_3), G(A_4)$ are: - $G(A_1)$: $(1,2), (2,3)$. Therefore $F(A_1) = 2$. - $G(A_2)$: $(1,2), (2,3)$. Therefore $F(A_2) = 2$. - $G(A_3)$: $(1,2), (1,3), (2,3)$. Therefore $F(A_3) = 1$. - $G(A_4)$: $(1,2), (1,3), (2,3)$. Therefore $F(A_4) = 1$. So $f(a) = [2,2,1,1]$, which matches the input. The valid $a$ is not unique. For example, $a = [4,3,1,2]$ is also correct. **Explanation of Sample 2** The permutation in this sample is the same as the first test case in Sample 1, but this sample includes the hints for subtask $5$. Note that when giving $path_j$, the original indices are still used. For example, after deleting $1$, the vertices on the new shortest path are numbered $2 \to 3 \to 4$. **Explanation of Sample 3** The permutation in this sample is the same as the first test case in Sample 1, but this sample includes the hints for subtask $6$. **Constraints** For all testdata: $1 \le T \le 4 \times 10^4$, $4 \le n \le 10^5$, $\sum n \le 5 \times 10^5$. - Subtask 1 ($7$ points): $T \le 250$, $n \le 7$. - Subtask 2 ($5$ points): $b_i = 1$. - Subtask 3 ($10$ points): $n \ge 90000$, and it is guaranteed that there exists a solution satisfying $a_1 = 1, a_n = n$. - Subtask 4 ($7$ points): $n \ge 90000$, and it is guaranteed that there exists a solution satisfying $a_2 = 1, a_{n-1} = n$. - Subtask 5 ($15$ points): $n \le 100$, $\sum n^3 \le 3 \times 10^6$, with hints for all $path_j$. - Subtask 6 ($15$ points): $n \le 100$, $\sum n^3 \le 3 \times 10^6$, with a hint for $path_0$. - Subtask 7 ($15$ points): $n = 100$, $T = 3$, with $5$ test points. The input is generated by picking a random $a$ and then computing $f(a)$ as the input. - Subtask 8 ($25$ points): $n \le 100$, $\sum n^3 \le 3 \times 10^6$. - Subtask 9 ($1$ point): No special constraints. Translated by ChatGPT 5