QOJ.ac

QOJ

Limite de temps : 5.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓

#17689. 冬季奥林匹克运动会

Statistiques

图:守护郎(Soohorang)。与本题无关,只是因为它很可爱才放进来的。

2018 RUN@KAIST 冬季冰壶比赛女子决赛正在进行中。在 KAIST 结冰的“鸭子塘”上,韩国女子冰壶队正与来自 Jwepan 国的队伍展开激烈角逐!

“鸭子塘”上共有 $N$ 个冰壶。由于竞争异常激烈,每个冰壶都从一个标记处排成一线。最左边的冰壶距离标记最近,而最右边的冰壶距离标记最远。冰壶要么属于韩国队(用 '1' 表示),要么属于 Jwepan 队(用 '0' 表示)。这些冰壶的排列可以用一个长度为 $N$ 的二进制序列来表示。

平昌冬奥会结束后,韩国队进行了高强度的训练。现在,伴随着一些呐喊声(?),负责投壶的队员“荣美(Youngmi)”可以击飞一些连续的冰壶,并将自己的冰壶停留在该位置。形式上,韩国队可以选择二进制字符串中的任意子段(可以为空),并将其替换为单个数字 "1"。

韩国队是冰壶策略的大师,他们知道单回合的最佳策略是使最终的字符串字典序最大!为了在比赛中快速做出决策,他们希望找到一个能实现这一目标的最快算法。请帮助韩国队赢得比赛!

对于长度为 $n$ 的字符串 $s = s_1 s_2 \dots s_n$ 和长度为 $m$ 的字符串 $t = t_1 t_2 \dots t_m$,如果满足以下条件之一,则称 $s$ 的字典序大于 $t$:

  • 存在某个 $i$ 使得 $s_1 = t_1, s_2 = t_2, \dots, s_{i-1} = t_{i-1}$,且 $s_i > t_i$。
  • $n > m$ 且 $s_1 = t_1, s_2 = t_2, \dots, s_m = t_m$。

输入格式

第一行给定冰壶的数量 $N$。($1 \le N \le 1,000,000$)

第二行给定一个长度为 $N$ 的二进制字符串,由 '0' 或 '1' 组成。该字符串按距离标记由近到远的顺序表示每个冰壶的归属。字符串中不包含引号或空格。

输出格式

输出两个整数 $S, L$。这表示荣美移除了第 $S$ 个字符之后的 $L$ 个冰壶(并在此处放入一个 '1')。如果存在多个正确答案,输出其中任意一个。($0 \le S, L \le N$)

样例

输入样例 1

8
10101101

输出样例 1

1 3

输入样例 2

5
11111

输出样例 2

0 0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.