luogu#P7734. [JDWOI-2] 01 串

[JDWOI-2] 01 串

题目背景

小 K 和小 M 写了一个 01 串。

题目描述

小 K 和小 M 写了一个 01 串 SS,串的结尾包含 2 个连在一起的空格(用 . 表示)。

小 M 定义一个 01 串是美观的,当且仅当串中没有逆序对,即没有 1 出现在 0 的前面。

为了满足小 M 的上述要求,小 K 决定对这个 01 串进行一些修改。每一次修改,小 K 可以选择串中两个连续的非空格字符,并把他们移动到空格的位置,并且不改变相对位置。这样,被移动的字符处会变成空格,而原来的空格会被这两个字符填起来。

小 K 为了尽快让字符串变美观,希望在 1000010000 步以内完成。现在,请求出需要用多少步使得 01 串变美观,并输出方案。如果无法使串美观,或者步数必须超过 1000010000 ,请输出 -1

注:你并不需要最小化修改步数,并且最终空格的位置随便。

输入格式

一行一个 01 字符串,保证输入符合题意。

输出格式

第一行一个整数 mm,表示修改的步数。

接下来 mm 行,每行两个整数 x,yx,y,表示将 (x,x+1)(x,x+1) 位置上的两个数移动到 (y,y+1)(y,y+1)

1100..
1
1 5

0101..
-1

提示

本题采用 Special Judge 和子任务评测。

【样例解释 1】

1100....0011\texttt{1100..} \rightarrow \texttt{..0011}

【样例解释 2】

可以发现无论如何移动都无法实现小 M 要求的 01 串。

【数据范围和子任务分数】

Subtask1(20pts):3S103 \leq |S| \leq 10
Subtask2(30pts):3S1003 \leq |S| \leq 100
Subtask3(50pts):3S20003 \leq |S| \leq 2000