제출 #917029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917029		mpb_	동굴 (IOI13_cave)	C++17	100 / 100	259 ms	696 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] ^= 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] = 1;
			ans[loc] ^= 1;
			where[loc] = i;
		} 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] = 1;
			where[loc] = i;
		}
		score = guess(ans);
	}
	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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24