#L9741. 洛谷模拟「KDOI-06-J」翻转与反转

洛谷模拟「KDOI-06-J」翻转与反转

「KDOI-06-J」翻转与反转

题目描述

小 W 有一个长度为 nn0101 序列 a1,a2,,ana_1,a_2,\ldots,a_n,他将对这个序列按顺序进行 nn 次操作。

在第 ii 次操作中(1in1\le i\le n),小 W 将按顺序执行以下两种变换:

  1. 将区间 [1,i][1,i] 中的数按下标翻转。形式化地说,在这次变换之后,序列 aa 将变为 $a_i,a_{i-1},\ldots,a_{1},a_{i+1},a_{i+2},\ldots,a_n$。
  2. 将区间 [1,i][1,i] 中的数按值翻转。形式化地说,在这次变换之后,对于任意 1ji1\le j\le i,若 aj=0a_j=0,则 aja_j 将变为 11,否则 aja_j 将变为 00

小 W 想要知道,在全部 nn 次操作结束后,序列 aa 中每个元素的值。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 nn,表示序列长度。

接下来一行 nn 个整数,表示序列 a1,a2,,ana_1,a_2,\ldots, a_n。保证 ai=0a_i=011

输出格式

输出到标准输出。

输出包含一行 nn 个整数,表示操作结束后序列 aa 中每个元素的值。

样例 #1

样例输入 #1

3
1 1 1

样例输出 #1

0 0 1

样例 #2

样例输入 #2

8
1 0 1 1 1 0 0 1

样例输出 #2

0 1 0 1 1 1 1 0

提示

【样例解释 #1】

序列 aa 的变化如下表所示:

操作次数 序列 aa 的变化
11 [1,1,1][1,1,1][0,1,1][1,1,1]\to [1,1,1]\to[0,1,1]
22 [0,1,1][1,0,1][0,1,1][0,1,1]\to [1,0,1]\to[0,1,1]
33 [0,1,1][1,1,0][0,0,1][0,1,1]\to [1,1,0]\to[0,0,1]

【样例解释 #2】

序列 aa 的变化如下表所示:

操作次数 操作后的序列 aa
- [1,0,1,1,1,0,0,1][1,0,1,1,1,0,0,1]
11 [0,0,1,1,1,0,0,1][0,0,1,1,1,0,0,1]
22 [1,1,1,1,1,0,0,1][1,1,1,1,1,0,0,1]
33 [0,0,0,1,1,0,0,1][0,0,0,1,1,0,0,1]
44 [0,1,1,1,1,0,0,1][0,1,1,1,1,0,0,1]
55 [0,0,0,0,1,0,0,1][0,0,0,0,1,0,0,1]
66 [1,0,1,1,1,1,0,1][1,0,1,1,1,1,0,1]
77 [1,0,0,0,0,1,0,1][1,0,0,0,0,1,0,1]
88 [0,1,0,1,1,1,1,0][0,1,0,1,1,1,1,0]

【样例 #3】

见选手文件中的 revflip/revflip3.inrevflip/revflip3.ans

【样例 #4】

见选手文件中的 revflip/revflip4.inrevflip/revflip4.ans

【数据范围】

对于所有数据保证:1n2×1061\le n\le 2\times 10^6,且对于任意 1in1\le i\le nai=0a_i=011

测试点编号 nn\le 特殊性质
131\sim 3 10310^3
454\sim 5 10510^5
676 \sim 7 2×1062\times 10^6 ai=0a_i=0
8108\sim 10