제출 #106343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106343		Kenzo_1114	동굴 (IOI13_cave)	C++14	100 / 100	606 ms	640 KiB

cave

#include<bits/stdc++.h>
#include"cave.h"
#define debug(args...)	//fprintf(stderr,args)
using namespace std;
const int MAXN=5010;

int N,resp[MAXN],porta[MAXN],v[MAXN],s[MAXN];
/*
int tryCombination(int v[])
{
	for(int i=0;i<N;i++)	printf("%d ",v[i]);
	printf("\n");
	int a;
	scanf("%d",&a);
	return a;
}*/

void color(int i,int j,int v[])
{
	for(;i<=j;i++)
	{
		if(s[i]==1)	continue;
		v[i]=0;
	}
}

void color2(int i,int j,int v[])
{
	for(;i<=j;i++)
	{
		if(s[i]==1)	continue;
		v[i]=1;
	}
}


void exploreCave(int N)
{
	for(int i=0;i<N;i++)
	{
		int ini=0,fim=N-1,type;
		color(ini,fim,v);
		int case1=tryCombination(v);
		if(case1==i)	type=0;
		else{	color2(ini,fim,v);	type=1;	}
		while(ini<fim)
		{
			int m=(ini==fim-1) ? ini : (ini+fim)/2;
			debug("ini = %d   fim = %d   m = %d\n",ini,fim,m);
			if(type==0)
			{
				color2(ini,m,v);
				int case2=tryCombination(v);
				if(case2>i || case2==-1){	color(ini,m,v);	fim=m;	}
				else 	ini=m+1;
			}
			else
			{
				color(ini,m,v);
				int case2=tryCombination(v);
				if(case2>i || case2==-1){	color2(ini,m,v);	fim=m;	}
				else 	ini=m+1;
			}
		}
		s[ini]=1;
		v[ini]^=1;
		porta[ini]=i;
		debug("I = %d v[%d] = %d\n",i,ini,v[ini]);
	}
	answer(v,porta);
}
/*
int main ()
{
	scanf("%d",&N);
	exploreCave(N);
	for(int i=0;i<N;i++)	printf("%d ",v[i]);
	printf("\n");
	for(int i=0;i<N;i++)	printf("%d ",porta[i]);
	printf("\n");
}*/

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