题解 CF1617D2 Too Many Impostors (hard version)

· · 题解

延续 easy version 的思路，找到两个三元组 (a,b,c),(b,c,d) 满足它们询问出的 01 值不同。

把原序列每三个元素分一块分成 \frac{n}{3} 块，然后对每一块对应的三元组依次询问。由于题目保证 \frac{n}{3}<k<\frac{2n}{3}，因此一定能找到两块满足它们询问得到的值不同，不妨设 (p,p+1,p+2),(q,q+1,q+2) 是找到的询问值不同的两块，且前者询问的结果为 0。

把 (p,p+1,p+2),(q,q+1,q+2) 单拎出来，每次询问两个相邻的三元组，如 (p+1,p+2,q),(p+2,q,q+1)，一定能找到相邻且询问值不同的两个三元组。这有点像离散版的零点存在定理，因为三元组内 1 的数量的变化只可能为 -2,0,2，而最终 1 的数量由负转正，那么一定有一个时刻 1 的数量由 -1 变为了 1。

现在我们可以用 \frac{n}{3}+2 次操作找到两个三元组 (a,b,c),(b,c,d) 满足它们询问出的 01 值不同，即找到两个位置 s,t 满足 a_s=0,a_t=1。接下来，我们对于每一块使用至多 2 次求出块内三个位置的确切值。不妨设当前块 (i,i+1,i+2) 询问值为 0，先询问 (t,i,i+1)，如果返回值为 1 则 i,i+1 中有且仅有一个 1，所以 a_{i+2}=0，再询问一次 (s,t,i) 就能确定 a_i，从而确定 a_{i+1}。而如果 (t,i,i+1) 返回值为 0，那么 a_i=a_{i+1}=0，再询问一次 (s,t,i+2) 就能确定 a_{i+2}。(i,i+1,i+2) 询问值为 1 时同理。综上，总操作数为 n+2。

代码如下：

//author:望远星
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define ull unsigned long long
#define db double
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline int read(){int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-') fh=-1; ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*fh;}
inline void out(int *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}

const int N=1e5+5;
int a[N],n,b[N];

int ask(int x,int y,int z){
    printf("? %d %d %d\n",x,y,z);cout.flush();
    int ret=read();
    if(ret==-1) exit(0);
    return ret;
}

void solve(){
    cin>>n;int p,q;//p:0 q:1
    for(int i=1;i<=n;i+=3){
        b[i]=ask(i,i+1,i+2);
        if(b[i]) q=i;
        else p=i;
    }
    int x=ask(p+1,p+2,q),y,s,t;
    if(x) s=p,t=q;
    else{
        y=ask(p+2,q,q+1);
        if(y) s=p+1,t=q+1;
        else s=p+2,t=q+2;
    }
    //printf("%d,%d\n",s,t);
    a[s]=0,a[t]=1;
    for(int i=1;i<=n;i+=3){
        if(p==i||q==i){
            fo(j,i,i+2) if(j!=s&&j!=t) a[j]=ask(s,t,j);
            continue;
        }
        if(b[i]){
            if(ask(s,i,i+1)){
                a[i]=a[i+1]=1;
                a[i+2]=ask(s,t,i+2);
            }else a[i+2]=1,a[i]=ask(s,t,i),a[i+1]=a[i]^1;
        }else{
            if(!ask(t,i,i+1)){
                a[i]=a[i+1]=0;
                a[i+2]=ask(s,t,i+2);
            }else a[i+2]=0,a[i]=ask(s,t,i),a[i+1]=a[i]^1;
        }
    }
    vector<int> ans;fo(i,1,n) if(!a[i]) ans.pb(i);
    cout<<"! "<<ans.size()<<' ';for(int i:ans) cout<<i<<' ';puts("");
    cout.flush();
}

signed main(){
    int T=read();
    while(T--) solve();
    return 0;
}
/*
-------------------------------------------------
*/