Submission #251715

#	Time	Username	Problem	Language	Result	Execution time	Memory
251715		tutis	Cave (IOI13_cave)	C++17	100 / 100	562 ms	768 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N)
{
	int S[N];
	int D[N];
	int K[N];
	for (int i = 0; i < N; i++)
	{
		vector<bool>tinka(N, true);
		for (int j = 0; j < i; j++)
		{
			tinka[K[j]] = false;
		}
		vector<int>antros;
		for (int j = 0; j < N; j++)
			if (tinka[j])
				antros.push_back(j);
		for (int j : antros)
			S[j] = 0;
		int t = 0;
		if (tryCombination(S) == i)
			t = 1;
		while (antros.size() > 1)
		{
			vector<int>a1;
			vector<int>a2;
			for (int j : antros)
			{
				if (a1.size() < a2.size())
				{
					a1.push_back(j);
				}
				else
				{
					a2.push_back(j);
				}
			}
			for (int j : a1)
			{
				S[j] = t;
			}
			for (int j : a2)
			{
				S[j] = 1 - t;
			}
			if (tryCombination(S) != i)
			{
				antros = a1;
				for (int j : a2)
					S[j] = t;
			}
			else
			{
				antros = a2;
				for (int j : a1)
					S[j] = t;
			}
		}
		int k = antros[0];
		D[k] = i;
		K[i] = k;
		S[k] = t;
	}
	answer(S, D);
}

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