No.3046 White Tiger vs Monster
Problem Statement
White Tiger is fighting $N$ monsters.
The health of the $i$-th monster is $A_i$. White Tiger's initial attack power is $B$.
White Tiger can attack a monster if and only if its current attack power is greater than or equal to the monster's health.
When White Tiger attacks a monster, that monster disappears. Furthermore, letting $X$ be White Tiger's attack power before the attack and $Y$ be the health of the attacked monster, White Tiger's attack power changes to $X \oplus Y$.
Here, $\oplus$ denotes bitwise exclusive OR.
If White Tiger chooses the order of attacking monsters optimally, what is the maximum number of monsters it can defeat?
Constraints
- $1 \leq N \leq 2\times 10^5$
- $1 \leq B \leq 10^{18}$
- $1 \leq A_i \leq 10^{18}$
Input
The input is given from Standard Input in the following format.
$N\ B$ $A_1\ A_2 \ldots \ A_N$
Output
Print on one line the maximum number of monsters White Tiger can defeat.
Sample
Sample 1
Input
3 5 1 3 5
Output
3
White Tiger can defeat all 3 monsters as follows.
- Defeat monster 2. White Tiger's attack power becomes $5 \oplus3 = 6$.
- Defeat monster 3. White Tiger's attack power becomes $6 \oplus 5 = 3$.
- Defeat monster 1. White Tiger's attack power becomes $3 \oplus 1 = 2$.
Therefore, the answer is $3$.
Sample 2
Input
2 1 1 2
Output
1
Sample 3
Input
15 49497 1964 616 419 161 9 2 6 19 49 49 4619649 16 19 16961 9619
Output
14
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。