[THUPC 2024 初赛] 二进制
题目描述
今天也是喜欢二进制串的一天,小 F 开始玩二进制串的游戏。
小 F 给出了一个这里有一个长为 $n$ 的二进制串 $s$,下标从 $1$ 到 $n$,且 $\forall i\in[1,n],s_i\in \{0,1\}$,他想要删除若干二进制子串。
具体的,小 F 做出了 $n$ 次尝试。
在第 $i\in[1,n]$ 次尝试中,他会先写出正整数 $i$ 的二进制串表示 $t$(无前导零,左侧为高位,例如 $10$ 可以写为 $1010$)。
随后找到这个二进制表示 $t$ 在 $s$ 中从左到右 **第一次** 出现的位置,并删除这个串。
注意,删除后左右部分的串会拼接在一起 **形成一个新的串**,请注意新串下标的改变。
若当前 $t$ 不在 $s$ 中存在,则小 F 对串 $s$ 不作出改变。
你需要回答每一次尝试中,$t$ 在 $s$ 中第一次出现的位置的左端点以及 $t$ 在 $s$ 中出现了多少次。
定义两次出现不同当且仅当出现的位置的左端点不同。
请注意输入输出效率。
输入输出格式
输入格式
第一行一个正整数 $n$($1\leq n\leq 1000000$)。
第二行一个长度为 $n$ 的字符串 $s$。保证 $\forall i\in[1,n], s_i \in \{0, 1\}$。
输出格式
输出共 $n$ 行,每行两个整数,第 $i$ 行表示小 F 进行第 $i$ 次尝试时开头端点的位置以及相应的字符串出现的次数。
若这次尝试失败,则当前行输出 $-1\ 0$。
输入输出样例
输入样例 #1
20
01001101101101110010
输出样例 #1
2 11
5 5
4 5
11 1
4 2
7 1
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
说明
### 题目使用协议
来自 THUPC2024(2024年清华大学学生程序设计竞赛暨高校邀请赛)初赛。
以下『本仓库』皆指 THUPC2024 初赛 官方仓库([https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public))
1. 任何单位或个人都可以免费使用或转载本仓库的题目;
2. 任何单位或个人在使用本仓库题目时,应做到无偿、公开,严禁使用这些题目盈利或给这些题目添加特殊权限;
3. 如果条件允许,请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法;否则,请附上本仓库的 github 地址。