cf 1521 C

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#define bug(x) cout<<#x<<"=="<<x<<endl;
using namespace std;
typedef long long ll;
const int maxn = 6e5+1000;
ll ans[maxn] = { 0 };
inline ll ask(int a,int b,int c,int d)
{
    ll ret;
    cout<<"? "<<a<<' '<<b<<' '<<c<<' '<<d<<'\n';
    cin>>ret;
    cout.flush();
    return ret;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        memset(ans,0,sizeof(ans));
        if(n==1)
        {
            printf("! 1\n");
            continue;
        }
        int pos=n;
        for(int i=1; i+1<=n; i+=2)
        {
            ll ret=ask(1,i,i+1,n-1);
            if(ret==n)
            {
                pos = i+1;
                break;
                ///i+1为最大元素所在的位置
            }
            else if(ret==n-1)///说明p[i]可能等于n
            {
                ret=ask(1,i+1,i,n-1);
                if(ret==n)
                {
                    pos = i;
                    break;
                }
            }
        }
        ans[pos] = n;
        for(int i=1;i<=n;i++)
        {
            if(i==pos)continue;
            ll ret=ask(2,i,pos,1);
            ans[i]=ret;
        }
        cout<<"!";
        for(int i=1;i<=n;i++)
        {
            cout<<' '<<ans[i];
        }
        printf("\n");
    }
}

第一次做这种交互题，看半天才明白题目的输入和输出的关系其实是一一对应的。通过1是找

t=1: max( min( x , pi) , min( x+1,pj ) );

构造的求出来数列的最大值所在的位置，这样子可以通过2直接求出p[i]的值