Like the Bitset

The condition looks scarier than it is. The trick is to stop staring at all intervals, because most of them are just noisy extras.

For a position $i$ with $s_i=1$, we need:

In every interval of length at least $k$ containing $i$, $p_i$ is not the maximum.

Key simplification: it is enough to check intervals of length exactly $k$.

Why? Take any interval $[l,r]$ with length at least $k$ that contains $i$. Inside it, we can always choose a length-$k$ subarray that still contains $i$. If $p_i$ is not the maximum inside that smaller subarray, then it definitely is not the maximum inside the larger interval either.

So the real requirement is:

For every index $i$ where $s_i=1$, every length-$k$ window containing $i$ must contain some value larger than $p_i$.

Now look at one length-$k$ window.

If this window contains only 1s, then no construction can work. Among those $k$ positions, one has the largest value. That position is a 1, and in this exact length-$k$ interval it is the maximum. That violates the rule immediately. No clever permutation magic saves it. Math says no; pack it up.

So a necessary condition is:

$$\text{there is no run of } k \text{ consecutive `1`s.}$$

Now the nice part: this condition is also sufficient.

Suppose every length-$k$ window contains at least one 0. Then construct the permutation like this:

• every 1 position gets one of the small values,
• every 0 position gets one of the large values.

For example, if there are $c$ ones, give the ones values $1,2,\dots,c$, and give the zeros values $c+1,c+2,\dots,n$.

Now take any constrained position $i$ with $s_i=1$, and take any length-$k$ window containing it. Since there are no $k$ consecutive ones, this window has at least one 0. That 0 has a larger value than every 1, including $p_i$. Therefore $p_i$ is not the maximum.

And since length-$k$ windows imply all longer intervals, the whole condition is satisfied.

So the full algorithm is brutally simple:

1. Scan the string and compute the longest consecutive run of 1s.
2. If it is at least $k$, print NO.
3. Otherwise, print YES and build a permutation where:
   • 1 positions receive increasing small values,
   • 0 positions receive increasing large values.

The values do not need fancy ordering inside each group. The only thing that matters is:

$$\max(\text{values on `1` positions}) < \min(\text{values on `0` positions}).$$

That single inequality does all the heavy lifting.

Complexity: Each test case is processed in $O(n)$ time, and the total input size is bounded by $2\cdot 10^5$, so this easily fits.