Mexes


Submit solution


Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Given an integer \(n\) and a binary string \(a\) of \(n+1\) characters, find the lexicographically smallest permutation \(P\) of \({0,1,2,...,n-1}\) that satisfies the following conditions for all \(i\) \(0 \leq i \leq n\) :

if \(a_i = 0\) : No contiguous segment of \(P\) has mex equal to \(i\)

if \(a_i = 1\) : there exists at least one contiguous segment of \(P\) that has mex equal to \(i\)

Input Specification

The first line contains the number of test cases \(t\) \((1\leq t \leq 10^4)\). Description of the test cases follows.

The first line of each test case contains a single integer \(n\) \((3 \leq n \leq 3.10^5)\)

The second line of each test case contains the binary string \(a\) of size equal to \(n+1\).

It is guaranteed that the sum of \(n\) over all test cases does not exceed \(3.10^5\).

Output Specification

For each test case print (case sensitive):

  • "Yes" if there exists a permutation P that satisfies the conditions described in the statement,followed by the permutation P on a separate line.
  • "No" otherwise.

Sample input

1
7
00100110

Sample output

No

Scoring

\begin{array}{|c|c|c|} \hline \text{Group} & \text{Points} & \text{Constraints} \cr \hline 1 & 20 & 3 \leq n \leq 8 \cr \hline 2 & 45 & \text{Sum of \(n\) over all test cases does not exceed 5000} \cr \hline 3 & 35 & \text{ No additional constraints } \cr \hline \end{array}


Comments

There are no comments at the moment.