Submission #167964

#	Time	Username	Problem	Language	Result	Execution time	Memory
167964		lukameladze	Cave (IOI13_cave)	C++14	0 / 100	752 ms	524 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++)
	{
		for (int j=0; j<n; j++)
		{
			if (pre[i]==-1) 
			x[i]=1;
			else
			x[i]=pre[i];
		}
		 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(pr[i]==-1) x[i]=k;
				else x[i]=pr[i];
			}
			for(int j=0; j<le; j++) 
			{
				if (pr[j]==-1)
				{
					if (k==1)
					{
						x[j]=0;
					}
					else
					x[j]=1;
				}
				else
				x[j]=pr[j];
			}
			for (int j=mid+1; j<n; j++)
			{
				if (pr[j]==-1)
				{
					if (k==1)
					{
						x[j]=0;
					}
					else
					x[j]=1;
				}
				else
				x[j]=pr[j];
			}
    		 idx=tryCombination(x);
    	if(idx>i || idx==-1)
    		ri=mid;
			else
			le=mid+1;
		}
		mid=(le+ri)/2;
		w=mid;
		ans[mid]=i;
		pr[mid]=k;
	}
	answer(pr,ans);
}

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