luogu#P7734. [JDWOI-2] 01 串
[JDWOI-2] 01 串
题目背景
小 K 和小 M 写了一个 01 串。
题目描述
小 K 和小 M 写了一个 01 串 ,串的结尾包含 2 个连在一起的空格(用 .
表示)。
小 M 定义一个 01 串是美观的,当且仅当串中没有逆序对,即没有 1 出现在 0 的前面。
为了满足小 M 的上述要求,小 K 决定对这个 01 串进行一些修改。每一次修改,小 K 可以选择串中两个连续的非空格字符,并把他们移动到空格的位置,并且不改变相对位置。这样,被移动的字符处会变成空格,而原来的空格会被这两个字符填起来。
小 K 为了尽快让字符串变美观,希望在 步以内完成。现在,请求出需要用多少步使得 01 串变美观,并输出方案。如果无法使串美观,或者步数必须超过 ,请输出 -1
。
注:你并不需要最小化修改步数,并且最终空格的位置随便。
输入格式
一行一个 01 字符串,保证输入符合题意。
输出格式
第一行一个整数 ,表示修改的步数。
接下来 行,每行两个整数 ,表示将 位置上的两个数移动到 。
1100..
1
1 5
0101..
-1
提示
本题采用 Special Judge 和子任务评测。
【样例解释 1】
【样例解释 2】
可以发现无论如何移动都无法实现小 M 要求的 01 串。
【数据范围和子任务分数】
Subtask1(20pts):;
Subtask2(30pts):;
Subtask3(50pts):。