No.2195 AND Set
タグ : / 解いたユーザー数 145
作問者 :
Problem Statement
There is an empty set $S$. Process the $Q$ queries described below. The $i$-th query is one of the following $3$ types (exactly $1$ of them).
- Query 1: Add the integer $x_i$ to the set $S$. If $S$ already contains $x_i$, do nothing.
- Query 2: Remove the integer $x_i$ from the set $S$. If $S$ does not contain $x_i$, do nothing.
- Query 3: Print the Bitwise AND of all elements in the set $S$. However, if $S$ is empty, print $-1$.
What is Bitwise AND? (click to expand)
For $2$ non-negative integers $X, Y$, the Bitwise AND of $X$ and $Y$, denoted $X$ $\mathrm{AND}$ $Y$, is defined as follows.
- When $X$ $\mathrm{AND}$ $Y$ is written in base $2$, the digit in the $2^k$ $(k \geq 0)$ place is $1$ if both the digit in the $2^k$ place of $X$ in base $2$ and the digit in the $2^k$ place of $Y$ in base $2$ are $1$, and $0$ otherwise.
For example, $3$ $\mathrm{AND}$ $5 = 1$. (In base $2$: $011$ $\mathrm{AND}$ $101 = 001$.)
In general, the Bitwise AND of $k$ non-negative integers $p_1, p_2, \dots, p_k$ is defined as $( \dots ((p_1$ $\mathrm{AND}$ $p_2)$ $\mathrm{AND}$ $p_3)$ $\mathrm{AND}$ $\dots)$ $\mathrm{AND}$ $p_k)$, and it can be proved that this does not depend on the order of $p_1, p_2, \dots, p_k$.
Constraints
- All inputs are integers.
- $1 \leq Q \leq 4 \times 10^5$
- $0 \leq x_i < 2^{30}$
- The queries are given in the format described in the problem statement.
- Query 3 is given at least $1$ time.
Input
The input is given from standard input in the following format.
$Q$ $query_1$ $query_2$ $\vdots$ $query_Q$Here, each query $query_i$ is given in one of the following formats.
Query 1:
$1$ $x_i$
Query 2:
$2$ $x_i$
Query 3:
$3$
Output
Let $X$ be the number of times Query 3 is given. Print $X$ lines. On the $i$-th line, print the answer to the $i$-th given Query 3.
Sample
Sample 1
Input
7 1 1 1 4 3 2 3 1 1 2 1 3
Output
0 4
When the $1$st query of type $3$ is given, $S = (1, 4)$. Therefore, the Bitwise AND is $0$.
When the $2$nd query of type $3$ is given, $S = (4)$. Therefore, the Bitwise AND is $4$.
Note that even if an add query with the same value is given multiple times, the value is not added multiple times.
Sample 2
Input
20 3 1 1 2 0 1 3 1 2 1 1 3 2 0 2 1 2 1 2 1 2 3 2 2 3 1 2 1 2 1 3 2 3 2 1 3
Output
-1 0 -1 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。