CF1451E1-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 of elements $ a_i $ and $ a_j $ $ (1 \leq i, j \le n $ , $ i \neq j) $
• OR $ i $ $ j $ : ask for the bitwise 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 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 $ .

样例:

样例输入1:

1
2
3
4
5
6
7

4

0

2

3

样例输出1:

1
2
3
4
5
6
7

OR 1 2

OR 2 3

XOR 2 4

! 0 0 2 3

思路:

实现:

 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
49
50
51
52
53
54
55

#include "ybwhead/ios.h"
int n;
const int maxn=5e5+10;
int x[maxn];
int tt=-1,tt1=-1;
map<int,int> y;
int a[maxn];
int main()
{
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cout<<"XOR "<<1<<' '<<i<<endl;
		cin>>x[i];
		if(y[x[i]])tt=i,tt1=y[x[i]];
		y[x[i]]=i;
		fflush(stdout);
	}
	if(tt>=0)
	{
		cout<<"AND "<<tt<<' '<<tt1<<endl;
		int xx;
		cin>>xx;
		fflush(stdout);
//		a[tt]=xx;a[tt1]=xx;
		a[1]=x[tt]^xx;
		for(int i=2;i<=n;i++)
		{
			a[i]=a[1]^x[i];
		}
	}
	else
	{
		int ttt=1,ttt1=2;
		for(int i=2;i<=3;i++)
			for(int j=i+1;j<=n;j++)
				if((x[i]^x[j])==n-1)
					ttt=i,ttt1=j;
		cout<<"AND "<<1<<' '<<ttt<<endl;
		int xx,yy,zz=0;
		cin>>xx;
		fflush(stdout);
		cout<<"AND "<<1<<' '<<ttt1<<endl;
		cin>>yy;
		fflush(stdout);
		int x1=xx*2+x[ttt],x2=yy*2+x[ttt1],x3=zz*2+(x[ttt]^x[ttt1]);
		a[1]=x1+x2-x3;
		a[1]>>=1;
		for(int i=2;i<=n;i++)a[i]=a[1]^x[i];
	}
	cout<<"! ";
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	fflush(stdout);
	return 0;
}