Submission #306333

#	Time	Username	Problem	Language	Result	Execution time	Memory
306333		syy	Cave (IOI13_cave)	C++17	100 / 100	265 ms	624 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

int spos[5005], door[5005], ret;
bool cor[5005], prevdopen, dopen;

void exploreCave(int N) {
	for (int i = 0; i < N; i++) door[i] = -1;
	memset(cor, 0, sizeof cor); //All incorrect
	ret = tryCombination(spos);
	
	for (int i = 0; i < N; i++) { //Solve for each door
		if (ret == -1 or ret > i) prevdopen = true;
		else prevdopen = false;

		int upper = N, lower = -1;

		while (upper - lower > 1) {
			int mid = (upper + lower) / 2;
			for (int j = lower + 1; j <= mid; j++) {
				if (cor[j]) continue;
				spos[j] = !spos[j];
			}
			ret = tryCombination(spos);

			if (ret == -1 or ret > i) dopen = true;
			else dopen = false;

			if (dopen == prevdopen) lower = mid; //Switch not in this half
			else upper = mid;
			prevdopen = dopen;
		}
		door[upper] = i;//Switch is upper
		cor[upper] = true;
		
		if (!dopen) { //Guessed which switch but position wrong
			spos[upper] = !spos[upper];
			ret = tryCombination(spos);
		}
	}
	answer(spos, door);
}

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