题目描述

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 对输出格式要求非常严格，每行行末不能有空格等多余字符。

4
3
111
7
1111111
3
000
7
0000000

1 2 3
1 2 3 4 5 6 7
3 2 1
7 6 5 4 3 2 1

2
3
010
7
0010110

3 2 1
7 3 1 5 2 4 6

提示

评分规则

• 当一个子任务中的所有排列 $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 Day 2 A BinSearch。欢迎通过私信或发帖的方式对自行编写的 Special Judge 进行 hack。