제출 #1274114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274114		oswaldzz	Mađioničar (COI22_madionicar)	C++20	13 / 100	480 ms	1984 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nl endl
#define hehe ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)  ;

// const int mod = 998244353;
const int mod = 1e9+7;
const int M = 2e5+5;

int gas(int a, int b){
    cout << "? " << a << ' ' << b << nl;
    cout.flush();
    int x; 
    if(!(cin >> x)) exit(0);
    return x;
}

void solve(){
    int n; cin >> n;
    if(n == 1){
        cout << "! " << 1 << nl;
        return;
    }

    int ans = 1;

    vector<int> d1(n+1,0);
    int l = 1, r = 0;
    for(int i = 1; i <= n; i++){
        int k = 1;
        if(i <= r) k = min(d1[l + r - i], (r - i + 1));
        while(i - k >= 1 && i + k <= n && gas(i - k, i + k) == 1) k++;
        d1[i] = k;
        if(i + k - 1 > r){
            l = i - k + 1;
            r = i + k - 1;
        }
        ans = max(ans, (2 * d1[i] - 1));
    }

    vector<int> d2(n+1,0); 
    l = 1; r = 0;
    for(int i = 1; i <= n; i++){
        int k = 0;
        if(i <= r) k = min(d2[l + r - i + 1], (r - i + 1));
        while(i - k - 1 >= 1 && i + k <= n && gas(i - k - 1, i + k) == 1) k++;
        d2[i] = k;
        if(i + k - 1 > r){
            l = i - k;
            r = i + k - 1;
        }
        ans = max(ans, (2 * d2[i]));
    }

    cout << "! " << ans << nl;
}

signed main(){
    hehe
    // int t; cin >> t;
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}

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