Олимпиадный тренинг

Задача . C. Mocha и прогулка

Задача

Mocha живет в городском уезде Чжицзян. В уезде $n+1$ поселение и $2n-1$ ориентированная дорога.

Все дороги имеют один из двух типов:

$n-1$ дорога идет от поселения $i$ к поселению $i+1$, для всех $1\leq i \leq n-1$.
$n$ дорог описываются последовательностью $a_1,\ldots,a_n$. Если $a_i=0$, то $i$-я из этих дорог идет от поселения $i$ к поселению $n+1$, иначе она идет от поселения $n+1$ к поселению $i$, для всех $1\leq i\leq n$.

Mocha собирается в поход вместе с Taki. Чтобы поход не был скучным, они собираются посетить каждое поселение ровно один раз. Они могут начать и закончить в любых поселениях. Можете помочь составить им план похода?

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

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

Первая строка набора входных данных содержит одно целое число $n$ ($1 \le n \le 10^4$), что означает, что всего поселений $n+1$.

Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 1$). Если $a_i=0$, то есть дорога из поселения $i$ в поселение $n+1$. Если $a_i=1$, то есть дорога из поселения $n+1$ в поселение $i$.

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

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

Для каждого набора входных данных выведите одну строку с $n+1$ целыми числами, где $i$-е число — поселение, которое они должны посетить $i$-м по порядку. Если ответа не существует, выведите $-1$.

Если существует несколько решений, выведите любое из них.

Примечание

В первом наборе входных данных уезд выглядит следующим образом:

$\text{[math]}$

Возможные ответы: $(1 \to 4 \to 2 \to 3)$ или $(1 \to 2 \to 3 \to 4)$.

Во втором наборе входных данных уезд выглядит следующим образом:

$\text{[math]}$

Возможные ответы — $(4 \to 1 \to 2 \to 3)$, $(1 \to 2 \to 3 \to 4)$, $(3 \to 4 \to 1 \to 2)$ и $(2 \to 3 \to 4 \to 1)$.

Примеры

№	Входные данные	Выходные данные
1	2 3 0 1 0 3 1 1 0	1 4 2 3 4 1 2 3

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет