oj.uz

Submission #960836

# Submission time Handle Problem Language Result Execution time Memory
960836 2024-04-11T06:04:11 Z Pring Mađioničar (COI22_madionicar) C++17
100 / 100
 1211 ms 20556 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2072 KB Output is correct
2 Correct 65 ms 2532 KB Output is correct
3 Correct 87 ms 2840 KB Output is correct
4 Correct 57 ms 1560 KB Output is correct
5 Correct 66 ms 2024 KB Output is correct
6 Correct 63 ms 2612 KB Output is correct
7 Correct 82 ms 2468 KB Output is correct
8 Correct 70 ms 1688 KB Output is correct
9 Correct 73 ms 1980 KB Output is correct
10 Correct 68 ms 2308 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2072 KB Output is correct
2 Correct 65 ms 2532 KB Output is correct
3 Correct 87 ms 2840 KB Output is correct
4 Correct 57 ms 1560 KB Output is correct
5 Correct 66 ms 2024 KB Output is correct
6 Correct 63 ms 2612 KB Output is correct
7 Correct 82 ms 2468 KB Output is correct
8 Correct 70 ms 1688 KB Output is correct
9 Correct 73 ms 1980 KB Output is correct
10 Correct 68 ms 2308 KB Output is correct
11 Correct 525 ms 7728 KB Output is correct
12 Correct 726 ms 13804 KB Output is correct
13 Correct 721 ms 14012 KB Output is correct
14 Correct 670 ms 9160 KB Output is correct
15 Correct 716 ms 13140 KB Output is correct
16 Correct 763 ms 10016 KB Output is correct
17 Correct 750 ms 9732 KB Output is correct
18 Correct 548 ms 8520 KB Output is correct
19 Correct 727 ms 9796 KB Output is correct
20 Correct 675 ms 11520 KB Output is correct
21 Correct 593 ms 10980 KB Output is correct
22 Correct 659 ms 12752 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 11272 KB Output is correct
2 Correct 535 ms 8300 KB Output is correct
3 Correct 780 ms 11320 KB Output is correct
4 Correct 1189 ms 14576 KB Output is correct
5 Correct 1173 ms 14260 KB Output is correct
6 Correct 793 ms 10736 KB Output is correct
7 Correct 1158 ms 13960 KB Output is correct
8 Correct 797 ms 11208 KB Output is correct
9 Correct 750 ms 11000 KB Output is correct
10 Correct 786 ms 11484 KB Output is correct
11 Correct 1174 ms 14324 KB Output is correct
12 Correct 1174 ms 14668 KB Output is correct
13 Correct 848 ms 11204 KB Output is correct
14 Correct 801 ms 11368 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2072 KB Output is correct
2 Correct 65 ms 2532 KB Output is correct
3 Correct 87 ms 2840 KB Output is correct
4 Correct 57 ms 1560 KB Output is correct
5 Correct 66 ms 2024 KB Output is correct
6 Correct 63 ms 2612 KB Output is correct
7 Correct 82 ms 2468 KB Output is correct
8 Correct 70 ms 1688 KB Output is correct
9 Correct 73 ms 1980 KB Output is correct
10 Correct 68 ms 2308 KB Output is correct
11 Correct 525 ms 7728 KB Output is correct
12 Correct 726 ms 13804 KB Output is correct
13 Correct 721 ms 14012 KB Output is correct
14 Correct 670 ms 9160 KB Output is correct
15 Correct 716 ms 13140 KB Output is correct
16 Correct 763 ms 10016 KB Output is correct
17 Correct 750 ms 9732 KB Output is correct
18 Correct 548 ms 8520 KB Output is correct
19 Correct 727 ms 9796 KB Output is correct
20 Correct 675 ms 11520 KB Output is correct
21 Correct 593 ms 10980 KB Output is correct
22 Correct 659 ms 12752 KB Output is correct
23 Correct 837 ms 11272 KB Output is correct
24 Correct 535 ms 8300 KB Output is correct
25 Correct 780 ms 11320 KB Output is correct
26 Correct 1189 ms 14576 KB Output is correct
27 Correct 1173 ms 14260 KB Output is correct
28 Correct 793 ms 10736 KB Output is correct
29 Correct 1158 ms 13960 KB Output is correct
30 Correct 797 ms 11208 KB Output is correct
31 Correct 750 ms 11000 KB Output is correct
32 Correct 786 ms 11484 KB Output is correct
33 Correct 1174 ms 14324 KB Output is correct
34 Correct 1174 ms 14668 KB Output is correct
35 Correct 848 ms 11204 KB Output is correct
36 Correct 801 ms 11368 KB Output is correct
37 Correct 826 ms 10908 KB Output is correct
38 Correct 1123 ms 20344 KB Output is correct
39 Correct 1140 ms 20556 KB Output is correct
40 Correct 947 ms 12188 KB Output is correct
41 Correct 1061 ms 19032 KB Output is correct
42 Correct 1132 ms 14384 KB Output is correct
43 Correct 1211 ms 13668 KB Output is correct
44 Correct 910 ms 13872 KB Output is correct
45 Correct 1207 ms 14184 KB Output is correct
46 Correct 1012 ms 17708 KB Output is correct
47 Correct 1076 ms 18240 KB Output is correct
48 Correct 1078 ms 19992 KB Output is correct
49 Correct 1158 ms 14452 KB Output is correct
50 Correct 861 ms 11484 KB Output is correct
51 Correct 1124 ms 20008 KB Output is correct
52 Correct 1182 ms 19576 KB Output is correct