Submission #960836

#	Time	Username	Problem	Language	Result	Execution time	Memory
960836		Pring	Mađioničar (COI22_madionicar)	C++17	100 / 100	1211 ms	20556 KiB

Main

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 200005;
int n;
int N;
map<pii, int> M;

int fquery(int l, int r) {
    cout << "? " << l << ' ' << r << endl;
    int x;
    cin >> x;
    return x;
}

int query(int l, int r) {
    // [l, r]
    auto fquery = [&](int l, int r) -> int {
        if (l == r) return 1;
        cout << "? " << l << ' ' << r << endl;
        int x;
        cin >> x;
        return x;
    };
    if (l <= 0 || r > N) return 0;
    if (l & 1) l++;
    if (r & 1) r--;
    l /= 2;
    r /= 2;
    auto it = M.find(mp(l, r));
    return (it == M.end() ? (M[mp(l, r)] = fquery(l, r)) : it -> sc);
}

namespace MANACHER {
    int m[MXN], l;

    void DO() {
        m[1] = 0;
        m[2] = 1;
        l = 2;
        FOR(i, 3, N + 1) {
            if (i >= l + m[l] + 1) {
                while (true) {
                    if (query(i - m[i] - 1, i + m[i] + 1) == 0) break;
                    m[i]++;
                }
                l = i;
            } else {
                int i_ = 2 * l - i;
                if (i_ - m[i_] == l - m[l]) {
                    m[i] = m[i_];
                    while (true) {
                        if (query(i - m[i] - 1, i + m[i] + 1) == 0) break;
                        m[i]++;
                    }
                    l = i;
                } else if (i_ - m[i_] < l - m[l]) {
                    m[i] = i_ + m[l] - l;
                } else {
                    m[i] = m[i_];
                }
            }
        }
    }
}

void miku() {
    cin >> n;
    N = 2 * n + 1;
    MANACHER::DO();
    // int ans = 0;
    // FOR(1, N + 1) {
    //     if (i & 1) 
    // }
    cout << "! " << *max_element(MANACHER::m + 1, MANACHER::m + N + 1) << endl;
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

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