Submission #1216919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216919		beijing	Cave (IOI13_cave)	C++20	100 / 100	296 ms	516 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

void exploreCave(int N){
    int S[N],D[N];
    bool used[N];

    for(int i=0;i<N;i++){
        S[i]=0;
        D[i]=0;
        used[i]=false;
    }

    for(int door=0;door<N;door++){
        for(int i=0;i<N;i++){
            if(!used[i])S[i]=0;
        }

        int blocked=tryCombination(S);
        int correctPos=(blocked!=door?0:1);

        for(int i=0;i<N;i++){
            if(!used[i])S[i]=1-correctPos;
        }

        int l=0,r=N-1,idx=0;
        while(l<r){
            int m=(l+r)/2;
            for(int i=l;i<=m;i++){
                if(!used[i])S[i]=correctPos;
            }

            blocked=tryCombination(S);

            if(blocked!=door){
                idx=m;
                r=m;
            }else{
                idx=m+1;
                l=m+1;
            }

            for(int i=l;i<=m;i++){
                if(!used[i])S[i]=1-correctPos;
            }
        }

        D[idx]=door;
        used[idx]=true;
        S[idx]=correctPos;
    }

    answer(S,D);
}

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