Submission #39137

#	Time	Username	Problem	Language	Result	Execution time	Memory
39137		faustaadp	Cave (IOI13_cave)	C++14	100 / 100	387 ms	544 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int i,hz,a[5050],b[5050],l,r,c;
void TO(int aa,int bb)
{
	ll ii;
	for(ii=aa;ii<=bb;ii++)
	{
		if(b[ii]==-1)
		{
			//cout<<"d";
			a[ii]=1-a[ii];
		}
	}
//	cout<<aa<<" "<<bb<<" ";
//	for(ii=0;ii<N;ii++)
//		cout<<a[ii];
//	cout<<"\n";
}
void exploreCave(int N) {
	for(i=0;i<N;i++)
		b[i]=-1;
	for(i=0;i<N;i++)
	{
		l=0;
		r=N-1;
		if(tryCombination(a)!=i)
			TO(0,N-1);
		while(l<r)
		{
			c=(l+r)/2;
			TO(l,c);
			if(tryCombination(a)==i)
				l=c+1;
			else
			{
				TO(l,c);
				r=c;
			}
		}
//		cout<<l<<"l r"<<r<<"\n";
		TO(l,l);
		b[l]=i;
	}
	answer(a,b);
	
}

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