Submission #1164633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164633		crispxx	Cave (IOI13_cave)	C++20	100 / 100	954 ms	768 KiB

cave

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define eb emplace_back
#define pb push_back
#define ar array
#define nl '\n'

#include "cave.h"
// #include "grader.c"

const int mxN = 5e3 + 5;

bool is[mxN];
int S[mxN], D[mxN];

void exploreCave(int n) {
	auto opens = [&](int got, int trg) {
		return got == -1 || got > trg;
	};
	
	auto color = [&](int trg) {
		int q[n]{};
		for(int i = 0; i < n; i++) {
			if(is[i]) q[i] = S[i];
		}
		if(opens(tryCombination(q), trg)) return 0;
		else return 1;
	};
	
	auto Dnc = [&](auto &&self, int l, int r, int trg, int col) -> void {
		if(l == r) {
			is[l] = true;
			S[l] = col;
			D[l] = trg;
			return;
		}
		int q[n];
		int m = (l + r) >> 1;
		for(int i = 0; i < n; i++) {
			if(is[i]) q[i] = S[i];
			else if(i >= l && i <= m) q[i] = col;
			else q[i] = col ^ 1;
		}
		if(opens(tryCombination(q), trg)) {
			self(self, l, m, trg, col);
		} else {
			self(self, m + 1, r, trg, col);
		}
	};
	
	for(int i = 0; i < n; i++) {
		Dnc(Dnc, 0, n - 1, i, color(i));
	}
	
	answer(S, D);
}

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