#P9702. 括号序列

    ID: 6327 传统题 1000ms 128MiB 尝试: 2 已通过: 1 难度: 4 上传者: 标签>难度分类普及构造与建模序列构造贪心支配关系CF1400

括号序列

括号序列

题目描述

给定仅含 (、)、? 的字符串 ss,保证长度为偶数。请将每个 ? 替换为左括号或右括号,使整个字符串为合法括号序列,且它的每个非空真前缀都不是合法括号序列。真前缀指不等于整个字符串的前缀。

合法括号序列递归定义如下:空串合法;若 pp 合法,则 (p) 合法;若 p,qp,q 均合法,则它们的拼接 pqpq 合法。

本题使用特殊判题,可以输出任意一种合法方案。若无解,输出 Are you kidding me?。

输入格式

从标准输入读入一行字符串 ss。

输出格式

输出一行,表示构造方案;无解时输出 Are you kidding me?。

样例 1 输入

(?????

样例 1 输出

(()())

样例 2 输入

(???(???(?

样例 2 输出

Are you kidding me?

其他样例

样例 3 见下发文件 bracket3.in、bracket3.out,满足子任务 3 的性质。样例 4 见 bracket4.in、bracket4.out,满足子任务 2 的性质。

数据规模

子任务 长度范围 特殊性质 依赖关系 分值
1 2≤∣s∣≤162\le \lvert s\rvert\le16 无 无 15
2 2≤∣s∣≤1032\le \lvert s\rvert\le10^3 1 25
3 2≤∣s∣≤3×1052\le \lvert s\rvert\le3\times10^5 不含 ? 无 15
4 无 1、2、3 45