原题

题目描述

The city where Mocha lives in is called Zhijiang. There are n+1 villages and 2n−1 directed roads in this city.

There are two kinds of roads:

n−1 roads are from village i to village i+1, for all 1≤i≤n−1.
n roads can be described by a sequence a1,…,an. If ai=0, the i-th of these roads goes from village i to village n+1, otherwise it goes from village n+1 to village i, for all 1≤i≤n.
Mocha plans to go hiking with Taki this weekend. To avoid the trip being boring, they plan to go through every village exactly once. They can start and finish at any villages. Can you help them to draw up a plan?

Input
Each test contains multiple test cases.

The first line contains a single integer t (1≤t≤20) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains a single integer n (1≤n≤104) — indicates that the number of villages is n+1.

The second line of each test case contains n integers a1,a2,…,an (0≤ai≤1). If ai=0, it means that there is a road from village i to village n+1. If ai=1, it means that there is a road from village n+1 to village i.

It is guaranteed that the sum of n over all test cases does not exceed 104.

Output
For each test case, print a line with n+1 integers, where the i-th number is the i-th village they will go through. If the answer doesn’t exist, print −1.

If there are multiple correct answers, you can print any one of them.

样例输入

2
3
0 1 0
3
1 1 0

样例输出

1 4 2 3 
4 1 2 3 

题意

n个村子之间有2n+1条路，其中n-1条道路是从村子i通向村子i+1的,n条路对应以下关系:
如果a[i]==0,则道路从村子i通向村子n+1;
如果a[i]==1,道路从村子n+1通向村子i;

找出一种方式可以在不重复的情况下走过所有村子，输出走过村子的顺序

思路

总有一天会卒于模拟题(x)。

分三种情况进行讨论：

1.a[1]==1,此时有第n+1个村子通向第i个村子，此时输出n+1，然后从头开始遍历村子即可。
2.a[n]==0,此时正好有第n个村子通向第n+1个村子，直接从头开始遍历村子即可。
3.上述两种不存在，此时我们需要找到一个i使得a[i]==0&&a[i+1]==1,这样我们才可以将n+1插入到序列中去。
如果不存在这样的i，直接输出-1即可。

C++ 代码

#include <iostream>
using namespace std;
const int N=10010;
int a[N],b[N];
int n;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int i,j;
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        if(a[1]==1)
        {
            printf("%d ",n+1);
            for(i=1;i<=n;i++)
            {
                printf("%d ",i);
            }
            printf("\n");
        }
        else if(a[n]==0)
        {
            for(i=1;i<=n+1;i++)
            {
                printf("%d ",i);
            }
            puts("");
        }
        else
        {
            int f=0,k=-1;
            for(i=1;i<=n;i++)
            {
                if(a[i]==0&&a[i+1]==1)
                {
                    f=1;
                    k=i;
                    break;
                }
            }
            if(f==1)
            {
                for(i=1;i<=k;i++)
                {
                    printf("%d ",i);
                }
                printf("%d ",n+1);
                for(i=k+1;i<=n;i++)
                {
                    printf("%d ",i);
                }
                printf("\n");
            }
            else
            {
                printf("-1\n");
            }
        }
    }
    return 0;
}