Submission #395122

#	Time	Username	Problem	Language	Result	Execution time	Memory
395122		jeroenodb	Cave (IOI13_cave)	C++14	100 / 100	443 ms	580 KiB

cave

#include "cave.h"
#include <vector>
#include <iostream>
using namespace std;

#define D(a) \
    do { cout << #a " " << (a) << " ";} while(false)
const int mxN = 5010;
int myn, blockingdoor,zeroes,dif,foundcnt;
int door[mxN],combi[mxN];
vector<int> range;


void makeRange() {
	// maakt een vector met alle deuren die nog niet zijn gevonden
	range.clear();
	//cout << "range: ";
	for(int i=0;i<myn;++i) {
		if(door[i]==-1) {
			range.push_back(i);
			//cout << i;
		}
	} //cout << endl;
}

int getTry(int l, int r) {
	for(int i=l;i<=r;++i) {
		combi[range[i]] = 1;
	}
	//cout << "trying ";
	// for(int i=0;i<myn;++i) {
	// 	cout << combi[i];
	// } cout << ' ';
	int ans = tryCombination(combi);
	for(int i=l;i<=r;++i) {
		combi[range[i]] = 0;
	} 
	if(ans==-1) ans = 1e9-1;
	return ans;
}

bool explore(int l,int r, bool dotry=true, int prevans=-1) {
	//D(l);D(r);cout <<endl;

	int mytry, mid = (l+r)/2;

	if(dotry) { 
		mytry = getTry(l,r);
		//D(mytry);cout << endl;
	}
	else mytry = prevans;

	if(l==r) {
		// aangekomen bij een enkel element in de binary search
		if(mytry>zeroes) { // Blockingdoor is kennelijk opengegaan
			door[range[l]] = zeroes;
			blockingdoor = range[l];
			//cout << "found blockingdoor\n";
			foundcnt++;
			return true;
		} else if(mytry<zeroes) { // Een andere deur blokkeert nu
			door[range[l]] = mytry;
			foundcnt++;
			return true;
		}
		else return false;

	}
	if(mytry>zeroes or mytry<zeroes) {
		bool found = explore(l,mid,true,mytry);
		if(foundcnt>=dif) { // alle deuren voor de blockingdoor en de blockingdoor zelf zijn gevonden
			//cout << "No more\n";
			return true;
		}
		explore(mid+1,r,found,mytry);
		return true;
	}
	// mytry blokkeert nog steeds de blockingdoor en blokkeert geen enkele deur ervoor. geen extra info
	return false;
}
using namespace std;
void exploreCave(int N) {

	blockingdoor=-1;zeroes=-1;myn = N;
	for(int i=0;i<myn;++i) {door[i]=-1;combi[i]=0;}

	while(true) {
		makeRange();
		if(range.size()==0) break;

		int prevzeroes=zeroes;
		zeroes = getTry(0,-1); 
		dif = zeroes-prevzeroes;
		foundcnt = 0;
		//D(zeroes);cout << endl;
		explore(0,range.size()-1);
		// de blockingdoor is gevonden, deze stond op nul, nu zetten we hem op 1
		if(blockingdoor!=-1) combi[blockingdoor] = 1;
	}
	answer(combi,door);	

}

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