No.911 ラッキーソート
ei1333333
treeoneThis statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
Problem Statement
There is a sequence $A$ of length $N$, and any $2$ of its elements are distinct from each other.
Perform the following operation exactly $1$ time.
- Choose an integer $x$ between $L$ and $R$, inclusive.
- Replace every element of the sequence with $A_i\ \mathrm{XOR}\ x$.
$\mathrm{XOR}$ denotes the bitwise exclusive OR.
Find the number of values of $x$ for which the operation makes the sequence monotonically increasing. Here, monotonically increasing means that $A_i \lt A_{i+1}$ holds for all $i(1 \leq i \lt N)$.
Input
$N$ $L$ $R$ $A_1$ $A_2$ $\cdots$ $A_N$
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq L \leq R \lt 2^{61}$
- $0 \leq A_i \lt 2^{61}$
- If $i \neq j$, then $A_i \neq A_j$
- All input values are integers
Output
Print the answer on $1$ line.
Sample
Sample 1
Input
6 1325 1350 1332 1335 1334 1329 1328 1331
Output
4
For example, when $x = 1333$, the sequence after the operation is $\{1, 2, 3, 4, 5, 6\}$, which is monotonically increasing.
On the other hand, for example, when $x = 1334$, the sequence after the operation is $\{2, 1, 0, 7, 6, 5\}$, which is not monotonically increasing.
Sample 2
Input
4 100 500 1 7 41 23
Output
0
There are cases where not even $1$ value of $x$ makes the sequence monotonically increasing.
Sample 3
Input
1 0 10000 1
Output
10001
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。