题目描述

本题译自 eJOI2021 Problem D. Binsearch

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;
}

众所周知，如果 $p$ 恰好是排好序的，这段代码将返回 $\texttt{true}$，当且仅当 $\texttt{target}$ 在 $\texttt p$ 中出现。换句话说，如果 $\texttt p$ 不是排好序的，那么可能就不是这样了。

给一个正整数 $n$ 和一个序列 $b_1,\ldots ,b_n\in \{\texttt{true},\texttt{false}\}$。保证存在一个正整数 $k$ 满足 $n=2^k-1$。你必须生成一个 $\{1,\ldots,n\}$ 的排列 $p$ 满足一些条件。令 $S(p)$ 为对于 $i\in\{1,\ldots,n\}$，调用 \texttt{binary_search(n, p, i)} 时不返回 $b_i$ 的 $i$ 的个数。你必须找到一个 $p$ 使得 $S(p)$ 尽可能小（详见「数据范围与提示」中的说明）。

注意，一个 $\{1,\ldots,n\}$ 的排列是指一个 $n$ 个整数组成的数列，满足从 $1$ 到 $n$ 的整数在数列中恰好出现一次。

输入格式

输入包含多组数据。第一行包含一个整数 $T$，表示测试数据组数。接下来有 $T$ 组数据。

对于每组数据，第一行一个整数 $n$，第二行一个长度为 $n$ 且只包含 $01$ 的字符串。这些字符不用空格隔开。如果第 $i$ 个字符为 $1$，则 $b_i=\texttt{true}$，如果是 $0$，则 $b_i=\texttt{false}$。

输出格式

输出包含对于这 $T$ 组数据的答案。每行一个排列 $p$，表示对该组测试数据的答案。

4
3
111
7
1111111
3
000
7
000000000

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

数据范围与提示

• 令 $\sum n$ 表示在输入中所有 $n$ 的和
• $1\le \sum n\le 10^5$
• $1\le T\le 7000$
• 存在 $k\in \mathbb{N},k>0$，满足 $n=2^k-1$
• 如果对于子任务的所有测试点，都有 $S(p)\le 1$，那么你会得到该子任务的全部分数。
• 否则，如果对于子任务的所有测试点，都有 $0\le S(p)\le \lceil\log_2 n\rceil$（即 $1\le 2^{S(p)}\le n+1$），那么你会得到该子任务 $50\%$ 的分数。