题解 | 小红的排列构造②

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
inline void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}
int main() {
    fast_io();
    int T = 1;
    
    while (T--) {
    	int n;
    	cin>>n;
    	string s;
    	cin>>s;
    	vector<int> a(n);

    	for(int i=0;i<n;i++){
    		a[i]=i+1;
    	}
    	for(int i=0;i<n;i++){
    		if(s[i]=='0'){
    			int isprime=0;
    			for(int j=i+1;j<n;j++){
    				if(s[j]=='1'){
    					swap(a[i],a[j]);
    					isprime=1;
    					i=j;
    					break;
    				}
    			}
    			if(isprime==0){
    					cout<<"-1";
    					return 0;
    			}
    		}
    	}
    	for(int i=0;i<n;i++){
    		cout<<a[i]<<" ";
    	}

    }
    return 0;
}

初始化一个从1到n的数组，遍历字符串，0必须和后面的1匹配，交换数组中两个对应位置的元素之后，0和1中间的所有0都解决了，如果0匹配不上后面的1，说明最后一位为0，最后一位一定是1才可以，所以无解。