Submission #863493

#	Time	Username	Problem	Language	Result	Execution time	Memory
863493		20163070	Cave (IOI13_cave)	C++14	100 / 100	367 ms	856 KiB

cave

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

void exploreCave(int N) {
    int c[N],d[N],res[N],res1[N],h1;
    for(int i=0;i<N;i++) d[i]=-1;
    for(int i=0;i<N;i++)
	{
		h1=0;
		for(int j=0;j<N;j++)
		{
			if(d[j]==-1) c[j]=0;
			else c[j]=d[j];
		}
		int h=tryCombination(c);
		if(h!=i) h1=1;
		int l,r;
		l=0,r=N-1;
		while(l<r)
		{
			int m=(l+r)/2;
			for(int j=0;j<N;j++)
			{
				if(d[j]==-1) c[j]=h1;
				else c[j]=d[j];
			}
			for(int j=l;j<=m;j++)
			{
				if(d[j]==-1) c[j]=1-h1;
			}
			h=tryCombination(c);
			if(h>i||h==-1) r=m;
			else l=m+1;
		}
		res[l]=1-h1;
		res1[l]=i;
		d[l]=1-h1;
	}
	answer(res,res1);
}

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