T533508 「GFOI Round 2」Colors (English ver.)
题目背景
**[Chinese statement](https://www.luogu.com.cn/problem/P11282). You must submit your code at the Chinese version of the statement.**
> 世界が鮮やかに 染まって
题目描述
There are $n$ balls arranged in a row, numbered from $1$ to $n$ from left to right. Initially, each ball is red. The initial weight of the $i$-th ball is $p_i$. **It is guaranteed that $\bm{n}$ is an odd number and that $\bm{p}$ is a permutation of $\bm{1 \sim n}$.**
You need to perform exactly $\frac{n - 1}{2}$ operations. In one operation, you must:
- Choose a **red** ball $i$ such that there is at least one red ball in the range $1 \sim i - 1$ and at least one red ball in the range $i + 1 \sim n$.
- Let $j$ be the largest integer such that $j < i$ and the ball at position $j$ is red, and let $k$ be the smallest integer such that $k > i$ and the ball at position $k$ is red. You will paint both balls $i$ and $k$ blue.
- Then, perform exactly one of the following two operations:
- Modify $p_j$ (the weight of ball $j$) to $\max(p_i, p_j, p_k)$;
- Modify $p_j$ (the weight of ball $j$) to $\min(p_i, p_j, p_k)$.
After performing $\frac{n - 1}{2}$ operations, there will be exactly one red ball left.
You need to determine for each positive integer $x$ in the range $1$ to $n$ whether it is possible to perform the operations in such a way that the weight of the remaining red ball is $x$.
输入格式
无
输出格式
无
说明/提示
#### Sample Explanation
For the first test case, the initial state of the balls (color and weight) is $\color{red}{3\ 2\ 1}$.
You need to perform $1$ operation. In this operation, you can only choose ball $2$ and paint both balls $2$ and $3$ blue.
- If you choose to modify $p_1$ to $\max(p_1, p_2, p_3)$, then after the operation, the state of the balls will be $\color{red}{3}\ \color{blue}{2\ 1}$, and the weight of the remaining red ball will be $3$;
- If you choose to modify $p_1$ to $\min(p_1, p_2, p_3)$, then after the operation, the state of the balls will be $\color{red}{1}\ \color{blue}{2\ 1}$, and the weight of the remaining red ball will be $1$.
Thus, you will output a $01$ string that has $1$s at the $1$st and $3$rd positions, and $0$s in the other positions.
For the second test case, it can be easily proven that the weight of the remaining red ball can take all positive integers from $1$ to $n$. Here is an example of a sequence of operations that results in the remaining red ball having a weight of $2$:
- The initial state of the balls is $\color{red}{1\ 3\ 5\ 2\ 4}$.
- Choose ball $2$, paint both balls $2$ and $3$ blue, and set $p_1$ to $\max(p_1, p_2, p_3) = 5$. After this operation, the state of the balls becomes $\color{red}{5}\ \color{blue}{3\ 5}\ \color{red}{2\ 4}$.
- Choose ball $4$, paint both balls $4$ and $5$ blue, and set $p_1$ to $\min(p_1, p_4, p_5) = 2$. After this operation, the state of the balls becomes $\color{red}{2}\ \color{blue}{3\ 5\ 2\ 4}$.
#### Subtasks and Constraints
| Subtask ID | $n \le$ | $\sum n \le$ | Special Properties | Score |
| :-: | :-: | :-: | :-: | :-: |
| $1$ | $5$ | $10^4$ | No | $16$ |
| $2$ | $19$ | $10^4$ | No | $19$ |
| $3$ | $99$ | $10^6$ | No | $19$ |
| $4$ | $10^6 - 1$ | $10^6$ | A | $3$ |
| $5$ | $10^6 - 1$ | $10^6$ | No | $43$ |
- Special Property A: $p_i = i$.
For all tests, it is guaranteed that:
- $1 \le T \le 10^5$;
- $3 \le n \le 10^6 - 1$ and $n$ is an odd number;
- $\sum n \le 10^6$;
- $p$ is a permutation of $1 \sim n$.