Submission #8269196

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> P;
typedef pair<pair<int, int>, int> PP;
const ll INF = 60 << 1LL;
const ll MOD = 1000000007;

/*-------------------------------------------------------------------------------------------------*/


int main(void) {
    int N, M; cin >> N >> M;
    vector<ll> X(M + 1); X[M] = N;
    for (int i = 0; i < M; i++) cin >> X[i];
    ll left = -1, right = INF;
    while(right-left>1){
        ll mid = (left + right) / 2;
        ll pre = 1;
        bool isOK = true;
        for (int i = 0; i < M; i++) {
            if (pre + mid < X[i]) {
                isOK = false; break;
            }
            ll num = max(mid + 2 * pre - X[i] + 1, (mid + pre + X[i]) / 2 + 1);
            pre = min(num, X[i + 1]);
        }
        if (pre < X[M]) isOK = false;
        if (isOK) right = mid;
        else left = mid;
    }
    cout << right << endl;
}

Submission Info

Judge Result