Submission #199990

#	Time	Username	Problem	Language	Result	Execution time	Memory
199990		Osama_Alkhodairy	Gap (APIO16_gap)	C++17	32.81 / 100	85 ms	1284 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long

ll ans;
ll mn, mx;

void solve(ll l, ll r){
    if(ans > r - l + 2) return;
    if(l == r) return;
    ll d = r - l;
    vector <ll> s;
    for(int i = 0 ; i < 10 ; i++){
        s.push_back(l + d / 10 * i);
    }
    s.push_back(r);
    s.resize(unique(s.begin(), s.end()) - s.begin());
    int sz = (int)s.size() - 1;
    vector <ll> mnq, mxq;
    for(int i = 0 ; i < sz ; i++){
        MinMax(s[i], s[i + 1], &mn, &mx);
        if(mn != -1){
            mnq.push_back(mn);
            mxq.push_back(mx);
        }
    }
    if(mnq.size()){
        ans = max(ans, mnq[0] - (l - 1));
        ans = max(ans, r + 1 - mxq.back());
    }
    else ans = max(ans, r + 1 - (l - 1));
    for(int i = 0 ; i + 1 < (int)mnq.size() ; i++){
        ans = max(ans, mnq[i + 1] - mxq[i]);
    }
    for(int i = 0 ; i < (int)mnq.size() ; i++){
        solve(mnq[i] + 1, mxq[i] - 1);
    }
}
ll findGap(int T, int N){
    if(T == 1){
        MinMax(0, 1e18, &mn, &mx);
        ll ans = 0;
        while(mn + 1 < mx){
            ll new_mn, new_mx;
            MinMax(mn + 1, mx - 1, &new_mn, &new_mx);
            ans = max(ans, new_mn - mn);
            ans = max(ans, new_mx - mx);
            mn = new_mn;
            mx = new_mx;
        }
        if(mn != mx) ans = max(ans, mx - mn);
        return ans;
    }
    MinMax(0, 1e18, &mn, &mx);
    solve(mn + 1, mx - 1);
    return ans;
}

• Subtask 1: 0 / 30
• Subtask 2: 32.8087459815 / 70