Submission #741576

#	Time	Username	Problem	Language	Result	Execution time	Memory
741576		JakobZorz	Cave (IOI13_cave)	C++14	100 / 100	438 ms	584 KiB

cave

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

int n, depth;
int states[5000];
int conn[5000];
vector<int> active;

bool try_comb() {
    return tryCombination(states) != depth;
}

void find(int l, int r, bool prev) {
    if(l==r-1) {
        if(!prev)
            states[active[l]]^=1;
        conn[active[l]]=depth;
        active.erase(active.begin()+l);
        depth++;
        return;
    }
    
    int mid=(l+r)/2;
    bool s1=prev;
    for(int i=0;i<mid;i++)
        states[active[i]]^=1;
    bool s2=try_comb();
    if(s1==s2)
        find(mid, r, s2);
    else
        find(l, mid, s2);
}

void exploreCave(int N) {
    n=N;
    for(int i=0;i<n;i++)
        active.push_back(i);
    
    while(!active.empty()) {
        find(0, active.size(), try_comb());
    }
    
    answer(states, conn);
}

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