Submission #741575

#	Time	Username	Problem	Language	Result	Execution time	Memory
741575		JakobZorz	Cave (IOI13_cave)	C++14	51 / 100	95 ms	452 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) {
    if(l==r-1) {
        if(!try_comb())
            states[active[l]]^=1;
        conn[active[l]]=depth;
        active.erase(active.begin()+l);
        depth++;
        return;
    }
    
    int mid=(l+r)/2;
    bool s1=try_comb();
    for(int i=0;i<mid;i++)
        states[active[i]]^=1;
    bool s2=try_comb();
    if(s1==s2)
        find(mid, r);
    else
        find(l, mid);
}

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

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