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; } ``` 众所周知，当上述函数在传入一个单调不递减的数组 $\texttt p$ 且 $\texttt{target}$ 在数组 $\texttt p$ 中出现过，那么会返回 $\texttt{true}$。然而，当 $\texttt p$ 不存在单调性时则不然。 给定正整数 $n$ 和一个数组 $b_1,\dots,b_n \in \{\texttt{true},\texttt{false}\}$。数据保证存在一个正整数 $k$，使得 $n=2^k-1$。 规定 $S(p)$ 为 $i \in \{1,\dots,n\}$ 时 $\texttt{binary\_search(n, p, i)}$ 返回值不为 $b_i$ 的个数。你的任务是求一个 $\{1,\dots,n\}$ 的排列 $p$，使得 $S(p)$ 尽可能小（具体请见评分规则）。

**本题有多组数据。** 第一行一个正整数 $T$，表示数据组数。 每组数据的第一行包含一个正整数 $n$。第二行包含一个长度为 $n$ 的字符串（只含有字符 `0` 和 `1` 且无空格）。其中当第 $i$ 个字符为 `1` 时，则 $b_i=\texttt{true}$，否则 $b_i=\texttt{false}$。

输出 $T$ 行，每行输出求得的排列 $p$。**Special Judge 对输出格式要求非常严格，每行行末不能有空格等多余字符。**

#### 评分规则 - 当一个子任务中的所有排列 $p$ 均满足 $S(p) \le 1$ 时，得分为该子任务总分的 $100\%$。 - 否则当一个子任务中的所有排列 $p$ 均满足 $0 \le S(p) \le \lceil \log_2 n \rceil$ 时，得分为该子任务总分的 $50\%$。 由于洛谷评分机制，每个测试点的实际得分为上式下取整的结果。例如，当该子任务的总分为 $3$ 且该子任务中的所有排列 $p$ 均满足 $0 \le S(p) \le \lceil \log_2 n \rceil$ 时，得分为 $1$ 而不是 $1.5$。 #### 样例 1 解释 前两组数据满足 $S(p)=0$。 第三组数据中 $S(p)=1$，因为 $\texttt{binary\_search(n, p, 2)}=\texttt{true} \neq b_2$。 第四组数据中 $S(p)=1$，因为 $\texttt{binary\_search(n, p, 4)}=\texttt{true} \neq b_4$。 #### 样例 2 解释 两组数据均满足 $S(p)=0$。 #### 数据规模与约定 **本题采用捆绑测试。** - 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$ 且 $b_i$ 数据随机。 - Subtask 6（30 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le T \le 7000$，$1 \le \sum n \le 10^5$，$\forall n \in \{n|n=2^k-1,k \in \N^*\}$。 #### 说明 本题译自 [eJOI2021](https://sepi.ro/ejoi/2021) Day 2 A BinSearch。欢迎通过私信或发帖的方式对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/5fdi0fvc) 进行 hack。