제출 #379342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379342		pavement	동굴 (IOI13_cave)	C++17	100 / 100	371 ms	756 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

int A[5005], B[5005], C[5005];
bool F[5005];
vector<int> V;

// yeet
void exploreCave(int N) {
	for (int i = 0; i < N; i++) V.push_back(i);
	for (int i = 0; i < N; i++) {
		int lo = 0, hi = V.size() - 1;
		bool st = tryCombination(A) == i;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			for (int i = lo; i <= mid; i++)
				A[V[i]] = !A[V[i]];
			bool nst = tryCombination(A) == i;
			if (nst != st) st = nst, hi = mid;
			else lo = mid + 1;
		}
		if (st) C[V[lo]] = A[V[lo]];
		else C[V[lo]] = !A[V[lo]];
		A[V[lo]] = !C[V[lo]];
		B[V[lo]] = i;
		F[V[lo]] = 1;
		V.clear();
		for (int i = 0; i < N; i++)
			if (!F[i]) V.push_back(i);
	}
	answer(A, B);
}
// yeet

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