제출 #1311534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311534		kustov_vadim_533	Cave (IOI13_cave)	C++20	100 / 100	407 ms	524 KiB

cave

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

const int MAXN = 5000;

int p[MAXN], f[MAXN], us[MAXN];

void inverse(int l, int r) {
	for (int i = l; i < r; ++i) {
		if (!us[i]) f[i] = 1 - f[i];
	}
}

void solve(int l, int r, int res) {
	if (r - l == 1) {
		f[l] = 1 - f[l];
		int c = tryCombination(f);
		us[l] = 1;

		if (c < res && c != -1) {
			f[l] = 1 - f[l];
		}
		return;
	}

	int s = 0;
	for (int i = l; i < r; ++i) {
		s += 1 - us[i];
	}
	if (s == 1) {
		for (int i = l; i < r; ++i){
			if (!us[i]) {
				solve(i, i + 1, res);
				return;
			}
		}
	}


	int m = l;
	int pr = 0;
	while (pr < s / 2 && m + 1 < r) {
		pr += 1 - us[m];
		++m;
	}

	inverse(l, m);
	int c = tryCombination(f);
	inverse(l, m);

	if (c != res) {
		solve(l, m, res);
	}
	else {
		solve(m, r, res);
	}
}

void exploreCave(int N) {
	for (int i = 0; i < N; ++i) {
		f[i] = 0;
		us[i] = 0;
	}

	for (int res = tryCombination(f); res != -1; res = tryCombination(f)) {
		if (res == 0) {
			inverse(0, N);
			continue;
		}
		solve(0, N, res);
	}

	for (int i = 0; i < N; ++i) {
		f[i] = 1 - f[i];
		p[i] = tryCombination(f);
		f[i] = 1 - f[i];
	}

	answer(f, p);
}

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