【Codeforces 1451 E1】Bitwise Queries (Easy Version)，交互题，位运算，猜数组

problem

E1. Bitwise Queries (Easy Version)
time limit per test4 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 of elements ai and aj (1≤i,j≤n, i≠j)
OR i j: ask for the bitwise OR of elements ai and aj (1≤i,j≤n, i≠j)
XOR i j: ask for the bitwise XOR of elements ai and aj (1≤i,j≤n, i≠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.

Input
The first line of input contains one integer n (4≤n≤216) — the length of the array. It is guaranteed that n is a power of two.

Interaction
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≤i,j≤n, i≠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≤n≤216) — 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.

Example
inputCopy
4

0

2

3

outputCopy
OR 1 2

OR 2 3

XOR 2 4

! 0 0 2 3
Note
The array a in the example is [0,0,2,3].

solution

/*
题意：
+ 交互题，设定一个长为n的数组，给出n。
+ 每次可以询问任意两个值|,&,^的值，最多n+2次，求出原数组。
思路：
+ 已知a+b==a&b+a|b，所以可以用3次&和3次|求出a[1]+a[2],a[1]+a[3],a[2]+a[3]进而求出a[1],a[2],a[3]，合计6次。
+ 已知a+b==a^b+2(a&b),并且(a^b)^(a^c)==b^c，所以可以用6-1=5次求出a[1],a[2],a[3]。
+ 剩下的n-3个数，可以用a[1]^a[i]用n-3次求出答案，合计n+2次。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 600000+10;
const int mod = 1e9+7;

int main(){
	ios::sync_with_stdio(false);
	int T=1;  //cin>>T; //Idleness limit exceeded
	while(T--){
		int n;  cin>>n;
		vector<int>a(n+1);
		
		int ab1, ab2,ac1, ac2, bc1,bc2;
		cout<<"XOR 1 2\n"; fflush(stdout); cin>>ab1;
		cout<<"AND 1 2\n"; fflush(stdout); cin>>ab2;
		cout<<"XOR 1 3\n"; fflush(stdout); cin>>ac1;
		cout<<"AND 1 3\n"; fflush(stdout); cin>>ac2;
		bc1 = ab1 ^ ac1;
		cout<<"AND 2 3\n"; fflush(stdout); cin>>bc2;
		int x=ab1+2*ab2, y=ac1+2*ac2, z=bc1+2*bc2;
		a[1] = (x+y-z)/2;
		a[2] = (x+z-y)/2;
		a[3] = (y+z-x)/2;
		
		for(int i = 4; i <= n; i++){
			cout<<"XOR 1 "<<i<<"\n";
			fflush(stdout);
			int t;  cin>>t;
			a[i] = t^a[1];
		}
		cout<<"! ";
		for(int i = 1; i <= n; i++)
			cout<<a[i]<<" ";
		cout<<endl;
		fflush(stdout);
	}
	return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/114076427