b066: 熵用魔法 (Entropy Magic)
Tags : ytp
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-10-10 11:28

Content

作為一個物理大師,小Y盡力想避免這個宇宙產生「熱寂」。他從小P那邊學到了一個可以降低熵的魔法,希望能夠拯救整個世界。但是這個魔法的使用存在某些限制,為了簡單起見,我們將整個宇宙視為一個長度為N 的序列$a_1, a_2,a_3,
,a_N$,每一個元素都是0或1,這個魔法可以選擇一個長度為3並非全部都是0或1的區間 $a_i, a_{i+1}, a_{i+2}(1 ≤i≤
N-2)$,之後將其換成 $a_{i+1} \oplus a_{i+2},a_i \oplus a_{i+2}, a_{i} \oplus a_{i+1} $

 $\oplus$ 代表  XOR

 

小Y想問你是否可以使用這個魔法將整個序列變成0,把熵降到最低。可以證明如果能用魔法將整個序列變成0,那麼必定可以使用 2N 次以内的魔法就達成,因此假如可以用這個魔法將整個序列變成0,請輸出一個長度不超過 2N 的操作序列如果有很多個操作序列滿足條件,請輸出任意一個。

Input

輸人的第一行包含一正整數N,代表小Y將整個宇宙視為一個長度為N的序列。
下一行包含一個長度為N的序列$a_1, a_2, ..., a_N$,代表宇宙被轉換成的序列

$N ≤ 10^6$

Output

第一行輸出 “YES” 或“NO” 代表是否可以使用這個魔法將整個序列變成 0。

如果是 “YES” 的話,第二行輸出一個整數M,代表你可以使用恰好M次魔法將整個序列變成0。

第三行請輸出 M 個正整數b,代表第i個操作會對 $a_i, a_{i+1}, a_{i+2}$ 使用魔法。如果有多種使用魔法的方式可以滿足條件,請輸出任意一個。若不需任何魔法即可滿足,則輸出0。
如果 M >2N 或是依序使用這些魔法並不會讓整個序列變成 0,你將會獲得 WA

Sample Input
5
0 0 0 0 0
Sample Output
YES
0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
ytp
出處:
ytp_2021 [管理者:
Ching367436 (Ching367436)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」