Submission #166728

#	Time	Username	Problem	Language	Result	Execution time	Memory
166728		alanhpereira	Cave (IOI13_cave)	C++11	100 / 100	1085 ms	564 KiB

cave

#include "cave.h"
#define MAX 5123

int ans[MAX];
int att[MAX];
int crsp[MAX];

void invert(int l, int r) {
	//printf("inverting %d to %d\n", l, r);
	for (int i = l; i <= r; i++)
		att[i] = !att[i];
}

int goFor(int N) {
	for (int j = 0; j < N; j++) {
		if (ans[j] != -1) att[j] = ans[j];
	}
	/*printf("trying:\n");
	for (int i = 0; i < N; i++) {
		printf("%d ", att[i]);
	}
	printf("\n");*/
	int ret = tryCombination(att);
	//printf("got %d\n", ret);
	return ret;
}

void exploreCave(int N) {
	for (int i = 0; i < N; i++) {
		ans[i] = -1;
		att[i] = 0;
	}
	for (int i = 0; i < N; i++) {
		int ret = goFor(N);
		int lastState = ret == i;
		int l = 0, r = N - 1;
		while (l != r) {
			int mid = (l + r) / 2;
			invert(l, mid);
			ret = goFor(N);
			int state = ret == i;
			if (state == lastState) {
				l = mid + 1;
			}
			else {
				r = mid;
			}
			lastState = state;
		}
		crsp[l] = i;
		//printf("lastState is %d\n", lastState);
		if (lastState)
			ans[l] = !att[l];
		else
			ans[l] = att[l];
		//printf("ans[%d]=%d\n", l, ans[l]);
		//printf("crsp[%d]=%d\n\n", l, crsp[l]);
	}
	answer(ans, crsp);
}

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