为了方便,定义0区间初始左端点所在的编号为0,其余位置顺时针依次为$[1,nm)$
考虑对0区间顺时针旋转,记$s_{i}$为0区间左端点旋转到$i$时的答案(约定$s_{i+n}=s_{i}$)
性质1:若$s_{i}-s_{i-1}=1$且$s_{i+1}-s_{i}\ne 1$(其中$0\le i<nm$),则存在一段区间以$i$为左端点
记$a_{i}$为除0以外是否存在区间包含位置$i$(存在为1),不难得到$s_{i}-s_{i-1}=a_{i+m-1}-a_{i-1}$
代入条件,由$s_{i}-s_{i-1}=1$得$a_{i+m-1}=1$且$a_{i-1}=0$,同时$a_{i+m}\ne 1$或$a_{i}\ne 0$
对后者分类讨论,以第一种情况为例,即$a_{i+m-1}=1$且$a_{i+m}\ne 1(=0)$,显然得证
同时,显然$s_{i}$中必然存在这样的$i$,记为$I$并对其余区间分别逆时针旋转一次
性质2:记$s'_{i}$为区间$j$逆时针旋转后的$s_{i}$,则$j$以$I$为左端点当且仅当$s'_{I}-s'_{I-1}\ne 1$
若$j$以$I$为左端点,注意到这会使得$a_{I-1}$变为1,进而即$s'_{I}-s'_{I-1}\ne 1$
另一方面,其需要影响$a_{I-1}$或$a_{I+m-1}$,且前者初始为0、后者初始为1,因此仅能以$I$为左端点
综上,考虑重复以下过程直至得到答案——
1.暴力找到$I$,同时将第0个区间移动到以$I$为左端点的位置
2.枚举所有未确定位置的区间,通过4次移动可以判定其是否以$I$为左端点并还原
另外,可以通过合理的操作顺序,使得其同时判定$s_{i}-s_{i-1}$是否为1(不为1即已经不存在以$I$为左端点的区间)
3.对于左端点在$I$上的区间,再逆时针移动$m+1$次(要求不覆盖到$I-1$)
(实际上,这个过程即不断找到连续段的开头)
进一步的,考虑上述过程所需操作次数,对每一步分别考虑:
1.对于第一步,不难发现第一次找到后至多再转一圈,共计$2nm+2(n-1)$次
2.对于第二步,一共有$n-1$轮,第$i$轮至多有$n-i$个区间,共计$4\sum_{i=1}^{n-1}(n-i)$
3.对于第三步,若第二步中最后一次不还原,每一次实际仅额外产生$m-1$次,共计$(n-1)(m-1)$次
求和后,共计需要$2n^{2}+3nm-n-m-1=25879$次,无法通过
对性质2拓展,每次旋转多个区间,设其构成集合$S$,则$S$中存在以$I$为左端点的区间当且仅当$s'_{I}-s'_{I-1}=1$
以此法不断进行二分,即0区间的移动次数变为$2\log n$,次数降为$2\sum_{i=1}^{n-1}(n-i)+2(n-1)\log n$
同时,由于是不断二分,确定不以$I$为左端点的区间并不需要还原(原来可能会从$I+1$移动到$I$后跳过)
另外,此时第二步还会多出$4(n-1)$次检验,第三步每一次实际额外产生$m+1$次
综上,后两步的次数分别变为$\sum_{i=1}^{n-1}(n-i)+2(n-1)(\log n+2)$和$(n-1)(m+1)$
求和后,共计需要$\frac{n^{2}}{2}+3nm+2n\log n+\frac{11n}{2}-2\log n-m-7=13107$次,可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 105 4 vector<int>v; 5 int n,m,L,now,ans[N]; 6 void move(int k,int p){ 7 printf("? %d %d\n",k,p); 8 fflush(stdout); 9 scanf("%d",&now); 10 } 11 int main(){ 12 scanf("%d%d",&n,&m),L=n*m; 13 for(int i=1;i<n;i++)ans[i]=-1; 14 move(0,1); 15 int lst=now,flag=0; 16 for(int i=0;i<(L<<1);i++){ 17 move(0,1); 18 if (ans[0]==n-1)continue; 19 if (lst+1==now)flag=1; 20 else{ 21 if (flag){ 22 move(0,-1); 23 while (1){ 24 if (ans[0]==n-1)break; 25 move(0,-1),lst=now,move(0,1); 26 if (lst+1!=now)break; 27 lst=now,move(0,1); 28 if (lst+1==now){ 29 move(0,-1); 30 break; 31 } 32 move(0,-1),v.clear(); 33 for(int j=1;j<n;j++) 34 if (ans[j]<0)v.push_back(j); 35 int l=0,r=(int)v.size()-1,flag=0; 36 while (l<r){ 37 int mid=(l+r>>1); 38 if (!flag){ 39 for(int j=l;j<=mid;j++)move(v[j],-1); 40 } 41 else{ 42 for(int j=mid+1;j<=r;j++)move(v[j],1); 43 } 44 move(0,-1),lst=now,move(0,1); 45 if (lst+1==now)l=mid+1,flag=0; 46 else r=mid,flag=1; 47 } 48 for(int j=0;j<=m-flag;j++)move(v[l],-1); 49 ans[0]++,ans[v[l]]=(i+L-m-1)%L; 50 } 51 lst=now,move(0,1); 52 } 53 flag=(lst+1==now); 54 } 55 lst=now; 56 } 57 printf("! "); 58 for(int i=1;i<n;i++)printf("%d ",ans[i]); 59 fflush(stdout); 60 return 0; 61 }View Code