제출 #4477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4477		pichulia	동굴 (IOI13_cave)	C++98	51 / 100	143 ms	512 KiB

cave

#include "cave.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;
		while(l<r)
		{
			m=(l+r)/2;
			for(j=l;j<=r;j++)
			{
				if(sw[j]==-1)
					s[j]=1;
				else
					s[j]=sw[j];
			}
			result1 = tryCombination(s);
			for(j=l;j<=m;j++)
			{
				if(sw[j]==-1)
					s[j]=0;
				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(result1 != i)
			{
				if(result2 == i)
				{
					r=m;
				}
				else
				{
					if(m==l)
						l=m+1;
					else
					l=m;
				}
			}
			else
			{
				if(result2==i)
				{
					if(m==l)
						l=m+1;
					else
					l=m;
				}
				else
				{
					r=m;
				}
			}
		}
	//	printf("%d\n",l);
		s[l] = 0;
		result1 = tryCombination(s); 
		s[l] = 1;
		result2 = tryCombination(s);
		if(result1 == i) sw[l] = 1;
		else sw[l] = 0;

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

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