Codeforces Round #720 (Div. 2)

subject ：

The main idea of the topic ：
There is a length of n Hidden arrangement of p, The length is n, from 1 To n Composed of integers . I want you to pass the most 3*n/2+30 Query times to get this arrangement .

Ideas ：
You can use the following query ：
t=1 : max(min(x,pi),min(x+1,pj));
t=2 : min(max(x,pi),max(x+1,pj));

You can use at most 3*n/2+30 Query search permutation p, So you can use n/2 Maximum value found times n The location of , then n Find the value of each position once .

First, through t=1 : max(min(x,pi),min(x+1,pj)); Find the permutation p The maximum n The location of , Make x == n-1, be ans=max(min(n-1,pi),min(n,pj));
If ans=n, shows pj It must be n, If ans=n-1, shows pi be equal to n-1 Or equal to n, At this time will be pi and pj Change the position , Continue query ,ans=max(min(n-1,pj),min(n,pi)), If ans=n, shows pi be equal to n;

Find the maximum n After the subscript of , adopt t=2 : min(max(x,pi),max(x+1,pj)); Make x=1,pj Is the maximum n The subscript , here ans=min(max(1,pi),max(2,ppos))=min(pi,n)=pi, At this point, we can get the number of each position .

Code ：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N];
int n;
int ask(int t,int i,int j,int x) {
    cout << "? " << t << " " << i << " " <<  j << " " << x << endl;
    // cout.flush();
    int res;
    cin >> res;
    return res;
}
void printResult() {
    cout << "! ";
    for(int i=1;i<=n;i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    // cout.flush();
}
int main() {
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        int pos=n;// Find the maximum subscript 
        for(int i=1;i<n;i+=2) {
            int ans=ask(1,i,i+1,n-1);
            if(ans==n) {
                pos=i+1;
                break;
            }
            else if(ans==n-1) {
                ans=ask(1,i+1,i,n-1);
                if(ans==n) {
                    pos=i;
                    break;
                }
            }
        }
        a[pos]=n;
        for(int i=1;i<=n;i++) {
            if(i==pos) continue;
            a[i]=ask(2,i,pos,1); 
        }
        printResult();
    }
    return 0;

}

For interactivity issues , You can use... After each output cout.flush() Refresh buffer , It can also be used directly cout<< endl, because endl Can automatically refresh the buffer .