Submission #199992

#	Time	Username	Problem	Language	Result	Execution time	Memory
199992		Osama_Alkhodairy	Gap (APIO16_gap)	C++17	28.43 / 100	82 ms	1196 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 < 5 ; i++){
        s.push_back(l + d / 5 * 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) return 0;
    MinMax(0, 1e18, &mn, &mx);
    solve(mn + 1, mx - 1);
    return ans;
}

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