← 返回比赛

已结束 GESP巅峰赛#29

← 上一题下一题 →

A7094 | $月环封印$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港学宫的封印符文是一圈括号组成的环。把符文从任意处切开、摊平成串记为 $s$，长度为偶数 $n$，字符仅为'(' 与')' 。你可以在 切开之前 对整圈符文做 一次换位 ：选定两个位置，交换它们上的字符（仍然是环上的交换）。随后从环上任意处切开摊平（等价于对串做任意循环位移），检查是否是一条 正规括号序列 。 在所有“先换一次、再任选一个切口（循环位移）”的方案中，设 $g$ 为 能得到正规括号序列的切口个数 的最大值。请你输出这个最大值 $g$，以及 任取一对 达到该最大值的交换位置 $(l,r)$（$1$-下标，环上计数）。 - 若不进行交换即可达到最大值，也要求输出一对 $(l,r)$（可以输出 $l=r$ 表示“不交换”）。

输入格式

- 第一行一个偶数 $n$； - 第二行一个长度为 $n$ 的字符串 $s$（仅含'(' 与')' ）。

输出格式

- 一行输出三个整数：$g,\ l,\ r$。要求交换 $s_l$ 与 $s_r$（环上位置），使得在该交换后，对循环位移的切口计数达到 $g$ 的最大值。

输入输出样例

输入 #1

6
)()()(

输出 #1

3 2 2

输入 #2

8
(()))(((

输出 #2

0 3 6

数据范围 - $2\le n\le 2\times 10^5$，$n$ 为偶数； - $s$ 仅含 '(' 与 ')'。 层级$n$ 范围A$1\le n\le 20$B$20< n\le 500$C$500< n\le 2\times 10^5$

C++ 编辑器

输入

输出