問題一覧 > 通常問題

No.2071 Shift and OR

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 131
作問者 : taiga0629kyopro / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 8511 / 自分の提出
問題文最終更新日: 2022-09-17 00:07:54
This 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. Back to the original
yukicoder contest 360 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A$ of length $N$. For an integer $x$, define the function $\mathrm{shift}(x)$ as follows.

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

You may perform the following operation any number of times. (You do not have to perform it even $1$ time.)

  • Choose 1 integer $i$ satisfying $1 \le i \le N$, and replace $A_i$ with $\mathrm{shift}(A_i)$.

Find the maximum possible value of $A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \dots \mathrm{OR} \ A_N$ after the operations. Here, $\mathrm{OR}$ denotes bitwise OR.


▶︎What is $\left \lfloor \frac{x}{2} \right \rfloor$? (click to open)

$\left \lfloor \frac{x}{2} \right \rfloor$ denotes the quotient when $x$ is divided by $2$.


▶︎What is $x\ \mathrm{mod}\ 2$? (click to open)

$x\ \mathrm{mod}\ 2$ denotes the remainder when $x$ is divided by $2$.


Input

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

  • $1 \le N \le 2×10^5$
  • $1 \le A_i < 2^{16}$
  • All inputs are integers.
  • Output

    Output the maximum value of $A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \dots \mathrm{OR} \ A_N$ after performing the operations.

    Sample

    Sample 1
    Input
    2
    1 2
    Output
    49152

    Perform the operations as follows.

    • Let $i=1$. Then $A=(32768,2)$.
    • Let $i=2$. Then $A=(32768,1)$.
    • Let $i=2$. Then $A=(32768,32768)$.
    • Let $i=2$. Then $A=(32768,16384)$.

    Then $A_1 \ \mathrm{OR} \ A_2=49152$, and this is the maximum.

    Sample 2
    Input
    3
    6 2 9
    Output
    63488

    Sample 3
    Input
    5
    3 1 4 1 5
    Output
    65024

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