Submission #512716

Source Code Expand

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    int x[100000];
    int sg[100001];
    int i,j;
    for(i = 0;i < m;i++){
        cin >> x[i];
    }
    sg[0] = x[0]-1;
    for(i = 1;i < m;i++){
        sg[i] = x[i]-x[i-1]-1;
    }
    sg[i] = n-x[i-1];
    int t = 0,b,e,z;
    for(i = 30;i >= 0;i--){
        t |= 1<<i;
        b = 0;
        for(j = 0;j < m;j++){
            if (t >= sg[j] - b) {
                e = t - (sg[j] - b)*2;
                z = (t - (sg[j] - b)) / 2;
                e = (e > z) ? e : z;
                if (e > sg[j + 1]) b = sg[j + 1];
                else b = e;
            } else
                break;
        }
        if(j == m && sg[m] == b)
            t ^= 1<<i;
    }
    if(n != m)cout << t+1 << endl;
    else cout << 0 << endl;
}

Submission Info

Submission Time
Task D - 壊れた電車
User hu5
Language C++ (GCC 4.9.2)
Score 100
Code Size 935 Byte
Status AC
Exec Time 119 ms
Memory 1700 KiB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3
Score / Max Score 0 / 0 20 / 20 60 / 60 20 / 20
Status
AC × 2
AC × 17
AC × 36
AC × 58
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
Case Name Status Exec Time Memory
01-01.txt AC 28 ms 932 KiB
01-02.txt AC 26 ms 932 KiB
01-03.txt AC 26 ms 816 KiB
01-04.txt AC 26 ms 920 KiB
01-05.txt AC 24 ms 928 KiB
01-06.txt AC 26 ms 804 KiB
01-07.txt AC 25 ms 928 KiB
01-08.txt AC 26 ms 804 KiB
01-09.txt AC 26 ms 932 KiB
01-10.txt AC 26 ms 924 KiB
01-11.txt AC 27 ms 808 KiB
01-12.txt AC 27 ms 952 KiB
01-13.txt AC 28 ms 804 KiB
01-14.txt AC 27 ms 804 KiB
01-15.txt AC 26 ms 800 KiB
02-01.txt AC 25 ms 800 KiB
02-02.txt AC 27 ms 804 KiB
02-03.txt AC 27 ms 928 KiB
02-04.txt AC 33 ms 804 KiB
02-05.txt AC 104 ms 1612 KiB
02-06.txt AC 63 ms 1316 KiB
02-07.txt AC 104 ms 1572 KiB
02-08.txt AC 101 ms 1572 KiB
02-09.txt AC 102 ms 1576 KiB
02-10.txt AC 26 ms 808 KiB
02-11.txt AC 104 ms 1608 KiB
02-12.txt AC 104 ms 1576 KiB
02-13.txt AC 101 ms 1576 KiB
02-14.txt AC 102 ms 1568 KiB
02-15.txt AC 99 ms 1576 KiB
02-16.txt AC 100 ms 1612 KiB
02-17.txt AC 105 ms 1608 KiB
02-18.txt AC 104 ms 1580 KiB
02-19.txt AC 105 ms 1572 KiB
03-01.txt AC 27 ms 800 KiB
03-02.txt AC 27 ms 804 KiB
03-03.txt AC 28 ms 808 KiB
03-04.txt AC 115 ms 1568 KiB
03-05.txt AC 56 ms 1056 KiB
03-06.txt AC 70 ms 1192 KiB
03-07.txt AC 116 ms 1576 KiB
03-08.txt AC 104 ms 1508 KiB
03-09.txt AC 27 ms 808 KiB
03-10.txt AC 117 ms 1572 KiB
03-11.txt AC 119 ms 1568 KiB
03-12.txt AC 56 ms 964 KiB
03-13.txt AC 108 ms 1696 KiB
03-14.txt AC 115 ms 1700 KiB
03-15.txt AC 102 ms 1604 KiB
03-16.txt AC 109 ms 1608 KiB
03-17.txt AC 105 ms 1604 KiB
03-18.txt AC 118 ms 1612 KiB
03-19.txt AC 117 ms 1636 KiB
03-20.txt AC 117 ms 1604 KiB
03-21.txt AC 117 ms 1692 KiB
03-22.txt AC 119 ms 1500 KiB
sample-01.txt AC 27 ms 884 KiB
sample-02.txt AC 28 ms 924 KiB