Submission #17650

#	Time	Username	Problem	Language	Result	Execution time	Memory
17650		Namnamseo	Cave (IOI13_cave)	C++14	100 / 100	493 ms	644 KiB

cave

#include "cave.h"
#include <cstdio>

int  trial_array   [5010];

bool fixed_point   [5010];

int switch_forward [5010]; // index is for switch
int switch_reverse [5010]; // index is for door
int switch_parity  [5010]; // index is for switch; value makes it open.

int n;

// zero is for open, one means closed.

int try_wrapper(){
    int tmp = tryCombination(trial_array);
    if(tmp<0) tmp=2*n;
    return tmp;
}

void find_switch(int l,int r,int target,int zero_result){
    if(l==r){
        //printf("Found door %d : switch %d\n",target,l);
        switch_reverse[target]=l;
        switch_forward[l]=target;
        switch_parity [l]=1-zero_result;
        fixed_point   [l]=1;
    } else {
        int m=(l+r)/2;
        int i;
        for(i=l; i<=m; ++i) if(!fixed_point[i]) trial_array[i]=1;
        /*int tmp;
        printf("Trial ");
        for(tmp=0; tmp<n; ++tmp) {
            printf("%d",trial_array[tmp]);
            if(tmp+1<n) putchar(',');
        }
        printf(" : ");*/
        int result = try_wrapper();
        //printf("%d\n",result);
        for(i=l; i<=m; ++i) if(!fixed_point[i]) trial_array[i]=0;
        if((result != target) == !zero_result) {
            find_switch(l  , m, target, zero_result);
        } else {
            find_switch(m+1, r, target, zero_result);
        }
    }
}

void exploreCave(int n) {
    ::n=n;
    int i,j;
    for(i=0;i<n;++i){
        for(j=0;j<n;++j) trial_array[j]=0;
        for(j=0; j<i; ++j) {
            trial_array[switch_reverse[j]]=switch_parity[switch_reverse[j]];
            //printf("Fixed[%d] = %d; %d opens %d\n",j,fixed_point[j],switch_reverse[j],j);
        }
        /*printf("zero result(");
        printf("%d,%d,%d,%d",
               trial_array[0],
               trial_array[1],
               trial_array[2],
               trial_array[3]
               );
        printf(") : %d\n",(try_wrapper() != i));*/
        find_switch(0,n-1, i,(try_wrapper() != i));
    }
    answer(switch_parity, switch_forward);
}

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