Submission #16266

#	Time	Username	Problem	Language	Result	Execution time	Memory
16266		CodingBug	Cave (IOI13_cave)	C++98	100 / 100	311 ms	512 KiB

cave

#include "cave.h"
#define M 5000

void exploreCave(int N) {
    bool ch[N];
    int s[N],a[N],i,j;
    for(i=0;i<N;i++){
        ch[i]=false;
        s[i]=0;
        a[i]=0;
    }
    for(i=0;i<N;i++){
        int p,p2=tryCombination(s);
        int st,ed,mi;
        for(st=0,ed=N-1;st<ed;((p==i)^((p2=tryCombination(s))==i)) ? st=mi+1 : ed=mi){
            p=p2;
            mi=(st+ed)/2;
            for(j=mi+1;j<=ed;j++) if(!ch[j]) s[j]=!s[j];
        }
        if(p2==i) s[st]=!s[st];
        ch[st]=true;
        a[st]=i;
    }
    answer(s,a);
}

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