Submission #1655303


Source Code Expand

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

int N;
std::vector< std::pair<int,int> > A;

bool isTravelable(int k){
    std::vector<bool> visit(N, false);
    for(int i=0; i<k; ++i){
        int x = -1;
        for(int j=0; j<N; ++j){
            if(!visit[j]){
                x = j;
                break;
            }
        }
        if(x == -1){
            return true;
        }

        std::pair<int,int> p = A[x];
        visit[x] = true;
        for(int j=x+1; j<N; ++j){
            if(p.second + 1 == A[j].second || (p.second == N - 1 && A[j].second == 0)){
                p = A[j];
                visit[j] = true;
            }
        } 
    }
    int x = -1;
    for(int j=0; j<N; ++j){
        if(!visit[j]){
            x = j;
            break;
        }
    }
    if(x == -1){
        return true;
    }
    return false;
}

int main(void){
    std::cin >> N;
    A.resize(N);
    for(int i=0; i<N; ++i){
        int a;
        std::cin >> a;
        A[i] = std::make_pair(a, i);
    }
    std::sort(A.begin(), A.end());

    int left = 0;
    int right = N;
    while(right-left > 1){
        int mid = (left+right)/2;
        bool f = isTravelable(mid);
        if(f){
            right = mid;
        } else {
            left = mid;
        }
    }
    if(isTravelable(left)){
        std::cout << left << std::endl;
    }else{
        std::cout << right << std::endl;
    }
}

Submission Info

Submission Time
Task B - ディスコ社内ツアー
User b1464296
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1508 Byte
Status WA
Exec Time 2103 ms
Memory 1024 KB

Judge Result

Set Name Sample Small Permutation All
Score / Max Score 0 / 0 0 / 20 0 / 10 0 / 70
Status
AC × 4
AC × 12
WA × 14
AC × 9
WA × 7
TLE × 7
AC × 15
WA × 18
TLE × 15
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt
Small 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 20_perm_01.txt, 20_perm_02.txt, 20_perm_03.txt, 20_perm_04.txt, 20_perm_05.txt, 20_perm_06.txt, 20_perm_07.txt, 20_perm_08.txt, 30_hand_01.txt, 30_hand_02.txt, 30_hand_03.txt, 30_hand_04.txt, 30_hand_05.txt, 30_hand_06.txt
Permutation 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 20_perm_01.txt, 20_perm_02.txt, 20_perm_03.txt, 20_perm_04.txt, 20_perm_05.txt, 20_perm_06.txt, 20_perm_07.txt, 20_perm_08.txt, 30_hand_01.txt, 30_hand_02.txt, 60_perm_01.txt, 60_perm_02.txt, 60_perm_03.txt, 60_perm_04.txt, 60_perm_05.txt, 60_perm_06.txt, 60_perm_07.txt, 60_perm_08.txt, 70_hand_01.txt, 70_hand_02.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 20_perm_01.txt, 20_perm_02.txt, 20_perm_03.txt, 20_perm_04.txt, 20_perm_05.txt, 20_perm_06.txt, 20_perm_07.txt, 20_perm_08.txt, 30_hand_01.txt, 30_hand_02.txt, 30_hand_03.txt, 30_hand_04.txt, 30_hand_05.txt, 30_hand_06.txt, 50_rand_01.txt, 50_rand_02.txt, 50_rand_03.txt, 50_rand_04.txt, 50_rand_05.txt, 50_rand_06.txt, 50_rand_07.txt, 50_rand_08.txt, 60_perm_01.txt, 60_perm_02.txt, 60_perm_03.txt, 60_perm_04.txt, 60_perm_05.txt, 60_perm_06.txt, 60_perm_07.txt, 60_perm_08.txt, 70_hand_01.txt, 70_hand_02.txt, 70_hand_03.txt, 70_hand_04.txt, 70_hand_05.txt, 70_hand_06.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 5 ms 764 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 1 ms 256 KB
00_example_04.txt AC 1 ms 256 KB
10_rand_01.txt WA 1 ms 256 KB
10_rand_02.txt WA 1 ms 256 KB
10_rand_03.txt WA 1 ms 256 KB
10_rand_04.txt WA 1 ms 256 KB
10_rand_05.txt AC 1 ms 256 KB
10_rand_06.txt WA 1 ms 256 KB
10_rand_07.txt WA 1 ms 256 KB
10_rand_08.txt WA 1 ms 256 KB
20_perm_01.txt WA 1 ms 256 KB
20_perm_02.txt AC 1 ms 256 KB
20_perm_03.txt WA 1 ms 256 KB
20_perm_04.txt WA 1 ms 256 KB
20_perm_05.txt AC 1 ms 256 KB
20_perm_06.txt WA 1 ms 256 KB
20_perm_07.txt AC 1 ms 256 KB
20_perm_08.txt WA 1 ms 256 KB
30_hand_01.txt AC 1 ms 256 KB
30_hand_02.txt AC 1 ms 256 KB
30_hand_03.txt AC 1 ms 256 KB
30_hand_04.txt AC 1 ms 256 KB
30_hand_05.txt WA 1 ms 256 KB
30_hand_06.txt WA 1 ms 256 KB
50_rand_01.txt TLE 2103 ms 512 KB
50_rand_02.txt TLE 2103 ms 768 KB
50_rand_03.txt TLE 2103 ms 768 KB
50_rand_04.txt TLE 2103 ms 640 KB
50_rand_05.txt TLE 2103 ms 384 KB
50_rand_06.txt WA 2 ms 256 KB
50_rand_07.txt WA 879 ms 384 KB
50_rand_08.txt TLE 2103 ms 640 KB
60_perm_01.txt TLE 2103 ms 512 KB
60_perm_02.txt TLE 2103 ms 768 KB
60_perm_03.txt TLE 2103 ms 768 KB
60_perm_04.txt TLE 2103 ms 640 KB
60_perm_05.txt TLE 2103 ms 384 KB
60_perm_06.txt WA 2 ms 256 KB
60_perm_07.txt WA 905 ms 384 KB
60_perm_08.txt TLE 2103 ms 640 KB
70_hand_01.txt AC 44 ms 1024 KB
70_hand_02.txt TLE 2103 ms 1024 KB
70_hand_03.txt AC 36 ms 1024 KB
70_hand_04.txt AC 34 ms 1024 KB
70_hand_05.txt TLE 2103 ms 1024 KB
70_hand_06.txt TLE 2103 ms 1024 KB