Submission #1274197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274197		ezrapo	Mađioničar (COI22_madionicar)	C++20	0 / 100	535 ms	13708 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    map<pair<int, int>, bool> mp;
    auto query=[&](int l, int r) {
        auto it=mp.find({l, r});
        if (it!=mp.end()) return it->second;
        cout << "? " << l << " " << r << endl;
        cout.flush();
        int res;
        if (!(cin >> res)) exit(0);
        return mp[{l, r}]=(res==1);
    };
    auto ans=[&](int answer) {
        cout << "! " << answer << endl;
        cout.flush();
        exit(0);
    };
    vector<int> c1(n+1, 0), c2(n+1, 0);
    {
        int l=1, r=0;
        for (int i=1; i<=n; i++) {
            int k=1;
            if (i<=r) k=min(c1[l+r-i], r-i+1);
            while (i-k>=1 && i+k<=n) {
                if (!query(i-k, i+k)) break;
                k++;
            }
            c1[i]=k;
            if (i+k-1>r) {
                l=i-k+1;
                r=i+k-1;
            }
        }
    }
    {
        int l=1, r=0;
        for (int i=1; i<=n; i++) {
            int k=0;
            if (i<=r) k=min(c2[l+r-i+1], r-i+1);
            while (i-k>=1 && i+k+1<=n) {
                if (!query(i-k, i+k+1)) break;
                k++;
            }
            c2[i]=k;
            if (i+k>r) {
                l=i-k+1;
                r=i+k;
            }
        }
    }
    int best=0;
    for (int i=1; i<=n; i++) {
        best=max(best, c1[i]*2-1);
        best=max(best, c2[i]*2);
    }
    ans(best);
}

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