Submission #8328198

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int n,m;
ll x[100100];


bool isOK(ll mid){
    ll fin = 1;
    // cout << mid << endl;
    rep(i,m){
        // cout << fin<<endl;
        if (x[i] > fin)
        {
            if(x[i]-fin>mid){

                return false;
            }
            if((x[i]-fin)*2>mid){
                fin = x[i]+1;
            }
            else{
                fin = mid - (x[i] - fin)  +fin;
            }
        }
        else{
            if(fin-x[i]>mid){
                continue;
            }
            else{
                fin = x[i]+mid+1;
            }
        }
    }
    if(fin>=n){
        return true;
    }
    return false;
}

int main(){
    cin >> n>>m;
    rep(i,m){
        cin >> x[i];
    }
    ll l = 0;
    ll r = 1e10;
    ll ans = 1e10;
    while(l<r){
        ll mid = (l+r)/2;
        if(isOK(mid)){
            ans = min(ans,mid);
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    cout << ans-1 << endl;
    return 0;
}

Submission Info

Judge Result