Submission #989591

#	Time	Username	Problem	Language	Result	Execution time	Memory
989591		ttamx	Cave (IOI13_cave)	C++17	100 / 100	489 ms	600 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

void exploreCave(int N){
    int s[N]={},d[N]={};
    vector<bool> known(N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)if(!known[j])s[j]=0;
        int door=tryCombination(s);
        int state=1;
        if(door>i||door==-1)state=0;
        int l=0,r=N-1;
        while(l<r){
            int m=(l+r)/2;
            for(int j=0;j<N;j++)if(!known[j]){
                if(j<=m)s[j]=state;
                else s[j]=state^1;
            }
            door=tryCombination(s);
            if(door>i||door==-1)r=m;
            else l=m+1;
        }
        known[l]=true;
        s[l]=state;
        d[l]=i;
    }
    answer(s,d);
}

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