Submission #8314854

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    cin.tie(0);
    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう

*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };


// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */

ll n, m;
vector<ll> x;

void input(){
    cin >> n >> m;
    x.resize(m+1);
    rep(i, m) cin >> x[i];
    x[m] = n+1;
}

bool check(ll k){
    if(k == -1) return false;

    ll left = 1;

    for(int i=0; i<m; ++i){
        ll right = x[i];
        if(x[i]-left > k) return false;
        while( 2*min(x[i]-left, right-x[i]) + max(x[i]-left, right-x[i]) <= k && right < x[i+1]) ++right;
        if(i == m-1){
            if(right > n) return true;
            else return false;
        }
        else{
            left = right;
        }
    }
    cerr << " aaaa " << endl;
    return false;
}


void solve(){
    ll ng = -1;
    ll ok = 2e9+5;
    ll mid;
    while(ok - ng > 1){
        mid = (ok + ng) / 2;
        if(check(mid)) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    input();
    solve();
    
    return 0;
}

Submission Info

Judge Result