oj.uz

Submission #1027039

# Submission time Handle Problem Language Result Execution time Memory
1027039 2024-07-18T19:06:42 Z VMaksimoski008 Mađioničar (COI22_madionicar) C++17
13 / 100
 1267 ms 12880 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

map<pii, int> mp;

int query(int l, int r) {
    if(mp.count({ l, r })) return mp[{ l, r }];
    cout << "? " << l << " " << r << endl;
    int x;
    cin >> x;
    return mp[{ l, r }] = x;
}

signed main() {
    int n;
    cin >> n;

    int l=2, r=(n-1)/2, ans=1;
    while(l <= r) {
        int mid = (l + r) / 2, ok = 0;
        int len = 2 * mid + 1;
        for(int i=1; i+len-1<=n; i++) {
            if(query(i, i+len-1)) {
                ok = 1;
                break;
            }
        }

        if(ok) ans = len, l = mid + 1;
        else r = mid - 1;
    }

    l=1, r=n/2;
    int ans2=0;
    while(l <= r) {
        int mid = (l + r) / 2, ok = 0;
        int len = 2 * mid;
        for(int i=1; i+len-1<=n; i++) {
            if(query(i, i+len-1)) {
                ok = 1;
                break;
            }
        }

        if(ok) ans2 = len, l = mid + 1;
        else r = mid - 1;
    }

    cout << "! " << max(ans, ans2) << endl;
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 8688 KB Output is correct
2 Correct 861 ms 9256 KB Output is correct
3 Correct 913 ms 9932 KB Output is correct
4 Correct 606 ms 7092 KB Output is correct
5 Correct 976 ms 10516 KB Output is correct
6 Correct 684 ms 7860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 440 ms 5080 KB Output is correct
9 Correct 398 ms 4788 KB Output is correct
10 Correct 995 ms 10160 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 8688 KB Output is correct
2 Correct 861 ms 9256 KB Output is correct
3 Correct 913 ms 9932 KB Output is correct
4 Correct 606 ms 7092 KB Output is correct
5 Correct 976 ms 10516 KB Output is correct
6 Correct 684 ms 7860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 440 ms 5080 KB Output is correct
9 Correct 398 ms 4788 KB Output is correct
10 Correct 995 ms 10160 KB Output is correct
11 Runtime error 1267 ms 12716 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1252 ms 12880 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 8688 KB Output is correct
2 Correct 861 ms 9256 KB Output is correct
3 Correct 913 ms 9932 KB Output is correct
4 Correct 606 ms 7092 KB Output is correct
5 Correct 976 ms 10516 KB Output is correct
6 Correct 684 ms 7860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 440 ms 5080 KB Output is correct
9 Correct 398 ms 4788 KB Output is correct
10 Correct 995 ms 10160 KB Output is correct
11 Runtime error 1267 ms 12716 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -