P8168 [eJOI 2021] BinSearch

```cpp bool binary_search(int n, int p[], int target){ int left = 1, right = n; while(left < right){ int mid = (left + right) / 2; if(p[mid] == target) return true; else if(p[mid] < target) left = mid + 1; else right = mid - 1; } if(p[left] == target) return true; else return false; } ``` As everyone knows, when the function above is given a monotone non-decreasing array $\texttt p$ and $\texttt{target}$ appears in the array $\texttt p$, it will return $\texttt{true}$. However, if $\texttt p$ is not monotone, this is no longer guaranteed. You are given a positive integer $n$ and an array $b_1,\dots,b_n \in \{\texttt{true},\texttt{false}\}$. The testdata guarantees that there exists a positive integer $k$ such that $n=2^k-1$. Define $S(p)$ as the number of indices $i \in \{1,\dots,n\}$ for which the return value of $\texttt{binary\_search(n, p, i)}$ is not equal to $b_i$. Your task is to find a permutation $p$ of $\{1,\dots,n\}$ such that $S(p)$ is as small as possible (see the scoring rules for details).

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case, the first line contains a positive integer $n$. The second line contains a string of length $n$ (only characters `0` and `1`, with no spaces). If the $i$-th character is `1`, then $b_i=\texttt{true}$; otherwise $b_i=\texttt{false}$.

Output $T$ lines. For each line, output the permutation $p$ you found. **This problem uses Special Judge, and the output format is very strict: there must be no extra characters such as trailing spaces at the end of each line.**

#### Scoring Rules - If for a subtask, all permutations $p$ satisfy $S(p) \le 1$, then you get $100\%$ of that subtask's total score. - Otherwise, if for a subtask, all permutations $p$ satisfy $0 \le S(p) \le \lceil \log_2 n \rceil$, then you get $50\%$ of that subtask's total score. Due to Luogu's scoring mechanism, the actual score for each test point is the floor of the value above. For example, if a subtask's total score is $3$ and all permutations $p$ in that subtask satisfy $0 \le S(p) \le \lceil \log_2 n \rceil$, then the score is $1$ rather than $1.5$. #### Sample 1 Explanation In the first two test cases, $S(p)=0$. In the third test case, $S(p)=1$, because $\texttt{binary\_search(n, p, 2)}=\texttt{true} \neq b_2$. In the fourth test case, $S(p)=1$, because $\texttt{binary\_search(n, p, 4)}=\texttt{true} \neq b_4$. #### Sample 2 Explanation In both test cases, $S(p)=0$. #### Constraints and Notes **This problem uses bundled tests.** - Subtask 1 (3 pts): $b_i=\texttt{true}$. - Subtask 2 (4 pts): $b_i=\texttt{false}$. - Subtask 3 (16 pts): $1 \le n \le 7$. - Subtask 4 (25 pts): $1 \le n \le 15$. - Subtask 5 (22 pts): $n=2^{16}-1$ and the $b_i$ testdata is random. - Subtask 6 (30 pts): No special restrictions. For $100\%$ of the testdata, $1 \le T \le 7000$, $1 \le \sum n \le 10^5$, $\forall n \in \{n|n=2^k-1,k \in \N^*\}$. #### Notes This problem is translated from [eJOI2021](https://sepi.ro/ejoi/2021) Day 2 A BinSearch. You are welcome to hack the self-written [Special Judge](https://www.luogu.com.cn/paste/5fdi0fvc) via private message or by making a post. Translated by ChatGPT 5