Submission #1106318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106318		_callmelucian	Mađioničar (COI22_madionicar)	C++14	100 / 100	1612 ms	336 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int n;

bool ask (int l, int r) {
    assert(1 <= l && l <= r && r <= n);
    cout << "? " << l << " " << r << "\n";
    cout.flush();

    bool ans; cin >> ans;
    return ans;
}

void answer (int ans) {
    cout << "! " << ans << "\n";
    cout.flush();
}

bool okOdd (int sz, int mid) {
    return mid - sz / 2 >= 1 && mid + sz / 2 <= n;
}

bool okEven (int sz, int mid) {
    return mid - sz / 2 + 1 >= 1 && mid + sz / 2 <= n;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    int bestOdd = 1, bestEven = 0;

    for (int i = 1; i <= n; i++) {
        while (okOdd(bestOdd + 2, i) && ask(i - bestOdd / 2 - 1, i + bestOdd / 2 + 1)) bestOdd += 2;
        if (i < n) {
            while (okEven(bestEven + 2, i) && ask(i - bestEven / 2, i + bestEven / 2 + 1)) bestEven += 2;
        }
    }
    answer(max(bestOdd, bestEven));

    return 0;
}

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