Submission #106330

#	Time	Username	Problem	Language	Result	Execution time	Memory
106330		Kenzo_1114	Cave (IOI13_cave)	C++14	0 / 100	677 ms	564 KiB

cave

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

int N,resp[MAXN],porta[MAXN],v[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.find(i)!=s.end())	continue;
		v[i]^=1;
	}
}

void exploreCave(int N)
{
	for(int i=0;i<N;i++)
	{
		int ini=0,fim=N-1;
		while(ini<fim)
		{
			int m=(ini==fim-1) ? ini : (ini+fim)/2;
//			debug("ini = %d   fim = %d   m = %d\n",ini,fim,m);
//			debug("Case 1 :\n");
			int case1=tryCombination(v);//		debug("\n");
			if(case1==-1)	case1=MAXN;
			if(case1<=i)
			{
				color(ini,m,v);
				if(tryCombination(v)<=i && tryCombination(v)!=-1)	ini=m+1;
				else{	color(ini,m,v);	fim=m;	}
			}
			else
			{
				color(ini,m,v);
				if(tryCombination(v)<=i && tryCombination(v)!=-1)	fim=m;
				else{	color(m+1,fim,v); ini=m+1;	}
			}
		}
		s.insert(ini);
		porta[ini]=i;
		v[ini]^=1;
//		debug("I = %d v[%d] = %d\n",i,ini,v[ini]);
	}
}
/*
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: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24