A8902 | Main Sequence
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
As you know, Vova has recently become a new shaman in the city of Ultima Thule. So, he has received the shaman knowledge about the correct bracket sequences. The shamans of Ultima Thule have been using lots of different types of brackets since prehistoric times. A bracket type is a positive integer. The shamans define a correct bracket sequence as follows:
- An empty sequence is a correct bracket sequence.
- If ${a_{1},a_{2},...,a_{l}}$ and ${b_{1},b_{2},...,b_{k}}$ are correct bracket sequences, then sequence ${a_{1},a_{2},...,a_{l},b_{1},b_{2},...,b_{k}}$ (their concatenation) also is a correct bracket sequence.
- If ${a_{1},a_{2},...,a_{l}}$ — is a correct bracket sequence, then sequence  also is a correct bracket sequence, where $v$ $(v>0)$ is an integer.
For example, sequences ${1,1,-1,2,-2,-1}$ and ${3,-3}$ are correct bracket sequences, and ${2,-3}$ is not.
Moreover, after Vova became a shaman, he learned the most important correct bracket sequence ${x_{1},x_{2},...,x_{n}}$ , consisting of $n$ integers. As sequence $x$ is the most important, Vova decided to encrypt it just in case.
Encrypting consists of two sequences. The first sequence ${p_{1},p_{2},...,p_{n}}$ contains types of brackets, that is, $p_{i}=|x_{i}|$ ( $1<=i<=n$ ). The second sequence ${q_{1},q_{2},...,q_{t}}$ contains $t$ integers — some positions (possibly, not all of them), which had negative numbers in sequence ${x_{1},x_{2},...,x_{n}}$ .
Unfortunately, Vova forgot the main sequence. But he was lucky enough to keep the encryption: sequences ${p_{1},p_{2},...,p_{n}}$ and ${q_{1},q_{2},...,q_{t}}$ . Help Vova restore sequence $x$ by the encryption. If there are multiple sequences that correspond to the encryption, restore any of them. If there are no such sequences, you should tell so.
- An empty sequence is a correct bracket sequence.
- If ${a_{1},a_{2},...,a_{l}}$ and ${b_{1},b_{2},...,b_{k}}$ are correct bracket sequences, then sequence ${a_{1},a_{2},...,a_{l},b_{1},b_{2},...,b_{k}}$ (their concatenation) also is a correct bracket sequence.
- If ${a_{1},a_{2},...,a_{l}}$ — is a correct bracket sequence, then sequence  also is a correct bracket sequence, where $v$ $(v>0)$ is an integer.
For example, sequences ${1,1,-1,2,-2,-1}$ and ${3,-3}$ are correct bracket sequences, and ${2,-3}$ is not.
Moreover, after Vova became a shaman, he learned the most important correct bracket sequence ${x_{1},x_{2},...,x_{n}}$ , consisting of $n$ integers. As sequence $x$ is the most important, Vova decided to encrypt it just in case.
Encrypting consists of two sequences. The first sequence ${p_{1},p_{2},...,p_{n}}$ contains types of brackets, that is, $p_{i}=|x_{i}|$ ( $1<=i<=n$ ). The second sequence ${q_{1},q_{2},...,q_{t}}$ contains $t$ integers — some positions (possibly, not all of them), which had negative numbers in sequence ${x_{1},x_{2},...,x_{n}}$ .
Unfortunately, Vova forgot the main sequence. But he was lucky enough to keep the encryption: sequences ${p_{1},p_{2},...,p_{n}}$ and ${q_{1},q_{2},...,q_{t}}$ . Help Vova restore sequence $x$ by the encryption. If there are multiple sequences that correspond to the encryption, restore any of them. If there are no such sequences, you should tell so.
输入格式
The first line of the input contains integer $n$ ( $1<=n<=10^{6}$ ). The second line contains $n$ integers: $p_{1},p_{2},...,p_{n}$ $(1<=p_{i}<=10^{9})$ .
The third line contains integer $t$ ( $0<=t<=n$ ), followed by $t$ distinct integers $q_{1},q_{2},...,q_{t}$ $(1<=q_{i}<=n)$ .
The numbers in each line are separated by spaces.
The third line contains integer $t$ ( $0<=t<=n$ ), followed by $t$ distinct integers $q_{1},q_{2},...,q_{t}$ $(1<=q_{i}<=n)$ .
The numbers in each line are separated by spaces.
输出格式
Print a single string "NO" (without the quotes) if Vova is mistaken and a suitable sequence ${x_{1},x_{2},...,x_{n}}$ doesn't exist.
Otherwise, in the first line print "YES" (without the quotes) and in the second line print $n$ integers $x_{1},x_{2},...,x_{n}$ $(|x_{i}|=p_{i}; x_{qj}<0)$ . If there are multiple sequences that correspond to the encrypting, you are allowed to print any of them.
Otherwise, in the first line print "YES" (without the quotes) and in the second line print $n$ integers $x_{1},x_{2},...,x_{n}$ $(|x_{i}|=p_{i}; x_{qj}<0)$ . If there are multiple sequences that correspond to the encrypting, you are allowed to print any of them.
输入输出样例
输入 #1
2 1 1 0
输出 #1
YES 1 -1
输入 #2
4 1 1 1 1 1 3
输出 #2
YES 1 1 -1 -1
输入 #3
3 1 1 1 0
输出 #3
NO
输入 #4
4 1 2 2 1 2 3 4
输出 #4
YES 1 2 -2 -1
暂无题解
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?
提交通过
评测结果:Accepted