Submission #4479

#	Time	Username	Problem	Language	Result	Execution time	Memory
4479		pichulia	Cave (IOI13_cave)	C++98	100 / 100	470 ms	520 KiB

cave

#include "cave.h"
#include<stdio.h>

static int sw[5005];
static int de[5005];
void exploreCave(int N) {
	int i, j;
	int l, r, m;
	int s[5005];
	for(i=0; i<N;i++)
	{
		sw[i] = -1;
		s[i] = 1;
		de[i] = -1;
	}
	int result1;
	int result2;
	for(i=0; i<N; i++)
	{
		l=0;r=N-1;
		for(j=0;j<N;j++)
		{
			if(sw[j]==-1)
				s[j]=1;
			else
				s[j]=sw[j];
		}
		result1 = tryCombination(s);
		if(result1 == i)
		{
		for(j=0;j<N;j++)
		{
			if(sw[j]==-1)
				s[j]=0;
			else
				s[j]=sw[j];
		}
		}
		while(l<r)
		{
			m=(l+r)/2;
			for(j=l;j<=m;j++)
			{
				if(sw[j]==-1)
					s[j]^=1;
				else
					s[j]=sw[j];
			}
			result2 = tryCombination(s);

//			for(j=l;j<=r;j++)
//				printf("%d",s[j]);
//			printf("\n");
//			printf("%d %d %d, %d %d\n",l,m,r, result1,result2);

			if(result2!=i)
			{
				l=m+1;
			}
			else
			{
				for(j=l;j<=m;j++)
				{
					if(sw[j]==-1)
						s[j]^=1;
					else
						s[j]=sw[j];
				}
				r=m;
			}
		}
//		printf("%d\n",l);
//		result1 = tryCombination(s);
//		printf("%d ",result1);
		sw[l] = s[l];
		

		de[l] = i;
	}
//	printf("%d\n",tryCombination(sw));
	answer(sw, de);
}

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