Reincarnation

正因为梦易碎，才格外美好。

P8849 『JROI-7』hibernal & CF835E The penguin's game

发表于 更新于 分类于
本文字数： 6.9k 阅读时长 ≈ 6 分钟

有意思的交互题。

因为考虑到有 的话，还明确规定了 次，我们可以很容易发现 ，那我们大胆猜测这道题可以在 的时间内解决，就往位运算或者二分那个方面想。

对于主题库那道题得到两个集合的异或以及 上得到一个集合里的异或，实际上求得的都是同一个东西——两个特殊点是否同时在你选取的集合中。这是显然的，可以自证。

那么我们考虑二分，查找 ，这样可以得到其中一个点所在的位置，然后把整个序列划分成两部分分别二分，这样的话，时间复杂度是不会超过 的。

具体来讲，是如下操作：

我们钦定一个二进制位 （从 的最高位向下枚举），然后每一次把 的 都提出来组成集合（即二进制位 为 的所有数），直到找到某一位 使得两个特殊点不在同一个集合里，从这一位开始，我们可以二分得到集合答案。

我们先枚举左集合得到第一个特殊点记作 ，也就是二分 区间，这是左集合的答案，用同样的方法得到右集合答案，二分 区间，得到第二个特殊点记为 。

现在我们的情况是，用了 的时间获得了 在 位以下的答案，现在考虑向上推进。注意到，我们每一次向上推一位，都会得到两个相同的答案记作 ，他们与原答案的不同在于 位的不同，这样的话，我们需要在这两者中判断，这是简单的，直接询问某一个，得到信息，如果是，则当前的 就是答案，否则 可能是答案，并向 位推进。

两道题的思路是一样的。

感谢 爷帮我秒掉了这题。

[open]
 
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// ----- Eternally question-----
// Problem: P8849 『JROI-7』hibernal
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8849
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-11-12 15:47:21
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=(1<<10)+10;
int Test,N,Cnt;
inline bool ask(std::vector<int>vec)
{
	if(vec.empty()||(int)vec.size()==N) return 0;
	if(++Cnt>19) assert(0);
	std::cout<<"? "<<vec.size()<<' ';
	for(int x:vec) std::cout<<x<<' ';
	std::cout<<std::endl;
	int type;
	std::cin>>type;
	return type;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	std::cout.tie(0)->sync_with_stdio(false),std::cin.tie(0);
	read(Test);
	while(Test--)
	{
		read(N);
		int l=std::log2(N),r,type;
		Cnt=0;
		for(r=l;r>=0;--r)
		{
			std::vector<int>vec;
			for(int i=1;i<=N;++i)
				if(i&(1<<r)) vec.push_back(i);
			if(ask(vec)) break;
		}
		// std::cout<<r<<'\n';
		int ql=0,qr=(1<<r)-1,ress;
		while(ql<qr)
		{
			int mid=(ql+qr)>>1;
			std::vector<int>vec;
			for (int i=1;i<=N;++i)
				if((i&((1<<(r+1))-1))>=ql&&(i&((1<<(r+1))-1))<=mid) vec.push_back(i);
			if(ask(vec)) qr=mid;
			else ql=mid+1;
		}
		ress=ql;
		// std::cout<<"Done "<<ress<<'\n';
		ql=(1<<r),qr=(1<<(r+1))-1;int resf;
		while(ql<qr)
		{
			int mid=(ql+qr)>>1;
			std::vector<int>vec;
			for(int i=1;i<=N;++i)
				if((i&((1<<(r+1))-1))>=ql&&(i&((1<<(r+1))-1))<=mid) vec.push_back(i);
			if(ask(vec)) qr=mid;
			else ql=mid+1;
		}
		resf=ql;
		// puts("done");
		// std::cout<<ress<<' '<<resf<<std::endl;
		for(r=r+1;r<=l;++r)
		{
			std::cout<<"? 1 "<<ress<<std::endl;
			std::cin>>type;
			if(!type) ress+=(1<<r),resf+=(1<<r);
			else break;
		}
		std::cout<<"! "<<ress<<" "<<resf<<std::endl;
	}
	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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// ----- Eternally question-----
// Problem: CF835E The penguin's game
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF835E
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-11-13 18:58:47
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define int long long
int X,Y,N,Xr;
inline bool query(std::vector<int>Vec)
{
	std::cout<<"? "<<Vec.size()<<" ";
	for(int i:Vec) std::cout<<i<<" ";std::cout<<std::endl;
	int type;std::cin>>type;
	if(Vec.size()&1)
	{
		if(type==X) return 0;
		if(type==Y) return 1;
	}
	else
	{
		if(type==0) return 0;
		if(type==X^Y) return 1;
	}
}
signed main()
{
	std::cin>>N>>X>>Y;
	for(int i=0;i<10;++i)
	{
		std::vector<int>Vec;Vec.clear();
		for(int j=1;j<=N;++j) if(j&(1<<i)) Vec.push_back(j);
		if(Vec.size()&&query(Vec)) Xr|=1<<i;
	}
	std::vector<int>Vec;Vec.clear();
	for(int i=1;i<=N;++i)
		if((i^Xr)<=N&&(i^Xr)>i) Vec.push_back(i);
	int l=0,r=Vec.size()-1;
	while(l<r)
	{
		int mid=(l+r)>>1;
		std::vector<int>V;V.clear();
		for(int i=l;i<=mid;++i) V.push_back(Vec[i]);
		if(query(V)) r=mid;
		else l=mid+1;
	}
	std::cout<<"! "<<std::min(Vec[l]^Xr,Vec[l])<<" "<<std::max(Vec[l]^Xr,Vec[l])<<std::endl;
}
相关文章