Submission #167967

#	Time	Username	Problem	Language	Result	Execution time	Memory
167967		lukameladze	Cave (IOI13_cave)	C++14	100 / 100	1100 ms	632 KiB

cave

# include <bits/stdc++.h>
# include "cave.h"
using namespace std;
int n,pr[100005],x[100005],le,ri,mid,pre[1000005],k,ans[1000005],idx,w;
void exploreCave(int N)
{
	n=N;
	for (int i=0; i<n; i++)
	pre[i]=-1;
	for (int i=0; i<n; i++)
	{
		for (int j=0; j<n; j++)
		{
			if (pre[j]==-1) 
			x[j]=1;
			else
			x[j]=pre[j];
		}
		 idx=tryCombination(x);
		if (idx>i || idx==-1) 
		k=1;
		else k=0;
		le=0;
		ri=n-1;
		while (le<ri)
		{
			mid=(le+ri)/2;
			for (int j=le; j<=mid; j++)
			{
				if(pre[j]==-1) x[j]=k;
				else x[j]=pre[j];
			}
			for(int j=0; j<le; j++) 
			{
				if (pre[j]==-1)
				{
					if (k==1)
					{
						x[j]=0;
					}
					else
					x[j]=1;
				}
				else
				x[j]=pre[j];
			}
			for (int j=mid+1; j<n; j++)
			{
				if (pre[j]==-1)
				{
					if (k==1)
					{
						x[j]=0;
					}
					else
					x[j]=1;
				}
				else
				x[j]=pre[j];
			}
    		 idx=tryCombination(x);
    	if(idx>i || idx==-1)
    		ri=mid;
			else
			le=mid+1;
		}
		mid=(le+ri)/2;
		w=mid;
		ans[mid]=i;
		pre[mid]=k;
	}
	answer(pre,ans);
}

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