Submission #598439

#	Time	Username	Problem	Language	Result	Execution time	Memory
598439		PoonYaPat	Cave (IOI13_cave)	C++14	0 / 100	399 ms	412 KiB

cave

#include "cave.h"

//#include "grader.c"

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

void exploreCave(int n) {
    int con[n-1],test[n-1],ans[n-1]; // switch i connect to door con[i]
    bool fix_switch[n-1];
    memset(fix_switch,0,sizeof(fix_switch));

    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=0; j<n; ++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