n, s = int(input()), input()
N = len(s)

def _solve():
    # 检查是否以 '1' 结尾
    if s[-1] != '1':
        return "-1"
    # 收集所有 '1' 的位置（0-based）
    oi = [-1]  # 初始化为 -1，方便处理第一个区间
    for i in range(N):
        if s[i] == '1':
            oi.append(i)
    no = len(oi)  # '1' 的个数 + 1（因为初始有 -1）
    d = [0] * n
    # 从后往前处理每个 '1' 的区间
    for i in range(no - 1, 0, -1):
        num = oi[i] + 1  # 当前 '1' 的 1-based 位置
        index = oi[i - 1] + 1  # 前一个 '1' 的 1-based 位置
        d[index] = num  # 将前一个 '1' 的下一个位置设置为 num
        # 填充递减序列
        k = num - 1
        for j in range(index + 1, num):
            d[j] = k
            k -= 1
    return " ".join(map(str, d))

def solve():
    res = _solve()
    print(res)

solve()

题目重述

我们有一个由 0 和 1 组成的字符串 s 和一个长度为 n 的排列 p。定义 s 和 p 匹配的条件如下：

  1. 如果 s[i] == '1'，那么 p[1..i] 必须是一个排列（即包含 1 到 i 的所有整数，每个整数恰好出现一次）。
  2. 如果 s[i] == '0'，那么 p[1..i] 不能是一个排列。

给定字符串 s，构造一个满足条件的排列 p，如果不存在这样的排列，则输出 -1。

解题思路

我们需要构造一个排列 p，使得对于每个位置 i：

  • 如果 s[i] == '1'，那么 p[1..i] 是 1 到 i 的排列。
  • 如果 s[i] == '0'，那么 p[1..i] 不是 1 到 i 的排列。

关键观察：

  1. ​**s 必须以 '1' 结尾**​：因为 p[1..n] 必须是一个排列（1 到 n 的排列），所以 s[n-1] 必须是 '1'（因为 Python 是 0-based 索引，题目中 s 是 1-based 索引时 s[n] 必须是 '1'）。如果 s 以 '0' 结尾，直接返回 -1。
  2. ​**'1' 的位置**​：假设 s 中有 k 个 '1'，分别出现在位置 i_1, i_2, ..., i_k（其中 i_k = n-1）。那么：对于每个 i_j，p[1..i_j] 必须是 1 到 i_j 的排列。对于 i_{j-1} + 1 到 i_j - 1 的位置（即两个 '1' 之间的 '0' 区域），p[1..m] 不能是 1 到 m 的排列（其中 m 在这些位置之间）。

构造方法：

  1. ​处理 '1' 的位置​：对于每个 '1' 的位置 i_j，p[1..i_j] 必须是 1 到 i_j 的排列。因此，我们可以将 p[1..i_j] 设置为 1 到 i_j 的某种排列。为了满足 '0' 的条件，我们需要确保在两个 '1' 之间的 '0' 区域中，p 的构造不会让 p[1..m] 成为 1 到 m 的排列。
  2. ​具体构造​：假设 '1' 的位置是 i_1, i_2, ..., i_k（按顺序）。对于 i_j，p[1..i_j] 是 1 到 i_j 的排列。我们可以将 p[i_{j-1}+1..i_j] 设置为 i_j - i_{j-1} 到 1 的递减序列（即 i_j - i_{j-1}, ..., 1），然后将前面的部分调整为满足排列的条件。这样，对于 '0' 的位置 m（i_{j-1} < m < i_j），p[1..m] 会缺少 i_j - i_{j-1} - (m - i_{j-1}) 的一些数，因此不是 1 到 m 的排列。

代码步骤：

  1. ​输入处理​：读取 n 和字符串 s。N 是 s 的长度（实际上是 n）。
  2. ​检查 s 是否以 '1' 结尾​：如果不是，直接返回 -1。
  3. ​收集所有 '1' 的位置​：oi 是一个列表，初始化为 [-1]，然后收集所有 '1' 的 0-based 索引。
  4. ​**初始化结果数组 d**​：d 是长度为 n 的数组，初始化为 0。
  5. ​从后往前处理 '1' 的区间​：no 是 '1' 的个数 + 1（因为 oi 初始有 -1）。从最后一个 '1' 开始往前处理：num 是当前 '1' 的 1-based 位置（oi[i] + 1）。index 是前一个 '1' 的 1-based 位置（oi[i-1] + 1）。将 d[index] 设置为 num（即前一个 '1' 的下一个位置是 num）。然后从 index + 1 到 num - 1 填充递减序列 num - 1, num - 2, ..., 1。
  6. ​返回结果​：将 d 转换为字符串输出。

总结

该算法的核心是通过从后往前处理 '1' 的位置，确保每个 '1' 对应的前缀是一个排列，而 '0' 对应的前缀不是排列。通过填充递减序列，可以高效地构造出满足条件的排列。如果 s 不以 '1' 结尾，则直接判定无解。