C. Неправильный бинарный поиск
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$n$$$ и бинарная строка$$$^{\text{∗}}$$$ $$$s$$$ длины $$$n$$$.

Для перестановки$$$^{\text{†}}$$$ $$$p$$$ длины $$$n$$$ и целого числа $$$x$$$ определим $$$\text{find}(x)$$$ следующим образом в псевдокоде:

function find(int x):
    l := 1
    r := n
    while l <= r:
        пусть m — случайное число от l до r (включительно)
        if p[m] == x
            return m
        if p[m] > x:
            r := m - 1
        else:
            l := m + 1
    return undefined     // не найдено

Назовём целое число $$$x$$$ ($$$1\le x\le n$$$) стабильным, если и только если $$$\text{find}(x)$$$ всегда не равно undefined и $$$p_{\text{find}(x)}=x$$$ всегда выполняется, независимо от того, как выбирается значение $$$m$$$ в процессе выполнения псевдокода.

Вам необходимо построить перестановку $$$p$$$ длины $$$n$$$, такую что:

  • Для каждого $$$1\le i\le n$$$ целое число $$$i$$$ является стабильным если и только если $$$s_i=\mathtt{1}$$$.

Или определить, что такой перестановки не существует.

$$$^{\text{∗}}$$$Бинарная строка — это строка, в которой каждый символ является либо $$$\mathtt{0}$$$, либо $$$\mathtt{1}$$$.

$$$^{\text{†}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n \le 2\cdot 10^5$$$) — длина перестановки.

Вторая строка содержит бинарную строку $$$s$$$ длины $$$n$$$ ($$$s_i=\mathtt{0}$$$ или $$$\mathtt{1}$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных:

  • Если искомой перестановки не существует, выведите «NO» в единственной строке вывода.
  • В противном случае выведите «YES» в первой строке вывода. Затем выведите $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1\le p_i\le n$$$) во второй строке — перестановку, которую вы построили.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительные ответы.

Если есть несколько ответов, вы можете вывести любой из них.

Пример
Входные данные
6
3
111
5
00000
5
10100
7
0010000
11
00001001100
12
011100010000
Выходные данные
YES
1 2 3 
YES
2 4 3 5 1
NO
YES
2 1 3 5 7 6 4
YES
2 1 4 3 5 7 6 8 9 11 10
NO
Примечание

В первом наборе входных данных мы построили $$$p=[1,2,3]$$$. Возьмём $$$\text{find(2)}$$$ в качестве примера:

  • В начале $$$l=1$$$ и $$$r=3$$$;
  • Мы выберем $$$m$$$ как случайное целое число между $$$l=1$$$ и $$$r=3$$$.
    • Если мы выберем $$$m=1$$$:
      • $$$p_1=1 \lt 2$$$, поэтому $$$l$$$ устанавливается в $$$m + 1 = 2$$$. Теперь $$$l=2$$$ и $$$r=3$$$;
      • Мы выберем $$$m$$$ как случайное целое число между $$$l=2$$$ и $$$r=3$$$.
      • Если мы выберем $$$m=2$$$: $$$p_2=2$$$, поэтому возвращаемое значение равно $$$2$$$.
      • Если мы выберем $$$m=3$$$: $$$p_3=3 \gt 2$$$, поэтому $$$r$$$ устанавливается в $$$m-1=2$$$. Теперь $$$l=2$$$ и $$$r=2$$$, поэтому мы можем выбрать только $$$m=2$$$. $$$p_2=2$$$, поэтому возвращаемое значение равно $$$2$$$.
    • Если мы выберем $$$m=2$$$:
      • $$$p_2=2$$$, поэтому возвращаемое значение равно $$$2$$$.
    • Если мы выберем $$$m=3$$$, процесс аналогичен тому, когда выбрано $$$m=1$$$. Возвращаемое значение всегда равно $$$2$$$.
  • Таким образом, независимо от того, как $$$m$$$ выбирается в процессе, возвращаемое значение $$$\text{find}(2)$$$ всегда равно $$$2$$$.

Таким образом, $$$p_{\text{find}(2)}= p_2 = 2$$$ всегда выполняется, и целое число $$$2$$$ является стабильным.

Аналогично, мы можем показать, что целые числа $$$1$$$ и $$$3$$$ также являются стабильными. Таким образом, перестановка $$$p = [1, 2, 3]$$$ является допустимым ответом.

Во втором наборе входных данных мы построили $$$p=[2,4,3,5,1]$$$. Возьмём $$$\text{find(3)}$$$ в качестве примера:

  • В начале $$$l=1$$$ и $$$r=5$$$;
  • Мы выберем $$$m$$$ как случайное целое число между $$$l=1$$$ и $$$r=5$$$. Давайте выберем $$$m=2$$$;
  • $$$p_2=4 \gt 3$$$, поэтому $$$r$$$ устанавливается в $$$m-1=1$$$. Теперь $$$l=1$$$ и $$$r=1$$$;
  • Мы выберем $$$m$$$ как случайное целое число между $$$l=1$$$ и $$$r=1$$$. Мы можем выбрать только $$$m=1$$$;
  • $$$p_1=2 \lt 3$$$, поэтому $$$l$$$ устанавливается в $$$m + 1 = 2$$$. Теперь $$$l=2$$$ и $$$r=1$$$;
  • Поскольку $$$l \gt r$$$, цикл завершается, и возвращаемое значение равно undefined.

Таким образом, возвращаемое значение $$$\text{find}(3)$$$ равно undefined, поэтому целое число $$$3$$$ не является стабильным.

Аналогично, мы можем показать, что целые числа $$$1$$$, $$$2$$$, $$$4$$$ и $$$5$$$ также не являются стабильными. Таким образом, $$$p = [2, 4, 3, 5, 1]$$$ является допустимым ответом.

Некоторые другие перестановки, такие как $$$p=[5,4,3,2,1]$$$ и $$$p=[3,5,1,4,2]$$$, также являются допустимыми ответами. Вы можете напечатать любую из них.

В третьем наборе входных данных можно доказать, что искомой перестановки не существует.