CF1153C Serval and Parenthesis Sequence

Serval 很快就和 Japari 幼儿园说再见，开始了在 Japari 小学的生活。 在他最喜欢的数学课上，老师教了他以下有趣的定义。 括号序列是一个只包含字符 “(” 和 “)” 的字符串。 一个合法括号序列是指，通过在原序列字符之间插入字符 “1” 和 “+”，可以变换成一个合法的算术表达式的括号序列。例如，括号序列 “()()”、“(())” 是合法的（变换后的表达式分别为：“(1+1)+(1+1)”、“((1+1)+1)”），而 “)(” 和 “)” 则不是。注意，空字符串根据定义也是合法括号序列。 我们定义 $|s|$ 为字符串 $s$ 的长度。字符串 $s = s_1s_2\dots s_{|s|}$ 的严格前缀 $s[1\dots l]$（$1\leq l

第一行包含一个整数 $|s|$（$1\leq |s|\leq 3 \times 10^5$），表示字符串的长度。 第二行包含一个只由 “(”、“)”、和 “?” 组成的字符串 $s$。

输出一行，表示替换后的字符串。 如果有多种方案，输出任意一种。 如果无解，输出一行 “:(”。

可以证明，第二个样例无解，因此输出 “:(”。 由 ChatGPT 4.1 翻译