Submission #706071

#	Time	Username	Problem	Language	Result	Execution time	Memory
706071		Nonoze	동굴 (IOI13_cave)	C++14	100 / 100	343 ms	444 KiB

cave

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

void exploreCave(int N) {
	vector<int> S(N, 0), D(N, -1);
	for (int i = 0; i < N; ++i)
	{
		int remplacer=1;
		int tryc=tryCombination(&S[0]);
		if (tryc>i || tryc==-1) {
			for (int j = 0; j < N; ++j)
			{
				if (D[j]==-1)
				{
					S[j]=1;
				}
			}
			remplacer=0;
		}
		vector<int> s_new=S;
		int l=0, r=N-1;
		while(l<r) {
			int mid=(l+r)/2;
			for (int j = l; j <= mid; ++j)
			{
				if (D[j]==-1)
				{
					s_new[j]=remplacer;
				}
			}
			int tryc=tryCombination(&s_new[0]);
			if (tryc>i || tryc==-1) {
				r=mid;
			}
			else {
				l=mid+1;
			}
			s_new=S;
		}
		S[l]=remplacer;
		D[l]=i;
		for (int j = 0; j < N; ++j)
		{
			if (D[j]==-1)
			{
				S[j]=0;
			}
		}
		/*cout << l << endl;
		for (int j = 0; j < N; ++j)
		{
			cout << D[j] << " ";
		}
		cout << " ;" << remplacer << endl;
		cout << endl;*/
	}
	answer(&S[0], &D[0]);
}

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