题解 | 小红的排列构造②

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    // p是一个排列，那么p的内容就是1~n的乱序
    // s[n-1] 必须是1，否者p就不满足【排列】定义
    // 如果[i,j]是连续的1，那么p[k] = k+1, 其中k=i+1~j)
    // 如果是s[i] = 1, 那么0~i项为1~i+1的乱序
    // 如果前i项s都是0，那么s[i] 不能为i+1
    // 最终选择：如果s[i] = 1，那么从i+1到上一个s[k]=1的位置倒叙填充
    // s[0]如果为1，则填充1
    if(s[n-1] != '1') {
        cout << -1 << endl;
        return 0;
    }
    vector<int> a(n);
    int last = n;
    for(auto i = n - 1; i >= 0; i--) {
        if(s[i] == '1') {
            if(last < n) {
                int m = last+1;
                for(auto j = i+1; j <= last; j++) {
                    a[j] = m;
                    m--;
                }
            }
            last = i;
        }
    }
    if(s[0] == 1) {
        a[0] = 1;
    } else {
        int m = last+1;
        for(auto j = 0; j <= last; j++) {
            a[j] = m;
            m--;
        }
    }
    auto first = true;
    for(auto v : a) {
        if(!first) {
            cout << " ";
        }
        first = false;
        cout << v;
    }
    cout << endl;
}
// 64 位输出请用 printf("%lld")