QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 512 MB
[-1]

# 7967. 二进制

统计

题目描述

今天也是喜欢二进制串的一天,小 F 开始玩二进制串的游戏。

小 F 给出了一个这里有一个长为 n 的二进制串 s,下标从 1n,且 i[1,n],si{0,1},他想要删除若干二进制子串。

具体的,小 F 做出了 n 次尝试。

在第 i[1,n] 次尝试中,他会先写出正整数 i 的二进制串表示 t(无前导零,左侧为高位,例如 10 可以写为 1010)。

随后找到这个二进制表示 ts 中从左到右 第一次 出现的位置,并删除这个串。

注意,删除后左右部分的串会拼接在一起 形成一个新的串,请注意新串下标的改变。

若当前 t 不在 s 中存在,则小 F 对串 s 不作出改变。

你需要回答每一次尝试中,ts 中第一次出现的位置的左端点以及 ts 中出现了多少次。

定义两次出现不同当且仅当出现的位置的左端点不同。

请注意输入输出效率。

输入格式

第一行一个正整数 n1n1000000)。

第二行一个长度为 n 的字符串 s。保证 i[1,n],si{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