CF 286C(Main Sequence-贪心括号婚配)

CF 286C(Main Sequence-贪心括号匹配)
C. Main Sequencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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,?a2,?...,?al} and {b1,?b2,?...,?bk} are correct bracket sequences, then sequence {a1,?a2,?...,?al,?b1,?b2,?...,?bk} (their concatenation) also is a correct bracket sequence.}
• If {a1,?a2,?...,?al} — 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,?x2,?...,?xn}, consisting of nintegers. 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,?p2,?...,?pn} contains types of brackets, that is, pi?=?|xi| (1?≤?i?≤?n). The second sequence {q1,?q2,?...,?qt} contains t integers — 这些地方必须取负数 {x1,?x2,?...,?xn}.}

  Unfortunately, Vova forgot the main sequence. But he was lucky enough to keep the encryption: sequences {p_{1,?p2,?...,?pn} and{q1,?q2,?...,?qt}. 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.}

  Input

  The first line of the input contains integer n (1?≤?n?≤?10^{6). The second line contains n integers: p_{1,?p2,?...,?pn (1?≤?pi?≤?109).}}

  The third line contains integer t (0?≤?t?≤?n), followed by t distinct integers q_{1,?q2,?...,?qt (1?≤?qi?≤?n).}

  The numbers in each line are separated by spaces.

  Output

  Print a single string "NO" (without the quotes) if Vova is mistaken and a suitable sequence {x_{1,?x2,?...,?xn} doesn't exist.}

  Otherwise, in the first line print "YES" (without the quotes) and in the second line print n integers x_{1,?x2,?...,?xn (|xi|?=?pi; xqj?<?0). If there are multiple sequences that correspond to the encrypting, you are allowed to print any of them.}

  Sample test(s)input

  21 10

  output

  YES1 -1

  input

  41 1 1 11 3

  output

  YES1 1 -1 -1

  input

  31 1 10

  output

  NO

  input

  41 2 2 12 3 4

  output

  YES1 2 -2 -1

  贪心，从后向前做，尽可能取左括号。

  #include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<functional>#include<algorithm>#include<stack>using namespace std;#define MAXN (1000000+10)#define MAXP (1000000000+10)int n,m,a[MAXN],ans[MAXN],tot;bool b[MAXN];int s[MAXN],size=0;int main(){memset(b,0,sizeof(b));scanf("%d",&n);tot=n+1;if (n%2) {printf("NO\n");return 0;}for (int i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d",&m);for (int i=1;i<=m;i++) {int p;scanf("%d",&p);b[p]=1;}for (int i=n;i;i--){if (size==0||s[size]!=a[i]||b[i]){s[++size]=a[i];ans[--tot]=-a[i];}else ans[--tot]=s[size--];}if (size) printf("NO\n");else{printf("YES\n");for (int i=1;i<n;i++) printf("%d ",ans[i]);printf("%d\n",ans[n]);}return 0;}