P1087 [NOIP 2004 Junior] FBI Tree

We can divide strings composed of 0 and 1 into three categories: an all-0 string is called a B string, an all-1 string is called an I string, and a string that contains both 0 and 1 is called an F string. An FBI tree is a binary tree whose node types are F, B, and I. Given a binary string $S$ of length $2^N$, an FBI tree $T$ can be constructed recursively as follows: 1. Let $R$ be the root of $T$, and set its type to be the same as the type of $S$. 2. If the length of $S$ is greater than 1, split $S$ in the middle into equal-length left and right substrings $S_1$ and $S_2$. Construct the left subtree $T_1$ of $R$ from $S_1$, and the right subtree $T_2$ of $R$ from $S_2$. Given a binary string of length $2^N$, construct an FBI tree using the method above and output its postorder traversal sequence.

The first line contains an integer $N (0 \le N \le 10)$. The second line contains a binary string of length $2^N$.

A single string, i.e., the postorder traversal sequence of the FBI tree.

For 40% of the testdata, $N \le 2$. For all the testdata, $N \le 10$. This is the 3rd problem of NOIP 2004 Junior. Translated by ChatGPT 5