Nastia and a Hidden Permutation

坑：
又是一种可以搞死面向案例编程的选手的恶心案例，仗着数组是自己隐藏的，自己是知道答案的，于是就假装问几下然后就输出答案。这题别看样例！光这几个问答根本确定不了排列。

思路：
通过 $min(max(p_i,1),max(p_{i+1},2))$ 一定能找出 $1$ 的位置，如果 $p_i==1$ 那么 $min(max(p_i,1),max(p_{i+1},2))==1$ ，如果 $p_{i+1}=1$ ，那么 $min(max(p_i,1),max(p_{i+1},2))==2\ \&\&\ min(max(p_{i+1},1),max(p_{i},2))==1$

找到 $1$ 之后就可以通过 $max(min(p_{pos},4),min(p_i),5)$ 来得到 $a_i$ 的值。

MyCode:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e4+7;
int a[maxn];
int main() {
    int t,n,num;
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        int pos=n;
        for(int i=1;i<n;i+=2) {
            printf("? %d %d %d %d\n",2,i,i+1,1);
            fflush(stdout);
            scanf("%d",&num);
            if(num==1) {
                pos=i; break;
            }
            else if(num==2) {
                printf("? %d %d %d %d\n",2,i+1,i,1);
                fflush(stdout);
                scanf("%d",&num);
                if(num==1) {
                    pos=i+1; break;
                }
            }
        }
        for(int i=1;i<=n;++i) {
            if(i==pos) continue;
            printf("? %d %d %d %d\n",1,pos,i,n-1);
            fflush(stdout);
            scanf("%d",&num);
            a[i]=num;
        }
        a[pos]=1;
        putchar('!');
        for(int i=1;i<=n;++i) printf(" %d",a[i]);
        putchar('\n');
        fflush(stdout);
    }
    return 0;
}