Submission #1277698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277698		dosts	Mađioničar (COI22_madionicar)	C++20	38 / 100	534 ms	12948 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

const int N = 1e5+1;

int n;
map<pii,int> mp;
int ask(int l,int r) {
    if (l == r) return 1;
    if (l < 1 || r > n) return 0;
    if (mp.count({l,r})) return mp[{l,r}];
    cout << "?" sp l sp r << endl;
    int x;
    cin >> x;
    return mp[{l,r}] = x;
}

void solve() {
    cin >> n;
    int mx1 = 1,mx2 = 0;
    for (int i=1;i<=n;i++) {
        if (ask(i-mx1/2,i+mx1/2)) {
            while (mx1 < n && ask(i-mx1/2-1,i+mx1/2+1)) mx1+=2;
        }
        if (ask(i-mx2/2,i+1+mx2/2)) {
            mx2 = max(mx2,2ll);
            while (mx2 < n && ask(i-mx2/2,i+1+mx2/2)) mx2+=2;
        }
        mx1 = max(mx1,mx2-1);
        mx2 = max(mx2,mx1-1);
    }
    cout << "!" sp max(mx1,mx2) << endl;
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

• Subtask 1: 13 / 13
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37