Submission #829736

#	Time	Username	Problem	Language	Result	Execution time	Memory
829736		nnin	Cave (IOI13_cave)	C++14	100 / 100	246 ms	524 KiB

cave

#include "cave.h"
#include <iostream>
using namespace std;

int s[6000], d[6000], n;
bool sure[6000], to = 1;

void change(int l, int r) {
    for(int i=l;i<=r;i++) {
        if(!sure[i]) s[i] = 1-s[i];
    }
}

int SwitchForDoor(int door) {
    int cur = tryCombination(s);
    if(cur>door || cur==-1) {
        to = !to;
        change(0, n-1);
    }
    int l = 0, r = n-1;
    while(l<r) {
        int m = (l+r)/2;
        change(l, m);
        cur = tryCombination(s);
        change(l, m);
        if(cur>door || cur==-1) {
            r = m;
        } else {
            l = m+1;
        }
    }
    return l;
}

void exploreCave(int N) {
    n = N;
    for(int i=0;i<n;i++) {
        int sw = SwitchForDoor(i);
        d[sw] = i;
        sure[sw] = true;
        s[sw] = to;
    }
    answer(s, d);
}

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