Wrong Binary Search

Let's pin down what "stable" actually means, because the random midpoint is a distraction. Random? Nah. Since $x$ must work for every possible choice of midpoint, we should treat the midpoint choices as hostile.

Suppose value $x$ is placed at position $pos[x]$.

During the search, if the current interval still contains $pos[x]$ and we choose some midpoint $m$:

• If $m < pos[x]$, then to keep $x$ inside the interval, the algorithm must move right. That requires $p_m < x$.
• If $m > pos[x]$, then to keep $x$ inside the interval, the algorithm must move left. That requires $p_m > x$.
• If $m=pos[x]$, we find $x$.

Since the first midpoint can be any position from $1$ to $n$, this condition must already hold globally:

$$\forall i < pos[x],\ p_i < x$$

and

$$\forall i > pos[x],\ p_i > x.$$

That is the whole game.

Key Consequence

There are exactly $x-1$ values smaller than $x$. If all positions before $pos[x]$ contain values smaller than $x$, then there can be at most $x-1$ such positions:

$$pos[x]-1 \le x-1.$$

So $pos[x]\le x$.

Similarly, all positions after $pos[x]$ must contain values larger than $x$. There are exactly $n-x$ larger values, so:

$$n-pos[x] \le n-x,$$

which gives $pos[x]\ge x$.

Therefore:

$$pos[x]=x.$$

So if $x$ is stable, it must be sitting at its own index. More strongly, the prefix before it must be exactly the smaller values and the suffix after it must be exactly the larger values. In permutation language, stable values are fixed points that are also valid split points.

How to Construct the Exact Pattern

Now look at the target string $s$.

If $s_i=1$, we want value $i$ stable. The easiest way is to leave $p_i=i$.

If $s_i=0$, we want value $i$ unstable. The easiest way is to make sure $p_i\ne i$ by moving it somewhere else.

But we must not accidentally break the stable 1 values. Since a stable value $i$ needs all smaller values on the left and all larger values on the right, we cannot move values across a 1 position. A 1 acts like a wall: values less than it stay left, values greater than it stay right.

So the permutation naturally splits into maximal consecutive blocks of equal characters in $s$:

• For a block of 1s, keep everything fixed.
• For a block of 0s, rotate the values inside that block by one position.

Example: positions $[l,l+1,\dots,r]$ are all 0. Put

$$p_l=l+1,\ p_{l+1}=l+2,\dots,\ p_{r-1}=r,\ p_r=l.$$

This keeps all values inside the same block, so it does not cross any 1 wall. Every position in the block changes value, so every zero value becomes unstable.

When Is It Impossible?

A 0 block of length $1$ is fatal.

If position $i$ is a lone zero, then both neighbors, if they exist, are 1 walls. Value $i$ cannot move left or right without crossing a stable value's boundary. But if $p_i=i$, then $i$ is stable. So there is no way out. Tiny block, big pain.

So the condition is simple:

Every maximal block of 0s must have length at least $2$.

If that holds, rotate each zero block and leave one blocks fixed. Done.