Submission #821333

#	Time	Username	Problem	Language	Result	Execution time	Memory
821333		annabeth9680	Cave (IOI13_cave)	C++17	100 / 100	200 ms	528 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int MAXN = 5010;
bool vis[MAXN]; int S[MAXN],match[MAXN];
void exploreCave(int N){
    for(int i = 0;i<N;++i){
        if(tryCombination(S) == i){ 
            for(int j = 0;j<N;++j){
                if(!vis[j]) S[j] = !S[j];
            }
        }
        int lo = 0, hi = N-1;
        while(lo < hi){
            int mid = (lo+hi)/2;
            for(int j = lo;j<=mid;++j){
                if(!vis[j]) S[j] = !S[j];
            }
            if(tryCombination(S) == i) hi = mid;
            else lo = mid+1;
            for(int j = lo;j<=mid;++j){
                if(!vis[j]) S[j] = !S[j];
            }
        }
        vis[lo] = true;
        match[lo] = i;
    }
    answer(S,match);
}

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