Submission #960835

#TimeUsernameProblemLanguageResultExecution timeMemory
960835PringMađioničar (COI22_madionicar)C++17
0 / 100
834 ms11188 KiB
#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) << '\n'; } int32_t main() { cin.tie(0) -> sync_with_stdio(false); cin.exceptions(cin.failbit); miku(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...