Submission #333226

#	Time	Username	Problem	Language	Result	Execution time	Memory
333226		Cantfindme	Cave (IOI13_cave)	C++17	100 / 100	257 ms	620 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int currentd,high,low,mid;
int dstate,prevs,result;
bool bug = false;

void exploreCave(int N) {
	int D[N], A[N];
	bool known[N];
	currentd = 0;

	memset(known,0,sizeof known);
	for (int i =0;i<N;i++) D[i] = -1;
	for (int i =0;i<N;i++) A[i] = 0;

	result = tryCombination(A);
	for (;currentd < N;currentd++) {
		//1 is open 0 is close
		if (result == -1 or result > currentd) {
			prevs = 1;
		}	else prevs = 0;
		high = N;
		low = -1;
		if (bug) cout << currentd << " r:" << result << " s:" << prevs << "\n";
		while (high - low > 1) {
			mid = (high+low)/2;
			//< or <=?
			for (int i = low+1;i<=mid;i++) {
				if (known[i]) continue;
				A[i] = !A[i];
			}
			result = tryCombination(A);
			if (result == -1 or result > currentd) dstate = 1;
			else dstate = 0;

			if (dstate == prevs) low = mid; 
			else high = mid;
			prevs = dstate;
			if (bug) {
				cout << prevs << " ";
				printf("h:%d m:%d l:%d d:%d r:%d \n A:",high,mid,low,dstate,result);
				for (int i =0;i<N;i++) cout << A[i] << " ";
				cout << "\n";
			}
		}
		known[high] = true;
		if (!prevs) {A[high] = !A[high]; result = tryCombination(A);}
		D[high] = currentd;
		if (bug) cout << high << " " << D[high] << "\n";
	}
	answer(A,D);
}

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