No.2195 AND Set

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 140
作問者 :

Shirotsume / テスター : 👑

p-adic

1 ProblemId : 8886 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2023-01-17 00:28:44

問題文

空集合 $S$ があります。以下に説明する $Q$ 個のクエリを処理してください。 $i$ 番目のクエリは以下の $3$ つの種類のうちいずれか $1$ つです。

クエリ1 : 集合 $S$ に整数 $x_i$ を追加する。すでに $S$ に $x_i$ が含まれているならば、なにもしない。
クエリ2 : 集合 $S$ から整数 $x_i$ を削除する。 $S$ に $x_i$ が含まれていないならば、なにもしない。
クエリ3 : 集合 $S$ に含まれるすべての要素の Bitwise AND を出力する。ただし、 $S$ が空のときは $-1$ を出力する。

Bitwise AND とは（クリックで展開）

$2$ つの非負整数 $X, Y$ について、 $X$ と $Y$ の Bitwise AND、 $X$ $\mathrm{AND}$ $Y$ は以下のように定義されます。

$X$ $\mathrm{AND}$ $Y$ を $2$ 進表記したときの $2^k$ $(k \geq 0)$ の位は、 $X$ の $2$ 進表記での $2^k$ の位と、 $Y$ の $2$ 進表記での $2^k$ の位の両方が $1$ である場合 $1$ 、そうでない場合 $0$

例えば、 $3$ $\mathrm{AND}$ $5 = 1$ です。（ $2$ 進表記すると $011$ $\mathrm{AND}$ $101 = 001$ ）

一般に $k$ 個の非負整数 $p_1, p_2, \dots, p_k$ の Bitwise AND は $( \dots ((p_1$ $\mathrm{AND}$ $p_2)$ $\mathrm{AND}$ $p_3)$ $\mathrm{AND}$ $\dots)$ $\mathrm{AND}$ $p_k)$ と定義され、これは $p_1, p_2, \dots, p_k$ の順番によらないことが証明できます。

制約

入力は全て整数
$1 \leq Q \leq 4 \times 10^5$
$0 \leq x_i < 2^{30}$
クエリは問題文にある形式で与えられる。
クエリ3が少なくとも $1$ 回与えられる。

入力

入力は標準入力から以下の形式で与えられる。

 $Q$ 
 $query_1$ 
 $query_2$ 
 $\vdots$ 
 $query_Q$

ただし、各クエリ

query_i

は、以下の形式のいずれかで与えられる。

クエリ1:

 $1$   $x_i$

クエリ2:

 $2$   $x_i$

クエリ3:

$3$

出力

クエリ3 が与えられた回数を $X$ として、 $X$ 行出力せよ。 $i$ 行目には、 $i$ 回目に与えられたクエリ3に対する答えを出力せよ。

サンプル

サンプル1

入力

出力

0
4

$1$ つめのクエリ $3$ が与えられた時点で、 $S = (1, 4)$ です。よって、 Bitwise AND は $0$ です。

$2$ つめのクエリ $3$ が与えられた時点で、 $S = (4)$ です。よって、 Bitwise AND は $4$ です。

複数回同じ値の追加クエリが来たとしても、複数個の値を追加するわけではないことに注意してください。

サンプル2

入力

出力

-1
0
-1
2

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