题解 | 小红的排列构造

观察到以下规律：

如果[1, 2, ... , n]的第k<n位和最后一位交换，那么[0,n)依旧是一个排列，而[0,k]不是一个排列。

所以算法如下：

从1 2 3 4 5 ... n开始

对每个'0'的位置 i，总是找其后面的第一个'1'位置 j，交换perm[i],perm[j]。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> perm(n);
    int j=0;
    int i;
    for (i = 1; i <= n; i++) {
        perm[i - 1] = i;
    }

    bool flag = true;
    for (i = 0; i < s.size(); i++) {
        if (s[i] == '0') {
            if (i >= j) {
                // find next '1' after this '0'
                for (j = i + 1; j < n; j++) {
                    if (s[j] == '1')break;
                }
            }
            if (j >= n) {
                flag = false;
                break;
            }
            swap(perm[i], perm[j]);
        }
    }
    if (flag) {
        for (i = 0; i < s.size() - 1; i++)
            cout << perm[i] << ' ';
        cout << perm[i];
    } else {
        cout << -1;
    }
}
// 64 位输出请用 printf("%lld")