問題一覧 > 通常問題

No.2071 Shift and OR

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

問題文

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

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

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

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

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


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

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


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

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


入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

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

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

    サンプル

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

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

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

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

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

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

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