1634D - Finding Zero - CodeForces Solution

#include <bits/stdc++.h> 
using namespace std;
#define ll                long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define nl                "\n"
#define all(x)            (x).begin(),(x).end()
#define sz(x)             (int)((x).size())
#define pii               pair<ll, ll>
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;
 
void run_case(){
    int n;
    cin >> n;
    
    auto query = [&](int i, int j, int k) {
        cout << "? " << i << " " << j << " " << k << endl;
        cout << flush;
        int res;
        cin >> res;
        return res;  
    };       
    
    vector<int> extremes;
    
    vector<int> vals(n + 1);
    
    for(int i = 3; i <= n; ++i) {
        vals[i] = query(1, 2, i);
    }
    
    int ind = max_element(all(vals)) - vals.begin();
    
    // ops-performed => n - 2
    // one extreme lies in {1, 2, ind}
    
    int xtra = ind == 3 ? 4 : 3;
    int fre = count(all(vals), vals[ind]);
    
    if(fre == n - 2) {
        if(query(2, 3, 4) < vals[ind]) {
            cout << "! 1 2" << endl;
            cout.flush();
            return;
        }
    }
    
    fill(all(vals), 0);
    
    for(int i = 2; i <= n; ++i)
        if(i != ind)
            vals[i] = query(1, ind, i);
        
    int mx = max_element(all(vals)) - vals.begin();
    fre = count(all(vals), vals[mx]);
    
    extremes.pb(ind);
    
    if(fre == n - 2)
        extremes.pb(1);
    else
        extremes.pb(mx);
    
    cout << "! " << extremes[0] << " " << extremes[1] << endl;
    cout.flush();
    
    return;
    
}

int main(){

    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    
    int tests;
    cin >> tests;
    while(tests--){
        run_case();
        cout.flush();
    }

}