Submission #917021

#	Time	Username	Problem	Language	Result	Execution time	Memory
917021		mpb_	Cave (IOI13_cave)	C++17	0 / 100	247 ms	852 KiB

cave

#include "cave.h"
#include <vector>
#include <iostream>
#include <string.h>

void exploreCave(int N) {
	using namespace std;
	auto guess = [&](vector<int>& g) {
		int s[N];
		for (int i = 0; i < N; i++) {
			s[i] = g[i];
		}
		int res = tryCombination(s);
		return (res == -1 ? 1e9 : res);
	};
	vector<int> ans(N), where(N), fix(N);
	auto build = [&](int l, int r) {
		vector<int> g = ans;
		for (int i = l; i <= r; i++) {
			if (fix[i]) g[i] = ans[i] ^ 1;
		}
		return g;
	};
	int score = guess(ans);
	for (int i = 0; i < N; i++) {
		if (score <= i) {
			int l = 0, r = N - 1, loc = -1;
			while (l <= r) {
				int m = l + (r - l) / 2;
				vector<int> g = build(l, m);
				int score = guess(g);
				if (score >= i) {
					loc = m;
					r = m - 1;
				} else {
					l = m + 1;
				}
			}
			fix[loc] ^= ans[loc];
			ans[loc] ^= ans[loc];
			where[i] = loc;
		} else {
			int l = 0, r = N - 1, loc = -1;
			while (l <= r) {
				int m = l + (r - l) / 2;
				vector<int> g = build(l, m);
				int score = guess(g);
				if (score < i) {
					loc = m;
					r = m - 1;
				} else {
					l = m + 1;
				}
			}
			fix[loc] ^= ans[loc];
			ans[loc] ^= ans[loc];
			where[i] = loc;
		}
	}
	int a[N], b[N];
	for (int i = 0; i < N; i++) {
		a[i] = ans[i];
		b[i] = where[i];
	}
	answer(a, b);
}

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