問題一覧 > 通常問題

No.1296 OR or NOR

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : 沙耶花沙耶花 / テスター : Kiri8128Kiri8128
1 ProblemId : 4597 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-09-29 23:34:06

問題文

あなたは非負整数 $x$ を持っています. はじめ, $x$ の値は0です.

あなたは$i=1,2,...,N$の順に, 下に示す2種類の操作のうち一方を選び, 実行しなければなりません.

  • 操作1: $x$ を「$x$ と $a_i$ のbitごとの論理和」に置き換える.
  • 操作2:「$x$ と $a_i$ のbitごとの論理和」の二進表記を$B$とする. $B$の桁数が60に満たないならば, 先頭側を0埋めして60桁に直す.
    そして, $x$ を「$B$のすべてのbitを反転(0は1に, 1は0に変更)した結果が表す非負整数」に置き換える.

あなたは$N$回の操作を終えた時点で $x$ の値を $b$ にしたいです.
また, なるべく操作2を行いたくありません.(面倒なので)

$i=1,2,...,Q$それぞれに対し, $b=b_i$の場合, 最小で何回操作2を行う必要があるかを求めてください.
ただし, $N$回の操作を終えた時点で$x=b_i$にできない場合, 代わりに-1を出力してください.

入力

$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}$
  • 入力はすべて整数

出力

$Q$行出力してください.
$i$ 行目には, $b=b_i$における答えを出力してください.
最後に改行してください.

サンプル

サンプル1
入力
1
1
3
1 1152921504606846974 100
出力
0
1
-1

操作1を行えば$x=1$, 操作2を行えば$x=1152921504606846974$となります.
$x=100$にはなりません.

サンプル2
入力
4
1 2 3 4
8
0 1 2 3 4 5 6 7
出力
2
-1
-1
2
2
-1
-1
0

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