构造括号序列

题目描述

你需要构造一个长度大于等于 $a$ 并且 小于等于 $b$ 的括号序列 $s$，使得 $s$ 中有 $c$ 对数对 $(i,j)$ 满足 $0\le i < j < |s|$ 且 $s_i$ 为左括号 (、$s_j$ 为右括号 )。
如果无解输出 -1。

输入格式

输入第 $1$ 行 $1$ 个数 $T$，表示数据组数。 接下来 $T$ 行，每行 $3$ 个数 $a,b,c$。

输出格式

输出共 $T$ 行，每行一个仅包含左括号 ( 和右括号 ) 的括号串 $s$。如果无解输出 -1。

输入输出样例 #1

输入 #1

2
1 115 3
3 4 7

输出 #1

((()
-1

说明/提示

• subtask1 $a=1,b\le 10^5,\sum{b}\le 2\times 10^5$。
• subtask2 $1\le a\le b\le 10^9,\sum{a} \le 2\times 10^5$。
  对于所有数据，满足 $1\le a\le b\le 10^9,1\le T\le 100,1\le c\le 2^{50} \approx 1.1\times 10^{15}$。

保证存在一种构造方案使得 $\sum{|s|} \le 5\times 10^7$

2s,512MB,Special Judge。

题解

考虑构造连续的 $x$ 个左括号和连续的 $y$ 个右括号，其中 $y=x$ 或 $y=x+1$。
不难发现只要交换一个左括号和一个右括号即可构造出 $c$ 对合法括号对，且这种构造方案下生成的 $c$ 是连续的。
贪心求出长度为 $b$ 时的合法括号对数量的最大值然后判一下无解即可。
如果 $a$ 太大就在末尾放连续的左括号，显然不产生任何贡献。