問題一覧 > 通常問題

No.2071 Shift and OR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 129
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : 遭難者遭難者
10 ProblemId : 8511 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-17 00:07:54

問題文

長さ NN の整数列 AA が与えられます。また整数 xx に対して関数 shift(x)\mathrm{shift}(x) を次のように定めます。

shift(x)=x2+215×(x mod 2)\mathrm{shift}(x)=\left \lfloor \frac{x}{2} \right \rfloor+2^{15} × (x\ \mathrm{mod}\ 2)

あなたは次の操作を何度でも行うことができます。(11 回も行わなくても良い。)

  • 1iN1 \le i \le N を満たす整数 ii を1つ選び、AiA_ishift(Ai)\mathrm{shift}(A_i) に置き換える。

操作後の A1 OR A2 OROR ANA_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \dots \mathrm{OR} \ A_N としてあり得る値のうち最大値を求めてください。 ただし、OR\mathrm{OR} はビットごとの論理和を表します。


▶︎x2\left \lfloor \frac{x}{2} \right \rfloor とは(クリックで開く)

x2\left \lfloor \frac{x}{2} \right \rfloorxx22 で割った時の商を表します。


▶︎x mod 2x\ \mathrm{mod}\ 2 とは(クリックで開く)

x mod 2x\ \mathrm{mod}\ 2xx22 で割った余りを表します。


入力

NN
A1A_1 A2A_2 \dots ANA_N

  • 1N2×1051 \le N \le 2×10^5
  • 1Ai<2161 \le A_i < 2^{16}
  • 入力は全て整数
  • 出力

    操作を行った後の A1 OR A2 OROR ANA_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \dots \mathrm{OR} \ A_N の最大値を出力してください。

    サンプル

    サンプル1
    入力
    2
    1 2
    出力
    49152

    次のように操作を行います。

    • i=1i=1 とする。A=(32768,2)A=(32768,2) となる。
    • i=2i=2 とする。A=(32768,1)A=(32768,1) となる。
    • i=2i=2 とする。A=(32768,32768)A=(32768,32768) となる。
    • i=2i=2 とする。A=(32768,16384)A=(32768,16384) となる。

    A1 OR A2=49152A_1 \ \mathrm{OR} \ A_2=49152 となり、これが最大です。

    サンプル2
    入力
    3
    6 2 9
    出力
    63488

    サンプル3
    入力
    5
    3 1 4 1 5
    出力
    65024

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