#P12748. [thupc 2025 final] conditionop
[thupc 2025 final] conditionop
Background
三目运算符表达式 a?b:c
的含义是:如果 a
为真,则返回 b
,否则返回 c
。
三目运算符是右结合的,例如:a?b:c?d:e
等价于 a?b:(c?d:e)
。
$0$ 表示假,$1$ 表示真。
Description
给定一个长度为 $2n+1$ 的 01 串,你需要使用 $n$ 次三目运算符,即在中间插入恰好 $n$ 个 ?
和 $n$ 个 :
以及若干括号,使得表达式的结果为 $1$,或者判断无解。
如果有解,你需要输出一个满足条件的表达式;如果无解,则输出 No
。
你输出的表达式中数字的顺序必须和原串一致,并且使用的三目运算符次数必须恰好为 $n$(即每两个相邻的数字之间都有一个 ?
或 :
)。
你输出的表达式长度不能超过 $10n+1000$。
可以证明,如果存在解,则一定存在满足条件的构造方案。
Format
Input
第一行一个正整数 $n$,满足 $1 \le n \le 1.5\times 10^5$。 第二行一个长度为 $2n+1$ 的 01 串,表示给定的字符串。
Output
- 如果无解,输出一行
No
。 - 如果有解,第一行输出
Yes
,第二行输出一个值为 $1$ 的表达式。
Samples
2
10101
Yes
(1?0:1)?0:1
2
00000
No