Submission #228101

#	Time	Username	Problem	Language	Result	Execution time	Memory
228101		monus1042	Cave (IOI13_cave)	C++17	100 / 100	458 ms	632 KiB

cave

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

const int MAXS = 5001;
int sw[MAXS], opens[MAXS], definedcomb[MAXS];

void funfun(int l, int r, int color, int currdoor)
{
	// base case:
	if (l==r){
		definedcomb[r]=color;
		opens[r]=currdoor;
		return;
	}
	
	// general case:
	int mid=(l+r)/2;
	for (int i=l; i<=mid; i++)
		if (definedcomb[i]==-1)
			sw[i]=color;

	int complement=color ^ 1;
	for (int i=mid+1; i<=r; i++)
		if (definedcomb[i]==-1)
			sw[i]=complement;

	int temp=tryCombination(sw);
	if (temp!=currdoor){
		funfun(l, mid, color, currdoor);
	}else{
		for(int i=l; i<=mid; i++)
			if (definedcomb[i]==-1)
				sw[i]=complement;

		for (int i=mid+1; i<=r; i++)
			if (definedcomb[i]==-1)
				sw[i]=color;

		funfun(mid+1, r, color, currdoor);
	}
}

void exploreCave(int N)
{
	memset(opens, -1, sizeof opens);
	memset(definedcomb, -1, sizeof definedcomb);
	int n=N;
	
	for (int i=0; i<n; i++){ //find out the switch of the ith door
		memset(sw, 0, sizeof sw);
		for (int j=0; j<n; j++)
			if (definedcomb[j]!=-1)
				sw[j]=definedcomb[j];

		int temp=tryCombination(sw);
		if (temp!=i){
			//ok this opens the door
			funfun(0, n-1, 0, i);
		}else{
			for (int j=0; j<n; j++){
				if (definedcomb[j]==-1) sw[j]=1;
				else sw[j]=definedcomb[j];
			}
			funfun(0, n-1, 1, i);
		}
	}
	answer(definedcomb, opens);
}

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