H · Hidden Track (Easy Version)：中文题面与个人代码

时限 2 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面与交互目标 #

这是交互题。每组隐藏一个 $0,\ldots,n-1$ 的排列 $p_1,\ldots,p_n$ ，相邻元素之间连边形成一条隐藏路径。 $n\ge2$ 时保证 $p_1<p_n$ ，用来确定路径方向。你需要还原整个排列。隐藏排列在交互开始前就固定，不会根据询问变化。

令 $k=\lceil\log_2n\rceil$ 。一次询问选择 $0\le m<2^k$ ，以及 $v=-1$ 或 $0\le v<n$ 。先构造

$B(m)=\{x:0\le x<n,\ \operatorname{popcount}(x\mathbin{\&}m)\text{ 为奇数}\}.$

其中 $\&$ 为按位与，popcount 为二进制中一的数量。若 $v=-1$ ，令 $S=B(m)$ ；否则翻转 $v$ 是否属于该集合。交互器统计隐藏路径中恰有一个端点在 $S$ 内的边数 $c(S)$ ，返回 $c(S)\bmod3$ 。

输入、协议与限制 #

开始读入 $1\le T\le10^4$ 。每组先读入 $1\le n\le10^3$ ；所有组 $\sum n\le10^4$ 。

询问输出 ? m v，换行并刷新输出，再读取 $0,1,2$ 中的一个回答。
最终答案输出 ! q1 q2 ... qn，要求与隐藏排列完全相同，同样换行并刷新。答完本组后才能开始下一组。
每组最多 $nk$ 次询问，只有 ? 操作计数。
任何时候读到 $-1$ 必须立即结束程序；继续交互可能得到任意判定。

在 C++ 中可用 endl，或换行后调用 cout.flush() / fflush(stdout)。没有及时刷新可能导致空闲超时。 $n=1$ 时 $k=0$ ，不能询问，直接回答唯一排列 $0$ 。

样例交互记录 #

输入 1 #

输出 1 #

样例说明 #

这是一段交互记录，输入栏的回答依次对应输出栏询问，并非可以直接重定向运行的普通测试。第一组隐藏路径为 $1,0,2$ ，四次都用 $m=1$ ，初始 $B(1)=\{1\}$ 。分别不翻转、翻转顶点 $0,1,2$ ，所得回答为 $1,1,0,2$ 。随后回答 ! 1 0 2。此时 $k=2$ ，预算为六次，实际四次。第二组 $n=1$ ，直接输出 ! 0。

个人代码：交互重建草稿 #

用 $m=0$ 时，初始集合为空，翻转一个顶点 $v$ 后返回其度数模三；对至少两个点的路径，返回一表示端点，二表示内部点。用 $m=2^i$ 则可以观察相邻点的第 $i$ 位对割边计数的影响。代码中逐点询问、逐位比较与 lst 扣除前驱的结构，体现了寻找端点再沿路径恢复邻居的尝试。

设翻转前集合由单个位决定，顶点 $v$ 度数为 $d$ 、其中有 $t$ 个邻居与它位值不同，翻转后割边数的变化为 $d-2t$ 。这解释了为什么需要可靠的基准回答和已知邻居信息。但原稿尚未把这条关系变成完整可执行算法。

ans[i] 看起来用于存放不翻转顶点时的基准回答，但原稿没有相应询问或赋值；lst 记录上一个顶点，R 试图保存一侧路径，p 标记已经收集的顶点。其余 s,r,l,L 在使用处缺少有效声明，末尾 if(p[i]) 没有语句体，实际 C++17 编译失败。

即使补齐声明仍不能直接提交：询问输出缺少 ? 前缀；没有收到 $-1$ 后立即退出的逻辑；没有完整最终排列输出；if(!s) break 把零当结束标记，但顶点零本身是合法顶点；询问预算也没有完整核算。代码把 k 减一后用 0..k 枚举位，这是循环上界写法，不能把它当作题面定义的 $k$ 去计算预算。

本地结果： 编译器报告未声明标识符和末尾语法错误，未进入交互测试。没有宣称它达到 $O(n\log n)$ 查询数或完成全排列重建。后续需先补全协议与算法，再用独立交互器检查返回值、方向、刷新和询问预算。

原始 C++ 文件 #

下载 H.cpp · 验证说明

下面展示原稿，保留未完成部分和已发现问题；下载文件保留原始字节。SHA-256：af22935aa3c15507b5dd091b78f5b8391d347824ed6cd3c821132b171a99d28f。

#include<bits/stdc++.h>
#define int long long
#define pa pair<int,int>
#define bs basic_string
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
using namespace std;
int read(){
	int x;scanf("%lld",&x);
	return x;
}
int t,n,k;
int ans[15];
int get(int x){
	return __builtin_popcount(x)&1;
}
bool ok[15];
bool p[1005];
mt19937 rd(time(0));
void solve(){
	n=read();
	for(int i=0;i<n;i++)p[i]=0;
	memset(ok,0,sizeof(ok));
	for(int i=0;i<=10;i++)if((1<<i)>=n){
		k=i;
		break;
	}
	k--;
	if(n==1){
		cout<<"! 0"<<endl;
		return;
	}
	if(n==2){
		cout<<"! 0 1"<<endl;
		return;
	}
	for(int i=0;i<n;i++){
		cout<<0<<" "<<i<<endl;
		int x=read();
		if(x==1){
			s=i;
			break;
		}
	}
	bs<int>R;
	R+=r;
	int lst=0;
	while(1){
		int s=0;
		for(int i=0;i<=k;i++){
			cout<<(1<<i)<<' '<<r<<endl;
			int a1=read();
			int a=ans[i];
			if((r>>i)&1)swap(a,a1);
			int d=((a1-a)%3+3)%3;
			d-=((lst>>i)&1); 
			if(d)s|=(1<<i);
		}
		if(!s)break;
		R+=s;
		lst=r;
		r=s;
	}
	int ti=n-3-R.size();
	L+=l;
	swap(l,r);
	lst=0;
	while(ti--){
		int s=0;
		for(int i=0;i<=k;i++){
			cout<<(1<<i)<<' '<<r<<endl;
			int a1=read();
			int a=ans[i];
			if((r>>i)&1)swap(a,a1);
			int d=((a1-a)%3+3)%3;
			d-=((lst>>i)&1); 
			if(d)s|=(1<<i);
		}
		if(!s)break;
		L+=s;
		lst=r;
		r=s;
	}
	for(auto x:L)p[x]=1;
	for(auto x:R)p[x]=1;
	for(int i=1;i<n;i++)if(p[i])
}
signed main(){
	t=read();while(t--)solve();
}