#P18953. [Mladen Manev 2022 AT3] brackets / 两种顺序的括号序列

[Mladen Manev 2022 AT3] brackets / 两种顺序的括号序列

两种顺序的括号序列

给定偶数 NN 和 11 至 NN 的排列 pp。构造长度为 NN、仅由 ( 和 ) 组成的串 ss,使以下两个串都是合法括号序列:

$$s_1s_2\cdots s_N,\qquad s_{p_1}s_{p_2}\cdots s_{p_N}.$$

合法括号序列的左右括号总数相等,且任意前缀中左括号数不少于右括号数。

输入格式

第一行偶数 NN。第二行排列 p1,…,pNp_1,\ldots,p_N。

输出格式

无解输出 NIE;否则输出任意一个满足条件的长度为 NN 的括号串。

数据范围

2≤N≤1062\le N\le10^6,NN 为偶数。pp 是一个排列。

样例

6
4 6 1 2 3 5
(()())
2
2 1
NIE

本题为波兰 XXVIII OI 决赛第二天 Nawiasowania(2021),由本网站 2022 年训练赛选用。

来源与数据说明

2022 年 Dr. Mladen Manev,AT3,原题名 brackets。赛事资料,原文题面见附件 statement.pdf。

原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。