Submission #976728

#	Time	Username	Problem	Language	Result	Execution time	Memory
976728		SiliconSquared	Cave (IOI13_cave)	C++14	100 / 100	144 ms	600 KiB

cave

#include "cave.h"
using namespace std;

void exploreCave(int N) {
    int a,b,q;
    bool e,f;
    int z[N];
    int y[N];
    int x[N];
    bool g[N];
    for (int i=0;i<N;i++){z[i]=0;g[i]=false;}
    for (int i=0;i<N;i++){
        q=tryCombination(z);
        a=0;
        b=N-1;
        for (int j=0;j<N;j++){x[j]=z[j];}
        while (a!=b){
            f=(q==i);
            for (int j=a;j<=(a+b)/2;j++){
                if (!g[j]){
                    x[j]=!x[j];
                }
            }
            q=tryCombination(x);
            e=(q==i);
            if (e!=f){
                b=(a+b)/2;
            }else{
                a=(a+b)/2+1;
            }
        }
        g[a]=true;
        y[a]=i;
        if (q==i){
            x[a]=!x[a];
        }
        for (int i=0;i<N;i++){z[i]=x[i];}
    }
    answer(x,y);
}

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