← 返回题目列表

Codeforces · 1043/C

C. 最小的字

中文机器翻译题面 查看原题

IA 的冰箱上有很多彩色磁铁!每块磁铁上都写有一个字母“a”或“b”。她喜欢和它们一起玩,将所有磁铁排成一排。然而,女孩很快就会感到无聊,通常会思考如何让她的娱乐变得更有趣。

今天,IA看冰箱的时候,发现磁铁组成的字真的很乱。 “如果我交换其中一些,看起来会好得多!” ——女孩想——“但是该怎么做呢?”。过了一会儿,她有了一个主意。 IA 将查看长度从 $$$1$$$ 到单词长度的所有前缀,对于每个前缀,她要么反转该前缀,要么保持原样。她会按照固定的顺序考虑前缀:从最短到最大。她希望在考虑所有前缀后获得字典顺序上最小的可能单词。你能帮助她,告诉她应该选择哪些前缀来进行逆向吗?

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。

输入

第一行也是唯一一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 1000$$$),描述由磁铁形成的初始字符串。字符串 $$$s$$$ 仅包含字符“a”和“b”。

输出

准确输出 $$$|s|$$$ 整数。如果 IA 应反转第 $$$i$$$ 前缀(即从 $$$1$$$ 到 $$$i$$$ 的子字符串),则第 $$$i$$$ 整数应等于 $$$1$$$,否则应等于 $$$0$$$。

如果有多个可能的序列导致最佳答案,请打印其中任何一个。

示例

输入 #1

bbab

输出 #1

0 1 1 0

输入 #2

aaaaa

输出 #2

1 0 0 0 1

注意

在第一个示例中,IA 可以反转第二个和第三个前缀并得到字符串“abbb”。她无法获得更好的结果,因为它也是通过排列初始字符串的字符获得的按字典顺序排列的最小字符串。

在第二个示例中,她可以反转前缀的任何子集 - 所有字母都是“a”。