Problem Description

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).

Input Format

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 Format

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.

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

Hint

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 Day 2 A BinSearch. You are welcome to hack the self-written Special Judge via private message or by making a post.

Translated by ChatGPT 5