Submission #613630

#	Time	Username	Problem	Language	Result	Execution time	Memory
613630		PoonYaPat	동굴 (IOI13_cave)	C++14	0 / 100	204 ms	416 KiB

cave

#include "cave.h"

using namespace std;

int con[5000],test[5000],ans[5000]; // switch i connect to door con[i]
bool fix_switch[5000];

void exploreCave(int n) {
    for (int i=0; i<n; ++i) { //find door x (0 to x-1 are open)
        for (int j=0; j<n; ++j) if (!fix_switch[j]) test[j]=0;
        int st=tryCombination(test);

        int l=0, r=n-1;

        while (r>l) {
            int mid=(l+r)/2;
            for (int j=l; j<=mid; ++j) if (!fix_switch[j]) test[j]=0;
            for (int j=mid+1; j<=r; ++j) if (!fix_switch[j]) test[j]=1;

            if (tryCombination(test)==st) r=mid; //not change
            else l=mid+1; //change
        }

        //door i switch r
        con[r]=i;
        fix_switch[r]=true;

        if (st==i) ans[r]=1;
        else ans[r]=0;

        test[r]=ans[r];
    }

    answer(ans,con);
}

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