Submission #280926

#	Time	Username	Problem	Language	Result	Execution time	Memory
280926		jairRS	Cave (IOI13_cave)	C++17	46 / 100	33 ms	640 KiB

cave

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

int c[5000];
int s[5000];

int invert(int bit)
{
	return bit * -1 + 1;
}

void exploreCave(int N)
{
	set<int> unknown;
	for (int i = 0; i < N; i++)
	{
		unknown.insert(i);
	}

	int closed, newClosed;
	closed = tryCombination(c);
	while (closed != -1)
	{
		for (int sw : unknown)
		{
			c[sw] = invert(c[sw]);
			newClosed = tryCombination(c);
			if (newClosed > closed || newClosed == -1)
			{
				s[sw] = closed;
				unknown.erase(sw);
				break;
			}
			else if (newClosed < closed)
			{
				s[sw] = newClosed;
				unknown.erase(sw);
				c[sw] = invert(c[sw]);
			}
		}
		closed = tryCombination(c);
	}

	for (int sw : unknown)
	{
		c[sw] = invert(c[sw]);
		closed = tryCombination(c);
		s[sw] = closed;
		c[sw] = invert(c[sw]);
	}

	answer(c, s);
}

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