Submission #972107

#	Time	Username	Problem	Language	Result	Execution time	Memory
972107		tamir1	Cave (IOI13_cave)	C++17	100 / 100	181 ms	756 KiB

cave

#include "cave.h"
#include<iostream>
using namespace std;
int S[5000],D[5000];
void exploreCave(int N) {
	int i,j;
	for(i=0;i<N;i++) D[i]=-1;
	for(i=0;i<N;i++){
		bool t=tryCombination(S)==i;
		int l=0,r=N-1,mid;
		while(r>l){
			mid=(r+l)/2;
			for(j=l;j<=mid;j++){
				if(D[j]==-1) S[j]=1-S[j];
			}
			if((tryCombination(S)==i)==t) l=mid+1;
			else r=mid;
			for(j=l;j<=mid;j++){
				if(D[j]==-1) S[j]=1-S[j];
			}
		}
		if(t) S[r]=1-S[r];
        D[r]=i;
	}
    answer(S,D);
}

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