問題一覧 > 通常問題

No.3539 Parentheses Square

レベル : / AI推定難易度 : 2250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 13
作問者 : nauclhlt / テスター : もの
お気に入りにしたユーザー ProblemId : 12106 / 自分の提出
問題文最終更新日: 2026-05-07 18:09:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 499 (順位表) の他の問題:

Problem Statement

If repeatedly deleting () contained as a (contiguous) substring of a string $X$ can turn $X$ into the empty string, and only in that case, $X$ is called a correct parenthesis sequence.

You are given a positive integer $N$ and $N$ strings of length $N$ consisting of ., (, ): $T_1, T_2, \cdots, T_N$.

Is it possible to replace every . contained in each of $T_1, T_2, \cdots, T_N$ with ( or ) to make $N$ pairwise distinct correct parenthesis sequences? If it is possible, construct one such way.

Formally, determine whether there exists an $N$-tuple $S_1, S_2, \cdots, S_N$ of strings of length $N$ satisfying all of the following conditions. If one exists, construct one.

  • For each $i(1\leq i\leq N)$, $S_i$ is a correct parenthesis sequence
  • If $T_{i, j}(1\leq i, j\leq N)$ is not ., then $S_{i, j}=T_{i, j}$
  • For $1\leq i, j\leq N$, if $i\neq j$ then $S_i\neq S_j$

Here, for a string $X$, $X_i$ denotes the $i$-th character of $X$.

Input

$N$
$T_1$
$T_2$
$\vdots$
$T_N$
  • $1\leq N\leq 200$
  • $T_i$ is a string of length $N$ consisting of ., (, and )
  • $N$ is an integer

Output

If a tuple $S_1, S_2, \cdots, S_N$ satisfying the conditions exists, output $N$ lines in the following format.

$S_1$
$S_2$
$\vdots$
$S_N$

If none exists, output -1.

$-1$

Print a newline at the end.

Sample

Sample 1
Input
8
(.......
.......)
.(......
....)...
......()
........
()......
.(....).
Output
((()()))
((())())
(()(()))
(()()())
((()))()
(()())()
()((()))
(((())))

There may be multiple solutions; the one shown here is just one example.

Sample 2
Input
2
..
..
Output
-1

No $S_1, S_2$ satisfying the conditions exist. Therefore, output only -1.

Sample 3
Input
4
))))
((((
....
....
Output
-1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。