题解 | 小红的排列构造

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
#include <iostream>
#include <vector>
using namespace std;
int main() {
  int n;
  string s;
  cin >> n >> s;
  int size = s.size();
  vector<int> a, b(size);
  for (int i = 0; i < size; i++) b[i] = i + 1;
  bool flag = 0;
  flag = (s[0] - '0');//--------n>=1,用于标记当前元素是1还是0，《true》表示1
  int i = 0;
  char last = s[0];
  int num;
  size = 0;
  while(i < n){
    num = 0;
    while(i < n && s[i] == last){
      i++;
      num++;
    }
    a.push_back(num);
    size++;
    if (i < n) last = s[i];
  }
  int index = 0;
  auto shuffle = [&](int ind, size_t lenth){//-----顺时针转一圈使其不能构成排列
    int temp = b[ind];
    for (int j = ind; j < ind + lenth - 1; j++){
      b[j] = b[j + 1];
    }
    b[ind + lenth - 1] = temp;
  };
  for(int j = 0; j < size; j++){
    if (flag){
      void();
    }
    else{
      if (j == size - 1){//-----如果0在最后面则必然不能实现题意
        cout << -1;
        return 0;
      }
      shuffle(index, a[j] + 1);
    }
    index += a[j];
    flag = !flag;
  }
  for (int i = 0; i < b.size(); i++){
    cout << b[i] << " ";
  }
}
// 64 位输出请用 printf("%lld")