#P9044. [2017年备战省选]c
[2017年备战省选]c
题目描述
给定长度为 的排列 ,保证每个 都满足 。构造一个长度为 的括号序列,使其满足以下条件:
- 括号序列合法。
- 在 个点上构造一张无向图。当且仅当序列第 个字符为左括号时,加入一条连接点 和 的边。要求图中每个点的度数恰为 。
合法括号序列可递归定义如下:
- 空序列合法。
- 若 合法,则将其括在一对括号中所得的序列合法。
- 若 合法,则将它们拼接所得的序列合法。
输入格式
第一行一个正整数 。第二行 个正整数,给出排列 。保证排列合法。
输出格式
输出一行长度为 的括号序列。若有多种合法解,可以输出其中任意一种。
样例 1
6
2 3 6 1 4 5
()()()
原题的第二组样例见原比赛样例数据文件夹。
数据范围
| 子任务 | 分值 | |
|---|---|---|
| 1 | 20 | 10 |
| 2 | 40 | 30 |
| 3 | 100 | 60 |
原比赛要求通过一个子任务的全部测试点才能获得该子任务的分数。