Submission #1151418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151418		tesseract	Cave (IOI13_cave)	C++20	100 / 100	100 ms	524 KiB

cave

#include "cave.h"
#include <vector>
#include <ranges>

using namespace std;

const int max_N = 5000;

// toTry[s] is the position of switch s to try the next time.
// For switches whose correct position is known, toTry[s]
// is frozen to the correct position.
int toTry[max_N];

// The switches whose door isn't yet known.
vector<int> remainingSwitches;

// door[i] is the door number connected to switch i.
int door[max_N];

void solve(int d);

void exploreCave(int N) {

	remainingSwitches.resize(N);
	for(int i : views::iota(0,N)) {
		remainingSwitches[i] = i;
	}
	for(int d : views::iota(0,N)) {
		solve(d);
	}
	answer(toTry, door);
}

// Tries with the configuration toTry, and returns whether door d is open,
// assuming all earlier doors are open.
bool isDoorOpen(int d) {
	int firstClosedDoor = tryCombination(toTry);
	return (firstClosedDoor == -1 || firstClosedDoor > d);
}

// Solve for door d, assuming all previous doors have been solved.
void solve(int d) {
	for(int s : remainingSwitches) {
		toTry[s] = 0;
	}
	int correctSwitchPosition = isDoorOpen(d) ? 0 : 1;

	int L = 0, U = remainingSwitches.size();
	// Invariant: The correct switch corresponding to door d is remainingSwitches[i]
	// for some i in [L, U).
	while(U-L > 1) {
		int mid = L+(U-L)/2;
		for(int q : views::iota(L, mid)) {
			toTry[remainingSwitches[q]] = correctSwitchPosition;
		}
		for(int q : views::iota(mid, U)) {
			toTry[remainingSwitches[q]] = 1-correctSwitchPosition;
		}
		if(isDoorOpen(d)) {
			U = mid;
		} else {
			L = mid;
		}
	}

	int switchForThisDoor = remainingSwitches[L];

	door[switchForThisDoor] = d;
	toTry[switchForThisDoor] = correctSwitchPosition;
	remainingSwitches.erase(remainingSwitches.begin() + L);
}

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