A13906. Bitwise Queries (Easy Version)
编程题
普及/提高-
知识点
题目描述
The only difference between the easy and hard versions is the constraints on the number of queries.
This is an interactive problem.
Ridbit has a hidden array $a$ of $n$ integers which he wants Ashish to guess. Note that $n$ is a power of two. Ashish is allowed to ask three different types of queries. They are of the form
- AND $i$ $j$ : ask for the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of elements $a_i$ and $a_j$ $(1 \leq i, j \le n$ , $i \neq j)$
- OR $i$ $j$ : ask for the [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) of elements $a_i$ and $a_j$ $(1 \leq i, j \le n$ , $i \neq j)$
- XOR $i$ $j$ : ask for the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of elements $a_i$ and $a_j$ $(1 \leq i, j \le n$ , $i \neq j)$
Can you help Ashish guess the elements of the array?
In this version, each element takes a value in the range $[0, n-1]$ (inclusive) and Ashish can ask no more than $n+2$ queries.
This is an interactive problem.
Ridbit has a hidden array $a$ of $n$ integers which he wants Ashish to guess. Note that $n$ is a power of two. Ashish is allowed to ask three different types of queries. They are of the form
- AND $i$ $j$ : ask for the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of elements $a_i$ and $a_j$ $(1 \leq i, j \le n$ , $i \neq j)$
- OR $i$ $j$ : ask for the [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) of elements $a_i$ and $a_j$ $(1 \leq i, j \le n$ , $i \neq j)$
- XOR $i$ $j$ : ask for the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of elements $a_i$ and $a_j$ $(1 \leq i, j \le n$ , $i \neq j)$
Can you help Ashish guess the elements of the array?
In this version, each element takes a value in the range $[0, n-1]$ (inclusive) and Ashish can ask no more than $n+2$ queries.
输入格式
The first line of input contains one integer $n$ $(4 \le n \le 2^{16})$ — the length of the array. It is guaranteed that $n$ is a power of two.
输出格式
To ask a query print a single line containing one of the following (without quotes)
- "AND i j"
- "OR i j"
- "XOR i j"
where $i$ and $j$ $(1 \leq i, j \le n$ , $i \neq j)$ denote the indices being queried.For each query, you will receive an integer $x$ whose value depends on the type of query. If the indices queried are invalid or you exceed the number of queries however, you will get $x = -1$ . In this case, you should terminate the program immediately.
When you have guessed the elements of the array, print a single line "! " (without quotes), followed by $n$ space-separated integers — the elements of the array.
Guessing the array does not count towards the number of queries asked.
The interactor is not adaptive. The array $a$ does not change with queries.
After printing a query do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
Hacks
To hack the solution, use the following test format:
On the first line print a single integer $n$ $(4 \le n \le 2^{16})$ — the length of the array. It must be a power of 2. The next line should contain $n$ space-separated integers in the range $[0, n-1]$ — the array $a$ .
- "AND i j"
- "OR i j"
- "XOR i j"
where $i$ and $j$ $(1 \leq i, j \le n$ , $i \neq j)$ denote the indices being queried.For each query, you will receive an integer $x$ whose value depends on the type of query. If the indices queried are invalid or you exceed the number of queries however, you will get $x = -1$ . In this case, you should terminate the program immediately.
When you have guessed the elements of the array, print a single line "! " (without quotes), followed by $n$ space-separated integers — the elements of the array.
Guessing the array does not count towards the number of queries asked.
The interactor is not adaptive. The array $a$ does not change with queries.
After printing a query do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
Hacks
To hack the solution, use the following test format:
On the first line print a single integer $n$ $(4 \le n \le 2^{16})$ — the length of the array. It must be a power of 2. The next line should contain $n$ space-separated integers in the range $[0, n-1]$ — the array $a$ .
输入输出样例
输入 #1
4 0 2 3
输出 #1
OR 1 2 OR 2 3 XOR 2 4 ! 0 0 2 3
说明/提示
The array $a$ in the example is $[0, 0, 2, 3]$ .