Submission #444648

#	Time	Username	Problem	Language	Result	Execution time	Memory
444648		Hanksburger	Cave (IOI13_cave)	C++14	100 / 100	1080 ms	716 KiB

cave

#ifdef __cplusplus
extern "C" {
#endif
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
#ifdef __cplusplus
}
#endif
#include <bits/stdc++.h>
using namespace std;
int ansS[5000], ansD[5000], guess[5000], NN;
void recur(int index, int L, int R, int x)
{
	if (L==R)
	{
		int cnt=0;
		for (int i=0; i<NN; i++)
		{
			if (ansS[i]==-1)
			{
				if (cnt==L)
				{
					ansS[i]=guess[i]=x;
					ansD[i]=index;
					return;
				}
				cnt++;
			}
		}
//		cout << "-------------------------------------------\n";
	}
//	cout << "recur " << index << ' ' << L << ' ' << R << ' ' << x << '\n';
	int mid=(L+R)/2, cnt=0;
	for (int i=0; i<NN; i++)
	{
//		cout << "here\n";
		if (ansS[i]==-1)
		{
			if (L<=cnt && cnt<=mid)
				guess[i]=x;
			else
				guess[i]=1-x;
			cnt++;
//			cout << "guess " << i << " = " << guess[i] << '\n';
		}
	}
	if (tryCombination(guess)==index)
		recur(index, mid+1, R, x);
	else
		recur(index, L, mid, x);
}
void exploreCave(int N)
{
	NN=N;
	for (int i=0; i<N; i++)
		ansS[i]=-1;
	for (int i=0; i<N; i++)
	{
		for (int j=0; j<N; j++)
			if (ansS[j]==-1)
				guess[j]=0;
		recur(i, 0, N-i-1, (tryCombination(guess)==i));
	}
	answer(ansS, ansD);
}

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