CF123C Brackets

如果一个二维数组的每个格子都只包含两种括号之一——“(” 或 “)”——则称其为括号数组。如果一条路径经过的任意两个相邻格子都是边相邻的，并且路径上的每个格子都位于前一个格子的下方或右侧，则称这条路径是单调的。 如果一个大小为 $n \times m$ 的二维数组满足：从格子 $(1,1)$ 到格子 $(n,m)$ 的任意一条单调路径上，依次写出路径经过的括号，所得的字符串都是合法括号序列，则称该数组为合法括号数组。 我们定义两个大小相同的合法括号数组 $a$ 和 $b$ 的比较操作如下：给定一个优先级数组 $c$，它是一个同样大小的二维数组，包含 $1$ 到 $nm$ 的不同整数。找到所有满足 $a_{i,j} \neq b_{i,j}$ 的位置 $(i,j)$，选择其中 $c_{i,j}$ 最小的那个。如果 $a_{i,j}$ 为 “(”，则 $a < b$，否则 $a > b$。如果没有这样的 $(i,j)$，则认为 $a$ 和 $b$ 相等。 你的任务是找到第 $k$ 小的二维合法括号数组。保证对于给定的 $n$ 和 $m$，合法括号数组的数量不少于 $k$。

第一行包含整数 $n$、$m$ 和 $k$，分别表示数组的大小和要求的第 $k$ 小合法括号数组（$1 \leq n, m \leq 100$，$1 \leq k \leq 10^{18}$）。接下来输入优先级数组，共 $n$ 行，每行 $m$ 个数字，第 $i$ 行第 $j$ 个数字 $p_{i,j}$ 表示第 $i$ 行第 $j$ 列字符的优先级（$1 \leq p_{i,j} \leq nm$，所有 $p_{i,j}$ 互不相同）。 请不要在 C++ 中使用 %lld 读写 64 位整数，建议使用 cin、cout 流或 %I64d。

输出第 $k$ 小的二维合法括号数组。

在第一个样例中，只存在一个合法的二维括号数组。 在第二个和第三个样例中，存在两个合法的数组。 一个括号序列被称为合法的，如果可以通过在序列中插入“+”和“1”字符得到一个正确的算术表达式。例如，“(())()”、“()” 和 “(()(()))” 是合法的，而 “)(”、“(()” 和 “(()))(” 不是。 由 ChatGPT 4.1 翻译