Submission #8328474


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;
            }
            fin = max(mid - (x[i] - fin) + fin, x[i] + (mid - (x[i] - fin))/2+1);
        }
        else{
            fin = max(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 = 1e18;
    ll ans = 1e18;
    while(l<r){
        ll mid = (l+r)/2;
        if(isOK(mid)){
            ans = min(ans,mid);
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task D - 壊れた電車
User octo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1005 Byte
Status WA
Exec Time 48 ms
Memory 1024 KB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3
Score / Max Score 0 / 0 0 / 20 0 / 60 0 / 20
Status
AC × 2
AC × 15
WA × 2
AC × 30
WA × 6
AC × 48
WA × 12
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
Dataset1 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt
Dataset2 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt
Dataset3 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 1 ms 256 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 1 ms 256 KB
01-07.txt AC 1 ms 256 KB
01-08.txt AC 1 ms 256 KB
01-09.txt WA 1 ms 256 KB
01-10.txt AC 1 ms 256 KB
01-11.txt AC 1 ms 256 KB
01-12.txt AC 1 ms 256 KB
01-13.txt AC 1 ms 256 KB
01-14.txt WA 1 ms 256 KB
01-15.txt AC 1 ms 256 KB
02-01.txt AC 1 ms 256 KB
02-02.txt AC 1 ms 256 KB
02-03.txt AC 1 ms 256 KB
02-04.txt AC 4 ms 256 KB
02-05.txt AC 37 ms 1024 KB
02-06.txt AC 19 ms 640 KB
02-07.txt AC 37 ms 1024 KB
02-08.txt AC 35 ms 1024 KB
02-09.txt AC 35 ms 1024 KB
02-10.txt WA 1 ms 256 KB
02-11.txt WA 37 ms 1024 KB
02-12.txt WA 37 ms 1024 KB
02-13.txt WA 36 ms 1024 KB
02-14.txt AC 35 ms 1024 KB
02-15.txt AC 37 ms 1024 KB
02-16.txt AC 36 ms 1024 KB
02-17.txt AC 38 ms 1024 KB
02-18.txt AC 37 ms 1024 KB
02-19.txt AC 37 ms 1024 KB
03-01.txt WA 1 ms 256 KB
03-02.txt AC 1 ms 256 KB
03-03.txt AC 1 ms 256 KB
03-04.txt AC 45 ms 1024 KB
03-05.txt AC 15 ms 512 KB
03-06.txt AC 23 ms 640 KB
03-07.txt AC 45 ms 1024 KB
03-08.txt AC 41 ms 896 KB
03-09.txt WA 1 ms 256 KB
03-10.txt AC 46 ms 1024 KB
03-11.txt AC 46 ms 1024 KB
03-12.txt AC 14 ms 512 KB
03-13.txt WA 40 ms 1024 KB
03-14.txt AC 45 ms 1024 KB
03-15.txt AC 35 ms 1024 KB
03-16.txt AC 45 ms 1024 KB
03-17.txt AC 40 ms 1024 KB
03-18.txt WA 47 ms 1024 KB
03-19.txt WA 47 ms 1024 KB
03-20.txt WA 47 ms 1024 KB
03-21.txt AC 47 ms 1024 KB
03-22.txt AC 48 ms 1024 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB