Submission #170339

#	Time	Username	Problem	Language	Result	Execution time	Memory
170339		ngmh	Cave (IOI13_cave)	C++11	100 / 100	275 ms	632 KiB

cave

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

int s[5005], d[5005], res;
bool c[5005], pr, dw;

void exploreCave(int N) {
    memset(d, -1, sizeof(d));
    res = tryCombination(s);
    for(int i = 0; i < N; i++){
        if(res == -1 or res > i) pr = true;
        else pr = false;
        int maxi = N, mini = -1;
        while(maxi - mini > 1) {
            int medi = (maxi + mini) / 2;
            for (int j = mini + 1; j <= medi; j++) {
                if (c[j]) continue;
                s[j] = !s[j];
            }
            res = tryCombination(s);
            if (res == -1 or res > i) dw = true;
            else dw = false;
            if (dw == pr) mini = medi;
            else maxi = medi;
            pr = dw;
        }
        d[maxi] = i;
        c[maxi] = true;
        if(!dw){
            s[maxi] = !s[maxi];
            res = tryCombination(s);
        }
    }
    answer(s, d);
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24