题解：AT_past202109_f 不完全順列

题意

建议评红。

有一个 $01$ 串 $s$，长度为 $n$，要求给出一个排列 $p$，$1$ 到 $n$ 每个数都要出现一次，对于第 $i$ 个数，如果 $s_i$ 为 $1$ 则 $p_i$ 为 $i$，否则 $p_i$ 不能为 $i$。

分析

如果 $s$ 中有 $n-1$ 个 $1$ 则所有 $p_i$ 一定等于 $i$，输出 $-1$。

对于 $s_i$ 等于 $0$ 的情况，我们将所有的 $i$ 记录下来，然后对于记录的第 $x$ 个下标 $a_x$，使 $p_{a_x}$ 等于 $a_{x+1}$。

注意此处存储下标用的数组 $a$ 是一个环，这样才能保证每个位置都有数可填。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],x=0,ans[1000005]={
   0},c=0;
string s;
int main(){
   
  cin>>n>>s;
  for(int i=0;i<n;i++)
  {
   
    if(s[i]=='1')ans[i]=i+1;
    else a[x++]=i+1;//记录下标
  }
  a[x]=a[0];//围链成环
  if(x==1)//特判无解
  {
   
    cout<<-1;
    return 0;
  }
  for(int i=0;i<n;i++)
  {
   
    if(ans[i])cout<<ans[i];
    else
    {
   
      cout<<a[(c++)+1];
    }
    cout<<" ";
  }
  return 0;
}