#P9044. [2017年备战省选]c

[2017年备战省选]c

题目描述

给定长度为 nn 的排列 PP,保证每个 ii 都满足 Pi≠iP_i\ne i。构造一个长度为 nn 的括号序列,使其满足以下条件:

  1. 括号序列合法。
  2. 在 nn 个点上构造一张无向图。当且仅当序列第 ii 个字符为左括号时,加入一条连接点 ii 和 PiP_i 的边。要求图中每个点的度数恰为 11。

合法括号序列可递归定义如下:

  • 空序列合法。
  • 若 AA 合法,则将其括在一对括号中所得的序列合法。
  • 若 A,BA,B 合法,则将它们拼接所得的序列合法。

输入格式

第一行一个正整数 nn。第二行 nn 个正整数,给出排列 PP。保证排列合法。

输出格式

输出一行长度为 nn 的括号序列。若有多种合法解,可以输出其中任意一种。

样例 1

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

原题的第二组样例见原比赛样例数据文件夹。

数据范围

子任务 nn 分值
1 20 10
2 40 30
3 100 60

原比赛要求通过一个子任务的全部测试点才能获得该子任务的分数。

原 PDF 题面