Submission #1208463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208463		Fatonim	Mađioničar (COI22_madionicar)	C++20	13 / 100	493 ms	2004 KiB

Main

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

#ifdef ONPC
#include "debug.h"
#else
#define dbg(...)
#endif

#define ll long long
#define int long long
#define ld long double
#define pi pair<int, int>
#define sz(a) ((int)(a.size()))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sqr(n) ((n) * (n))
#define divup(a, b) (((a) + (b)-1) / (b))
#define popcount(n) __builtin_popcountll(n)
#define clz(n) __builtin_clzll(n)
#define Fixed(a) cout << fixed << setprecision(12) << a;

template <class T> bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool chmax(T& a, const T& b) { return b > a ? a = b, 1 : 0; }

const int mod = 998244353; // 998244353 1e9 + 7
const ll inf = (ll)(1e18) + 7;
const ld eps = 1e-9;

const int B = 32;
const int N = 1000 + 3;
const int logn = 20;
const int maxn = 2e5 + 7;
/////////////////////////solve/////////////////////////

int qr = 0;

bool ask(int l, int r) {
    ++qr;
    if (qr > 1900000) {
        return 0;
    }
    cout << "? " << l + 1 << ' ' << r + 1 << endl;
    bool res;
    cin >> res;
    return res;
}

vector<int> manacher_odd(int n) {
    int l = -1, r = -1;
    vector<int> d(n, 0);
    for (int i = 0; i < n; ++i) {
        if (i < r) d[i] = min(d[l + r - i], r - i);
        while (i - d[i] - 1 >= 0 && i + d[i] + 1 < n && ask(i - d[i] - 1, i + d[i] + 1)) ++d[i];
        if (i + d[i] > r) {
            r = i + d[i];
            l = i - d[i];
        }
    }
    return d;
}

vector<int> manacher_even(int n) {
    int l = -1, r = -1;
    vector<int> d(n, 0);
    for (int i = 1; i < n; ++i) {
        if (i < r) d[i] = min(d[l + r - i + 1], r - i + 1);
        while (i - d[i] - 1 >= 0 && i + d[i] < n && ask(i - d[i] - 1, i + d[i])) ++d[i];
        if (i + d[i] - 1 > r) {
            r = i + d[i] - 1;
            l = i - d[i];
        }
    }
    return d;
}

void answer(int ans) {
    cout << "! " << ans << endl;
    exit(0);
}

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



    int ans = 0;
    vector<int> d_odd = manacher_odd(n);
    for (auto x : d_odd) {
        chmax(ans, 2 * x + 1);
    }
    vector<int> d_even = manacher_even(n);
    for (auto x : d_even) {
        chmax(ans, 2 * x);
    }

    answer(ans);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // #ifdef ONPC
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    //     freopen("error.txt", "w", stderr);
    // #endif

    solve();
}

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