Submission #164370

#	Time	Username	Problem	Language	Result	Execution time	Memory
164370		cfalas	Cave (IOI13_cave)	C++14	100 / 100	948 ms	736 KiB

cave

#include<bits/stdc++.h>
using namespace std;
#include "cave.h"
#define pr(x) cout<<#x<<" "<<x<<endl;


void exploreCave(int n) {
	int used[n]={}, correct[n] = {};
	int aa[n];
	for(int i=0;i<n;i++){
		// Find correct position of switch
		int curr[n];
		for(int j=0;j<n;j++){
			if(used[j]) curr[j] = correct[j];
			else curr[j] = 1;
			//cout<<curr[j]<<" ";
		}
		//cout<<endl;
		int ans = tryCombination(curr);
		int correctVal = 1;
		//cout<<ans<<endl;
		if(ans<=i && ans!=-1) correctVal = 0;
		
		//pr(correctVal);

		// Find switch needed
		int l=0, r=n-1;
		int m;
		while(l<=r){
			m = (l+r)/2;
			//cout<<m<<": ";
			for(int j=0;j<=m;j++){
				if(used[j]) curr[j] = correct[j];
				else curr[j] = correctVal;
				//cout<<curr[j]<<" ";
			}
			for(int j=m+1;j<n;j++){
				if(used[j]) curr[j] = correct[j];
				else curr[j] = 1 - correctVal;
				//cout<<curr[j]<<" ";
			}
			//cout<<endl;
			ans = tryCombination(curr);
			if(ans>i || ans==-1){
				r = m-1;
			}
			else m++, l = m;
		}
		used[m] = true;
		correct[m] = correctVal;
		aa[m] = i;
		//pr(m);
		//cout<<"--------------------\n";
	}
		answer(correct, aa);
}

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