Translation Notice
This article was machine-translated using DeepSeek-R1.

• Original Version: Authored in Chinese by myself
• Accuracy Advisory: Potential discrepancies may exist between translations
• Precedence: The Chinese text shall prevail in case of ambiguity
• Feedback: Technical suggestions regarding translation quality are welcomed

ARC138 B - 01 Generation

Approach

Consider reverse thinking. We can prioritize removing trailing 0s (reverse operation of Operation B), then remove the leading 0 and flip the sequence if present (reverse operation of Operation A). Repeat these steps until the sequence becomes empty. If the process gets stuck, output No; otherwise, output Yes.

Proof of correctness:

• Assume there exists a sequence $A$ where our method outputs No but the correct answer is Yes;
• Then there must exist a step (possibly the first) where only reverse Operation A can be applied first instead of Operation B. Let the sequence before this step be $S$;
• Let $N=|S|$, then $S_1=S_N=0$;
• If we apply reverse Operation A first, we get $(S_2,S_3,\dots,S_{N-1},1)$;
• If we apply reverse Operation B first, we get $(S_1,S_2,\dots,S_{N-1})$;
• Comparing both results, performing reverse Operation B first does not block subsequent reverse Operation A, hence such sequence $S$ cannot exist;
• Conclusion: The approach is correct.

Code

In implementation, no actual sequence flipping is needed. Track the flip state using a boolean flipped. The actual value at position $i$ is $A_i = A_i' \oplus \text{flipped}$ (where $A_i'$ is the input sequence, $\oplus$ denotes XOR).

Use deque or track endpoints with l and r.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <cstdio>
#define maxn 200005
using namespace std;

bool a[maxn];

int main()
{
    int n = 0;
    char c;
    while((c = getchar()) != '\n')
        n = (n << 3) + (n << 1) + (c ^ 48);
    for(int i=0; i<n; i++, getchar())
        a[i] = getchar() ^ 48;
    bool flipped = false;
    for(int l=0, r=n-1; a[l]==flipped; flipped^=1, l++)
        while(!a[r] ^ flipped)
            if(l > --r)
                return puts("Yes"), 0;
    puts("No");
    return 0;
}