CF1019B The hat 做题记录

这是一道交互题。

一共有 $n$ 个人做成一圈，他们的编号从 $1$ 到 $n$。

现在每个人的手里面都有一个数字 $a_i$ ，并且保证每个人与他周围两个人的数字差为 $1$ ，即 $\mid a_i-a_{i\pm 1}\mid =1$ ，特别地，编号为 $1$ 与 $n$ 的人也满足这个规则。

在这个圈里面，编号为 $i$ 的人的对面坐着的是编号为 $i+\frac{n}{2}$ 的人（其中 $i\le \frac{n}{2}$），现在要你找到哪个人与他对面坐着的那个人手中的数字一样。

$2\mid n, n\le 10^5$。

首先若 $\frac{n}{2}$ 是奇数那么无解，因为 $i$ 和 $i+\frac{n}{2}$ 之间隔了 $\frac{n}{2}$ 个 $\pm 1$，若 $\frac{n}{2}$ 是奇数那么 $a_i$ 和 $a_{i+\frac{n}{2}}$ 奇偶性一定不同。

考虑 $\frac{n}{2}$ 为偶数的情况，令 $i'=\begin{cases}i+\frac{n}{2}&i\le\frac{n}{2}\\i-\frac{n}{2}&i>\frac{n}{2}\\\end{cases}$，$d_i=a_i-a_{i'}$。显然问题转化成找到一个 $1\le i\le \frac{n}{2}$ 的 $i$，满足 $d_i=0$。那么观察到 $d_i$ 都是偶数，所以 $d_i-d_{i+1}\in[2,-2,0]$。也就是说，若 $d_l,d_r$ 异号，则 $d_{[l,r]}$ 中一定有至少一个 $0$，即 $[l,r]$ 中一定有满足条件的位置。

由于 $d_i=-d_{i+\frac{n}{2}}$，所以若 $d_1\not=0$ 那么 $[1,1+\frac{n}{2}]$ 中一定有至少一个满足条件的位置。那么在这个区间中二分即可，若 $d_{mid}$ 与 $d_1$ 异号，那么往 $[1,mid-1]$ 二分，否则往 $[mid+1,r]$ 二分。

代码如下：

// Problem: CF1019B The hat
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1019B
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

int n;

inline int que(int x)
{
	printf("? %d\n",x);
	fflush(stdout);
	int res;
	scanf("%d",&res);
	return res;
}

int main()
{
	scanf("%d",&n);
	if(n%4!=0)
	{
		puts("! -1");
		fflush(stdout);
		return 0;
	}
	int l=1,r=n/2+1,ans=-1;
	int d1=que(1)-que(1+n/2);
	if(d1==0)
	{
		puts("! 1");
		fflush(stdout);
		return 0;
	}
	while(l<=r)
	{
		int mid=l+r>>1;
		int di=que(mid)-que(mid+n/2);
		if(di==0)
		{
			ans=mid;
			break;
		}
		else if(di<0^d1<0) r=mid-1;
		else l=mid+1;
	}
	printf("! %d\n",ans);
	fflush(stdout);
	return 0;
}