题解 CF1521C 【Nastia and a Hidden Permutation】

· · 题解

CF救命题，没这题就rk 5k了...

不难发现，若我们已经掌握 p_i=1 的 i，则可以用这样一条询问：1 i j n-1 来得到 p_j 的值，其相当于询问 \max(\min(n-1,p_i),\min(n,p_j))，因为 p_i=1,1<p_j\leq n，所以 \max(\min(n-1,p_i),\min(n,p_j))=\max(1,p_j)=p_j。

于是我们用 n-1 次查询得到了所有 j\neq i 的 p_j 的值，那么问题转化为用 \leq \lfloor\frac{n}{2}\rfloor+31 次查询找出 p_i=1 的 i。

考虑这样一条询问的意义：2 j k 1

根据题意，它表示的是 \min(\max(1,p_j),max(2,p_k))，其中 \max(1,p_j) 必定为 p_j，故其可以简化为 \min(p_j,max(2,p_k))。好像还是看不出什么东西，我们来具体讨论一下它的返回值：

分别观察一下：第一种给了我们需要的 p_i=1 的 i；第二种说明 p_k 可能 =1，且只会在 p_j=2 或 p_k\leq2 时得到，故我们只会遇见第二种范围值不超过 2 次，且可以通过查询 2 k j 1 确定 p_k的值；第三种范围过广，没有用。

先假设 n 为偶数（因为按如下方法若没有找到 p_i=1 的 i，则 i=n ），考虑对所有奇数 k 进行如下查询 2 k k+1 1，则我们会共执行 \lfloor\frac{n}{2}\rfloor 次查询，且这些查询包括了排列的每个元素，故至少会有一个查询的返回值 \leq2，然后按上述方式进行处理，即可得到 i 的值。

于是我们通过 \leq \lfloor\frac{3n}{2}\rfloor+2 次查询解决了本题。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ri register int
#define SZ(k) k.size()
#define ALL(k) k.begin(),k.end()
#define DEBUG(k...) fprintf(stderr,k)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
template<class T>inline bool chkmax(T &x,const T &y){return x<y?x=y,true:false;}
template<class T>inline bool chkmin(T &x,const T &y){return x>y?x=y,true:false;}
const int maxn=2e5+10;
int ans[maxn],n,rt,t_case;
inline void ask(int op,int i,int j,int x){
    cout<<"? "<<op<<" "<<i<<" "<<j<<" "<<x<<endl;
}
int main(){
    cin>>t_case;
    while(t_case--){
        cin>>n;
        rt=0;
        for(ri i=1,j;i<n;i+=2){
            ask(2,i,i+1,1);
            cin>>j;
            if(j==1){rt=i;break;}
            if(j==2){
                ask(2,i+1,1,1);
                cin>>j;
                if(j==1){rt=i+1;break;}
            }
        }
        if(!rt)rt=n;
        ans[rt]=1;
        for(ri i=1;i<=n;++i)
            if(i!=rt){
                ask(1,rt,i,n-1);
                cin>>ans[i];
            }
        cout<<"!";
        for(ri i=1;i<=n;++i)cout<<" "<<ans[i];
        cout<<endl;
    }
    return 0;
}