Submission #864922

#	Time	Username	Problem	Language	Result	Execution time	Memory
864922		dpsaveslives	Cave (IOI13_cave)	C++17	100 / 100	188 ms	808 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
bool vis[MAXN]; //save for all switches if we set them already
int S[MAXN], ans[MAXN];
void exploreCave(int N){
    //memset
    for(int i = 0;i<N;++i){
        if(tryCombination(S) == i){
            for(int j = 0;j<N;++j){
                if(!vis[j]) S[j] = 1-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] = 1-S[j];
            }
            if(tryCombination(S) == i) hi = mid;
            else lo = mid+1;
            for(int j = lo;j<=mid;++j){
                if(!vis[j]) S[j] = 1-S[j];
            }
        }
        vis[lo] = true;
        ans[lo] = i;
    }
    answer(S,ans);
}

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