oj.uz

Submission #963905

# Submission time Handle Problem Language Result Execution time Memory
963905 2024-04-16T02:43:27 Z becaido Mađioničar (COI22_madionicar) C++17
63 / 100
 1040 ms 2468 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;

int n;
int z[SIZE];

int que(int l, int r) {
    if (l & 1) return 1;
    int foo = 114514;
    l /= 2, r /= 2;
    cout << "? " << l << ' ' << r << endl;
    cin >> foo;
    return foo;
}

void solve() {
    cin >> n;
    n = 2 * n + 1;
    for (int i = 1, mid = 0, r = 0; i <= n; i++) {
        if (i <= r) {
            z[i] = min(z[2 * mid - i], r - i);
            if (i + z[i] < r) continue;
        }
        int len = min(i - 1, n - i);
        for (int j = z[i] + 1; j <= len; j++) {
            if (que(i - j, i + j) == 0) break;
            z[i]++;
        }
        if (i + z[i] > r) {
            mid = i;
            r = i + z[i];
        }
    }
    cout << "! " << *max_element(z + 1, z + n + 1) << '\n';
}

int main() {
    Waimai;
    solve();
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1212 KB Output is correct
2 Correct 71 ms 988 KB Output is correct
3 Correct 69 ms 988 KB Output is correct
4 Correct 57 ms 1236 KB Output is correct
5 Correct 81 ms 972 KB Output is correct
6 Correct 63 ms 1504 KB Output is correct
7 Correct 67 ms 716 KB Output is correct
8 Correct 79 ms 964 KB Output is correct
9 Correct 102 ms 1224 KB Output is correct
10 Correct 69 ms 988 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1212 KB Output is correct
2 Correct 71 ms 988 KB Output is correct
3 Correct 69 ms 988 KB Output is correct
4 Correct 57 ms 1236 KB Output is correct
5 Correct 81 ms 972 KB Output is correct
6 Correct 63 ms 1504 KB Output is correct
7 Correct 67 ms 716 KB Output is correct
8 Correct 79 ms 964 KB Output is correct
9 Correct 102 ms 1224 KB Output is correct
10 Correct 69 ms 988 KB Output is correct
11 Correct 539 ms 1864 KB Output is correct
12 Correct 659 ms 1696 KB Output is correct
13 Correct 648 ms 1680 KB Output is correct
14 Correct 562 ms 1336 KB Output is correct
15 Correct 668 ms 1472 KB Output is correct
16 Correct 629 ms 1412 KB Output is correct
17 Correct 682 ms 1388 KB Output is correct
18 Correct 574 ms 1632 KB Output is correct
19 Correct 1004 ms 1732 KB Output is correct
20 Correct 625 ms 1832 KB Output is correct
21 Correct 569 ms 1456 KB Output is correct
22 Correct 642 ms 1700 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 2056 KB Output is correct
2 Correct 452 ms 1336 KB Output is correct
3 Correct 830 ms 1940 KB Output is correct
4 Correct 966 ms 1640 KB Output is correct
5 Correct 983 ms 1616 KB Output is correct
6 Correct 761 ms 2168 KB Output is correct
7 Correct 991 ms 1696 KB Output is correct
8 Correct 842 ms 2168 KB Output is correct
9 Correct 771 ms 2044 KB Output is correct
10 Correct 833 ms 1944 KB Output is correct
11 Correct 989 ms 1328 KB Output is correct
12 Correct 952 ms 1420 KB Output is correct
13 Correct 828 ms 2072 KB Output is correct
14 Correct 890 ms 1748 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1212 KB Output is correct
2 Correct 71 ms 988 KB Output is correct
3 Correct 69 ms 988 KB Output is correct
4 Correct 57 ms 1236 KB Output is correct
5 Correct 81 ms 972 KB Output is correct
6 Correct 63 ms 1504 KB Output is correct
7 Correct 67 ms 716 KB Output is correct
8 Correct 79 ms 964 KB Output is correct
9 Correct 102 ms 1224 KB Output is correct
10 Correct 69 ms 988 KB Output is correct
11 Correct 539 ms 1864 KB Output is correct
12 Correct 659 ms 1696 KB Output is correct
13 Correct 648 ms 1680 KB Output is correct
14 Correct 562 ms 1336 KB Output is correct
15 Correct 668 ms 1472 KB Output is correct
16 Correct 629 ms 1412 KB Output is correct
17 Correct 682 ms 1388 KB Output is correct
18 Correct 574 ms 1632 KB Output is correct
19 Correct 1004 ms 1732 KB Output is correct
20 Correct 625 ms 1832 KB Output is correct
21 Correct 569 ms 1456 KB Output is correct
22 Correct 642 ms 1700 KB Output is correct
23 Correct 836 ms 2056 KB Output is correct
24 Correct 452 ms 1336 KB Output is correct
25 Correct 830 ms 1940 KB Output is correct
26 Correct 966 ms 1640 KB Output is correct
27 Correct 983 ms 1616 KB Output is correct
28 Correct 761 ms 2168 KB Output is correct
29 Correct 991 ms 1696 KB Output is correct
30 Correct 842 ms 2168 KB Output is correct
31 Correct 771 ms 2044 KB Output is correct
32 Correct 833 ms 1944 KB Output is correct
33 Correct 989 ms 1328 KB Output is correct
34 Correct 952 ms 1420 KB Output is correct
35 Correct 828 ms 2072 KB Output is correct
36 Correct 890 ms 1748 KB Output is correct
37 Correct 835 ms 2468 KB Output is correct
38 Runtime error 1040 ms 2032 KB Execution killed with signal 13
39 Halted 0 ms 0 KB -