Submission #1274096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274096		thesen	Mađioničar (COI22_madionicar)	C++20	38 / 100	5053 ms	1960 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vll vector<ll>
#define vbool vector<bool>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;

void solve(){
    ll n; cin >> n;

    vll a(n*2, 1); ll x;
    for(ll i = 2; i < n*2;){
        if((i+(a[i]/2+1)) > n*2)break;
        if(i-(a[i]/2+1) >= 1){
            if((i-(a[i]/2+1))%2 == 0){
                a[i]+=2; continue;
            }
            //cout << i << ' ' << a[i] << endl;
            cout << "? " << (i-(a[i]/2+1))/2+1 << ' ' << (i+(a[i]/2+1))/2+1 << endl;
            fflush(stdout);
            cin >> x;

            if(x){
                a[i]+=2; continue;
            }
        }
        
        ll k = (a[i]/2)+1;
        for(ll j = 1; j <= a[i]/2; j++){
            if(i+(a[i]/2) == i+j + a[i-j]/2){
                k = min(k, j);
            }
            if(i+(a[i]/2) < i+j + a[i-j]/2){
                a[i+j] = (i+(a[i]/2))-(i+j);
                a[i+j]*=2; a[i+j]++;
            }else a[i+j] = a[i-j];
        }i+=k;
    }

    ll res = 0;
    for(ll i = 1; i < 2*n; i++){
        if((i-(a[i]/2))%2 == 0)a[i]-=2;
        res = max(res, a[i]/2+1);
    }cout <<  "! " << res << endl; fflush(stdout);

}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll t=1; //cin >> t;
    for(int i = 1; i <= t; i++){
        solve();
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37