Overview

Encryption is the operation of “XOR the received value with your own key,” repeated from left to right in order. Therefore, the final result can be computed in one shot as “the XOR of \(X\) with all the keys actually used.” After that, we just need to cancel out the keys of servers that are treated as \(0\) due to “sandwich detection.”

Analysis

Key Insight 1: A chain of XORs can be computed all at once

If servers \(1\) through \(N\) process normally, the output is:

• After server 1: \(X \oplus A_1\)
• After server 2: \((X \oplus A_1) \oplus A_2 = X \oplus A_1 \oplus A_2\)
• …
• Final: \(X \oplus A_1 \oplus A_2 \oplus \cdots \oplus A_N\)

Since XOR satisfies the associative and commutative laws, we can get the same result by “XORing everything together” without simulating step by step.

Key Insight 2: “Using 0” is the same as “not using that key”

Due to sandwich detection, when a server \(j\) (\(2 \le j \le N-1\)) satisfies:

• \(A_{j-1} = A_{j+1}\) and \(A_{j-1} \ne A_j\)

server \(j\) XORs with \(0\) instead of \(A_j\).

However, since \(Y \oplus 0 = Y\) in XOR, this is equivalent to “not XORing \(A_j\) when it was supposed to be XORed.”

How to compute the final result

First, compute the total XOR under normal processing:

• \(\text{total} = A_1 \oplus A_2 \oplus \cdots \oplus A_N\)

From this, for each server \(j\) that is treated as 0, we need to remove \(A_j\) from \(\text{total}\) since it is “not used.”

In the world of XOR, “removal” is the same as XORing once more (\(A \oplus A = 0\)):

• Computing \(\text{total} \oplus A_j\) cancels out the \(A_j\) within \(\text{total}\)

Therefore, if we prepare the XOR of all keys from servers treated as 0:

• \(\text{abnormal} = \bigoplus(\text{all } A_j \text{ treated as } 0)\)

then the answer is:

• \(\text{ans} = X \oplus \text{total} \oplus \text{abnormal}\)

(Example) When \(A = [5, 7, 5]\), the middle element satisfies \(A_1=A_3\) and \(A_2 \ne A_1\), so it is treated as 0. - Normal: \(X \oplus 5 \oplus 7 \oplus 5\) - Actual: \(X \oplus 5 \oplus 0 \oplus 5 = X\) Using the formula above, \(\text{total}=5\oplus7\oplus5=7\), \(\text{abnormal}=7\), so \(X \oplus 7 \oplus 7 = X\), which matches.

Why a naive approach can be dangerous

While a step-by-step simulation itself is possible in \(O(N)\), if the implementation searches the surrounding elements each time for the “treated as 0” check, or re-examines candidates multiple times, it can result in unnecessary \(O(N^2)\) complexity in the worst case. In this problem, the check for each \(j\) only needs to be done once (just looking at \(A_{j-1}, A_j, A_{j+1}\)), so the entire problem can be solved with a single pass.

Algorithm

1. Compute the XOR of all elements in array \(A\) to create total_xor.
2. For \(i=1\) to \(N-2\) (or i=0..N-3 in 0-indexed), examine the triple \((A_i, A_{i+1}, A_{i+2})\):
   • If \(A_i = A_{i+2}\) and \(A_i \ne A_{i+1}\), then abnormal_xor ^= A[i+1]
3. Output the answer as X ^ total_xor ^ abnormal_xor.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (additional space excluding the input array \(A\))

Implementation Notes

• When implementing with 0-indexed arrays, it is safe to check the sandwich condition for i=0..N-3 by examining A[i], A[i+1], A[i+2].

• XOR can be computed using the ^ operator (Python).

• Since \(N\) can be up to \(2\times 10^5\), in Python it is more stable to read input all at once using sys.stdin.buffer.read() for faster I/O.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, X = data[0], data[1]
    A = data[2:2 + N]

    total_xor = 0
    for v in A:
        total_xor ^= v

    abnormal_xor = 0
    for i in range(N - 2):
        if A[i] == A[i + 2] and A[i] != A[i + 1]:
            abnormal_xor ^= A[i + 1]

    print(X ^ total_xor ^ abnormal_xor)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.