题解 | 小红的排列构造②

import java.util.Scanner;

/**
 * @author supermejane
 * @date 2025/10/11 12:21
 * @description BGN78 小红的排列构造②
 */
public class Main {
  	//题目只要是把问题想清楚，实际上代码就是一个o(n)双指针就行了
  	//首先第一点如果存在一个排列，那么s最后一位肯定是'1',这个是一个充分条件
  	//同时我们可以想的是对于任意一个'1'结尾的s,每一小段s(i) - s(j)'0001'的字串都可以是对应i - j的值的“打乱”（都不在自己位置上），那么也就是说 存在一个排列是s最后一位肯定是'1'的充要条件
  	//知道上面的情况只要判断结尾是否为'1'，对于为'1',使用上面的结论双指针对于每一小段s(i) - s(j)'0001'输出一个“打乱”就行了
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String s = in.nextLine();

        int len;
        if ((len = s.length()) != n || s.charAt(len - 1) != '1') System.out.println(-1);
        else {
            int p1 = 0, p2;
            boolean flag = false;
            for (p2 = 0; p2 < len; p2++) {
                if (s.charAt(p2) == '1') {
                    for (int i = p1 + 2; i <= p2 + 1; i++) {
                        System.out.print((flag ? " " : "") + i);
                        flag = true;
                    }
                    System.out.print((flag ? " " : "") + (p1 + 1));
                    flag = true;
                    p1 = p2 + 1;
                }
            }
        }
    }
}