Submission #64945

#	Time	Username	Problem	Language	Result	Execution time	Memory
64945		gnoor	Cave (IOI13_cave)	C++17	100 / 100	1634 ms	640 KiB

cave

#include "cave.h"

int asking[5010];

bool known[5010];
int	config[5010]; 
int whatd[5010];

int n;
void prepare() {
	for (int i=0;i<n;i++) {
		if (known[i]) asking[i]=config[i];
	}
}

void set(int l,int r,int val) {
	for (int i=l;i<=r;i++) {
		asking[i]=val;
	}
}

void clear(int val) {
	set(0,n-1,val);
}

void exploreCave(int N) {
	n=N;
	for (int i=0;i<n;i++) {
		clear(0);
		prepare();
		int state=-1;
		int res;
		res=tryCombination(asking);
		if (res>i||res==-1) {
			state=0;
		} else {
			state=1;
		}
		int lo=0;
		int hi=n-1;
		int mid;
		while (lo<hi) {
			mid=(lo+hi)>>1;
			clear(!state);
			set(lo,mid,state);
			prepare();
			res=tryCombination(asking);
			if (res>i||res==-1) {
				hi=mid;
			} else {
				lo=mid+1;
			}
		}
		known[lo]=1;
		config[lo]=state;
		whatd[lo]=i;
	}
	answer(config,whatd);
}

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