← 返回题目列表

Codeforces · 578/E

E. 走路!

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

爱丽丝家门前有一条沙路。

白天,人们走过它,每一步都在小路上留下脚印。爱丽丝无法区分脚印的顺序,但她可以分辨出每个脚印是左脚还是右脚。她还确信所有人都是左右脚交替行走的。

例如,假设一个人走过这条小路并留下了一些脚印。足迹沿步道按 RRLRL 顺序排列(“R”表示右脚,“L”表示左脚)。您可能会认为脚印的结果很奇怪。但事实上,有些脚步是倒着走的结果!

产生这些足迹的步骤可能有一些顺序,例如 1 → 3 → 2 → 5 → 4 或 2 → 3 → 4 → 5 → 1(我们假设两个连续步骤之间的距离可以是任意长)。上述两个例子的后退步数分别为2和1。

爱丽丝对这些脚印很感兴趣。每当有人走过这条小路时,她就会拍下小路上所有脚印的照片,然后把它们全部擦掉,这样下一个人就会留下一组新的脚印。我们知道人走路时右脚和左脚交替,但我们不知道第一步是左脚还是右脚。

Alice 想知道一个人向后退步的最小可能数量。但这有点难。请帮助爱丽丝计算一下。您还需要构建这些足迹的一种可能的历史。

输入

只有一行包含字符串 S (1 ≤ |S| ≤ 100 000),其中包含从入口到出口沿小路按顺序排列的所有足迹。

保证至少有一个可能的足迹历史记录。

输出

您应该输出 2 行。

第一行应包含一个数字,表示最小后退步数。

第二行应包含从 1 到 |S| 的整数排列。这种排列应该表示步行到那里的人可能使用的足迹的顺序。

如果有多个可能的答案,您可以输出其中任何一个。

示例

输入 #1

RRLRL

输出 #1

1
2 5 1 3 4

输入 #2

RLRLRLRLR

输出 #2

0
1 2 3 4 5 6 7 8 9

输入 #3

RRRRRLLLL

输出 #3

4
4 9 3 8 2 7 1 6 5

注意

对于第一个样本,一个可能的顺序是 2 → 5 → 1 → 3 → 4,其中只有步骤 5 → 1 是后退步骤,因此答案为 1。

对于第二个示例,一种可能的顺序就是遵循输入的顺序,因此没有向后的步骤。

对于第三个样本,将有 4 个后退步骤,因为从 L 到 R 的每一步都是一个后退步骤。