問題一覧 > 通常問題

No.1296 OR or NOR

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 20
作問者 : 沙耶花 / テスター : Kiri8128
お気に入りにしたユーザー ProblemId : 4597 / 自分の提出
問題文最終更新日: 2020-09-29 23:34:06
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 275 (順位表) の他の問題:

Problem Statement

You have a non-negative integer $x$. Initially, the value of $x$ is 0.

For $i=1,2,...,N$ in this order, you must choose one of the two types of operations below and perform it.

  • Operation 1: Replace $x$ with "the bitwise OR of $x$ and $a_i$".
  • Operation 2: Let $B$ be the binary representation of "the bitwise OR of $x$ and $a_i$". If $B$ has fewer than 60 digits, pad it with leading 0s to make it 60 digits.
    Then, replace $x$ with "the non-negative integer represented by the result of inverting all bits of $B$ (changing 0 to 1 and 1 to 0)".

You want the value of $x$ to be $b$ after finishing the $N$ operations.
Also, you would like to avoid performing Operation 2 as much as possible (because it is troublesome).

For each $i=1,2,...,Q$, find the minimum number of times Operation 2 must be performed when $b=b_i$.
However, if it is impossible to make $x=b_i$ after finishing the $N$ operations, output -1 instead.

Input

$N$
$a_1\ ...\ a_N$
$Q$
$b_1\ ...\ b_Q$

  • $1 \le N,Q \le 2 \times 10^5$
  • $0 \le a_i,b_i < 2^{60}$
  • All inputs are integers.

Output

Output $Q$ lines.
On the $i$-th line, output the answer for $b=b_i$.
Print a newline at the end.

Sample

Sample 1
Input
1
1
3
1 1152921504606846974 100
Output
0
1
-1

Performing Operation 1 gives $x=1$, and performing Operation 2 gives $x=1152921504606846974$.
It is not possible to get $x=100$.

Sample 2
Input
4
1 2 3 4
8
0 1 2 3 4 5 6 7
Output
2
-1
-1
2
2
-1
-1
0

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