Submission #774859

#	Time	Username	Problem	Language	Result	Execution time	Memory
774859		khshg	Cave (IOI13_cave)	C++14	100 / 100	334 ms	516 KiB

cave

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

void exploreCave(int N) {
	int cor[N]{}, DtoS[N]{}, StoD[N]{};
	for(int i = 0; i < N; ++i) {
		bool f = (tryCombination(cor) == i);
		int tl = 0, tr = N - 1;
		while(tl < tr) {
			int tm = (tl + tr) / 2;
			int ask[N]{};
			for(int j = 0; j <= tm; ++j) {
				ask[j] = 1;
			}
			for(int j = 0; j < i; ++j) ask[DtoS[j]] = cor[DtoS[j]];
			bool F = (tryCombination(ask) == i);
			if(F == f) {
				tl = tm + 1;
			} else tr = tm;
		}
		DtoS[i] = tl;
		StoD[tl] = i;
		cor[tl] = f;
	}
	answer(cor, StoD);
}

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