No.1296 OR or NOR
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 :
沙耶花
/ テスター :
Kiri8128
タグ : / 解いたユーザー数 21
作問者 :
沙耶花
/ テスター :
Kiri8128
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。