oj.uz

Submission #963908

# Submission time Handle Problem Language Result Execution time Memory
963908 2024-04-16T02:49:04 Z becaido Mađioničar (COI22_madionicar) C++17
63 / 100
 1032 ms 2408 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 cnt;
int que(int l, int r) {
    if (l & 1) return 1;
    cnt++;
    if (cnt == 200000) {
        cout << "! " << *max_element(z + 1, z + n + 1) << '\n';
        exit(0);
    }
    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 53 ms 1224 KB Output is correct
2 Correct 69 ms 980 KB Output is correct
3 Correct 85 ms 1004 KB Output is correct
4 Correct 54 ms 992 KB Output is correct
5 Correct 92 ms 724 KB Output is correct
6 Correct 77 ms 976 KB Output is correct
7 Correct 72 ms 724 KB Output is correct
8 Correct 73 ms 724 KB Output is correct
9 Correct 99 ms 972 KB Output is correct
10 Correct 70 ms 1108 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 1224 KB Output is correct
2 Correct 69 ms 980 KB Output is correct
3 Correct 85 ms 1004 KB Output is correct
4 Correct 54 ms 992 KB Output is correct
5 Correct 92 ms 724 KB Output is correct
6 Correct 77 ms 976 KB Output is correct
7 Correct 72 ms 724 KB Output is correct
8 Correct 73 ms 724 KB Output is correct
9 Correct 99 ms 972 KB Output is correct
10 Correct 70 ms 1108 KB Output is correct
11 Correct 557 ms 1580 KB Output is correct
12 Correct 671 ms 1640 KB Output is correct
13 Correct 643 ms 2112 KB Output is correct
14 Correct 549 ms 1400 KB Output is correct
15 Correct 675 ms 1932 KB Output is correct
16 Correct 626 ms 1144 KB Output is correct
17 Correct 618 ms 1100 KB Output is correct
18 Correct 574 ms 1644 KB Output is correct
19 Correct 972 ms 1516 KB Output is correct
20 Correct 626 ms 1672 KB Output is correct
21 Correct 557 ms 1876 KB Output is correct
22 Correct 654 ms 1908 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 2044 KB Output is correct
2 Correct 474 ms 1644 KB Output is correct
3 Correct 843 ms 1964 KB Output is correct
4 Correct 1000 ms 1188 KB Output is correct
5 Correct 1010 ms 1456 KB Output is correct
6 Correct 807 ms 2408 KB Output is correct
7 Correct 969 ms 1412 KB Output is correct
8 Correct 786 ms 1964 KB Output is correct
9 Correct 787 ms 2264 KB Output is correct
10 Correct 829 ms 1872 KB Output is correct
11 Correct 999 ms 1368 KB Output is correct
12 Correct 999 ms 1224 KB Output is correct
13 Correct 860 ms 1940 KB Output is correct
14 Correct 852 ms 2028 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 1224 KB Output is correct
2 Correct 69 ms 980 KB Output is correct
3 Correct 85 ms 1004 KB Output is correct
4 Correct 54 ms 992 KB Output is correct
5 Correct 92 ms 724 KB Output is correct
6 Correct 77 ms 976 KB Output is correct
7 Correct 72 ms 724 KB Output is correct
8 Correct 73 ms 724 KB Output is correct
9 Correct 99 ms 972 KB Output is correct
10 Correct 70 ms 1108 KB Output is correct
11 Correct 557 ms 1580 KB Output is correct
12 Correct 671 ms 1640 KB Output is correct
13 Correct 643 ms 2112 KB Output is correct
14 Correct 549 ms 1400 KB Output is correct
15 Correct 675 ms 1932 KB Output is correct
16 Correct 626 ms 1144 KB Output is correct
17 Correct 618 ms 1100 KB Output is correct
18 Correct 574 ms 1644 KB Output is correct
19 Correct 972 ms 1516 KB Output is correct
20 Correct 626 ms 1672 KB Output is correct
21 Correct 557 ms 1876 KB Output is correct
22 Correct 654 ms 1908 KB Output is correct
23 Correct 841 ms 2044 KB Output is correct
24 Correct 474 ms 1644 KB Output is correct
25 Correct 843 ms 1964 KB Output is correct
26 Correct 1000 ms 1188 KB Output is correct
27 Correct 1010 ms 1456 KB Output is correct
28 Correct 807 ms 2408 KB Output is correct
29 Correct 969 ms 1412 KB Output is correct
30 Correct 786 ms 1964 KB Output is correct
31 Correct 787 ms 2264 KB Output is correct
32 Correct 829 ms 1872 KB Output is correct
33 Correct 999 ms 1368 KB Output is correct
34 Correct 999 ms 1224 KB Output is correct
35 Correct 860 ms 1940 KB Output is correct
36 Correct 852 ms 2028 KB Output is correct
37 Correct 847 ms 1944 KB Output is correct
38 Correct 988 ms 1696 KB Output is correct
39 Correct 987 ms 2016 KB Output is correct
40 Correct 822 ms 2088 KB Output is correct
41 Correct 998 ms 1844 KB Output is correct
42 Incorrect 1032 ms 1376 KB L = 61091, expected 72432
43 Halted 0 ms 0 KB -