CF1019B The hat 做题记录

这是一道交互题。

一共有 nn 个人做成一圈,他们的编号从 11nn

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

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

2n,n1052\mid n, n\le 10^5

首先若 n2\frac{n}{2} 是奇数那么无解,因为 iii+n2i+\frac{n}{2} 之间隔了 n2\frac{n}{2}±1\pm 1,若 n2\frac{n}{2} 是奇数那么 aia_iai+n2a_{i+\frac{n}{2}} 奇偶性一定不同。

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

由于 di=di+n2d_i=-d_{i+\frac{n}{2}},所以若 d1=0d_1\not=0 那么 [1,1+n2][1,1+\frac{n}{2}] 中一定有至少一个满足条件的位置。那么在这个区间中二分即可,若 dmidd_{mid}d1d_1 异号,那么往 [1,mid1][1,mid-1] 二分,否则往 [mid+1,r][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;
}