問題一覧 > 通常問題

No.2024 Xer

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 : milkcoffeemilkcoffee / テスター : first_vilfirst_vil
17 ProblemId : 8133 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-27 14:38:41

問題文

長さ $N$ の非負整数列 $A$ と、非負整数 $X$ が与えられます。あなたは $A$ の要素を自由に並び替えることができます。
以下の条件を満たすように $A$ を並び替えることはできますか?

  • 各整数 $i \ (1 \leq i \leq N-1)$ について、以下の両方が成り立つ。
    • $A_i < A_{i+1} \ \mathrm{xor} \ X$
    • $A_i \ \mathrm{xor} \ X < A_{i+1} $

入力

$N\ \ X$
$A_1 \ \ A_2 \ \cdots \ A_N $

  • $2 \leq N \leq 2 \times 10^5$
  • $0 \leq X < 2^{30}$
  • $0 \leq A_i < 2^{30} \ (1 \leq i \leq N)$
  • 入力は全て整数である

出力

条件を満たすように $A$ を並び替えられる場合は Yes, そうでなければ No を出力してください。

サンプル

サンプル1
入力
3 2
4 0 8
出力
Yes

例えば $A=(0,4,8)$ という並べ方は条件を満たします。

サンプル2
入力
2 0
1000000000 1000000000
出力
No

条件を満たす並び替え方は存在しません。

サンプル3
入力
21 58
83 288 284 150 486 432 167 474 221 137 241 207 13 460 428 466 20 471 334 173 422
出力
No

サンプル4
入力
20 36251
312825 61132 198714 286989 525118 68197 276005 239658 483138 88020 214783 133172 117691 301236 416410 575820 339887 255432 6 263987
出力
Yes

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。