Submission #718129

#	Time	Username	Problem	Language	Result	Execution time	Memory
718129		irmuun	Gap (APIO16_gap)	C++17	100 / 100	81 ms	2240 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"

using namespace std;

#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()

const ll INF=1e18;

ll findGap(int T,int N){
    if(T==1){
        vector<ll>v;
        ll l=0;
        ll r=INF;
        for(int i=1;i<=(N+1)/2;i++){
            ll a,b;
            MinMax(l,r,&a,&b);
            v.pb(a);
            if(a!=b){
                v.pb(b);
            }
            l=a+1;
            r=b-1;
        }
        sort(all(v));
        ll ans=v[1]-v[0];
        for(int i=2;i<N;i++){
            ans=max(ans,v[i]-v[i-1]);
        }
        return ans;
    }
    else{
        ll l,r;
        ll ans=0;
        MinMax(0,INF,&l,&r);
        ll dif=(r-l+N-2)/(N-1);
        ll bef=l;
        for(ll i=l;i<=r;i+=dif+1){
            ll x,y;
            MinMax(i,i+dif,&x,&y);
            if(x==-1){
                continue;
            }
            ans=max(ans,y-x);
            ans=max(ans,x-bef);
            bef=y;
        }
        return ans;
    }
}

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