题解

题面描述

给定一个长度为 $n-1$ 的 $01$ 字符串，要求构建一个从 $1$ 到 $n$ 各出现一次的长度为 $n$ 的排列。字符串的第 $i$ 位为 $0$ 表示排列第 $i+1$ 位比第 $i$ 位小，反之，第 $i$ 位为 $1$ 表示排列第 $i+1$ 位比第 $i$ 位大。

思路

本题要求根据给定的 $01$ 字符串构造一个排列，使得排列中相邻元素的大小关系与字符串中的 $0$ 和 $1$ 对应。具体来说，字符串中的 $0$ 表示排列中后一个元素比前一个元素小，$1$ 表示后一个元素比前一个元素大。通过使用双指针策略，分别指向当前可用的最小数和最大数，根据字符串的字符动态选择当前元素的值，可以高效地构造出满足条件的排列。这种方法的时间复杂度为 $O(n)$，适用于大规模数据。

题目内容

给定一个长度为 $n-1$ 的 $01$ 字符串，要求构建一个从 $1$ 到 $n$ 各出现一次的长度为 $n$ 的排列。字符串的第 $i$ 位为 $0$ 表示排列第 $i+1$ 位比第 $i$ 位小，反之，第 $i$ 位为 $1$ 表示排列第 $i+1$ 位比第 $i$ 位大。

输入描述

输入为一个长度为 $n-1(2 ≤n≤ 10^5)$ 的 $01$ 字符串。

输出描述

输出一个满足条件的排列，如果没有满足要求的排列则输出"$-1$"。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。

注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

0101

输出

3 2 4 1 5

说明

构建的排列为 $3,2,4,1,5$。

$s_1=0$，排列 $a_2=2$ 比 $a_1=3$ 小；

$s_2=1$，排列 $a_3=4$ 比 $a_2=2$ 大；

$s_3=0$，排列 $a_4=1$ 比 $a_3=4$ 小；

$s_4=1$，排列 $a_5=5$ 比 $a_4=1$ 大。