Submission #1147393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147393		guagua0407	Gap (APIO16_gap)	C++20	100 / 100	41 ms	3260 KiB

gap

#include "gap.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

long long findGap(int T, int n)
{
    ll L,R;
    MinMax(1ll,(ll)1e18,&L,&R);
    if(T==1){
        ll ans=0;
        if(n==2){
            ans=R-L;
            return ans;
        }
        for(int i=0;i<(n+1)/2-1;i++){
            ll L1,R1;
            MinMax(L+1,R-1,&L1,&R1);
            ans=max({ans,L1-L,R-R1});
            L=L1;
            R=R1;
        }
        if(n%2==0){
            ans=max(ans,R-L);
        }
        return ans;
    }
    ll gap=(R-L-1+(n-1)-1)/(n-1);
    vector<pair<ll,ll>> vec;
    vec.push_back({L,L});
    for(ll l=L+1;l<R;l+=gap){
        ll r=min(R-1,l+gap-1);
        ll mn,mx;
        MinMax(l,r,&mn,&mx);
        if(mn!=-1)vec.push_back({mn,mx});
    }
    vec.push_back({R,R});
    ll ans=0;
    int sz=(int)vec.size();
    for(int i=0;i<sz-1;i++){
        ans=max(ans,vec[i+1].f-vec[i].s);
    }
    return ans;
}

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