308010: CF1451E2. Bitwise Queries (Hard Version)

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Bitwise Queries (Hard Version)

题意翻译

**本题使用SPJ交互评测** Ridbit 有一个隐藏的长度为 $n$ 的整数数组 $a$,想让 Ashish 去猜,注意 $n$ 是 $2$ 的**整数次幂**。Ridbit 允许 Ashish 提出三种不同类型的查询。它们分别是: AND $i$ $j$: 求元素 $a_i$ 和 $a_j$ 每一位的 [$and$](https://en.wikipedia.org/wiki/Bitwise_operation#AND) ($1≤i$,$j≤n$,$i≠j$) OR $i$ $j$: 求元素 $a_i$ 和 $a_j$ 每一位的 [$or$](https://en.wikipedia.org/wiki/Bitwise_operation#OR) ($1≤i$,$j≤n$,$i≠j$) XOR $i$ $j$: 求元素 $a_i$ 和 $a_j$ 每一位的 [$xor$](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) ($1≤i$,$j≤n$,$i≠j$) 有限制:(1) Ashish 最多可以询问 $n + 1$ 次。(2) $a$ 数组满足 $0 \le a_i \le n - 1$。 ### 输入 输入的第一行包含一个整数$n$,保证$n$在$4 \leq n \leq 2^{16}$,也就是数组的长度。同时保证$n$是$2$的整数次幂。 ### 输出 评测时,请打印一行包含以下内容之一(不带引号) - "AND i j" - "OR i j" - "XOR i j" 对于每次评测,你会得到一个$int$类型的$x$,这取决于评测数据的类型。如果查询的索引无效或超过查询数量,$x$会变成$-1$,即$x=-1$。当$x=-1$时,你应该立刻终止程序。 当计算出数组中的元素时,输出单行的"!"(英文格式,不带引号),然后输出$n$以空格分隔的整数数组的元素。 数组**并没有**对要求查询的数量计算。 **交互器不是自适应的**。数组$a$**不会**随着评测而改变。 输出后,不要忘记输出行尾并刷新输出。否则,会有`Idleness limit exceeded`报错。 使用: - C++中,使用`fflush(stdout)`或者`cout.flush()`; - Java中,使用`System.out.flush()`; - Pascal中,使用`flush(output)`; - Python中,使用`stdout.flush()`; - 其他语言中,按照其要求。 Translated by @[qinyihao](luogi.com.cn/user/348831) on 2020/11/22.

题目描述

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+1 $ 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 $ .

输入输出样例

输入样例 #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] $ .

Input

题意翻译

**本题使用SPJ交互评测** Ridbit 有一个隐藏的长度为 $n$ 的整数数组 $a$,想让 Ashish 去猜,注意 $n$ 是 $2$ 的**整数次幂**。Ridbit 允许 Ashish 提出三种不同类型的查询。它们分别是: AND $i$ $j$: 求元素 $a_i$ 和 $a_j$ 每一位的 [$and$](https://en.wikipedia.org/wiki/Bitwise_operation#AND) ($1≤i$,$j≤n$,$i≠j$) OR $i$ $j$: 求元素 $a_i$ 和 $a_j$ 每一位的 [$or$](https://en.wikipedia.org/wiki/Bitwise_operation#OR) ($1≤i$,$j≤n$,$i≠j$) XOR $i$ $j$: 求元素 $a_i$ 和 $a_j$ 每一位的 [$xor$](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) ($1≤i$,$j≤n$,$i≠j$) 有限制:(1) Ashish 最多可以询问 $n + 1$ 次。(2) $a$ 数组满足 $0 \le a_i \le n - 1$。 ### 输入 输入的第一行包含一个整数$n$,保证$n$在$4 \leq n \leq 2^{16}$,也就是数组的长度。同时保证$n$是$2$的整数次幂。 ### 输出 评测时,请打印一行包含以下内容之一(不带引号) - "AND i j" - "OR i j" - "XOR i j" 对于每次评测,你会得到一个$int$类型的$x$,这取决于评测数据的类型。如果查询的索引无效或超过查询数量,$x$会变成$-1$,即$x=-1$。当$x=-1$时,你应该立刻终止程序。 当计算出数组中的元素时,输出单行的"!"(英文格式,不带引号),然后输出$n$以空格分隔的整数数组的元素。 数组**并没有**对要求查询的数量计算。 **交互器不是自适应的**。数组$a$**不会**随着评测而改变。 输出后,不要忘记输出行尾并刷新输出。否则,会有`Idleness limit exceeded`报错。 使用: - C++中,使用`fflush(stdout)`或者`cout.flush()`; - Java中,使用`System.out.flush()`; - Pascal中,使用`flush(output)`; - Python中,使用`stdout.flush()`; - 其他语言中,按照其要求。 Translated by @[qinyihao](luogi.com.cn/user/348831) on 2020/11/22.

加入题单

上一题 下一题 算法标签: