自动搬运

查看原文

来自洛谷，原作者为

	stoorz **

搬运于2025-08-24 22:26:09，当前版本为作者最后更新于2020-11-03 20:10:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有一个很直接的想法是我们枚举每一块金牌 $i$，将前 $i$ 块中剩余的金牌扔到队列里。如果第 $i$ 块金牌和队列里的金牌不一致，那么就将这两块金牌都加入答案序列，否则将 $i$ 压入队列中。

那么最后有若干个多出来的互相排斥的金牌在队列中，我们就枚举答案序列，如果相邻两项均与在队列中的金牌吸引，那么就在它们之间插入一块金牌。

如果最终队列里还有金牌，那么该情况就无解。因为上述操作保证了相邻两个中一定有一块金牌和队列中金牌互相排斥，所以任何情况下这种金牌都无法全部插入答案中。

由于我们最开始将 $0$ 直接加入到答案序列中，所以最多会有 $2(n-1)=2n-2$ 次交互。

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int Q,n,m,ret,ans[N];
queue<int> q;

void prework()
{
	while (q.size()) q.pop();
	m=1; ans[1]=0;
}

int main()
{
	scanf("%d",&Q);
	while (Q--)
	{
		scanf("%d%d",&n,&m);
		prework();
		for (int i=1;i<n;i++)
			if (!q.size())  //将能插入的金牌插入到答案序列，否则扔到队列里
			{
				printf("%d %d\n",i,ans[m]);
				fflush(stdout);
				scanf("%d",&ret);
				if (ret) ans[++m]=i;
					else q.push(i);
			}
			else
			{
				printf("%d %d\n",i,q.front());
				fflush(stdout);
				scanf("%d",&ret);
				if (ret) ans[++m]=i,ans[++m]=q.front(),q.pop();
					else q.push(i);
			}
		for (int i=2*m;i>=1;i-=2)
			ans[i]=ans[i/2],ans[i-1]=-1;  //将两个金牌中隔出一个空位
		if (q.size())
		{
			bool last=1;
			for (int i=2;i<=2*m;i+=2)  //枚举并判断是否有两个金牌间还可以再次插入
			{
				printf("%d %d\n",q.front(),ans[i]);
				fflush(stdout);
				scanf("%d",&ret);
				if (ret && last) ans[i-1]=q.front(),q.pop();
				if (!q.size()) break;
				last=ret;
			}
		}
		if (q.size()) printf("-1\n");
		else
		{
			printf("%d\n",n);
			for (int i=1;i<=2*m;i++)
				if (ans[i]!=-1) printf("%d ",ans[i]);
			printf("\n");
		}
		fflush(stdout);
	}
	return 0;
}