1698D - Fixed Point Guessing - CodeForces Solution

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(0),cin.tie(0)
#define ll long long
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define pb push_back
#define sorta(vec) sort(vec.begin(),vec.end())
#define sortd(vec) sort(vec.begin(),vec.end(),greater<int>())
#define pb push_back
#define vll vector<long long int>
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>pbds; // find_by_order, order_of_key(0-indexed)
//less , less_equal , greater , greater_equal -> rule for insertion
#define start_execution auto start = std::chrono::high_resolution_clock::now();
#define stop_execution auto stop = std::chrono::high_resolution_clock::now();
#define execution_time auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start); cerr<<"Time taken : "<<((long double)duration.count())/((long double)1e9) <<"s"<<endl; 
#define nline "\n"
#define all(v) (v).begin(),(v).end()
#define pi 3.14159265359 
 
void debug(int x)
{
    cout<<"Value Debugged is "<<x<<endl;
}
void debug(vector<int>x)
{
    cout<<"Value Debugged is "<<endl;
    for(auto y:x)
    {
        cout<<y<<" ";
    }
    cout<<endl;
}
void debug(vector<vector<int>>x)
{
    cout<<"Value Debugged is "<<endl;
    for(auto y:x)
    {
        for(auto z:y)
        {
            cout<<z<<" ";
        }
        cout<<endl;
    }
}
ll int mod=1e9+7;
ll int inv(ll int r)
{
	if(r==1) return 1;
	return (mod-((mod/r)*inv(mod%r))%mod+mod)%mod;
}
int ceil_div(ll int a,ll int b)
{
    int k=a%b;
    if(k>0) return (a/b)+1;
    return a/b;
}
void print_with_precision(const double val,int n)
{
    cout << fixed << setprecision(n) <<val<<endl;
}
template<class ForwardIterator>
void read(ForwardIterator first,ForwardIterator last) 
{
    while (first != last) 
    {
        cin >> (*first);
        ++first;
    }
}
ll gcd(ll a, ll b)
{
    if (!a)
        return b;
    return gcd(b % a, a);
}
template<class T>
void read(vector<T> &v) 
{
    read(v.begin(), v.end());
}
ll int pwr(ll int a,ll int b)
{
    if(b==0)
        return 1;
    if(b%2==0){ll int ans1=pwr(a,b/2);ll int ans2=(ans1*ans1)%mod;return ans2;}
    ll int ans1=pwr(a,b/2);ll int ans2=(ans1*ans1)%mod;
    ans2=(ans2*a)%mod;
    return ans2;
}
ll int fact(ll int n)
{
    if(n<0)
    {
        return 0;
    }
    ll int ans=1;
    if(n==0) return 1;
    for(int i=1;i<=n;i++)
    {
        ans=(ans*i)%mod;
    }
    return ans;
}
ll int Combination(ll int n,ll int r)
{
    if(n<r)
    {
        return 0;
    }
    ll int ans1=fact(n);ll int ans2=fact(r);
    ll int ans3=fact(n-r);ll int ans=(ans1*inv(ans2))%mod;
    ans=(ans*inv(ans3))%mod;return ans;
}
#define pii pair<ll int,ll int>
//Code starts here
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    fast;
    //start_execution
    int tt=1;
    cin>>tt;
    for(int cse=0;cse<tt;cse++)
    {
        ll int n;
        cin>>n;
        int l=1;
        int r=n;
        while(l<r)
        {
            int mid=(l+r)/2;
            cout<<"? "<<l<<" "<<mid<<endl;
            cout.flush();
            set<int>vec;
            int num=mid-l+1;
            while(num--)
            {
                int x;
                cin>>x;
                vec.insert(x);
            }
            int cnt=0;
            //int pos=l;
            for(int i=l;i<=mid;i++)
            {
                if(vec.find(i)!=vec.end())
                {
                    cnt++;
                }
            }
            if(cnt%2==0)
            {
                //Fixed element in other half
                l=mid+1;
            }
            else
            {
                //Fixed element in this half
                r=mid;
            }

            if(l==r)
            {
                break;
            }

        }

        cout<<"! "<<l<<endl;
    }
    //stop_execution
    //execution_time
    return 0;
}