Submission #16640

#	Time	Username	Problem	Language	Result	Execution time	Memory
16640		suhgyuho_william	Cave (IOI13_cave)	C++98	100 / 100	507 ms	604 KiB

cave

#include "cave.h"

int ans[5002],door[5002],res[5002],resd[5002];
int test[5002],check[5002];

void exploreCave(int N) {
    //ans[0]=ans[1]=ans[2]=1; ans[3]=0;
    //door[0]=3; door[1]=1; door[2]=0; door[3]=2;

    int i,j,n=N;
    int left,mid,right;
    int num;

    for(i=0;i<n;i++){
        for(j=0;j<n;j++) if(!check[j]) test[j]=0;
        num=tryCombination(test);
        if(num==i) ans[i]=1;
        else ans[i]=0;

        left=0; right=n-1;
        while(left<=right){
            mid=(left+right)/2;
            if(left==right) break;

            for(j=left;j<=mid;j++) if(!check[j]) test[j]=ans[i];
            for(j=mid+1;j<=right;j++) if(!check[j]) test[j]=1-ans[i];
            num=tryCombination(test);
            if(num==i) left=mid+1;
            else right=mid;
        }
        door[i]=mid;
        check[mid]=1;
        test[mid]=ans[i];
    }

    for(i=0;i<n;i++) res[door[i]]=ans[i];
    for(i=0;i<n;i++) resd[door[i]]=i;
    answer(res,resd);
}

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