Submission #242086

#	Time	Username	Problem	Language	Result	Execution time	Memory
242086		GREGOIRELC	Cave (IOI13_cave)	C++14	100 / 100	294 ms	640 KiB

cave

#include "cave.h"

const int MAX_PORTE = 5000;

int etatValide[MAX_PORTE];
int porteRelie[MAX_PORTE];
int curEtat[MAX_PORTE];

void fixe(int bGauche, int bDroite, int val)
{
	for(int i = bGauche; i <= bDroite; i++)
	{
		if(etatValide[i] == -1)
		{
			curEtat[i] = val;
		}
		else
		{
			curEtat[i] = etatValide[i];
		}
	}
}

void exploreCave(int N) 
{
	for(int i = 0; i < N; i++)
	{
		etatValide[i] = -1;
	}
	for(int i = 0; i < N; i++)
	{
		fixe(0, N - 1, 0);
		int valide = 1;
		int a = tryCombination(curEtat);
		if(a > i || a == -1)
		{
			valide = 0;
		}
		else
		{
			fixe(0, N - 1, 1);
		}
		int deb = 0, fin = N - 1;
		while(deb < fin - 1)
		{
			int mid = (deb + fin) / 2;
			fixe(deb, mid, (valide + 1) % 2);
			a = tryCombination(curEtat);
			if(a > i || a == -1)
			{
				deb = mid + 1;
			}
			else
			{
				fin = mid;
			}
			fixe(deb, mid, valide);
		}
		fixe(deb, deb, (valide + 1) % 2);
		a = tryCombination(curEtat);
		if(a > i || a == -1)
		{
			porteRelie[fin] = i;
			etatValide[fin] = valide;
		}
		else
		{
			porteRelie[deb] = i;
			etatValide[deb] = valide;
		}
		fixe(deb, deb, valide);
	}
	answer(etatValide, porteRelie);
}

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