P10857 [MX-X2-T6] "Cfz Round 4" Ad-hoc Master

I do not need to be so fired up every day, but I can keep living while searching for you.

Given a positive integer $h$. We define $n=2^h-1$. Now, for every positive integer $u$ not greater than $n$ and every positive integer $k$ not greater than $2h-2$, the value of $f_{u,k}$ is given. You need to construct a pair $(r,w)$ satisfying $1 \le r \le n$, $0 \le w \lt 2^{30}$, such that there exists a **full** binary tree $T$ with $h$ levels satisfying: - The labels of all nodes in the full binary tree $T$ form a permutation of $1 \sim n$, and each node has a weight. - The root of the full binary tree $T$ is node $r$. - The weight of each node in the full binary tree $T$ is a non-negative integer less than $2^{30}$, and the weight of the root node is $w$. - For every positive integer $u$ not greater than $n$ and every positive integer $k$ not greater than $2h-2$, the **xor sum** of the weights of all nodes $v$ satisfying $\operatorname{dis}(u,v)=k$ is $f_{u,k}$. In particular, if there is no node $v$ satisfying the condition, then $f_{u,k}=0$ must hold. Here, $\operatorname{dis}(u,v)$ is the number of edges on the simple path between node $u$ and node $v$. In particular, $\operatorname{dis}(u,u)=0$. It is guaranteed that there exists at least one pair $(r,w)$ that satisfies the requirements.

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. Then each test case is given as follows. For each test case: - The first line contains a positive integer $h$. - The next $n$ lines: line $u$ contains $2h-2$ integers, where the $k$-th integer represents the value of $f_{u,k}$.

For each test case, output one line with two integers, representing $r$ and $w$ in your constructed pair $(r,w)$. - If your constructed pair $(r,w)$ satisfies the requirements, you get $100\%$ of the score for that test point. - Otherwise, if your constructed pair $(r,w)$ does not satisfy the requirements, but there exists a valid pair $(r',w')$ such that $r'=r$, you get $50\%$ of the score for that test point. - Otherwise, if your constructed pair $(r,w)$ does not satisfy the requirements, but there exists a valid pair $(r',w')$ such that $w'=w$, you get $50\%$ of the score for that test point. - Otherwise, you get no score for that test point.

**[Sample Explanation #1]** For the first test case: When the constructed pair $(r,w)=(2,1)$, there exists a binary tree as shown in the figure that satisfies the requirements, where the weights of nodes $1,2,3$ are $2,1,0$ respectively.  When you output `2 2`, you can get $50\%$ of the score for that test point, because although $(r,w)=(2,2)$ does not satisfy the requirements, there exists a valid pair $(r',w')=(2,1)$ such that $r'=r=2$. When you output `1 1`, you can also get $50\%$ of the score. But when you output `1 2`, you will get no score for that test point. **[Constraints]** Let $\sum n$ denote the sum of $n$ within a single test point. For all testdata, $1\le T \le 1000$, $2 \le h \le 16$, $\sum n \le 2^{16}$, $0 \le f_{u,k}\lt2^{30}$, and it is guaranteed that there exists at least one valid pair $(r,w)$. **This problem uses bundled judging.** - Subtask 1 (20 points): $h=2$. - Subtask 2 (20 points): Satisfies a special property. - Subtask 3 (60 points): No special restrictions. Special property: There exists a pair $(r,w)$ satisfying $1 \le r \le n$, $0 \le w \lt 2^{30}$, and based on this, there exists a full binary tree that satisfies the requirements, where the weights of all nodes are equal to $w$. Translated by ChatGPT 5